2.1. 命题逻辑

本节将介绍最简单的一种语言, 并描述其性质.

定义 2.1.0.1 (命题逻辑, 语法蕴含). 命题逻辑的语言 $L_{p ro p}$ 有一个可数集合的变量符号和以下这些有限个函数符号:

1.	零元函数符号或常元符号, 真 $⊤$
2.	零元函数符号或常元符号, 假 $⊥$
3.	一元函数符号, 非 $\neg$
4.	二元函数符号, 且 $\land$
5.	二元函数符号, 或 $\lor$
6.	二元函数符号, 蕴含 $\to$

我们定义命题逻辑中的项指的是按照以下操作规则得到的只有有限长度的字符串:

1.	$⊤$ 与 $⊥$ 是项.
2.	若 $p$ 是变量符号, 则 $p$ 是项.
3.	若 $t$ 是项, 则 $\neg t$ 是项.
4.	若 $t_{1}$ 与 $t_{2}$ 是项, 则 $(t_{1} \land t_{2})$ 、 $(t_{1} \lor t_{2})$ 、 $(t_{1} \to t_{2})$ 是项.

且若一个有限长度的字符串不能经由此过程生成, 则不称其为项.

我们定义命题逻辑的公理为全体以下这些形式的项, 其中 $p$ 、 $q$ 、 $r$ 是任意的项:

1.	$P_{1}$ : $(p \to (q \to p))$
2.	$P_{2}$ : $((p \to (q \to r)) \to ((p \to q) \to (p \to r)))$
3.	$P_{3}$ : $((\neg p \to q) \to ((\neg p \to \neg q) \to p))$
4.	$((p \land q) \to \neg (p \to \neg q))$ , $(\neg (p \to \neg q) \to (p \land q))$
5.	$((p \lor q) \to (\neg p \to q))$ , $((\neg p \to q) \to (p \lor q))$
6.	$(⊤ \to (p \lor \neg p))$ , $(p \to ⊤)$
7.	$(⊥ \to p)$ , $((p \land \neg p) \to ⊥)$

注意, 每个这些形式的项都叫公理, 所以其实我们有无穷多个公理. 我们给出的规则无非是让我们能递归地枚举它们. 因此, 上面列出来的那些句子又被我们称为公理模式, 意为 " 长成这样子的都是公理 ".

我们定义命题逻辑的推理规则为分离规则: 若 $p$ 且 $(p \to q)$ , 则 $q$ . 其中 $p$ 与 $q$ 是任意的项.

我们定义形式推理 ${p_{1}, p_{2}, ..., p_{n}} ⊢ p$ 为一串项 ${q_{i} ∣1 \leq i \leq N, n < N}$ 的缩略记法, 这些项满足: 对任何 $1 \leq i \leq N$ , 都有 $q_{i}$ 满足:

1.	$q_{i} = p_{1}$ 或 $q_{i} = p_{2}$ 或... 或 $q_{i} = p_{n}$ , 或
2.	存在一个 $1 \leq j < i$ 使得 $q_{i} = q_{j}$ , 或
3.	存在一个 $1 \leq j < i$ 和一个 $1 \leq k < i$ 使得 $q_{k} = (q_{j} \to q_{i})$ (换言之, $q_{i}$ 由推理规则从之前的项中得来),

其中等号是字符串的等号 (所有符号均相同); 且有 $p = q_{N}$ . 这个 $⊢$ 读作语法蕴含.

我们扩张地定义 $Σ ⊢ p$ , 其中 $Σ$ 是一集项, 为 ${p_{1}, p_{2}, ..., p_{n}} ⊢ p$ 的概称, 其中 ${p_{1}, p_{2}, ..., p_{n}} \subseteq Σ$ .

如果 $\emptyset ⊢ p$ , 则称 $p$ 是一个定理.

我们又称这些项为命题, 变量符号为原子命题.

细心检查的读者会发现, 上述定义虽然冗长, 但是都符合我们对命题真、假的一般认知. 不过这样定义的意思是, 我们正在反思我们的推理行为, 因此我们用日常生活所用的元语言定义出了一套对象语言, 并且通过种种定义来试图让它能做的事恰好就是我们想要反思的事. 这类定义以后经常出现, 我们会把元语言命题全部以汉语说明, 而对象语言的命题则尽量以符号说明, 以示差别.

评注. 很多时候我们只考虑 $\to$ 与 $\neg$ , 此时我们在无括号简写时默认 $\neg$ 只管右边第一个符号, $\to$ 从右向左算 (即 $p \to q \to r$ 是 $(p \to (q \to r))$ ).

为了说明以上定义是良定的 (换言之, (在元语言中! ) 无矛盾的), 我们还需要验证以下关于字符串的命题, 其证明留作练习. (Hint: 对命题的长度做归纳)

定理 2.1.0.2 (唯一可读性). 我们考虑把每个命题按照其构造方式做成一棵命题的不多于二叉的树, 即令 $(p * q)$ 的两个子节点为 $p$ 和 $q$ , 其中 $*$ 是二元函数符号之一, 而 $\neg p$ 只有一个子节点 $p$ , 最后全部叶节点都是原子命题或常元符号.

唯一可读性定理指出, 这棵二叉树唯一确定这个命题, 而这个命题也唯一确定这棵树.

如果这是一本逻辑书, 现在应当让大家用这个形式推理的定义和上面的公式组来练习证明一些显而易见的重言式, 不过这里就免去这些功夫了. 今后命题逻辑的重言式我们都会不加说明地默认.

现在我们还有另一种方法: 前面只是从形式的角度定义了推理和语法蕴含, 我们还可以从意义的角度来定义语义蕴含的概念.

