數理邏輯筆記 No.1

〔參考: 汪芳庭《數理邏輯》、復旦《數理邏輯: 證明及其限度》〕
自學數理邏輯的筆記, 到 Gödel 不完全性定理為止. 內容主要是抄書…

命題演算

命題演算是最簡單的形式系統, 以簡單命題為研究對象. 在命題演算中, 簡單命題類似於原子, 可以通過命題聯結詞構成複合命題, 但自身不能再分解, 因此整個系統的結構也較為簡單. 我們不必去關心原子命題的具體含義, 只需賦予其古典二值邏輯的真或假 (1或0). 下面先規定語法, 建立起命題演算的語言, 隨後引入這種語言的語義, 最後通過可靠性和完全性將兩者聯繫起來.

語法

命題演算公式集

拋開符號的意義, 我們用選定的字母表, 純形式地建立語言. 字母表包括:

1. 兩個運算符 $\neg$(否定)和 $\to$(蘊涵);
2. 命題變元的可數序列: $x_1,x_2,\cdots x_n\cdots$.

命題形成規則如下:

1. 命題變元 $x_1,x_2,\cdots x_n\cdots$ 中的每一個都是公式;
2. 若 $p,q$ 為公式則 $\neg p$, $p\to q$ 均為公式;
3. 任一公式由前兩條規則使用有限次得到.

記 $X=\left\lbrace x_1,x_2,\cdots x_n\cdots\right\rbrace$, $L(X)$ 為所有公式構成的集, 則公式集具有分層:

$$L(X)=L_0\cup L_1\cup\cdots\cup L_n\cup\cdots$$

其中 $L_0=X$, $L_n$ 中公式由命題變元經過 $n$ 次運算 (使用規則1和規則2) 得到.

$L(X)$ 的分層性是後面一些歸納定義的基礎, 顯然, 它的不同層次之間沒有公共元素, 這保證了歸納定義的合理性.

在處理命題變元有限的情形時, 令 $X_n=\left\lbrace x_1,\cdots x_n\right\rbrace$, 則可以以相同的方式定義代數 $L(X_n)\subseteq L(X)$, 這是 $L(X)$ 的一個子代數, 同樣具有分層性和可數性.

命題演算

在公式集 $L(X)$ 的基礎上, 我們建立命題演算 $L$, 即在 $L(X)$ 上規定 “公理” 和 “證明”.

“公理” 定義為 $L(X)$ 的具有如下形狀的公式:

1. $(L1)$ 肯定後件律: $p\to(q\to p)$;
2. $(L2)$ 蘊涵詞分配律: $(p\to (q\to r))\to((p\to q)\to(p\to r))$;
3. $(L3)$ 換位律: $(\neg p\to\neg q)\to(q\to p)$.

其中 $p,q,r\in L(X)$. 這實質上是三個公理模式, 依據 $p$, $q$, $r$ 的具體選擇可形成無窮多條公理.〔取 $L(X)$ 中特殊公式為公理, 取法不唯一, 不同取法可得到不同的命題演算.〕

“證明” 定義為 $L(X)$ 中公式的特定的有限序列. 設 $\Gamma\subseteq L(X)$, $p\in L(X)$, 我們說 “公式 $p$ 從公式集 $\Gamma$ 中可證”, 假如存在 $L(X)$ 中公式的有限序列 $p_1,\cdots,p_n$, 其中 $p_n=p$, 且每個 $p_k$ 都滿足:

1. $p_k\in\Gamma$, 或
2. $p_k$ 是 "公理", 或
3. 存在 $i,j<k$ 使得 $p_j=p_i\to p_k$〔分離規則(Modus Ponens, $\text{MP}$)〕.

則這樣的有限序列 $p_1,\cdots,p_n$ 叫做 $p$ 從 $\Gamma$ 的 “證明”. 證明如果存在, 就一定不是唯一的.

如果公式 $p$ 從公式集 $\Gamma$ 中可證, 我們稱 $\Gamma$ 中公式為 “假定”, 稱 $p$ 為假定集 $\Gamma$ 的語法推論, 記作 $\Gamma\vdash p$. 若 $\varnothing\vdash p$, 則稱 $p$ 為 $L$ 的 “定理”, 記作 $\vdash p$.

如果對任何公式 $p$, $\Gamma\vdash p$ 和 $\Gamma\vdash\neg p$ 不同時成立, 那麼就稱公式集 $\Gamma$ 是無矛盾公式集 (或稱 $\Gamma$ 是一致的); 反之, 如果 $\Gamma$ 是有矛盾公式集 ($\Gamma$ 是不一致的), 那麼容易證明, 對任一公式 $p$ 都有 $\Gamma\vdash p$, 這有時被稱為爆炸原理 (principle of explosion). 一個含有矛盾的系統是完全平凡的, 這正是我們重視系統無矛盾性的原因.

---

下面是三個常用的語法定理.

