经典逻辑推理优秀文档

2022/11/22郑州大学振动工程研究所第四章经典逻辑推理为了使计算机具有智能仅仅拥有知识是不够的，还需要让它拥有思维能力，即能够运用知识进行推理、求解问题。因此推理是人工智能的一个重要研究课题。接下来，我们将介绍关于推理的一般概念，然后介绍几种推理方法。2022/11/22郑州大学振动工程研究所

推理、推理方式及其分类运用已经掌握的知识，找出其中蕴涵的事实，或归纳出新事实的过程称为推理。推理有以下不同的方式：1.演绎推理、归纳推理、默认推理2.确定性推理、不确定性推理3.单调推理、非单调推理4.启发式推理、非启发式推理5.基于知识的推理、统计推理、直觉推理2022/11/22郑州大学振动工程研究所Ⅰ.演绎推理、归结推理、默认推理（从新判断推出的途径来划分）演绎推理——从全称判断推导出特称判断或单称判断的过程，即由一般性知识推出适合于某一具体情况的结论。这是一种从一般到个别的推理。演绎推理有多种形式，经常用的是三段论式，它包括：

1)大前提，这是已知的一般性知识或假设；

2)小前提，这是关于所研究的具体情况或个别事实的判断；

3)结论，这是由大前提推出的适合于小前提所示情况的新判断。例如：1)足球运动员的身体都是强壮的；

2)高波是一名足球运动员；

3)所以，高波的身体是强壮的。2022/11/22郑州大学振动工程研究所归纳推理——归纳推理是从足够多的事例中归纳出一般性纳论的推理过程，是一种从个别到一般的推理。归纳推理又分为完全归纳和不完全归纳两种。完全归纳：指在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都有某种属性，从而推出这种事物是否具有这个属性。不完全归结：指只考察了相应事物的部分对象，就得出了结论。2022/11/22郑州大学振动工程研究所默认推理——又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。在默认推理过程中，如果到某一时刻发现原先所作的默认不正确，则就要撤销所作默认，以及由此默认推出的所有结论，重新按新情况进行推理。2、ACP规则解，问题转化成证子句集合S={PQ，PQ，PQ，PQ}的不可满足问题，用线形消解的图解表示如下：子句集中各子句之间是合取关系。*设S是子句集，则按下述方法构造的域H称为是海伯伦域：启发式推理、非启发式推理郑州大学振动工程研究所在与/或形正向演绎推理中，通常要求F规则具有如下的形式：若两条规则均按匹配度匹配成功，则匹配度大的那条规则优先启用。郑州大学振动工程研究所郑州大学振动工程研究所但如果是公式集F的一个合一，若对任一个合一都存在一个代换使得：=·，则称是一个最一般合一。逆向推理是以某个假设目标作为出发点的一种推理,又称为目标驱动推理、逆向链推理及后件推理等。求证小王喜欢ds这门课程。C2=QS如果一个子句中同时包含互补文字对，则称该子句为重言式，显然重言式不会影响子句集合S的不可满足性，所以，可以从子句集合中删除。其中I(x)R(x)是目标公式的否定得到的子句。2022/11/22郑州大学振动工程研究所Ⅱ.确定性推理，不确定性推理（按推理时所用知识的确定性来划分）

确定性推理——

