用户: HoshinoKoji/数理逻辑/命题逻辑系统

1引言

在命题逻辑中, 语义分析和语法分析从不同角度讨论了公式集和公式的关系, 其中前者通过赋值函数讨论真值的蕴含, 而后者通过推演规则或公理探讨了公式的形式可推演性. 在选取特定语法系统的前提下, 两者会具有相似的元定理和蕴含关系. 在本文中, 我们以公理系统为例, 证明语义蕴含和语法推演具有相同的结果:

•	可靠性定理, 在语法上被蕴含的公式, 也在语义上被蕴含;
•	完全性定理, 在语义上被蕴含的公式, 也在语法上被蕴含;

由于课程内容已经详尽地讨论了命题逻辑的语义系统, 我们仅罗列出后续证明中需要使用的核心定义和定理, 而对公理系统给出详细的定义和定理证明, 大致思路参考了《数理逻辑》¹ 一书的 Henkin 构造方法.

2命题逻辑的语义系统

在后文中, 我们统一使用 $\Gamma ,\Delta$ 等大写希腊字母来指代公式集, 用 $\phi ,\psi$ 等小写希腊字母来指代公式, 用 $\upsilon$ 指代赋值函数.

定义 2.1. 称 $\phi$ 为恒真式, 当且仅当任给 $\upsilon$ 有 $\upsilon (\phi )=1$; 称 $\phi$ 为可满足式, 当且仅当存在 $\upsilon$ 使得 $\upsilon (\phi )=1$; 称 $\Gamma$ 可满足, 当且仅当存在 $\upsilon$ 使得任给 $\phi \in \Gamma$ 有 $\upsilon (\phi )=1$.

定义 2.2 (语义蕴含). $\Gamma$ 语义蕴含 $\phi$ 当且仅当 $\upsilon (\Gamma )=1$ 时, $\upsilon (\phi )=1$, 记为 $\Gamma \models \phi$, 否则记为 $\Gamma ⊭\phi$. 特别地,

•	显然可知 $\Gamma =\varnothing$ 当且仅当 $\phi$ 为恒真式, 记为 $\models \phi$.
•	当 $\Gamma =\left\{\psi \right\}$ 时, 记为 $\psi \models \phi$.
•	当 $\phi \models \psi$ 且 $\psi \models \phi$ 时, 称 $\phi$ 与 $\psi$ 语义等值, 记作 $\phi \mid =\mid \psi$.

基于语义蕴涵, 我们将列出并证明部分重要定理.

定理 2.3. 如果 $\phi \in \Gamma$, 那么 $\Gamma \models \phi$.

证明. 若 $\upsilon (\Gamma )=1$, 由 $\phi \in \Gamma$ 有 $\upsilon (\phi )=1$, 得证.

$\square$

定理 2.4 (增加前提). 如果 $\Gamma \models \phi$, 那么 $\Gamma \cup \Delta \models \phi$.

证明. 若 $\upsilon (\Gamma \cup \Delta )=1$, 则任给公式 $\psi \in \Gamma \cup \Delta$ 有 $\upsilon (\psi )=1$. 又由于 $\Gamma \in \Gamma \cup \Delta$, 则任给公式 $\psi \in \Gamma$ 有 $\upsilon (\psi )=1$, 由假设可知 $\upsilon (\phi )=1$, 得证.

$\square$

定理 2.5 (蕴含消去). 如果 $\Gamma \models \phi$ 且 $\Gamma \models \phi \to \psi$, 那么 $\Gamma \models \psi$.

证明. 由假设, 当 $\upsilon (\Gamma )=1$ 时, $\upsilon (\phi )=\upsilon (\phi \to \psi )=1$, 由实质蕴涵的真值表可知 $\upsilon (\psi )=1$, 得证.

$\square$

3命题逻辑的语法系统

