《经典逻辑推理》PPT课件.ppt

《《经典逻辑推理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《经典逻辑推理》PPT课件.ppt（73页珍藏版）》请在金锄头文库上搜索。

1、12024/8/15郑州大学振动工程研究所第四章 经典逻辑推理为了使计算机具有智能仅仅拥有知识是不够的，还需要让它拥有思维能力，即能够运用知识进行推理、求解问题。因此推理是人工智能的一个重要研究课题。接下来，我们将介绍关于推理的一般概念，然后介绍几种推理方法。4.1基本概念4.2自然演绎推理4.3归结演绎推理4.4与/或形演绎推理22024/8/15郑州大学振动工程研究所4.1基本概念 推理、推理方式及其分类运用已经掌握的知识，找出其中蕴涵的事实，或归纳出新事实的过程称为推理。推理有以下不同的方式：1.演绎推理、归纳推理、默认推理2.确定性推理、不确定性推理3.单调推理、非单调推理4.启发式推

2、理、非启发式推理5.基于知识的推理、统计推理、直觉推理32024/8/15郑州大学振动工程研究所. 演绎推理、归结推理、默认推理（从新判断推出的途径来划分 ） 演绎推理从全称判断推导出特称判断或单称判断的过程，即由一般性知识推出适合于某一具体情况的结论。这是一种从一般到 个别的推理。演绎推理有多种形式，经常用的是三段论式，它包括： 1) 大前提，这是已知的一般性知识或假设； 2) 小前提，这是关于所研究的具体情况或个别事实的判断； 3) 结论，这是由大前提推出的适合于小前提所示情况的新判断。 例如：1) 足球运动员的身体都是强壮的； 2) 高波是一名足球运动员； 3) 所以，高波的身体是强壮的

3、。42024/8/15郑州大学振动工程研究所归纳推理归纳推理是从足够多的事例中归纳出一般性纳论的推理过程，是一种从个别到一般的推理。归纳推理又分为完全归纳和不完全归纳两种。完全归纳：指在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都有某种属性，从而推出这种事物是否具有这个属性。 不完全归结：指只考察了相应事物的部分对象，就得出了结论。52024/8/15郑州大学振动工程研究所默认推理又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。在默认推理过程中，如果到某一时刻发现原先所作的默认不正确，则就要撤销所作默认，以及由此默认推出的所有结论，重新按新情况进行推理。62

4、024/8/15郑州大学振动工程研究所. 确定性推理，不确定性推理（按推理时所用知识的确定性来划分） 确定性推理 指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或为“真”，或为“假”，没有第三种情况出现。 下面将要讨论的经典逻辑推理就属于这一类。不确定性推理指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于“真”和“假”之间，命题的外延模糊不清。72024/8/15郑州大学振动工程研究所. 单调推理、非单调推理（按推理过程中推出的结论是否单调的增加来划分） 单调推理指在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标

5、，在推理过程中不会出现反复的情况，即不会由于新知识的加入而否定了前面推出的结论，使推理又退回到前面的一步。非单调推理指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。82024/8/15郑州大学振动工程研究所. 启发式推理、非启发式推理（按推理中是否运用与问题有关的启发性知识分）启发式推理推理中运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门，对解的特性及规律的估计等实践经验和知识，以加快推理过程、提高搜索效率、提高推理的准确性，这种推理称为启发式推理。非启发式推理比如穷举式推理等。92024/8/15郑州大学振动工程研究所.

6、 基于知识的推理、统计推理、直觉推理（从方法论的角度划分）基于知识的推理根据已掌握的事实，通过运用知识进行的推理。统计推理根据对某事物的数据统计进行的推理(相当于归纳推理)。直觉推理又称常识性推理，是根据常识进行的推理。102024/8/15郑州大学振动工程研究所4.1基本概念推理的控制策略：推理的控制策略主要包括推理方向的控制策略、搜索的控制策略、冲突消解策略、求解策略及限制策略等。112024/8/15郑州大学振动工程研究所4.1基本概念推理方向的控制策略则包括；正向推理、逆向推理、混合推理、双向推理。正向推理：正向推理是以已知事实作为出发点的一种推理，又称数据驱动推理、前向链推理及前件推

