1. 命题逻辑

1.1语言

在我们所生活的世界中, 很久很久以前人们就学会了从 0 开始数数. 我们数出的 0, 1, 2 等等将被称作元自然数或是标准自然数, 默认用小写字母 $i,j,k,l,m,n$ 表示. 我们在元自然数上熟知有加法、乘法等各种操作, 最重要的是有数学归纳法.

定理 1.1.1 (数学归纳法). 给定一个性质 $P$, 若 $P(0)$ 成立, 且任给元自然数 $n$ 均有 $P(n)\to P(n+1)$, 则 $P$ 对每个元自然数成立.

首先, 我们对以上采取的立场作一解释. 所谓元, 自然是相对于对象而言; 因为我们今后要将大部分数学活动作为对象进行反思, 我们需要一个元理论来进行这一反思活动, 元自然数上的以上理论正是我们所用的元理论. 笔者对这一理论 (可以理解为 PA) 的辩护是康德式的, 即认为这是先天综合知识.

另一方面, 将元自然数又称作标准自然数则是一种约定俗成. 为不同却一致的实体指定标准本是一个困难的任务, 但好在这些元自然数有各种各样的唯一确定性质和辩护, 一般没什么人会对其提出质疑.

接下来, 我们学会了给字母加上下标, 以创造不同的符号. 我们称 $p_0$, $p_1$, $p_2$ 等记号为命题符号, 当无需刻意指定下标上的元自然数时默认用小写字母 $p,q,r$ 表示. 我们又引入两个符号 $\to$ 与 $\perp$, 这就是命题逻辑的语言元素.

注 1.1.2. 如果我们认为朴素集合论也具有良好的辩护, 可以将以上陈述抽象为一句话: 命题逻辑的语言元素是三元组 $\mathcal{L}=\{P,\to ,\perp \}$, 其中 $P$ 是可数集. 不过这时 $P$ 上的良序需要由可数性和 $\omega$ 上的良序共同指出, 相对而言不够自然.

我们今后将全体语言元素简称为语言. 命题逻辑的语言中因而有三类对象: 命题符号, $\to$ 与 $\perp$. 我们接下来按照字符串的长度定义语言对象:

定义 1.1.3. 命题逻辑的语言对象如下按字符串长度归纳地定义:

1.	命题符号 $p_n$.
2.	$\perp$.
3.	$\to \phi \psi$, 这里 $\phi$ 和 $\psi$ 是语言对象.

语言对象默认用小写希腊字母 $\phi ,\varphi ,\psi$ 表示, 并被称为公式.

注 1.1.4. 注意, 命题逻辑的公式现在已经被反思而成为一种对象了, 现在仍然保留在元语境中的只有公式的长度. 这一归纳定义事实上由一层编码和数学归纳法决定, 我们将在后面详细考察这一过程.

为了方便, 我们有时也将前缀表达式 $\to \phi \psi$ 记为中缀表达式 $\phi \to \psi$, 引入左右小括号确定构造次序, 并默认 $\to$ 右结合.

公式有唯一且能行的方法确定其构造过程. 不过我们这里还不需要证明这个过程能行, 因此只需要证明一个常见版本的定理.

定理 1.1.5 (唯一可读性). 任给公式 $\phi$, 存在最短的公式序列 $({\phi }_0,...,{\phi }_n)$ 使得 ${\phi }_n=\phi$, 且每个 ${\phi }_i$ 或是某个 $p_m$, 或是 $\perp$, 或是 ${\phi }_j\to {\phi }_k$, 这里 $j,k<i$, 且这一序列中的公式在不记顺序时唯一. 我们称此定理中宣称的公式序列为 $\phi$ 的一个最短构造序列.

证明. 由公式的定义知存在一个构造序列, 因此由数学归纳法给出的最小自然数原理指出存在最短构造序列. 我们现在只要证明它在不记顺序时唯一. 我们作以下定义.

定义 1.1.6. 若一个公式 $\psi$ 在 $\phi$ 的每个最短构造序列中出现, 则称 $\psi$ 是 $\phi$ 的一个子公式.

引理 1.1.7. $\phi$ 的所有子公式可以给予适当的排序, 使之成为一个 $\phi$ 的构造序列.

证明. 对 $\phi$ 的结构归纳. 下面的等号意为形如, 以后默认此记号.

1.	$\phi =p_n$ 或 $\phi =\perp$, 这两个情况都是显然的.
2.	$\phi =\to \varphi \psi$, 此时 $\phi$ 的全体子公式显然就是 $\varphi$ 的全体子公式、$\psi$ 的全体子公式, 再多加一个 $\phi$ 自己. 我们把 $\varphi$ 和 $\psi$ 的子公式构造序列串接在一起, 再在最后串接一个 $\phi$, 则这个序列恰好也是 $\phi$ 的一个构造序列.

由公式的定义, 这种归纳法确实遍历所有公式, 因此我们对所有的公式验证了此引理.

$\square$

以上引理已经说明, 所有子公式排列而成的构造序列恰好就是一个最短构造序列, 因此最短构造序列中的公式在不记顺序时恰好就是全体子公式.

$\square$

