廉师友>作业二参考答案 1.(补充习题)判断以下公式对是否可合一,若可合一,则求出最一般的合一: (3)P(f(x),y),P(y,f(b)) 解:令σo=E,S0={P(f(x),y),P(y,f(b)}。 ①差异集为{f(x)y},做替换{f(x)/y},则 0,=oo off()/y=f(x)/yl S,=Sog,=P(f(),f(x)), Pcf(x),f(b)) 差异集为{x,b},做替换{b/x},则 σ2=1o{b/x}={f(b)/y,b/x} S,=so,=(P((b),f(b) 已经是单元集,所以原子句集可合一,且最一般合一为:{f(b)/y,b/x} (4) P((),y, x), P(x,f(a),f(b)) 解:令。=E,S={P(f(y),y,x),P(x,f(a),f(b)} ①差异集为{f(y),x},做替换{(y)/x},则 O1=0o{f(y)/x}={f(y)/x S,=soo,=(Pff(),y,f()), P(f(),f(a),f(b)) ②差异集为{y,f(a)},做替换{f(a)/y},则 0,=o,off(a)ly=ff(f(a)/x,f(a)/yi S2=Sa2={P(f(f(a),f(a),f((a)),P(f(f(a),f(a),f(b)} ③差异集为{f(a),b}。由于其中不存在变量,所以原子句集不可合 (5)P(x,y)P(y,x)
廉师友>作业二参考答案 1． （补充习题）判断以下公式对是否可合一，若可合一，则求出最一般的合一： （3） P( f (x), y), P( y, f (b)) 解：令 , { ( ( ), ), ( , ( ))} 0 = S0 = P f x y P y f b 。 ① 差异集为 { f (x), y} ，做替换 { f (x)/ y} ，则 { ( )/ } { ( )/ } 1 0 = f x y = f x y { ( ( ), ( )), ( ( ), ( ))} S1 = S0 1 = P f x f x P f x f b ② 差异集为 {x,b} ，做替换 {b / x} ，则 { / } { ( )/ , / } 2 1 = b x = f b y b x { ( ( ), ( ))} S2 = S1 2 = P f b f b 已经是单元集，所以原子句集可合一，且最一般合一为： { f (b)/ y,b / x} 。 （4） P( f ( y), y, x), P(x, f (a), f (b)) 解：令 , { ( ( ), , ), ( , ( ); ( ))} 0 = S0 = P f y y x P x f a f b 。 ① 差异集为 { f ( y), x} ，做替换 { f ( y)/ x} ，则 { ( )/ } { ( )/ } 1 0 = f y x = f y x { ( ( ), , ( )), ( ( ), ( ), ( ))} S1 = S0 1 = P f y y f y P f y f a f b ② 差异集为 {y, f (a)} ，做替换 { f (a)/ y} ，则 { ( )/ } { ( ( ))/ , ( )/ } 2 1 = f a y = f f a x f a y { ( ( ( )), ( ), ( ( ))), ( ( ( )), ( ), ( )} S2 = S1 2 = P f f a f a f f a P f f a f a f b ③ 差异集为 { f (a),b} 。由于其中不存在变量，所以原子句集不可合一。 （5） P(x, y), P( y, x)
解:令σ0=E,S0={P(x,y),P(y,x)}。 ①差异集为{x,y},做替换{y/x},则 0,=goofy/x)=y/x) S1=S0G1={P(y,y)} 已经是单元集,所以原子句集可合一,且最一般合一为:{y/x} 2.P86第6题 解:首先定义谓词 E(x)表示录取x 将题设的条件表示成谓词公式如下 E(AVE(B)VE(C) (2)E(A)∧-E(B)→>E(C) 而要证的结论为:E(C) 将题设和结论的否定化为子句集得 (1) E(A)VE(BVE(C) (2)E(AV E(B)VE(C) (3)=E(B)vE(C) (4)-E(C) 归结得 (5) E(B)VE(C) (1)(2) (6)E(C) (7)NIL (4)(6) 得 3.P86题7张某被盗公安局派出五个侦察员去调查研究案情时侦察员A说赵与钱至 少有一人做案”;侦察员B说”钱与孙至少有一人做案”;侦察员C说”孙与李至少有一人做 案”;侦察员D说赵与孙有一人与此案无关”;侦察员E说~钱与李有一人与此案无关”;如果
解：令 , { ( , ), ( , )} 0 0 = S = P x y P y x 。 ① 差异集为 {x, y} ，做替换 {y / x} ，则 { / } { / } 1 0 = y x = y x { ( , )} 1 0 1 S = S = P y y 已经是单元集，所以原子句集可合一，且最一般合一为： {y / x} 。 2． P86 第 6 题 解：首先定义谓词： E(x) 表示 录取 x 将题设的条件表示成谓词公式如下： （1） E(A) E(B) E(C) （2） E(A) E(B) → E(C) （3） E(B) → E(C) 而要证的结论为： E(C) 将题设和结论的否定化为子句集得： （1） E(A) E(B) E(C) （2） E(A) E(B) E(C) （3） E(B) E(C) （4） E(C) 归结得： （5） E(B) E(C) （1）（2） （6） E(C) （3）（5） （7）NIL （4）（6） 得证。 3．P86 题 7 张某被盗,公安局派出五个侦察员去调查.研究案情时,侦察员 A 说”赵与钱至 少有一人做案”; 侦察员 B 说”钱与孙至少有一人做案”; 侦察员 C 说”孙与李至少有一人做 案”; 侦察员 D说”赵与孙有一人与此案无关”; 侦察员 E说”钱与李有一人与此案无关”;如果
这五个侦察员的话都是可信的试用归结演绎推理求出谁是盗窃犯 解:首先定义谓词: (x)表示x作案 则已知的前提可以表示为 (1) F(Zhao)v F(oian) (2)F(Qian )v F(Sun) (3) F(Sun)V F(Li (4)F(Zhao)v-F(Sun) (5)F(Oian)V-F(Li) 待求解的问题为: (6)F(x)v Ans(x) 上面已经是子句集,直接进行归结: (7) Ans(Cian)v F(Zhao (1)(6){amn/x} (8)Ans(Or (4)(7) (9)Ans(Qian)v F(Cian (2)(8) (10)Ans( ian) (6)(9){Qimn/x 所以,Oamn是罪犯 另一方面,还可以进行如下归结: (11) Ans(Sun)v F(Cian) (2)(6){Sm/x} (12) Ans(Sun)V-F(Li) (5)(11) (13)Ans(Sun)v F(Sun) (3)(12) (14 )Ans(Sun) (6)(13){Sm/x} 所以,Sm也是罪犯 同时根据(4)和(5)可知:zhao和Li不是罪犯 4。P86第10题 答:线性归结策略的反例如下 S=PvO,PvO,PVnO
这五个侦察员的话都是可信的,试用归结演绎推理求出谁是盗窃犯. 解：首先定义谓词： F(x) 表示 x 作案 则已知的前提可以表示为： （1） F(Zhao) F(Qian) （2） F(Qian) F(Sun) （3） F(Sun) F(Li) （4） F(Zhao) F(Sun) （5） F(Qian) F(Li) 待求解的问题为： （6） F(x) Ans(x) 上面已经是子句集，直接进行归结： （7） Ans(Qian) F(Zhao) （1）（6） {Qian / x} （8） Ans(Qian) F(Sun) （4）（7） （9） Ans(Qian) F(Qian) （2）（8） （10） Ans(Qian) （6）（9） {Qian / x} 所以， Qian 是罪犯。 另一方面，还可以进行如下归结： （11） Ans(Sun) F(Qian) （2）（6） {Sun / x} （12） Ans(Sun) F(Li) （5）（11） （13） Ans(Sun) F(Sun) （3）（12） （14） Ans(Sun) （6）（13） {Sun / x} 所以， Sun 也是罪犯。 同时根据（4）和（5）可知： Zhao 和 Li 不是罪犯。 4。P86 第 10 题 答： 线性归结策略的反例如下： S = {P Q,P Q, P Q,P Q}
单文字子句归结策略的反例如下 (PvOPvO,PVO,PV-Q) (补充)设有子句集S={-P(x)vQ(xbP(a)y-Q(a,b),-Qa,(a),-P(y)vQy,y}分别 用每一种归结策略求出S的归结式 (1)=P(x)vQ(x,b) (2)P(a)v-Q(a,b) (3)-Q(a,f(a) (4)-P(y)vQ(y,y) 方法一:穷举法 (5)Q(a,b)y-Q(a,b)或P(a)y-P(a)(1)(2){a/x} (6)-P(b)vQ(b,b) (1)(4){b/y,b/x} (7)O(a, b)vo(a,a) (2)(4){a/y} 已无法继续进行归 方法二:删除策略 首先,原子句集中的(3)和(4)可以直接删除,因为(3)以及(4)中的Q(y,y)是 纯文字 其次进行第一次归结得 (5)Q(a,b)y-Q(a,b)或P(a)v-P(a)(1)(2){a/x} 但是(5)可以删除,因为它是重言式 归结结束。 方法三:支持集策略 这取决于所选择的目标子句 以下以(1)-P(x)vQ(x,b)作为目标子句的否定进行支持集归结 (5)Q(a,b)y-Q(a,b)或P(a)v-P(a)(1)(2){a/x} (6)-P(b)vQ(b,b) (1)(4){b/y,b/x}
单文字子句归结策略的反例如下： S = {P Q,P Q, P Q,P Q} （补充） 设有子句集:S={P(x) Q(x,b),P(a) Q(a,b), Q(a,f(a)), P(y) Q(y,y)}分别 用每一种归结策略求出 S 的归结式。 解： （1） P(x) Q(x,b) （2） P(a) Q(a,b) （3） Q(a, f (a)) （4） P( y) Q( y, y) 方法一：穷举法 S1: （5） Q(a,b) Q(a,b) 或 P(a) P(a) （1）（2） {a / x} （6） P(b) Q(b,b) （1）（4） {b / y,b / x} （7） Q(a,b) Q(a,a) （2）（4） {a / y} 已无法继续进行归结。 方法二：删除策略 首先，原子句集中的（3）和（4）可以直接删除，因为（3）以及（4）中的 Q( y, y) 是 纯文字。 其次进行第一次归结得 S1: （5） Q(a,b) Q(a,b) 或 P(a) P(a) （1）（2） {a / x} 但是（5）可以删除，因为它是重言式。 归结结束。 方法三：支持集策略 这取决于所选择的目标子句。 以下以（1） P(x) Q(x,b) 作为目标子句的否定进行支持集归结： S1: （5） Q(a,b) Q(a,b) 或 P(a) P(a) （1）（2） {a / x} （6） P(b) Q(b,b) （1）（4） {b / y,b / x}
已无法继续进行归结。 方法四:线性输入归结策略 得到的归结式和穷举法的相同。 方法五:单文字子句策略 不能得到任何归结式。 方法六:祖先过滤形策略 能够得到的归结式和穷举法的相同。 3.课本P53第1题: 答:运行结果是 在屏幕上显示出“ the x is a3” 4.课本P54第3题 答:在程序的 clauses段中增加子句: run:-path(X,Y,wite(X,"→”,Y),nl,fail run 并在goal段中以run为目标子句。 5.分析课本P51的例2.12程序的执行过程。 提示:关键是理解 Prolog中的递归和回溯机制 编写Prog程序计算累加和:f(m)=∑ 答:代码如下: predicates sum(integer, inte write("Please input an positive interger X=") readint(X) sum(X, R) write("The sum(0,0) Sum(X,Y): -X>0, XI=X-1, sum(Xl, Y1), Y=X+Yl
已无法继续进行归结。 方法四：线性输入归结策略 得到的归结式和穷举法的相同。 方法五：单文字子句策略 不能得到任何归结式。 方法六：祖先过滤形策略 能够得到的归结式和穷举法的相同。 3． 课本 P53 第 1 题： 答：运行结果是： 在屏幕上显示出“the x is a3”。 4． 课本 P54 第 3 题： 答：在程序的 clauses 段中增加子句： run :- path(X, Y), write(X, “➔”, Y), nl, fail. run. 并在 goal 段中以 run 为目标子句。 5． 分析课本 P51 的例 2.12 程序的执行过程。 提示：关键是理解 Prolog 中的递归和回溯机制。 6． 编写 Prolog 程序计算累加和： = = n i f n i 1 ( ) 答：代码如下： predicates sum(integer, integer) goal write(“Please input an positive interger X = “), readint(X), sum(X, R), nl, write(“The result is: “, R), clauses sum(0,0). Sum(X, Y) :- X>0, X1=X-1, sum(X1, Y1), Y=X+Y1