指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或为“真”，或为“假”，没有第三种情况出现。下面将要讨论的经典逻辑推理就属于这一类。不确定性推理——指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于“真”和“假”之间，命题的外延模糊不清。2022/11/22郑州大学振动工程研究所Ⅲ.单调推理、非单调推理（按推理过程中推出的结论是否单调的增加来划分）单调推理——指在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不会出现反复的情况，即不会由于新知识的加入而否定了前面推出的结论，使推理又退回到前面的一步。非单调推理——指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。2022/11/22郑州大学振动工程研究所Ⅳ.启发式推理、非启发式推理（按推理中是否运用与问题有关的启发性知识分）启发式推理——推理中运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门，对解的特性及规律的估计等实践经验和知识，以加快推理过程、提高搜索效率、提高推理的准确性，这种推理称为启发式推理。非启发式推理——比如穷举式推理等。2022/11/22郑州大学振动工程研究所Ⅴ.基于知识的推理、统计推理、直觉推理（从方法论的角度划分）基于知识的推理——根据已掌握的事实，通过运用知识进行的推理。统计推理——根据对某事物的数据统计进行的推理(相当于归纳推理)。直觉推理——又称常识性推理，是根据常识进行的推理。2022/11/22郑州大学振动工程研究所推理的控制策略：推理的控制策略主要包括推理方向的控制策略、搜索的控制策略、冲突消解策略、求解策略及限制策略等。2022/11/22郑州大学振动工程研究所推理方向的控制策略则包括；正向推理、逆向推理、混合推理、双向推理。正向推理：正向推理是以已知事实作为出发点的一种推理，又称数据驱动推理、前向链推理及前件推理等。根据已知的实事，在知识库中查找当前可用的知识，构成可适用的知识集KS，再安照冲突消解策略从KS中选出一条知识进行推理，并将推出的新实事加入到数据库中作为下一步推理的实事……再查找，再推理，直到求得了所要求的解或者知识库中没有可用的知识为止。2022/11/22郑州大学振动工程研究所正向推理过程算法描述：开始把初始已知事实送入DBDB中包含问题的解？KB中有可适用知识？KS空？把KB中所有可适用知识都选出来送入KS推出的是新事实？按冲突消解策略从KS中选出一条知识进行推理将该新事实加入到DB中成功，退出把用户提供的新事实加入DB中用户可补充新事实？失败，退出YYYYYNNNNN2022/11/22郑州大学振动工程研究所逆向推理：逆向推理是以某个假设目标作为出发点的一种推理,又称为目标驱动推理、逆向链推理及后件推理等。逆向推理的基本思想：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设成立；若无论如何都找不到所需证据，说明原假设不成立，此时需要另作新的假设，进行一轮新的推理。2022/11/22郑州大学振动工程研究所逆向推理过程算法描述开始提出假设该假设在数据库DB中？该假设是证据？在知识库中找出所有能导出该假设的知识，形成适用知识集KS从KS中选出一条知识，并将该知识的一个运用条件作为一个新的假设目标。该假设成立询问用户有此事实？该假设成立，并将此事实存入数据库还有假设？退出YYYYNNNN2022/11/22郑州大学振动工程研究所逆向推理：逆向推理的主要优点：不必使用与目标无关的知识，目的性强，同时还有利于向用户提供解释。主要缺点：初始目标的选择有盲目性，若不符合实际，就要多次提出假设，影响到系统效率。2022/11/22郑州大学振动工程研究所混合推理正、逆向推理存在的缺陷正向推理——具有盲目、效率低等缺点；逆向推理——若提出的假设目标不符合事实，也会降低系统效率。为解决这些问题，可把正向推理与逆向推理结合起来，取长补短；象这样既有正向又有逆向的推理称为混合推理。混合推理适应于下列情况：1：已知的实事不够充分2：单纯由正向推理得出的结论可信度不高3：希望得到更多的结论2022/11/22郑州大学振动工程研究所混合推理的两种情况先正向再逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度。先逆向再正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。2022/11/22郑州大学振动工程研究所双向推理双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理方式。基本思想：一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所需要的证据，这时推理就可结束，逆向推理时所做的假设就是推理的最终结论。2022/11/22郑州大学振动工程研究所求解策略求解策略是指，推理是只求一个解，还是求所有解以及最优解等。限制策略所谓限制策略是指为了防止无穷的推理过程，以及由于推理过长增加时间及空间上的复杂度，可在控制策略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。2022/11/22郑州大学振动工程研究所模式匹配所谓模式匹配是指对两个知识模式（如谓词公式、两个框架片段或两个语义网络片段等）的比较与耦合，即检查这两个知识模式是否完全一致或近似一致。若完全一致或不完全一致但其相似程度在指定的范围内,就称它们是匹配的，否则为不可匹配。