语法系统可以采用自然推演系统, 基于推演规则定义语法蕴含; 也可以采用公理系统, 基于公理得到不同的推理规则. 而由于后者可以在一定程度上简化定义过程, 我们会采用公理系统完成证明.

定义 3.1 (公理系统). 公理系统包含以下公理模式:

(P1)	$\phi \to \psi \to \phi$
(P2)	$(\phi \to \psi \to \xi )\to (\phi \to \psi )\to (\phi \to \xi )$
(P3)	$(\neg \phi \to \psi )\to (\neg \phi \to \neg \psi )\to \phi$

和分离规则 (MP), 即由 $\phi \to \psi$ 和 $\phi$ 可以得到 $\psi$.

通过真值分析或翻译为自然语言, 不难看出上述公理虽然高度概括, 但也具有一定的直观意义. 其中, P1 相当于取值为真的后件总是被任意前件蕴含, P2 相当于一种特定形式的假言三段论, 而 P3 相当于反证法.

定理 3.2. 定义 3.1 中的公理均为恒真式.

证明. 我们使用反证法逐条说明.

1.	反设存在赋值函数 $\upsilon$ 使得 $\upsilon (\phi \to \psi \to \phi )=0$, 那么 $\upsilon (\phi )=1$ 且 $\upsilon (\psi \to \phi )=0$, 于是又得到 $\upsilon (\phi )=0$, 矛盾.
2.	反设存在赋值函数 $\upsilon$ 使得 $\upsilon ((\phi \to \psi \to \xi )\to (\phi \to \psi )\to (\phi \to \xi ))=0$, 那么 $\upsilon (\phi \to \psi \to \xi )=1$, $\upsilon ((\phi \to \psi )\to (\phi \to \xi ))=0$, 由后者又得到 $\upsilon (\phi \to \psi )=1$ 且 $\upsilon (\phi \to \xi )=0$, 于是 $\upsilon (\phi )=1$, $\upsilon (\xi )=0$. 由于 $\upsilon (\phi \to \psi \to \xi )=1$ 且 $\upsilon (\phi )=1$, 则 $\upsilon (\psi \to \xi )=1$. 又由 $\upsilon (\xi )=0$ 有 $\upsilon (\psi )=0$, 代入得 $\upsilon (\phi \to \psi )=0$, 矛盾.
3.	反设存在赋值函数 $\upsilon$ 使得 $\upsilon ((\neg \phi \to \psi )\to (\neg \phi \to \neg \psi )\to \phi )=0$, 那么 $\upsilon (\neg \phi \to \psi )=\upsilon (\neg \phi \to \neg \psi )=1$, $\upsilon (\phi )=0$, 进一步可得 $\upsilon (\psi )=\upsilon (\neg \psi )=0$, 矛盾.

综上所述, 定理得证.

$\square$

由此可以刻画公理系统的推演方式, 定义公式集和公式的语法蕴含关系.

定义 3.3 (证明和演绎). 给定公式集 $\Gamma$ 和有限长的公式序列 ${\phi }_1,{\phi }_2,\dots ,{\phi }_n$, 序列中的任意公式 ${\phi }_m$ 满足以下条件之一:

•	公式 ${\phi }_m\in \Gamma$,
•	公式 ${\phi }_m$ 属于任一公理模式,
•	公式 ${\phi }_m$ 由序列中的 ${\phi }_i$ 和 ${\phi }_j$ 应用 MP 规则得到, 即 ${\phi }_i=\xi \to {\phi }_m$, ${\phi }_j=\xi$, 且 $i,j<m$,

且 ${\phi }_n=\phi$, 则称上述序列是从 $\Gamma$ 到 $\phi$ 的演绎, 记为 $\Gamma ⊢\phi$. 特别地, 若 $\Gamma =\varnothing$, 称 $\phi$ 为定理, 该序列是 $\phi$ 的证明, 记为 $⊢\phi$; 若 $\Gamma =\left\{\psi \right\}$, 记为 $\psi ⊢\phi$.

