廉师友>作业一参考答案 1.已知前提:(1)如果x与y是同班同学,则x的老师也是y的老师;(2)小李和小张是 同班同学;(3)王先生是小李的老师,运用自然演绎推理证明:王先生也是小张的老师。 证明:首先定义谓词: Teacherx, y) x是y的老师 Classmates(x, y) x和y是同班同学 则已知的前提可以符号化为: (1) Vx'VyV=Teacher(x, y)A Classmates(, =)-> Teacher(x, =)) (2) Teacher(Wang, Xiaoli) 3)Classmates( Xiaoli, Xiaozhang) 要证的结论为: Teacher( Wang, Xiaozhang) 推导过程如下 ① Vx'vyvz(F(x,y)∧F(y,)→>G(x,) P规则 Teacher(Wang, Xiaoli)A Classmates( Xiaoli, Xiaozhang)->Teacher(Wang, Xiaozhang) ①UI规则 8 Teacher(Wang, Xiaoli) P规则 4 Classmates( Xiaoli, Xiaozhang) P规则 5 Teacher (Wang, Xiaoli )A Classmates( Xiaoli, Xiaozhang ③④合取引入 ( Teacher(Wang, Xiaozhang) ②⑤假言推理 (补充)利用自然演绎推理证明-P(a,b)是xvy(P(x,y)→>W(x,y)和_W(a,b) 的逻辑结果。 证明:①wxvy(P(x,y)→>W(x,y) P规则 ②P(a,b)→W(a,b) ①全称固化(UI规则) aw(a, b) P规则
廉师友>作业一参考答案 1． 已知前提：（1）如果 x 与 y 是同班同学，则 x 的老师也是 y 的老师；（2）小李和小张是 同班同学；（3）王先生是小李的老师，运用自然演绎推理证明: 王先生也是小张的老师。 证明：首先定义谓词： Teacher(x, y) x 是 y 的老师 Classmates(x, y) x 和 y 是同班同学 则已知的前提可以符号化为： （1） xyz(Teacher(x, y) Classmates( y,z) → Teacher(x,z)) （2） Teacher(Wang, Xiaoli) （3） Classmates(Xiaoli, Xiaozhang) 要证的结论为： Teacher(Wang, Xiaozhang) 推导过程如下： ① xyz(F(x, y) F( y,z) → G(x,z)) P 规则 ② Teacher(Wang, Xiaoli) Classmates(Xiaoli, Xiaozhang) → Teacher(Wang, Xiaozhang) ① UI 规则 ③ Teacher(Wang, Xiaoli) P 规则 ④ Classmates(Xiaoli, Xiaozhang) P 规则 ⑤ Teacher(Wang, Xiaoli) Classmates(Xiaoli, Xiaozhang) ③④ 合取引入 ⑥ Teacher(Wang, Xiaozhang) ②⑤ 假言推理 （补充）利用自然演绎推理证明 P a b ( , ) 是 → x y P x y W x y ( ( , ) ( , )) 和 W a b ( , ) 的逻辑结果。 证明： ① → x y P x y W x y ( ( , ) ( , )) P 规则 ② P(a,b) →W (a,b) ① 全称固化（UI 规则） ③ W (a,b) P 规则
④-P(a,b) ②③拒取式规则 得证:-P(a,b)是xvjν(P(x,y)→>W(x,y)和W(a,b)的逻辑结论 2.教材P85页第1题 6) Exy(=uVw(P(x,y, =, u,v, w)A(O(,y, =,u, v, w)V-R(, w))) 解: (v=)(v)(P(a,b,=,f(=),v,g(=,v)∧(Q(a,b,=,f(=),v,g(=,v)V-R(a,=,g(=,v)) (P(a,b,=,f(=),v,g(=,v)∧(Qa,b,=,f(=)v,g(=,v)-R(a,=,g(=,v)) (P(a,b,x,f(x)y,g(x,y)^(Q(a,b,z,f(=)v,g(=,v)-R(a,=,g(=,) 求得子句集为 (P(abx,f(x)yg(x,y)Q(ab,=,f()V,g(=,)-R(a1=,8(=,)} (补充1)(x)(y)(P(x,y)v(Q(x,y)→R(x,y)) 解 O(Vxy(P(x,y)v(O(x, y)VR(x, y)) 2(Vx(P(x,f(x))v-O(,f(x))vR(x,f(x))) BP(x,f(x))V-O(x,f(x))vR(x,f(x)) 求得子句集为{P(x,f(x)y-Q(x,f(x)vR(x,f(x)} (补充2)(vx)y)(彐)(P(x,y)→>Q(x,y)vR(x,=) 解:①(x)(yyX彐)(-P(x,y)vQ(x,y)vR(x,) 2(Vx)(Vy(P(x, y)v o(x,y)vR(x,f(x,y))) 3-P(x, y)vO(x,y)vR(x,f(x, y) 求得子句集为{P(x,y)√(x,y)yR(x,f(xy)}
④ P a b ( , ) ②③ 拒取式规则 得证： P a b ( , ) 是 → x y P x y W x y ( ( , ) ( , )) 和 W a b ( , ) 的逻辑结论。 2． 教材 P85 页 第 1 题 （6） (x)(y)(z)(u)(v)(w)(P(x, y,z,u,v,w) (Q(x, y,z,u,v,w) R(x,z,w))) 解： ① (z)(v)(P(a,b,z, f (z), v, g(z,v)) (Q(a,b,z, f (z), v, g(z,v)) R(a,z, g(z,v)))) ② (P(a,b,z, f (z), v, g(z,v)) (Q(a,b,z, f (z), v, g(z,v)) R(a,z, g(z,v)))) ③ (P(a,b, x, f (x), y, g(x, y)) (Q(a,b,z, f (z), v, g(z,v)) R(a,z, g(z,v)))) 求得子句集为 (P(a,b, x, f (x), y, g(x, y)),Q(a,b,z, f (z),v, g(z,v)) R(a,z, g(z,v))。 （补充 1） ( )( )( ( , ) ( ( , ) ( , ))) → x y P x y Q x y R x y 解： ① (x)(y)(P(x, y) (Q(x, y) R(x, y))) ② (x)(P(x, f (x)) Q(x, f (x)) R(x, f (x))) ③ P(x, f (x)) Q(x, f (x)) R(x, f (x)) 求得子句集为 P(x, f (x)) Q(x, f (x)) R(x, f (x))。 （补充 2） (x)(y)(z)(P(x, y) → Q(x, y) R(x,z)) 解： ① (x)(y)(z)(P(x, y) Q(x, y) R(x,z)) ② (x)(y)(P(x, y) Q(x, y) R(x, f (x, y))) ③ P(x, y) Q(x, y) R(x, f (x, y)) 求得子句集为 P(x, y) Q(x, y) R(x, f (x, y))
3.教材P85页第3题 (3)S={-P(x)y-Q(y)-L(x,y)P(a)-R(=)vL(a,=),R(b),Q(b)} 解:①-P(x)v-Q(x) ②P(a) ③-R(=)L(a,) ④R(b) ⑤Q(b) ⑥-Q(y)v-L(a,y) ①2②{a/: ⑦-L(a,b) ⑤⑥{/y ③④{/} ⑨NIL ⑦⑧ 所以,原子句集是不可满足的 (4) S=(P(x)vo(x)VR(), P()vr(),O(a, R(b) 解: ①P(x)Q(x)vR(x) R(b ⑤Q(y)vR(y) v/x) ⑥R(a) all 无法归结出空子句,所以原子句集是可满足的。 (5)S={P(x)Q(x),Q(y)R(y),-P()vQ(=),-R(u)} 解: ①P(x)vQ(x) O()VR(y)
3． 教材 P85 页 第 3 题： （3） S P x Q y L x y P a R z L a z R b Q b = { ( ) ( ) ( , ), ( ), ( ) ( , ), ( ), ( )} 解： ① P(x) Q(x) L(x, y) ② P(a) ③ R(z) L(a,z) ④ R(b) ⑤ Q(b) ⑥ Q( y) L(a, y) ①② a / x ⑦ L(a,b) ⑤⑥ b/ y ⑧ L(a,b) ③④ b / z ⑨NIL ⑦⑧ 所以，原子句集是不可满足的。 （4） S P x Q x R x P y R y Q a R b = { ( ) ( ) ( ), ( ) ( ), ( ), ( )} 解： ① P(x) Q(x) R(x) ② P( y) R( y) ③ Q(a) ④ R(b) ⑤ Q( y) R( y) ①② y / x ⑥ R(a) ③⑤ a / y 无法归结出空子句，所以原子句集是可满足的。 （5） S P x Q x Q y R y P z Q z R u = { ( ) ( ), ( ) ( ), ( ) ( ), ( )} 解： ① P(x) Q(x) ② Q( y) R( y)
③-P()Q(=) ⑤-Q() ②④{/y ⑥P() ①⑤{/x ⑦-P() 8⑤w/x} ⑧NIL ⑥⑦ 所以,原子句集是不可满足的。 (补充1)S={-P(x)vQ(x),P(y)VR(y),P(a),S(a,-S(=)v-R(=)} 解: ①-P(x)vQ(x) ②-P(y)vR(y) ③P(a) ④S(a) ⑤→S(二)-R(=) ⑥R(a) ②8{/y ④⑤{/x 所以,原子句集是不可满足的。 (补充2)S={-P(x)vQ((x),a),-P(h(y)VvQ(f(h(y),a)V-P(=)} 解: ①-P(x)vQ(f(x),a) 2-P(h()) oc(h()),a)v-P(:) 3-P(h(y)vo(ch(y)), a ②{0y) @P(h())voc(h(),a) ①{(y)/x 无法归结出空子句,所以原子句集是可满足的
③ P(z) Q(z) ④ R(u) ⑤ Q(u) ②④ u / y ⑥ P(u) ①⑤ u / x ⑦ P(u) ③⑤ u / x ⑧NIL ⑥⑦ 所以，原子句集是不可满足的。 （补充 1） S P x Q x P y R y P a S a S z R z = { ( ) ( ), ( ) ( ), ( ), ( ), ( ) ( )} 解： ① P(x) Q(x) ② P( y) R( y) ③ P(a) ④ S(a) ⑤ S(z) R(z) ⑥ R(a) ②③ a / y ⑦ R(a) ④⑤ a / x ⑧NIL ⑥⑦ 所以，原子句集是不可满足的。 （补充 2） S P x Q f x a P h y Q f h y a P z = { ( ) ( ( ), ), ( ( )) ( ( ( )), ) ( )} 解： ① P(x) Q( f (x), a) ② P(h( y)) Q( f (h( y)), a) P(z) ③ P(h( y)) Q( f (h( y)), a) ② h(y)/z ④ P(h( y)) Q( f (h( y)), a) ① h(y)/ x 无法归结出空子句，所以原子句集是可满足的
4、教材P86页第4题 (3)F1:(xP(x)→>(vy)Q()→>-(x,y) F2:(x)(P(x)∧(wy)(R(y)→>L(x,y) G:(Vx)(R(x)→>-Q(x) 解:首先将F,F2和一G化为子句集 F F ③-R()L(a,z) R(b) 然后进行归结: ⑥-Q(y)y-L( alx) ⑦L(a,b) ③④b/z} ⑧L(a ⑤⑥{/y ⑦⑧ 所以,G是F和F2的逻辑结论。 补充1):(xF(x))ygb G:(x)(P(x)∧Q(x) 证明:首先将F1和一G化为子句集: ②Q(a)vQ(b) aP()v-O()
4、教材 P86 页 第 4 题： （3） 1F x P x y Q y L x y :( )( ( ) ( )( ( ) ( , ))) → → 2 F x P x y R y L x y :( )( ( ) ( )( ( ) ( , ))) → G x R x Q x : ( )( ( ) ( )) → 解：首先将 F1，F2 和 G 化为子句集： F1 ： ① P(x) Q( y) L(x, y) F2 ： ② P(a) ③ R(z) L(a,z) G ： ④ R(b) ⑤ Q(b) 然后进行归结： ⑥ Q( y) L(a, y) ①② a / x ⑦ L(a,b) ③④ b / z ⑧ L(a,b) ⑤⑥ b/ y ⑨ NIL ⑦⑧ 所以， G 是 F1 和 F2 的逻辑结论。 （补充 1） 1 : ( )( ( ) ( ( ) ( ))) : ( )( ( ) ( )) F x P x Q a Q b G x P x Q x 证明：首先将 F1 和 G 化为子句集： F1： ① P(x) ② Q(a) Q(b) G： ③ P( y) Q( y)
然后进行归结: ②④{/x ⑥NL ④⑤{/x} 所以,G是F的逻辑结论。 (补充2)F:(VxA(x)∧_B(x)→>(yD(x,y)ACO) F2:(丑x)(E(x)∧A(x)∧(vy)D(x,y)→E(y)) F3:(x)(E(x)→-B(x) G:(x)(E(x)∧C(x) 解:首先将F,F2,F3和一G化为子句集: F O -A(x)vB(x)V D(x,f(x)) ②_4(y)vB(y)C(f(y) F3 ③E(b) A(b) ⑤-D(b,=)VE(=) F3: ⑥-E(u)=B() ⑦-E(v)-C(v) 因为归结不出空子句 所以,G不是F,F2和F3的逻辑结论
然后进行归结： ④ Q(x) ①③ x / y ⑤ Q(b) ②④ a / x ⑥ NIL ④⑤ b / x 所以， G 是 F1 的逻辑结论。 （补充 2） 1F x A x B x y D x y C y :( )( ( ) ( ) ( )( ( , ) ( ))) → 2 F x E x A x y D x y E y :( )( ( ) ( ) ( )( ( , ) ( ))) → 3 F x E x B x : ( )( ( ) ( )) → G x E x C x : ( )( ( ) ( )) 解：首先将 F1，F2，F3 和 G 化为子句集： F1 ： ① A(x) B(x) D(x, f (x)) ② A( y) B( y) C( f ( y)) F2 ： ③ E(b) ④ A(b) ⑤ D(b,z) E(z) F3 ： ⑥ E(u) B(u) G ： ⑦ E(v) C(v) 因为归结不出空子句， 所以， G 不是 F1，F2 和 F3 的逻辑结论