《谓词演算推理理论》PPT课件.ppt

《《谓词演算推理理论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《谓词演算推理理论》PPT课件.ppt（43页珍藏版）》请在三一办公上搜索。

1、第四章 谓词演算的推理理论,4.1 谓词演算的永真推理系统4.2谓词演算的假设推理系统4.3谓词演算的归结推理系统,4.3 谓词演算的归结推理系统,将前提集S化成子句集，将目标公式的否定(即B)化成子句集，归结若能归结出矛盾，则认为证明完成。,1，2，k B,前提公式集S,目标公式B,引例(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

2、，提取子句),(1)R(x1)L(x1)(2)H(x2)L(x2)(3)H(a)I(a)(5)I(x3)R(x3),前提：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，归结),(1)R(x1)L(x1)(2)H(x2)L(x2)(3)H(a)(4)I(a)(5)I(x3)R(x3)(6)R(a)a/x3(4)(5)归结(7)L(a)a/x1(6)(1)归结(8)H(a)a/x2(7)(2)归结(9)(8)(3)归结注意：归结时使用了未讨论过的置换的概念。,4.3.1 置换,置换项对变量的替换。(1)置换必须处

3、处进行。(2)要求没有变量被含有同一变量的项来代替。,x不能用f(x)替换,例 已知表达式 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,一般地，置换可通过有序对的集合t1/v1，t2/v2，tn/vn来表达，其中ti/vi表示变量vi处处以项ti来代替。,4.3.2 归结反演系统,一、谓词演算公式子句的形成二、一般归结三、归结反演系统,子句形成的一般步骤:,(1)消去蕴含词和等价词(2)否定深入(3)约束变元改名(4)化为前束范式(5)消去存在量词(按Skolem标准形)(6)消去全称