接下来, 我们会证明一系列定理和元定理.

定理 3.4 (同一性). $⊢\phi \to \phi$.

证明. 构造证明序列.

(1)	$\phi \to (\phi \to \phi )\to \phi$ (P1)
(2)	$(\phi \to (\phi \to \phi )\to \phi )\to (\phi \to \phi \to \phi )\to (\phi \to \phi )$ (P2)
(3)	$(\phi \to \phi \to \phi )\to (\phi \to \phi )$ (MP, 1, 2)
(4)	$\phi \to \phi \to \phi$ (P1)
(5)	$\phi \to \phi$ (MP, 3, 4)

于是得证.

$\square$

注意到在证明中, 我们总是可以利用已证明的定理构造相同模式的序列, 不必重复.

定理 3.5 (双重否定消去). $⊢\neg \neg \phi \to \phi$.

证明. 构造证明序列.

(1)	$(\neg \phi \to \neg \phi )\to (\neg \phi \to \neg \neg \phi )\to \phi$ (P3)
(2)	$\neg \phi \to \neg \phi$ (3.4)
(3)	$(\neg \phi \to \neg \neg \phi )\to \phi$ (MP, 1, 2)
(4)	$((\neg \phi \to \neg \neg \phi )\to \phi )\to \neg \neg \phi \to ((\neg \phi \to \neg \neg \phi )\to \phi )$ (P1)
(5)	$\neg \neg \phi \to ((\neg \phi \to \neg \neg \phi )\to \phi )$ (MP, 3, 4)
(6)	$(\neg \neg \phi \to (\neg \phi \to \neg \neg \phi )\to \phi )\to (\neg \neg \phi \to \neg \phi \to \neg \neg \phi )\to (\neg \neg \phi \to \phi )$ (P2)
(7)	$(\neg \neg \phi \to \neg \phi \to \neg \neg \phi )\to (\neg \neg \phi \to \phi )$ (MP, 5, 6)
(8)	$\neg \neg \phi \to \neg \phi \to \neg \neg \phi$ (P1)
(9)	$\neg \neg \phi \to \phi$ (MP, 7, 8)

于是得证.

$\square$

定理 3.6. 若 $\phi \in \Gamma$, 则 $\Gamma ⊢\phi$.

证明. 显然可知, ${\phi }_1=\phi$ 是从 $\Gamma$ 到 $\phi$ 的演绎.

$\square$

定理 3.7 (增加前提). 若 $\Gamma ⊢\phi$, 则 $\Gamma \cup \Delta ⊢\phi$.

证明. 由 $\Gamma ⊢\phi$, 存在从 $\Gamma$ 到 $\phi$ 的演绎序列, 而且由演绎的定义可知该序列也为从 $\Gamma \cup \Delta$ 到 $\phi$ 的演绎, 故得证.

$\square$

定理 3.8 (演绎定理). $\Gamma \cup \left\{\phi \right\}⊢\psi$ 当且仅当 $\Gamma ⊢\phi \to \psi$.

证明. 首先证明从左至右. 由假设可知存在从 $\Gamma \cup \left\{\phi \right\}$ 到 $\psi$ 的演绎 ${\phi }_1,{\phi }_2,\dots ,{\phi }_n$, 其中 ${\phi }_n=\psi$. 我们对序列位置 $i$ 实施归纳法, 证明任给序列中的 ${\phi }_i$ 有 $\Gamma ⊢\phi \to {\phi }_i$.

