1.2 真值表與邏輯等價

這一節會把命題公式變成可以逐步計算的對象。當原子命題一旦固定之後， 真值表就可以透過檢查所有可能真假指派，去判斷一個複合公式到底是真定假。

這件事聽落似乎機械，但其實數學意義好清楚：如果一個公式只牽涉 $n$ 個命題變數，就只會有 $2^n$ 種真假配置。真值表正正是把全部情況列全部出來， 所以不會有遺漏的情況。

真值表記錄甚麼

定義

真值表

一個命題公式 $\varphi$ 的 真值表，會列出 $\varphi$ 之中所有變數的 每一種真假指派，並記錄 $\varphi$ 在每一行的真假值。

例如，如果公式只涉及 $P$ 同 $Q$，那麼就有四行：

$$(T,T), \quad (T,F), \quad (F,T), \quad (F,F).$$

所以真值表不只是一張表，而是一個完整的分類討論。

逐行建立真值表的程序

一張可靠的真值表要有清楚的行次序同欄次序。若有 $n$ 個原子變數，就列出 $2^n$ 行，並由頭到尾保持同一個次序。例如三個變數可以依次列作 TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF。之後每一個子公式增加一欄，先計 最內層的連接詞，最後先計整條公式。沒有中間欄，最後一欄就好難檢查。

例題

分步建立 $(A ∨ B) → C$

先計算 $A ∨ B$，再將這一欄作為蘊含式的前件：

$A$	$B$	$C$	$A ∨ B$	$(A ∨ B) → C$
T	T	T	T	T
T	T	F	T	F
T	F	T	T	T
T	F	F	T	F
F	T	T	T	T
F	T	F	T	F
F	F	T	F	T
F	F	F	F	T

最後一欄只會在已算出的前件為真而 $C$ 為假時為假。這裏有三個獨立變數，所以張表 有八行。

巢狀蘊含都要跟同一原則。在 $A → (B → A)$ 中，先計內層 $B → A$。按 $TT, TF, FT, FF$ 次序，它的四個值是 $T, T, F, T$；再計外層蘊含，得到 $T, T, T, T$，所以公式是永真式。即使 $A$ 出現兩次，也不可以跳過內層欄； 每次出現的作用範圍由所屬連接詞決定。

定理

每個賦值定出一個最終真值

為原子命題指定真假賦值之後，遞歸真值規則會為每一條良構 Boolean 公式定出唯一值。 因此，行次序相同而且計算正確的兩張表必須有相同的最後一欄。如果結果不同，就表示 解析或計算出錯，而不是同一條公式有兩個真值。

一個最重要的等價式

例題

為甚麼 $P \to Q$ 同 $\neg P \lor Q$ 是同一句意思

考慮公式 $P \to Q$ 同 $\neg P \lor Q$。

$P$	$Q$	$\neg P$	$P \to Q$	$\neg P \lor Q$
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

最後兩列逐行完全一致。

因此

$$P \to Q \equiv \neg P \lor Q.$$

這個等價式在初等邏輯之中非常重要。它說明咗蘊含式只會在「前件真、 後件假」那一行失敗。

邏輯等價

定義

邏輯等價

如果兩個公式 $\varphi$ 同 $\psi$ 在所有變數指派之下都得到相同真假值， 就話它們 邏輯等價，記作

$$\varphi \equiv \psi.$$

邏輯等價比「剛好在某個例子一致」強得多。它表示兩個公式其實定義咗同一個 truth function。

這裏需要特別留意，以下兩種寫法不可以混為一談：

• $\varphi \leftrightarrow \psi$ 是一個新的 Boolean 公式；
• $\varphi \equiv \psi$ 是一個關於兩個公式的陳述。

兩者有關，但不是同一樣嘢。

定理

等價同雙條件

兩個公式 $\varphi$ 同 $\psi$ 邏輯等價，當且僅當

$$\varphi \leftrightarrow \psi$$

是一個永真式。

所以雙條件可以視為檢查工具：如果它的最後一列全部都是真，那麼兩個公式就 在每一行都一致。

永真式、矛盾式與偶然式

定義

三種基本類型

設 $\varphi$ 是一個命題公式。

• 如果 $\varphi$ 在每一行都真，它就是 永真式。
• 如果 $\varphi$ 在每一行都假，它就是 矛盾式。
• 如果 $\varphi$ 有些行真、有些行假，它就是 偶然式。

