Table of contents

命題與連接詞

定義 1.1.1 命題邏輯的語言

命題邏輯的語言由下列符號組成：

1. 命題符號：$p_0$, $p_1$, $p_2$, …，
2. 連詞：$\vee$, $\wedge$, $\rightarrow$, $\neg$, $\leftrightarrow$, $\bot$，
3. 輔助符號：$($, $)$。

定義 1.1.2 命題集合 $PROP$

命題集合 $PROP$ 是符合下述性質的最小集合 $X$：

1. $p_i \in X(i \in N)$ 且 $\bot\in X$，
2. $\phi,\psi \in X \Rightarrow (\phi\vee\psi), (\phi\wedge\psi), (\phi\rightarrow\psi), (\phi\leftrightarrow\psi) \in X$，
3. $\phi\in X\Rightarrow(\neg\phi)\in X$。

註：

1. $p_i$ 和 $\bot$ 稱為原子命題（atomic proposition），構成的集合定義為 $ATOM$。
2. 「$\Rightarrow$」是表達「若…則…」的後設邏輯語言，$\phi, \psi$ 是表達集合成員的後設邏輯語言。
3. 這裡「最小」的意義是集合的最小，即 $PROP$ 包含於所有滿足上述性質的集合。
4. $\bot$ 為集合中的邏輯常數（logic constant）。
5. 輔助符號不可省略。
6. 這三項性質定義了三種顯然排他的形式。

定理 1.1.3 歸納法原理

令 $A$ 是一個性質，若下述條件成立，則：若 $\phi \in PROP$，$A(\phi)$ 成立。

1. 對於任意 $i$，$A(p_i)$，
2. $A(\bot)$，
3. $A(\phi), A(\psi) \Rightarrow A((\phi \square \psi))$，$\square \in \{ \vee, \wedge, \rightarrow, \leftrightarrow \}$，
4. $A(\phi) \Rightarrow A((\neg \phi))$。

證明：

1. $X = \{ \phi \in PROP | A(\phi)\}$，$X \subset PROP$。
2. $X$ 滿足 1.2 的所有性質，因此 $PROP \subset X$。

註：往後，當我們將 $\square$ 用於二元連接詞時，表示所有二元連接詞的統稱，不再另外說明。

定義 1.1.4 構成序列 formation sequence

序列 $\langle \phi_i | i \leq n \rangle$ 稱為 $\phi$（$= \phi_n$）的構成序列，意思是，對於所有 $i$，滿足：

1. $\phi_i \in ATOM$，或
2. $\phi_i = (\phi_j \square \phi_k)$，$j,k<i$，或
3. $\phi_i = (\neg \phi_j)$，$j<i$。

定理 1.1.5 構成序列與命題的充要條件

$PROP$ 是所有有構成序列的表達式的集合。

證明：以 1.3 歸納法原理證明這個集合滿足 1.2 定義的所有性質。

定理 1.1.6 遞迴定義 recursive definition

令 $H_\square: A^2 \rightarrow A$、$H_\neg: A \rightarrow A$、$H_{at}: ATOM \rightarrow A$，則存在滿足下述條件唯一的 $F: PROP \rightarrow A$：

1. $F(\phi) = H_{at}(\phi)$，對所有 $\phi \in ATOM$，
2. $F((\phi \square \psi)) = H_\square(F(\phi), F(\psi))$，
3. $F((\neg \phi)) = H_\neg(F(\phi))$。

證明：

1. 存在性證明：以 1.3 歸納法原理證明對於所有的命題 $F$ 都定義完善。
2. 唯一性證明：以 1.3 歸納法原理證明，對於任一滿足上述條件的 $G: PROP \rightarrow A$，則 $G = F$。

例子：

語句的剖析樹（parsing tree）因此是合法且唯一的。

語句 $\phi$ 的秩（rank） $r(\phi)$ 因此也是合法且唯一的：

1. $r(\phi) = 0$，若 $\phi \in ATOM$，
2. $r((\phi \square \psi)) = \max(r(\phi), r(\psi)) + 1$，
3. $r((\neg \phi)) = r(\phi) + 1$。

語句 $\phi$ 的子構句（subformula）的集合 $Sub(\phi)$ 因此也是合法且唯一的：

1. $Sub(\phi) = \{ \phi \}$，若 $\phi \in ATOM$，
2. $Sub((\phi \square \psi)) = Sub(\phi) \cup Sub(\psi) \cup \{ (\phi \square \psi) \}$，
3. $Sub((\neg \phi)) = Sub(\phi) \cup \{ (\neg \phi) \}$。

定理 1.1.7 秩的歸納法原理