2022/11/22郑州大学振动工程研究所模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才能从知识库中选出当前适用的知识，才能进行推理。模式匹配可以有确定性匹配和不确定性匹配2种。确定性匹配是指两个模式完全一样，或者通过代换后变得完全一致。所谓不确定性匹配是指两个知识模式不完全一样，但从总体上看它们的相似程度又落在规定的限度内。无论是确定性匹配还是不确定性匹配都需要进行变量的代换。2022/11/22郑州大学振动工程研究所代换：代换是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，t1，t2，…,tn是项，x1.，x2,…,xn是互不相同的变元；ti/xi表示用项ti代换变量xi，不允许ti和xi相同，也不允许xi循环的出现在另一个tj中。例如{a/x,f(b)/y,w/z}就是一个代换2022/11/22郑州大学振动工程研究所但是{g(y)/x,f(x)/y}则不是一个代换，因为代换的目的是使某些变元被另外的变元、常量、或函数表达式取代，使之不再在公式中出现，而{g(y)/x,f(x)/y}在x与y之间出现了循环代换的情况，它既没有消去x,也没有消去y。如果把它改为{g(a)/x,f(x)/y}就可以了，它将把公式中的x代换成g(a),y代换成f(g(a)),从而消去了变量x和y。2022/11/22郑州大学振动工程研究所复合代换设有两个代换和，其中={t1/x1,t2/x2,…,tn/xn}，={u1/y1,u2/y2,…,um/ym}则和的复合也是一个代换，它的定义如下：先做代换：{t1

/x1,t2

/x2,…,tn

/xn，u1/y1,u2/y2,…,um/ym}（注：ti是用代换来替换ti中的项）若ti·=xi时，从上述集合中删除

ti

/xi

若yi

{x1，x2,…,xn}

从上述集合中删除ui/yi

删除之后剩下的元素构成的集合称作与的乘积，记为·。2022/11/22郑州大学振动工程研究所例如设有如下代换：={f(y)/x,z/y}，={a/x,b/y,y/z}现在来求·

先做代换：{f(y)

·/x,z·/y,a/x,b/y,y/z}={f(b)/x,y/y,a/x,b/y,y/z}删除y/y，再删除a/x,b/y,得到·

={f(b)/x,y/z}满足条件1满足条件2对于Z，因为它不属于xi，所以y/z就不能删除2022/11/22郑州大学振动工程研究所合一：寻找项对变量的代换以使两表达式一致，就叫合一设有公式集F={F1，F2，…,Fn},若存在一个代换使得F1=F2=…=Fn，则称为公式集F的一个合一代换，且称F1，F2，…,Fn是可合一的。例如：对于公式集F={P(x,y，f(y)),P(a,g(x),z)}，则={a/x，g(a)/y，f(g(a))/z}是公式F的一个合一。(原因：将的代换关系带入公式集，可知公式集中的2个公式是等价的。)2022/11/22郑州大学振动工程研究所一个公式的合一一般不是唯一的。但如果是公式集F的一个合一，若对任一个合一都存在一个代换使得：=·

