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$ 出現兩次，也不可以跳過內層欄； 每次出現的作用範圍由所屬連接詞決定。

把蘊含寫成析取

例題

為甚麼 $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$ 當成三元連接詞。

從真值到成員關係與量詞

固定元素 $x$ 後，$x\in A$ 和 $x\in B$ 都有確定真值。因此，把前面的邏輯恆等式 應用於每個元素的成員關係，就能證明相應的集合運算恆等式。 對無限定義域使用量詞則不同：有限的命題真值表不能枚舉所有元素。下一頁將用任意元素 和經過檢驗的見證處理這類陳述。

常見錯誤

常見錯誤

只正確一兩行不足夠

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

常見錯誤

不要把 $\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 量詞與否定 做準備。