命题逻辑演算形式系统的性质定理

这一节我们来证明一些关于PC的性质定理。注意，这些定理有一些是没办法用有限方法证明的，因此我们需要将已集合论框架内的很多结论作为自然语言移植过来。应当意识到如下证明是在ZFC集合论框架内进行的，并且可以还原回ZFC的形式语言。

PC是可靠的

逻辑演算系统的可靠性是指在该形式系统中推演出来的形式定理，都在实际上反映了某种逻辑规律，即确实是真命题，因此也称合理性。关于PC的可靠性由如下定理所表述。

定理1（PC是可靠的）：‌若 $A$ 为PC的定理，即 $\vdash A$ ，则 $A$ 永真。更一般地，若对任意的公式集 $\Gamma$ 及公式 $A$ ，如果 $\Gamma \vdash A$ ，则 $\Gamma \vDash A$ 。

〔证明定理1〕‌容易用真值表验证PC的公理A1、A2、A3都是永真式。由蕴涵的定义可得若 $A$ 和 $A \imp B$ 永真，则 $B$ 也永真，因此PC的推理规则具有保真性。所以若 $A$ 能在PC中被推理出来，则 $A$ 永真。
现在证如果 $\Gamma \vdash A$ ，则 $\Gamma \vDash A$ 。采用结构归纳法，在 $\Gamma$ 到 $A$ 的演绎序列 $A_1,A_2,\cdots,A_n$ 上进行结构归纳。设 $\alpha$ 为弄真 $\Gamma$ 中所有公式的任一指派，我们需要证明对正整数 $k(1 \le k \le n)$ ，有 $\alpha(A_k) = \mathrm{T}$ 成立。
(1)基例：当 $k=1$ 时，$A_1$ 或为公理或为 $\Gamma$ 中的成员，则 $\alpha(A)=\mathrm{T}$ 。
(2)归纳假设：当 $2 \le k \le n$ 时，假设对正整数 $l(1 \le l \le k-1)$ ，$\alpha(A_l)=\mathrm{T}$ 成立。
(3)归纳步骤：$A_k$ 或为公理，或为 $\Gamma$ 中的成员，或为 $A_l(1 \le l \le k-1)$ ，或为 $A_i,A_j(1 \le i,j \le k)$ 通过分离规则所得。由基例和归纳假设可得前三种情况都有 $\alpha(A_k)=\mathrm{T}$ 。第四种情况由分离规则的保真性也可得 $\alpha(A_k)=\mathrm{T}$ 。因此总有 $\alpha(A_k)=\mathrm{T}$ 。
(4)结论：由结构归纳法原理可知，对所有 $1 \le k \le n$ ， $\alpha(A_k)=\mathrm{T}$ 成立。因此， $\alpha(A_n)=\mathrm{T}$ 成立，即 $\alpha(A)=\mathrm{T}$ 成立。〔定理1证毕〕‌

PC的可靠性定理说明：在反映命题逻辑范围内的推理规律方面，PC是可靠的，其推理的定理都是重言式。而一个命题如果是在中从一定的前提推演出来的，那么它一定是这些前提的逻辑推论，也就是从为真的前提一定得出为真的结论。

PC是一致的

可靠性定理同时也表明了是一致的，即在中不可能推出相互矛盾的结论来。一致性是形式系统，也是逻辑演算系统所要关心的一个基本要求。如果一个形式系统是不一致的，那么在该系统中就会推出相互矛盾的结论来，从而导致该系统是毫无意义的。下面给出有关的一致性定理。

定理2（PC是一致的）：‌PC中不存在公式 $A$ 与 $\neg A$ 均为PC的定理，即不存在公式 $A$ 使得 $A$ 及 $\neg A$ 同时成立。

〔证明定理2〕‌若存在公式 $A$ 使得 $\vdash A$ 及 $\vdash \neg A$ 同时成立，则由PC是可靠的可知 $A$ 及 $\neg A$ 均永真，而这是不可能的。〔定理2证毕〕‌

