上文说了数理逻辑的可靠性，今天说完备性。
说之前先提一下自己这一周找工作的进展：略有收获，依然惨淡。
可以下读我的博客《找工作时怎么谈待遇？果然是一个老大难》。
前面证明了如果φ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）即可。
证毕。