注 1.1.8. 这种归纳证明的方法是非常典范的.

最后, 我们引入一些常见的记号.

定义 1.1.9. 下面的:=意为将右侧式简记为左侧式, 或定义为, 以后默认这种记法.

1.	$\top :=\perp \to \perp$
2.	$\neg \phi :=\phi \to \perp$
3.	$\phi \vee \psi :=(\neg \phi )\to \psi$
4.	$\phi \wedge \psi :=\neg ((\neg \phi )\vee (\neg \psi ))$

我们称 $\top$ 为真, 称 $\perp$ 为矛盾 (或为假), 称 $\to$ 为推出 (或为蕴含), 称 $\vee$ 为或 (或为析取), 称 $\wedge$ 为且 (或为合取).

1.2语法

有了公式, 我们现在来定义推理规则, 又称语法. 这里介绍的是 Hilbert 式的语法.

定义 1.2.1. 我们统称以下三种公式为公理:

1.	$P_1(\phi ,\psi ):=\phi \to \psi \to \phi$, $\phi$ 与 $\psi$ 是两个公式.
2.	$P_2(\phi ,\psi ,\varphi ):=(\phi \to \psi \to \varphi )\to (\phi \to \psi )\to \phi \to \varphi$, $\phi ,\psi$ 与 $\varphi$ 是三个公式.
3.	$P_3(\phi ,\psi ):=(\neg \phi \to \psi )\to (\neg \phi \to \neg \psi )\to \phi$, $\phi$ 与 $\psi$ 是两个公式.

有了递归可枚举的公理们, 我们就可以定义证明序列了.

定义 1.2.2. 一列公式 $({\phi }_0,...,{\phi }_n)$ 被称作从一个公式集 $\Sigma$ 到公式 $\phi$ 的一个证明序列, 若 $\phi ={\phi }_n$ 且每个 $0\le i\le n$ 均满足:

1.	${\phi }_i$ 是公理, 或
2.	${\phi }_i$ 在 $\Sigma$ 中, 或
3.	${\phi }_j={\phi }_k\to {\phi }_i$, 这里 $0\le j,k<i$.

将存在 $\Sigma$ 到 $\phi$ 的证明序列这件事记为 $\Sigma ⊢\phi$.

这个 $⊢$ 直接读作证明, 它有各种性质, 不过这些性质的证明都繁琐但简单, 我们仅仅是列举一些在下面.

命题 1.2.3. 以下论证成立.

1.	$\psi ⊢\phi$ 当且仅当 $⊢\psi \to \phi$.
2.	$\{{\psi }_0,...,{\psi }_n\}⊢\phi$ 当且仅当 ${\psi }_0\wedge ...\wedge {\psi }_n⊢\phi$.
3.	$\Sigma ⊢\phi$ 当且仅当存在有限个 ${\psi }_0,...,{\psi }_n\in \Sigma$ 使得 $\{{\psi }_0,...,{\psi }_n\}⊢\phi$
4.	$\{\phi ,\neg \phi \}⊢\perp$ 且 $\perp ⊢\phi$, 这里 $\phi$ 是任意公式.
5.	$⊢\phi \to \phi$
6.	$⊢\neg \neg \phi \to \phi$

1.3语义

我们现在定义一种看起来与可证明不一样的概念, 它称作真. 首先, 我们给出赋值的概念.

定义 1.3.1. 一个原始赋值 $s$ 将每个不是 $\to$ 的语言元素对应为 $\top ,\perp$ 两符号之一, 且将 $\perp$ 对应为 $\perp$.

每个原始赋值 $s$ 都归纳地成为一个赋值 $\bar{s}$, 它将每个公式对应于 $\top ,\perp$ 两符号之一, 这个对应由以下规则归纳地给出:

1.	$\bar{s}(\perp )=s(\perp )=\perp$
2.	$\bar{s}(p_n)=s(p_n)$
3.	$\phi =\varphi \to \psi$, 且 $\bar{s}(\varphi )=\top$ 而 $\bar{s}(\psi )=\perp$, 则 $\bar{s}(\phi )=\perp$.
4.	$\phi =\varphi \to \psi$, 且 $\bar{s}(\varphi )=\perp$ 或 $\bar{s}(\psi )=\top$, 则 $\bar{s}(\phi )=\top$.

显然, 一个赋值将每个公式判断为真或假. 我们借此给出满足的定义.

定义 1.3.2. 若任何把公式集 $\Sigma$ 中的每个公式都赋真的赋值都同时把公式 $\phi$ 赋真, 则称 $\Sigma$ 满足 $\phi$, 记作 $\Sigma \models \phi$.

这个 $\models$ 与 $⊢$ 一样有各种性质, 这些性质的证明同样也都繁琐但简单, 我们仅仅是列举一些在下面.

命题 1.3.3. 以下论证成立.

1.	$\psi \models \phi$ 当且仅当 $\models \psi \to \phi$.
2.	$\{{\psi }_0,...,{\psi }_n\}\models \phi$ 当且仅当 ${\psi }_0\wedge ...\wedge {\psi }_n\models \phi$.
3.	$\{\phi ,\neg \phi \}\models \perp$ 且 $\perp \models \phi$, 这里 $\phi$ 是任意公式.
4.	$\models \phi \to \phi$
5.	$\models \neg \neg \phi \to \phi$
6.	$\models \phi$, 这里 $\phi$ 是公理.