1. 演繹定理: $\Gamma\cup\left\lbrace p\right\rbrace\vdash q\Leftrightarrow\Gamma\vdash p\to q$.
   推論 (假設三段論): $\left\lbrace p\to q,q\to r\right\rbrace\vdash p\to r$. 簡稱 $\text{HS}$, 可作為一條推理規則.
2. 反證律: $\Gamma\cup\left\lbrace \neg p\right\rbrace\vdash q$, $\Gamma\cup\left\lbrace \neg p\right\rbrace\vdash \neg q$ $\Rightarrow$ $\Gamma\vdash p$.
3. 歸謬律: $\Gamma\cup\left\lbrace p\right\rbrace\vdash q$, $\Gamma\cup\left\lbrace p\right\rbrace\vdash \neg q$ $\Rightarrow$ $\Gamma\vdash\neg p$.

需注意的是, 反證律和歸謬律在日常推理中似乎是一回事, 但形式系統中, 反證律要強於歸謬律. 一些系統不承認公理 $(L3)$, 將其換為比 $(L3)$ 更弱的形式, 在這些系統中雖然有歸謬律成立, 但卻沒有反證律. 事實上, 這些系統與命題演算 $L$ (即我們在此考察的系統) 的根本分歧在於對排中律的不同態度. 在這些系統中, 儘管也有 $\vdash p\to\neg\neg p$ 恆成立, 但 $\vdash\neg\neg p\to p$ 不一定恆成立.

---

在 $\left\lbrace \neg,\to\right\rbrace$ 型代數 $L(X)$ 中進一步定義二元運算析取, 合取及等值:

$$p\vee q=\neg p\to q$$ $$p\wedge q=\neg(p\to\neg q)$$ $$p\leftrightarrow q=(p\to q)\wedge(q\to p)$$

至此, 五個基本命題聯結詞都已得到語法上的定義.

語義

命題邏輯的語義不關心具體表述什麼, 以及這種表述是否為真, 重要的只是我們在元語言層次上賦予公式的真值. 因此, 命題邏輯語義的根本其實就是真值表.

真值函數

我們首先定義真值函數. 記 $Z_2=\left\lbrace 0,1\right\rbrace$, 則函數 $f: Z_2^n\to Z_2$ 叫做 $n$ 元真值函數. 一元真值函數共有4個, 分別用 $f_1,f_2,f_3,f_4$ 表示:

$$\begin{array}{c|cc} v\in Z_2 & f_1(v) & f_2(v) & f_3(v) & f_4(v)\\ \hline 1 & 1 & 1 & 0 & 0\\ \hline 0 & 1 & 0 & 1 & 0\\ \end{array}$$

其中 $f_3$ 稱作 “否定”, 記為 $f_3=\neg v=1-v$.
二元真值函數共有16個:

$$\begin{array}{cc|cc} v_1 & v_2 & f_1 & f_2 & \cdots & f_5 & \cdots & f_7 & f_8 & \cdots & f_{16}\\ \hline 1 & 1 & 1 & 1 & \cdots & 1 & \cdots & 1 & 1 & \cdots & 0\\ \hline 1 & 0 & 1 & 1 & \cdots & 0 & \cdots & 0 & 0 & \cdots & 0\\ \hline 0 & 1 & 1 & 1 & \cdots & 1 & \cdots & 0 & 0 & \cdots & 0\\ \hline 0 & 0 & 1 & 0 & \cdots & 1 & \cdots & 1 & 0 & \cdots & 0\\ \end{array}$$

其中 $f_5$ 稱作 “蘊涵”, 記為 $f_5(v_1,v_2)=v_1\to v_2=1-v_1+v_1v_2$. 同時分別用 $\vee$, $\wedge$, $\leftrightarrow$ 來表示上表中的 $f_2$, $f_8$, $f_7$. 這裡我們用 $\neg$, $\to$ 等符號僅僅是對特定真值函數的簡化表示, 但對應真值表很容易看出, 這些函數與經典邏輯中的 “否定”, “蘊涵” 等聯結詞具有一致的作用效果.

任一真值函數都可僅用 $\neg$ 和 $\to$ 表示出來. 對真值函數的元數 $n$ 歸納. $n=1$ 時顯然; $n>1$ 時, 定義另外三個真值函數如下:

$$\begin{align*} &g(x_1,\cdots,x_{n-1}) = f(x_1,\cdots,x_{n-1},1), \\ &h(x_1,\cdots,x_{n-1}) = f(x_1,\cdots,x_{n-1},0), \\ &k(x_1,\cdots,x_{n-1},x_n) = (h(x_1,\cdots,x_{n-1})\to x_n)\to\neg(g(x_1,\cdots,x_{n-1})\to\neg x_n) \end{align*}$$

容易驗證, $k=f$. 由歸納假設, 命題得證. $\square$