，则称是一个最一般合一。最一般合一是唯一的。若用最一般合一去代换那些可合一的谓词公式，可使它们变成完全一致的公式。由此可知，为了使两个知识模式匹配，可用其最一般合一对它们进行代换。为了求最一般合一要用到一个差异集（也叫分歧集）的概念。2022/11/22郑州大学振动工程研究所设有如下两个谓词公式F1：P(x,y,z)，F2:P(x,f(a),h(b))分别从F1与F2的第一个符号开始，逐个向右比较，此时发现F1中的y与F2中的f(a)不同,它们构成了一个差异集：D1={y,f(a)}当继续向右比较时，又发现F1中与F2中的h(b)不同，于是又得到一个差异集：D2={z,h(b)}。2022/11/22郑州大学振动工程研究所下面给出求最一般合一的算法：（1）令k=0,Fk=F,k=。这里，F是欲求其最一般合一的公式集，是空代换,它表示不做代换。（2）若Fk只含一个表达式，则算法停，k就是所求最一般合一。（3）找出Fk的差异集Dk。（4）若Dk中存在元素xk和tk,其中xk是变元，tk是项,且xk不在tk中出现，则置：k+1=k·{tk/

xk}Fk+1=Fk{tk/xk}k=k+1转（2）（5）算法停，F的最一般合一不存在。2022/11/22郑州大学振动工程研究所冲突消解策略在推理的过程中，系统不断的用已知的事实与知识库中的知识进行匹配，此时可能发生如下三种情况：（1）已知事实不能与知识库中的任何知识匹配成功。（2）已知事实恰好与知识库中的一条知识匹配成功。（3）已知事实可与知识库中的多条知识匹配成功。第一种情况中,使得推理无法进行下去,第二种情况恰好匹配,第三种情况则出现冲突，需要按一定的策略解决冲突。2022/11/22郑州大学振动工程研究所目前解决冲突的策略有多种，其基本思想都是对知识进行排序，常用的有以下几中：1、按针对性排序设有如下两条产生式规则：r1:IFA1andA2and…AnTHENH1r2:IFB1andB2and…BmTHENH2如果存在最一般合一，使得r1中每一个Ai都可变成相应的Bi，即r2中除了包含的r1全部条件A1,A2,…,An外，还包含其它条件，则称r2比r1有更大的针对性，r1比r2有更大的通用性。2022/11/22郑州大学振动工程研究所上面的策略是优先选用针对性较强的产生式规则。(即应选用r2)因为它要求的条件较多，其结论一般更接近目标，一旦得到满足，可缩短推理过程。2022/11/22郑州大学振动工程研究所2、按已知事实的新鲜性排序在产生式系统推理过程中，每应用一条产生式规则就会得到一个或多个结论，数据库就会增加新的事实。把数据库后生成的事实称为新鲜的事实，即后生成的事实比先生成的事实具有较大的新鲜性。设规则r1可与事实组A匹配成功，规则r2可与事实组B匹配成功，则A与B中哪一组新鲜与它匹配的产生式规则就先被应用。2022/11/22郑州大学振动工程研究所3、按匹配度排序在不确定性匹配中，为了确定两个知识模式是否可以匹配，需要计算这两个模式的相似程度，当其相似程度达到某个预定的值时，就认为它们是可匹配的。若两条规则均按匹配度匹配成功，则匹配度大的那条规则优先启用。2022/11/22郑州大学振动工程研究所4、根据领域问题的特点排序某些领域问题可事先知道它的某些特性，可根据这些特性把知识排成固定的顺序，按照领域知识特性决定匹配顺序。2022/11/22郑州大学振动工程研究所5、按上下文限制排序把产生式规则按它们所描述的上下文分成若干组，在不同的条件下，只能从相应的组中选取有关的产生式规则。这样可以减少冲突的发生6、按冗余限制排序若哪一条产生式规则被应用后产生冗余知识，则就降低它被应用的优先级。7、按条件个数排序如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用。2022/11/22郑州大学振动工程研究所从一组已知的事实出发，直接运用经典逻辑推理规则推出结论的过程称为自然演绎推理。其中，基本的推理规则是P规则、T规则、假言推理、拒取式推理等。假言推理的一般形式是：P，PQQ拒取式的一般形式是PQ，QP以下是自然演绎推理的例子：2022/11/22郑州大学振动工程研究所4.2自然演绎推理（续）例1：已知A，B，AC，BCD，DQ求证Q1、AP规则2、AC

P规则3、CT规则1和24、BP规则5、BCT规则3和46、BCDP规则7、DT规则5和68、DQP规则9、QT规则7和8问题得证P规则：在推理的任何步骤上都可引入前题T规则：在推理时，如果前面步骤中有一个或多个永真蕴涵公式S，则可把S引入推理过程。2022/11/22郑州大学振动工程研究所4.2自然演绎推理（续）例2设已知如下事实；（1）凡是容易的课程小王（Wang)都喜欢。（2）C班的课程都是容易的。（3）ds是C班的一门课程求证小王喜欢ds这门课程。证明：首先定义谓词如下：EASY(x):x是容易的LIKE(x,y):x喜欢yC(x):x是C班的一门课程于是问题可以表示成：2022/11/22郑州大学振动工程研究所4.2自然演绎推理（续）已知：x(EASY(x)LIKE(Wang,x))x(C(x)EASY(x))C(ds)求证：LIKE(Wang,ds)证明：1、x(C(x)EASY(x))P规则2、C(ds)EASY(ds)T规则13、x(EASY(x)LIKE(Wang,x))P规则4、EASY(ds)LIKE(Wang,ds)T规则和35、LIKE(Wang,ds)得证2022/11/22郑州大学振动工程研究所