注意，这里说在PC中不存在公式 $A$ 使得 $\vdash A$ 及 $\vdash \neg A$ 同时成立，并不意味着对任一公式 $A$ ，$\vdash A$ 与 $\vdash \neg A$ 至少有一个是成立的。

PC是不完全的

定理3（PC是不完全的）：‌即在PC中存在公式 $A$ 使得 $\vdash A$ 及 $\vdash \neg A$ 均不成立。

〔证明定理3〕‌设公式 $A \strdefine p \imp q$ ，其中 $p,q$ 为原子变元符，显然 $\vdash p \imp q$ 及 $\vdash \neg (p \imp q)$ 均不成立，因为 $A \strequals p \imp q$ 是一个非永真也非永假的公式。〔定理3证毕〕‌

PC是完备的

从PC的可靠性定理可以看出，在PC中一个语法角度的形式逻辑推理对应着一个语义角度的逻辑蕴涵，那么反过来，在PC中一个语义上的逻辑蕴涵是否一定也对应着系统中的一个形式化的逻辑推理？这就是所谓的形式化系统的完备性问题。如果一个逻辑系统是完备的，那么该系统就把所有成立的逻辑蕴涵关系均反应和包括进来，因此也就称为完备性。下面在给出PC的完备性定理之前，先给出几个相关定义和基本引理。

定义1（PC的理论）：‌称下列集合为PC的理论，即

$$\begin{aligned} Th(\text{PC}) = \set{A| \vdash_{\text{PC}}A} \tag{1}\end{aligned}$$

称下列集合为PC的基于前提 $\Gamma$ 的扩充，即

$$\begin{aligned} Th(\text{PC} \cup \set{\Gamma}) = \set{A|\Gamma \vdash_{\text{PC}}A} \tag{2}\end{aligned}$$

对PC的基于前提 $\Gamma$ 的扩充，通常情况下考虑的是前提 $\Gamma$ 是一致的扩充。如果前提 $\Gamma$ 是一致的，那么 $Th(\text{PC} \cup \set{\Gamma})$ 显然是一致的。而若 $\Gamma$ 不一致，即存在公式 $B$ ，使得 $\Gamma \vdash \neg B$ 且 $\Gamma \vdash B$ ，对于任意的公式 $A$ ，由爆炸原理可知 $\Gamma \vdash A$ ，从而 $Th(\text{PC} \cup \Gamma)$ 是完全的。

引理1：‌设PC的公式集 $\Gamma$ 是一致的，且 $\Gamma \nvdash A$ ，则 $\Gamma \cup \set{\neg A}$ 也是一致的。

〔证明引理1〕‌若 $\Gamma \cup \set{\neg A}$ 不一致，则存在公式 $B$ ，使得 $\Gamma \cup \set{\neg A} \vdash B$ 且 $\Gamma \cup \set{\neg A} \vdash \neg B$ 。又由爆炸原理可知 $\set{B,\neg B} \vdash A$ ，所以 $\Gamma \cup \set{\neg A} \vdash A$ ，由演绎定理#1可得 $\Gamma \vdash \neg A \imp A$ ，而由 $\neg$ 消除#1可得 $\neg A \imp A \vdash A$ ，因此 $\Gamma \vdash A$ ，与条件矛盾。所以 $\Gamma \cup \set{\neg A}$ 是一致的。〔引理1证毕〕‌

引理2：‌若 $\Gamma$ 是PC一致的公式集，则存在公式集 $\Delta$ ，使得 $\Gamma \sube \Delta$ ，$\Delta$ 是一致的且完全的。

〔证明引理2〕‌由PC的公式可知PC的公式是可数的，设公式序列 $A_0,A_1,\cdots,A_n,\cdots$ 为PC的所有公式的枚举，构造公式集序列如下：

