Home

To be completed!

考點

  • 命題邏輯（Propositional Logic）
  • 邏輯運算（AND, OR, NOT, IMPLIES, IFF）
  • 真值表（Truth Tables）
  • 邏輯等價（Logically Equivalent）
  • 邏輯推論 (即論證)（Inference Rules）
  • 述詞邏輯（Predicate Logic）
  • 量詞（∀, ∃）

  • c for 'it is cold'; r for 'it is rainy'; w for 'it is windy', choose the correct propositional formula for "It is rainy only if it is windy and cold." (p4)

    • r → (w ∧ c)
    • (w ∧ c) → r

    only if 表 →

  • True or False (p5)

    • If 2+2=5, then 1+1=3
    • (1=1 → 2=2) ↔ (2≠2 → 1≠1)
    • 3+2=6 iff 1+1=3
    • If π is a rational number, then the set of integers is uncountable.
    • 前提 false, 所以整句 true
    • iff 為 true ↔ true or false ↔ false, 又第二個 () 前提 false, 所以整句 true
    • 同 A
    • 同 A

  • "x for y" 形式的 condition, find necessary but not sufficient (p7 中央資工)
    => 即找滿足 x→y, 但不滿足 y→x 者

  • 判別是否為 tautology or contradiction 的方法:

    1. truth table
    2. 利用 satisfiable (指能夠代入某組值使整個命題為真) 找反例
    3. 推導出 true or false

  • 命題 (proposition/statement):"If p then q else r" 的 propositional formula 為？(p11)
    Ans: (p → q) ∧ (!p → r) or (p ∧ q) ∨ (!p ∧ r) ，推導如下

(p→q)∧(!p→r)
≡ (!p∨q) ∧ (p∨r) ≡ ((!p∨q)∧p) ∨ ((!p∨q) ∧ r)，分配律
≡ (p∧!p) ∨ (p∧q) ∨ (r∧!p) ∨ (r∧q)，q,r 不可能同時成立
≡ (q∧p) ∨ (!p∧r)
若把 "else r" 去掉，則由 (p ∧ q) ∨ (!p ∧ r) 可以推導成 ~q ∨ p

  • consistent : 指條件們可同時成立，類似 "方程式有解" (p13)

  • p → q ≡ ~q → ~p ≡ ~p ∨ q (p24)

  • 反命題 (inverse): ~p → ~q ≡ 逆命題 (converse): q → p

  • 等價證明常用的性質表: (p27)

對偶∨∧
1. 分配律 (distributive)p ∨ (q∧r) ≡ (p∨q) ∧ (p∨r)p ∧ (q∨r) ≡ (p∧q) ∨ (p∧r)
2. 結合律 (associative)(p∨q) ∨ r ≡ p ∨ (q∨r)(p∧q) ∧ r ≡ p ∧ (q∧r)
3. 交換律 (commutative)p ∨ q ≡ q ∨ pp ∧ q ≡ q ∧ p
4. 吸收律 (absorption)p ∨ (p∧q) ≡ pp ∧ (p∨q) ≡ p
5. 冪等律 (idempotent)p ∨ p ≡ pp ∧ p ≡ p
6. 同一律 (identity)p ∨ F ≡ pp ∧ T ≡ p
7. 控制律 (domination)p ∨ T ≡ Tp ∧ F ≡ F
8. 否定律 (negation)p ∨ ~p ≡ Tp ∧ ~p ≡ F
9. 雙否定律 (double negation)(p) ≡ p
10.De Morgan's law~(p∨q) ≡ ~p ∧ ~q~(p∧q) ≡ ~p ∨ ~q
其它p ↔ q ≡ (p→q) ∧ (q→p)

其中分配律可以擴展如: (p∨a∨b) ∧ (p∨c∨d) ∧ (p∨e∨f) ≡ p ∨ [(a∨b) ∧ (c∨d) ∧ (e∨f)] (p34)

  • ~(p ↔ q) ≡ p ↔ ~q (p29)

  • resolution0 : 以 (p∨q) ∧ (~p∨r) → (q∨r) 為基礎的推論規則。(因為若 p=0, 看 q; 若 p=1, 看 r) (p320)

  • 常用的論證 (argument) 方法 (P38)

名稱true 的前提導出為 true 的結論
1. 肯定律 (modus ponens)(p→q) ∧ (p)∴q
2. 反證法 (modus tollens)(p→q) ∧ (~q)∴~p
3. 矛盾法(~p → F)∴p
4. 三段論證(p→q) ∧ (q→r)∴p→r
5.conjunction(p) ∧ (q)∴p∧q
6.disjunctionp∴p∨q
7.simplication(p ∧ q)∴p
8.(p∨q) ∧ (~q)∴p

  • Let L (x,y) be proposition function "x loves y"，求下面 proposition 的 symbolically. (p51)

    • "There is someone who loves no one besides himself." ∃x∀y\exist{x} \forall{y} (x≠y) → ~L(x,y)

    "有個人不愛自己以外的任何人"

    • "Nobody loves everyone." ∀x∃y\forall{x} \exist{y} ~L(x,y)

    "每人都有不愛之人"
    相當於～[∃x∀y\exist{x} \forall{y} L(x,y)]

  • "There is no maximum integer." ∀x∃y\forall{x} \exist{y} x < y (p53)

    不論 x 多大，都有比 x 大的數。

進度: p58