標準例子是：

$$P \lor \neg P$$

它是永真式；而

$$P \land \neg P$$

就是矛盾式。

這個區分好重要，因為許多簡短邏輯論證本質上都是證明某個公式永遠真， 或者永遠假。

第二個例題

例題

用真值表檢查 De Morgan 定律

我們檢查

$$\neg(P \lor Q) \equiv (\neg P) \land (\neg Q).$$

$P$	$Q$	$P \lor Q$	$\neg(P \lor Q)$	$\neg P$	$\neg Q$	$(\neg P) \land (\neg Q)$
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

第四欄同第七欄逐行一致，所以兩個公式邏輯等價。

這個例子顯示咗真值表的典型用途：不只是計某一個公式，而是證明一條等價律。

把論證化成一個真值表欄

定理

檢驗有限命題推論

對前提 $P_1,\ldots,P_n$ 和結論 $Q$，其中 $n\ge1$，論證有效當且僅當

$$(P_1\land\cdots\land P_n)\to Q$$

是永真式。這個蘊含式恰好在全部前提真而結論假時為假，這正是反模型。含有假前提的行不能否定論證的有效性。

例題

比較兩組前提

以前提 $P\to Q,P$ 推出 $Q$，檢驗式為 $((P\to Q)\land P)\to Q$。兩個前提同時為真的唯一一行是 $P=T,Q=T$，該行結論也真；其餘各行的外層前件為假，外層蘊含式仍真。若改以前提 $P\to Q,Q$ 推出 $P$，檢驗式就在 $P=F,Q=T$ 處失敗。改變前提就是改變所檢驗的論證。

例題

替換等價的內部部分

在 $R\land(P\to Q)$ 中，以 $\neg P\lor Q$ 替換 $P\to Q$。對任意賦值，兩個內部表達式真值相同，與同一個 $R$ 合取後的結果也相同。因此 $R\land(P\to Q)\equiv R\land(\neg P\lor Q)$；外層連接詞及其作用域保持不變。

受控的改寫過程

前面介紹的等價式亦提供一套可以審查的改寫方法。先將每個雙條件替換成 $(P → Q) ∧ (Q → P)$，再用 $P → Q ≡ ¬P ∨ Q$ 替換所有蘊含；用德摩根律將 否定推入內層；消去雙重否定；需要重新分組時使用分配律。例如：

$$¬(P → (Q ∧ R)) \equiv ¬(¬P ∨ (Q ∧ R)) \equiv P ∧ ¬(Q ∧ R) \equiv P ∧ (¬Q ∨ ¬R).$$

每一行都用邏輯等價式替換，所以最後一欄的真假值保持不變。這樣做的好處是令只 有 $¬$、$∧$、$∨$ 的子公式更加清楚，方便建立中間欄。這些等價式支持改寫，但仍然 要檢查原公式的作用範圍。這裏把只用 $¬$、$∧$、$∨$，而每個 $¬$ 直接作用於原子 命題的形式稱為否定範式；它是方便造表的目標，不是將所有證明都化成改寫。

例題

等價同蘊含不是同一回事

$P ∧ Q$ 同 $P$ 不等價：當 $P = T,\,Q = F$ 時，前者是假而後者是真。不過，論證 「$P ∧ Q$，所以 $P$」是有效的，因為沒有前提真而結論假的一行。相應的檢驗式 $(P ∧ Q) → P$ 是永真式。所以，等價要求兩條公式每一列都相同，而推論只要求 不存在被禁止的前提真、結論假那一行。

用表格回答不同類型的問題

同一張表可以回答不同問題，但讀法一定要配合題目。要判斷公式類型，只看自己的最後一欄： 全真是永真式，全假是矛盾式，真假都有是偶然式。要判斷兩條公式是否等價，就逐行比較 兩條最後欄。要判斷論證是否有效，則只圈出全部前提為真的行，再看這些行的結論；前提 為假的行不會成為反模型。

所以做題時應先在紙上寫清楚目標是「公式類型」、「公式等價」還是「論證有效性」，再 決定比較哪一欄。一張表可能包含足夠資料，但如果讀錯問題，仍然會得到錯誤結論。

交換律、結合律與分配律

以下真值表等價式適合在改寫公式時使用：

