數理邏輯 (1) 命題邏輯

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

命題邏輯

命題演算是最簡單的形式系統, 以簡單命題為研究對象. 在命題演算中, 簡單命題類似於原子, 可以通過命題聯結詞構成複合命題, 但自身不能再分解, 因此整個系統的結構也較為簡單. 下面先規定語法, 建立起命題演算的語言, 隨後引入這種語言的語義, 最後通過可靠性和完全性將兩者聯繫起來.

語法

命題演算公式集

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

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$, $X$ 生成的公式集記作 $L(X)$.

令 $X_n=\lbrace x_1,\cdots,x_n\rbrace$, 類似地可定義有限變元上的公式集 $L(X_n)$.

命題演算

在公式集 $L(X)$ 的基礎上, 我們建立命題演算 $L$, 即在 $L(X)$ 上規定 “公理” 和 “證明”. 下面建立的系統是 Hilbert 式的, 由較多公理模式與較少的推理規則構成, 與 Gentzen 式自然演繹截然相反, 後者在此不做討論.

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

• $\text{(L1)}$ 肯定後件律: $p\to(q\to p)$,
• $\text{(L2)}$ 蘊涵詞分配律: $(p\to (q\to r))\to((p\to q)\to(p\to r))$,
• $\text{(L3)}$ 換位律: $(\neg p\to\neg q)\to(q\to p)$.

這實質上是三個公理模式, 依據 $p$, $q$, $r$ 的具體選擇可形成無窮多條公理.

甚至就 Hilbert 式演繹系統而言, 公理的選取也並不唯一. 例如公理 $\text{(L3)}$ 可以換成 $$\text{L3}': (\neg p\to q)\to((\neg p\to\neg q)\to p)$$ 所得系統的演繹能力與原系統完全一致 (公理 $\text{L3}'$ 的字面意思是反證律). 我們在此採用的演繹系統最初大概是由 Łukasiewicz 設計的.

“證明” 定義為 $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$. 若 $\emptyset\vdash p$, 則稱 $p$ 為 $L$ 的 “定理”, 記作 $\vdash p$.

一個最經典的例子是同一律的推導:
1. $p\to(p\to p)$

$\text{(L1)}$

2. $p\to((p\to p)\to p)$

$\text{(L1)}$

3. $(p\to((p\to p)\to p))\to((p\to(p\to p))\to(p\to p))$

$\text{(L2)}$

4. $(p\to(p\to p))\to(p\to p)$

$\text{(MP,2,3)}$

5. $p\to p$

$\text{(MP,1,4)}$

從證明序列的有限性立即可以得到:

命題: 若 $\Gamma\vdash p$, 則存在 $\Gamma$ 的有窮子集 $\Delta$ 使得 $\Delta\vdash p$.

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

---

命題(Cut): 對任意公式集 $\Gamma$ 和 $\Delta$, 公式 $\varphi_1,\cdots,\varphi_k$ 和 $\psi$, 若 $\Delta,\varphi_1,\cdots,\varphi_k\vdash\psi$ 且對 $i=1,\cdots,k$ 都有 $\Gamma\vdash\varphi_i$, 則 $\Gamma\cup\Delta\vdash\psi$.

該命題的作用是 “切割” 掉證明中使用的 “引理”, 這保證了我們使用演繹元定理的合法性: 任何使用引理作為跳板的證明, 原則上都可還原為一個直接的演繹.

下面是三個常用的演繹元定理.

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

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

---

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

$$\begin{align*} 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) \end{align*}$$

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

語義

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

真值函數

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

$$\begin{array}{c|cccc} 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=2^4$ 個:

$$\begin{array}{cc|ccccccccc} 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$ 上的一些運算能夠表示任一真值函數, 我們就稱這些運算構成了一個完全組, 所以 $\lbrace\neg,\to\rbrace$ 是一個完全組. 同樣, $\lbrace\neg,\vee\rbrace$ 和 $\lbrace\neg,\wedge\rbrace$ 也是完全組, 因為 $u\to v=\neg u\vee v=\neg(u\wedge\neg v)$.

