1.1 命題邏輯

邏輯先從已經足夠完整、可以判斷真假的陳述開始。這個分別很重要： 一旦句子還未封閉，就不可以當作命題處理。

命題與真假值

定義

命題

命題是一個有確定真假值的陳述。它不是真，就是假，沒有第三種情況。

這個定義的目的不是令邏輯變得抽象，而是分清楚哪些句子已經可以檢驗， 哪些句子還未完整。

例子：

• $2 + 2 = 4$ 是命題。
• 每個偶數都可以被 2 整除 是命題。
• 請打開門。 不是命題，因為它是命令。
• 若未指定 $x$，$x + 1 = 3$ 還未是命題。

常見錯誤

含有自由變量的公式不會自動變成命題

如果句子的真假仍然依賴未指定的變量，那麼它仍然是開放句，不是完整陳述。 要先賦值，或者之後用量詞綁定它。

例題

判斷哪些句子是命題

考慮以下三句：

1. $7$ 是質數。
2. $x + 1 = 3$。
3. 請交功課。

第 1 句是命題，而且是真。第 2 句不是命題，因為要看 $x$ 取甚麼值：$x = 2$ 時為真，$x = 0$ 時為假。第 3 句不是命題，因為它是請求，不是主張。相反，在 實數範圍內，$x^2 + 1 > 0$ 對每個實數 $x$ 都為真，但在為 $x$ 賦值或用量詞 綁定之前，它仍然是開放句。

邏輯分析只可以在句子足夠完整時開始。未封閉的句子，不適合直接做真值表分析。

布林字母表

課程反覆用到五個連接詞：

這些不是純粹的口語縮寫，而是邏輯語言的基本符號，用來拼出更複雜的陳述。

優先次序只有部分規定：

1. $¬$
2. $∧$ 與 $∨$ 處於同一層級
3. $→$ 同 $↔$

$∧$ 與 $∨$ 之間沒有先後，所以同時出現時一定要加括號。下面例子直接展示這個問題：

例題

先解析，再閱讀

字串 $¬A ∧ B ∨ C$ 有兩種可能讀法：

$$\neg A \land B \lor C$$

它可以表示 $(¬A ∧ B) ∨ C$，即 $A$ 假而 $B$ 真，或者 $C$ 真；亦可以表示 $¬A ∧ (B ∨ C)$，即 $A$ 假而 $B$、$C$ 至少一個為真。這是兩條不同公式。

如果你想表達其他意思，就一定要明確加括號。

邏輯公式是精確對象。括號不是裝飾，而是決定句子真正內容的一部分。

語法、作用域與真值函數

良構公式用遞歸方式生成。原子命題 $A$ 是公式；如果 $φ$ 是公式，$¬φ$ 也是 公式，而且 $¬$ 恰好只有一個運算對象。如果 $φ$、$ψ$ 是公式，那麼 $(φ ∧ ψ)$、$(φ ∨ ψ)$、$(φ → ψ)$、$(φ ↔ ψ)$ 都是公式，每個二元連接詞恰好 需要兩個完整運算對象。因此 $P ∧ ∨ Q$ 不是公式。

$A → B ∧ ¬C$ 沒有歧義：先算 $¬$，再算 $∧$，最後算 $→$， 所以是 $A → (B ∧ ¬C)$。同樣，$¬A ↔ B ∨ C$ 是 $¬A ↔ (B ∨ C)$，因為 $∨$ 在 $↔$ 之前計算。雙條件比較 $¬A$ 同 $B ∨ C$ 的真假值，並不是將整個析取式否定。

為原子命題指定 $T$ 或 $F$ 之後，每個連接詞都可以按照直接運算對象的值定出一個 結果；所以同一個賦值總會給同一條公式同一個真值。這就是公式的 truth function， 而真值表就記錄它的全部輸入同輸出。

真值表與邏輯等價

當你知道各個命題的真假值之後，就可以計算複合公式的真假。真值表就是用來記錄這件事。

定理

常用等價式

以下幾條等價式是基本工具，應該盡量熟記：

$$P → Q \equiv ¬P ∨ Q$$$$P ↔ Q \equiv (P → Q) ∧ (Q → P)$$$$¬(P ∧ Q) \equiv ¬P ∨ ¬Q$$$$¬(P ∨ Q) \equiv ¬P ∧ ¬Q$$$$¬¬P \equiv P$$

這些不是哲學命題，而是真值表恒等式。

例題

用真值表檢查蘊含

$P → Q$ 只會在一種情況下為假：$P$ 真而 $Q$ 假。其餘情況都為真。

$P$	$Q$	$P → Q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