7、理等。根据已知的实事，在知识库中查找当前可用的知识，构成可适用的知识集KS，再安照冲突消解策略从KS中选出一条知识进行推理，并将推出的新实事加入到数据库中作为下一步推理的实事再查找，再推理，直到求得了所要求的解或者知识库中没有可用的知识为止。122024/8/15郑州大学振动工程研究所正向推理过程算法描述：开始开始把初始已知事实送入把初始已知事实送入DBDB中包含问题的解？中包含问题的解？KB中有可适用知识？中有可适用知识？KS空？空？把把KB中所有可适用知识都选出来送入中所有可适用知识都选出来送入KS推出的是新事实？推出的是新事实？按冲突消解策略从按冲突消解策略从KS中选出一条知识进行推理中

8、选出一条知识进行推理将该新事实加入到将该新事实加入到DB中中成功，退出成功，退出把用户提供的新事实加入把用户提供的新事实加入DB中中用户用户 可补充新事实？可补充新事实？失败，退出失败，退出YYYYYNNNNN132024/8/15郑州大学振动工程研究所逆向推理：逆向推理是以某个假设目标作为出发点的一种推理,又称为目标驱动推理、逆向链推理及后件推理等。逆向推理的基本思想：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设成立；若无论如何都找不到所需证据，说明原假设不成立，此时需要另作新的假设，进行一轮新的推理。142024/8/15郑州大学振动工程研究所逆向推理

9、过程算法描述开始开始 提出假设提出假设该假设在数据库该假设在数据库DB中？中？该假设是证据？该假设是证据？在知识库中找出所有能在知识库中找出所有能导出该假设的知识，形导出该假设的知识，形成适用知识集成适用知识集KS从从KS中选出一条知识，并中选出一条知识，并将该知识的一个运用条件将该知识的一个运用条件作为一个新的假设目标。作为一个新的假设目标。该假设成立该假设成立询问用户询问用户有此事实？有此事实？该假设成立，该假设成立，并将此事实并将此事实存入数据库存入数据库还有假设？还有假设？退出退出YYYYNNNN152024/8/15郑州大学振动工程研究所逆向推理：逆向推理的主要优点：不必使用与目标无

10、关的知识，目的性强，同时还有利于向用户提供解释。主要缺点：初始目标的选择有盲目性，若不符合实际，就要多次提出假设，影响到系统效率。162024/8/15郑州大学振动工程研究所混合推理正、逆向推理存在的缺陷 正向推理具有盲目、效率低等缺点； 逆向推理若提出的假设目标不符合事实，也会降低系统效率。为解决这些问题，可把正向推理与逆向推理结合起来，取长补短；象这样既有正向又有逆向的推理称为混合推理。混合推理适应于下列情况：1：已知的实事不够充分2：单纯由正向推理得出的结论可信度不高3：希望得到更多的结论 172024/8/15郑州大学振动工程研究所混合推理的两种情况先正向再逆向 ：先进行正向推理，帮助

11、选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度。先逆向再正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。 182024/8/15郑州大学振动工程研究所双向推理双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理方式。基本思想：一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所需要的证据，这时推理就可结束，逆向推理时所做的假设就是推理的最终结论。19202

12、4/8/15郑州大学振动工程研究所求解策略求解策略是指，推理是只求一个解，还是求所有解以及最优解等。限制策略所谓限制策略是指为了防止无穷的推理过程，以及由于推理过长增加时间及空间上的复杂度，可在控制策略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。202024/8/15郑州大学振动工程研究所模式匹配所谓模式匹配是指对两个知识模式（如谓词公式、两个框架片段或两个语义网络片段等）的比较与耦合，即检查这两个知识模式是否完全一致或近似一致。若完全一致或不完全一致但其相似程度在指定的范围内,就称它们是匹配的，否则为不可匹配。4.1基本概念 212024/8/15郑州大学振动工程研究所

13、模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才能从知识库中选出当前适用的知识，才能进行推理。模式匹配可以有确定性匹配和不确定性匹配2种。确定性匹配是指两个模式完全一样，或者通过代换后变得完全一致。所谓不确定性匹配是指两个知识模式不完全一样，但从总体上看它们的相似程度又落在规定的限度内。无论是确定性匹配 还是不确定性匹配都需要进行变量的代换。222024/8/15郑州大学振动工程研究所代换：代换：代换是形如t1/x1,t2/x2,tn/xn的有限集合。其中， t1， t2， ,tn是项，x1. ，x2, xn是互不相同的变元；ti/xi表示用项ti代换变量xi，不允许ti 和xi

