《四章节谓词演算推理理论.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
2、): x是海豚； I(x): x有智慧,引例 (p45，提取子句),(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(
3、7)(2)归结 (9) (8)(3)归结 注意：归结时使用了未讨论过的置换的概念。,4.3.1 置换,置换项对变量的替换。 (1)置换必须处处进行。 (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 归结反演系统,一、谓词演算公式子句的形成 二、一般归结 三、归结反演
4、系统,子句形成的一般步骤:,(1)消去蕴含词和等价词 (2)否定深入 (3)约束变元改名 (4)化为前束范式 (5)消去存在量词(按Skolem标准形) (6)消去全称量词(直接去掉) (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标准形) 原式
5、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(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
6、(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分别化为子句集； 归结出空子句,即证明其不可满足。,第步等价于将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为
7、作品”； 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，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
8、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) (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
9、) 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喜欢骑自行车”,证明(续),则已知知识可以翻译为： （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
10、) ) 结论的否定为： 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 霍恩子句逻辑程序,许多人工智能系统中使用的知识是由一般的蕴含表达式来表示的。 如果把蕴含式 (PQ)R 化为等价的析取式 P Q R ， 往往会丢失可能包含在蕴
11、含式中的重要的超逻辑的控制信息。,基于规则的演绎系统,知识：,规则一般知识，由蕴含式表示 事实专门知识，由不包含蕴含式的陈述组成,基于规则的演绎系统 根据事实和规则来证明目标公式,一、子句的蕴含表示形式,一个子句(析取式)： C = P1P2PnQ1Q2Qm 可以表示为： (P1P2Pn)(Q1Q2Qm) 简记为： P1，P2，Pn Q1，Q2，Qm,Q1，Q2，Qm P1，P2，Pn,子句的类型,Q1，Q2，Qm P1，P2，Pn m0,n0 P1，P2，Pn m0,n0 Q1，Q2，Qm m0,n0 口 m=0, n 0,子句的归结,相同的文字出现在两边即可以消除 每次归结只能消除一对相同
12、的文字,霍恩子句,定义：子句 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分别化为霍恩子句集； 归结出
13、空子句,即证明其不可满足。,第步等价于将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(COMPUTE
14、R,y) At(MARY,y) 过程 (3) At(TOM, 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) 霍恩子句逻辑
15、程序及执行过程如下： (1) 吃草(x)羊(x) 过程 (2) 死羊(x1), 吃草(x1) 目标 (3) 死羊(a) 事实 (4) 羊(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
16、，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） 目标 (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)某个不出名的人写了桌上某本书； 结论：某个不出
17、名的人是天才。,解：令 A(e)表示“e为桌上的书”； B(e)表示“e为杰作”； C(e)表示“e为天才”； D(e)表示“e出名”； P(e)表示“e为人”； W(e1，e2)表示“e1 写了 e2”.,例 (p50-51) 已知知识： (1)桌子上的每一本书均是杰作； (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
18、 (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) 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
19、)归结 (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)病毒是一种程序 (3)有些程序员没写过病毒； 结论：有些程序不是病毒。 试用霍恩子句逻辑程序证明之。,证明： 令 P(e)表示 e为程序员； A
20、(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) (A(y) W(x,f(x) P(x) (A(y) W(x,f(x)
21、 （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)归结,