经典逻辑推理.ppt

第四章经典逻辑推理,4.1 基本概念4.2 自然演绎推理4.3 归结演绎推理4.4 与或形演绎推理,如何实现推理？,逻辑方法是自动证明中常用的方法如何进行逻辑推理？推理的过程怎样？怎么实现推理？,柯南的推理过程,观察结果时钟与分钟重叠在一起时间是六点半推理依据正常的时钟如果是六点半，那么时钟与分钟应该是分开的推理结果有人故意移动过时钟人类的推理可以理解语义机器如何进行这样类似的推理？需要将推理的过程和理解分开，使其形式化,事实,规则,结论,推理的一般形式,已知事实：事实1，事实2，.规则：如果 事实1 那么 结论1 如果 事实2 那么 结论2.得到：结论1，结论2 将事实与规则借助一些符号来表示，推理过程就可以被形式化 P:某已知事实 P Q:如果P，那么Q 结论：Q,符号与形式语言,自然语言不适合计算机处理她用红色水彩笔写了个蓝字。小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑,符号与形式语言,自然语言不适合计算机处理她用红色水彩笔写了个蓝字。小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑命题逻辑谓词逻辑,符号与形式语言,自然语言不适合计算机处理她用红色水彩笔写了个蓝字。小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑命题逻辑谓词逻辑,如果不下雨，我就去你家玩P Q 今天没有下雨 P 我去了你家 Q,凡人都会死 x(Man(x)Mortal(x)苏格拉底是人 Man(Socrates)苏格拉底会死 Mortal(Socrates),4.1 基本概念,4.1.1 什么是推理所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。在人工智能中，推理是由程序实现的，称为推理机。,4.1.2 推理方式及其分类,1.演绎推理、归纳推理、默认推理演绎推理：从一般到特殊。例如三段论。归纳推理：从个体到一般。默认推理：缺省推理，在知识不完全的情况下假设某些条件已经具备所进行的推理。2.确定性、不确定性推理3.单调推理、非单调推理推出的结论是否单调增加4.启发式、非启发式推理所谓启发性知识是指与问题有关且能加快推理进程、求得问题最优解的知识。5.基于知识的推理（专家系统）、统计推理、直觉推理（常识性推理）,4.1.3 推理的控制策略,推理的控制策略主要包括：推理方向、搜索策略、冲突消解策略、求解策略及限制策略。1.正向推理（数据驱动推理）正向推理的基本思想是：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用的知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中，作为下一步推理的已知事实。在此之后，再在知识库中选取可适用的知识进行推理。如此重复进行这一过程，直到求得所要求的解。,正向推理示意图,动物识别的例子,已知事实：一动物有毛，吃草，黑条纹R1：动物有毛 哺乳类 R2：动物产奶 哺乳类 R3：哺乳类 吃肉 食肉类 R4：哺乳类 吃草 有蹄类 R5：食肉类 黄褐色 有斑点 猎狗 R6：食肉类 黄褐色 黑条纹 虎 R7：有蹄类 长脖 长颈鹿 R8：有蹄类 黑条纹 斑马,2 逆向推理,逆向推理的基本思想是：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设。,逆向推理示意图,动物识别系统,r1：if 该动物有毛发 then 该动物是哺乳动物 r2：if 该动物有奶 then 该动物是哺乳动物 r3：if 该动物有羽毛 then 该动物是鸟 r4：if 该动物会飞 and 会下蛋 then 该动物是鸟 r5：if 该动物吃肉 then 该动物是食肉动物 r6：if 该动物有犬齿 and 有爪 and 眼盯前方 then 该动物是食肉动物 r7：if 该动物是哺乳动物 and 有蹄 then 该动物是有蹄类动物 r8：if 该动物是哺乳动物 and 是嚼反刍类动物 then 该动物是有蹄类动物,r9：if 该动物是哺乳动物 and 是食肉类动物 and 是黄褐色 and 身上有暗斑点 then 该动物是金钱豹 r10：if 该动物是哺乳动物 and 是食肉类动物 and 是黄褐色 and 身上有黑色条纹 then 该动物是虎 r11：if 该动物是有蹄类动物 and 有长脖子 and 有长腿 and 身上有暗斑点 then 该动物是长颈鹿 r12：if 该动物是有蹄类动物 and 身上有黑色条纹 then 该动物是斑马,r13：if 该动物是鸟 and 有长脖子 and 有长腿 and 不会飞 then 该动物是鸵鸟 r14：if 该动物是鸟 and 会游泳 and 不会飞 and 有黑白两色 then 该动物是企鹅 r15：if 该动物是鸟 and 善飞 then 该动物是信天翁,3.混合推理先正向推理后逆向推理先逆向推理后正向推理4.双向推理正向推理与逆向推理同时进行，且在推理过程中的某一步上“碰头”。5.求解策略只求一个解，还是求所有解以及最优解。6.限制策略限制搜索的深度、宽度、时间、空间等等。,所谓模式匹配是指对两个知识模式(例如两个谓词公式、框架片断、语义网络片断)进行比较，检查这两个知识模式是否完全一致或者近似一致。模式匹配可分为确定性匹配与不确定性匹配。确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。知识：IF father(x,y)and man(y)THEN son(y,x)事实：father(李四，李小四)and man(李小四)不确定性匹配是指两个知识模式不完全一致，但是它们的相似程度又在规定的限度内。,4.1.4 模式匹配,变量代换,定义4.1 代换是一个形如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是一个代换g(y)/x,f(x)/y不是代换g(a)/x,f(x)/y是代换,令=t1/x1,t2/x2,tn/xn为一个代换，F为表达式，则F表示对F用ti代换xi后得到的表达式。F称为F的特例。规则:IF father(x,y)and man(y)THEN son(y,x)事实:father(李四，李小四)and man(李小四)F=father(x,y)man(y)=李四/X,李小四/Y F=father(李四，李小四)man(李小四)结论:son(李小四,李四),代换的复合,定义4.2 设=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/xi当ti=xiui/yi当yix1,x2,xn后剩下的元素所构成的集合，记为。注：ti表示对ti运用进行代换。就是对一个公式F先运用进行代换，然后再运用进行代换：F（）=（F）,代换的例子,例如，设有代换=f(y)/x,z/w=a/x,b/y,w/z则=f(y)/x,z/w,a/x,b/y,w/z=f(b)/x,w/w,a/x,b/y,w/z=f(b)/x,b/y,w/z,公式集的合一,定义4.3 设有公式集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一个公式集的合一一般不唯一。,最一般的合一,定义4.4 设是公式集F的一个合一，如果对任一个合一都存在一个代换，使得=则称是一个最一般的合一。（1）代换过程是一个用项代替变元的过程，因此是一个从一般到特殊的过程。（2）最一般合一是唯一的。,求取最一般合一,差异集：两个公式中相同位置处不同符号的集合。例如：F1:P(x,y,z),F2:P(x,f(a),h(b)则D1=y,f(a),D2=z,h(b)求取最一般合一的算法：令k=0,Fk=F,k=。是空代换。若Fk只含一个表达式，则算法停止，k就是最一般合一。找出Fk的差异集Dk。若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出现，则置：Fk+1=Fktk/xkK+1=ktk/xkk=k+1然后转(2)。若不存在这样的xk和tk则算法停止。算法终止，F的最一般合一不存在。,求取最一般合一的例子,例如，设 F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一。令F0=F,0=。F0中有两个表达式，所以0不是最一般合一。差异集：D0=a,z。代换：a/zF1=F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u)。1=0a/z=a/zD1=x,f(a)。代换：f(a)/xF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u)。2=1f(a)/x=a/z,f(a)/x D2=g(y),u。代换：g(y)/uF3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y)。3=2g(y)/u=a/z,f(a)/x,g(y)/u,4.1.5 冲突消解策略,冲突：多个知识都匹配成功。正向推理：多条产生式前件都与已知事实匹配成功逆向推理：多条规则后件都和同一个假设匹配成功冲突消解的基本思想都是对知识进行排序。,几种冲突消解策略,按针对性排序优先选用针对性强的产生式规则。按已知事实的新鲜性排序优先选用与较多新事实匹配的规则。按匹配度排序在不确定性匹配中，计算两个知识模式的相似度(匹配度)，并对其排序，相似度高的规则先推。按领域问题特点排序按上下文限制排序把规则按照下上文分组，并只能选取组中的规则。按冗余限制排序冗余知识越少的规则先推。按条件个数排序条件少的规则先推。,4.2 自然演绎推理,从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程，称为自然演绎推理。其中，基本的推理规则是P规则、T规则、假言推理、拒取式推理等。假言推理的一般形式拒取式推理的一般形式,P规则：在推理的任何步骤都可以引入前提。T规则：推理时，如果前面步骤中有一个或者多个公式永真蕴含公式S，则可把S引入推理过程中。,4.3 归结演绎推理,定理证明即证明PQ(PQ)的永真性。根据反证法，只要证明其否定(PQ)不可满足性即可。海伯伦(Herbrand)定理为自动定理证明奠定了理论基础；鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。,4.3.1 子句,在谓词逻辑中，把原子谓词公式及其否定统称为文字。如：P(x)，P(x,f(x)，Q(x,g(x)定义4.5：任何文字的析取式称为子句。例如：P(x)Q(x),P(x,f(x)Q(x,g(x)定义4.6：不包含任何文字的子句称为空子句。,子句集,(1)合取范式：C1 C2 C3 Cn(2)子句集:S=C1,C2,C3,Cn(3)任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S。,把谓词公式化成子句集的步骤(1),1.利用等价关系消去“”和“”例如公式可等价变换成2.利用等价关系把“”移到紧靠谓词的位置上上式经等价变换后3.重新命名变元，使不同量词约束的变元有不同的名字上式经变换后,把谓词公式化成子句集的步骤(2),4.消去存在量词a.存在量词不出现在全称量词的辖域内，则只要用一个新的个体常量替换受该量词约束的变元。b.存在量词位于一个或者多个全称量词的辖域内，此时要用Skolem函数f(x1,x2,xn)替换受该存在量词约束的变元。上式中存在量词(y)及(z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后得到5.把全称量词全部移到公式的左边,把谓词公式化成子句集的步骤(3),6.利用等价关系把公式化为Skolem标准形Skolem标准形的一般形式是其中，M是子句的合取式，称为Skolem标准形的母式。上式化为Skolem标准形后得到7.消去全称量词8.对变元更名，使不同子句中的变元不同名上式化为9.消去合取词，就得到子句集,子句集的性质,（1）子句集中子句之间是合取关系。（2）子句集中的变元受全称量词的约束。,子句集的意义,子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。定理4.1 设有谓词公式F，其子句集为S，则F不可满足的充要条件是S不可满足。要证明PQ永真，只需证明公式F=(PQ)永假，即S不可满足。,4.3.2 Herbrand理论,为了判断子句集的不可满足性，需要对所有可能论域上的所有解释进行判定。只有当子句集对任何非空个体域上的任何一个解释都是不可满足的，才可断定该子句集是不可满足的。海伯伦构造了一个特殊的论域(海伯伦域)，并证明只要对这个特殊域上的一切解释进行判定，就可知子句集是否不可满足。,海伯伦域,定义4.7 设S为子句集，则按下述方法构造的域H称为海伯伦域，记为H域。(1)令H0是S中所有个体常量的集合，若S中不包含个体常量，则令H0a，其中a为任意指定的一个个体常量。(2)令Hi+1=HiS中所有n元函数f(x1,xn)|xj(j=1,n)是Hi中的元素，其中i=0,1,2,。例4.3 求子句集S=P(x)Q(x),R(f(y)的H域。解：此例中没有个体常量，任意指定一个常量a作为个体常量，得到H0=aH1=a,f(a)H2=a,f(a),f(f(a)H3=a,f(a),f(f(a),f(f(f(a)H=a,f(a),f(f(a),f(f(f(a),为研究子句集的永假性，引入H域上的原子谓词公式实例集A:A=所有出现于S中原子谓词公式的实例若原子公式是命题（不包含变量），则其实例就是其本身；若原子公式形如P(t1,t2,tm),ti是变量（i=1，2，m）,则其实例通过让ti=kiH(即H)来形成（i=1，2，m）。例如，对于上述例4.3，有：A=P(a),Q(f(a),Q(f(f(a),我们称A中的元素为基原子，进而A也称为基原子集。鉴于这些元素都是原子命题，只要给它们每个指派一个真值（T或F），就可建立子句集在H域上的一个解释，记为I*。就以基原子自身指示取真值T，前面加取反符号指示取真值F,则对于上述第一例，有 I*1=P(a),Q(f(a),Q(f(f(a),I*2=P(a),Q(f(a),Q(f(f(a),一个子句集的基原子有无限多个，它在H域上的解释也有无限多个。,在H域上进行解释的意义,意义：对于S任意可能论域D上的任意一个解释I，总存在H域上的一个解释I与它对应，且子句集在这两个解释下具有相同的真值。定理4.2 子句集S不可满足的充要条件是S对H域上一切解释都为假。,4.3.3 鲁滨逊归结原理,鲁滨逊归结原理的基本思想：检查子句集S中是否包含空子句。若包含，则S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句，就说明子句集S是不可满足的。子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。一旦S中包含空子句，则S必不可满足。,命题逻辑中的归结原理,定义4.9 若P是原子谓词公式，则称P与P为互补文字。在命题逻辑中，P为命题。定义4.10 设C1与C2是子句集中的任意两个子句。如果C1中的文字L1与C2中文字L2互补，那么从C1和C2中分别消去L1和L2，并将两个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结。称C12为C1和C2的归结式，C1和C2为C12的亲本子句。例4.9 设C1=PQ,C2=QR,C3=PC1与C2归结得到：C12=PRC12与C3归结得到：C123=R,定理4.4 C12是其亲本子句C1与C2的逻辑结论。证明：设C1=LC1,C2=LC2,则C12=C1C2,推论1 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即S1的不可满足性S的不可满足性推论2 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若把C12加入S中得到新子句集S2，则S与S2在不可满足的意义上是等价的，即S2的不可满足性S的不可满足性,推论1及推论2保证了我们可以用归结的方法来证明子句集S的不可满足性。为了要证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入子句集S，或者用归结式替换它的亲本子句，然后对新子句集(S1或者S2)证明不可满足性就可以了。如果经过归结能得到空子句，则立即可得原子句集S是不可满足的结论。在命题逻辑中，对不可满足的子句集S，归结原理是完备的。即，若子句集不可满足，则必然存在一个从S到空子句的归结演绎；若存在一个从S到空子句的归结演绎，则S一定是不可满足的。,谓词逻辑中的归结原理,在谓词逻辑中，由于子句中含有变元，所以不能像命题逻辑那样直接消去互补文字，而需要先用最一般合一对变元进行代换，然后才能进行归结。例如,设有两个子句C1=P(x)Q(x),C2=P(a)R(y)由于P(x)与P(a)不同，所以C1与C2不能直接进行归结。但是若用最一般合一=a/x对两个子句分别进行代换：C1=P(a)Q(a)C2=P(a)R(y)就可对它们进行归结，得到归结式：Q(a)R(y),二元归结式的定义,定义4.11 设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字。若是L1和L2的最一般合一，则称C12=(C1-L1)(C2-L2)为C1和C2的二元归结式，L1和L2称为归结式上的文字。例4.10 设C1=P(a)Q(x)R(x),C2=P(y)Q(b)若选L1=P(a),L2=P(y)，则有：L1=P(a),L2=P(y)，=a/y就是L1与L2的最一般合一。可得：C12=(C1-L1)(C2-L2)=Q(x)R(x)Q(b),若子句C含有可合一的文字，则在进行归结之前应先对这些文字进行合一。记其最一般的合一为，称C子句C的因子。C1=P(x)VP(f(a)VQ(x),C2=P(y)VR(b)=f(a)/x C1=P(f(a)VQ(f(a)C12=Q(f(a)VR(b),定义4.12 子句C1和C2的归结式是下列二元归结式之一：C1与C2的二元归结式；C1与C2的因子C22的二元归结式；C1的因子C11与C2的二元归结式；C1的因子C11与C2的因子C22的二元归结式。对于一阶谓词逻辑归结原理也是完备的。即，若子句集S不可满足，则必然存在一个从S到空子句的归结演绎；若存在一个从S到空子句的归结演绎，则S一定是不可满足的。,4.3.4 归结反演,如欲证明Q为P1,P2,Pn的逻辑结论，只需证(P1P2Pn)Q是不可满足的，或证明其子句集是不可满足的。而子句集的不可满足性可用归结原理来证明。应用归结原理证明定理的过程称为归结反演。设F为已知前提的公式集，Q为目标公式(结论)，用归结反演证明Q为真的步骤是：否定Q，得到Q；把Q并入到公式集F中，得到F,Q;把公式集F,Q化为子句集S；应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。,归结反演的例子,例4.12 已知求证：G是F的逻辑结论。证明：首先把F和G化为子句集：然后进行归结：(6)A(x,y)B(y)由(1)与(3)归结，f(x)/z(7)B(b)由(4)与(6)归结，a/x,b/y(8)NIL由(5)与(7)归结所以G是F的逻辑结论。上述归结过程如右图归结树所示。,假设：所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李明能看书且不贫穷，快乐的人过着激动人心的生活。求证：李明过着激动人心的生活。解：先定义谓词：Poor(x)x是贫穷的 Smart(x)x是聪明的 Happy(x)x是快乐的 Read(x)x能看书 Exciting(x)x过着激动人心的生活,问题谓词表示：“所有不贫穷并且聪明的人都是快乐的”(x)(Poor(x)Smart(x)Happy(x)“那些看书的人是聪明的”(y)(Read(y)Smart(y)“李明能看书且不贫穷”Read(Liming)Poor(Liming)“快乐的人过着激动人心的生活”(z)(Happy(z)Exciting(z)目标“李明过着激动人心的生活”的否定 Exciting(Liming),将上述谓词公式转化为子句集如下：(1)Poor(x)Smart(x)Happy(x)(2)Read(y)Smart(y)(3)Read(Liming)(4)Poor(Liming)(5)Happy(z)Exciting(z)(6)Exciting(Liming)(结论的否定),Exciting(Liming),Happy(z)Exciting(z),Happy(Liming),Happy(x)Smart(x)Happy(x),Poor(Liming)Smart(Liming),Read(y)Smart(y),Poor(Liming)Read(Liming),Poor(Liming),Read(Liming),Read(Liming),NIL,Liming/z,Liming/x,Liming/y,4.3.5 应用归结原理求取问题的答案,求解的步骤：把已知前提用谓词公式表示出来，并且化为相应的子句集。设该子句集的名字为S。把待求解的问题也用谓词公式表示出来，然后把它否定并与谓词Answer构成析取式。Answer是一个为了求解问题而专设的谓词。把此析取式化为子句集，并且把该子句集并入到子句集S中，得到子句集S。对S应用归结原理进行归结。若得到归结式Answer，则答案就在Answer中。,用归结原理求解问题的例子(1),例4.16 设A,B,C三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者？解：设用T(x)表示x说真话。T(C)T(A)T(B)T(C)T(A)T(B)T(A)T(B)T(C)T(A)T(B)T(C)T(B)T(A)T(C)T(B)T(A)T(C)T(C)T(A)T(B)T(C)T(A)T(B),用归结原理求解问题的例子(2),把上述公式化成子句集，得到S：(1)T(A)T(B)(2)T(A)T(C)(3)T(C)T(A)T(B)(4)T(B)T(C)(5)T(C)T(A)T(B)(6)T(A)T(C)(7)T(B)T(C)下面先求谁是老实人。把T(x)Ansewer(x)并入S得到S1。即多一个子句：(8)T(x)Ansewer(x)应用归结原理对S1进行归结：(9)T(A)T(C)(1)和(7)归结(10)T(C)(6)和(9)归结(11)Ansewer(C)(8)和(10)归结所以C是老实人，即C从不说假话。,(1)T(A)T(B)(2)T(A)T(C)(3)T(C)T(A)T(B)(4)T(B)T(C)(5)T(C)T(A)T(B)(6)T(A)T(C)(7)T(B)T(C)下面证明A不是老实人，即证明T(A)。对T(A)进行否定，并入S中，得到子句集S2，即S2比S多如下子句：(8)(T(A),即T(A)应用归结原理对S2进行归结：(9)T(A)T(C)(1)和(7)归结(10)T(A)(2)和(9)归结(11)NIL(8)和(10)归结所以A不是老实人。同样可以证明B也不是老实人。,归结时，并不要求把子句集中所有的子句都用到。在归结过程中，一个子句可以多次被用来进行归结。,4.3.6 归结策略,归结策略可分为两大类：一类是删除策略；删除某些无用的子句来缩小归结的范围。一类是限制策略。通过对参加归结的子句进行种种限制，尽可能减小归结的盲目性，使其尽快地归结出空子句。归结的一般过程设有子句集S=C1,C2,C3,C4，则对此子句集归结的一般过程是：S内任意子句两两逐一进行归结，得到一组归结式，称为第一级归结式，记为S1。把S与S1内的任意子句两两逐一进行归结，得到一组归结式，称为第二级归结式，记为S2。S和S1内的子句与S2内的任意子句两两逐一进行归结，得到一组归结式，称为第三级归结式，记为S3。如此继续，直到出现了空子句或者不能再继续归结为止。,一个归结的例子,例4.17 设有子句集S=P,R,PQ,QR。归结过程为：S:(1)P(2)R(3)PQ(4)QRS1:(5)Q(1)与(3)归结(6)Q(2)与(4)归结(7)PR(3)与(4)归结S2:(8)R(1)与(7)归结(9)P(2)与(7)归结(10)P(3)与(6)归结(11)R(4)与(5)归结S3:(12)NIL(1)与(9)归结,删除策略,纯文字删除法如果某文字L在子句集中不存在可与之互补的文字L，则称该文字为纯文字。包含纯文字的子句可以删除。重言式删除法如果一个子句中同时包含互补文字对，则该字句称为重言式。重言式是永远为真的子句，可以删除。,支持集策略,对参加归结的子句提出如下限制：每一次归结时，亲本子句中至少有一个是由目标公式的否定所得到的子句，或者是它的后裔。可以证明，支持集策略是完备的。例4.18 设有子句集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)归结(6)I(x)L(x)(1)与(3)归结S2:(7)L(a)(2)与(6)归结(8)L(a)(3)与(5)归结(9)I(a)(4)与(6)归结S3:(10)NIL(2)与(9)归结,支持集策略示例,线性输入策略,限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。线性输入策略可限制生成归结式的数量，具有简单、高效的优点。但是它是不完备的。,单文字子句策略,如果一个子句只包含一个文字，则称它为单文字子句。限制：参加归结的两个子句中必须至少有一个是单文字子句。用单文字子句策略归结时，归结式比亲本子句含有较少的文字，这有利于朝着空子句的方向前进，因此它有较高的归结效率。但是，这种归结策略是不完备的。当初始子句集中不包含单文字子句时，归结就无法进行。,祖先过滤策略,该策略与线性策略比较相似，但放宽了限制。当对两个子句C1和C2进行归结时，只要它们满足下述任一个条件就可以归结。C1和C2中至少有一个是初始子句集中的子句。C1和C2中一个是另外一个的祖先子句。祖先过滤策略是完备的。,优点：简单，便于在计算机上实现。缺点：必须把逻辑公式化成子句集。不便于阅读与理解。P(x)Q(x)没有P(x)Q(x)直观。可能丢失控制信息。下列逻辑公式：(AB)C A(BC)(AC)B B(AC)(CB)A C(BA)化成子句后都是:ABC,归结演绎推理的特点,4.4 与/或形演绎推理,归结演绎推理要求把有关问题的知识及目标的否定都化成子句形式，然后通过归结进行演绎推理，其推理规则只有一条，即归结规则；与/或形演绎推理不再把有关知识转化成子句集，而把领域知识及已知事实分别用蕴含式及与/或形表示出来，然后通过运用蕴含式进行演绎推理，从而证明某个目标公式。,基于规则的演绎推理,规则是一种比较接近于人们习惯的问题描述方式，用蕴含式（“If Then”规则）按照这种问题描述方式进行求解的系统称为基于规则的系统，或者叫做规则演绎系统。规则演绎系统按照推理方式可分为：规则正向演绎系统规则逆向演绎系统规则双向演绎系统,规则正向演绎系统,规则正向演绎系统是从已知事实出发，正向使用规则（蕴含式）直接进行演绎，直至到达目标为止。在规则正向演绎系统中，对已知事实和规则都有一定的要求，如果不是所要求的形式，需要进行变换。事实表达式的与或形变换在基于规则的正向演绎系统中，把事实表示为非蕴含形式的与或形，作为系统的总数据库把一个公式化为与或形的步骤与化为子句集类似，只是不必把公式化为子句的合取形式，也不能消去公式中的合取。,规则正向演绎系统,把事实表达式化为非蕴含形式的与/或形的步骤如下：(1)利用“PQPQ”，消去蕴含符号；(2)利用狄.摩根定律及量词转换率把“”移到紧靠谓词的位置，直到否定符号的辖域最多只含一个谓词为止；(3)重新命名变元，使不同量词约束的变元有不同的名字；(4)对存在量词量化的变量用skolem函数代替；(5)消去全称量词，且使各主要合取式中的变元具有不同的变量名。,规则正向演绎系统,例如：有如下表达式(x)(y)(Q(y,x)(R(y)P(y)S(x,y)可把它转化为：Q(z,a)(R(y)P(y)S(a,y)这就是与/或形表示。事实表达式的与/或形可用一棵与/或图表示出来。,规则正向演绎系统,Q(z,a)(R(y)P(y)S(a,y)的与/或图表示如下：,规则正向演绎系统,与/或形的与/或图表示当某表达式为k个子表达式的析取：E1E2Ek，其中的每个子表达式Ei均被表示为E1E2Ek的后继节点，并由一个k线连接符（即图中的半圆弧）将这些后继节点都连接到其父节点，即表示成与的关系。当某表达式为k个子表达式的合取：E1E2Ek，其中的每个子表达式Ei均被表示为E1E2Ek的一个单一的后继节点，无需用连接符连接，即表示成或的关系。这样，与/或图的根节点就是整个事实表达式，叶节点均为事实表达式中的一个文字。,规则正向演绎系统,与/或形的与/或图表示有了与/或图的表示，就可以求出其解树（结束于文字节点上的子树）集。可以发现，事实表达式的子句集与解树集之间存在着一一对应关系，即解树集中的每个解树都对应着子句集中的一个子句。解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。例如：上图所示的与/或图有3个解树，分别对应这以下3个子句：Q(z,a)R(y)S(a,y)P(y)S(a,y),规则正向演绎系统,规则的表示为简化演绎过程，通常要求规则具有如下形式：LW其中，L为单文字，W为与/或形公式。假定出现在蕴含式中的任何变量全都受全称量词的约束，并且这些变量已经被换名，使得他们与事实公式和其他规则中的变量不同。如果领域知识的规则表示形式与上述要求不同，则应将它转换成要求的形式。,规则正向演绎系统,将规则转换为要求形式的步骤：(1)暂时消去蕴含符号“”。设有如下公式：(x)(y)(z)P(x,y,z)(u)Q(x,u)运用等价关系“PQPQ”，可将上式变为：(x)(y)(z)P(x,y,z)(u)Q(x,u)(2)把否定符号“”移到紧靠谓词的位置上，使其作用域仅限于单个谓词。通过使用狄.摩根定律及量词转换率可把上式转换为：(x)(y)(z)P(x,y,z)(u)Q(x,u),规则正向演绎系统,(3)引入Skolem函数，消去存在量词。消去存在量词后，上式可变为：(x)(y)(P(x,y,f(x,y)(u)Q(x,u)(4)把所有全称量词移至前面化成前束式，消去全部全称量词。消去全称量词后，上式变为：P(x,y,f(x,y)Q(x,u)此公式中的变元都被视为受全称量词约束的变元。(5)恢复蕴含式表示。利用等价关系“PQPQ”将上式变为：P(x,y,f(x,y)Q(x,u),规则正向演绎系统,规则的表示在上述对规则的要求中，之所以限制其前件为单文字，是因为在进行正向演绎推理时要用规则作用于表示事实的与/或树，而该与/或树的叶节点都是单文字，这样就可用规则的前件与叶节点进行简单匹配。对非单文字情况，若形式为L1L2W，则可将其转换成与之等价的两个规则L1W与 L2W进行处理。目标公式的表示形式与/或树正向演绎系统要求目标公式用子句形表示。如果目标公式不是子句形，则需要化成子句形。,规则正向演绎系统,推理过程规则正向演绎推理过程是从已知事实出发，不断运用规则，推出欲证明目标公式的过程。先用与/或树把已知事实表示出来，然后再用规则的前件和与/或树的叶节点进行匹配，并通过一个匹配弧把匹配成功的规则加入到与/或树中，依此使用规则，直到产生一个含有以目标节点为终止节点的解树为止。下面分命题逻辑和谓词逻辑两种情况来讨论规则正向演绎过程。,规则正向演绎系统,命题逻辑的规则正向演绎过程已知事实：AB规则：r1:ACD r2:BEG目标公式：CG证明：1）先将已知事实用与/或树表示出来；2）然后再用匹配弧把r1和r2分别连接到事实与/或树中与r1和r2 的前件匹配的两个不同端节点；3)由于出现了以目标节点为终节点的解树，故推理过程结束。这一证明过程可用下图表示。,规则正向演绎系统,在该图中，双箭头表示匹配弧，它相当于一个单线连接符。,规则正向演绎系统,谓词逻辑的规则正向演绎过程已知事实的与/或形表示：P(x,y)(Q(z)R(v,y)规则：P(u,v)(S(u)N(v)目标公式：S(a)N(b)Q(c)证明：在谓词逻辑情况下，由于事实、规则及目标中均含有变元，因此，其规则演绎过程还需要用最一般合一对变进行置换。证明过程可用下图表示。,规则正向演绎系统,目标公式：S(a)N(b)Q(c),规则逆向演绎系统,规则逆向演绎推理过程：规则逆向演绎推理过程是从待证明的问题，即目标公式的与/或树出发，通过逆向地使用蕴含式（B规则），对目标公式的与/或树进行变换，直到得出包含已知事实的终止条件为止。规则逆向演绎系统目标公式的表示：与/或形变换，与/或树表示 B规则的表示形式已知事实的表示形式规则逆向演绎推理过程,目标公式的与/或形变换,在与/或形逆向演绎推理中，要求目标公式采用与/或形表示，其化简采用与正向系统中对事实表达式处理的对偶形式。转化步骤要用存在量词约束变元的Skolem函数来替换由全称量词约束的相应变元，消去全称量词。（隐含着变量受存在量词的约束）再消去存在量词，并进行变元换名，使主析取元之间具有不同的变元名。,目标公式的与/或形变换,例如，有如下目标公式：(y)(x)(P(x)(Q(x)(R(x)S(y)Skolem化后为 P(f(y)(Q(f(y),y)(R(f(y)S(y)变元换名后为 P(f(z)(Q(f(y),y)(R(f(y)S(y),目标公式的与/或树表示,目标公式的与/或形也可用与/或树表示出来，其表示方法与正向演绎推理中事实的与或树表示略有不同：子表达式之间的析取关系用单一连接符连接，表示为或的关系；子表达式之间的合取关系则用k线连接符连接，表示为与的关系。例如：对上述目标公式的与/或形，可用如下的与/或树表示。,目标公式的与/或树表示,若把叶节点用它们之间的合取及析取关系连接起来，就可得到原目标公式的三个子目标：,P(f(z)；Q(f(y),y)R(f(y)；Q(f(y),y)S(y),B规则的表示形式,B规则的表示形示形式 WL其中，前项W为任一与/或形公式，后项 L为一单文字。这里要求B规则的右边为文字，是因为推理时要用它与目标与或树中的叶节点进行匹配（合一），而目标与或树中的叶节点是文字。如果已知的B规则不是要求的形式，可用与转化F规则类似的方法把它转化为规定的形式。特别地，当B规则为WL1L2时，则可化件为两条规则WL1和WL2进行处理。,已知事实的表示形式,已知事实的表示形式反向演绎系统的事实表达式限制为文字合取形式，如：F1F2 Fn其中，每个Fi（i=1,2,n）都为单文字，且都可单独起作用，因此可表示为如下集合形式 F1，F2，Fn,规则逆向演绎推理过程,规则逆向演绎推理从目标公式的与/或树出发，通过运用B规则最终得到了某个终止在事实节点上的一致解图，推理就可成功结束推理过程1）首先用与/或树把目标公式表示出来；2）用B规则的右部和与/或树的叶节点进行匹配，并将匹配成功的B规则加入到与/或树中；3）重复进行步骤2，直到