4、量词(直接去掉)(7)化为合取范式(8)消去合取词得子句集，(9)改变变量的名称(变量符号不重复使用),例 求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)化为前束范式 xzy(P(x)(A(z)(B(y)W(z，y)(4)消去存在量词(按Skolem标准形)原式z(P(a)(A(z)(B(f(z)W(z，f(z),(5)消去全称量词(直接去掉)原式 P(a)(A(z)(B(f(z)W(z，f(z)(6)利用分配律化为合取范式 原式 P(a)(A(

5、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(z1)B(f(z1),A(z2)W(z2，f(z2),关于改变变量名的说明:x(A(x)B(x)=xA(x)yB(y),互补文字对的归结,寻找一个置换使得子句上含有互补的文字对(如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，

6、An,B分别化为子句集；归结出空子句,即证明其不可满足。,第步等价于将A1A2AnB化为子句集,例(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(e1，e2)表示“e1 写了 e2”,求子句:每个作家均写过作品,(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

7、，f(x)A(x)(B(f(x)W(x，f(x)=(A(x)B(f(x)(A(x)W(x，f(x)得到子句：A(x1)B(f(x1)，A(x2)W(x2，f(x2),求子句:有些作家没写过小说,(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),求子句:有些作品不是小说,x(B(x)N(x)否定结论得到：x(B(x)N(x)=x(B(x)N(x)B(x)N(x)得到子句：B(x)N(x),(1)A(x1)B(f(x1)(

8、2)A(x2)W(x2，f(x2)(3)A(a)(4)N(y)W(a，y)(5)B(x)N(x)(6)A(x1)N(f(x1)f(x1)/x(5)(1)归结(7)N(f(a)a/x1(6)(3)归结(8)W(a，f(a)f(a)/y(7)(4)归结(9)A(a)a/x2(8)(2)归结(10)口(9)(3)归结,补充习题,任何人如果喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车，或者喜欢骑自行车；有的人不喜欢骑自行车，因而有的人不爱步行。试用归结原理证明之。,证明：令 P(e)表示“e为人”；W(e)表示“e喜欢步行”；D(e)表示“e喜欢乘汽车”；R(e)表示“e喜欢骑自行车”,证明(续)

9、,则已知知识可以翻译为：（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(x1)W(x1)D(x1)(2)P(x2)D(x2)R(x2)(3)P(a)(4)R(a)(5)P(x)W(x)(6)W(a)D(a)a/x1(3)(1)归结(7)P(a)D(a)a/x2(4)(2)归结(8)P(a)D(a)a/y(5)(6)归结(9)P(a)(8)(7)归结(10)口(9)(3)归结,4.3.3 霍恩子句逻辑程序,许多人工智能系统中使用的知识是由一般的蕴含表达式来表示的。如果把蕴含

10、式(PQ)R化为等价的析取式P Q R，往往会丢失可能包含在蕴含式中的重要的超逻辑的控制信息。,基于规则的演绎系统,知识：,规则一般知识，由蕴含式表示事实专门知识，由不包含蕴含式的陈述组成,基于规则的演绎系统根据事实和规则来证明目标公式,一、子句的蕴含表示形式,一个子句(析取式)：C=P1P2PnQ1Q2Qm可以表示为：(P1P2Pn)(Q1Q2Qm)简记为：P1，P2，Pn Q1，Q2，Qm,Q1，Q2，Qm P1，P2，Pn,子句的类型,Q1，Q2，Qm P1，P2，Pnm0,n0 P1，P2，Pnm0,n0Q1，Q2，Qm m0,n0口m=0,n 0,子句的归结,相同的文字出现在两边即可

11、以消除每次归结只能消除一对相同的文字,霍恩子句,定义：子句 L1L2Ln 中，如果至多只含有一个正文字，那么该子句称为霍恩子句。,霍恩子句PQ1Q2Qn可表为：,PQ1，Q2，Qn,霍恩子句的类型,P Q1，Q2，Qn n0 P 上式n=0 Q1，Q2，Qn n0口 上式n=0,过程事实目标停机语句,过程名过程调用，过程调用，过程调用,霍恩子句逻辑,由霍恩子句构成的一阶谓词演算系统,执行算法：由目标中的一个过程调用与事实或过程名匹配启动，当匹配成功后，形成新的目标。,两个霍恩子句的归结是一个霍恩子句。,霍恩子句逻辑,要证明定理 A1，A2，An B，只要：,将A1，A2，An,B分别化为霍恩子

12、句集；归结出空子句,即证明其不可满足。,第步等价于将A1A2AnB化为霍恩子句集,例 已知前提(1)TOM在何处，MARY在何处(2)MARY在何处，她的COMPUTER在何处(3)TOM在图书馆 试证“MARY的COMPUTER是在图书馆？”,解：霍恩子句为(1)At(MARY,x)At(TOM,x)过程(2)At(COMPUTER,y)At(MARY,y)过程(3)At(TOM,Library)事实(4)At(COMPUTER,Library)目标,解：霍恩子句逻辑程序为(1)At(MARY,x)At(TOM,x)过程(2)At(COMPUTER,y)At(MARY,y)过程(3)At(T

13、OM,Library)事实(4)At(COMPUTER,Library)目标(5)At(MARY,Library)Library/y(2)(4)匹配(6)At(TOM,Library)Library/x(1)(5)匹配(7)口(3)(6)匹配 此程序证明了MARY的COMPUTER在图书馆。,例 所有羊都吃草,所有死羊都不吃草.所以,所有死羊都不是羊.,解:知识翻译为 x(羊(x)吃草(x)x(死羊(x)吃草(x)x(死羊(x)羊(x),其否定为 x(死羊(x)羊(x)霍恩子句逻辑程序及执行过程如下：(1)吃草(x)羊(x)过程(2)死羊(x1),吃草(x1)目标(3)死羊(a)事实(4)羊(

14、a)事实(5)死羊(x),羊(x)x/x1(2)(1)归结(6)羊(a)a/x(5)(3)归结(7)口(6)(4)归结,例 已知知识：,(1)有些病人喜欢所有的医生；(2)所有的病人均不喜欢庸医；试证明结论：所有的医生均不是庸医。,x(P(x)y(D(y)L(x，y)x(P(x)y(Q(y)L(x，y)x(D(x)Q(x)证明：令P(e)表示“e为病人”；D(e)表示“e为医生”；Q(e)表示“e为庸医”；L(e1，e2)表示“e1喜欢e2”；,x(D(x)Q(x),霍恩子句逻辑程序及执行过程如下：(1)P(a)事实(2)L(a,y)D(y)过程(3)P(x1),Q(y1),L(x1,y1）目

15、标(4)D(b)事实(5)Q(b)事实(6)Q(y1),L(a，y1)a/x1(3)(1)归结(7)Q(y)，D(y)y/y1(6)(2)归结(8)Q(b)b/y(7)(4)归结(9)口(8)(5)归结,例(p50-51)已知知识：(1)桌子上的每一本书均是杰作；(2)写出杰作的人是天才；(3)某个不出名的人写了桌上某本书；结论：某个不出名的人是天才。,解：令 A(e)表示“e为桌上的书”；B(e)表示“e为杰作”；C(e)表示“e为天才”；D(e)表示“e出名”；P(e)表示“e为人”；W(e1，e2)表示“e1 写了 e2”.,例(p50-51)已知知识：(1)桌子上的每一本书均是杰作；(

16、2)写出杰作的人是天才；(3)某个不出名的人写了桌上某本书；结论：某个不出名的人是天才。,(1)x(A(x)B(x)(2)x(P(x)y(B(y)W(x,y)C(x)(3)x(P(x)D(x)y(A(y)W(x，y)x(P(x)D(x)C(x),(1)x(A(x)B(x)(2)x(P(x)y(B(y)W(x,y)C(x)=x y(P(x)B(y)W(x，y)C(x)(P(x)B(y)W(x，y)C(x)(3)x(P(x)D(x)y(A(y)W(x，y)=xy(P(x)A(y)D(x)W(x，y)P(a)A(b)D(a)W(a，b),否定结论得到 x(P(x)D(x)C(x)=x(P(x)D(x

17、)C(x),解：,(7)D(x3)P(x3)，C(x3)过程(8)P(a)，C(a)a/x3(5)(7)归结(9)C(a)(8)(3)归结(10)P(a),B(y),W(a，y)a/x2(9)(2)归结(11)B(y)，W(a，y)(10)(3)归结(12)A(y)，W(a，y)y/x1(11)(1)归结(13)W(a，b)b/y(12)(4)归结(14)口(13)(6)归结,(1)B(x1)A(x1)过程(2)C(x2)P(x2)，B(y)，W(x2，y)过程(3)P(a)事实(4)A(b)事实(5)D(a)目标(6)W(a，b)事实,例 已知知识如下：(1)每个程序员均写过程序；(2)病毒

18、是一种程序(3)有些程序员没写过病毒；结论：有些程序不是病毒。试用霍恩子句逻辑程序证明之。,证明：令 P(e)表示 e为程序员；A(e)表示 e为程序；B(e)表示 e为病毒；W(e1,e2)表示 e1写了 e2.,例 已知知识如下：(1)每个程序员均写过程序；(2)病毒是一种程序(3)有些程序员没写过病毒；结论：有些程序不是病毒。试用霍恩子句逻辑程序证明之。,（1）x(P(x)y(A(y)W(x,y)（2）x(B(x)A(x)（3）x(P(x)y(B(y)W(x,y)x(A(x)B(x),提取子句:（1）x(P(x)y(A(y)W(x,y)=x y(P(x)(A(y)W(x,y)x(P(x)

19、(A(y)W(x,f(x)P(x)(A(y)W(x,f(x)（2）x(B(x)A(x)（3）x(P(x)y(B(y)W(x,y)P(a)y(B(y)W(a,y)结论的否定为：x(A(x)B(x)=x(A(x)B(x),(1)A(f(x1)P(x1)过程(2)W(x2,f(x2)P(x2)过程(3)A(x3)B(x3)过程(4)P(a)事实(5)B(y),W(a,y)目标(6)B(x4)A(x4)过程(7)A(y),W(a,y)y/x4(5)(6)归结(8)P(x1),W(a,f(x1)f(x1)/y(7)(1)归结(9)W(a,f(a)a/x1(8)(4)归结(10)P(a)a/x2(9)(2)归结(11)口(4)(10)归结,