资源预览内容
第1页 / 共50页
第2页 / 共50页
第3页 / 共50页
第4页 / 共50页
第5页 / 共50页
第6页 / 共50页
第7页 / 共50页
第8页 / 共50页
第9页 / 共50页
第10页 / 共50页
亲,该文档总共50页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第四章 谓词演算的推理理论,4.1 谓词演算的永真推理系统4.2谓词演算的假设推理系统4.3谓词演算的归结推理系统 4.3.1 置换 4.2.2 归结反演系统 4.3.3 霍恩子句逻辑程序,4.3 谓词演算的归结推理系统,问题:从公式集S出发,证明目标公式T。在归结系统中:首先否定目标公式,然后将这个公式加到公式集S中,再将该公式化成子句集,若能归结成空子句(用表示),则认为证明了该公式T。,引例(p45),设有语句串及它的符号表示如下:(1)无论谁能读就有知识;x(R(x) L(x)(2)所有的海豚均没有知识;x(H(x) L(x)(3)有些海豚有智慧。x(H(x)I(x)从这些语句出发,证明语句:(4)一些有智慧的个体不能读。x(I(x)R(x),引例 (p45,提取子句),对应语句(1)至(3)的子句集为:(1) R(x1) L(x1)(2) H(x2) L(x2)(3) H(a)(4) I(a)其中子句(3)(4)为对(3)式SKOLEM化而得,a为SKOLEM常量。要证明的定理的否定式为: x(I(x)R(x), 即 x(I(x)R(x)化为子句形式为(5):(5) I(x3)R(x3),引例 (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)要求没有变量被含有同一变量的项来代替。 如表达式P(x,g(x),b)中的x不能用含有x的项f(x)来置换,即P(f(x),g(f(x),b)是错误的置换。,例 已知表达式 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)消去全称量词(直接去掉)(7)化为合取范式(8)消去合取词得子句集,(9)改变变量的名称 (变量符号不重复使用),例(p46-47) 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),例 (p47),(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),二、一般归结,只需寻找一个置换,把它们作用到母体子句上使它们含有互补的文字对(如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,归结反演系统产生式系统,子句集看作为一个综合数据库,而规则表就是归结,表中的规则用到数据库中的子句对,产生一个新的子句,把新子句加入数据库中产生新的数据库,形成新的归结,重复此过程,观察数据库中是否含有空子句。,例 (p47)已知知识:,(1)每个作家均写过作品; (2)有些作家没写过小说;结论:有些作品不是小说。,证明:令 A(e)表示“e为作家”; B(e)表示“e为作品”; N(e)表示“e为小说”; W(e1,e2)表示“e1 写了 e2” 知识可以符号化如下: (1) x(A(x)y(B(y)W(x,y) (2) x(A(x)y(N(y)W(x,y),例 (p47, 求子句),(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),例 (p47,续),(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),例 (p47,续),要证明的结论为:有些作品不是小说。 x(B(x)N(x) 否定结论得到: x(B(x)N(x) = x(B(x)N(x) B(x)N(x) 得到子句: B(x)N(x),例 (p47, 归结),(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)归结,补充习题,任何人如果喜欢步行,他就不喜欢乘汽车;每个人或者喜欢乘汽车,或者喜欢骑自行车;有的人不喜欢骑自行车,因而有的人不爱步行。试用归结原理证明之。,证明:令 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)(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)归结,例 用归结方法证明下列公式,x(P(f(x)(P(f(a)P(x),证: 目标的否定为 x(P(f(x)(P(f(a) P(x) = x (P(f(x)(P(f(a) P(x) = x (P(f(x) ( P(f(a) P(x) 子句集为 (1) P(f(x1) (2) P(f(a) P(x2) (3) P(x2) a/x1 (1)(2)归结 (4)口 f(x1)/x2(1)(3)归结,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号