對於任意 $\phi \in PROP$，若滿足下述條件，則 $A(\phi)$ 成立：

• 若對於所有滿足 $r(\psi) < r(\phi)$ 的 $\psi$，$A(\psi) \Rightarrow A(\phi)$。

證明：不難證明 1.7 的歸納法原理與 1.3 歸納法原理等價。

語義學 semantics

從本節開始，我們開始省略輔助符號。並且，由於語義學定理大多可以歸納法證明，我在此也將略過不提。

定義 1.2.1 賦值函數

$v: PROP \rightarrow \{0,1\}$ 稱為賦值函數（valuation function），意思是對於所有 $\phi, \psi \in PROP$，滿足下述條件：

1. $v(\phi \wedge \psi) = \min(v(\phi), v(\psi))$，
2. $v(\phi \vee \psi) = \max(v(\phi), v(\psi))$，
3. $v(\phi \rightarrow \psi) = \max(1 - v(\phi), v(\psi))$，
4. $v(\phi \leftrightarrow \psi) = 1 - |v(\phi) - v(\psi)|$，
5. $v(\neg \phi) = 1 - v(\phi)$。
6. $v(\bot) = 0$。

定理 1.2.2 賦值函數的唯一性

對原子命題賦值相同的賦值函數是唯一的。

證明：根據定理 1.6，歸納定義。

註：

1. 由於定義 2.1 是遞迴的，$v$ 可以只定義在 $ATOM$ 上，然後擴展到 $PROP$ 上。
2. 若 $v$ 是賦值，對於一個語句 $\phi$，$\llbracket \phi \rrbracket_v$ 代表 $\phi$ 的值。

定義 1.2.3 模型

1. $\phi$ 是恆真句（tautology），若對於所有 $v$，$v(\phi) = 1$。寫作 $\models \phi$，
2. 若 $\Gamma$ 是命題集合，$\Gamma\models \phi$ 表示對於所有 $v$，若 $\psi\in\Gamma, v(\psi) = 1$，則 $v(\phi) = 1$。

註：可以寫作 $\llbracket \phi \rrbracket = 1$，表示容許任意賦值。

定義 1.2.4 取代

$\phi[\psi / p]$ 表示（$p \in ATOM$）：

1. 若 $\phi \in ATOM$ 且 $\phi \neq p$，則 $\phi[\psi / p] = \phi$，
2. 若 $\phi = p$，則 $\phi[\psi / p] = \psi$，
3. $(\phi_1 \square \phi_2)[\psi / p] = \phi_1[\psi / p] \square \phi_2[\psi / p]$，
4. $(\neg \phi)[\psi / p] = \neg \phi[\psi / p]$。

定理 1.2.5 取代定理

若 $\models \phi_1 \leftrightarrow \phi_2$，則 $\models \phi_1[\psi / p] \leftrightarrow \phi_2[\psi / p]$。

引理 1.2.6 取代定理的推廣

1. $\llbracket \phi_1 \leftrightarrow \phi_2 \rrbracket _v \leq \llbracket \psi[\phi_1 / p] \leftrightarrow \psi[\phi_2 / p] \rrbracket _v$。
2. $\models (\phi_1 \leftrightarrow \phi_2) \rightarrow (\psi[\phi_1 / p] \leftrightarrow \psi[\phi_2 / p])$。

命題邏輯的諸性質

性質 1.3.1

結合律：

1. $\models (\phi \lor \psi) \lor \sigma \leftrightarrow \phi \lor (\psi \lor \sigma)$
2. $\models (\phi \land \psi) \land \sigma \leftrightarrow \phi \land (\psi \land \sigma)$

交換律：

1. $\models (\phi \lor \psi) \leftrightarrow (\psi \lor \phi)$
2. $\models (\phi \land \psi) \leftrightarrow (\psi \land \phi)$

分配律：

1. $\models (\phi \lor (\psi \land \sigma)) \leftrightarrow ((\phi \lor \psi) \land (\phi \lor \sigma))$
2. $\models (\phi \land (\psi \lor \sigma)) \leftrightarrow ((\phi \land \psi) \lor (\phi \land \sigma))$

笛摩根律：

1. $\models \neg (\phi \lor \psi) \leftrightarrow (\neg \phi \land \neg \psi)$
2. $\models \neg (\phi \land \psi) \leftrightarrow (\neg \phi \lor \neg \psi)$

冪等律：

1. $\models \phi \lor \phi \leftrightarrow \phi$
2. $\models \phi \land \phi \leftrightarrow \phi$

雙重否定：

• $\models \neg \neg \phi \leftrightarrow \phi$

性質 1.3.2

