一、写在前面

我们之前讲过了命题逻辑中，一套形式推演系统由11条规则构成，这次我们要讲另外一个形式推演系统，这个形式推演系统只有一条规则，我们会形式化证明其可靠性和完备性。这个系统我们称为Resolution归结原理。

二、归结原理

假设我们有一个KB，在KB中有很多sentence，构成了一个集合，这个集合中，sentence是由合取连接而成，我

我们可以把这个KB变成一个合取范式。

合取范式：是两堆的con合取，这两堆中间是liter文字的disjunctions析取。Liter要么是原子命题，要么是原子命题的否。

任何的KB，都可以转为语义等价的合取范式。

我们看到上面那图中，中间有个横线，线上是一个合取范式，逗号表示合取，有两堆，这个规则是，上面有两堆东西，归结完之后得到下面这一堆（推出来的），归结得到的新的sentence可以放到KB中去。归结一次我们成为一次消解，一次resolution。这个归结在命题逻辑中是sound可靠的和complete完备的。

一条sentence怎么转换成合取范式的形式呢？我们可以用equivalent逻辑等价(三根线，语义上是等价的)这个东西进行证明。

三、归结算法

我们知道了什么是归结原理，那么我们怎么做归结呢？我们往往希望，有一个kB，有一个a，希望证明，KB entail a，我们在证明这个的时候，只能用等价证明。归结的时候，并不是直接用KB推出a，我们用KB和a的否一起放进来，构成一个新的KB，然后在新的KB中，用归结原理，如果能够推出一个sentence，空集，就可以证明了可靠性了。

举个例子：

命题逻辑归结原理：通常结论取个否放到里面，任意归结，有两个停止条件，第一个归结到一个空集，第二个归结不动了，可能有一个状态没法归结了，总是会停止了。如果找到一个空集，停止下来，说明这个结论成立，如果归结不动了，说明结论不成立。

一阶谓词逻辑不一定，可能会永远进行下去，命题逻辑归结肯定会停止的。

四、归结原理的可靠性和完备性

4.1 可靠性

我们需要证明归结是可靠的：可靠性证明，查真值表即可

实际上就是去证明这个子句合取第二个子句可以蕴含下面那个子句。我们就是要证明这个东西。用到我们之前学的证明蕴含有两个可以等价的形式，要么证明M（KB）含于M（a）,或者证明KB^否a永假。

真值指派：指的是如果一个KB 有K个原子命题，所有的复杂句子都是有这些原子命题运算构成的，那么他有多少种真值指派呢？什么叫一种真值指派，我们说P1到Pk,我们设置true或者是false，那么一共有多少种真值指派，答案是2^k种真值指派。如果在每一个指派都使得这个sentence为真，这个sen就是valid,如果每一个都为假，则这个sentence就是unsatisifiable.如果能够找到一个指派使得sentence成立，则这个sentence为satisfiable的。

4.2 完备性

证明方式：

这个定理的证明就是完备性证明，用到了反证法，如果说RC（s）中没有包含一个空集，这个s就是satisfiable的，什么叫satisfiable呢？（如果能够找到一个指派使得sentence成立，则这个sentence为satisfiable的）可以找到一个真值指派使得S为真。我们所有的证明，R1到RL就是我们的原子命题，我们构造了一种真值指派，我们要证明，我们在这种真值指派的情况下，S为真，证明这个集合中每一个sentence子句为真。每一个sentence内部都是析取的方式，我们只要证明内部只要有一个为真就可以了。

构造的这个算法：这个指派是按照一定的顺序来到，先指派R1，再指派R2，最后指派RL，R1的时候，首先所有的没有被指派过，相当于是说，我如果包含一个子句，这个子句就是否Ri   这个子句中其他的都是false,再析取否Ri   则把Ri 设置成false  ,如果找不到设置为true。在这个指派下面，我们使得RC（s）所有sentenc都是真的。利用反证法，我们在指派过程中，我们指派到了Ri,我们首次找到一个子句C为false,什么是C为假？这个子句中每一个部分都是假，指派Ri也为假。这个时候，我们实际上证明一个结论：如要要是使得C为false,RC(s)中两个sentence都会包含。为什么？也是利用反证法，假设只是包含一个，C可以是其中一个，由于这两个子句可以归结，不是首次，产生了矛盾。

检查完备性，主要是检查规则中是否有矛盾
如果有两条规则：1.人是动物(人→动物)、2.人不是动物(人→﹁动物)。那就矛盾了，子句集就是不可满足的，归结后就会产生空子句，就是不完备的。书里面讲到i是从1到k之间的数，逻辑运算是从左往右依次运算的，因此构造i的时候，只要保证pi之前的值是可满足的就行，不必考虑后面的，只有把Pi之前的都为false，Pi也设为false，才可能保证出现﹁Pi的情况下，子句集是可满足的，不会产生空子句

五、归结原理在计算机中的实现

归结原理在计算机中怎么实现呢？？？我们讲过搜索，实际上归结原理背后的实现就是搜索，A*算法（考试会考的）

任何一个搜索，有一个初始状态和目标状态，我从一个目的地到另个目的地，现在我说这个归结原理，什么是一个状态呢？他这个状态是说，初始状态KB和否a放到一个集合里面我们说是初始状态，归结之后，将新的sen放到集合中，这个一个新的状态，我们找到一个包含空集的集合，这个是一个目标状态，这个就是一个搜索的问题。搜索的话，就会有策略，宽度优先或者深度优先。还可以使用A*算法（可以采纳的启发式函数Heuristically ）

家庭作业：设计一个  启发式函数 A*搜索