"與非" 和 "或非" 算符分別用 $\mid$ 和 $\downarrow$ 表示, 定義為: $$\begin{align*} v_1\mid v_2=\neg(v_1\wedge v_2) \\ v_1\downarrow v_2=\neg(v_1\vee v_2) \end{align*}$$ 對應真值表 $$\begin{array}{cc|cc} v_1 & v_2 & v_1\mid 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}$$ 容易驗證, 獨元集 $\lbrace\mid\rbrace$ 和 $\lbrace\downarrow\rbrace$ 都是完全組, 因為 $$\begin{align*} \neg v_1&=v_1\mid v_1=v_1\downarrow v_1 \\ v_1\vee v_2&=(v_1\mid v_1)\mid(v_2\mid v_2) \\ v_1\wedge v_2&=(v_1\downarrow v_1)\downarrow(v_2\downarrow v_2) \end{align*}$$ $\mid$ 又叫做 Sheffer 豎; $\downarrow$ 又叫做 Peirce 箭頭. 理論上說, 命題演算的任一公式都可以僅由命題變元經過一種運算 ( $\mid$ 或 $\downarrow$ ) 表出, Wittgenstein 據此在《邏輯哲學論》中提出了所謂 "命題的一般形式". 但在實際使用中, 這樣的轉寫往往使公式更加冗長且不直觀, 所以沒有多大意義.

賦值

接下來通過 “賦值” 在 $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$ 的真值.

把 $v$ 限制在 $X$ 上可得映射 $v_0:X\to Z_2$, 即命題變元的賦值, 該賦值是任意的. 但在確定命題變元的真值後, 由於保運算性, $v_0$ 必可唯一擴張成 $L(X)$ 的一個賦值 $v$.

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

---

若公式 $p$ 的真值函數取常值 $1$, 則稱 $p$ 為命題演算 $L$ 的重言式 (tautoloy), 記作 $\vDash p$. 字面上看, $\vDash p$ 意為: $p$ 對 $X$ 的任意賦值恆真. 若 $\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\Longleftrightarrow\Gamma\vDash p$$

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

可靠性定理: $\Gamma\vdash p$ $\Longrightarrow$ $\Gamma\vDash p$.

只需驗證公理 $\text{(L1)}$, $\text{(L2)}$, $\text{(L3)}$ 都是重言式, 然後用歸納法即可證明. 可靠性定理的含義是: 使用語法推演規則得到的推論, 必然是語義上真的.

完全性定理: $\Gamma\vDash p$ $\Longrightarrow$ $\Gamma\vdash p$.

其含義為: 任何一個語義上真的公式, 必然是系統內定理.

---

如果有一真值指派使公式集 $\Gamma$ 中的所有公式都為真, 我們就稱公式集 $\Gamma$ 是可滿足的. 則如下兩條等價:

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

這給出了完全性定理的等價形式.

證明: “(1)$\Longrightarrow$(2)”: 假定 $\Gamma$ 一致, 反設 $\Gamma$ 不可滿足, 那麼對任意公式 $p$ 都有 $\Gamma\vDash p$ (注意 “$\vDash$” 的定義), 由(1)知 $\Gamma\vdash p$ 且 $\Gamma\vdash\neg p$, 故 $\Gamma$ 是不一致的. 矛盾.
“(2)$\Longrightarrow$(1)”: 假定 $\Gamma\vDash p$, 反設 $\Gamma\nvdash p$, 則 $\Gamma\cup\left\{\neg p\right\}$ 是一致的, 由(2)知 $\Gamma\cup\left\{\neg p\right\}$ 可滿足, 故存在一個賦值 $v$ 使得 $\Gamma$ 中公式均為真而 $p$ 為假, 即 $\Gamma\nvDash 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\nvdash p_{n-1}. \end{cases} \end{align*}$$

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

定理 (Lindenbaum): 任何一致公式集都可擴張為極大一致集.

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

考慮完全性定理的弱形式: $\vDash p$ $\Longrightarrow$ $\vdash p$. 該形式有更簡單直接的證明.

假設 $p$ 是僅包含命題變元 $x_1,\cdots,x_k$ 的一個公式, $v_0$ 是 $x_1,\cdots,x_k$ 的一個賦值, $v$ 是 $v_0$ 的擴張. 根據 $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$. 那麼有 (歸納並分類討論):

$$\lbrace x_1',x_2',\cdots,x_k'\rbrace\vdash p'$$

設 $\vDash p$, 則 $p'$ 就是 $p$, 所以對任意賦值都有 $\lbrace x_1',x_2',\cdots,x'_k\rbrace\vdash p$, 所以有 $\lbrace x_1',x_2',\cdots,x_k\rbrace\vdash p$ 和 $\lbrace x_1',x_2',\cdots,\neg x_k\rbrace\vdash p$. 由演繹定理得 $\lbrace x_1',x_2',\cdots,x_{k-1}'\rbrace\vdash x_k\to p$ 和 $\lbrace x_1',x_2',\cdots,x_{k-1}'\rbrace\vdash\neg x_k\to p$.

使用反證律, 公理 $\text{(L3)}$ 和演繹定理很容易證明:

$$\lbrace x_1',x_2',\cdots,x_{k-1}'\rbrace\vdash(x_k\to p)\to(\neg x_k\to p)\to p\tag{*}$$

接下來用兩次分離規則即得 $\lbrace x_1',x_2',\cdots,x_{k-1}'\rbrace\vdash p$. 多次重複該過程, 便可把命題變元一個個消去, 得到 $\vdash p$. $\square$

注意 $(\ast)$ 式的證明用到了全部三條公理, 表明我們對公理的選取本質上是為了確保系統的完全性.

---

緊緻性定理: 公式集 $\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$

緊緻性定理的一個應用: 證明任何集合都可線序化.

給定集合 $M$, 指定命題變元集 $X=\lbrace x_{ab}:a,b\in M\rbrace$, 其下標為 $M$ 中元素構成的有序對. 考慮 $X$ 的如下公式集 $\Gamma$:

$$\begin{align*} \Gamma=&\lbrace\neg x_{aa}:a\in M\rbrace\cup \\ &\lbrace x_{ab}\to x_{bc}\to x_{ac}:a,b,c\in M\rbrace\cup \\ &\lbrace x_{ab}\vee x_{ba}:a,b\in M,a\not=b\rbrace \end{align*}$$ $\Gamma$ 的任何有窮子集都可滿足, 所以 $\Gamma$ 也可滿足, 任何一個滿足 $\Gamma$ 的真值指派都給出 $M$ 上的一個線序. $\square$

當然, 如果集合 $M$ 的基數是不可數的, 那麼這個證明就不太嚴格了, 因為我們在此考慮的只是可數語言. 命題變元不可數的情況下, 命題邏輯的緊緻性定理依賴於一些更強的假設.

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

另一些課題

等值公式

如果 $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$ 必有與它等值的主合取範式. 注意到 $\neg p$ 不是矛盾式, 故由廣義 De Morgan 律即可求出.

在構造析取範式時, 我們只考慮了公式 $p$ 所含的命題變元及其表達的真值函數, 而該函數明顯是任意的, 故析取範式的存在表明 $\lbrace \neg,\vee,\wedge\rbrace$ 是一個完全組. 同時已知 $\vee$ 和 $\wedge$ 都能用 $\lbrace\neg,\to\rbrace$ 表出, 這就給出了 $\lbrace\neg,\to\rbrace$ 是完全組的另一證明.

模態邏輯

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

可能世界語義

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

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

$W$ 中的元素 $w$ 稱為一個世界或可能世界, 而 $xRy$ 表示 "從 $x$ 可通達 $y$", $\langle W,R\rangle$ 可看成以 $W$ 為頂點, $R$ 為邊的有向圖.

對一個命題變元 $A_i$, $V(A_i)=\overline{w_i}\subseteq W$, 對於所有 $w\in\overline{w_i}$, $A_i$ 在 $w$ 中成立.

---

我們用 $(\mathcal{M},w)\vDash \alpha$ 來表示 “模態公式 $\alpha$ 在模型 $\mathcal{M}$ 的世界 $w$ 中為真”, 歸納定義公式的語義真如下:

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

結合語義來看, 這幾條的含義都是比較直觀的. 特別地, 我們定義嚴格蘊含 $\varphi ⊰ \psi:=\Box(\varphi\to\psi)$, 它要強於實質蘊含 $\varphi\to\psi$, 但仍不足以表達相關性.

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

語法

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

