《离散数学第四章 谓词演算的推理理论-归结推理系统》由会员分享，可在线阅读，更多相关《离散数学第四章 谓词演算的推理理论-归结推理系统（50页珍藏版）》请在金锄头文库上搜索。
1、第四章 谓词演算的推理理论4.1 谓词演算的永真推理系统 4.2谓词演算的假设推理系统 4.3谓词演算的归结推理系统4.3.1 置换4.2.2 归结反演系统4.3.3 霍恩子句逻辑程序4.3 谓词演算的归结推理系统问题：从公式集S出发，证明目标公式T。在归结系统中: l 首先否定目标公式， l 然后将这个公式加到公式集S中， l 再将该公式化成子句集， l 若能归结成空子句(用表示)， 则认为证明了该公式T。引例(p45)设有语句串及它的符号表示如下： (1)无论谁能读就有知识；x(R(x) L(x) (2)所有的海豚均没有知识；x(H(x) L(x) (3)有些海豚有智慧。x(H(x)I(x
2、)从这些语句出发，证明语句： (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) (
3、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/yP(a，g(b)，b) a/x，b/y P(f(y)，g(a)，b) f(y)/x，a/
4、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(
5、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(
6、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/xQ(y) Q(x) x/zP(x，g(a)P(z，g(a) z/y 归结反演系统产生式系统l 子句集看作为一个综合数据库，l 而规则表就是归结，表中的规则用到数据库中的子句对，产生一个新的子句，把新子句加入数据库中产生新的数据库，形成新的归
7、结，重复此过程，观察数据库中是否含有空子句。 例 (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)
8、(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
9、(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)表示“
10、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
11、(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)归结直观解释: 显然，如果存在x, 使得P(f(x)为假，则公式为真。 反之，如果对于任意t, P(f(t)皆为真，则取x=f(t)即
12、可。三、归结反演算系统的应用在人工智能领域中的规划生成问题。例(p48)给机器人r 编制一程序，使它能够登 上一只椅子c以取下挂在房顶的香蕉b。4.3.3 霍恩子句逻辑程序一、子句的蕴含表示形式二、霍恩子句逻辑程序超逻辑的控制信息许多人工智能系统中使用的知识是由一般的蕴 含表达式来表示的。如果把蕴含式(PQ)R化为等价的析取式 P Q R ，往往会丢失可能包含在蕴含式中的重要的超逻 辑的控制信息。基于规则的演绎系统将知识分为两类：l一类是规则，其由蕴含式表示，它表达了有关领 域的一般知识，且可作为产生式规则来使用； l另一类是事实，其由不包含蕴含式的陈述组成， 它们用来表达某一领域专门的知识。基于规则的演绎系统(产生式系统)根据这些事 实和规则来证明目标公式，这种推理强调使用规则 进行演绎，直观易于理解。正向演绎系统、逆向演绎系统事实表达式目标表达式推理事实表达式目标表达式推理关于规则