若 $\models \phi \rightarrow \psi$，則：

1. $\models \phi \land \psi \leftrightarrow \phi$
2. $\models \phi \lor \psi \leftrightarrow \psi$

性質 1.3.3

1. $\models \phi \Rightarrow \models \phi \land \psi \leftrightarrow \psi$，
2. $\models \phi \Rightarrow \models \neg \phi \lor \psi \leftrightarrow \psi$，
3. $\models \bot \lor \phi \leftrightarrow \phi$，
4. $\models \top \land \phi \leftrightarrow \phi$。

性質 1.3.4

1. $\models (\phi \leftrightarrow \psi) \leftrightarrow (\phi \rightarrow \psi) \land (\psi \rightarrow \phi)$，
2. $\models (\phi \rightarrow \psi) \leftrightarrow (\neg \phi \lor \psi)$，
3. $\neg \phi \leftrightarrow (\phi \rightarrow \bot)$，
4. $\models \bot \leftrightarrow \phi \land \neg \phi$。

引理 1.3.5 等價關係 $\approx$

$\phi\approx\psi$ 表示 $\models \phi \leftrightarrow \psi$，$\phi\approx\phi$ 是在 $PROP$ 上的等價關係，

定理 1.3.6 $\neg, \lor$ 的語義完備性

若 $\delta$ 是一個 $n$ 元邏輯連詞，存在函數 $f$ 使得 $\llbracket \delta(p_1,...,p_n) \rrbracket = f(\llbracket p_1 \rrbracket,...,\llbracket p_n \rrbracket)$，則我們說 $\delta$ 是由其賦值函數所定義的。

對於由其賦值函數所定義的 $n$ 元邏輯連詞 $\delta$，存在只由 $p_1,...,p_n, \neg, \lor$ 構成的語句 $\phi$，使得 $\models \phi \leftrightarrow \delta(p_1,...,p_n)$。

定義 1.3.7 連續連詞

1 選言

$\bigvee_{i=0}^0 \phi_i = \phi_0$

$\bigvee_{i \leq 0}^{n+1} \phi_i = (\bigvee_{i \leq 0}^n \phi_i) \lor \phi_{n+1}$

2 連言

$\bigwedge_{i = 0}^n \phi_i = \phi_0$

$\bigwedge_{i \leq 0}^{n+1} \phi_i = (\bigwedge_{i \leq 0}^n \phi_i) \land \phi_{n+1}$

定義 1.3.8 標準式

$\phi = \bigwedge_j\bigvee_i\phi_{i,j}$，其中 $\phi_{i,j}$ 是原子命題或帶 $\neg$ 連詞的原子命題，稱為連言標準式（conjunctive normal form）。

$\phi = \bigvee_j\bigwedge_i\phi_{i,j}$，其中 $\phi_{i,j}$ 是原子命題或帶 $\neg$ 連詞的原子命題，稱為選言標準式（disjunctive normal form）。

定理 1.3.9 標準式的存在性

對於任意語句 $\phi$，存在連言標準式 $\phi^\land$ 與選言標準式 $\phi^\lor$，使得 $\models \phi \leftrightarrow \phi^\land \leftrightarrow \phi^\lor$。

定義 1.3.10 否定函數

$\star: PROP \rightarrow PROP$ 遞迴定義如下：

1. $\phi^\star = \neg \phi$，若 $\phi \in ATOM$，
2. $(\phi \lor \psi)^\star = (\phi^\star \land \psi^\star)$，
3. $(\phi \land \psi)^\star = (\phi^\star \lor \psi^\star)$。
4. $(\neg \phi)^\star = \neg \phi^\star$。

性質 1.3.11 否定函數的性質

$\phi^{\star} \approx \neg \phi$。

定義 1.3.12 共軛函數 duality function

共軛函數 $d: PROP \rightarrow PROP$ 遞迴定義如下：

1. $\phi^d = \phi$，若 $\phi \in ATOM$，
2. $(\phi \lor \psi)^d = \phi^d \land \psi^d$，
3. $(\phi \land \psi)^d = \phi^d \lor \psi^d$。
4. $(\neg \phi)^d = \neg \phi^d$。

定理 1.3.13 共軛定理

若 $\models \phi \leftrightarrow \psi$，則 $\models \phi^d \leftrightarrow \psi^d$。

自然演繹法

定義 1.4.1 自然演繹法的演繹集合

演繹集合是最小的滿足下面性質的樹的集合 $X$：