$$\begin{aligned} \Delta_0 & = \Gamma \\[5pt] \Delta_1 & = \begin{cases} \Delta_0 \cup \set{A_0} & \Delta_0 \vdash A_0\\ \Delta_0 \cup \set{\neg A_0} & \Delta_0 \nvdash A_0 \\ \end{cases}\\ \vdots\\\ \Delta_{n+1} & = \begin{cases} \Delta_n \cup \set{A_n} & \Delta_n \vdash A_n\\ \Delta_{n+1} \cup \set{\neg A_n} & \Delta_n \nvdash A_n \end{cases} \tag{3}\end{aligned}$$

令 $\Delta = \bigcup_{n=0}^{\infin}\Delta_n$ 。现在我们证明如下结论。
1. $\Gamma \sube \Delta,\Delta_n \sube \Delta_{n+1}$ 。
由式(3)可得显然成立。
2. $\Delta_n$ 是一致的。
采用结构归纳法，在 $\Delta_0,\Delta_1,\cdots,\Delta_n$ 上进行结构归纳。我们需要证明对正整数 $k(1 \le k \le n)$ ，$\Delta_k$ 是一致的。
(1)基例：当 $k=0$ 时，由假设可得 $\Delta_0$ 是一致的。
(2)归纳假设：当 $2 \le k \le n$ 时，假设 $\Delta_{k-1}$ 是一致的。
(3)归纳步骤：若 $\Delta_{k} = \Delta_{k-1} \cup \set{A_k}$ ，此时 $\Delta_{k-1} \vdash A_k$ ，由归纳假设可知 $\Delta_{k-1}$ 是一致的，则此时 $\Delta_{k}$ 为 $\Delta_{k-1}$ 的一致扩充，则 $\Delta_k$ 是一致的。若 $\Delta_k = \Delta_{k-1} \cup \set{\neg A_k}$ ，此时 $\Delta_k \nvdash A_k$ ，由引理1可知 $\Delta_k$ 是一致的。
(4)结论：由结构归纳法原理可知，对所有 $1 \le k \le n$ ，$\Delta_k$ 是一致的。因此，$\Delta_n$ 是一致的。
3. $\Delta$ 是完全的。
由 $\Delta$ 的构造可知，对PC中的任一公式 $A$ ，要么 $A \in \Delta$ ，要么 $\neg A \in \Delta$ ，根据式(3)可得，要么 $\Delta \vdash A$ ，要么 $\Delta \vdash \neg A$ ，故 $\Delta$ 是完全的。
4.对PC的公式 $A$ ，若 $\Delta \vdash A$ ，则存在充分大的正整数 $k$ 使得 $\Delta_k \vdash A$ 。
由 $\Delta \vdash A$ 知存在证明序列 $B_0,B_1,\cdots,B_m$ ，其中 $B_i(0 \le i \le m-1)$ 或为PC的公理，或为 $\Delta$ 中的成员，或为 $B_j(j < i)$ ，或为 $B_j,B_k(0 \le j,k \le i)$ 使用分离规则导出，而 $B_m$ 即为公式 $A$ 。记 $\Delta'=\set{B_0,B_1,\cdots,B_m} \cap \Delta = \set{C_0,C_1,\cdots,C_r}0 \le r \le m$ ，则有 $\Delta' \vdash A$ ，又由 $C_j \in \Delta(0 \le j \le r)$ 知存在正整数 $n_0,n_1,\cdots,n_r$ 使得 $C_j \in \Delta_{n_j}(j=0,1,\cdots,r)$ ，取 $k=\max(n_0,n_1,\cdots,n_r)$ ，则由 $\Delta_n$ 的构造知 $\Delta_{n_j} \sube \Delta_k$ ，所以 $C_j \in \Delta_k$ ，则 $\Delta' \sube \Delta_k$ ，从而 $\Delta_k \vdash A$ 。
5.$\Delta$ 是一致的。
若 $\Delta$ 不一致，则存在公式 $A_i$ ，使得 $\Delta \vdash A_i$ 且 $\Delta \vdash \neg A_i$ ，由 $\Delta \vdash A_i$ 和4.可得存在充分大的正整数 $n_1$ 使得 $\Delta_{n_1} \vdash A$ ，同理由 $\Delta \vdash \neg A_i$ 可知存在充分大的正整数 $n_2$ 使得 $\Delta_{n_2} \vdash \neg A$ ，取 $k=\max (n_1,n_2)$ ，由 $\Delta_n$ 的构造知 $\Delta_{n_1} \sube \Delta_k,\Delta_{n_2} \sube \Delta_k$ ，从而 $\Delta_k \vdash A,\Delta_k \vdash \neg A$ ，从而 $\Delta_k$ 不一致，这与2.的 $\Delta_n$ 一致相矛盾。〔引理2证毕〕‌

