单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章 谓词演算的推理理论,4.1,谓词演算的永真推理系统,4.2,谓词演算的假设推理系统,4.3,谓词演算的归结推理系统,第四章 谓词演算的推理理论4.1 谓词演算的永真推理系统,4.3,谓词演算的归结推理系统,将前提集,S,化成子句集，,将目标公式的否定,(,即,B),化成子句集，,归结,若能归结出矛盾，则认为证明完成。,1,，,2,，,，,k B,前提公式集,S,目标公式,B,4.3 谓词演算的归结推理系统将前提集S化成子句集，1，,引例,(p45),已知：,(1),无论谁能读就有知识；,(2),所有的海豚均没有知识；,(3),有些海豚有智慧。,试证明：,(4),一些有智慧的个体不能读。,x,(R(x),L(x),x,(H(x),L,(x),x,(H(x),I,(x),x,(I(x),R,(x),其中：,R(x):x,能读；,L(x):x,有知识；,H(x):x,是海豚；,I(x):x,有智慧,引例(p45)已知：(1)无论谁能读就有知识；x(R,引例,(p45,，提取子句,),(1),R,(x,1,),L(x,1,),(2),H,(x,2,),L,(x,2,),(3)H(a),I(a),(5),I,(x,3,),R,(x,3,),前提：,x,(R(x),L(x),x,(H(x),L,(x),x,(H(x),I,(x),结论的否定,x,(I(x),R,(x),=,x,(,I,(x),R,(x),引例(p45，提取子句)前提：=x(I(x)R(x),引例,(p45,，归结,),(1),R,(x,1,),L(x,1,),(2),H,(x,2,),L,(x,2,),(3)H(a),(4)I(a),(5),I,(x,3,),R,(x,3,),(6)R(a),a/x,3,(4)(5),归结,(7)L(a),a/x,1,(6)(1),归结,(8),H,(a),a/x,2,(7)(2),归结,(9),(8)(3),归结,注意：归结时使用了未讨论过的,置换,的概念。,引例(p45，归结)(1)R(x1)L(x1),4.3.1,置换,置换,项对变量的替换。,(1),置换必须处处进行。,(2),要求没有变量被含有同一变量的项来代替。,例 已知表达式,P,(,x,),P,(f(x),x,不能用,f(x),替换,4.3.1 置换置换项对变量的替换。例 已知表达式,例 已知表达式,P,(,x,，,g,(,y,),，,b,),，考察置换,:,P,(,x,，,g,(,a,),，,b,),a/y,P,(,a,，,g,(,b,),，,b,),a/x,，,b/y,P,(,f,(,y,),，,g,(,a,),，,b,),f,(,y,),/x,，,a/y,一般地，置换可通过有序对的集合,t,1,/v,1,，,t,2,/v,2,，,，,t,n,/v,n,来表达，其中,t,i,/v,i,表示变量,v,i,处处以项,t,i,来代替,。,例 已知表达式 P(x，g(y)，b)，考察置换:,4.3.2,归结反演系统,一、谓词演算公式子句的形成,二、,一般归结,三、归结反演系统,4.3.2 归结反演系统一、谓词演算公式子句的形成,子句形成的,一般步骤,:,(1),消去蕴含词和等价词,(2),否定深入,(3),约束变元改名,(4),化为前束范式,(5),消去存在量词,(,按,Skolem,标准形,),(6),消去全称量词,(,直接去掉,),(7),化为合取范式,(8),消去合取词得子句集,，,(9),改变变量的名称,(,变量符号不重复使用,),子句形成的一般步骤:(1)消去蕴含词和等价词,例,求,xP,(,x,),x,(,A,(,x,),y,(,B,(,y,),W,(,x,，,y,),的子句,解,:,(1),消去蕴含词,xP,(,x,),x,(,A,(,x,),y,(,B,(,y,),W,(,x,，,y,),(2),约束变元改名,：,xP,(,x,),z,(,A,(,z,),y,(,B,(,y,),W,(,z,，,y,),(3),化为前束范式,x,z,y,(,P,(,x,),(,A,(,z,),(,B,(,y,),W,(,z,，,y,),(4),消去存在量词,(,按,Skolem,标准形,),原式,z(,P(a),(,A,(z),(,B(f(z),W,(z,，,f(z),例 求xP(x)x(A(x)y(B(y)W(x，,(,5),消去全称量词,(,直接去掉,),原式,P(a),(,A,(z),(,B(f(z),W,(z,，,f(z),(,6),利用分配律化为合取范式,原式,P,(,a,),(,A,(,z,),B,(,f,(,z,),(,A,(,z,),W,(,z,，,f,(,z,),(7),消去合取词得子句集,P(a),A,(z),B,(f(z),A,(z),W,(z,，,f(z),(8),改变变量的名称,：,P(a),A,(z,1,),B,(f(z,1,),A,(z,2,),W,(z,2,，,f(z,2,),关于改变变量名的说明,:,x(A(x)B(x)=xA(x)yB(y),(5)消去全称量词(直接去掉)关于改变变量名的说明:,互补文字对的归结,寻找一个置换使得子句上含有互补的文字对,(,如,P,和,P),。,例,设有两个子句,P,(,x,，,g,(,a,),Q,(,y,),P,(,z,，,g,(,a,),Q,(,z,),可得若干归结式如下：,Q,(,y,),Q,(,z,),z/x,Q,(,y,),Q,(x),x/z,P,(,x,，,g,(,a,),P,(,z,，,g,(,a,),z/y,互补文字对的归结寻找一个置换使得子句上含有互补的文字对例,归结反演系统,要证明定理,A1,，,A2,，,，,An,B,，,只要：,将,A1,，,A2,，,，,An,B,分别化为子句集；,归结出空子句,即证明其不可满足。,第步等价于将,A1,A2,An,B,化为子句集,归结反演系统要证明定理将 A1，A2，An,B分别,例,(p47),已知知识：,(1),每个作家均写过作品；,(2),有些作家没写过小说；,结论：有些作品不是小说。,x,(,A,(,x,),y,(,B,(,y,),W,(,x,，,y,),x,(,A,(,x,),y,(,N,(,y,),W,(,x,，,y,),x,(,B,(,x,),N,(,x,),证明：令,A,(,e,),表示“,e,为作家”；,B,(,e,),表示“,e,为作品”；,N,(,e,),表示“,e,为小说”；,W,(,e,1,，,e,2),表示“,e,1,写了,e,2”,例(p47)已知知识：(1)每个作家均写过作品；,求子句,:,每个作家均写过作品,(1),x,(A(x),y,(,B(y),W,(x,，,y),),),=,x(,A(x),y(,B(y),W,(x,，,y),=,x,y(,A(x)(B(y),W,(x,，,y),x(,A(x)(B(f(x),W,(x,，,f(x),A(x)(B(f(x),W,(x,，,f(x),=(A(x)B(f(x)(A(x),W,(x,，,f(x),得到子句：,A(x,1,)B(f(x,1,),，,A(x,2,)W(x,2,，,f(x,2,),求子句:每个作家均写过作品 (1)x(,求子句,:,有些作家没写过小说,(2),x,(,A,(,x,),y,(,N,(,y,),W,(,x,，,y,),=,x,(,A,(,x,),y,(,N,(,y,),W,(,x,，,y,),=,x,y,(,A,(,x,),(,N,(,y,),W,(,x,，,y,),y,(,A,(a),(,N,(,y,),W,(a,，,y,),A,(a),(,N,(,y,),W,(a,，,y,),得到子句：,A,(a),N,(,y,),W,(a,，,y,),求子句:有些作家没写过小说(2)x(A(x)y(N,求子句,:,有些作品不是小说,x,(,B,(,x,),N,(,x,),否定结论得到：,x,(,B,(,x,),N,(,x,),=,x,(,B,(,x,),N,(,x,),B,(,x,),N,(,x,),得到子句：,B,(,x,),N,(,x,),求子句:有些作品不是小说 x(B(x)N(x),(1),A,(,x,1,),B,(,f,(,x,1,),(2),A,(,x,2,),W,(,x,2,，,f,(,x,2,),(3),A,(,a,),(4),N,(,y,),W,(,a,，,y,),(5),B,(,x,),N,(,x,),(6),A,(,x,1,),N,(,f,(,x,1,),f,(,x,1,)/,x,(5)(1),归结,(7),N,(,f,(,a,),a,/,x,1,(6)(3),归结,(8),W,(,a,，,f,(,a,),f,(,a,)/,y,(7)(4),归结,(9),A,(,a,),a,/,x,2,(8)(2),归结,(10),口,(9)(3),归结,(1)A(x1)B(f(x1),补充习题,任何人如果喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车，或者喜欢骑自行车；有的人不喜欢骑自行车，因而有的人不爱步行。试用归结原理证明之。,证明：令,P(e),表示“,e,为人”；,W(e),表示“,e,喜欢步行”；,D(e),表示“,e,喜欢乘汽车”；,R(e),表示“,e,喜欢骑自行车”,补充习题任何人如果喜欢步行，他就不喜欢乘汽车；每个人或者喜欢,证明,(,续,),则已知知识可以翻译为：,（,1,）,x(P(x),(,W(x),D,(x),),),（,2,）,x(P(x),(,D(x),R,(x),),),（,3,）,x(P(x),R,(x),结论为：,x(P(x),W(x),),结论的否定为：,x(,P(x)W(x),),证明(续)则已知知识可以翻译为：,(1),P,(,x,1,),W,(x,1,)D(x1),(2)P(,x,2,)D(x,2,)R(x,2,),(3),P,(,a,),(4)R(a),(5)P(,x,)W(,x,),(6)W(,a,)D(a),a,/,x,1,(3)(1),归结,(7),P(a)D(a),a,/,x,2,(4)(2),归结,(8)P(a)D(a),a,/,y,(5)(6),归结,(9),P,(,a,),(8)(7),归结,(10),口,(9)(3),归结,(1)P(x1)W(x1)D(x1),4.3.3,霍恩子句逻辑程序,许多人工智能系统中使用的知识是由一般的,蕴含表达式,来表示的。,如果把蕴含式,(P,Q),R,化为等价的析取式,P,Q,R,，,往往会丢失可能包含在蕴含式中的重要的,超逻辑的控制,信息。,4.3.3 霍恩子句逻辑程序许多人工智能系统中使用的知识是由,基于规则的演绎系统,知识：,规则,一般知识，由,蕴含式,表示,事实,专门知识，由不包含蕴含式的,陈述,组成,基于规则的演绎系统,根据事实和规则来证明目标公式,基于规则的演绎系统知识：规则一般知识，由蕴含式表示基于规,一、子句的蕴含表示形式,一个子句,(,析取式,),：,C=,P,1,P,2,P,n,Q,1,Q,2,Q,m,可以表示为：,(P,1,P,2,P,n,),(Q,1,Q,2,Q,m,),简记为：,P,1,，,P,2,，,，,P,n,Q,1,，,Q,2,，,，,Q,m,Q,1,，,Q,2,，,，,Q,m,P,1,，,P,2,，,，,P,n,一、子句的蕴含表示形式一个子句(析取式)：Q1，Q2，Q,子句的类型,Q,1,，,Q,2,，,，,Q,m,P,1,，,P,2,，,，,P,n,m,0,n,0,P,1,，,P,2,，,，,P,n,m,0,n,0,Q,1,，,Q,2,，,，,Q,m,m,0,n,0,口,m=0,n,0,子句的类型Q1，Q2，Qm P1，P2，Pn,子句的,归结,