1.	由演绎定义, ${\phi }_1$ 为公理模式或满足 ${\phi }_1\in \Gamma \cup \left\{\phi \right\}$, 构造演绎序列 ${\phi }_1,{\phi }_1\to \phi \to {\phi }_1,\phi \to {\phi }_1$, 得证.
2.	若 ${\phi }_1,{\phi }_2,\dots ,{\phi }_k$ 均满足归纳假设, 只需证明 $\Gamma ⊢\phi \to {\phi }_{k+1}$. 由定义可知 ${\phi }_1$ 要么为公理模式, 要么满足 ${\phi }_1\in \Gamma \cup \left\{\phi \right\}$, 要么由 ${\phi }_i$ 和 ${\phi }_j$ 应用 MP 规则得到. 前两种情形证明同上, 只需讨论第三种情形. 不妨令 ${\phi }_i=\xi \to {\phi }_{k+1}$, ${\phi }_j=\xi$, 由归纳假设可知 $\Gamma ⊢\phi \to \xi \to {\phi }_{k+1}$ 且 $\Gamma ⊢\phi \to \xi$, 合并其演绎序列并延长: (*1) $(\phi \to \xi \to {\phi }_{k+1})\to (\phi \to \xi )\to (\phi \to {\phi }_{k+1})$ (P3) (*2) $\phi \to \xi \to {\phi }_{k+1}$ (已证) (*3) $(\phi \to \xi )\to (\phi \to {\phi }_{k+1})$ (MP, *1, *2) (*4) $\phi \to \xi$ (已证) (*5) $\phi \to {\phi }_{k+1}$ (MP, *3, *4) 由构造过程可知, 延长后的序列是从 $\Gamma$ 到 $\phi \to {\phi }_{k+1}$ 的演绎序列.
3.	综上所述, 归纳证明成立.

然后证明从右至左. 由假设可知存在从 $\Gamma$ 到 $\phi \to \psi$ 的演绎序列, 该序列也是从 $\Gamma \cup \left\{\phi \right\}$ 到 $\phi \to \psi$ 的演绎序列, 在此基础上延长:

(*1)	$\phi \to \psi$ (已证)
(*2)	$\phi$ (假设)
(*3)	$\psi$ (MP, *1, *2)

由构造过程可知, 延长后的序列是从 $\Gamma \cup \left\{\phi \right\}$ 到 $\psi$ 的演绎序列, 得证.

$\square$

定理 3.9 (三段论). $⊢(\phi \to \psi )\to (\psi \to \xi )\to (\phi \to \xi )$.

证明. 由定理 3.8, 命题等价于 $\{\phi \to \psi ,\psi \to \xi \}⊢\phi \to \xi$, 于是又等价于 $\{\phi ,\phi \to \psi ,\psi \to \xi \}⊢\xi$, 构造演绎序列:

(1)	$\phi \to \psi$ (假设)
(2)	$\phi$ (假设)
(3)	$\psi$ (MP, 1, 2)
(4)	$\psi \to \xi$ (假设)
(5)	$\xi$ (MP, 3, 4)

于是等价命题和原命题均得证.

$\square$

定理 3.10 (P3*). $⊢(\phi \to \psi )\to (\phi \to \neg \psi )\to \neg \phi$.

证明. 由定理 3.8, 命题等价于 $\{\phi \to \psi ,\phi \to \neg \psi \}⊢\neg \phi$, 构造演绎序列.

(1)	$\neg \neg \phi \to \phi$ (3.5)
(2)	$(\neg \neg \phi \to \phi )\to (\phi \to \psi )\to (\neg \neg \phi \to \psi )$ (3.9)
(3)	$(\phi \to \psi )\to (\neg \neg \phi \to \psi )$ (MP, 1, 2)
(4)	$\phi \to \psi$ (假设)
(5)	$\neg \neg \phi \to \psi$ (MP, 3, 4)
(6)	$(\neg \neg \phi \to \phi )\to (\phi \to \neg \psi )\to (\neg \neg \phi \to \neg \psi )$ (3.9)
(7)	$(\phi \to \neg \psi )\to (\neg \neg \phi \to \neg \psi )$ (MP, 1, 6)
(8)	$\phi \to \neg \psi$ (假设)
(9)	$\neg \neg \phi \to \neg \psi$ (MP, 7, 8)
(10)	$(\neg \neg \phi \to \psi )\to (\neg \neg \phi \to \neg \psi )\to \neg \phi$ (P3)
(11)	$(\neg \neg \phi \to \neg \psi )\to \neg \phi$ (MP, 5, 10)
(12)	$\neg \phi$ (MP, 9, 11)