所以 $P → Q$ 不是話 $P$ 同 $Q$ 都真，而是排除咗「前件真、後件假」這種情況。

許多人會將 $P → Q$ 讀成因果句。在邏輯之中，它不是故事式的因果，而是真值條件。

推理規則

課程之中會反覆用到幾種有效推理模式。

定理

常見推理模式

如果 $P → Q$ 同 $P$ 都真，那麼 $Q$ 一定真。這個叫 modus ponens。

如果 $P → Q$ 同 $¬Q$ 都真，那麼 $¬P$ 一定真。這個叫 modus tollens。

如果 $P → Q$ 同 $Q → R$ 都真，那麼 $P → R$ 都真。這個叫 hypothetical syllogism。

如果 $P ∨ Q$ 同 $¬P$ 都真，那麼 $Q$ 一定真。這個叫 disjunctive syllogism。

這些模式之所以重要，是因為它們似乎合法運算：前提真，結論就一定真。

例題

一條有效的推理鏈

假設你知道

$$A → B,\qquad B → C,\qquad A.$$

你可以先由第一同第三句推出 $B$，再由第二句推出 $C$。

所以結論 $C$ 由前提邏輯上跟得出。

這個是 modus ponens 用兩次：先由 $A$ 推 $B$，再由 $B$ 推 $C$。

常見錯誤

不好混淆有效同無效模式

由 $P → Q$ 同 $Q$，你不可以推出 $P$。這個謬誤叫 affirming the consequent。

由 $P → Q$ 同 $¬P$，你不可以推出 $¬Q$。這個謬誤叫 denying the antecedent。

否定前件的反模型

對論證 $P → Q$、$¬P$，所以 $¬Q$，取 $P = F$、$Q = T$。因為前件為假， 蘊含式為真；$¬P$ 亦為真；但 $¬Q$ 為假。這個賦值同時滿足兩個前提而否定結論， 所以論證無效。

將條件翻譯成公式

布林字母代表一個完整命題，連接詞就記錄完整命題怎樣組合。因此，翻譯英文句子要 分兩步：先說明每個字母代表甚麼，再按原句的範圍選擇連接詞同括號。

例題

必要條件與充分條件

令 $D$ 表示「這個整數可以被 4 整除」，令 $E$ 表示「這個整數是偶數」。 「被 4 整除是成為偶數的充分條件」翻譯為 $D → E$。同一個關係亦可以說成 「偶數是被 4 整除的必要條件」：只要 $D$ 成立，$E$ 就必須成立。措辭次序改變了， 但箭咀仍然由被假定的條件指向必然跟隨的條件。

逆命題 $E → D$ 是另一條斷言，原句沒有支持它。2 是反例：2 是偶數，但不可以被 4 整除。

因為 $∧$ 與 $∨$ 在課程約定中處於同一層級，$A ∧ B ∨ C$ 有歧義。要表達「$A$ 同 $B$，或者 $C$」，寫 $(A ∧ B) ∨ C$；要表達「$A$，而且 $B$ 或 $C$」，寫 $A ∧ (B ∨ C)$。兩條公式可能在同一個賦值下給出不同真假值，所以一定要先確定分組。

有效性到底問甚麼

論證由前提與結論組成。當每一個令全部前提為真的賦值都同時令結論為真，論證就是 有效。這是在說公式之間的關係，並不是說前提在現實中一定是真的。

定理

用被禁止的一行檢查有效性

對前提 $P_1, ..., P_n$ 和結論 $Q$，找一行：所有 $P_i$ 都真而 $Q$ 是假。找到這一行， 就是反模型，論證無效；找不到，論證有效。等價地，公式

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

是一條永真式。

例題

肯定後件的反模型

以前提 $P → Q$ 同 $Q$ 推出結論 $P$。取 $P = F$、$Q = T$：因為前件為假，$P → Q$ 為真；第二個前提 $Q$ 亦為真；但結論 $P$ 為假。所以一行已經足以否定有效性。 前提為假的行不能做到這點，因為有效性只要求檢查全部前提都成立的行。

這亦解釋了邏輯等價同推理有效性不可混為一談。$φ ≡ ψ$ 表示兩個公式每一行都有 相同真假值；「$φ$，所以 $ψ$」只要求沒有 $φ$ 真而 $ψ$ 假的行。只要 $φ → ψ$ 是 永真式，推理就有效；除非 $ψ → φ$ 亦是永真式，否則反向推理未必有效。

否定及化簡命題