4.2自然演绎推理（续）自然演绎推理的优点是表达定理证明过程自然，容易理解，拥有丰富的推理规则，推理过程灵活，便于在推理过程中嵌入领域启发知识。缺点是容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增，这对于一个大型推理问题是十分不利的，甚至是不可能实现的。2022/11/22郑州大学振动工程研究所以下还有的推理方法：归结演绎推理与/或形演绎推理自己看书2022/11/22郑州大学振动工程研究所定理证明是人工智能的一个重要研究领域，这不仅仅是因为许多数学问题要通过定理证明得以解决，很多非数学问题（如医疗诊断、机器人规划及难题求解等）也都归结为一个定理证明问题。定理证明的实质是对前提P和结论Q证明PQ的永真性。但是证明一个谓词公式的永真性不像证明一个命题公式的永真性那麽简单，（它牵涉到谓词变量、客体变量及函数符号）在某些情况下甚至是行不通的。在这种情况下，人们提出了用反证法来解决问题的思路。在这方面，海伯伦和鲁宾逊都作出了杰出的贡献。两人的研究都是以子句集为背景展开的。接下来，我们介绍这些概念。2022/11/22郑州大学振动工程研究所4.3归结演绎推理（续）子句：在谓词逻辑中，称原子谓词公式及其否定为文字；任何文字的析取式为子句。例如，P（x)Q(x),P(x,f(x))Q(x,g(x))都是子句。而P（x)、Q(x,g(x))、P(x,f(x))等都是文字。并把不包含任何文字的子句称为空子句。由于空子句不包含任何文字，它不能被任何解释所满足，所以空子句是永假的，不可满足的。由子句构成的集合称为子句集。在谓词逻辑中任何一个谓词公式均可通过等价变换化为相应的子句集。2022/11/22郑州大学振动工程研究所4.3归结演绎推理（续）化子句集的步骤如下：1、利用等价公式消去公式中的逻辑连接词“”和“”：PQPQPQ（PQ）（PQ）2、利用下列公式将否定符号“”深入到单个变元前PP（PQ）PQ（PQ）PQ(x)P(x)P(x)P(x)P2022/11/22郑州大学振动工程研究所3、重新命名变元名，使不同量词约束的变元有不同的名字4、消去存在量词。分两种情况处理：一种情况是存在量词不出现在全称量词的辖域内，此时只要用一个新的个体常量替换受该存在量词约束的变元就可消去存在量词；另一种情况是存在量词位于一个或多个全称量词的辖域内，例如（x1)（x2)…(xn)(y)P(x1,x2,…,xn,y)此时需要用Skolem函数f(x1,x2,…,xn)替换受该存在量词约束的变元，然后才能消去存在量词。5、把全称量词全部移到公式的左边。6、利用等价关系P（QR）=（PQ）（PR）把公式化为Skolem标准型。2022/11/22郑州大学振动工程研究所4.3归结演绎推理（续）Skolem标准型的一般形式是：（x1)（x2)…(xn)M其中，M是子句的合取式，称为Skolem标准型的母式。7、消去全称量词8、对变元更名，使不同子句中的变元不同名。9、消去合取连接词，变为子句集。子句集中各子句之间是合取关系。谓词公式是不可满足的，则其子句集合是不可满足的，反之亦然。2022/11/22郑州大学振动工程研究所

4.3归结演绎推理（续）如何证明一个子句集是不可满足的呢？下面就海伯伦理论和鲁宾逊的归结原理进行讨论。一、海伯伦理论要判定一个子句集是否是不可满足的，需要对子句集中的谓词公式进行判定，而谓词公式的判定需要对个体域上的任何解释进行判定，这是很困难的。海伯伦定义了一个特殊的域称为海伯伦域，在任何域上的判定，只要在海伯伦域上进行即可。*设S是子句集，则按下述方法构造的域H称为是海伯伦域：2022/11/22郑州大学振动工程研究所4.3归结演绎推理（续）1、令H0是S中所有个体常量的集合，若S中不包含个体常量，则令H0=[a}，其中a为任意指定的一个个体常量。2、令Hi+1=Hi{S中所有n元函数f(x1,x2,…,xn)|xj(j=1,2,…,n)是Hi中的元素}，其中，i=0,1,…。下面通过例子来解释这个定义。例1求子句集S={P(x)Q(x),R(f(y))}的H域。解：因为S中没有个体常量，所以指定a作为个体常量，于是得到：H0={a},H1={a,f(a)},H2={a,f(a),f(f(a))},…,H={a,f(a),f(f(a)),…}2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）例2求子句集S=[P(a),Q(b),R(f(x))}的H域解：根据H域的定义得到：H0={a,b}H1={a,b,f(a),f(b)}┇

