数理逻辑之 命题逻辑完备性

上文说了数理逻辑的可靠性，今天说完备性。

说之前先提一下自己这一周找工作的进展：略有收获，依然惨淡。

可以下读我的博客《找工作时怎么谈待遇？果然是一个老大难》。

 

前面证明了如果φ1, φ2,..., φn |- ψ 成立，则 φ1, φ2,..., φn |= ψ 成立。

现在需要证明φ1, φ2,..., φn |= ψ 成立，则 φ1, φ2,..., φn |- ψ 成立。

证明过程分三步：

证明|= φ1 → (φ2 → (φ3 → (...(φn → ψ) ... ))) 成立；
证明|- φ1 → (φ2 → (φ3 → (...(φn → ψ) ... ))) 成立；
证明 φ1, φ2, . . . , φn |- ψ成立。

 一三两步的转换过程比较简单，步骤二比较费神。

证明：

步骤一：

还记得重言式的概念吗？一个命题逻辑公式 φ称为重言式，当且仅当它在真值表中的每一次赋值都为T。

即= φ。

假设φ1, φ2, ... , φn |= ψ，我们来证明φ1 → (φ2 →(φ3 → (...(φn → ψ) ... )))是重言式。由于后式是嵌套蕴含，所以当且仅当φ1, φ2, ... , φn都为T且ψ为F时整个公式才为F。但是这种赋值就和φ1, φ2, ... , φn |= ψ成立矛盾了。所以|=φ1 → (φ2 →(φ3 → (...(φn → ψ) ... )))成立。

步骤二：

先说一个定理：如果|=η成立则 |-η成立。换句话说，如果η是重言式，则 η 是定理。

由于η由n个原子命题组成，所以它的真值表组合有2^n行。每一行都是一个相继式（当然可能和其他行相同）。相继式的形式如下

ˆp1, ˆp2, . . . , ˆpn |- φ
ˆp1, ˆp2, . . . , ˆpn |- ┐φ

 对于任意1<=i<=n，在第 l 行中若pi为T，则ˆpi取pi，否则取┐pi。

这样，如果φ为T取式1，否则取式2。

1。如果φ是原子命题，那么很容易证明p|-p和￢p |- ￢p

2。如果φ的形式是否定，则需要分别考虑φ为T和F的情况。

3。如果φ的形式是蕴含，也要分情况。当φ为F时一定是T蕴含F；为T是有三种情况。

4。如果φ的形式是合取，有四种情况要考虑。

5。如果φ的形式是析取，同上。

每一步证明过程比较烦长，但是思路比较简单。此处略去，有兴趣的读者可以自己尝试。

 |=φ1 → (φ2 →(φ3 → (...(φn → ψ) ... )))在真值表中总是为T。ˆp1, ˆp2, . . . , ˆpn |- η也是成立的。

现在我们的目标变成了不使用任何前提假设证明 |-η成立。

先来看一个例子：p ∧q → p。

这个公式有两个原子命题，所以有四个构成相继式：

p, q |- p ∧ q → p
¬p, q |- p ∧ q → p
p, ¬q |- p ∧ q → p
¬p, ¬q |- p ∧ q → p

 

 由于要证明定理，我们必须摒弃相继式的左端前提。这里使用LEM规则和析取消去规则 进行证明（还记得这些命题演算规则吗）：

 这个是证明定理的通用定式。虽然证明p ∧q → p不需要这么长。还记得三角函数里的万能公式吗？这个也一样，可能它不是最好的，但它是管用的。

步骤三：

现在需要证明 φ1, φ2,..., φn |- ψ 了。上一部已经证明了|-φ1 → (φ2 →(φ3 → (...(φn → ψ) ... )))。

把φ1, φ2,..., φn 都当作前提，使用n次蕴含消去规则（∧e）即可。

证毕。