转载自CSDN博客：http://blog.csdn.net/on_1y/article/details/8727346
原作者：on_1y
1 导言
初学数理逻辑的时候，一个非常重要的点就是对可靠性与完备性概念的理解，这两个概念极为重要，却又经常让人觉得难以理解。
说它重要是因为它涉及逻辑系统的基本框架，初学数理逻辑，最重要的倒不在于你有多高超的技巧去推导那些公式，而在于对一些基本概念的理解和把握，这是思想层面的，如同学习概率论和数理统计不在于记住那几个公式和定理， 而在于获得一些基本的概率和统计的思想。TED演讲时，有一次一位在线教育的创始人谈到教育时说到，我们教授学生知识，不是让他们仅仅记住那些公式，而是改变他们认识世界的方式。请大家一定记住这一点。同时也请注意，这句话不是在说 记住公式没有用。学习数理逻辑，要时刻提醒自己，我们需要去推导定理，但目的不在于此。可靠性与完备性之所以让人难以理解，原因是多方面的。一方面是初学数理逻辑，根本不知道书上那些定理是要做什么，也就是前面说的，对知识的整体没有一个宏观的把握，注意：这是教师的责任。另一方面在于对语法和语义不理解，经常将 二者混在一起看。而这一方面的“不理解”，又在于我们将现实世界的逻辑与形式系统中逻辑又混在一起看。 下面就谈一下我对可靠性与完备性的理解。特别需要说明的是，这是针对命题逻辑的，并且我也是初学，很可能有一些错误，请不怀疑的怀疑，怀疑的指出。
要谈可靠性与完备性，需要先理解语法和语义，把这两个概念弄清楚了，理解可靠性与完备性就会水到渠成。
命题逻辑系统由语法和语义两部分组成。一旦定义了语法和语义，整个逻辑系统也就构建好了。下面我们开始构造命题逻辑系统。
2 语法
我们首先从几个问题开始。
2.1 语法是什么？
简单地说，语法就是一些规则的集合。那规则又是什么？规则是人为确定的一些原则，许多情况下，规则来源于现实世界， 同时又用于指导对现实世界的理解。我们举一个自然语言语法中的例子：
主语 ＋ 谓语 ＋ 宾语
这就是一个基本的语法规则，而且是人为定义的。在没有这个定义之前，它就存在于语言当中，人们将这种在自然语言中 广泛出现的形式总结成简单的规则，这样方便了我们对语言的学习与利用。我们把一些经常出现的规则集合在一些，就构成了语法。请一定记住，一旦这些规则被从现实世界中剥离出来，它们就有了一定程度的独立性，不信赖于具体的含义。 例如，"我 吃 饭"，和 "饭 吃 我"都符合主谓宾结构，我们认为后者不正确不是因为主谓宾结构不对，而是它所表达的意思不正确，这是语义层面，而不是语法层面。
2.2 命题逻辑中的语法是什么？
命题逻辑中的语法就是一些自然推导规则(Natural deduction rules)的集合。那自然推导规则又是什么？我们回到现实世界。现实世界中，我们常常会做一些推理。
例如，你肯定能:
从“我喜欢计算机科学，而且我也喜欢数学”中 推理出 “我喜欢计算机科学”。
你也能:
从“我经常编写程序，而且我也经常读书” 中 推理出 “我经常编写程序”。
我们并没有意识到自己是在做推理，但是我们确确实实完成了一次推理，确且地说，是两次。并且我们发现这两次推理具有高度统一的形式：
A 而且 B 推出 A
其中的A和B被称作命题。我们可以把命题理解为可以判断真假的句子。
例如，“我喜欢计算机科学”是一个命题，但是“我喜欢文学吗？”就不是一个命题。
对比一下自然语言中语法规则的产生，这一次，我们再次将这些在现实世界中广泛出现的推理形式抽象出来，把他们组成一个集合，于是，我们就有了下面这组命题逻辑的自然推导规则集合。
解释一下这些符号的含义，例如当中的$\wedge -E1(And-Elimination 1)$:
其中的 $\phi , \varphi$ 我们叫做公式。公式可以是以下这些形式：
$p,\;q,\;p \wedge q,\;\neg q,\;(p \wedge q) \vee p,\;$...
其中的 $\wedge -E1$ ，我们叫做规则。e的意思是消除(elimination). 这条规则从 $\phi\wedge\varphi$ 中消除了 $\wedge$,只留下了前面的$\phi$, e1 中的 1 就是指 $\phi$,因为它排在第1个，对比一下 $\wedge -E2$ 就会明白了。
规则中的i表示引入(introduction). 规则的具体含义可参考1.至于其中的 $\neg , \rightarrow , $... ，我认为目前没有必要知道含义，你仅仅需要知道他们是一些推导规则就好了。虽然你们多半都知道含义，但是，现在把它们忘了吧。
请再一次又一次地记住，这些推导规则从现实世界中剥离出来后，就有了他们的独立性，和具体的含义无关，例如在$\wedge -E1$里，我们只知道 $\phi$ 和 $\varphi$ 是命题，有真假，但是，不管他们是真是假，都不影响这条规则的成立。这一点请千万注意。 例如：
$\phi$ = "我不喜欢计算机科学" （当然，这是假的）
$\varphi$ = "我喜欢数学"
由上面的那条推导规则，可以推出$\phi$,即"我不喜欢计算机科学",尽管这个结论是假的，但这和这条推导规则的成立无关。不能说， 这规则得出假的结论，所以这条规则就是不正确的。
2.3 推理和推理的有效性
前面在引入自然推导规则时，我们举了一些例子，如自然语言中的对应形式，包括命题的真假，等等。这一切都是为了 理解这些规则是怎么来的。那么，从现在开始，请忘掉那些例子，让你的知识保留在只知道图1所示的自然推导规则表.我们现在仅仅知道这张规则表，那么，这些规则用来做什么呢？ 这些规则可以用来推理。
2.3.1 什么是推理
看下面这种形式：
$\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \vdash \varphi$
这就叫一次推理(sequent).其中 $\phi$i 叫做前提(premise), $\varphi$ 叫做结论(conclusion). 例如，下面这个形式就叫一次推理。
$p,\; \neg\neg (q \wedge r) \vdash \neg\neg p \wedge r$
2.3.2 什么是推理的有效性
推理有效性的概念与可靠性，完备性直接相关，所以一定保证你理解它的含义。 推理的有效性是指：使用图1中定义的自然推导规则以及前提($\phi$i)，可以得出结论($\varphi$)。
例如我们如果问： $p,\; \neg\neg (q \wedge r) \vdash \neg\neg p \wedge r$ 是不是有效的，那只需要看我们能不能仅根据自然推导规则，将前提转化为结论。转化的过程，我们叫做：证明(proof).
下面就是这个推导的证明：
上面的证明过程，例如第6行，最右面的 ∧i 3,5 表示使用第3，5行的公式和规则∧i, 得到第6行的公式。
关于语法部分，现在只需要知道两件事：一：公式及自然推导规则表；二：推理和推理的有效性。
下面开始语义部分。
3 语义
3.1 语义是什么？
简单地说，语义就是语言所表达的含义。同样以自然语言为例：“我吃饭”
你很容易知道这句话是什么意思。但是你想过为什么你能知道这句话是什么意思吗？
原因在于，首先你知道“我”是什么意思，“饭”是什么意思，其次你知道“吃”是什么意思。最后，你明白“我吃饭”三个字连在一起是什么意思。你可能觉得这是一句废话，但是后面提到命题逻辑时，你可能就会明白为什么在这儿说了一句废话。
关于这句话，还需要有两点要说明：
一是，这句话是一个主谓宾的结构，但是即使你不知道这个句子的语法，你仍然可以知道它的含义。
二是，在主谓宾结构中：
主语和宾语可以取的值其实是一个集合：{我，你，饭，计算机，书,……},
谓语可以取的值也是 一个集合：{吃，看，打,……}.
句子代表的含义也构成一个集合：{我吃饭的含义，我看书的含义,……}.
同时，在 “我吃饭”这个句子与“我吃饭的含义”之间存在着一种映射关系。语义中如果没有这种映射关系，那么你说“我吃饭”的时候， 别人可能觉得你在看书。
3.2 命题逻辑中的语义是什么？
要问命题逻辑中的语义是指什么，我们首先需要知道命题逻辑中的语言指什么，如果我们连“句子”的概念都没有，那么我们如何知道“句子的含义”是什么呢？我们需要有这样一种观念，数理逻辑中，这些框架都是由我们人来定义的，如果没有语言， 那么：我们定义它。
对比自然语言中的句子，为什么我能给出
我吃饭
这样的句子呢？因为我知道句子的结构是
主语 谓语 宾语
同时，还知道主语，谓语，宾语可以取值的集合：
"我" ∈ {我，你，饭，计算机，书，……}
"饭" ∈ {我，你，饭，计算机，书，……}
"吃" ∈ {吃，看，打，……}
所以， 我们得到了一个句子:“我吃饭”。
在命题逻辑中，我们也有自己的“句子结构”，例如:
$\phi \wedge \varphi$
之所以没有自己的“句子”，是因为我们的公式 $\phi，\;\varphi$ 没有自己的取值的集合，所以，
我们首先定义公式取值的集合：$\{T, \; F\}$, $T$代表真，$F$代表假。
看到了吧，这和前面讲的“命题是可以判断真假的”是相关的。
有了取值集合，我们就可以定义自己的“句子”了：
$T \wedge F$, $T \vee T$, $T \rightarrow F$, ...
我们知道，语义是指句子的含义，现在有了句子了，那么句子的含义是什么呢？ 从自然语言的例子中，我们知道句子的含义是一个集合，在命题逻辑里，“句子含义”的集合仍然由我们来定义, 命题逻辑中我们只关心真与假，所以，这个集合，我们仍然定义为：$\{T, \; F\}$
好了，现在我们有了“句子”，有了“句子含义”取值的集合，那么定义一个语义系统，还需要 什么呢？同样对比自然语言的例子中，我们最后说的那一点，还需要一种映射，将句子与句子的含义映射起来，即将 $T \wedge F$ 等句子与 $T, \; F$映射起来。而这，就是耳熟能详，家喻户晓的， 真值表：
有了真值表，我们才知道 $T \wedge F$ 意味着什么， $F \rightarrow T$ 意味着什么。
至此，我们的语义系统就定义好了。
3.3 语义蕴含(semantic entailment) 及其有效性
看下面这种形式： $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 其中的 $\models$ 即表示蕴含关系，从上面语法和语义的讨论中，你可能已经明白了，这只是一种语法层面的定义， 那么蕴含的语义是什么呢？翻译为人话就是：当我说蕴含的时候，我是在说什么。 蕴含就是在说，如果 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 的取值都为T, 那么 $\varphi$ 的取值一定为 $T$.
例如： $p \wedge q ,\; q,\; r \models p$, 当 $p \wedge q$ 为$T$, $q$为$T$，$r$为$T$时， $P$一定为$T$. 所以 $p \wedge q ,\; q, \; r$ 蕴含 $p$.
那么，什么是蕴含的有效性呢？
例如我问： $p \vee q,\; q,\; r\models p$ 是有效的么？ 我其实是在问， $p \vee q$ 为 T, q为T, r为T时， p一定为T么？ 如果p一定为T, 那么 $p \vee q,\; q,\; r\models p$ 是有效的。否则，$p \vee q,\; q,\; r\models p$ 是无效的。
所以，如果我说 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 蕴含 $\varphi$, 意思等同于： $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是有效的。
至此，语义部分就介绍到这里。下面，开始介绍可靠性与完备性。
4 可靠性与完备性(Soundness and Completeness)
经过了前面冗长的关于语法和语义的介绍，终于可以开始介绍可靠性与完备性了。在此之前，请保证你可以正确区分 $\vdash$ 和 $\models$ ,知道推理的有效性和语义蕴含的有效性意味着什么。
在完成命题逻辑系统的定义后，我们想知道这个系统的一切性质，其中最重要的性质就是可靠性与完备性。这一节的两个定理告诉我们，命题逻辑系统满足可靠性和完备性。
4.1 可靠性(Soundness)
4.1.1 可靠性是指什么？
可靠性定理：令 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 和 $\varphi$ 为命题逻辑中的公式，如果 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\vdash$ $\varphi$ 是有效的， 那么 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是有效的。
这个定理是在说，我们为逻辑系统定义好语法和语义后，如果在语法上，我们可以利用推导规则，将$\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 转化为 $\varphi$，
那么在语义上，如果$\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 都为T, 那么$\varphi$一定为T.
4.1.2 为什么要引入可靠性的概念？
首先，我们需要理解，可靠性是逻辑系统满足的一个性质。如果有一天，我们构造了另一个逻辑系统，自己定义了 语法，定义了语义，那么，我们可能需要问一下自己：我定义的这个逻辑系统满足可靠性么？
上面的靠性定理是指在命题逻辑中，我们定义了语法：自然推导规则，推导及其有效性；我们定义了语义：真值表，语义蕴含及其有效性。在由这些定义构成的一个命题逻辑系统中，像可靠性定理描述的那样的性质是满足的。一旦我们 证明了一个逻辑系统满足了可靠性，我们就可以利用这个好的性质来做一些事。
4.1.3 可靠性有什么用？
现在我们明白了，之前定义的命题逻辑系统满足可靠性。现在，我们就可以利用这一点来做一点事了。
我们可以利用逻辑系统的可靠性来确定：有一些证明是不存在的。
例如：在命题逻辑系统中给定前提 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$, 能否证明 $\varphi$ ？这其实是在问： $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\vdash$ $\varphi$ 是否是有效的。
如果这个前提和结论非常复杂，那么你很可能证明不出来，因为证明通常是需要一点灵感的，而灵感通常是难得的。 但是，你证明不出来不能说明这个证明不存在。那我们应该怎么做呢？ 有了可靠性定理，我们就可以将问题转化为： $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\models$ $\varphi$ 是否是有效的。
而这个问题，我们完全可以用真值表来确定。 假如我们用真假表确定了， $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\models$ $\varphi$ 是无效的, 那么，我们完全可以断言： $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\vdash$ $\varphi$ 是无效的。即证明不存在。 因为根据可靠性定理，如果 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\vdash$ $\varphi$ 是有效的， 那么 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是有效的， 与我们根据真值表得出的结论相矛盾。
5 完备性(Completeness)
5.1 完备性是指什么？
完备性定理：令 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 和 $\varphi$ 为命题逻辑中的公式，如果 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是有效的， 那么 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\vdash$ $\varphi$ 是有效的。
可以看出，这和可靠性定理的定义正好相反。这其实是在说，在一个逻辑系统中，如果从语义上看， $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是有效的， 那么我们一定可以为$\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ $\vdash$ $\varphi$ 找到一个证明。
在命题逻辑中，完备性定理也是成立的。具体的证明过程参考1
5.2 完备性有什么用？
与可靠性一样，完备性也是逻辑系统的性质。那么完备性有什么用呢？在一个逻辑系统中，如果我们知道一些前提是 真的，即 $\phi_1$, $\phi_2$, …,$\phi_n$ 都为真，那么，我们想知道在这样的条件下，结论 $\varphi$ 也一定是真吗？即我们想知道 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是否是有效的。那么我们可能想找一个由$\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 到 $\varphi$ 的证明，即利用推导规则将 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n$ 转化为 $\phi$. 这时候，完备性就会告诉我们， 如果 $\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是有效的，那么，这样 的证明一定存在。假如你的逻辑系统不满足完备性，那么即使$\phi_1 ,\; \phi_2 ,\; ...,\; \phi_n \models \varphi$ 是有效的，但是它的证明也可能 不存在，那你的努力可能就是徒劳的。
6 结束
关于可靠性与完备性的讨论到这里就结束了，这只是我学习参考资料1 第1章的一些体会，这本书相当不错，特别推荐给诸位。如果有什么问题，欢迎随时讨论。
7 参考
- Michael Huth, Mark Ryan. 面向计算科学的数理逻辑——系统建模与推理. 2005
本文由 Webster Zhang 创作，采用 知识共享署名4.0 国际许可协议进行许可