01.1 命題邏輯與真值表：從推理形式化到 Boole 代數#

1. 為什麼要形式化推理？#

人類自古就在爭論：什麼樣的推理是「正確」的？亞里斯多德在《工具論》中給出三段論：

所有人都會死；蘇格拉底是人；所以蘇格拉底會死。

注意這個論證的有效性與內容無關——把「人」換成「貓」、「會死」換成「有四條腿」，推理結構依然成立。這個觀察是整個邏輯學的起點：推理的有效性取決於形式，而非內容。

然而三段論體系有明顯限制：它只能處理「所有 \(A\) 是 \(B\) 」這類簡單句型，無法處理複合敘述（「且」「或」「若…則…」）。真正讓推理變成「可計算對象」的，是十九世紀兩位人物的工程：

• Augustus De Morgan（1806–1871）提出關係與量詞的雛形，並以代數方式處理邏輯。
• George Boole（1815–1864）在 1847 年出版《邏輯的數學分析》（The Mathematical Analysis of Logic），宣告一個劃時代觀念：邏輯法則可以用代數來表示。1854 年他擴充為《思維法則的研究》（An Investigation of the Laws of Thought），把「思考」轉成符號運算。

Boole 的洞見在於：若把「真」編碼為 \(1\) 、「假」編碼為 \(0\) ，則「且、或、非」恰好對應某種代數運算。這使邏輯從哲學議題轉變為可機械計算的數學結構——這條線最終通向 Claude Shannon（1938）把 Boole 代數用於開關電路，催生數位電腦；也通向 Curry–Howard 對應中「證明即程式」的預告。

2. 命題與邏輯連接詞#

定義 2.1（命題）：一個命題（proposition）是一個或真或假的陳述句，但不能兩者皆是。

• 「台北是台灣的首都」是真命題。
• 「 \(2+2=5\) 」是假命題（仍為命題！命題不必為真）。
• 「 \(x+1=2\) 」不是命題：真偽依 \(x\) 而定，這是 01.2 節謂詞邏輯的課題。
• 「這句話是假的」不是命題：若真則假、若假則真，產生說謊者悖論，真值無法定義。

定義 2.2（邏輯連接詞）：給定命題 \(p, q\) ：

條件式 \(p \to q\) 最常引起誤解：它只在 \(p\) 為真而 \(q\) 為假時為假。當前提為假時，條件式自動為真（稱為 vacuously true）。例如「若月球是起司做的，則 \(2\) 是質數」在古典邏輯中為真。這個「實質條件」定義的好處是讓 \(\neg p \lor q\) 、 \(p \to q\) 、 \(\neg(p \land \neg q)\) 三者邏輯等價，代數操作極為順暢；代價是它與日常語言的因果含義脫鉤。

3. 真值表與 Boole 代數#

3.1 真值表#

含 \(n\) 個變數的公式有 \(2^n\) 列。兩個基本範例：

可見 \(p \to q \equiv \neg p \lor q\) ，且 \((p \to q) \land (q \to p) \equiv p \leftrightarrow q\) 。

定義 3.1：若兩公式在所有賦值下真值相同，稱為邏輯等價，記 \(P \equiv Q\) 。

重要等價律（Boole 代數的公理與恆等式）：

觀察：上表中的等價律與「集合的聯集、交集、補集」運算律（02.1 節）完全同構——這不是巧合。命題與集合之間存在映射： \(\land \leftrightarrow \cap\) 、 \(\lor \leftrightarrow \cup\) 、 \(\neg \leftrightarrow\) 補集、 \(\top \leftrightarrow\) 宇集。這是「同一個抽象結構、多種具體實例」的第一個範例，也是 01.2 節中「邏輯=集合」這條線索的伏筆。

3.2 Boole 代數的定義#

定義 3.2：一個 Boole 代數是集合 \(B\) 配上兩個二元運算 \(\land, \lor\) 、一個一元運算 \(\neg\) ，以及特殊元素 \(0, 1\) ，滿足交換律、分配律、同一律（ \(x \land 1 = x\) ）、補律（ \(x \land \neg x = 0\) ）等公理。

事實上 \(\{0,1\}\) 、任意集合的冪集、命題的真值集合都是 Boole 代數。1847 年 Boole 的原始動機正是「思維法則」；1938 年 Shannon 證明二值 Boole 代數足以描述任何開關電路，邏輯從此成為工程學。

3.3 用 Python 驗證等價律#

from itertools import product

def implies(p, q): return (not p) or q

def check_equivalent(f1, f2, n_vars=2, names=("p", "q")):
    for vals in product([False, True], repeat=n_vars):
        env = dict(zip(names, vals))
        if f1(**env) != f2(**env):
            return False, env
    return True, None

# 驗證 De Morgan 律
demorgan1 = lambda p, q: not (p and q)
expanded  = lambda p, q: (not p) or (not q)
print(check_equivalent(demorgan1, expanded))  # (True, None)

# 驗證 p -> q 與 ~q -> ~p（對換命題）等價
a = lambda p, q: implies(p, q)
b = lambda p, q: implies(not q, not p)
print(check_equivalent(a, b))                 # (True, None)

# 生成完整真值表
for p, q in product([False, True], repeat=2):
    print(p, q, implies(p, q))

