四章节谓词演算推理理论ppt课件

1、第四章 谓词演算的推理实际4.1 谓词演算的永真推理系统谓词演算的永真推理系统4.2谓词演算的假设推理系统谓词演算的假设推理系统4.3谓词演算的归结推理系统谓词演算的归结推理系统4.3 谓词演算的归结推理系统谓词演算的归结推理系统l 将前提集将前提集S化成子句集，化成子句集，l 将目的公式的否认将目的公式的否认(即即 B)化成子句集，化成子句集，l 归结归结l 假设能归结出矛盾，那么以为证明完成。假设能归结出矛盾，那么以为证明完成。 1， 2， ， k B前提公式集前提公式集S目的公式目的公式B引例(p45) 知：(1)(1)无论谁能读就有知识；无论谁能读就有知识；(2)(2)一切的海豚均没有

2、知识；一切的海豚均没有知识；(3)(3)有些海豚有智慧。有些海豚有智慧。试证明：试证明：(4)(4)一些有智慧的个体不能读。一些有智慧的个体不能读。 x(R(x)x(R(x) L(x) L(x) x(H(x)x(H(x)L(x)L(x) x(H(x)x(H(x) I(x)I(x) x(I(x)x(I(x)R(x)R(x)其中：其中： R(x): x R(x): x能读；能读； L(x): x L(x): x有知识；有知识； H(x): x H(x): x是海豚；是海豚； I(x): x I(x): x有智慧有智慧引例 (p45，提取子句)(1) R(x1) L(x1)(2) H(x2) L(x

3、2)(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、念。4.3.1 置换置换置换置换项对变量的交换。项对变量的交换。(1)置换必需处处进展。置换必需处处进展。(2)要求没有变量被含有同一变量的项来替代。要求没有变量被含有同一变量的项来替代。 例例 知表达式知表达式 P(x) P(f(x)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表示变量表示

5、变量vi处处以项处处以项ti来替代。来替代。4.3.2 归结反演系统归结反演系统一、谓词演算公式子句的构成一、谓词演算公式子句的构成二、普通归结二、普通归结三、归结反演系统三、归结反演系统子句构成的普通步骤子句构成的普通步骤:(1)消去蕴含词和等价词消去蕴含词和等价词(2)否认深化否认深化(3)约束变元改名约束变元改名(4)化为前束范式化为前束范式(5)消去存在量词消去存在量词(按按Skolem规范形规范形)(6)消去全称量词消去全称量词(直接去掉直接去掉)(7)化为合取范式化为合取范式(8)消去合取词得子句集，消去合取词得子句集，(9)改动变量的称号改动变量的称号 (变量符号不反复运用变量符

6、号不反复运用)例例 求求 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)(5)消去全称量词消去全称量词(直接去掉直接去掉) 原式原式 P(a) ( A(z) (B(f(z) W(z，f(z)(

7、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) 。例例 设有两个子句设有两个子

8、句 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 A1，A2A2，An BAn B，只需：只需：将将 A1 A1，A2A2，An, An, B B分别化为子句集；分别化为子句集；归结出空子句归结出空子句, ,即证明其不可满足。即证明其不可满足。第步等价于将第步等价于将A1A2AnB化为子句集化为子句集例例 (p47)知知识：知知识： (1)每个作家均写过作品；每个作家均写过作品； (2)有些作家没写过小说

9、；有些作家没写过小说；结论：有些作品不是小说。结论：有些作品不是小说。 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，f(x) A

10、(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) 否认结论得到

11、：否认结论得到： 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) W(a，f(a) f(a)/y (7)(4)归结归结 (9) A(a) a/x2 (8)(2)归结归结(10) 口口 (9)(3)归结归结补充习题任何人假设喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车，

12、或者喜欢骑自行车；有的人不喜欢骑自行车，因此有的人不爱步行。试用归结原理证明之。证明：令证明：令 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(x1)W(x1) D(x1)(2) P(x2)D(x2) R(x2)

13、(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 ，往往会丧失能够包含在蕴含式中的重要的超逻往往会丧失能够包含

14、在蕴含式中的重要的超逻辑的控制信息。辑的控制信息。基于规那么的演绎系统知识：知识：l规那么规那么普通知识，由蕴含式表示普通知识，由蕴含式表示l现实现实专门知识，由不包含蕴含式的陈说组成专门知识，由不包含蕴含式的陈说组成基于规那么的演绎系统基于规那么的演绎系统根据现实和规那么来证明目的公式根据现实和规那么来证明目的公式一、子句的蕴含表示方式一个子句一个子句( (析取式析取式) )： C = C = P1P1P2P2PnPnQ1Q1Q2Q2QmQm可以表示为：可以表示为： (P1 (P1P2P2Pn)Pn)(Q1(Q1Q2Q2Qm)Qm)简记为：简记为：P1P1，P2P2，PnPn Q1 Q1，Q

15、2Q2，QmQmQ1Q1，Q2Q2，Qm Qm P1 P1，P2P2，PnPn子句的类型Q1，Q2，Qm P1，P2，Pnm0,n0 P1，P2，Pnm0,n0Q1，Q2，Qm m0,n0口口m=0, n 0子句的归结子句的归结子句子句1子句子句2归结式归结式PRQPQRP, QRQPQRP, QRP,QPP,RP, QRP,QQQ,RP, QRQ,RPRPP口口一样的文字出如今两边即可以消除一样的文字出如今两边即可以消除每次归结只能消除一对一样的文字每次归结只能消除一对一样的文字霍恩子句 定义：子句定义：子句 L1L2Ln 中，假设至多只含有一个正文字，中，假设至多只含有一个正文字， 那么该

16、子句称为霍恩子句。那么该子句称为霍恩子句。 霍恩子句霍恩子句PQ1Q2Qn可表为：可表为：PQ1，Q2，Qn霍恩子句的类型霍恩子句的类型 P Q1，Q2，Qn n 0 P 上式上式n=0 Q1，Q2，Qn n 0口口 上式上式n=0过程过程现实现实目的目的停机语句停机语句过程名过程名过程调用，过程调用，过程调用，过程调用，过程调用，过程调用霍恩子句逻辑霍恩子句逻辑由霍恩子句构成的一阶谓词演算系统由霍恩子句构成的一阶谓词演算系统执行算法：执行算法：由目的中的一个过程调用与现实或过程名匹由目的中的一个过程调用与现实或过程名匹配启动，当匹配胜利后，构成新的目的。配启动，当匹配胜利后，构成新的目的。两

17、个霍恩子句的归结是一个霍恩子句。两个霍恩子句的归结是一个霍恩子句。霍恩子句逻辑霍恩子句逻辑要证明定理要证明定理 A1 A1，A2A2，An BAn B，只需：只需：将将A1A1，A2A2，An, An, B B分别化为霍恩子分别化为霍恩子句集；句集；归结出空子句归结出空子句, ,即证明其不可满足。即证明其不可满足。第步等价于将第步等价于将A1A2AnB化为霍恩子化为霍恩子句集句集例例 知前提知前提 (1) TOM在何处，在何处， MARY在何处在何处 (2) MARY在何处，她的在何处，她的COMPUTER在何处在何处 (3) TOM在图书馆在图书馆 试证试证“MARY的的COMPUTER是在

18、图书馆？是在图书馆？ 解：霍恩子句为解：霍恩子句为 (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(TOM, Library) 现实现实 (4) At(COMPUTER, Library) 目的目的 (5) At(M

19、ARY, 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)羊羊

20、(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)证明：证明：

21、令令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 目目的的(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

22、) 口口 (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) 知知识：知知识： (

23、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 (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

24、 (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)x(P(x) D(x)D(x) C(x) C(x) = = x ( x ( P(x) P(x) D(x) D(x) C(x) C(x)解：解：(7)D(x3)(7)D(x3) P(x3) P(x3)，C(x3) C(x3) 过程过程 (8)(8) P(a) P(a)，C(a) a/x3(5)(7)C(a) a/x3(5)(7)归结归结(9)(9) C(a) (8)(3) C(a) (8)(3)归结归结(10)(1

25、0) P(a),B(y), W(a P(a),B(y), W(a，y) a/x2(9)(2)y) a/x2(9)(2)归结归结(11)(11) B(y) B(y)， W(a W(a，y) (10)(3)y) (10)(3)归结归结(12)(12) A(y) A(y)，W(aW(a，y) y/x1(11)(1)y) y/x1(11)(1)归结归结(13)(13) W(a W(a，b) b/y(12)(4)b) b/y(12)(4)归结归结(14)(14)口口 (13)(6) (13)(6)归结归结(1)B(x1)(1)B(x1)A(x1) A(x1) 过程过程(2)C(x2)(2)C(x2) P(x2) P(x2)，B(y)B(y)， W(x2 W(x2，y) y) 过程过程(3)P(a)(3)P(a) 现实现实(4)A(b)(4)A(b) 现实现实(5)(5) D(a) D(a) 目的目的(6)W(a(6)W(a，b)b) 现实现实例例 知知识如下：知知识如下： (1)每个程序员均写过程序；每个程序员均写过程序； (2)病