于是等价命题和原命题均得证.

$\square$

4可靠性和完全性

经过上文的准备, 我们已经可以着手证明可靠性定理和完全性定理.

定理 4.1 (可靠性定理). 如果 $\Gamma ⊢\phi$, 那么 $\Gamma \models \phi$.

证明. 由假设可知存在从 $\Gamma$ 到 $\phi$ 的演绎序列 ${\phi }_1,{\phi }_2,\dots ,{\phi }_n$, 我们对序列的位置实施归纳法, 说明任给序列中的公式 ${\phi }_k$ 有 $\Gamma \models {\phi }_k$.

1.	考察 ${\phi }_1$, 由定义可知 ${\phi }_1$ 要么为公理模式, 要么满足 ${\phi }_1\in \Gamma$, 定理 3.2 已经说明公理模式为恒真式, 定理 2.3 证明了第二种情形, 于是有 $\Gamma \models {\phi }_1$.
2.	假设 ${\phi }_1,{\phi }_2,\dots ,{\phi }_k$ 均满足归纳假设, 考察 ${\phi }_{k+1}$. 由定义可知 ${\phi }_{k+1}$ 要么为公理模式, 要么满足 ${\phi }_{k+1}\in \Gamma$, 要么由 ${\phi }_i$ 和 ${\phi }_j$ 应用 MP 规则得到. 前两种情形同上, 只讨论第三种情形. 不妨令 ${\phi }_i=\xi \to {\phi }_{k+1}$, ${\phi }_j=\xi$, 由归纳假设有 $\Gamma \models \xi \to {\phi }_{k+1}$ 且 $\Gamma \models \xi$, 又由定理 2.5 可得 $\Gamma \models {\phi }_{k+1}$.
3.	综上所述, 归纳证明成立.

由于 ${\phi }_n=\phi$, 定理得证.

$\square$

完全性定理需要的构造较为复杂, 我们会引入一致集和极大一致集的定义, 并将整体证明过程拆分为若干引理.

定义 4.2 (一致集). 公式集 $\Gamma$ 不一致, 当且仅当存在公式 $\phi$ 使得 $\Gamma ⊢\phi$ 且 $\Gamma ⊢\neg \phi$, 否则称 $\Gamma$ 为一致集.

定理 4.3 (爆炸法则). 如果 $\Gamma$ 不一致, 那么 $\Gamma ⊢\phi$.

证明. 由假设, 存在 $\psi$ 使得 $\Gamma ⊢\psi$ 且 $\Gamma ⊢\neg \psi$, 构造演绎序列.

(1)	$(\neg \phi \to \psi )\to (\neg \phi \to \neg \psi )\to \phi$ (P3)
(2)	$\psi \to \neg \phi \to \psi$ (P1)
(3)	$\psi$ (假设)
(4)	$\neg \phi \to \psi$ (MP, 2, 3)
(5)	$\neg \psi \to \neg \phi \to \neg \psi$ (P1)
(6)	$\neg \psi$ (假设)
(7)	$\neg \phi \to \neg \psi$ (MP, 5, 6)
(8)	$(\neg \phi \to \neg \psi )\to \phi$ (MP, 1, 4)
(9)	$\phi$ (MP, 7, 8)

于是得证.

$\square$

推论 4.4 (否定前件). $\neg \phi ⊢\phi \to \xi$.

证明. 由定理 3.8, 命题等价于 $\{\phi ,\neg \phi \}⊢\xi$, 而 $\{\phi ,\neg \phi \}$ 显然不一致, 由定理 4.3 得证.