這段程式展示 Boole 思想的現代版本：邏輯等價可以由窮舉（ \(2^n\) 次檢查）機械驗證。但注意複雜度： \(n=100\) 時 \(2^{100}\) 列是宇宙時間都算不完的——這個「真值表爆炸」問題正是計算複雜性理論（SAT 問題、P vs NP）的歷史起點之一。

4. 可滿足性與論證有效性#

定義 4.1： - 公式 \(P\) 是恆真式（tautology）若在所有賦值下為真；是矛盾式（contradiction）若在所有賦值下為假。 - \(P\) 是可滿足的（satisfiable）若存在某賦值使其為真。

定義 4.2（論證有效性）：由前提 \(P_1, \dots, P_k\) 推出結論 \(C\) 的論證是有效的，若 \(P_1 \land \cdots \land P_k \to C\) 是恆真式。

定理 4.3（基本推論規則）：

1. 肯定前件（Modus Ponens）： \(p \to q,\ p \vdash q\) 。
2. 否定後件（Modus Tollens）： \(p \to q,\ \neg q \vdash \neg p\) 。
3. 假言三段論： \(p \to q,\ q \to r \vdash p \to r\) 。
4. 選言三段論： \(p \lor q,\ \neg p \vdash q\) 。

證明（以 Modus Tollens 為例）：假設 \(p \to q\) 為真且 \(\neg q\) 為真。若 \(p\) 為真，由條件式真值表得 \(q\) 為真，與 \(\neg q\) 矛盾。故 \(p\) 為假，即 \(\neg p\) 為真。 \(\blacksquare\)

常見謬誤（務必區分）： - 肯定後件： \(p \to q,\ q \vdash p\) ——無效。雨後地濕；現在地濕，不代表下過雨。 - 否定前件： \(p \to q,\ \neg p \vdash \neg q\) ——無效。同例：沒下雨不代表地不濕（可能有人灑水）。

5. 範例：電路與程式的邏輯#

範例 5.1（電路簡化）：某警報器在「門開 ( \(D\) ) 且未輸入密碼 ( \(\neg C\) )」或「窗開 ( \(W\) ) 且未輸入密碼」時響起：

由分配律化簡為 \((D \lor W) \land \neg C\) ——硬體上省下一個 NOT 閘與一次接線。Boole 代數的價值正在此：邏輯等價 = 電路成本優化。

範例 5.2（程式條件句）：Python 的短路求值即蘊含直觀意義：

def is_adult(age: int) -> bool:
    return age is not None and age >= 18
    # 若 age is None，後半不執行 —— 短路避免 TypeError
    # 這正是 "p -> q" 在防禦性編程的體現

範例 5.3（SAT 問題初窺）：給定 \(\neg(p \land q) \land (p \lor r)\) ，求可滿足賦值。窮舉可得 \((p,q,r)=(T,F,T)\) 等。現代工業 SAT solver 可處理數萬變數，其應用涵蓋晶片驗證、排程、密碼協議分析——全部起源於本節的 \(2^n\) 真值表。

6. 歷史銜接：Boole 之後的深水區#

Boole 之後，Frege（1879）《概念文字》引進量詞與更強的語法，想證明算術可由純邏輯推出（邏輯主義）；Russell 1902 年寫信告訴 Frege：他發現了羅素悖論（詳見 02.1 節），樸素的邏輯—集合體系崩潰。Hilbert 因此提出綱領：把全部數學形式化並證明其一致性。1931 年 Gödel 證明不完備定理，證明 Hilbert 綱領原目標不可能；但形式化的副產品——證明可被編碼——反而催生了可計算性理論、Curry–Howard 對應（命題即型別、證明即程式）與現代型別系統。

命題邏輯正是這個宏大敘事的第一層：它把「推理」變成符號運算。但它還不夠強——「所有質數大於 1」這類敘述必須拆解到個體與性質的層次，這是下一節謂詞邏輯的任務。

7. 習題#

1. 用真值表證明： \(\neg(p \to q) \equiv p \land \neg q\) 。並解釋為何「若下雨則地濕；現在地不濕，故沒下雨」有效，但「若下雨則地濕；現在地濕，故下雨」無效。
2. 將「除非你登入，否則無法下載」翻成條件式命題，並寫出否定形式。
3. 用分配律與 De Morgan 律化簡 \(((p \to q) \to p) \to p\) ，並判斷是否為恆真式。
4. 寫 Python 程式驗證 \(((p \lor q) \land \neg p) \to q\) 是恆真式。
5. 三個開關控制一盞燈：燈亮當且唯當恰有奇數個開關打開。寫出其 Boole 表達式並化簡。

8. 小結與下一步#

• 命題邏輯把推理化為符號運算，有效性取決於形式。
• Boole (1847, 1854) 證明邏輯是一種代數；Shannon (1938) 證明它就是數位電路的數學。
• 等價律（De Morgan、分配、對偶）與集合運算律同構，預示「結構」比「符號」更根本。
• 條件式的實質蘊含定義支撐起整個證明方法學（01.3 節）。

下一步：命題邏輯視命題為不可拆的原子。但數學命題「存在偶質數」含有主詞、述詞與量詞的內部結構。01.2 節引進**謂詞、變數與量詞 \(\forall, \exists\) **，達到與所有數學敘述兼容的精確語法，並在此語法上重演 Frege 到 Russell 的危機。