14、相同，也不允许xi循环的出现在另一个tj中。例如a/x,f(b)/y,w/z就是一个代换232024/8/15郑州大学振动工程研究所但是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。242024/8/15郑州大学振动工程研究所复合代换复合代换设有两个代换和，其中 = t1/x1,t2/x2,tn

15、/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 删除之后剩下的元素构成的集合称作与的乘积 ，记为 。252024/8/15郑州大学振动工程研究所例如设有如下代换：=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删除

16、y/y，再删除a/x,b/y,得到 =f(b)/x,y/z满足条件1满足条件2对于Z，因为它不属于xi，所以y/z就不能删除262024/8/15郑州大学振动工程研究所合一：合一：寻找项对变量的代换以使两表达式一致，就叫合一设有公式集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个公式是等价的。)272024/8/15郑州大学振动工程

17、研究所一个公式的合一一般不是唯一的。但如果是公式集F的一个合一，若对任一个合一都存在一个代换使得：= ，则称是一个最一般合一。最一般合一是唯一的。若用最一般合一去代换那些可合一的谓词公式，可使它们变成完全一致的公式。由此可知，为了使两个知识模式匹配，可用其最一般合一对它们进行代换。为了求最一般合一要用到一个差异集（也叫分歧集）的概念。282024/8/15郑州大学振动工程研究所设有如下两个谓词公式F1：P(x,y,z)，F2: P(x,f(a),h(b)分别从F1 与F2的第一个符号开始，逐个向右比较，此时发现F1中的y与F2中的f(a)不同,它们构成了一个差异集：D1=y,f(a)当继续向右

18、比较时，又发现F1中与F2中的h(b)不同，于是又得到一个差异集：D2=z,h(b)。292024/8/15郑州大学振动工程研究所下面给出求最一般合一的算法：（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/ xkFk+1= Fktk/ xkk = k + 1转（2）（5）算法停，F的最一般合一不存在。302024/8/15郑州大学振动工程研究所4.1基本

19、概念冲突消解策略在推理的过程中，系统不断的用已知的事实与知识库中的知识进行匹配，此时可能发生如下三种情况：（1）已知事实不能与知识库中的任何知识匹配成功。（2）已知事实恰好与知识库中的一条知识匹配成功。（3）已知事实可与知识库中的多条知识匹配成功。第一种情况中,使得推理无法进行下去,第二种情况恰好匹配,第三种情况则出现冲突，需要按一定的策略解决冲突。 312024/8/15郑州大学振动工程研究所4.1基本概念目前解决冲突的策略有多种，其基本思想都是对知识进行排序，常用的有以下几中：1、按针对性排序设有如下两条产生式规则：r1:IF A1 and A2 and An THEN H1r2:IF B

20、1 and B2 and Bm THEN H2如果存在最一般合一，使得r1中每一个Ai都可变成相应的Bi ，即r2中除了包含的r1全部条件A1,A2, , An外，还包含其它条件，则称r2 比 r1有更大的针对性， r1 比r2 有更大的通用性。322024/8/15郑州大学振动工程研究所4.1基本概念上面的策略是优先选用针对性较强的产生式规则。(即应选用r2)因为它要求的条件较多，其结论一般更接近目标，一旦得到满足，可缩短推理过程。332024/8/15郑州大学振动工程研究所4.1基本概念2、按已知事实的新鲜性排序在产生式系统推理过程中，每应用一条产生式规则就会得到一个或多个结论，数据库就会

21、增加新的事实。把数据库后生成的事实称为新鲜的事实，即后生成的事实比先生成的事实具有较大的新鲜性。设规则r1可与事实组A匹配成功，规则r2可与事实组B匹配成功，则A与B中哪一组新鲜与它匹配的产生式规则就先被应用。342024/8/15郑州大学振动工程研究所3、按匹配度排序在不确定性匹配中，为了确定两个知识模式是否可以匹配，需要计算这两个模式的相似程度，当其相似程度达到某个预定的值时，就认为它们是可匹配的。若两条规则均按匹配度匹配成功，则匹配度大的那条规则优先启用。352024/8/15郑州大学振动工程研究所4、根据领域问题的特点排序某些领域问题可事先知道它的某些特性，可根据这些特性把知识排成固定

22、的顺序，按照领域知识特性决定匹配顺序。362024/8/15郑州大学振动工程研究所5、按上下文限制排序把产生式规则按它们所描述的上下文分成若干组，在不同的条件下，只能从相应的组中选取有关的产生式规则。这样可以减少冲突的发生6、按冗余限制排序若哪一条产生式规则被应用后产生冗余知识，则就降低它被应用的优先级。7、按条件个数排序如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用。372024/8/15郑州大学振动工程研究所4.2自然演绎推理从一组已知的事实出发，直接运用经典逻辑推理规则推出结论的过程称为自然演绎推理。其中，基本的推理规则是P规则、T规则、假言推理、拒取式推理等。假

23、言推理的一般形式是：P，PQ Q拒取式的一般形式是PQ，Q P以下是自然演绎推理的例子：382024/8/15郑州大学振动工程研究所4.2自然演绎推理（续）例1：已知A，B，AC，BC D，D Q求证 Q1、A P规则2、AC P规则3、C T规则1和24、B P规则5、BC T规则3和46、BC D P规则7、D T规则5和68、D Q P规则9、Q T规则7和8问题得证P规则：在推理的任何步骤上都可引入前题T规则：在推理时，如果前面步骤中有一个或多个永真蕴涵公式S，则可把S引入推理过程。392024/8/15郑州大学振动工程研究所4.2自然演绎推理（续）例2设已知如下事实；（1）凡是容易的

24、课程小王（Wang)都喜欢。（2）C班的课程都是容易的。（3）ds是C班的一门课程求证小王喜欢ds这门课程。证明：首先定义谓词如下：EASY(x): x是容易的LIKE(x,y): x喜欢yC(x): x是C班的一门课程于是问题可以表示成：402024/8/15郑州大学振动工程研究所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)

