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