否定作用於它範圍內的整個命題。要否定「$P$ 同 $Q$」，應該寫 $¬(P ∧ Q)$，不可以 直接寫 $¬P ∧ ¬Q$；用德摩根律後才得到等價式 $¬P ∨ ¬Q$。同樣，$¬(P → Q)$ 只在 蘊含唯一為假的一行成立，所以

$$¬(P → Q) \equiv P \land ¬Q.$$

例題

改寫被否定的蘊含式

先用 $A → B ≡ ¬A ∨ B$，再逐步用德摩根律及雙重否定：

$$¬(A → B) \equiv ¬(¬A ∨ B) \equiv ¬¬A \land ¬B \equiv A \land ¬B.$$

最後的公式正好表示前件真而後件假，也就是蘊含失敗的條件。

這種改寫是受控制的化簡程序：先移除蘊含，再用德摩根律把否定推入合取或析取，最後 消去雙重否定。每一步都是等價變形，所以前後公式定義同一個真值函數。

由語法到意思的檢查

寫好公式之後，還要分開檢查語法與意思。語法檢查問：每個連接詞兩邊是否都是完整公式， 括號是否配對，優先次序是否造成預期結構。意思檢查問：在指定真假賦值之下，是否按照 連接詞定義算出唯一結果。前一個問題防止將開放句當成命題，後一個問題防止將口語的 「如果」誤讀成因果關係。

例題

同一組原子命題的不同結構

令 $A$ 表示「今天下雨」，$B$ 表示「地面濕」，$C$ 表示「我帶傘」。公式 $(A → B) ∧ C$ 要求兩個部分都真；公式 $A → (B ∧ C)$ 則只在下雨時要求地面濕以及 帶傘。取 $A = F,\,B = F,\,C = T$，前一條公式是真，後一條公式亦是真；再取 $A = T,\,B = T,\,C = F$，兩條都假。要找到它們真的不同的賦值，取 $A = F,\,B = T,\,C = F$：前者仍然是假，後者卻是真。這顯示括號決定連接詞的作用範圍， 不是只改變符號排列。

如果題目問「能否由前提推出結論」，就要分開寫前提與結論，再尋找全部前提為真而 結論為假的行。如果題目問「兩條公式是否等價」，就必須比較兩條完整的最後一欄；只找到 一行相同沒有證明作用。先辨認題型，可以避免用等價證明取代有效性證明。

蘊含、反模型與證明方向

蘊含不宣稱前件為真，也不表示因果關係。它的真值條件恰好排除前件真而後件假的賦值。逆命題反轉箭頭；逆否命題還同時否定兩端。

逆否命題的推導

$P\to Q$ 等價於 $\neg P\lor Q$。逆否命題 $\neg Q\to\neg P$ 等價於 $\neg\neg Q\lor\neg P$，即 $Q\lor\neg P$；交換律又給出原來的析取式。因此 兩者在每個賦值下都等價。

例題

區分逆命題與逆否命題

令 $P$ 表示「正在下雨」，$Q$ 表示「地面是濕的」。逆命題 $Q\to P$ 表示地面濕就 一定下雨；灑水器可以令地面濕而沒有下雨，所以這是另一條可能失敗的斷言。逆否命題 $\neg Q\to\neg P$ 表示地面乾就沒有下雨，並且與原來的蘊含式等價。

Modus tollens 要檢查兩個前提

假設 $P\to Q$ 同 $\neg Q$ 都真。第二個前提迫使 $Q=F$；若 $P=T$，第一個前提便 為假。因此 $P=F$，即 $\neg P$。排除 $(T,F)$ 這一行的是第一個前提；檢驗有效性時 必須保留每個前提。

快速檢查

思考檢查

按課程約定，$¬A ∧ B ∨ C$ 是否沒有歧義？如果有，請寫出兩種括號方式。

記住 $¬$ 最先，而 $∧$ 與 $∨$ 處於同一優先層級。

解答 · 答案

它有歧義。兩種括號方式是 $(¬A ∧ B) ∨ C$ 和 $¬A ∧ (B ∨ C)$。

思考檢查

$P → Q$ 同 $¬P ∨ Q$、$P ∧ Q$，邊個等價？

看蘊含的真假條件。

解答 · 答案

$¬P ∨ Q$ 同 $P → Q$ 等價。

思考檢查

推理 $P → Q$、$Q$，所以 $P$ 有效嗎？

試想 $P$ 其實是假的情況。

解答 · 答案

無效。這個謬誤叫 affirming the consequent。

探索真值條件

用互動表試驗你自己寫出來的公式。

下一步：計算真值表

繼續閱讀 1.2 真值表與邏輯等價，把本節的語法和真值規則組織成檢驗公式的完整方法。