在 $\text{(L1)}$, $\text{(L2)}$, $\text{(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$ $\Longleftrightarrow$ 對每一個滿足 $\lbrace\alpha:\Box\alpha\in\Gamma\rbrace\subseteq\Delta$ 的 $K$-極大一致集 $\Delta$, 都有 $\beta\in\Delta$.

從而可以把每一個 $K$-極大一致集 $\Delta$ 看作一個 (包含了全部信息的) 可能世界, $\lbrace\alpha:\Box\alpha\in\Gamma\rbrace\subseteq\Delta$ 足以用來定義關係 $R$. 這樣得到的模型, 就是下文將要定義的典範模型.

典範模型

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

可靠性定理的證明仍然是使用歸納法. 顯然公理 $\text{(L1)}$, $\text{(L2)}$, $\text{(L3)}$ 是普遍有效的, 對於公理 $\text{K}:\Box(\alpha\to\beta)\to(\Box\alpha\to\Box\beta)$, 任給模型 $\mathcal{M}$ 和世界 $w$, 如果 $(\mathcal{M},w)\nvDash\Box(\alpha\to\beta)$, 那麼 $(\mathcal{M},w)\vDash\text{K}$, 所以只需討論 $(\mathcal{M},w)\vDash\Box(\alpha\to\beta)$ 的情況; 在這種情況下, 如果 $(\mathcal{M},w)\nvDash\Box\alpha$, 那麼 $(\mathcal{M},w)\vDash\Box\alpha\to\Box\beta$, 則 $(\mathcal{M},w)\vDash\text{K}$; 如果 $(\mathcal{M},w)\vDash\Box\alpha$, 那麼對任意 $w'\in W$, 如果 $w'Rw$, 就有 $(\mathcal{M},w')\vDash\alpha\to\beta$ 和 $(\mathcal{M},w')\vDash\alpha$, 從而 $(\mathcal{M},w')\vDash\beta$, 這就證明了 $(\mathcal{M},w)\vDash\Box\beta$. 故 $(\mathcal{M},w)\vDash\text{K}$, 從而 $\vDash\text{K}$. 之後用歸納法即可.

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

定義 $K$ 的典範模型 $\mathcal{M}=\langle W,R,V\rangle$ 為:

• $W=\lbrace\Gamma:\Gamma$ 是 $K$-極大一致集$\rbrace$,
• $(\Gamma,\Gamma')\in R$ 當且僅當 $\lbrace\alpha:\Box\alpha\in\Gamma\rbrace\subseteq\Gamma'$,
• $V(A_i)=\lbrace\Gamma\in W:A_i\in\Gamma\rbrace$.

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

加強系統

上文考慮的演繹系統 $K$ 只是模態邏輯的極小系統, 許多直觀的真理在其中沒有得到形式化. 例如, 根據已有的公理, 我們甚至甚至無法斷言 $\Box p\to p$, 從語義角度看, 這是因為沒有規定 $R$ 是自反的.

公理的添加同時構成對框架中關係 $R$ 的約束, 對應表格如下:

名稱	公理模式	框架條件	關係的性質
$\text{T}$	$\Box p \to p$	$\forall x(xRx)$	自反性
$\text{4}$	$\Box p \to \Box\Box p$	$\forall x\forall y\forall z((xRy\wedge yRz)\to xRz)$	傳遞性
$\text{B}$	$p \to \Box\Diamond p$	$\forall x\forall y(xRy\to yRx)$	對稱性
$\text{D}$	$\Box p \to \Diamond p$	$\forall x\exists y (xRy)$	序列性
$\text{5}$	$\Diamond p \to \Box\Diamond p$	$\forall x\forall y\forall z((xRy\wedge xRz)\to yRz)$	Euclid 性
$\text{C4}$	$\Box\Box p \to \Box p$	$\forall x\forall y(xRy\to\exists z(xRz\wedge zRy))$	稠密性
$\text{C}$	$\Diamond\Box p\to\Box\Diamond p$	$\forall x\forall y\forall z((xRy\wedge xRz)\to\exists w(yRw\wedge zRw))$	合流性
$\text{GL}$	$\Box(\Box p \to p) \to \Box p$	$R$ 傳遞且沒有無窮增鏈	傳遞性 + 逆良基

由這些公理可產生如下系統:

• $T$: $K+\text{T}$,
• $S4$: $T+\text{4}$,
• $S5$: $S4+\text{5}$,
• $D$: $K+\text{D}$.

其中 $S5$ 常用作形式化知識邏輯, 要求框架中的關係 $R_i$ 是一個等價關係, 表示兩個狀態對於主體 $i$ 是 “認知不可區分的”. $D$ 則常用於道義邏輯, 公理 $\text{D}$ 解釋為: 道義應當必推出許可.

這裡值得一提的是公理 $\text{GL}$ (其名稱代表 Gödel-Löb).

如果把 $\Box$ 解釋為 “可證”, 那麼

$$\text{GL}:\Box(\Box p \to p) \to \Box p$$

的含義恰為著名的 Löb 定理: 對任何算術語句 $\varphi$, 如果能在 $\text{PA}$ 中證明 “若 $\varphi$ 可證, 則 $\varphi$ 為真”, 那麼 $\varphi$ 就在 $\text{PA}$ 中可證.

由於 Gödel 第二不完全性定理, 系統無法證明 “所有可證命題都為真” (否則它就能證明自身的一致性), 故公理 $\text{T}$ 不能用於形式化可證性邏輯. 但採用公理 $\text{GL}$ 卻能充分地建立起模態邏輯與證明論的聯繫. 事實上, 這條公理是對可證性條件的最好刻畫, R. Solovay 於1976年證明了算術完全性定理: 模態邏輯系統 $GL$ 能推出的一切命題, 恰好就是 $\text{PA}$ 中關於可證性所能證明的一切命題.

下一篇: 一階邏輯