引理3：‌对PC中任一公式 $A$ ，$A \in \Delta$ 当且仅当 $\Delta \vdash A$ 。

〔证明引理3〕‌若 $A \in \Delta$ ，则由演绎的定义可知 $\Delta \vdash A$ 。若 $\Delta \vdash A$ ，则由 $\Delta$ 的一致性可知 $\neg A \notin \Delta$ ，又由 $\Delta$ 的构造知 $\neg A \notin \Delta$ 当且仅当 $A \in \Delta$ 。〔引理3证毕〕‌

引理4：‌设 $\Gamma$ 是PC一致的公式集，则存在一个指派 $\alpha$ ，使得 $\Gamma$ 中每一个公式 $A$ ，有 $\alpha(A)=\mathrm{T}$ 。

〔证明引理4〕‌定义指派 $\alpha$ 如下：

$$\begin{aligned} \alpha(p) = \begin{cases} \mathrm{T} & p \in \Delta \\[5pt] \mathrm{F} & p \notin \Delta \end{cases} \tag{4}\end{aligned}$$

其中 $p$ 为原子变元符。下证对任一公式 $A$ ，$\alpha(A)=\mathrm{T}$ 当且仅当 $A \in \Delta$ 。
采用结构归纳法，在公式 $A$ 的构造序列 $A_1,A_2,\cdots,A_n$ 上进行结构归纳。。我们需要证明对正整数 $k(1 \le k \le n)$ ，有 $\alpha(A)=\mathrm{T}$ 当且仅当 $A \in \Delta$ 。
(1)基例：当 $k=1$ 时，$A_1$ 是原子公式，由式(4)可得 $\alpha(A_1)=\mathrm{T}$ 当且仅当 $A_1 \in \Delta$ 。
(2)归纳假设：当 $2 \le k \le n$ 时，假设对自然数 $l(1 \le l \le k-1)$ ， $\alpha(A_l)=\mathrm{T}$ 当且仅当 $A_l \in \Delta$ 。
(3)归纳步骤：
① $A_k$ 是原子公式。则类似(1)可得 $\alpha(A_k)=\mathrm{T}$ 当且仅当 $A_k \in \Delta$ 。
② $A_k=\neg A_i(1 \le i \le k-1)$ ，则

$$\begin{aligned} & \alpha(A_k)= \mathrm{T} \\ & \miff \alpha(\neg A_i) = \mathrm{T} \\ & \miff \alpha(A_i) = \mathrm{F} \\ & \miff B \notin \Delta \\ & \miff \neg B \in \Delta \\ & \miff A_k \in \Delta \tag{5}\end{aligned}$$

③ $A_k=A_i \imp A_j(1 \le i,j \le k-1)$ ，则

$$\begin{aligned} & \alpha(A_k)=\mathrm{T} \\ & \miff \alpha(A_i \imp A_j) = \mathrm{T} \\ & \miff \alpha(A_i)=\mathrm{F} 或 \alpha(A_j)=\mathrm{T}\\ & \miff A_i \notin \Delta 或 A_j \in \Delta\\ & \miff \neg A_i \in \Delta 或 A_j \in \Delta \tag{6}\end{aligned}$$