若 $Z_2$ 上的一些運算能夠表示任一真值函數, 我們就稱這些運算構成了一個完全組, 所以 $\left\lbrace \neg,\to\right\rbrace$ 是一個完全組. 同樣, $\left\lbrace \neg,\vee\right\rbrace$ 和 $\left\lbrace \neg,\wedge\right\rbrace$ 也是完全組, 因為 $u\to v=\neg u\vee v=\neg(u\wedge\neg v)$.

NAND and NOR

“與非” 和 “或非” 算符分別用 $|$ 和 $\downarrow$ 表示, 定義為:
$$v_1|v_2=\neg(v_1\wedge v_2)$$
$$v_1\downarrow v_2=\neg(v_1\vee v_2)$$
對應真值表
$$\begin{array}{cccc}{v}_1& v_2& v_1\mathrm{\mid }{v}_2& v_1\downarrow v_2\\ 1& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$
\begin{array}{cc|cc} v_1 & v_2 & v_1|v_2 & v_1\downarrow v_2\
\hline 1 & 1 & 0 & 0\
\hline 1 & 0 & 1 & 0\
\hline 0 & 1 & 1 & 0\
\hline 0 & 0 & 1 & 1\
\end{array}

容易驗證, 獨元集 $\left\lbrace |\right\rbrace$ 和 $\left\lbrace \downarrow\right\rbrace$ 都是完全組, 因為
$$\neg v_1=v_1|v_1=v_1\downarrow v_1$$
$$v_1\vee v_2=(v_1|v_1)|(v_2|v_2)$$
$$v_1\wedge v_2=(v_1\downarrow v_1)\downarrow(v_2\downarrow v_2)$$
與非算符 $|$ 又叫做 Sheffer 豎. 理論上說, 命題演算的任一公式都可以僅由命題變元經過一種運算( $|$ 或 $\downarrow$ )表示出來, 因此, Wittgenstein 在《邏輯哲學論》中著重強調 $\downarrow$ 算符, 並提出所謂 “命題的一般形式”. 但在實際使用中, 這樣的轉寫往往使公式更加冗長且不直觀, 所以沒有多大實際意義.

賦值和語義推論

接著, 我們通過 “賦值” 在 $L(X)$ 和 $Z_2$ 這兩種代數之間建立聯繫.
具有保運算性的映射 $v: L(X)\to Z_2$ 稱為 $L(X)$ 的賦值, 其中, 保運算性是指, 對任意 $p,q\in L(X)$ 有:

1. $v(\neg p)=\neg v(p)$;
2. $v(p\to q)=v(p)\to v(q)$.

對任意公式 $p\in L(X)$, $v(p)$ 叫做 $p$ 的真值.

根據 $\vee$, $\wedge$, $\leftrightarrow$ 的語法定義, 容易驗證 $v$ 對這些運算也具有保運算性. 這種賦值之所以良好定義, 是因為我們此前定義的 $L(X)$ 和 $Z_2$ 都是 $\left\lbrace \neg,\to\right\rbrace$ 型代數, 兩者是同構的.

由 $L(X)$ 的代數結構和 $v$ 的保運算性可知, 只需明確命題變元 $x_1,\cdots,x_n,\cdots$ 的真值, $L(X)$ 中任意公式的真值就都能確定下來. 因此, 我們將映射 $v_0:X\to Z_2$ 定義為命題變元的真值指派. 歸納可知, 命題變元的任一真值指派, 必可唯一地擴張成 $L(X)$ 的賦值. 將 $v_0$ 限制在 $X_n=\left\lbrace x_1,\cdots x_n\right\rbrace$ 上, $v$ 限制在 $L(X_n)$ 上, 結論同樣成立.

若公式 $p$ 的真值函數取常值 $1$, 則稱 $p$ 為命題演算 $L$ 的重言式 (Tautoloy) 或永真式, 記作 $\vDash p$. 字面上看, $\vDash p$ 說的當然是, $p$ 對 $X$ 的任意真值指派恆真.

進而, 我們有代換定理: $\vDash p(x_1,\cdots,x_n)$ $\Rightarrow$ $\vDash p(p_1,\cdots,p_n)$, 其中 $p(x_1,\cdots,x_n)\in L(X_n)$, $p_1,\cdots,p_n\in L(X)$, 而 $p(p_1,\cdots,p_n)$ 即是用 $p_1,\cdots,p_n$ 替換 $x_1,\cdots,x_n$ 的結果.

若 $\neg p$ 是重言式, 則 $p$ 是矛盾式 (Contradiction) 或永假式, 非矛盾式叫做可滿足公式.

設 $\Gamma\subseteq L(X)$, $p\in L(X)$. 如果 $\Gamma$ 中所有公式的任何公共成真指派都一定是公式 $p$ 的成真指派, 則說 $p$ 是 $\Gamma$ 的語義推論, 記作 $\Gamma\vDash p$. 即是說, $L(X)$ 的任一賦值 $v$, 若對所有 $q\in \Gamma$ 都有 $v(q)=1$, 那麼必有 $v(p)=1$.