$$A \land B \equiv B \land A,\qquad A \lor B \equiv B \lor A$$ $$A \land (B \land C) \equiv (A \land B) \land C,\qquad A \lor (B \lor C) \equiv (A \lor B) \lor C$$ $$A \lor (B \land C) \equiv (A \lor B) \land (A \lor C),\qquad A \land (B \lor C) \equiv (A \land B) \lor (A \land C).$$

交換律容許交換兩個運算對象。結合律容許在重複使用同一個連接詞時改變括號。 分配律則改變連接詞結構，產生展開步驟。例如：

$$R \lor (P \land Q) \equiv (R \lor P) \land (R \lor Q).$$

在較大的公式中使用這個步驟時，先找出完整的左側模式，用右側模式替換，再繼續 計算新的子公式。每一行的最終真假值都保持不變，因為上面每個式子都是由真值表 驗證的等價式。

從真值表的模式到邏輯恆等式

交換律雙條件是永真式：

$(A → B) ∨ (B → A)$ 亦是永真式。當 $A$ 真而 $B$ 假時， $B → A$ 為真；當 $A$ 假而 $B$ 真時，$A → B$ 為真；當真假相同時，兩個蘊含式都真。

以下兩個雙條件在每一行的值相同：

因此 $A ↔ B ≡ ¬A ↔ ¬B$。這是關於兩條公式的陳述，不是說 $↔$ 同 $≡$ 是同一個 連接詞。

例題

完整計算 $(P ∧ Q) → P$

$(P ∧ Q) → P$ 的完整表如下：

$P$	$Q$	$P ∧ Q$	$(P ∧ Q) → P$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

最後一欄全真，所以它是永真式，論證「$P ∧ Q$，所以 $P$」有效；這不表示 $P ∧ Q$ 同 $P$ 等價，它們在 $P = T,\,Q = F$ 時仍然不同。

雙條件的否定與循環蘊含

$P ↔ Q$ 的否定恰好在兩個值不同時為真：

$$\neg(P \leftrightarrow Q) \equiv (P \land \neg Q) \lor (\neg P \land Q).$$

這是列出雙條件為假的兩行後得到的「互異」條件。

對於循環蘊含，應避免使用有歧義的鏈式記號。三個蘊含 $A → B$、$B → C$、 $C → A$ 迫使三個原子命題的真假值一致，因此精確的等價條件是

$$(A \leftrightarrow B) \land (B \leftrightarrow C).$$

這個明確合取寫出了需要的兩個雙條件；不可以把 $A ↔ B ↔ C$ 當成三元連接詞。

為甚麼這一節之後還有用

真值表不是邏輯課程的終點，但它訓練兩個一直也會用的習慣：

• 把語法與意思分開處理；
• 檢查「所有情況」而不是只看一兩個例子。

之後學量詞、集合同證明時，這種完整分類討論的要求會以更成熟的形式再出現。

常見錯誤

常見錯誤

只正確一兩行不足夠

如果兩個公式只是在某一行，甚至幾行之中一致，也不足以證明等價。 等價要求的是所有可能指派都一致。

常見錯誤

不好把 $\leftrightarrow$ 同 $\equiv$ 視為同一個符號

$\varphi \leftrightarrow \psi$ 是放入真值表裏面計算的公式。 $\varphi \equiv \psi$ 就是說明兩個公式定義同一個 truth function 的陳述。

讀到這裏，試一試

小檢查

思考檢查

如果一個公式涉及三個命題變數，真值表要有幾多行？

用真假配置數量的規則回答。

解答 · 答案

要有 $2^3 = 8$ 行，因為三個變數都可以各自獨立取真或假。

思考檢查

為甚麼 $P \lor \neg P$ 是永真式？

逐行情況回答，不好只背結論。

解答 · 答案

如果 $P$ 真，那麼 $P \lor \neg P$ 因為左邊真而成立；如果 $P$ 假， 那麼 $\neg P$ 真，所以析取仍然成立。每一行都是真，因此它是永真式。

思考檢查

$P \land Q$ 同 $P \lor Q$ 是否邏輯等價？

指出至少一行令它們表現不同。

解答 · 答案

不是。例如當 $P = T$、$Q = F$ 時，有 $P \land Q = F$， 但 $P \lor Q = T$。兩者在這一行不一致，所以不等價。

繼續學習量詞

這一頁直接承接 1.1 命題邏輯，並且為 1.3 量詞與否定 做準備。