$\square$

定理 4.5 (反证法). 如果 $\Gamma \cup \left\{\neg \phi \right\}$ 不一致, 那么 $\Gamma ⊢\phi$.

证明. 由不一致的定义有 $\Gamma \cup \left\{\neg \phi \right\}⊢\psi$ 且 $\Gamma \cup \left\{\neg \phi \right\}⊢\neg \psi$, 又由定理 3.8 有 $\Gamma ⊢\neg \phi \to \psi$ 且 $\Gamma ⊢\neg \phi \to \neg \psi$, 合并其演绎序列并延长:

(*1)	$\neg \phi \to \psi$ (已证)
(*2)	$(\neg \phi \to \psi )\to (\neg \phi \to \neg \psi )\to \phi$ (P3)
(*3)	$(\neg \phi \to \neg \psi )\to \phi$ (MP, *1, *3)
(*4)	$\neg \phi \to \neg \psi$ (已证)
(*5)	$\phi$ (MP, *3, *4)

由构造过程可知, 延长后的序列是从 $\Gamma$ 到 $\phi$ 的演绎, 于是得证.

$\square$

定理 4.6 (归谬法). 如果 $\Gamma \cup \left\{\phi \right\}$ 不一致, 那么 $\Gamma ⊢\neg \phi$.

证明. 由不一致的定义有 $\Gamma \cup \left\{\phi \right\}⊢\psi$ 且 $\Gamma \cup \left\{\phi \right\}⊢\neg \psi$, 又由定理 3.8 有 $\Gamma ⊢\phi \to \psi$ 且 $\Gamma ⊢\phi \to \neg \psi$, 合并其演绎序列并延长:

(*1)	$\phi \to \psi$ (已证)
(*2)	$(\phi \to \psi )\to (\phi \to \neg \psi )\to \neg \phi$ (3.10)
(*3)	$(\phi \to \neg \psi )\to \neg \phi$ (MP, *1, *3)
(*4)	$\phi \to \neg \psi$ (已证)
(*5)	$\neg \phi$ (MP, *3, *4)

由构造过程可知, 延长后的序列是从 $\Gamma$ 到 $\neg \phi$ 的演绎, 于是得证.

$\square$

定义 4.7 (极大一致集). 公式集 $\Gamma$ 为极大一致集, 当且仅当 $\Gamma \cup \left\{\phi \right\}$ 为一致集时有 $\phi \in \Gamma$.

定理 4.8 (极大一致集的等价条件). 公式集 $\Gamma$ 为极大一致集, 当且仅当 $\phi \in \Gamma$ 时有 $\neg \phi \notin \Gamma$, 并且 $\phi \notin \Gamma$ 时有 $\neg \phi \in \Gamma$, 换言之 $\phi \in \Gamma$ 当且仅当 $\neg \phi \notin \Gamma$.

证明. 首先证明从左至右. 若 $\phi \in \Gamma$, 则 $\neg \phi \notin \Gamma$, 否则由定理 3.6 有 $\Gamma ⊢\phi$ 且 $\Gamma ⊢\neg \phi$, 即 $\Gamma$ 不一致, 矛盾. 若 $\phi \notin \Gamma$, 则 $\Gamma \cup \left\{\neg \phi \right\}$ 一致, 否则由定理 4.5 有 $\Gamma ⊢\phi$, 矛盾, 于是由极大一致集定义有 $\neg \phi \in \Gamma$.

然后证明从右至左. 若 $\Gamma \cup \left\{\phi \right\}$ 为一致集, 则 $\neg \phi \notin \Gamma$, 否则由定理 3.6 有 $\Gamma ⊢\neg \phi$, 由定理 3.7 有 $\Gamma \cup \left\{\phi \right\}⊢\neg \phi$, 且 $\Gamma \cup \left\{\phi \right\}⊢\phi$, 即 $\Gamma \cup \left\{\phi \right\}$ 不一致, 矛盾. 由于 $\phi \notin \Gamma$ 时有 $\neg \phi \in \Gamma$, 那么 $\neg \phi \notin \Gamma$ 时有 $\phi \in \Gamma$, 得证.