語義推論和語法推論在形式和含義上都極為相似, 事實上, 一般情況下在簡單的數學系統中, 由於系統的可靠性和完全性, 這兩者是等價的.

可靠性和完全性

下面要證明的是命題演算 $L$ 中語法推論和語義推論的一致性, 即

$$\Gamma\vdash p\quad\Leftrightarrow\quad\Gamma\vDash p$$

特別地, $\vdash p$ 當且僅當 $\vDash p$, 即 $L$ 中定理集與重言式集重合.

首先是可靠性定理: $\Gamma\vdash p\enspace\Rightarrow\enspace\Gamma\vDash p$. 只需驗證公理 $(L1)$, $(L2)$ 和 $(L3)$ 都是重言式, 並用歸納法即可證明. 這一條保證: 使用語法推演規則得到的推論, 必然是語義上真的.

完全性定理是可靠性定理的逆命題: $\Gamma\vDash p\enspace\Rightarrow\enspace\Gamma\vdash p$, 它斷言: 任何一個語義上真的公式, 都必然可以語法地推出. 這個定理的證明要困難得多.

---

首先定義可滿足性: 如果有一真值指派使公式集 $\Gamma$ 中的所有公式都為真, 我們就稱公式集 $\Gamma$ 是可滿足的. 據此給出完全性定理的等價表述 (2):

1. $\Gamma\vDash p\enspace\Rightarrow\enspace\Gamma\vdash p$;
2. 如果 $\Gamma$ 是一致的, 則 $\Gamma$ 可滿足.

“(1)$\Rightarrow$(2)”: 假定 $\Gamma$ 一致, 反設 $\Gamma$ 不可滿足, 那麼對任意公式 $p$ 都有 $\Gamma\vDash p$ (注意 “$\vDash$” 的定義), 由 $\Gamma\vDash p\enspace\Rightarrow\enspace\Gamma\vdash p$ 知 $\Gamma\vdash p$ 且 $\Gamma\vdash\neg p$, 故 $\Gamma$ 是不一致的. 矛盾.

“(2)$\Rightarrow$(1)”: 假定 $\Gamma\vDash p$, 反設 $\Gamma\not\vdash p$, 則 $\Gamma\cup\left\lbrace \neg p\right\rbrace$ 是一致的, 由(2)知 $\Gamma\cup\left\lbrace \neg p\right\rbrace$ 可滿足, 故存在一個賦值 $v$ 使得 $\Gamma$ 中公式均為真而 $p$ 為假, 即 $\Gamma\not\vDash p$. 矛盾. $\square$

---

隨後對一個無矛盾公式集進行擴張:

$L(X)$ 是可數的, 所以我們可以把其中公式枚舉為 $p_0,p_1,p_2,\cdots$, 任取一個無矛盾公式集 $\Gamma$, 遞歸定義一個公式集序列 $\left\lbrace \Gamma_n\right\rbrace$ 如下: $$\begin{align*} \Gamma_0&=\Gamma;\\ \Gamma_n&= \begin{cases} \Gamma_{n-1},&\text{if}\enspace\Gamma\vdash p_{n-1};\\ \Gamma_{n-1}\cup\left\lbrace \neg p_{n-1}\right\rbrace,&\text{if}\enspace\Gamma\not\vdash p_{n-1}. \end{cases} \end{align*}$$

容易驗證, 序列中每一個公式集 $\Gamma_n$ 都是一致的. 令 $\Gamma^{*}=\bigcup_{n=0}^{\infty}\Gamma_n$, 則 $\Gamma^{*}$ 也是一致的. 由於我們遍歷了整個 $L(X)$, 在保證一致性的前提下將每一個公式或其否定都納入到 $\Gamma^{*}$ 之中, 所以對任意公式 $p$, $\Gamma^{*}\vdash p$ 和 $\Gamma^{*}\vdash\neg p$ 必居其一, 換句話說, $\Gamma^{*}\vdash p$ 是完備的 (或極大一致的). 我們稱 $\Gamma^{*}$ 是 $\Gamma$ 的完備無矛盾擴張. 由構造過程即可得到定理 (Lindenbaum): 無矛盾公式集必有完備無矛盾擴張.

定義一個映射 $v:L(X)\to Z_2$, 使得 $v(p)=1$ 當且僅當 $p\in\Gamma^{*}$, 容易證明這樣定義的 $v$ 具有保運算性, 所以是一個賦值. 存在賦值 $v$ 使 $\Gamma^{*}$ 中所有公式為真, 故 $\Gamma^{*}$ 是可滿足的. 又 $\Gamma\subseteq\Gamma^{*}$, 所以 $\Gamma$ 也是可滿足的. 因此, 我們證明了上面的等價表述(2), 也就證明了(1), 即 $L$ 的完全性. $\square$

完全性定理弱形式的證明

復旦版數理邏輯給出了一個更直接和直觀的方法, 可證明完全性定理的弱形式: $\vDash p$ $\Rightarrow$ $\vdash p$. 思路如下.