• (1) 對於任何 $\phi \in PROPS$，樹 ${\phi} \in X$。
• (2$\land$)
  • 若 $D / \phi, D' / \psi \in X$，則 $D / \phi \ D' / \psi \over \phi \land \psi$ $\in X$。
  • 若 $D / \phi \land \psi \in X$，則 $D / \phi \land \psi \over \psi$ $\in X$、$D / \phi \land \psi \over \phi$ $\in X$。
• (2$\rightarrow$)
  • 若 $\phi / D / \psi \in X$，則 $[\phi] / D / \psi \over \phi \rightarrow \psi$ $\in X$。
  • 若 $D / \phi, D' / \phi \rightarrow \psi \in X$，則 $D / \phi \ D' / \phi \rightarrow \psi \over \psi$ $\in X$。
• (2$\bot$)
  • 若 $D / \bot \in X$，則 $D / \bot \over \phi$ $\in X$。
  • 若 $\neg \phi / D / \bot \in X$，則 $[\neg \phi] / D / \bot \over \phi$ $\in X$。

給定任意一棵演繹樹，前提集合 $\Gamma$ 是所有不可消除的葉節點的集合，結論是樹的根節點。

定義 1.4.2 可推導性

• $\Gamma \vdash \phi$ 代表存在一個結論是 $\phi$，前提集合是 $\Gamma$ 的演繹。
• 若 $\Gamma = \emptyset$，我們寫成 $\vdash \phi$，這時我們稱 $\phi$ 是一個定理。

引理 1.4.3 可推導性的性質

• 若 $\phi \in \Gamma$ 則 $\Gamma \vdash \phi$。
• $\Gamma \vdash \phi, \Gamma' \vdash \phi \Rightarrow \Gamma \cup \Gamma' \vdash \phi$。
• $\Gamma \vdash \phi \land \psi \Rightarrow \Gamma \vdash \phi$ 和 $\Gamma \vdash \psi$。
• $\Gamma \cup \{ \phi \} \vdash \psi \Rightarrow \Gamma \vdash \phi \rightarrow \psi$。
• $\Gamma \vdash \phi, \Gamma' \vdash \phi \rightarrow \psi \Rightarrow \Gamma \cup \Gamma' \vdash \psi$。
• $\Gamma \vdash \bot \Rightarrow \Gamma \vdash \phi$。
• $\Gamma \cup \{ \neg \phi \} \vdash \bot \Rightarrow \Gamma \vdash \phi$。

定理 1.4.4 一些定理

• $\vdash \phi \rightarrow (\psi \rightarrow \phi)$
• $\vdash \phi \rightarrow (\neg \phi \rightarrow \psi)$
• $\vdash (\phi \rightarrow \psi) \rightarrow [(\psi\rightarrow\chi) \rightarrow (\phi\rightarrow\chi)]$
• $\vdash (\phi \rightarrow \psi) \leftrightarrow (\neg\psi\rightarrow\neg\phi)$
• $\vdash \neg\neg\phi \rightarrow \phi$
• $\vdash [\phi\rightarrow(\psi\rightarrow\chi)]\leftrightarrow[(\phi\land\psi)\rightarrow\chi]$
• $\vdash \bot \leftrightarrow (\phi \land \neg \phi)$

完備性

證明步驟如下：

1. 證明命題邏輯系統是健全的。
2. 證明（語法的）最大一致集存在（透過 Zorn’s Lemma）。
3. 透過最大一致集，建立能使最大一致集都為真的賦值函數。亦即，命題邏輯系統存在模型。
4. 亦即，不存在模型中為不為真，但能證明的命題。
5. 1 和 4 共同蘊含了完備性。

引理 1.5.1 健全性

若 $\Gamma \vdash \phi$，則 $\Gamma \models \phi$。

證明：以歸納法直接證明。

定義 1.5.2 一致性

$\Gamma$ 是一致的，若 $\Gamma \not\vdash \bot$。

引理 1.5.3 不一致性的等價性質

以下條件是等價的：

1. $\Gamma$ 不是一致的。
2. 存在 $\phi$ 使得 $\Gamma \vdash \phi$ 與 $\Gamma \vdash \neg \phi$。
3. 對於所有 $\phi$，$\Gamma \vdash \phi$。

引理 1.5.4 一致性的等價性質

以下條件是等價的：

1. $\Gamma$ 是一致的。
2. 不存在 $\phi$ 使得 $\Gamma \not\vdash \phi$ 與 $\Gamma \not\vdash \neg \phi$。
3. 存在 $\phi$ 使得 $\Gamma \not\vdash \phi$。

引理 1.5.5

若存在賦值 $v$ 使得 $\llbracket \phi \rrbracket_v = 1, \forall \phi \in \Gamma$，則 $\Gamma \not \vdash \bot$。

定理 1.5.6