定义 2.1.0.3 (语义蕴含). 注意到我们有一个可数集合的变量符号, 不妨记这个集合为原 , 代表原子命题. 我们现在考虑一个函数: 赋’, 它从原映到 ${$ 真, 假 $}$ , 也就是说给每个原子命题赋一个真或者假作为值. 不难发现, 赋’ 可以提升为定义域更大的函数赋 , 它从全体命题的集合映到 ${$ 真, 假 $}$ , 也就是给每个命题都赋一个真或者假作为值, 使得 (按长度):

1.	赋 $⊤$ 为真, $⊥$ 为假;
2.	每个公理都赋值为真;
3.	若赋 $p$ 真, 则赋 $\neg p$ 假;
4.	若赋 $p$ 假, 则赋 $\neg p$ 真;
5.	若赋 $p$ 真 $q$ 真, 则赋 $(p \land q)$ 真, $(p \lor q)$ 真, $p \to q$ 真;
6.	若赋 $p$ 真 $q$ 假, 则赋 $(p \land q)$ 假, $(p \lor q)$ 真, $p \to q$ 假;
7.	若赋 $p$ 假 $q$ 真, 则赋 $(p \land q)$ 假, $(p \lor q)$ 真, $p \to q$ 真;
8.	若赋 $p$ 假 $q$ 假, 则赋 $(p \land q)$ 假, $(p \lor q)$ 假, $p \to q$ 真;

现在我们考虑所有的赋 . 我们定义 $Σ ⊨ p$ , 称作前面集里的命题语义蕴含了最后一个命题, 若所有将前面命题都赋真值的赋都会把最后的 $p$ 赋为真值.

如果 $\emptyset ⊨ p$ , 则称 $p$ 是一个重言式.

这个定义没有矛盾是根据唯一可读性定理来的, 读者可以想想看为什么. 现在我们有一个最重要的定理, 它声称语法蕴含和语义蕴含在我们这些用元语言的人看来是同一件事. 注意, 对象语言现在还说不出语义蕴含这句话, 所有和语义蕴含相关的事都是我们元语言人的自嗨.

定理 2.1.0.4 (可靠性与完备性). 我们说命题逻辑是可靠的, 因为只要有 $Σ ⊢ p$ , 就有 $Σ ⊨ p$ .

我们说命题逻辑是完备的, 因为只要有 $Σ ⊨ p$ , 就有 $Σ ⊢ p$ .

证明. 可靠性是很简单的, 我们只需要逐个验证缩略的那一串项由于归纳法和我们对赋的定义必须逐个为真, 递推到最后一个自然就为真了.

完备性则相当不平凡: 我们只是对赋的性质加以描述, 怎么就能产生一个真真切切的推理序列呢? 为了克服这个困难, 我们将这个问题转换一下.

我们称一集命题 $Σ$ 是一致的, 若不存在从这个命题集到 $⊥$ 的形式推理序列; 称为可满足的, 若存在一个赋把集里的每个命题都赋真值. 我们首先证明第一个性质:

性质 2.1.0.5. $Σ ⊨ p$ 则 $Σ ⊢ p$ , 当且仅当 $Σ$ 一致则 $Σ$ 可满足.

这个性质的证明采取反证法. 首先再引入第二个性质.

性质 2.1.0.6. $Σ ⊢ p$ 当且仅当 $Σ \cup {\neg p}$ 不一致.

第二个性质的证明: 仅当是显然对, 当的时候注意公理

⊥ \to p

和

((\neg p \to p) \to ((\neg p \to \neg p) \to p))

, 再发现定理

(\neg p \to \neg p)

, 可以连续做推导

Σ \cup {\neg p} ⊢ p \Rightarrow Σ ⊢ (\neg p \to p) \Rightarrow Σ ⊢ p

, 证毕.

第一个性质的仅当: 反证, 假设有一个一致命题集 $Σ$ 不可满足, 则必有 $Σ ⊨ p$ 对任何 $p$ 成立, 进而由条件有 $Σ ⊢ p$ 对任何 $p$ 成立, 所以 $Σ ⊢ ⊥$ , 这与一致性假设矛盾, 证毕.

第一个性质的当: 反证, 若有一个 $Σ ⊨ p$ 且 $Σ \neq ⊢ p$ , 性质二指出 $Σ \cup {\neg p}$ 一致, 从而不妨设某个赋满足之. 这样赋就必须同时把 $p$ 和 $\neg p$ 都赋真值, 矛盾, 证毕.

现在, 我们经由第一个性质, 只需要来证明: 一致命题集都是可满足的, 从而避开了具体构造证明序列的麻烦.

我们称命题集 $Σ$ 是极大一致的, 如果它确是一致的, 且对任何不在其中的 $p$ , 都有 $Σ \cup {p}$ 不一致. 我们引入第三个性质.

性质 2.1.0.7. (Lindenbaum) 每一个一致的命题集都可以扩张成一个极大一致的命题集.

第三个性质的证明: 由于我们默认的可数性, 我们可以枚举全体公式

p = p_{n}, n \in N

. 我们在每一步总能从

p_{n}

与

\neg p_{n}

里选且仅选一个加入原有的命题集中, 使得命题集仍然一致 (为什么). 最后, 我们把所有有限步后扩充得到的命题集并在一起, 装作自己做了无穷次扩张, 得到的这个命题集就是极大一致集 (为什么).

于是最终完备性的证明就很简单了: 我们把一致命题集扩充为极大一致集, 然后定义赋把这个极大一致集全部赋真, 把其外的命题全部赋假. 不难验证这使得这个极大一致集可满足, 从而原来的一致命题集也是可满足的. 证毕.

$□$

名字空间

视图

2.1. 命题逻辑