假設 $p$ 是僅包含命題變元 $x_1,\cdots,x_k$ 的一個公式, $v_0$ 是 $x_1,\cdots,x_k$ 的一個真值指派, $v$ 為其對應的賦值. 根據 $v_0$ 對 $x_i$ 做變形, 如果 $v_0(x_i)=1$, 就令 $x_i'$ 為 $x_i$, 否則令 $x_i'$ 為 $\neg x_i$; 同樣指定 $p$ 的變形: 如果 $v(p)=1$, 就令 $p'$ 為 $p$, 否則為 $\neg p$. 那麼我們有:
$$\left\lbrace x_1',x_2',\cdots,x_k'\right\rbrace\vdash p'$$
設 $\vDash p$, 則 $p'$ 就是 $p$, 所以有 $\left\lbrace x_1',x_2',\cdots,x_k\right\rbrace\vdash p$ 和 $\left\lbrace x_1',x_2',\cdots,\neg x_k\right\rbrace\vdash p$. 由演繹定理得 $\left\lbrace x_1',x_2',\cdots,x_{k-1}'\right\rbrace\vdash x_k\to p$ 和 $\left\lbrace x_1',x_2',\cdots,x_{k-1}'\right\rbrace\vdash\neg x_k\to p$, 所以有 (這是重言式)
$$\left\lbrace x_1',x_2',\cdots,x_{k-1}'\right\rbrace\vdash(x_k\to p)\to((\neg x_k\to p)\to p)$$
用兩次分離規則即得 $\left\lbrace x_1',x_2',\cdots,x_{k-1}'\right\rbrace\vdash p$. 多次重複該過程, 便可把命題變元一個個消去, 得到 $\vdash p$. $\square$

這種弱形式之所以能如此簡單地得到證明, 是因為它只依賴於命題變元 (第一層) 的真值指派, 而不用關心由命題變元真值所決定的某些更高層次的公式的真值.

---

有了完全性定理, 我們很容易得到緊緻性定理: 公式集 $\Gamma$ 是可滿足的當且僅當 $\Gamma$ 的每一個有窮子集都是可滿足的. 這個定理可以看作拓撲中緊緻性定理的一個特殊情況.

證明: 假設公式集 $\Gamma$ 的任意有窮子集都是可滿足的, 反設 $\Gamma$ 不可滿足. 則根據完全性定理, $\Gamma$ 也不一致, 所以 $\Gamma\vdash p\wedge\neg p$. 由於每一個證明的長度都是有限的, 所以存在 $\Gamma$ 的一個有窮子集 $\Gamma_0$ 使得 $\Gamma_0\vdash p\wedge\neg p$, 根據可靠性定理就有 $\Gamma_0\vDash p\wedge\neg p$, 故 $\Gamma_0$ 不可滿足, 與假設矛盾. $\square$

Example

復旦版數理邏輯給出了一個有趣的例子: 用緊緻性定理證明任何集合都可線序化.
給定集合 $M$, 指定命題變元集 $X=\left\lbrace x_{ab}:a,b\in M\right\rbrace$, 其下標為 $M$ 中元素構成的有序對. 考慮 $X$ 的如下公式集 $\Gamma$:
$$\begin{array}{rl}{\displaystyle \mathrm{\Gamma }=}& {\displaystyle \{\mathrm{\neg }{x}_{aa}:a\in M\}\cup }\\ {\displaystyle }& {\displaystyle \{x_{ab}\to x_{bc}\to x_{ac}:a,b,c\in M\}\cup }\\ {\displaystyle }& {\displaystyle \{x_{ab}\vee x_{ba}:a,b\in M,a≠b\}}\end{array}$$
\begin{align*}
\Gamma=&\left\lbrace \neg x_{aa}:a\in M\right\rbrace\cup \
&\left\lbrace x_{ab}\to x_{bc}\to x_{ac}:a,b,c\in M\right\rbrace\cup \
&\left\lbrace x_{ab}\vee x_{ba}:a,b\in M,a\not=b\right\rbrace
\end{align*}

$\Gamma$ 的任何有窮子集都可滿足, 所以 $\Gamma$ 也可滿足, 任何一個滿足 $\Gamma$ 的真值指派都給出 $M$ 上的一個線序. 事實上, $\Gamma$ 是三種模式的公式的並集, 這三種模式的公式分別給出了線序的三個要求: (1) 非自反性; (2) 傳遞性; (3) 任意 $a,b\in M$, $aRb$, $a=b$, $bRa$ 必居其一.

最後, 命題演算 $L$ 是語義可判定的, 即, 存在算法可用來確定 $L$ 中任給的公式 $p(x_1,\cdots,x_n)$ 是否為重言式. 這樣的算法當然存在, 我們只需一一計算不同真值指派下的真值函數值即可, 這相當於列真值表並檢驗最後一列是否都是 $1$. 但這種算法效率很低, 是所謂指數時間算法. 由完全性定理, $L$ 也是語法可判定的, 但語法可判定完全依賴於語義可判定.