下面证 $\neg A_i \in \Delta 或 A_j \in \Delta \miff A_i \imp A_j \in \Delta$ 。
先证若 $\neg A_i \in \Delta$ 或 $A_j \in \Delta$ ，则有 $A_i \imp A_j \in \Delta$ 。若 $\neg A_i \in \Delta$ ，则由可知 $\Delta \vdash \neg A_i$ ，又由可得 $\Delta \vdash A_i \imp A_j$ ，所以 $A_i \imp A_j \in \Delta$ 。若 $A_j \in \Delta$ ，由可得 $\Delta \vdash A_j$ ，又由可得 $\Delta \vdash A_i \imp A_j$ ，从而 $A_i \imp A_j \in \Delta$ 。
再证若 $A_i \imp A_j \in \Delta$ ，则有 $\neg A_i \in \Delta$ 或 $A_j \in \Delta$ 。
假设不成立，则有 $\neg A_i \notin \Delta$ 且 $A_j \notin \Delta$ ，即 $A_i \in \Delta$ 且 $\neg A_j \in \Delta$ ，由可知 $\Delta \vdash A_i$ 且 $\Delta \vdash A_j$ ，又因为 $A_i \imp A_j \in \Delta$ ，则 $\Delta \vdash A_i \imp A_j$ ，从而 $\Delta \vdash A_j$ ，与 $\Delta \vdash \neg A_j$ 矛盾。
因此 $\neg A_i \in \Delta 或 A_j \in \Delta \miff A_i \imp A_j \in \Delta$ 。所以

$$\begin{aligned} & \alpha(A_k) = \mathrm{T} \\ & \miff A_i \imp A_j \in \Delta \\ & \miff A_k \in \Delta \tag{7}\end{aligned}$$

因此有 $\alpha(A_k)=\mathrm{T}$ 当且仅当 $A_k \in \Delta$。
(4)结论：由结构归纳法原理可知，对所有 $1 \le k \le n$ ， $\alpha(A_k)=\mathrm{T}$ 当且仅当 $A_k \in \Delta$。因此，对任意公式 $A$ 有 $\alpha(A)=\mathrm{T}$ 当且仅当 $A \in \Delta$。
因此对 $\Gamma$ 中每一个公式 $A$ ，均有 $A \in \Delta$ ，从而 $\alpha(A)=\mathrm{T}$ 。〔引理4证毕〕‌

从引理3可以看出，对PC的公式集 $\Gamma$ ，若 $\Gamma$ 是一致的，则 $\Gamma$ 是可满足的，即由公式集的一致性可推出其可满足性。

定理4（PC是完备的）：‌对PC中任一永真式 $A$ ，必为PC的定理，即有 $\vdash_{\text{PC}} A$ 。一般地，对PC的公式集 $\Gamma$ ，若 $\Gamma \vDash_{\text{PC}} A$ ，则 $\Gamma \vdash_{\text{PC}} A$ 。

〔证明定理4〕‌只需证明后者即可，前者可以看做 $\Gamma = \nothing$ 。
(1)若公式集 $\Gamma$ 不一致，此时由爆炸原理可得 $\Gamma \vdash_{\text{PC}} A$ 。
(2)若公式集 $\Gamma$ 一致，此时若 $\Gamma \nvdash_{\text{PC}} A$ ，则由引理1可得 $\Gamma \cup \set{\neg A}$ 一致，根据引理3可得 $\Gamma \cup \set{\neg A}$ 是可满足的，即存在指派 $\alpha$ 使得 $\Gamma \cup \set{\neg A}$ 中的每个公式均为真，即 $\alpha$ 使得 $\Gamma$ 中的每个公式均为真且有 $\alpha(\neg A) = \mathrm{T}$ ，又由 $\Gamma \vDash A$ 知任意使得 $\Gamma$ 中的每个公式均为真的指派一定使公式 $A$ 为真，从而 $\alpha(A)=\mathrm{T}$ ，与 $\alpha(\neg A)=\mathrm{T}$ 矛盾。〔定理4证毕〕‌

经验虽然告诉我们某物是如此这般的状况，但并不告诉我们它不能是另外的状况。

― Immanuel Kant, 《纯粹理性批判》

朴素数理逻辑(17)：命题逻辑演算形式系统的性质定理

关于命题逻辑演算形式系统本身的性质定理