人工智能ppt课件第4章

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,第四章 推理方法,要使计算机具有智能，仅仅使它拥有知识还不够，还必须使其具有运用知识进行推理，实现问题求解的能力。因此有关推理方法的研究是人工智能的重要课题之一。,4.1 推理概述,4.1 推理概述,4.1.1,推理的基本概念,所谓推理是指从已知事实出发，运用已掌握的知识，推导出其中蕴涵的事实性结论或归纳出某些新的结论的过程。,推理过程实际上也就是一个问题求解的过程。,推理概述,4.1.2 推理的方法及其分类,1. 按照推理的逻辑基础分类,（1）演绎推理,演绎推理是从已知的一般性知识出发，推理出适合于某种个别情况的结论的过程。它是一种由一般到个别的推理方法。,例如：,A.,音乐系的学生至少会弹奏一种乐器；,B.,李聪是音乐系的学生；,C.,李聪至少会弹奏一种乐器。,（2）归纳推理,归纳推理是从大量特殊事例出发，归纳出一般性结论的推理过程，是一种由个别到一般的推理方法。其基本思想是：首先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。,（3）默认推理,默认推理又称缺省推理，是在知识不完全的情况下假设某些已经具备所进行的推理。,2. 按所用知识的确定性分类,（1）,确定性推理,（2）,不确定性推理,3. 按推理过程的单调性分类,（1）,单调推理,所谓单调推理是指在推理过程中，由于新知识的加入和使用，使推理所得到的结论会越来越接近于最终目标，而不会出现反复情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理过程又退回到前面的某一步。,（2）,非单调推理,非单调推理则是指在推理过程中，当某些新知识加入后，不但没有加强已经推出的结论，反而会否定原来已推出的结论，使推理过程要退回到先前的某一步，重新进行推理。,4.1.3 推理的控制策略,智能系统的推理过程其实就是问题求解的过程，它不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。推理的控制策略包括推理方向、搜索策略、冲突消解策略、求解策略、限制策略；而推理方法则是推理控制策略确定之后，在进行具体推理时所要采取的匹配方法或不确定性传递算法等方法。,1.正向推理,正向推理又称为正向链接推理，它是一种数据驱动的推理方式，其推理基础是逻辑演绎的推理链，它从一组表示事实的谓词或命题出发，使用一组推理规则，来证明目标谓词公式或命题是否成立。,正向推理过程的算法描述：,（1）把用户提供的初始数据或已知事实放入到综合数据库。,（2）检查综合数据库中是否包含了问题的解，若有，则求解结束，并成功推出；否则执行（3）；,（3）检查知识库中是否有与综合数据库中已有事实相匹配的知识，若有，则将所有的匹配知识构成当前匹配知识集，转（4）；否则转（5）；,（4）按照某种冲突消解策略，从当前匹配知识集中选出一条知识作为启用知识用于进行推理，并将推出的新事实或证据加入到综合数据库中，然后转（2）；,（5）询问用户是否可以进一步补充新的事实或证据，若可补充，则将补充的事实或证据加入综合数据库中，然后转（3）；否则表示无解，失败退出。,例如，有规则集如下： 规则1：,IF P1 THEN P2,规则2：,IF P2 THEN P3,规则3：,IF P3 THEN q3,规则中的,P1、P2、P3、q3,可以是谓词公式或命题。设总数据库（工作存储器）中已有事实,P1，,则应用这三条规则进行正向推理，即从,P1,出发推导出,q3,的过程如下图所示。,2.反向推理 （逆向推理）,反向推理又称为后向链接推理，它是一种目标驱动的推理方式，其基本原理是从表示目标的谓词或命题出发，使用一组规则证明事实谓词或命题成立，即提出一批假设（目标），然后逐一验证这些假设。,首先假定目标,q3,成立，由规则（,P3q3），,为证明,q3,成立，须先验证,P3,是否成立；但总数据库没有事实,P3，,所以假定子目标,P3,成立；由规则（,P2P3），,应验证,P2；,同样，由于数据库中没有事实,P2，,假定子目标,P2,成立；由规则（,P1P2），,为验证,P2,成立，须先验证,P1。,因为数据库中有事实,P1，,所以假定的目标,P2,成立，因而,P3,成立，最终导出结论,q3,确实成立。,举例如下：仍用上述的三条规则为例，应用反向推理方法，,从,P1,出发推导出,q3,的过程如下图所示：,总之，反向推理的具体实现策略是：先假定一个可能的目标，系统试图证明它，看此假设目标是否在总数据库中，若在，则假设成立。否则，看这些假设是否证据（叶子）结点，若是，向用户询问，若不是，则再假定另一个目标，即找出结论部分中包含此假设的那些规则，把它们的前提作为新的假设，试图证明它。这样周而复始，直到所有目标被证明，或所有路径被测试。,3.双向推理,双向推理 又称为正反向混合推理，它综合了正向推理和逆向推理的长处，克服了了两者的短处。,双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。,具体的推理策略有多种。例如，通过数据驱动帮助选择某个目标，即从初始证据（事实）出发进行正向推理，同时以目标驱动求解该目标，通过交替使用正逆向混合推理对问题进行求解。双方推理的控制策略比前两种方法都要复杂。美国斯坦福研究所人工智能中心研制的基于规则的专家系统工具,KAS，,就是采用正、逆向混合推理的产生式系统的一个典型例子。下图给出双向混合推理过程的示意图。,4.1.2 推理的冲突消解策略,在利用推理求解问题的过程中，如果综合数据库中的已知事实与知识库中的多条知识相匹配，或者有多个已知事实都可与知识库中的某一条知识相匹配，或者有多个已知事实与知识库中的多条知识相匹配，则称这种情况为知识冲突。此时，需要按照某种策略从这多条匹配的知识中选择一条最佳知识用于推理，这种解决冲突的过程称为冲突消解。,（1）按就近原则排序,（2）按知识特殊性排序,（3）按上下文限制排序,（4）按知识的新鲜性排序,（5）按知识的差异性排序,（6）按领域知识的特点排序,（7）按规则的次序排序,（8）按前提条件的规模排序,4.2 命题逻辑,命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的自动证明发挥了重要作用，在人工智能的发展史中占有重要地位。,谓词逻辑是在命题逻辑的基础上发展起来的，命题逻辑可看作是谓词逻辑的一种特殊形式，在讨论谓词逻辑之前，先来介绍命题逻辑的基本概念。,4.2.1,命题,定义3.1 能够分辨真假的语句称做命题。,定义3.2,一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题。,原子命题是命题中的基本单位。,命题，比如“太阳从东边升起”，“雪是白的”,4.2.2,命题公式,1. 连接词,命题逻辑中，可以通过连接词将一些原子命题连接起来，构成复合命题，以表示复杂的定义。,称为“非”或“否定”。,称为 “析取”。表示被它连接的两个命题具有“或”的关系。,称为 “合取”。表示被它连接的两个命题具有“与”的关系。,称为“条件”或“蕴涵”.,P,Q,表示“,P,蕴涵,Q”，,即“如果,P，,则,Q”，,其中,P,为条件的前提，,Q,为条件的后件。,称为“双条件”.,P,Q,表示“,P,当且仅当,Q”,AI,的产生及主要学派,2. 命题公式,定义4.3 下面的递归形式给出命题公式的定义：,（1）,原子公式是命题公式,（2）,A,是命题公式，则,A,也是命题公式；,（3）若,A,和,B,都是命题公式，则,A,B，A,B，A,B，A,B,也都是命题公式,（4）只有（1）（3）所得的公式才是命题公式。,4.3 谓词逻辑,3.3.1 谓词与个体,在谓词逻辑中，将原子命题分解为谓词与个体两部分。,例如，“贝多芬是作曲家”中，“是作曲家”是谓词， “贝多芬”是个体。所谓个体是指可以独立存在的物体，它可以是抽象的，也可以是具体的。,例如，“李白是诗人”这个命题，若用,poet,表示“是诗人”，用,Libai,表示个体“李白”，则得到的谓词是,poet(,Libai,).,又如，53,这个不等式可用谓词表示为,greater(5,3),谓词的一般形式是：,P（x1,x2,xn,）,其中,P,是谓词，,x1,x2,xn,是个体。,例如，“小刘的哥哥是工人”，可以表示为,worker(brother(Liu),其中,brother(Liu),是一个函数。个体常数，变量和函数统称为,项,。,谓词中包含的个体数目称为谓词的元数，例如,P(x),是一元谓词，,P(x,y),是二元谓词，而,P(x1,x2,xn,),是,n,元谓词。,在谓词,P(x1,x2,xn,),中，若,xi,(i=1,2,n),都是个体常量、变元或函数，则称它为一阶谓词。如果,xi,本身又是一个一阶谓词，则称它为二阶谓词，依次类推。,谓词和函数从形式上看很相似，其实它们有着本质的区别，是两个完全不同的概念。谓词具有逻辑值“真”或“假”，而函数则是某个个体到另一个个体之间的映射。,3.3.2 谓词公式,1. 连接词,与命题逻辑中相同。,2. 量词,全称量词（,x,）表示“对于个体域中的所有个体,x”；,存,在量词(,x),表示,“,在个体域中存在个体,x,”,.,3. 谓词演算公式,定义4.4,谓词演算中，由某个谓词构成的不含任何连接词的公式，叫做原子谓词公式。一般一个形如,F(x1,x2,xn,),的谓词公式，称作,原子谓词公式,，或简称,原子,，其中,F,为,n,元谓词，而,x1,x2,xn,为个体变元。,定义4.5,可按下列规则得到谓词演算的合式公式如下：,(1) 原子谓词公式是合式公式；,(2),A,是合式公式，则,A,也是合式公式；,(3) 若,A,和,B,都是合式公式，则,A,B，A,B，A,B，A,B,也都是合式公式,(4) 若,A,是合式公式，,x,是一个体变元，则(,x)A,和(,x)A,也都是合式公式,(5) 只有(1)(4)所得的公式才是合式公式。,谓词演算公式就是一个按照一定规则由原子公式、连接词、量词及圆括号所组成的字符串。,例如：,(,x)P(x,y),(,x)(P(x),P(y),4. 谓词辖域与约束变元,在一个公式中，如果有量词出现，位于量词后面的单个量词或者用括弧括起来的合式公式称为,量词的辖域,。在辖域内与量词中同名的变元称为,约束变元,，不受约束的变元称为,自由变元,。,3.3.3 谓词公式的永真性与可满足性,1. 谓词公式的解释,定义4.6 设,D,为谓词公式,P,的个体域，若对,P,中的个体常量、函数和谓词按照下列规定赋值,：,（1）为每个个体常量指派,D,中的一个元素；,（2）为每个,n,元函数指派一个从,D,n,到,D,的映射，其中,D,n,(x1,x2,xn,)| x1,x2,xn,D,（3）为每个,n,元谓词指派一个从,D,n,到,F,T,的映射；,则称这些指派为公式,P,在,D,上的一个,解释,。,一般情况下，谓词公式的真值都是针对某一解释而言的。同一个公式可能在一种解释下其真值是,T，,而在另一种解释下，其真值是,F。,2. 谓词公式的永真性,定义4.7,如果谓词公式,P，,对个体域,D,上的任何一个解释都取得真值,T，,则称,P,在,D,上是永真的,；如果,P,在每个非空个体域上均永真，则称,P,永真,。,定义4.8,如果谓词公式,P，,对个体域,D,上的任何一个解释都取得真值,F，,则称,P,在,D,上是永假的,；如果,P,在每个非空个体域上均永假，则称,P,永假,。,谓词公式的永假性又称为不可满足性或不相容性。,3. 谓词公式的可满足性,定义4.9,对于谓词公式,P，,如果至少存在一个解释使得公式,P,在此解释下的真值为,T，,则称公式,P,是可满足的。,如果不存在任何解释，使得,P,的取值为,T，,则称公式,P,是不可满足的。,3.3.4 谓词公式的等价性与永真蕴涵,定义4.10,设,P,和,Q,是两个谓词公式，,D,为它们共同的个体域。若对,D,上的任何一个解释，,P,与,Q,的取值都相同，则公式,P,和,Q,在域,D,上是等价的,。如果,D,是任意个体域，则称,P,和,Q,是,等价的,，记做,P,Q。,常用的等价式：,交换律,P,Q Q,P,P,Q Q,P,结合律,(P,Q)R,P,(,QR),(P,Q)R,P,(,QR),分配律,P,(,QR),(P,Q),(P,R),P,(,QR),(P,Q),(P,R),狄.摩根定律,(P,Q) PQ,(P,Q) PQ,否定之否定定律,(,P,) P,吸收律,P,(P,Q),P,P,(P,Q) P,补余律,P,P, T,P,P, F,逆否定律,P,Q,Q,P,连接词化归律,P,Q,PQ,P,Q,(PQ)(QP),P,Q,(PQ)(PQ),量词转换律 (,x,),P,(,x,),(P),(,x,),P,(,x,),(P),量词分配律 (,x,) (,P,Q),(,x,),P,(,x,),Q,(,x,) (,P,Q),(,x,),P,(,x,),Q,定义4.11,对于谓词公式,P,和,Q，,如果,P,Q,永真，则称,P,永真蕴涵,Q，,且称,Q,为,P,的逻辑结论，称,P,为,Q,的前提，记作,P,Q。,下面是一些常用到的永真蕴涵式：,化简式,P,Q,P,P,QQ,附加式,P,P,Q,Q,P,Q,析取三段论,P，P,QQ,假言推理,P，P,QQ,拒取式,Q,，P,QP,假言三段论,P,Q，QR,P,R,二难推论,P,Q,，,P,R,，,Q,RR,全称固化,(,x,) (,P,(,x),P,(,y),其中,y,是个体域上的任一个体，利用此永真蕴涵式可以消去公式中的全称量词,存在固化,(,x,) (,P,(,x),P,(,y),其中,y,是个体域中某个使,P,(,y),为真的个体，利用此式可以消去公式中的存在量词,3.3.5 置换与合一,1. 置换,定义4.12,置换是形如,t1/x1, t2/x2,tn,/,xn,的一个有限集。其中，,xi,是变量，,ti,是不同于,xi,的项（常量、变量、函数），且,xi,xj,(i j),i,j=1,2,n.,例如：,a/x, b/y, f(x)/z, f(z)/x, y/z,2. 合一,定义4.13,设有公式集,E1,E2,En,和置换,，,使,E1,= E2, =,= En,便称,E1，E2， En,是可合一的，且,称为合一置换。,定义4.14,若,E1，E2， En,有合一置换,，,且对,E1，E2， En,的任一置换,都存在一个置换,，,使得,=,，,则称,为,E1，E2， En,的最一般合一置换，记为,mgu,。,例,若,E1Q(y)，E2=Q(z),对,E1,和,E2,来说，,=y/z,和,=z/y,都是它们的最一般合一置换。,4.5.1 谓词公式与字句集,1. 范式,（1）前束形范式,一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之末，同时公式中不出现连接词,及,，这种形式的公式称做前束形范式。,例如：,(,x)(,x)(,z),(P(x),F,(y,x),Q,(y,x),（2）斯克林（,skolem,）,范式,为了克服前束性范式的缺点，斯可林对它进行了改进，使前束性范式的首标不出现存在量词。从前束性范式中消去全部存在量词所得到公式即为,斯克林（,skolem,）,范式，或称,skolem,标准型。,将谓词公式,G,化为,skolem,标准型的步骤如下：,(1) 消去谓词公式,G,中的蕴涵,及双条件,，,以,A,B,代替,A,B，,以（,A,B）,（ ,A,B,）替换,A,B,(2) 减少否定负号的辖域，使否定符号最多只作用到一个谓词上。,(3) 重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。,(4) 消去存在量词。分两种情况，一种使存在量词不出现在全称量词的辖域内，此时，只要用一个新的个体变量替换该存在量词约束的变元，就可以消去存在量词；另一中情况是，存在量词位于一个或多个全称量词的辖域内，比如,(,x1)(,x2),(,xn,),(,y,)P(x1,x2,xn,y,),此时变元,y,实际受前面的变元,x1,x2,xn,的约束，需要用,Skolem,函数,f(,x1,x2,xn,),替换,y,即可将存在量词,y,消去，得到,(,x1)(,x2),(,xn,),(,y)P(x1,x2,xn,f(,x1,x2,xn,),),(5) 把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。,(6) 母式化为合取范式：任何母式都可以写成由一些谓词公式否定的析取的有限集组成的合取。,例： 将谓词公式,G=,(,x)(,y,),P(x,y), (,y,)(Q,(x,y), R,(x,y),化为,Skolem,标准型。,解,：（1）,消去,及,连接词。,(,x)(,y,),P(x,y), (,y,)(Q,(x,y),R,(x,y),（2）把的辖域减少到最多只作用于一个谓词。,(,x)(,y,) ,P(x,y),(,y,)(Q,(x,y),R,(x,y),（3）,变量更名,(,x)(,y,) ,P(x,y),(,z,)(Q,(x,z),R,(x,z),（4）,消去存在量词。因为存在量词,(,y,),和,(,z,),都在辖域(,x),内，属于上述所讲的第二种情况，所以分别用,skolem,函数,f(x),和,g(x),替换,y,和,z。,(,x)(,P(x,f(x),),(Q,(x,g(x),),R,(x,g(x),),（5）,全称量词移到左边。由于只有一个全称量词,(,x)，,已在左边，所以不移。,（6）,将母式化为合取范式。,(,x)( ,P(x,f(x),),(Q,(x,g(x),(,P(x,f(x),),R,(x,g(x),),2. 字句与字句集,定义4.16,不含有任何连接词的谓词公式称作,原子公式,，简称,原子,，而原子或原子的否定统称为,文字,。,例如：,P(x), P(x,c), R(x,y),定义4.17,字句就是由一些文字组成的析取式。,例如：,P(x),Q(x,y), P(x,c),R(x,y,f(x),定义4.18,不含有任何文字的字句称为,空子句,，记做,NIL。,由于空子句不含有任何文字，它不能被任何解释所满足，所以空子句是永假的，不可满足的。,定义4.19,由字句构成的集合称为,字句集,。,谓词公式,skolem,标准型的母式是由一些字句的合取组成的。,如果将谓词公式,G,的,skolem,标准型前面的全称量词全部消去，并用逗号代替合取符号，便可得到谓词公式,G,的字句集,S。,3. 不可满足意义下的一致性,公式,G,与其字句集,S,并不等价，但它们在不可满足的意义下是一致的。,定理4.2,设有谓词公式,G，,而其相应的字句集为,S，,则,G,是不可满足的充分必要条件是,S,是不可满足的。,4.5.2,Herbrand,理论,1.,H,域,定义4.20,设谓词公式,G,的字句集为,S，,则按下述方法构造的个体变元域,H,称为公式集或字句集,S,的,Herbrand,域，简称,H,域。,（1）令,H,0,为,S,中所出现的常量的集合。若,S,中没有常量出现，就任取一个常量,a,D,规定,H,0,a。,（2）,令,H,i+1,=H,i,S,中所有的形如,f(t,1,t,2,t,n,),的元素,其中，,f(t,1,t,2,t,n,),是出现于,G,中的任一函数负号，而,t,1,t,2,t,n,是,H,i,中的元素。这里,i=1,2,n,4.5.3 归结原理,归结原理又称为消解原理，是,Robinson,提出的证明字句集不可满足性，从而实现了定理证明的一种理论和方法。,定义4.25,若,P,是原子谓词公式或原子命题，则称,P,与,P,为互补文字。,1. 命题逻辑中的归结原理,(1) 归结与归结式,定义3.26,设,C1,与,C2,式字句集中的任意两个子句，如果,C1,中的文字,L1,与,C2,中文字,L2,互补，则从,C1,和,C2,中可以分别消去,L1,和,L2，,并将两个子句余下的部分做析取构成一个新的子句,C12，,称这一过程为归结，所得到的子句,C12,为,C1,和,C2,的,归结式,，而称,C1,和,C2,为,C12,的,亲本子句,。,归结过程是一种推理规则，即,C1,C2,C12,定理3.6,归结式,C12,是其亲本子句,C1,和,C2,的逻辑结论。,推论,设,C1,和,C2,是子句集,S,上的子句，,C12,是,C1,和,C2,的归结式。如果把,C12,加入到子句集,S,得到新的子句集,S1，,则,S1,和,S,在不可满足的意义下是等价的。,(2) 归结推理过程,由上面的推论以及空子句的不可满足性，可以得出证明子句集,S,不可满足性的推理过程如下：,A,对子句集,S,中的各子句间使用归结推理规则。,B,将归结所得的归结式放入子句集,S,中，得到新的子句集,S。,C,检查子句集,S,中是否有空子句，若有，则停止推理；否则转步骤,D。,D,置,SS，,转步骤,A。,例 4.14 证明子句集,S=P,Q, Q, P,是不可满足的。,证明：,(1),P,Q,(2),Q,(3),P,(4) P (1),和(2) 归结,(5) NIL (3),和(4) 归结,2. 一阶谓词逻辑中的归结原理,在一阶谓词逻辑中，由于子句中含有变元，所以不能像命题逻辑中那样可以直接消去互补文字进行子句归结。而是要首先使用置换与合一的思想，对子句中的某些变元进行合一置换，对置换后的新子句再次使用归结规则。,定义4.27,设,C1,与,C2,是两个没有相同变元的子句，,L1,和,L2,分别为,C1,和,C2,的文字，如果,L1,与,L2,有,mgu,则把,C12(C1,-,L1,),(,C2,-,L2,),，,称作子句,C1,和,C2,的一个,二元归结式,，而,L1,和,L2,是被归结的文字。,在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：,（1）若被归结的子句,C1,和,C2,中具有相同的变元，则需要将其中一个子句的变元更名；否则可能无法作合一置换，从而没有办法进行归结。,（2）在求归结式时，不能同时消去两个互补文字时，消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。,例,：,C1P,Q,C2P,Q,（3）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的简化。,例：,C1=P(x),P(f(a),Q(x),C2= P(x),R(b),用它们最一般合一,=,f(a)/x,进行置换得到,C1,=,P(f(a),Q(f(a) ),再对,C1,和,C2,进行归结，选用,mgu,为,=f(a)/x,得到,C1,和,C2,的二元归结式为,C12R(b),Q(f(a) ),定义4.28,设,C1,与,C2,是没有相同变元的子句，则下列四种二元归结式都叫做,C1,与,C2,的归结式，仍记做,C12。,（1）C1,与,C2,的二元归结式。,（2）,C1,的因子,C1,1,与,C2,的,二元归结式。,（3）,C1,与,C2,的因子,C2,2,的,二元归结式。,（4）,C1,的因子,C1,1,与,C2,的因子,C2,2,的,二元归结式。,4.5.4 利用归结原理进行定理证明,设要证明的定理可用谓词公式表示为如下的形式,A1,A2,An,B,，应用归结原理进行定理证明的步骤如下：,(1) 首先否定结论,B，,并将否定后的公式,B,与前提公式集组成如下形式的谓词公式：,G=A1,A2,An,B,(2) 求谓词公式,G,的子句集,S。,(3) 应用归结原理，证明子句集,S,的不可满足性，从而证明谓词公式,G,的不可满足性。这就说明对结论,B,的否定是错误的，推断出定理的成立。,例4.18 已知：,A：,(,x)(,y,) ,P(x,y),Q,(y),(,y,)(R,(y),T,(x,y),B: ,(,x) R,(x),(,y,) ,P(x,y),Q,(y),(,x)(,y,),P(x,y),Q(y),证明：,首先将,A,和,B,化为子句集。,(1),P(x,y),Q,(y),R,(f(x),(2),P(x,y),Q,(y),T,(x,f(x),(3), R,(z),(4) P(a,b),(5) Q(b),下面进行归结：,(6),P(x,y),Q,(y) (1),与,(3),进行归结,(7) ,Q,(b) (4),与,(6),进行归结,(8) NIL (5),与,(7),进行归结,4.5.5 利用归结原理进行问题求解,归结原理不仅可以应用于定理证明，而且也可以用来求取问题的答案，其步骤如下：,(1) 把已知前提条件用谓词公式表示出来，并化为相应的子句集，设该子句集的名字为,S1。,(2) 把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词,ANSWER,构成析取式。谓词,ANSWER,是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。,(3) 把问题公式与谓词,ANSWER,构成的析取式化为子句集，并把该子句集,与,S1,后并构成子句,集,S。,(4) 对子句集,S,应用谓词归结原理进行归结，再归结过程中，通过合一置换，改变,ANSWER,中的变元。,(5) 如果得到归结式,ANSWER，,则问题的答案即在,ANSWER,谓词中。,例：某人被盗，公安局派出所派出5个侦察员去调查。研究案情时，侦察员,A,说“赵与钱中至少有一人作案”；侦察员,B,说“钱与孙中至少有一人作案”；侦察员,C,说“孙与李中至少有一人作案”；侦察员,D,说“赵与孙中至少有一人与此案无关”；侦察员,E,说“钱与李中至少有一人与此案无关”。如果5个侦察员的话都是可信的，试问谁是盗窃犯呢？,解：,第一步 将5个侦察员的话表示成谓词公式，为此先定义谓词。设谓词,P(x),表示作案者，则根据题意：,A：P(,zhao,),P(,qian,),B：P(,qian,),P(sun),C：P(sun),P(,li,),D：P(,zhao,),P(sun),E：P(,qian,),P(,li,),第二步 将待求问题表示成谓词。设,y,为盗窃犯，则,P(y),ANSWER,(y),第三步 求前提条件及,P(y),ANSWER,(y),的子句集，并将各子句列表如下：,(1),P(,zhao,),P(,qian,),(2),P(,qian,),P(sun),(3),P(sun),P(,li,),(4),P(,zhao,),P(sun),(5),P(,qian,),P(,li,),(6),P(y),ANSWER,(y),第四步 应用归结原理进行推理,(7),P(,qian,),P(sun) (1),和(4)归结,(8),P(,zhao,),P(,li,) (1),和(5)归结,(9),P(,qian,),P(,zhao,) (2),和(4)归结,(10),P(sun),P(,li,) (2),和(5)归结,(11),P(,zhao,),P(,li,) (3),和(4)归结,(12),P(sun),P(,qian,) (3),和(5)归结,(13),P(,qian,) (2),和(7)归结,(14),P(sun) (2),和(12)归结,(15),ANSWER,(,qian,) (6),和(13)归结,(16),ANSWER,(sun) (6),和(14)归结,所以，本题的盗窃犯是两个人：钱和孙,4.6 归结过程中的控制策略,4.6.1,引入控制策略,1.引入控制策略的原因,对子句集,S,进行归结时，首先要从子句集中找出可进行归结的一对子句进行归结。如果采用盲目的归结策略，会产生大量的无用的归结式，而且归结式还会重复出现，这不仅浪费计算机的存储空间，而且要浪费大量的计算时间，如果子句集的规模较大的情况下，这种浪费是惊人的。,2.,控制策略分类,归结策略大致可以分为两大类：,第一类是删除策略。,主要是通过删除某些无用的子句来缩小归结的范围，从而提高归结效率；,另一类是限制策略,，是通过对参加归结的子句进行种种限制，尽可能地减少归结的盲目性，使其尽快归结出空子句。,4.6.2,归结控制策略,1.删除策略,（1）纯文字删除法,如果文字,L,出现在,S,中，而,L,不出现在,S,中，便说,L,为,S,的纯文字。,显然归结过程中，纯文字是不可能被消去的，因而包含它的子句进行归结时，不可能得到空子句，即这样的子句对归结是毫无意义的，所以可以把它所在的子句从子句集中删除。,（2）重言式删除法,如果一个子句中同时包含互补文字时，则称该子句为重言式。重言式是取值用真的子句。因此可以从子句集中删除。,（3）包孕删除法,设有子句,C1,和,C2，,如果存在一个置换,，,使,C1,C2，,则称,C1,包孕于,C2。,把子句集中包孕的子句删去后，不会影响子句集的不可满足性，因而可从子句集中删去那些被包孕的子句。,2. 线性归结策略,线性归结策略对参加归结的子句提出如下限制：首先从子句集,S,中先取一个称作顶子句的的子句,C0,开始作归结；其次将归结过程中所得到的归结式,Ci,立即同另一子句,Bi,进行归结，得归结式,Ci,+1,而,Bi,是原子子句,S,中一个子句或是已经归结出的某个归结式,Cj,（ji）。,3. 单文字（单元）归结策略,如果一个子句只含有一个文字，则称该子句为单文字子句或单元子句。,如果归结过程中，每次归结都有一个子句是单文字子句，则称这种归结就是单文字归结。也就是说，单文字归结策略要求参加归结的两个子句中至少有一个是单文字子句。,用单文字归结策略时，归结式将比亲本子句含有较少的文字，这有利于朝着空子句的方向前进，因此它有较高的效率。,4. 输入归结策略,输入归结策略对参加归结的子句有如下限制：参加归结的两个子句中，必须至少有一个子句是初始子句集中的子句。,本归结策略是不完备的，也就是说，该子句集,S,是不可满足的，用该归结原理进行归结时，也不一定能归结出空子句。但是，输入归结策略具有简单高效的优点。,