25、 LIKE(Wang,ds) T规则和35、LIKE(Wang,ds) 得证412024/8/15郑州大学振动工程研究所 4.2自然演绎推理（续）自然演绎推理的优点是表达定理证明过程自然，容易理解，拥有丰富的推理规则，推理过程灵活，便于在推理过程中嵌入领域启发知识。缺点是容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增，这对于一个大型推理问题是十分不利的，甚至是不可能实现的。422024/8/15郑州大学振动工程研究所以下还有的推理方法：归结演绎推理与/或形演绎推理自己看书432024/8/15郑州大学振动工程研究所4.3归结演绎推理定理证明是人工智能的一个重要研究领域，这不仅仅是

26、因为许多数学问题要通过定理证明得以解决，很多非数学问题（如医疗诊断、机器人规划及难题求解等）也都归结为一个定理证明问题。定理证明的实质是对前提P和结论Q证明P Q的永真性。但是证明一个谓词公式的永真性不像证明一个命题公式的永真性那麽简单，（它牵涉到谓词变量、客体变量及函数符号）在某些情况下甚至是行不通的。在这种情况下，人们提出了用反证法来解决问题的思路。在这方面，海伯伦和鲁宾逊都作出了杰出的贡献。两人的研究都是以子句集为背景展开的。接下来，我们介绍这些概念。442024/8/15郑州大学振动工程研究所4.3归结演绎推理（续）子句：在谓词逻辑中，称原子谓词公式及其否定为文字；任何文字的析取式为子

27、句。例如，P（x) Q(x), P(x,f(x) Q(x,g(x)都是子句。而P（x) 、 Q(x,g(x)、 P(x,f(x)等都是文字。并把不包含任何文字的子句称为空子句。由于空子句不包含任何文字，它不能被任何解释所满足，所以空子句是永假的，不可满足的。由子句构成的集合称为子句集。在谓词逻辑中任何一个谓词公式均可通过等价变换化为相应的子句集。452024/8/15郑州大学振动工程研究所4.3归结演绎推理（续）化子句集的步骤如下：1、利用等价公式消去公式中的逻辑连接词“”和“”：P QPQP Q （PQ）（P Q）2、利用下列公式将否定符号“”深入到单个变元前 P P （P Q） P Q （

28、P Q） P Q (x)P (x) P(x)P (x) P462024/8/15郑州大学振动工程研究所3、重新命名变元名，使不同量词约束的变元有不同的名字 4、消去存在量词。分两种情况处理：一种情况是存在量词不出现在全称量词的辖域内，此时只要用一个新的个体常量替换受该存在量词约束的变元就可消去存在量词；另一种情况是存在量词位于一个或多个全称量词的辖域内，例如（x1) （x2)(xn)( y)P(x1,x2,xn,y)此时需要用Skolem函数f(x1,x2,xn)替换受该存在量词约束的变元，然后才能消去存在量词。5、把全称量词全部移到公式的左边。6、利用等价关系P （QR） =（ P Q） （

29、 P R）把公式化为 Skolem标准型。472024/8/15郑州大学振动工程研究所4.3归结演绎推理（续）Skolem标准型的一般形式是：（x1) （x2)(xn)M其中，M是子句的合取式，称为Skolem标准型的母式。7、消去全称量词8、对变元更名，使不同子句中的变元不同名。9、消去合取连接词，变为子句集。子句集中各子句之间是合取关系。谓词公式是不可满足的，则其子句集合是不可满足的，反之亦然。 482024/8/15郑州大学振动工程研究所 4.3归结演绎推理（续）如何证明一个子句集是不可满足的呢？下面就海伯伦理论和鲁宾逊的归结原理进行讨论。一、海伯伦理论要判定一个子句集是否是不可满足的，