$\square$

引理 4.9 (可扩张性引理). 如果 $\Gamma$ 一致, 那么存在极大一致集 $\Delta$ 使得 $\Gamma \subseteq \Delta$.

证明. 由于命题逻辑的全体公式可数, 我们可以构建序列 $\{{\phi }_n{\}}_{n\in {\mathbb{N}}^{\ast }}$ 来列举所有公式, 将符合要求的公式添加到原有公式集内.

令 ${\Delta }_0=\Gamma$, 定义 $n\ge 1$ 时序列 $\{{\Delta }_n{\}}_{n\in \mathbb{N}}$ 的取值: $${\Delta }_n=\{\begin{array}{ll}{\Delta }_{n-1}\cup \left\{{\phi }_n\right\},& {\Delta }_{n-1}\cup \left\{{\phi }_n\right\}\text{一致}\\ {\Delta }_{n-1},& {\Delta }_{n-1}\cup \left\{{\phi }_n\right\}\text{不一致}\end{array}$$

令 $\Delta ={\bigcup }_{n\in \mathbb{N}}{\Delta }_n$, 显然有 $\Gamma \subseteq \Delta$ 且 ${\Delta }_n$ 为一致集, 只需验证 $\Delta$ 为极大一致集, 记 $\phi ={\phi }_i$, $\neg \phi ={\phi }_j$.

当 $\phi \in \Delta$ 时, 若 $j<i$, 反设 $\neg \phi \in \Delta$, 则 ${\Delta }_{i-1}\cup \left\{\phi \right\}$ 不一致, 由定理 4.6 有 ${\Delta }_{i-1}⊢\neg \phi$, 由 ${\Delta }_{i-1}$ 的一致性可知 $\phi \notin {\Delta }_{i-1}$, $\phi \notin \Delta$, 矛盾. 如果 $j>i$, 那么 ${\Delta }_{j-1}\cup \left\{{\phi }_j\right\}$ 不一致, $\neg \phi \notin \Delta$.

当 $\phi \notin \Delta$ 时, 显然有 $\phi \notin \Gamma$, 反设 $\neg \phi \notin \Delta$. 若 $j<i$, 则 ${\Delta }_{j-1}\cup \left\{\neg \phi \right\}$ 不一致, 由定理 4.5 有 ${\Delta }_{j-1}⊢\phi$, 又由定理 3.7 有 ${\Delta }_{i-1}⊢\phi$, 但 $\phi \notin \Delta$, 即 ${\Delta }_{i-1}\cup \left\{\phi \right\}$ 不一致, 由定理 4.6 有 ${\Delta }_{i-1}⊢\neg \phi$, 即 ${\Delta }_{i-1}$ 不一致, 矛盾. 若 $j>i$, 同理可得 ${\Delta }_{j-1}$ 不一致, 矛盾.

因此, 由定理 4.8 有 $\Delta$ 是极大一致集, 得证.

$\square$

引理 4.10 (赋值函数构造). 极大一致集可满足.

证明. 给定极大一致集 $\Gamma$, 我们可以定义原子公式 $\phi$ 的赋值: $$\upsilon (\phi )=\{\begin{array}{ll}1,& \phi \in \Gamma \\ 0,& \phi \notin \Gamma \end{array}$$其他公式的赋值由此确定. 我们将对公式结构实施归纳法, 说明任给公式 $\phi$ 有 $\upsilon (\phi )=1$ 当且仅当 $\phi \in \Gamma$.

•

考察 $\phi =\neg \psi$. $$\begin{array}{rlr}\upsilon (\phi )=1& \iff \upsilon (\neg \psi )=1& \phi =\neg \psi \\ & \iff \upsilon (\psi )=0& \text{赋值函数定义}\\ & \iff \psi \notin \Gamma & \text{归纳假设}\\ & \iff \neg \psi \in \Gamma & \text{已证}\\ & \iff \phi \in \Gamma & \phi =\neg \psi \end{array}$$其中第四步来自定理 4.8.

•

考察 $\phi =\psi \to \xi$, 我们证明其否定形式. $$\begin{array}{rlr}\upsilon (\phi )=0& \iff \upsilon (\psi \to \xi )=0& \phi =\psi \to \xi \\ & \iff \upsilon (\psi )=1且\upsilon (\xi )=0& \text{赋值函数定义}\\ & \iff \psi \in \Gamma 且\xi \notin \Gamma & \text{归纳假设}\\ & \iff \psi ,\neg \xi \in \Gamma & \text{已证}\end{array}$$其中第四步来自定理 4.8. 我们还需说明 $\psi ,\neg \xi \in \Gamma$ 当且仅当 $\phi \notin \Gamma$. 首先证明从左至右, 反设 $\phi \in \Gamma$, 构造演绎序列: (1) $\psi \to \xi$ (假设) (2) $\psi$ (假设) (3) $\xi$ (MP, 1, 2) 于是有 $\Gamma ⊢\xi$, 而由定理 3.6 有 $\Gamma ⊢\neg \xi$, 即 $\Gamma$ 不一致, 矛盾. 然后证明从右至左, 反设 $\psi \notin \Gamma$ 或 $\neg \xi \notin \Gamma$. 由 $\phi \notin \Gamma$ 和 $\Gamma$ 的极大一致性, 有 $\neg \phi =\neg (\psi \to \xi )\in \Gamma$. 若 $\psi \notin \Gamma$, 则 $\neg \psi \in \Gamma$, 由推论 4.4 得 $\Gamma ⊢\psi \to \xi$, 而 $\Gamma ⊢\neg (\psi \to \xi )$, 即 $\Gamma$ 不一致, 矛盾. 若 $\neg \xi \notin \Gamma$, 则 $\xi \in \Gamma$, 构造演绎序列: (1) $\xi \to \psi \to \xi$ (P1) (2) $\xi$ (假设) (3) $\psi \to \xi$ (MP, 1, 2) 于是 $\Gamma ⊢\psi \to \xi$, 同理矛盾得证.

综上所述, 上述构造保证了 $\upsilon (\Gamma )=1$, 即极大一致集可满足.

$\square$

经过一定的转换, 我们可以得到完全性定理的最终形式.

定理 4.11 (完全性定理). 如果 $\Gamma \models \phi$, 那么 $\Gamma ⊢\phi$.

证明. 我们证明其逆否形式, 即如果 $\Gamma ⊬\phi$, 那么 $\Gamma ⊭\phi$. 由 $\Gamma ⊬\phi$ 可得 $\Gamma \cup \left\{\neg \phi \right\}$ 一致, 否则由定理 4.5 有 $\Gamma ⊢\phi$, 矛盾.

根据引理 4.9, 可以将 $\Gamma \cup \left\{\neg \phi \right\}$ 扩充为极大一致集 $\Delta$, 而由引理 4.10, 存在赋值函数 $\upsilon$ 使得 $\upsilon (\Delta )=1$, 进而有 $\upsilon (\Gamma \cup \left\{\neg \phi \right\})=\upsilon (\Gamma )=\upsilon (\neg \phi )=1$, $\upsilon (\phi )=0$, 即 $\Gamma ⊭\phi$.

$\square$

至此, 我们完成了本文的目标, 阐明了语义系统和公理系统蕴含关系的等价性质.

1.	余俊伟, 赵晓玉, 裘江杰, 张立英. (2020). 数理逻辑, 北京: 人民大学出版社.