1.1 命題邏輯 (Propositional Logic)

命題 (Propositions)

==命題是正確或虛假的聲明性句子==

• 命題示例：
  • 月亮是由綠色乳酪製成的。
  • 特倫頓是新澤西州的首府。
  • 多倫多是加拿大的首都。
  • 1 + 0 = 1
  • 0 + 0 = 2
• 不是命題的示例。
  • 坐下！
  • 現在幾點鐘？
  • X + 1 = 2
  • X + Y = Z

命題邏輯 (Propositional Logic)

• 構建命題 (Constructing Propositions)
  • 命題變數：p, q, r, s, …
  • 總是正確的命題用T表示
  • 總是虛假的命題用F表示
  • 複合提案;由邏輯連接和其他命題構造
    • 否定(Negation) ¬
    • 關聯(Conjunction) ∧
    • 無關(Disjunction) ∨
    • 含意(Implication) →
    • 雙條件(Biconditional) ↔

¬ 複合命題:否定 (Compound Propositions: Negation)

∧ 關聯 (Conjunction)

==AND==

∨ 無關 (Disjunction)

==OR==

⊕ "Or"在英文中的涵義 (The Connective Or in English)

→ 含意 (Implication)

==p對，q就應該對==

e.g. 如果p表示"我在家，"q表示"下雨了"，p→q表示"如果我在家，那麼下雨了。
在p→q,p是假設(先行或前提)和q是結論(或後果).

不同方式表示"p→q"

• if p, then q
• if p, q
• q unless ¬p
• q if p
• q whenever p
• q follows from p
• p implies q
• p only if q
• q when p
• p is sufficient(充分) for q
• q is necessary(必須) for p
• a necessary condition for p is q
• a sufficient condition for q is p

逆向、對換和反 (Converse, Contrapositive, and Inverse)

• 從 p→q 產生新的句子
  • q→p ▶ p→q (Converse)
  • ¬q→¬p ▶ p→q (Contrapositive)
  • ¬p→¬q ▶ p→q (Inverse)

e.g.
converse: If I do not go to town, then it is raining.
inverse: If it is not raining, then I will go to town.
contrapositive: If I go to town, then it is not raining.

↔ 雙條件 (Biconditional)

真值表 (Truth Table)

等效命題 (Equivalent Propositions)

使用真值表顯示不等效性 (Using a Truth Table to Show Non-Equivalence)

邏輯運算子的優先順序 (Precedence of Logical Operators)

1. ¬
2. ∧
3. ∨
4. →
5. ↔

1.2 命題邏輯的應用 (Applications of Propositional Logic)

邏輯拼圖1

一個島上有兩種居民，騎士總是說實話，惡棍總是說謊。
你去島上，遇見A和B。
A說"B是騎士"
B說"我們兩個類型相反"

例子：A 和 B 的類型是什麼？
解決方案：

邏輯拼圖2

一個島上有兩種居民，騎士總是說實話，惡棍總是說謊。
你去島上，遇見A和B。
A說"B是騎士"
B說"A是惡棍"

例子：A 和 B 的類型是什麼？
解決方案：

邏輯電路 (Logic Circuits)

• 電子電路
  輸入/輸出信號可以視為 0 或 1
  • 0 表示假
  • 1 表示真
• 複雜的電路由三個基本電路構成，稱為閘門。
  • 逆變器(inverter)（不是gate）獲取輸入位並生成該位的否定
  • 的OR門取兩個輸入位，並生成等效于兩個位的分離的值
  • 的AND門取兩個輸入位，並生成等效于兩個位結合的值
• 通過組合這些基本電路，通過為輸出運算式的每一部分構建電路，然後組合它們，可以生成給定輸入信號的所需輸出，從而構建更複雜的數位電路

1.3 命題等價 (Propositional Equivalences)

語論、矛盾和意外 (Tautologies, Contradictions, and Contingencies)

邏輯等效 (Logically Equivalent)

德摩根定律 (De Morgan’s Laws)

==¬(p∧q)≡¬p∨¬q==
==¬(p∨q)≡¬p∧¬q==

關鍵邏輯等價 (Key Logical Equivalences)

p∧T≡p, p∨F≡p
p∨T≡T, p∧F≡F
p∨p≡p, p∧p≡p
¬(¬p)≡p
p∨¬p≡T, p∧¬p≡F

p∨q≡q∨p, p∧q≡q∧p
(p∧q)∧r≡q∧(p∧r)
(p∨q)∨r≡q∨(p∨r)
(p∨(q∧r))≡(p∨q)∧(p∨r)
(p∧(q∨r))≡(p∧q)∨(p∧r)
p∨(p∧q)≡p
p∧(p∨q)≡p

補充

• DNF
  • ()內連接詞只能有'且' 和'¬'，()外連接時只能有'或'
• CNF
  • ()內連接詞只能有'或'，()外連接時只能有'且'和'¬'