注意, 不存在赋值使得 $\perp$ 被赋为 $\top$, 那么使得 $\perp$ 被赋为 $\top$ 的全体赋值就满足任何对它们的要求 (因为其实没有赋值需要回应这些要求).

1.4可靠性与完备性

既然 $⊢$ 和 $\models$ 的性质如此相似, 我们自然会问它们在外延的意义下是否是同一个关系, 答案是肯定的.

定理 1.4.1 (命题逻辑的可靠性). $\Sigma ⊢\phi$, 则 $\Sigma \models \phi$.

证明. 我们沿着证明序列考察其中所有的公式的赋值. 我们证明, 任何将 $\Sigma$ 中公式都赋真的赋值也必须将这个证明序列 $({\psi }_0,...,{\psi }_n)$ 中的每个公式都赋真, 进而 $\phi ={\psi }_n$ 被赋真. 对序列下标 $i$ 归纳.

1.	${\psi }_i$ 是公理, 由命题 1.3.3 论证.
2.	${\psi }_i$ 是 $\Sigma$ 中的句子, 由对赋真的要求显然.
3.	存在 ${\psi }_j={\psi }_k\to {\psi }_i$, 这时由于 ${\psi }_k$ 和 ${\psi }_j$ 都被赋真, ${\psi }_i$ 必须被赋真.

$\square$

然而, 另一个方向的证明却不轻松, 因为从满足关系造出所需的证明序列的能行方法是困难的. 我们采取一种绕行的手段.

定义 1.4.2. 称 $\Sigma$ 是一致的, 若不存在它到 $\perp$ 的证明. 称 $\Sigma$ 是可满足的, 若存在把其中所有公式都赋真的赋值. 称 $\Sigma$ 是极大一致的, 若 $\Sigma$ 一致, 且任意不在其中的 $\phi$ 加上 $\Sigma$ 都可以证明 $\perp$.

定理 1.4.3. 任何一致的 $\Sigma$ 都可以扩张为一个极大一致的 $\Gamma$.

证明. 我们递归地枚举所有的公式 ${\phi }_n$, 并给出一列一致的 ${\Sigma }_n$. 令 ${\Sigma }_{-1}=\Sigma$, 然后:

1.	若 ${\phi }_n$ 在 ${\Sigma }_{n-1}$ 中, 则 ${\Sigma }_n={\Sigma }_{n-1}$.
2.	若 ${\phi }_n$ 不在 ${\Sigma }_{n-1}$ 中, 由于 ${\Sigma }_{n-1}$ 一致, ${\phi }_n$ 与 $\neg {\phi }_n$ 不能均加入 ${\Sigma }_{n-1}$ 后都得到 $\perp$ 的证明, 因此可以从二者中选取一个加入 ${\Sigma }_{n-1}$ 得到仍然一致的 ${\Sigma }_n$.

最后, 注意到 ${\Sigma }_n\subseteq {\Sigma }_{n+1}$, 我们令 $\Gamma$ 包含 $\phi$ 当且仅当存在 $n$ 使 ${\Sigma }_n$ 包含 $\phi$. 不难验证 $\Gamma$ 是极大一致的, 因为由归纳过程我们知道任何公式与其否定都有且仅有一个出现在 $\Gamma$ 中.

$\square$

定理 1.4.4. 极大一致的 $\Gamma$ 一定是可满足的.

证明. 我们令原始赋值 $s$ 把 $\Gamma$ 中的所有命题变元赋真, 把 $\Gamma$ 外的所有命题变元赋假. 归纳可知它给出的赋值 $\bar{s}$ 恰好把所有的 $\Gamma$ 中的公式赋真, 把所有 $\Gamma$ 外的公式赋假.

$\square$

现在, 我们来证明完备性定理.

定理 1.4.5 (命题逻辑的完备性). $\Sigma \models \phi$, 则 $\Sigma ⊢\phi$.

证明. 这是因为 $\Sigma \models \phi$ 则 $\Sigma ⊢\phi$, 当且仅当 $\Sigma$ 一致则 $\Sigma$ 可满足.

仅当: 反证, 假设有一个一致命题集 $\Sigma$ 不可满足, 则必有 $\Sigma \models \phi$ 对任何 $\phi$ 成立, 进而由条件有 $\Sigma ⊢\phi$ 对任何 $\phi$ 成立, 所以 $\Sigma ⊢\perp$, 这与一致性假设矛盾.

当: 反证, 若有一个 $\Sigma \models \phi$ 且 $\Sigma /⊢\phi$, 这指出 $\Sigma \cup \{\neg \phi \}$ 一致, 从而不妨设某个赋值满足之. 这样这个赋值就必须同时把 $\phi$ 和 $\neg \phi$ 都赋真值, 矛盾.

现在, 一致公式集总是可以扩张为极大一致公式集, 而后者是可满足的, 因此一致公式集总是可满足的.

$\square$