《第三讲经典逻辑推理课件.ppt》由会员分享，可在线阅读，更多相关《第三讲经典逻辑推理课件.ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三讲经典逻辑推理第1页，此课件共65页哦4.1 基本概念4.1.1 什么是推理什么是推理所谓推理就是按某种策略由已知判断推所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。出另一个判断的思维过程。在人工智能中，推理是由程序实现的，在人工智能中，推理是由程序实现的，称为推理机。称为推理机。第2页，此课件共65页哦4.1.2 推理方式及其分类1.演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理演绎推理：从一般到特殊。例如三段论。演绎推理：从一般到特殊。例如三段论。归纳推理：从个体到一般。归纳推理：从个体到一般。默认推理：缺省推理，在知识不完全的情况下假设某些条默认推理：缺省推理，
2、在知识不完全的情况下假设某些条件已经具备所进行的推理。件已经具备所进行的推理。2.确定性、不确定性推理确定性、不确定性推理3.单调推理、非单调推理单调推理、非单调推理推出的结论是否单调增加推出的结论是否单调增加4.启发式、非启发式推理启发式、非启发式推理所谓启发性知识是指与问题有关且能加快推理进程、求得所谓启发性知识是指与问题有关且能加快推理进程、求得问题最优解的知识。问题最优解的知识。5.基于知识的推理（专家系统）基于知识的推理（专家系统）、统计推理、直觉推理（常识性推、统计推理、直觉推理（常识性推理）理）第3页，此课件共65页哦4.1.3 推理的控制策略推理的控制策略主要包括：推理方向、搜
3、索策略、冲突消推理的控制策略主要包括：推理方向、搜索策略、冲突消解策略、求解策略及限制策略。解策略、求解策略及限制策略。1.正向推理（数据驱动推理）正向推理（数据驱动推理）正向推理的基本思想是：从用户提供的初始已知事实出发，正向推理的基本思想是：从用户提供的初始已知事实出发，在知识库在知识库KB中找出当前可适用的知识，构成可适用的知识中找出当前可适用的知识，构成可适用的知识集集KS，然后按某种冲突消解策略从，然后按某种冲突消解策略从KS中选出一条知识进行推中选出一条知识进行推理，并将推出的新事实加入到数据库理，并将推出的新事实加入到数据库DB中，作为下一步推中，作为下一步推理的已知事实。在此之
4、后，再在知识库中选取可适用的知理的已知事实。在此之后，再在知识库中选取可适用的知识进行推理。如此重复进行这一过程，直到求得所要求的识进行推理。如此重复进行这一过程，直到求得所要求的解。解。第4页，此课件共65页哦正向推理示意图第5页，此课件共65页哦2 逆向推理逆向推理的基本思想是：首先选定一个逆向推理的基本思想是：首先选定一个假设目标，然后寻找支持该假设的证据，假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则是成立的；若找不到所需要的证据，则说明原假设不成立，此时需要另作新的说明原假设不成立，此时需要另
5、作新的假设。假设。第6页，此课件共65页哦逆向推理示意图第7页，此课件共65页哦 动物识别的例子已知事实：一动物已知事实：一动物有毛，吃草，黑条纹有毛，吃草，黑条纹nR1：动物有毛：动物有毛 哺乳类哺乳类 nR2：动物产奶：动物产奶 哺乳类哺乳类 nR3：哺乳类：哺乳类 吃肉吃肉 食肉类食肉类 nR4：哺乳类：哺乳类 吃草吃草 有蹄类有蹄类 nR5：食肉类：食肉类 黄褐色黄褐色 有斑点有斑点 猎狗猎狗 nR6：食肉类：食肉类 黄褐色黄褐色 黑条纹黑条纹 虎虎 nR7：有蹄类：有蹄类 长脖长脖 长颈鹿长颈鹿 nR8：有蹄类：有蹄类 黑条纹黑条纹 斑马斑马第8页，此课件共65页哦3.混合推理混合推
6、理先正向推理后逆向推理先正向推理后逆向推理先逆向推理后正向推理先逆向推理后正向推理4.双向推理双向推理正向推理与逆向推理同时进行，且在推理过程中正向推理与逆向推理同时进行，且在推理过程中的某一步上的某一步上“碰头碰头”。5.求解策略求解策略只求一个解，还是求所有解以及最优解。只求一个解，还是求所有解以及最优解。6.限制策略限制策略限制搜索的深度、宽度、时间、空间等等。限制搜索的深度、宽度、时间、空间等等。第9页，此课件共65页哦所谓模式匹配是指对两个知识模式所谓模式匹配是指对两个知识模式(例如两个谓词公式、例如两个谓词公式、框架片断、语义网络片断框架片断、语义网络片断)进行比较，检查这两个知识
7、模式进行比较，检查这两个知识模式是否完全一致或者近似一致。是否完全一致或者近似一致。模式匹配可分为确定性匹配与不确定性匹配。模式匹配可分为确定性匹配与不确定性匹配。确定性匹配是指两个知识模式完全一致，或者经过变量代换后确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。变得完全一致。知识：知识：IF father(x,y)and man(y)THEN son(y,x)事实：事实：father(李四，李小四李四，李小四)and man(李小四李小四)不确定性匹配是指两个知识模式不完全一致，但是它不确定性匹配是指两个知识模式不完全一致，但是它们的相似程度又在规定的限度内。们的相似程
8、度又在规定的限度内。4.1.4 模式匹配第10页，此课件共65页哦变量代换定义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是代换第11页，此课件共65页哦令=t1/x1,t2/x2,tn/xn为一个代换，F为表达式，则F表示对F用ti代换xi后得到的表达式。F称为F的特例。规则:IF
9、 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(李小四,李四)第12页，此课件共65页哦代换的复合定义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后剩下的元素所构成
10、的集合，记为。注：ti表示对ti运用进行代换。就是对一个公式F先运用进行代换，然后再运用进行代换：F（）=（F）第13页，此课件共65页哦代换的例子例如，设有代换=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第14页，此课件共65页哦公式集的合一定义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
11、,g(a)/y,f(g(a)/z一个公式集的合一一般不唯一。第15页，此课件共65页哦 最一般的合一定义4.4 设是公式集F的一个合一，如果对任一个合一都存在一个代换，使得=则称是一个最一般的合一。（1）代换过程是一个用项代替变元的过程，因此是一个从一般到特殊的过程。（2）最一般合一是唯一的。第16页，此课件共65页哦求取最一般合一差异集：两个公式中相同位置处不同符号的集合。例如：F1:P(x,y,z),F2:P(x,f(a),h(b)则D1=y,f(a),D2=z,h(b)求取最一般合一的算法：1.令k=0,Fk=F,k=。是空代换。2.若Fk只含一个表达式，则算法停止，k就是最一般合一。3
12、.找出Fk的差异集Dk。4.若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出现，则置：Fk+1=Fktk/xkK+1=ktk/xkk=k+1然后转(2)。若不存在这样的xk和tk则算法停止。5.算法终止，F的最一般合一不存在。第17页，此课件共65页哦求取最一般合一的例子例如，设 F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一。1.令F0=F,0=。F0中有两个表达式，所以0不是最一般合一。2.差异集：D0=a,z。代换：a/z3.F1=F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u)。1=0a/z=a/zD1=x,f(a)。代
13、换：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)/u1.F3=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 第18页，此课件共65页哦4.1.5 冲突消解策略冲突：多个知识都匹配成功。正向推理：n多条产生式前件都与已知事实匹配成功逆向推理：n多条规则后件都和同一个假设匹配成功冲突消解的基本思想都是对知识进行排序。第19页，此课件共65页哦几种冲突消解策略1.按针对性排序优先选用
14、针对性强的产生式规则。2.按已知事实的新鲜性排序优先选用与较多新事实匹配的规则。3.按匹配度排序在不确定性匹配中，计算两个知识模式的相似度(匹配度)，并对其排序，相似度高的规则先推。4.按领域问题特点排序5.按上下文限制排序把规则按照下上文分组，并只能选取组中的规则。6.按冗余限制排序冗余知识越少的规则先推。7.按条件个数排序条件少的规则先推。第20页，此课件共65页哦4.2 自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程，称为自然演绎推理。其中，基本的推理规则是P规则、T规则、假言推理、拒取式推理等。假言推理的一般形式拒取式推理的一般形式第21页，此课件共65
15、页哦P规则：在推理的任何步骤都可以引入前提。T规则：推理时，如果前面步骤中有一个或者多个公式永真蕴含公式S，则可把S引入推理过程中。第22页，此课件共65页哦4.3 归结演绎推理定理证明即证明PQ(PQ)的永真性。根据反证法，只要证明其否定(PQ)不可满足性即可。海伯伦(Herbrand)定理为自动定理证明奠定了理论基础；鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。第23页，此课件共65页哦4.3.1 子句w在谓词逻辑中，把原子谓词公式及其否定统称为文字。如：P(x)，P(x,f(x)，Q(x,g(x)定义4.5：任何文字的析取式称为子句。例如：P(x)Q(x),P(x,f
16、(x)Q(x,g(x)定义4.6：不包含任何文字的子句称为空子句。第24页，此课件共65页哦 子句集(1)合取范式：C1 C2 C3 Cn(2)子句集:S=C1,C2,C3,Cn(3)任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S。第25页，此课件共65页哦把谓词公式化成子句集的步骤(1)1.利用等价关系消去“”和“”例如公式可等价变换成2.利用等价关系把“”移到紧靠谓词的位置上上式经等价变换后3.重新命名变元，使不同量词约束的变元有不同的名字上式经变换后第26页，此课件共65页哦把谓词公式化成子句集的步骤(2)4.消去存在量词a.存在量词不出现在全称量词的辖域内，则只要用一个新的
17、个体常量替换受该量词约束的变元。b.存在量词位于一个或者多个全称量词的辖域内，此时要用Skolem函数f(x1,x2,xn)替换受该存在量词约束的变元。上式中存在量词(y)及(z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后得到5.把全称量词全部移到公式的左边第27页，此课件共65页哦把谓词公式化成子句集的步骤(3)6.利用等价关系把公式化为Skolem标准形Skolem标准形的一般形式是其中，M是子句的合取式，称为Skolem标准形的母式。上式化为Skolem标准形后得到7.消去全称量词8.对变元更名，使不同子句中的变
18、元不同名上式化为9.消去合取词，就得到子句集第28页，此课件共65页哦 子句集的性质（1）子句集中子句之间是合取关系。（2）子句集中的变元受全称量词的约束。第29页，此课件共65页哦 子句集的意义子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。定理4.1 设有谓词公式F，其子句集为S，则F不可满足的充要条件是S不可满足。要证明PQ永真，只需证明公式F=(PQ)永假，即S不可满足。第30页，此课件共65页哦4.3.2 Herbrand理论为了判断子句集的不可满足性，需要对所有可能论域上的所有解释进行判定。只有当子句集对任何非空个体域上的任何一个解释都是不可满足的
19、，才可断定该子句集是不可满足的。海伯伦构造了一个特殊的论域(海伯伦域)，并证明只要对这个特殊域上的一切解释进行判定，就可知子句集是否不可满足。第31页，此课件共65页哦海伯伦域定义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
20、,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),第32页，此课件共65页哦为研究子句集的永假性，引入H域上的原子谓词公式实例集A:A=所有出现于S中原子谓词公式的实例n若原子公式是命题（不包含变量），则其实例就是其本身；n若原子公式形如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),第33页，此课件共65页哦我们称A中的元素为基原子，进而A也称为基原子集。鉴于这些
21、元素都是原子命题，只要给它们每个指派一个真值（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域上的解释也有域上的解释也有无限多个。无限多个。第34页，此课件共65页哦在H域上进行解释的意义意义：对于S任意可能论域D上的任意一个解释I，总存在H域上的一个解释I与它对应，且子句集在这两个解释下具有相同的真值。定理4.2 子句集S不可满足的充要条件
22、是S对H域上一切解释都为假。第35页，此课件共65页哦4.3.3 鲁滨逊归结原理 鲁滨逊归结原理的基本思想：检查子句集S中是否包含空子句。若包含，则S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句，就说明子句集S是不可满足的。子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。一旦S中包含空子句，则S必不可满足。第36页，此课件共65页哦命题逻辑中的归结原理定义4.9 若P是原子谓词公式，则称P与P为互补文字。在命题逻辑中，P为命题。定义4.10 设C1与C2是子句集中的任意两个子句。如果C1中的文字L1与C2中文字L2互补，那么
23、从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第37页，此课件共65页哦定理4.4 C12是其亲本子句C1与C2的逻辑结论。证明：设C1=LC1,C2=LC2,则C12=C1C2第38页，此课件共65页哦推论1 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即S1
24、的不可满足性S的不可满足性推论2 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若把C12加入S中得到新子句集S2，则S与S2在不可满足的意义上是等价的，即S2的不可满足性S的不可满足性第39页，此课件共65页哦推论1及推论2保证了我们可以用归结的方法来证明子句集S的不可满足性。为了要证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入子句集S，或者用归结式替换它的亲本子句，然后对新子句集(S1或者S2)证明不可满足性就可以了。如果经过归结能得到空子句，则立即可得原子句集S是不可满足的结论。在命题逻辑中，对不可满足的子句集S，归结原理是完备的。即，若子句集不
25、可满足，则必然存在一个从S到空子句的归结演绎；若存在一个从S到空子句的归结演绎，则S一定是不可满足的。第40页，此课件共65页哦谓词逻辑中的归结原理在谓词逻辑中，由于子句中含有变元，所以不能像命题逻辑那样直接消去互补文字，而需要先用最一般合一对变元进行代换，然后才能进行归结。例如,设有两个子句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)第41页，此课件共65页哦二元归结式的定义定义4.11 设
26、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)第42页，此课件共65页哦若子句C含有可合一的文字，则在进行归结之前应先对这些文字进行合一。记其最一般的合一为，称C子句C的因子。C1=P(x)VP(f(a)
27、VQ(x),C2=P(y)VR(b)=f(a)/x C1=P(f(a)VQ(f(a)C12=Q(f(a)VR(b)第43页，此课件共65页哦定义4.12 子句C1和C2的归结式是下列二元归结式之一：1.C1与C2的二元归结式；2.C1与C2的因子C22的二元归结式；3.C1的因子C11与C2的二元归结式；4.C1的因子C11与C2的因子C22的二元归结式。对于一阶谓词逻辑归结原理也是完备的。即，若子句集S不可满足，则必然存在一个从S到空子句的归结演绎；若存在一个从S到空子句的归结演绎，则S一定是不可满足的。第44页，此课件共65页哦4.3.4 归结反演如欲证明Q为P1,P2,Pn的逻辑结论，只
28、需证(P1P2Pn)Q是不可满足的，或证明其子句集是不可满足的。而子句集的不可满足性可用归结原理来证明。应用归结原理证明定理的过程称为归结反演。设F为已知前提的公式集，Q为目标公式(结论)，用归结反演证明Q为真的步骤是：1.否定Q，得到Q；2.把Q并入到公式集F中，得到F,Q;3.把公式集F,Q化为子句集S；4.应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。第45页，此课件共65页哦归结反演的例子例4.12 已知求证：G是F的逻辑结论。证明：首先把F和G化为子句集：然后进行归结：(6)A(x,y)B(y
29、)由(1)与(3)归结，f(x)/z(7)B(b)由(4)与(6)归结，a/x,b/y(8)NIL由(5)与(7)归结所以G是F的逻辑结论。上述归结过程如右图归结树所示。A(x,y)B(y)C(f(x)A(x,y)B(y)B(b)NILC(z)A(a,b)B(b)第46页，此课件共65页哦4.3.5 应用归结原理求取问题的答案求解的步骤：1.把已知前提用谓词公式表示出来，并且化为相应的子句集。设该子句集的名字为S。2.把待求解的问题也用谓词公式表示出来，然后把它否定并与谓词Answer构成析取式。Answer是一个为了求解问题而专设的谓词。3.把此析取式化为子句集，并且把该子句集并入到子句集S
30、中，得到子句集S。4.对S应用归结原理进行归结。5.若得到归结式Answer，则答案就在Answer中。第47页，此课件共65页哦用归结原理求解问题的例子(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
31、)T(B)第48页，此课件共65页哦用归结原理求解问题的例子(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从不说假话。第49页，此课件共65页哦(1)T(A
32、)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也不是老实人。第50页，此课件共65页哦练习:1.设已知：设已知：（1）如果）如果x是是y的父亲，的父亲，y是是z的父亲，则的父亲，则x是是
33、z的祖父；的祖父；（2）每个人都有一个父亲。）每个人都有一个父亲。试用归结演绎推理证明：对于某人试用归结演绎推理证明：对于某人u，一，一定存在一个人定存在一个人v，v是是u的祖父。的祖父。第51页，此课件共65页哦2.张某被盗，公安局派出五个侦察员去调查。张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员研究案情时，侦察员 A 说说“赵与钱中至少有赵与钱中至少有一人作案一人作案”；侦察员；侦察员 B 说说“钱与孙中至少有一钱与孙中至少有一人作案人作案”；侦察员；侦察员 C 说说“孙与李中至少有一人孙与李中至少有一人作案作案”；侦察员；侦察员 D 说说“赵与孙中至少有一人赵与孙中至少有一人
34、与此案无关与此案无关”；侦察员；侦察员 E 说说“钱与李中至少钱与李中至少有一人与此案无关有一人与此案无关”。如果这五个侦察员的。如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁话都是可信的，试用归结演绎推理求出谁是盗窃犯。是盗窃犯。第52页，此课件共65页哦归结时，并不要求把子句集中所有的子句都用到。在归结过程中，一个子句可以多次被用来进行归结。第53页，此课件共65页哦4.3.6 归结策略归结策略可分为两大类：一类是删除策略；删除某些无用的子句来缩小归结的范围。一类是限制策略。通过对参加归结的子句进行种种限制，尽可能减小归结的盲目性，使其尽快地归结出空子句。归结的一般过程设有子句集S
35、=C1,C2,C3,C4，则对此子句集归结的一般过程是：1.S内任意子句两两逐一进行归结，得到一组归结式，称为第一级归结式，记为S1。2.把S与S1内的任意子句两两逐一进行归结，得到一组归结式，称为第二级归结式，记为S2。3.S和S1内的子句与S2内的任意子句两两逐一进行归结，得到一组归结式，称为第三级归结式，记为S3。4.如此继续，直到出现了空子句或者不能再继续归结为止。第54页，此课件共65页哦一个归结的例子例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)归
36、结S2:(8)R(1)与(7)归结(9)P(2)与(7)归结(10)P(3)与(6)归结(11)R(4)与(5)归结S3:(12)NIL (1)与(9)归结第55页，此课件共65页哦删除策略纯文字删除法如果某文字L在子句集中不存在可与之互补的文字L，则称该文字为纯文字。包含纯文字的子句可以删除。重言式删除法如果一个子句中同时包含互补文字对，则该字句称为重言式。重言式是永远为真的子句，可以删除。第56页，此课件共65页哦支持集策略对参加归结的子句提出如下限制：每一次归结时，亲本子句中至少有一个是由目标公式的否定所得到的子句，或者是它的后裔。可以证明，支持集策略是完备的。例4.18 设有子句集S=
37、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)归结第57页，此课件共65页哦支持集策略示例I(x)R(x)I(a)R(y)L(y)L(a)R(a)L(a)I(x)L(x)L(a)I(a)NIL12345678910第58页，
38、此课件共65页哦线性输入策略限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。线性输入策略可限制生成归结式的数量，具有简单、高效的优点。但是它是不完备的。I(x)R(x)I(a)R(y)L(y)L(a)R(a)L(a)I(x)L(x)L(a)I(a)NIL123456981112R(a)I(a)710第59页，此课件共65页哦单文字子句策略如果一个子句只包含一个文字，则称它为单文字子句。限制：参加归结的两个子句中必须至少有一个是单文字子句。用单文字子句策略归结时，归结式比亲本子句含有较少的文字，这有利于朝着空子句的方向前进，因此它有较高的归结效率。但是，这种归结策略是不完备的。当初
39、始子句集中不包含单文字子句时，归结就无法进行。第60页，此课件共65页哦祖先过滤策略该策略与线性策略比较相似，但放宽了限制。当对两个子句C1和C2进行归结时，只要它们满足下述任一个条件就可以归结。1.C1和C2中至少有一个是初始子句集中的子句。2.C1和C2中一个是另外一个的祖先子句。祖先过滤策略是完备的。第61页，此课件共65页哦优点：简单，便于在计算机上实现。缺点：必须把逻辑公式化成子句集。不便于阅读与理解。P(x)Q(x)没有P(x)Q(x)直观。可能丢失控制信息。下列逻辑公式：(AB)C A(BC)(AC)B B(AC)(CB)A C(BA)化成子句后都是:ABC归结演绎推理的特点第6
40、2页，此课件共65页哦4.4 与/或形演绎推理归结演绎推理要求把有关问题的知识及目标的否定都化成子句形式，然后通过归结进行演绎推理，其推理规则只有一条，即归结规则；与/或形演绎推理不再把有关知识转化成子句集，而把领域知识及已知事实分别用蕴含式及与/或形表示出来，然后通过运用蕴含式进行演绎推理，从而证明某个目标公式。第63页，此课件共65页哦与/或形演绎推理的特点优点：不必把公式化为子句集，保留了连接词“”。这就可直观地表达出因果关系，比较自然。缺点：对正向演绎推理而言，目标表达式被限制为文字的析取式；对逆向演绎推理，已知事实的表达式被限制为文字的合取式；正、逆双向演绎推理虽然可以克服以上两个问题，但其“接头”的处理却比较困难。第64页，此课件共65页哦完谢谢第65页，此课件共65页哦