例3：求子句集S={P(x),Q(y)R(y)}的H域。解：由于该子句集中既无个体常量，又无函数，所以可任意指定一个常量a作为个体常量，从而得到H0=H1=…=H={a}有定理说：子句集S是不可满足的充要条件是S对H域上的一切解释都为假。并且海伯伦证明了若子句集S在任何域D上的解释能满足S，则在H域上相应的解释也能满足S。下面我们说明，S在H域上解释的定义：9、消去合取连接词，变为子句集。郑州大学振动工程研究所在不确定性匹配中，为了确定两个知识模式是否可以匹配，需要计算这两个模式的相似程度，当其相似程度达到某个预定的值时，就认为它们是可匹配的。将该知识的一个运用条件混合推理适应于下列情况：并称c12是c1和c2的归结式，c1和c2则称为c12的亲本子句。(u)(~P(x,y,f(x,y))Q(x,u))而P（x)、Q(x,g(x))、P(x,f(x))等都是文字。8、DQP规则郑州大学振动工程研究所（PQ）PQ郑州大学振动工程研究所并把不包含任何文字的子句称为空子句。2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）子句集S在H域上的一个解释满足下列条件：1、在解释I下，常量映射到自身；2、S中的任一个n元函数是HnH的映射。即，设h1,h2,…,hnH,则f(h1,h2,…,hn)H;3、S中的任一n元谓词是Hn{T，F}的映射。即谓词的真值可以指派T也可指派F。海伯伦在理论上证明了子句集不可满足性的可行性及方法，但要在计算机上实现其证明过程还是很困难的。1965年鲁宾逊提出了归结原理，使机器证明成为现实2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）*鲁宾逊归结原理归结原理也称消解原理，是鲁宾逊提出的一种证明子句不可满足性，从而实现定理证明的一种理论及方法。由谓词公式转化为子句集的过程可以看出，在子句集中子句之间的关系是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。前面，我们曾经说过空子句是不可满足的，即一个子句集中若含空子句，则它是不可满足的。归结原理的基本思想就是检查子句集中是否含空子句，若含则子句集S不可满足，或说证明一个谓词公式是永假的过程，就是归结由此公式转换成的子句集包含空子句的过程。2022/11/22郑州大学振动工程研究所