30、需要对子句集中的谓词公式进行判定，而谓词公式的判定需要对个体域上的任何解释进行判定，这是很困难的。海伯伦定义了一个特殊的域称为海伯伦域，在任何域上的判定，只要在海伯伦域上 进行即可。*设S是子句集，则按下述方法构造的域H称为是海伯伦域：492024/8/15郑州大学振动工程研究所4.3归结演绎推理（续）1、令H0是S中所有个体常量的集合，若S中不包含个体常量，则令H0 =a，其中a为任意指定的一个个体常量。2、令Hi+1 = HiS中所有n元函数f(x1,x2,xn) | xj(j=1,2,n)是Hi中的元素，其中，i = 0,1,。下面通过例子来解释这个定义。例1求子句集S=P(x)Q(x)

31、,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),502024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）例2 求子句集S=P(a),Q(b),R(f(x)的H域解：根据H域的定义得到：H0 =a,bH1=a,b,f(a),f(b) 例3：求子句集S=P(x),Q(y)R(y)的H域。解：由于该子句集中既无个体常量，又无函数，所以可任意指定一个常量a作为个体常量，从而得到H0 = H1= H= a有定理说：子句集S是不可满足的

32、充要条件是S对H域上的一切解释都为假。并且海伯伦证明了若子句集S在任何域D上的解释能满足S，则在H域上相应的解释也能满足S。下面我们说明，S在H域上解释的定义：512024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）子句集S在H域上的一个解释满足下列条件：1、在解释I下，常量映射到自身；2、S中的任一个n元函数是HnH的映射。即，设h1,h2,hnH,则f(h1,h2,hn) H;3、S中的任一n元谓词是HnT，F的映射。即谓词的真值可以指派T也可指派F。海伯伦在理论上证明了子句集不可满足性的可行性及方法，但要在计算机上实现其证明过程还是很困难的。1965年鲁宾逊提出了归结原理，使

33、机器证明成为现实522024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）*鲁宾逊归结原理归结原理也称消解原理，是鲁宾逊提出的一种证明子句不可满足性，从而实现定理证明的一种理论及方法。由谓词公式转化为子句集的过程可以看出，在子句集中子句之间的关系是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。前面，我们曾经说过空子句是不可满足的，即一个子句集中若含空子句，则它是不可满足的。归结原理的基本思想就是检查子句集中是否含空子句，若含则子句集S不可满足，或说证明一个谓词公式是永假的过程，就是归结由此公式转换成的子句集包含空子句的过程。532024/8/15郑州大学振动工程研究所 4

34、.3归结演绎推理(续）下面我们先来说明命题逻辑中的归结原理定义P是原子谓词公式，则称P与P为互补文字。我们知道在命题逻辑中有公式：PQ,Q R P R即 P Q， Q R P R c1 c2 c12显然上述公式向我们展示的是在子句c1 中存在文字Q，在子句c2中存在Q的补文字 Q，把这一对互补文字消去，剩下的文字析取起来就是子句 c1 和c2的逻辑结果c12。并称c12是c1 和c2的归结式， c1 和c2则称为c12的亲本子句。542024/8/15郑州大学振动工程研究所4.3归结演绎推理(续） 例如：1、C1= P Q R C2= Q S它们的归结式c12为 P R S2、C1= P C2

35、=P它们的归结式c12为NIL即空子句。3、C1= P Q C2= Q R C3=P它们的归结式c123为R。其归结过程可以用下面的一个树形结构很清楚的表现出来。552024/8/15郑州大学振动工程研究所4.3归结演绎推理(续） PQ QR PR P R 归结过程的树形表示图562024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）由命题逻辑中的归结原理可以得出如下的推论：设c1与c2是子句集S中的两个子句，c12是它们的归结式,若用c12代替c1和c2后得到新子句集S1，则由S1的不可满足性可以推出S的不可满足性。这个定理告诉我们，证明子句集S的不可 满足性问题，可以转化成证子句

36、集S1的不可满足性问题，直到从子句集Sn 中推出一个空子句来。572024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）谓词逻辑中的归结原理在谓词逻辑中，由于子句中含有变元，所以不象命题逻辑中那样可以直接消去互补文字，而先要用最一般合一对变元进行代换。然后才能进行归结。前面我们已经介绍过最一般合一的概念，下面给出谓词逻辑中二元归结式的概念。*设C1与C2是两个没有公共变量的子句，L1和L2 分别是C1与C2中的文字，若是L1和L2的最一般合一，则称C12= （ C1 -L1 ）（ C2 - L2 ）为C1与C2的二元归结式， L1和L2称为归结式上的文字。例子见P132页的例4.10

37、和例4.11。582024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）在谓词逻辑中二元归结式可能是下列情形之一：C1和C2的二元归结式 ；C1和C2的因子C22的二元归结式；C1的因子C11和C2的二元归结式 ；C1的因子C11和C2的因子C22的二元归结式 。下面我们介绍归结反演证明子句集不可满足的过程：设有如下的定理证明问题：P1，P2，,PnQ592024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）根据定义即证：P1P2，, Pn QT （1）即证（P1P2，, Pn） QT （2）即证 （P1P2，, Pn） Q）F （3）即证P1P2，, Pn QF （4）我

38、们的工作现在是反向进行，即从证（4） （3） （2）（1） 问题得证。设F为已知前提P1P2 ，, Pn的公式集，Q为目标公式，归结反演的过程：是把F， Q，化为子句集S，对S中的子句进行归结，并把每次归结得到的归结式并入S中，若出现空子句，则停止归结，即证明Q为真。602024/8/15郑州大学振动工程研究所4.3归结演绎推理(续） 下面我们用例子来说明这个过程见P134页的例4.12例4.16从上面的例子可以看出归结过程关键的是从子句集中找出可进行归结的一对子句。机器上用的是水平浸透法，这一过程可能产生大量无用子句，造成时间和空间的浪费。因此，如何提高消解效率就变成一个重要的研究课题。下面

39、提出的都是一些有效的方法：1、删除策略从水平浸透法的本质可以看出，提高消解效率的要害是使子句集合中子句的数量越少越好，子句中文字的数量越少越好。删除策略正是从这一点考虑提出的。几种删除方法如下：612024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）（1）纯文字删除法如果某文字L在子句集中不存在可与之互补的文字L，则称该文字是为纯文字。显然在归结时纯文字不可能消去，因此，包含它的子句进行归结时不可能得到空子句，即这样的子句对归结是无意义的，所以，这样的子句从子句集中删除。（请给出纯文字删除的算法实现）（2）重言式删除法如果一个子句中同时包含互补文字对，则称该子句为重言式，显然重言式

40、不会影响子句集合S的不可满足性，所以，可以从子句集合中删除。（给出检查一个公式是否是重言式的算法实现）（3）包孕删除法（被归类的子句可以删除）设有子句C1和C2，如果存在代换，使得C1 C2，则称C1包孕于C2或说C2包孕C1，包的子句可以删除，即622024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）子句C2可以删除。（想一想它的原理是什麽？P（PQ）=P）2、支持集策略每次归结时，亲本子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔。例如有子句集合S=I(x) R(x), I(a), R(y) L(y), L(a)其中I(x) R(x)是目标公式的否定得到的子

41、句。用支持集归结的过程是：S:（1） I(x) R(x) (2) I(a) (3) R(y) L(y) (4) L(a)S1 (5) R(a) (1)与（2）归结632024/8/15郑州大学振动工程研究所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 开

42、始做归结，其次是归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而BiS Ck(ki) (已出现过的归结式）。这里关键的问题是顶子句的选择，一般选择结论的否定作为顶子句。642024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）例如：证明P Q， P Q， P Q P Q解，问题转化成证子句集合S=P Q， P Q， P Q ， P Q 的不可满足问题，用线形消解的图解表示如下：652024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）4、单文字子句策略如果一个子句只包含一个文字，则称它为单文字子句。单文字子句策略要求参加归结的两个子句中必须至少有一

43、个是单文字子句。例子见P142页的例4.20.但单文字策略是不完备的，即当子句集合中不存在单文字子句时，不能使用单文字子句策略。5、祖先过滤形策略该策略与线性输入策略比较相似，它要求对两个子句进行消解时，只要它们满足下面两个条件之一就可进行归结。（1）C1与C2中至少有一个是初始子句集中的子句。 （2）如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先。所谓C1是C2的祖先是指C2是由 C1和其它子句消解得到的消解式。662024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）例4.21设有子句集S=P(x)vQ(x),P(y)vQ(y),P(u)vQ(u), P(t)vQ(

44、t)归结过程如下图所示：672024/8/15郑州大学振动工程研究所4.3归结演绎推理(续）以上我们讨论了归结演绎推理，它是在定理自动证明中影响较大的一种推理方法。它的缺点是要求把谓词公式转化成子句集，不便于理解，另外它还可能会丢失一些重要的控制信息。针对归结演绎存在的上述问题，人们提出了多种非子句定理证明的方法，尼尔逊提出的基于与/或形的演绎推理就是其中的一种。682024/8/15郑州大学振动工程研究所4.4 与/或形演绎推理归结演绎要求把相关问题的知识及问题的否定均转化成子句形式，然后通过归结演绎推理，其推理规则只有一条，即归结规则。与/或形演绎推理则是把领域知识及已知事实分别用蕴含式及

45、与/或形表示出来，然后通过运用蕴含式进行演绎推理，从而证明某个目标公式。与/或形演绎推理分别分为正向演绎、逆向演绎及双向演绎三种推理形式，下面分别介绍它们。4.4.1与/或形正向演绎推理在这种推理中，对已知事实、F规则及目标公式的表示形式都有一定的要求，如果不满足要求的形式就需要变换。692024/8/15郑州大学振动工程研究所4.4 与/或形演绎推理1、事实表达式的与/或形变换及其树形表示变换过程与化子句集类似，只是不必化为子句的合取形式，也不消去公式中的合取词。2、F规则的表示形式在与/或形正向演绎推理中，通常要求F规则具有如下的形式： LW其中，L是单文字，W是与/或形。之所以要求F规则

46、的左部为单文字，是因为在进行演绎推理时，要用F规则作用于表示事实的与/或树，而该与/或树的叶节点都是单文字，这样就可以用F规则的左部与叶节点进行简单匹配（合一）。702024/8/15郑州大学振动工程研究所4.4 与/或形演绎推理如果领域知识不是上面的形式则通过等价变换变成规定的形式。例如对公式（x)(y)(z)P(x,y,z) (u)Q(x,u)（x)( (y)(z)P(x,y,z) (u)Q(x,u) (x)( (y) (z) P(x,y,z) (u)Q(x,u) (x) (y) (z) (u)( P(x,y,z) Q(x,u) (u)( P(x,y,f(x,y) Q(x,u) P(x,y

47、,f(x,y) Q(x,u) P(x,y,f(x,y) Q(x,u) 712024/8/15郑州大学振动工程研究所4.4 与/或形演绎推理3、目标公式的表示形式在与/或形正向推理中，要求目标公式用子句表示，否则就需要化成子句形式，转化方法同前。4、推理过程应用F规则进行推理的目的在于证明某个目标公式。如果从已知事实的与/或树出发，通过运用F规则最终推出了欲证明的目标公式，则推理就可成功结束。其推理过程如下：(1)首先用与/或树把已知事实表示出来；(2)用F规则的左部和与/或树的叶节点进行匹配，并将匹配成功的F规则加入到与/或树中；(3)重复第(2)步，直到产生一个含有目标节点作为终止节点的解图为止。722024/8/15郑州大学振动工程研究所4.4 与/或形演绎推理（续）设已知的事实为AVBF规则为：r1: ACDR2:BEG欲证明的目标公式为：CVG 其证明过程如右图所示732024/8/15郑州大学振动工程研究所4.4 与/或形演绎推理（续）上图中已知事实为AVBF规则为：r1:ACD r2:BEG欲证明的目标公式为 C G