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 x(R(x)(R(x)L(x)L(x)x x(H(x)(H(x)L L(x)(x)x x(H(x)(H(x)I I(x)(x)x x(I(x)(I(x)R R(x)(x)其中：其中：R(x):x R(x):x能读；能读；L(x):xL(x):x有知识；有知识；H(x):x H(x):x是海豚；是海豚；I(x):xI(x):x有智慧有智慧引例(p45，提取子句)(1)R(x1)L(x1)(2)H(x2)L(x2)(3)H(a)(4)I(a)(5)I(x3)R(x3)
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，归结)(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)置换必须处处进行。置换必须处处进行。(2
4、)要求没有变量被含有同一变量的项来代替。要求没有变量被含有同一变量的项来代替。例例 已知表达式已知表达式 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表示变量表示变量vi处处以项处处以项ti来代替来代替。4.3.2 归结反演系统归结反演系统一、谓词演算公式子句的形成一、谓词演
5、算公式子句的形成二、一般归结一般归结三、归结反演系统三、归结反演系统子句形成的子句形成的一般步骤:(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(
6、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)(6)利用分配律化为合取范式利用分配律化为合取范式 原式原式 P(a)(A(z)B(f(z)(A(z)W(z，f(z)(7)消去合取词得子句集消去合取词得子句集 P(a),A(
7、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 归结反演系统要证明定理要证明定理
8、A1A1，A2A2，AnAn B B，只要：只要：将将 A1A1，A2A2，An,An,B B分别化为子句集；分别化为子句集；归结出空子句归结出空子句,即证明其不可满足。即证明其不可满足。第步等价于将第步等价于将A1A1 A2A2 AnAnB 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)表示表
9、示“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(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
10、 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)W(a，f(a)
11、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)结论为：结
12、论为：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 霍恩子句逻辑程序霍恩子句逻辑程序许多人工智能系统中使用的知识是由一般的许多人工智能系统中使用的知识是由一般的蕴蕴含表达式含表达式来表示的。来表示的。如果把蕴含式如果把蕴含式(
13、P Q)R化为等价的析取式化为等价的析取式 P Q R，往往会丢失可能包含在蕴含式中的重要的往往会丢失可能包含在蕴含式中的重要的超逻超逻辑的控制辑的控制信息。信息。基于规则的演绎系统知识：知识：l规则规则一般知识，由一般知识，由蕴含式蕴含式表示表示l事实事实专门知识，由不包含蕴含式的专门知识，由不包含蕴含式的陈述陈述组成组成基于规则的演绎系统基于规则的演绎系统根据事实和规则来证明目标公式根据事实和规则来证明目标公式一、子句的蕴含表示形式一个子句一个子句(析取式析取式)：C=C=P P1 1P P2 2 P Pn n Q Q1 1 Q Q2 2 Q Qm m可以表示为：可以表示为：(P(P1 1
14、 P P2 2 P Pn n)(Q(Q1 1 Q Q2 2 Q Qm m)简记为：简记为：P P1 1，P P2 2，P Pn n Q Q1 1，Q Q2 2，Q Qm mQ Q1 1，Q Q2 2，Q Qm m P P1 1，P P2 2，P Pn n子句的类型Q1，Q2，Qm P1，P2，Pnm m0,n0,n0 0 P1，P2，Pnm m0,n0,n0 0Q1，Q2，Qm m m0,n0,n0 0口口m=0,n 0子句的子句的归结归结子句子句1子句子句2归结式归结式PRQPQRP,QRQPQRP,QRP,QPP,RP,QRP,QQQ,RP,QRQ,RPRPP口口相同的文字出现在两边即可以
15、消除相同的文字出现在两边即可以消除每次归结只能消除一对相同的文字每次归结只能消除一对相同的文字霍恩子句 定义：子句定义：子句 L1 L2 Ln 中，如果至多只含有一个正文字，中，如果至多只含有一个正文字，那么该子句称为霍恩子句。那么该子句称为霍恩子句。霍恩子句霍恩子句PQ1Q2 Qn可表为：可表为：PQ1，Q2，Qn霍恩子句的类型霍恩子句的类型 P Q1，Q2，Qn n 0 P 上式上式n=0 Q1，Q2，Qn n 0口口 上式上式n=0过程过程事实事实目标目标停机语句停机语句过程名过程名过程调用，过程调用，过程调用，过程调用，过程调用，过程调用霍恩子句逻辑霍恩子句逻辑由由霍恩子句霍恩子句构成
16、的一阶谓词演算系统构成的一阶谓词演算系统执行算法：执行算法：由目标中的一个由目标中的一个过程调用过程调用与与事实事实或或过程名过程名匹匹配启动，当匹配成功后，形成新的目标。配启动，当匹配成功后，形成新的目标。两个霍恩子句的归结是一个霍恩子句。两个霍恩子句的归结是一个霍恩子句。霍恩子句逻辑霍恩子句逻辑要证明定理要证明定理 A1A1，A2A2，AnAn B B，只要：只要：将将A1A1，A2A2，An,An,B B分别化为分别化为霍恩霍恩子句子句集；集；归结出空子句归结出空子句,即证明其不可满足。即证明其不可满足。第步等价于将第步等价于将A1A1 A2A2 AnAnB B化为化为霍恩霍恩子句集子句
17、集例例 已知前提已知前提 (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(C
18、OMPUTER,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
19、)x(死羊死羊(x)羊羊(x),其否定为其否定为 x(死羊死羊(x)羊羊(x)霍恩子句逻辑程序及执行过程如下：霍恩子句逻辑程序及执行过程如下：(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)所有的病人均不喜欢庸医；所有的病人均不喜欢庸医；试证明结论：所有的医生均不是庸医。试证明
20、结论：所有的医生均不是庸医。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）目标目标(4)D(b)事实事实(5)Q(b)事实事实(6)Q(y1),L(a，y1)a/x1(3)(1)归结归结(7)Q(y
21、)，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)表示表示“e
22、1 写了写了 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(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
23、)(3)x(P(x)D(x)y(A(y)W(x，y)=x y(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)C(a)a/x3(5)(7)a/x3(5)(7)归结归结(9)(9)C(a)C(a)(8)(3)(8)(3)归结归结(10)(10)P(a),B(y),W(a P(a),B(y),W(a，y)y)
24、a/x2(9)(2)a/x2(9)(2)归结归结(11)(11)B(y)B(y)，W(aW(a，y)y)(10)(3)(10)(3)归结归结(12)(12)A(y)A(y)，W(aW(a，y)y)y/x1(11)(1)y/x1(11)(1)归结归结(13)(13)W(a W(a，b)b)b/y(12)(4)b/y(12)(4)归结归结(14)(14)口口 (13)(6)(13)(6)归结归结(1)B(x1)(1)B(x1)A A(x1)(x1)过程过程(2)C(x2)(2)C(x2)P P(x2)(x2)，B(y)B(y)，W(x2W(x2，y)y)过程过程(3)P(a)(3)P(a)事实事实
25、(4)A(b)(4)A(b)事实事实(5)(5)D D(a)(a)目标目标(6)W(a(6)W(a，b)b)事实事实例例 已知知识如下：已知知识如下：(1)每个程序员均写过程序；每个程序员均写过程序；(2)病毒是一种程序病毒是一种程序 (3)有些程序员没写过病毒；有些程序员没写过病毒；结论：有些程序不是病毒。结论：有些程序不是病毒。试用霍恩子句逻辑程序证明之。试用霍恩子句逻辑程序证明之。证明：证明：令令 P(e)表示表示 e为程序员；为程序员；A(e)表示表示 e为程序；为程序；B(e)表示表示 e为病毒；为病毒；W(e1,e2)表示表示 e1写了写了 e2.例例 已知知识如下：已知知识如下：
26、(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)（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)归结归结