真值方程組

除去直接列真值表, 我們還可以通過解真值方程組來判定一個公式是否為重言式. 例如, 考慮公式 $((p\to q)\to p)\to p$, 判定其是否為重言式相當於檢查如下真值方程組是否有解:
$$\{\begin{array}{l}(p\to q)\to p=1\\ p=0\end{array}$$
\begin{cases}
(p\to q)\to p=1 \
p=0
\end{cases}

將下式代入上式, 得 $p\to q=0$. 由於 $p=0$, 不管 $q=0$ 還是 $q=1$, 該式都不成立. 所以原方程組無解, 這說明原公式是重言式.

另一些課題

等值公式

如果 $p\leftrightarrow q$ 是重言式, 那麼就稱 $p$ 和 $q$ 為等值公式. 設 $p,q\in L(X_n)$, 則如下條件等價:

1. $p$, $q$ 等值;
2. 對 $L(X_n)$ (或 $L(X)$ )的任一賦值 $v$ 都有 $v(p)=v(q)$;
3. $p$ 和 $q$ 有相同的真值函數.

由於 $n$ 元真值函數共有 $2^{2^n}$ 個, 所以儘管 $L(X_n)$ 中有無窮多個公式, 語義不同的僅有有限種. 互相等值的公式形成一個等價類, 這就給出了 $L(X_n)$ 的一個分類.

設公式 $p$ 只含有命題變元, $\neg$, $\vee$, $\wedge$, 把 $p$ 中的命題變元改為自身的否定, 把 $\vee$ 全改為 $\wedge$, 把 $\wedge$ 全改為 $\vee$, 這樣得到的公式稱為 $p$ 的對偶, 記為 $p^{*}$. 例如, 公式 $p=x_1\vee x_2\wedge \neg x_3$ 的對偶即為 $p^{*}=\neg x_1\wedge \neg x_2\vee\neg\neg x_3$. 可以證明 (歸納法), 公式 $p^{*}$ 和 $\neg p$ 等值. 一個最簡單的例子是: $x_1\to x_2=\neg x_1\vee x_2=\neg(x_1\wedge\neg x_2)$.

進而, 我們有推廣的 De Morgan 律:

$$\models\enspace \bigvee_{i=1}^n \neg p_i\leftrightarrow\neg \bigwedge_{i=1}^n p_i$$ $$\models\enspace \bigwedge_{i=1}^n \neg p_i\leftrightarrow\neg \bigvee_{i=1}^n p_i$$

析取範式與合取範式

形如 $y_1\vee y_2\vee\cdots\vee y_n$ 和 $y_1\wedge y_2\wedge\cdots\wedge y_n$ 的公式分別叫做基本析取式和基本合取式, 其中每個 $y_i$ 是命題變元或命題變元的否定. 任給一個基本析取式, 很容易判定它是否是重言式, 如果式中同時出現 $x_k$ 和 $\neg x_k$, 那麼該式必為重言式; 同樣, 如果在一個基本合取式中同時出現 $x_k$ 和 $\neg x_k$, 那麼該式必為矛盾式.

形如 $\bigvee_{i=1}^m(\bigwedge_{j=1}^{n_i}y_{ij})$ 和 $\bigwedge_{i=1}^m(\bigvee_{j=1}^{n_i}y_{ij})$ 的公式分別叫做析取範式和合取範式, 其中每個 $y_i$ 是命題變元或命題變元的否定. 很容易判定析取範式是否為矛盾式, 因為每一析取支都是基本合取式, 原析取範式為矛盾式, 當且僅當每一析取支都是矛盾式; 同樣, 一個合取範式是重言式, 當且僅當每一合取支都是重言式.

進而, 我們稱 $L(X)$ 中的一個析(合)取範式為主析(合)取範式, 如果在它的每一析(合)取支中, 每個命題變元 $x_1,\cdots x_n$ 按下標由小到大的順序出現且僅出現一次. 於是我們有定理: 任一非矛盾式必有與它等值的主析取範式.

證明即是該主析取範式的求法. 設公式 $p$ 不是矛盾式, 則它有成真指派, 令它的所有成真指派為 $(v_{11},\cdots,v_{1n})$, $\cdots$, $(v_{k1},\cdots,v_{kn})$, 分別作出對應的基本合取式

$$y_{11}\wedge y_{12}\wedge\cdots\wedge y_{1n},\enspace\cdots,\enspace y_{k1}\wedge y_{k2}\wedge\cdots\wedge y_{kn}$$

其中

$$y_{ij}=\begin{cases} x_{j},&\text{if}\enspace v_{ij}=1 \\ \neg x_{j},&\text{if}\enspace v_{ij}=0 \end{cases}$$

令 $q=(y_{11}\wedge\cdots\wedge y_{1n})\vee\cdots\vee(y_{k1}\wedge\cdots\wedge y_{kn})$, 則 $q$ 就是所求的主析取範式. $\square$

類似地, 任一非重言式 $p$ 必有與它等值的主合取範式, 由廣義 De Morgan 律很容易求出. (注意 $\neg p$ 不是矛盾式)

模態邏輯*

這部分內容跟數理邏輯的核心問題似乎關係不大, 但是復旦版數理邏輯裡面有寫, 我覺得是個很有意思的擴展, 所以一並整理到這篇筆記裡. (也可以看作是處理一階邏輯前的一次預演)

---

模態邏輯的語言比命題邏輯僅僅多一個一元聯結詞 $\Box$, 也稱作模態算子. 一元聯結詞 $\Diamond$ 定義為 $\Box$ 的對偶: $\Diamond\alpha=\neg\Box\neg\alpha$, 下面的討論中不會涉及. $\Box$ 和 $\Diamond$ 一般分別解釋為 “必然” 和 “可能”, 其他解釋包括 “應當” 和 “允許”, “已知” 和 “不與已知矛盾” 等.

依舊是語義和語法兩個層次, 我們從語義入手. 根據 Kripke 的可能世界語義學, 我們首先定義模型:

1. $W$ 為一個非空集合, $R$ 為 $W$ 上的一個二元關係, 我們稱二元組 $F=(W,R)$ 為一個**框架**;
2. 我們稱從命題變元的集合 $X=\left\lbrace A_1,A_2,\cdots\right\rbrace$ 到 $W$ 的冪集的映射 $V:X\to \mathcal{P}(W)$ 為一個賦值;
3. 我們稱一個由框架和賦值形成的二元組 $M=(F,V)$ 為一個模型, 也常寫作 $M=(W,R,V)$.

$W$ 中的元素一般稱為一個**世界**或**可能世界** (可以想象成是一些平行宇宙的截面, 其中只有並列的命題, 而不包含時間性), 而 $xRy$ 表示 "從 $x$ 可通達 $y$". 對一個命題變元 $A_i$, $V(A_i)=\overline{w_i}\subseteq W$, 任意 $w\in\overline{w_i}$, $A_i$ 在 $w$ 中成立.

隨後我們歸納地定義一個模態公式 $\alpha$ 在模型 $M$ 的世界 $w$ 中為真, 記作 $(M,w)\vDash \alpha$, 如下:

1. 對命題變元 $A_i$, $(M,w)\vDash A_i$ 當且僅當 $w\in V(A_i)$;
2. $(M,w)\vDash \neg\beta$ 當且僅當 $(M,w)\not\vDash \beta$;
3. $(M,w)\vDash \beta\to\gamma$ 當且僅當 $(M,w)\not\vDash \beta$ 或 $(M,w)\vDash \gamma$;
4. $(M,w)\vDash \Box\beta$ 當且僅當對任意 $w'\in W$, 如果 $w'Rw$, 那麼 $(M,w')\vDash \beta$.

結合可能世界的字面意義, 這幾條的含義都是比較直觀的.

如果對所有 $w\in W$ 都有 $(M,w)\vDash \alpha$, 就稱 $\alpha$ 在模型 $M$ 中為真, 記作 $M\vDash\alpha$. 如果對所有模型 $M$ 都有 $M\vDash\alpha$, 就稱 $\alpha$ 是普遍有效的, 記作 $\vDash\alpha$.

---

接著定義模態邏輯的一個推理系統 $K$.

在 $(L1)$, $(L2)$, $(L3)$ 的基礎上添加公理 $K:\Box(\alpha\to\beta)\to(\Box\alpha\to\Box\beta)$, 在原有分離規則的基礎上添加必然化規則 $\text{RN}$: 從 $\alpha$ 可以得到 $\Box\alpha$. “證明” 和 “定理” 的定義都與命題邏輯相類似, 證明規則中多加一條必然化. $\alpha$ 是 $K$ 的定理, 記作 $\vdash_{K}\alpha$. 命題邏輯的語法演繹定理對 $K$ 仍然有效.

由於 $K$ 是 $L$ 的擴張, $L$ 中的重言式當然也是 $K$ 中的重言式, 但帶有模態語言中重言式的概念不完全相同. 我們把所有命題變元和形如 $\Box\alpha$ 的公式全都列出來: $\beta_1,\beta_2,\cdots$, 並為其指派新的符號如 $B_1,B_2,\cdots$, 若經過變換後關於 $B_i$ 的公式是古典意義的重言式, 則稱原來的模態公式為 $K$ 中的重言式. 顯然, 對每一個模態重言式 $\alpha$, 都有 $\vdash_{K}\alpha$.

仿照命題邏輯, 如果公式集 $\Gamma$ 是 $K$-一致的, 且對任意模態公式 $\alpha$, 或者 $\alpha\in\Gamma$ 或者 $\neg\alpha\in\Gamma$, 就稱 $\Gamma$ 為一個 $K$-極大一致集. $K$ 中也有相應的 Lindenbaum 定理: 任一 $K$-一致的公式集都可擴張成一個 $K$-極大一致集. 證明略. 設 $\Gamma$ 是一個 $K$-極大一致集, 則 $\Box\beta\in\Gamma$ 當且僅當對每一個滿足 $\lbrace \alpha:\Box\alpha\in\Gamma\rbrace\subseteq\Delta$ 的 $K$-極大一致集 $\Delta$, 都有 $\beta\in\Delta$. 事實上, 我們可以把每一個這樣的 $K$-極大一致集 $\Delta$ 視為對應於一個 (被徹底描述了的) 可能世界, 結合前面定義的模型概念, 自然就能對這個定理有一定程度的直觀理解. (當然, 我們還沒有證明這樣的模型一定存在. )

---

與命題邏輯相同, 我們可以證明模態邏輯的可靠性和完全性. 這裡只討論弱形式, 即 $\vdash_{K}\alpha$ 當且僅當 $\vDash\alpha$.

可靠性定理的證明仍然是使用歸納法. 顯然公理 $(L1)$, $(L2)$, $(L3)$ 是普遍有效的, 對於公理 $K:\Box(\alpha\to\beta)\to(\Box\alpha\to\Box\beta)$, 任給模型 $M$ 和世界 $w$, 如果 $(M,w)\not\vDash\Box(\alpha\to\beta)$, 那麼 $(M,w)\vDash K$, 所以我們只需討論 $(M,w)\vDash\Box(\alpha\to\beta)$ 的情況; 在這種情況下, 如果 $(M,w)\not\vDash\Box\alpha$, 那麼 $(M,w)\vDash\Box\alpha\to\Box\beta$, 則 $(M,w)\vDash K$; 如果 $(M,w)\vDash\Box\alpha$, 那麼由 $\Box(\alpha\to\beta)$ 和 $\Box\alpha$ 能推出 $\Box\beta$, 即 $(M,w)\vDash\Box\beta$. 故 $(M,w)\vDash K$, 從而 $\vDash K$. 之後用歸納法即可.

完全性定理的證明思路是, 如果 $\not\vdash_{K}\alpha$, 就找出一個模型 $M$ 和世界 $w$, 使得 $(M,w)\not\vDash\alpha$. 特別地, 在模態邏輯中, 我們能找到一個模型 $M=(W,R,V)$, 如果 $\not\vdash_{K}\alpha$, 就會有一個世界 $w\in W$, 使得 $(M,w)\not\vDash\alpha$. 這個為一切 “非定理” 提供反例的模型稱為典範模型.

定義 $K$ 的典範模型 $M=(W,R,V)$ 為: $W=\lbrace \Gamma:\Gamma$ 是 $K$-極大一致集$\rbrace$; $(\Gamma,\Gamma')\in R$ 當且僅當 $\left\lbrace \alpha:\Box\alpha\in\Gamma\right\rbrace\subseteq\Gamma'$; $V(A_i)=\left\lbrace \Gamma\in W:A_i\in\Gamma\right\rbrace$.

令 $M$ 為 $K$ 的典範模型, 則對任意模態公式 $\alpha$, 任意 $\Gamma\in W$, 我們有 $(M,\Gamma)\vDash\alpha$ 當且僅當 $\alpha\in\Gamma$, 即任意 $\Gamma$ 對語義推論是封閉的 (依舊歸納證明). 假定 $\not\vdash_{K}\alpha$, 則 $\left\lbrace \neg\alpha\right\rbrace$ 是 $K$-一致的, 將其擴張為一個 $K$-極大一致集 $\Gamma$, 考慮典範模型 $M$ 中的世界 $\Gamma$, 則 $\neg\alpha\in\Gamma$, 故 $(M,\Gamma)\not\vDash\alpha$. 這樣就證明了 $K$ 的完全性. $\square$

---

Remark. 按照可能世界的語義解釋, 模態邏輯看似只是把經典哲學關於可能、必然等問題的直觀理解進行了形式化, 但實際上, 模態邏輯的結構要比這複雜得多. 最有意思的一點或許是, 形如 $\Box\alpha$ 的句子看似只應該在跨可能世界 (元語言) 的層次上出現, 卻竟能在單個可能世界中有所斷言, 這似乎是缺乏解釋的. 如果要用模態邏輯去描述現實世界, 那麼它恐怕首先要面對關係 $R$ 和模態公式兩者孰先孰後的哲學問題. 另外, 按照公式的構成規則, $K$ 中將會出現如 $\Box\Box\alpha$ 這一類沒有明確直觀意義的公式, 這是否是形式化帶來的冗餘? 從數學角度看, 這些問題當然是沒有意義的, 我們關心的只是這個已經形式化的系統本身. 從哲學的角度看, 我們或許可以把每一個 “可能世界” 理解為 Leibniz 式的單子, 每一個單子都反映著整個世界, 也反映著其他單子中反映著其自身的映像, 形成無限遞歸的鏡面系統.

下一篇: 謂詞演算