$\Gamma \cup \{ \phi \} \vdash \bot \Rightarrow \Gamma \vdash \neg \phi$。

證明：根據引理 5.1。

定義 1.5.7 最大一致集合

$\Gamma$ 是最大一致的，若且唯若

• $\Gamma$ 是一致的，
• 若 $\Gamma \subset \Delta$ 且 $\Delta$ 是一致的，則 $\Delta = \Gamma$。

引理 1.5.8 最大一致集存在引理

對於任意的 $\Gamma \not \vdash \bot$，存在 $\Gamma^\star$ 是最大一致的，且 $\Gamma\subset\Gamma^\star$。

證明：定義 $\langle \Gamma_i \rangle$ 序列如下：

• $\Gamma_0 = \Gamma$，
• 若 $\Gamma_i \cup \{ \phi_i \} \not \vdash \bot$，$\Gamma_{i+1} = \Gamma_i \cup \{ \phi_i \}$，否則 $\Gamma_{i+1} = \Gamma_i$。
• $\Gamma^\star = \bigcup_i \Gamma_i$。

其中 $\langle \phi_i \rangle$ 是給所有的命題語句的一個排序。

可以證明 $\Gamma^\star$ 是最大一致的。

引理 1.5.9

若 $\Gamma$ 是最大一致的，則 $\Gamma$ 是演繹封閉的。

定理 1.5.10

若 $\Gamma$ 是最大一致的，則：

1. 對於所有 $\phi$ 要嘛 $\phi\in\Gamma$ 要嘛 $\neg\phi\in\Gamma$。
2. 對於所有 $\phi, \psi$，$\phi\rightarrow\psi\in\Gamma$ 若且唯若 $\phi\in\Gamma\Rightarrow\psi\in\Gamma$。
3. $\phi\in\Gamma$ 若且唯若 $\neg\phi\not\in\Gamma$。
4. $\neg\phi\in\Gamma$ 若且唯若 $\phi\not\in\Gamma$。

引理 1.5.11 模型存在引理

若 $\Gamma$ 是一致的，存在賦值 $v$ 使得 $\llbracket \phi \rrbracket_v = 1, \forall \phi \in \Gamma$。

證明：

定義 $\Gamma^\star$ 是最大一致的，且 $\Gamma\in\Gamma^\star$。

定義 $v(p_i) = 1, p_i\in\Gamma^\star$ 與 $v(p_i) = 0, p_i\not\in\Gamma^\star$，並遞迴地擴充成賦值函數。

以歸納法證明：$\llbracket \phi \rrbracket_v = 1$ 若且唯若 $\phi \in \Gamma^\star$。

推論 1.5.12

若 $\Gamma\not\vdash\phi$，存在賦值 $v$ 使得 $\llbracket \psi \rrbracket_v = 1, \forall \psi \in \Gamma$ 且 $\llbracket \phi \rrbracket_v = 0$。

亦即：若 $\Gamma\not\vdash\phi$，則 $\Gamma\not\models\phi$。

定理 1.5.13 完備性定理

$\Gamma \models \phi$ 若且唯若 $\Gamma \vdash \phi$。

其他連接詞

定義 1.6.1 三個連接詞

• $\phi\lor\phi =_\text{df} \neg(\neg\phi\land\neg\phi)$
• $\neg \phi=_\text{df} \phi\rightarrow\bot$
• $\phi\leftrightarrow\psi =_\text{df} (\phi\rightarrow\psi)\land(\psi\rightarrow\phi)$

引理 1.6.2 一些重要性質

• $\phi\vdash\phi\lor\psi, \psi\vdash\phi\lor\psi$
• 若 $\Gamma, \phi\vdash\sigma$ 且 $\Gamma, \psi\vdash\sigma$ 則 $\Gamma, \phi\lor\psi\vdash\sigma$
• $\phi,\neg\phi\vdash\bot$
• $\Gamma,\phi\vdash\bot\Rightarrow\Gamma\vdash\neg\phi$
• $\phi\leftrightarrow\psi,\phi\vdash\psi$ 且 $\phi\leftrightarrow\psi,\psi\vdash\phi$
• $\Gamma,\phi\vdash\psi$ 且 $\Gamma,\psi\vdash\phi$ 若且唯若 $\Gamma\vdash\phi\leftrightarrow\psi$

定理 1.6.3

• $\vdash\phi\lor\psi\leftrightarrow\neg(\neg\phi\land\neg\psi)$
• $\vdash\neg\phi\leftrightarrow\phi\rightarrow\bot$
• $\vdash\phi\leftrightarrow\psi\leftrightarrow(\phi\rightarrow\psi)\land(\psi\rightarrow\phi)$