数理逻辑之 命题逻辑可靠性

好几天没写了，因为这几天回到了北京，比较乱。

上海找工作依然没着落，再从北京看看。待好运！

 

命题逻辑的主要规则已经说完了。

对于逻辑学来说，一个很重要的部分就是“为什么这样”？

要证明一个逻辑系统是正确的，需要证明两部分：它的可靠性和它的完备性。

今天先来说可靠性。

 

下面的内容可能要求你对前面的课程很熟悉才比较方便。

 前面说了数学归纳法。归纳法是出现使得我们通过假设一些正确的前提就能得到正确的结论。

所以我们现在可以这样来证明一个结论：

φ1, φ2, . . . , φn |- ψ

 当命题φ1, φ2, . . . , φn都是正确的时候，如果可以得出ψ，则ψ就是正确的结论。

 

那么你有没有疑问：会不会出现这种情况，如果在真值表中前提假设都是正确的却能得出结论是错误的？

你可能会想当然的认为：不可能吧。但是why？

你的确说对了：不可能的。怎么证明呢？

要证明这个结论，我们需要在真值表中把前提都赋值为T，看能否出现结论为F的情况。

当然了，你一下子就想到了：需要把宇宙中的全部相继式都尝试过才能得出这个结论。

太扯淡了是吧！咋办呢？

还记得“语意继承关系吗”？在数理逻辑之合式公式中我们说过这个概念：如果某个（或某些）合式公式Θ1, Θ2, Θ3, …, Θn每次求值为T的时候都能使公式Ψ为T，则称它们之间是语意继承关系或语意蕴含关系，记作

Θ1, Θ2, Θ3, …, Θn |= Ψ

 考虑如下例子：

p ∧ q |=  p成立吗？

p ∨ q |=  p成立吗？

¬q, p ∨ q |= p成立吗？

p |= q ∨¬q成立不？

第一个例子当合取为T时子式肯定为T，所以成立；

第二个就不一定了，因为析取为T，只要任意一个为T就可以，不能得出某个子式为T；

第三个因为¬q为T所以q为F了，又析取为T所以p为T，成立；

第四个p为T是右边不影响，因为总是对的（这种公式称为重言式）。

所以我们的证明变成了另一种方式：如果相继关系成立，则语意继承关系成立。即

如果φ1, φ2,..., φn |- ψ 成立，则 φ1, φ2,..., φn |= ψ 成立。

可就是说我们不去考虑公式的真值表了，去看看它的相继关系成不成立就行了。 

 

上面这个称为命题逻辑的可靠性。

证明：

由于相继关系成立，我们有ψ可由φ1, φ2,..., φn导出。

我们的证明需要对证明的长度使用数学归纳法。

所谓证明的长度就是它的行数。

在使用归纳法前我们先提一个断言M(k)：

如果φ1, φ2,..., φn |- ψ 成立(其中n>0，相继关系的证明行数为k)，则 φ1, φ2,..., φn |= ψ 成立

 在看一个例子（别嫌啰嗦，否则直接证明就晕倒了）：

 

相继关系p ∧ q → r |- p → (q → r)的证明如下：

 
 一共有7行。如果去掉最后一行，最外层的盒子的结论就没有了，我们改写一下：

 
 我去掉了最外面的框，这样第二行就变成了前提。

当然了上面的证明过程是针对p ∧ q → r, p |- p → r的，这时候p ∧ q → r, p |= p → r也成立。

而且p ∧ q → r |= p → (q → r)也是成立的。why？

（如果你还记得一般相继式和定理的关系可能会有些释然）
我们的归纳假设是这样的：对于任意k'，k'<k，M(k')成立。我们希望能证明M(k)成立。

归纳基础：当k=1时，相继关系是这样的：ψ |- ψ,这时候语意继承关系ψ |= ψ成立，因为左边赋值T则右边也是T（当然了左边是F右边也是F，不过我们不关心）；

归纳步骤：假设相继关系φ1, φ2,..., φn |- ψ的证明过程是k行，并且所有小于k行的证明过程都是成立的。

证明过程的结构是这样的：

 
 这个描述中有两点令人疑惑：一是在n个前提写完之后到结论得出前发生了什么；二是结论的得出使用了什么规则。

 第一个疑惑数学归纳法帮我买解决了。第二个问题是大大的问题，证明过程基本花费在上面了。

由于不确定最后使用的什么规则，我们只能一个一个的来证明了。 

假设最后的规则是合取引入（∧i），则ψ的形式是ψ1 ∧ψ2，并且合取引入规则使用在第k行。必然在k之上有两行是ψ1和ψ2，假设它们的行号是k1和k2。那么一定有相继关系φ1, φ2,..., φn |- ψ1和φ1, φ2,..., φn |- ψ1成立，它们的证明行数分别是k1和k2。根据归纳假设，有φ1, φ2,..., φn |= ψ1和φ1, φ2,..., φn |= ψ1成立。所以φ1, φ2,..., φn |= ψ成立（为啥？）；

假设最后的规则是析取消去（∨e），则ψ之前必有形式是ψ1∨ψ2，得出结论的行号是k'(k'<k)。这样存在一个短证明φ1, φ2,..., φn |- ψ1∨ψ2，根据析取消去规则必有两个盒子分别证明φ1, φ2,..., φn,ψ1 |- ψ和φ1, φ2,..., φn,ψ2|- ψ。根据归纳假设，φ1, φ2,..., φn |= ψ1∨ψ2和φ1, φ2,..., φn,ψ1 |= ψ和φ1, φ2,..., φn,ψ2|= ψ都成立。这足以保证φ1, φ2,..., φn |= ψ成立（为啥？）；

其他规则类似。

 
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->