4.3归结演绎推理(续）下面我们先来说明命题逻辑中的归结原理定义P是原子谓词公式，则称P与P为互补文字。我们知道在命题逻辑中有公式：PQ,QRPR即PQ，QRPR

c1c2c12显然上述公式向我们展示的是在子句c1

中存在文字Q，在子句c2中存在Q的补文字Q，把这一对互补文字消去，剩下的文字析取起来就是子句

c1和c2的逻辑结果c12。并称c12是c1和c2的归结式，c1和c2则称为c12的亲本子句。2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）

例如：1、C1=PQRC2=QS它们的归结式c12为PRS2、C1=PC2=P它们的归结式c12为NIL即空子句。3、C1=PQC2=QRC3=P它们的归结式c123为R。其归结过程可以用下面的一个树形结构很清楚的表现出来。2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）

PQQR

PRP

R归结过程的树形表示图2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）由命题逻辑中的归结原理可以得出如下的推论：设c1与c2是子句集S中的两个子句，c12是它们的归结式,若用c12代替c1和c2后得到新子句集S1，则由S1的不可满足性可以推出S的不可满足性。这个定理告诉我们，证明子句集S的不可满足性问题，可以转化成证子句集S1的不可满足性问题，…直到从子句集Sn

中推出一个空子句来。2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）谓词逻辑中的归结原理在谓词逻辑中，由于子句中含有变元，所以不象命题逻辑中那样可以直接消去互补文字，而先要用最一般合一对变元进行代换。然后才能进行归结。前面我们已经介绍过最一般合一的概念，下面给出谓词逻辑中二元归结式的概念。*设C1与C2是两个没有公共变量的子句，L1和L2分别是C1与C2中的文字，若是L1和L2的最一般合一，则称C12=（C1-{L1}）（C2-{L2}）为C1与C2的二元归结式，L1和L2称为归结式上的文字。例子见P132页的例4.10和例4.11。2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）在谓词逻辑中二元归结式可能是下列情形之一：C1和C2的二元归结式；C1和C2的因子C22的二元归结式；C1的因子C11和C2的二元归结式；C1的因子C11和C2的因子C22的二元归结式。下面我们介绍归结反演证明子句集不可满足的过程：设有如下的定理证明问题：P1，P2，…,PnQ2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）根据定义即证：P1P2，…,PnQT（1）即证（P1P2，…,Pn）QT（2）即证（（P1P2，…,Pn）Q）F（3）即证P1P2，…,Pn

QF（4）我们的工作现在是反向进行，即从证（4）（3）（2）（1）问题得证。设F为已知前提P1P2

，…,Pn的公式集，Q为目标公式，归结反演的过程：是把{F，Q}，化为子句集S，对S中的子句进行归结，并把每次归结得到的归结式并入S中，若出现空子句，则停止归结，即证明Q为真。2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）下面我们用例子来说明这个过程见P134从上面的例子可以看出归结过程关键的是从子句集中找出可进行归结的一对子句。机器上用的是水平浸透法，这一过程可能产生大量无用子句，造成时间和空间的浪费。因此，如何提高消解效率就变成一个重要的研究课题。下面提出的都是一些有效的方法：1、删除策略从水平浸透法的本质可以看出，提高消解效率的要害是使子句集合中子句的数量越少越好，子句中文字的数量越少越好。删除策略正是从这一点考虑提出的。几种删除方法如下：2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）（1）纯文字删除法如果某文字L在子句集中不存在可与之互补的文字L，则称该文字是为纯文字。显然在归结时纯文字不可能消去，因此，包含它的子句进行归结时不可能得到空子句，即这样的子句对归结是无意义的，所以，这样的子句从子句集中删除。（请给出纯文字删除的算法实现）（2）重言式删除法如果一个子句中同时包含互补文字对，则称该子句为重言式，显然重言式不会影响子句集合S的不可满足性，所以，可以从子句集合中删除。（给出检查一个公式是否是重言式的算法实现）（3）包孕删除法（被归类的子句可以删除）设有子句C1和C2，如果存在代换，使得C1C2，则称C1包孕于C2或说C2包孕C1，包的子句可以删除，即2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）子句C2可以删除。（想一想它的原理是什麽？P（PQ）=P）2、支持集策略每次归结时，亲本子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔。例如有子句集合S={I(x)R(x),I(a),R(y)L(y),L(a)}其中I(x)R(x)是目标公式的否定得到的子句。用支持集归结的过程是：S:（1）I(x)R(x)(2)I(a)(3)R(y)L(y)(4)L(a)S1(5)R(a)(1)与（2）归结正向推理、逆向推理、混合推理、双向推理。主要缺点：初始目标的选择有盲目性，若不符合实际，就要多次提出假设，影响到系统效率。（注：ti是用代换来替换ti中的项）2、C(ds)EASY(ds)T规则1郑州大学振动工程研究所而P（x)、Q(x,g(x))、P(x,f(x))等都是文字。郑州大学振动工程研究所另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所需要的证据，这时推理就可结束，逆向推理时所做的假设就是推理的最终结论。C2=QR用支持集归结的过程是：1、在解释I下，常量映射到自身；若用最一般合一去代换那些可合一的谓词公式，可使它们变成完全一致的公式。郑州大学振动工程研究所3、x(EASY(x)LIKE(Wang,x))P规则即谓词的真值可以指派T也可指派F。*设S是子句集，则按下述方法构造的域H称为是海伯伦域：*设S是子句集，则按下述方法构造的域H称为是海伯伦域：2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）(6)I(x)L(x)S2(1)与（3）归结

S2:

(7)L(a)(2)与（6）归结(8)L(a)(3)与（5）归结(9)I(a)(4)与（6）归结

S3:(10)NIL(2)与（9）归结上述归结过程可以用P141页的图4-10来描述。3、线性输入策略线性归结是这样一种归结，首先从子句集中选取一个称为顶子句的子句C0

开始做归结，其次是归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而BiSCk(k<i)(已出现过的归结式）。这里关键的问题是顶子句的选择，一般选择结论的否定作为顶子句。2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）例如：证明PQ，PQ，PQPQ解，问题转化成证子句集合S={PQ，PQ，PQ，PQ}的不可满足问题，用线形消解的图解表示如下：2022/11/22郑州大学振动工程研究所4.3归结演绎推理(续）4、单文字子句策略如果一个子句只包含一个文字，则称它为单文字子句。单文字子句策略要求参加归结的两个子句中必须至少有一个是单文字子句。例子见P142页的例4.20.但单文字策略是不完备的，即当子句集合中不存在单文字子句时，不能使用单文字子句策略。5、祖先过滤形策略该策略与线性