Knowledge 3命题逻辑形式推演（resolution归结原理- -- 1条规则）_数学逻辑中的resolution

目录

一、写在前面

二、resolution归结原理

2.1 什么是resolution归结原理

2.2 怎么将一个任何一个式子改写成CNF合取范式的形式

2.3  利用归结原理和反证法证明       KB |=a

2.4 归结原理的使用举个例子

三、resolution归结原理的特性

3.1 可靠性sound

3.2 完备性complete

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

---

一、写在前面

我们之前讲过了命题逻辑中，一套形式推演系统由11条规则构成，之前我们讲了11条规则的情况，用的时候需要依赖我们的选择，我们希望电脑可以自动实现上面的功能，我们介绍一个非常常用的方法resolution归结原理。这个归结原理只有一条规则，非常重要的知识。我们会证明resolution的完备性和可靠性。

基本知识回顾：

1. ¬     取反（作用于一个原子命题）    negation
2.  ∩   ，^   ，and 两个真为真，其余为假   conjunction   合取
3.  ∪ ，V ，or 两个假得假，其余为真    disjunction    析取
4.（->） 假假、假真、真真为真 ，真假为假   implication
5.（<=>） 类似同或，相同为真，不同为假    biconditional

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

 

二、resolution归结原理

2.1 什么是resolution归结原理

首先，我们要将想要证明的东西转化为CNF（一堆disjunction的conjunction）（一堆析取【∪，V】的合取【∩，^】），我们把每一堆析取叫做子句clauses，这样的形态我们叫它合取范式。而且我们要知道的是，任意给一个sentence，都可以转为语义等价的合取范式CNF。

当我们已经有了一个CNF合取范式的时候，我们看上面的图，横线上面的是两个clause，我们已经给圈出来了。然后其中有两个

literal （Liter要么是原子命题，要么是原子命题的否。）是相反的（左面一个，右面一个），比如左面的Li和右面的Mi（Li = ¬ Mi，Mi = ¬ Li ），可以得到一个新的clause子句，就是横线下面的那个子句（将Li和Mi都删掉了，然后将其他的用V连接，取了并集）。左边少了Li，右边少了一个Mi，这个过程我们称为resolution。

怎么证明这个事情呢？可以直接使用真值表证明。

2.2 怎么将一个任何一个式子改写成CNF合取范式的形式

在我们讨论resolution各个特性之前， 怎么将一个任何一个式子改写成CNF合取范式的形式。结合上一次11条规则的时候，重回woopers例子来看。（先把双箭头和单箭头拿到，neg进入括号，最后只有and or的这种式子 ）

2.3  利用归结原理和反证法证明       KB |=a

我们有了CNF之后，我们想要证明KB |=a。我们利用特性

我们想要证明结论，可以先假设结论是错的，导致矛盾，没有任何一个世界，可以satisfiable这样一个sentence（KB ^ ¬ a）。

下面是一个证明过程；

（KB ^ ¬ a）中有很多clause子句，我们做的事情很简单，就是将所有的clause任意两两组合，使用resolution进行归结。有些clause可以归结，有些不能归结，需要有相反的两个literal。能进行归结的就进行归结得到的结果放到new集合中。直到clause无法变多，无法产生新的clause，如果都还没有出现空子句，就可以说原命题为假，否则就可以说原命题为真。

空子句（empty clause）是什么东西呢？比如 A 和  ¬A进行归结，就会都拿掉，产生一个空子句。这个是什么含义呢？产生空子句说明归结的两个sentence是没有交集的两个部分。A  ^  ¬A是unsat的，放到这个问题上可以说，KB ^  ¬a  是untat的，这个也就证明的我们的结论，进而得到  KB | = a。出现了空子句，我们就直接可以说原命题为真。

 

2.4 归结原理的使用举个例子

把KB展开为CNF（上面举得例子），我们在知道¬ B1,1的时候，在这个CNF式子后面添加（^ and）一个¬ B1,1  。

我们想要得到 a = ¬P1,2  这个结论，我们看能不能得到1 ，2 没有P这个结论。先假设 12有P，添加进去直到产生空子句，我们的证明结束。我们可以得到KB |=a；（1，2 没有P这个事情是真的）

三、resolution归结原理的特性

我们已经讲了resolition的原理，接下来我们想要证明其可靠性sound和完备性conplete

3.1 可靠性sound

sound的证明方法很简单，只要check一次resolution的过程是正确的（利用真值表），实际上就是去证明这个子句合取第二个子句可以蕴含下面那个子句。用到我们之前学的证明蕴含有两个可以等价的形式，要么证明M（KB）含于M（a）,或者证明KB^否a永假。

3.2 完备性complete

证明只要KB |= a，我们一定可以使用resolution得到这个结果（没有少推一些东西）。我们在做这件事情之前先定义一个东西，Resolution closure，简称RC(s)，就是通过resolution两两得到的新子句也加到KB中得到的新的KB，直到不再产生新子句的时候，这个时候的clause set集合，我们称为RC(S)。

通过以前知识，我们知道

我们想要证明resolution是complete的，我们把（KB ^ ¬ a） 叫做 S ；我们就要证明S是Unsatisfiable的，并且我们有下面一个性质，当S是unsat的时候，RC(S)包含空子句。

我们要证明这件事情，要用到了反证法，转化为了证明当RC(S)不包含空子句时候，则S是satisfiable的。

我们只要证明了这个就可以说明resolution是complete完备的。我要证明一个S是satisfiable的，最简单的方法是给你一个model，比如证明A ^B 是satisfiable的，我们给一个例子A true，B true，A^B为true，证明A^B 是satisfiable的。我们要找到一个model使得S为true即可证明。

最终证明：

我们给一个初始model（真值指派规则），一个model中有k个literal，如果一个clause有一个 neg pi 并且其他的literal已经是false了，我们就让这个Pi设置为false，其他情况下设置为true。我们宣称这种真值指派会使得整个sentence为真，是sat的。

接下来需要证明这样的真值指派会使得整个为真吗?
再次反证：如果我这样的指派没有model使得整个为真（and连接），只有一种可能，至少其中一个clause为false

我们假设其中一个clause是false，我们研究这个clause在成为false的前一步，只有两种可能  false V false V neg Pi   或者  false  V  false V  Pi（or连接）。
根据我们的真值指派，如果是前者形式，我们会把Pi设置为false，neg Pi为true，后者会设置为true（这个是我们的真值指派规则）。这样才会使得整个clause为true，原假设（其中有一个clause是false）是不可能成立的，回推就会得到整个S是sat的，就可以证明resolution是完备的。

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

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

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

家庭作业：设计一个  利用启发式函数 A*搜索设计归结原理