AI第五章作业讲解.doc

习题五求下列谓词公式的子句集。(1) $x$y(P(x,y) Q(x,y)解：去掉存在量词变为：P(a,b)Q(a,b) 变成子句集 P(a,b),Q(a,b)(2) x y(P(x,y) Q(x,y)解：去掉蕴涵符号变为：x y( P(x,y) Q(x,y)去掉全称量词变为： P(x,y) Q(x,y)变成子句集 P(x,y) Q(x,y)(3) x$y(P(x,y) Q(x,y) R(x,y)解：去掉蕴涵符号变为：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) R(x,f(x)( Q(x,f(x) R(x,f(x)变元：( P(x,f(x) R(x,f(x)( Q(y,f(y) R(y,f(y)变成子句集 P(x,f(x) R(x,f(x), Q(y,f(y) R(y,f(y)(4) x (P(x) $y (P(y) R(x,y)解：去掉蕴涵符号变为：x ( (P(x) $y (P(y) R(x,y)去掉存在量词变为：x ( (P(x) (P(f(x) R(x,f(x)去掉全称量词变为： ( (P(x) (P(f(x) R(x,f(x)化合取范式为：( (P(x) P(f(x) ( (P(x) R(x,f(x)变元：( (P(x) P(f(x) ( (P(y) R(y,f(y)变为子句集： (P(x) P(f(x), (P(y) R(y,f(y)(5) $x(P(x) x(P(y) R(x,y)解：去掉蕴涵符号变为：$x(P(x) x(P(y) R(x,y)去掉存在量词变为：P(a) x(P(y) R(a,y)去掉全称量词变为：P(a) (P(y) R(a,y)变成子句集： P(a) ，P(y) R(a,y) (6) $x$yz $uv $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) 3. 试判断下列子句集中哪些是不可满足的。(1) S=P(y) Q(y), P(f(x) Q(y)解：（1） P(y) Q(y)（2） P(f(x) Q(z) (适当改名使子句之间不含相同变元利用归结原理：（3）P(y) P(f(x) (1)(2) y/z（4）T f(x)/y归结不出空子句，所以原子句集是可以满足的。(2) S= P(x) Q(x), Q(y) R(y),P(a),R(a) 解：（1） P(x) Q(x) （2） Q(y) R(y)（3）P(a)（4）R(a)利用归结原理判断（5）Q(a) (1)(3) a/x（6）R(a) (2)(5) a/x归结不出空子句，所以是可满足的子句集。(3) S= P(x) Q(y) L(x,y),P(a), R(z) L(a,z) ,R(b),Q(b)解：（1） P(x) Q(y) L(x,y)（2）P(a)（3） R(z) L(a,z) （4）R(b)（5）Q(b)利用归结原理来进行判断（6）Q(y) L(a,y) (1)(2)a/x（7）L(a,b) (3)(4) b/z（8）L(a,b) （6）（5）b/y（9）Nil （8）（7）得到NIL所以原子句集不可满足。(4) S=P(x) Q(x) R(x), P(y) R(y), Q(a), R(b) 解：（1）P(x) Q(x) R(x)（2） P(y) R(y)（3） Q(a)）（4）R(b)利用归结原理来判断（5）（6）（7）(5) S=P(x) Q(x), Q(y) R(y), P(z) Q(z), R(u) 解：（1）P(x) Q(x)（2） Q(y) R(y)（3） P(z) Q(z)（4） R(u)利用归结原理来判断（5）Q(u) （2）（4）u/y（6）P(u) （3）（5）u/z（7）Q(u) （1）（6）u/x（8）NIL （5）（7）所以原子句集S不可满足4对下列各题请分别证明，G是否可肯定是F1，F2，的逻辑结论（1）F: x(P(x) Q(x) G: $x(P(x) Q(x)解： F的子句集为： P(x) Q(y) G的子句集为: P(z) Q(z) 然后应用消解原理得： Q(z) , ,z/x NIL ,z/y 所以G是F的逻辑结论此题应注意：化子句集时应改名，使子句，无同名变元。(3)F1: x(P(x)y(Q(y) L(x,y) F2: $x(P(x)y(R(y) L(x,y) G: x(R(x) Q(x)证明：首先求得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 Q(b) ,b/y NIL ,所以G是F1,F2的逻辑结论此题的方法是：F1 F2 G能推出空子句，就可以说明G是F1,F2的逻辑结论。（4） F1 (x)(P(x)(Q(x)R(x)F2 ($x) (P(x) S(x)G ($x)(S(x) R(x)证明：利用归结反演法，先证明F1 F2 G是不可满足的。 求子句集：F1 (1) P(x) Q(x)S (2) P(z) R(z)F2 (3)P(a) (4)S(a) (5) S(y) R(y) (G)利用归结原理进行归结(6)R(a) (2),(3), 1=a/z (7) R(a) (4),(5), 2 =a/y (8)Nil (6),(7)所以S是不可满足得，从而G是F1和F2的逻辑结果。5.设已知：(1)凡是清洁的东西就有人喜欢： (2)人们都不喜欢苍蝇： 用归结原理证明：苍蝇是不清洁的 证明：首先，定义如下谓词： C(x)：x是清洁的 P(x)：x是人 L(x,y)：x喜欢y F(x):x是苍蝇然后将上述各语句翻译为谓词公式：已知条件：(1) x(C(x) $ y(P(y) L(y,x) (2) x y(P(x) F(y) L(x,y)需证结论：(3) x(F(x) C(x)求题设与结论否定的子句集，得: C(x) P(f(x) C(y) L(f(y),y) P(u) F(v) L(u,v) F(a) C(a)然后应用消解原理得: P(f(a) ,a/x L(f(a),a) ,a/y F(v) L(f(a),v) ,f(a)/u L(f(a),a) ,a/v NIL ,所以苍蝇是不清洁的此题需注意谓词的定义：x喜欢y 定义成L(x,y)，另外要定义谓词：人。6 证明：用命题公式表述题意为：(1)ABC (2)AB C (3)B C结论：C是子句集的逻辑ABC , AB C , B C的逻辑结果。证： ABC A B C BC C B C 由, C 由, Null 由,即：对子句集S=ABC , A BC ,BC, C施以归结，最后推出空子句，所以子句集不可满足，所以C是子句集ABC , A BC ,BC的逻辑结果，所以公司一定要录取C.张某被盗，公安局派出五个侦探去调查研究案情时，侦察员说赵与钱中至少有一人做案；侦察员说钱与孙中至少有一人做案；侦察员说孙与李中至少有一人做案；侦察员说赵与孙中至少有一个与此案无关；侦察员说钱与李中至少有一人与此案无关如果这五个侦察员的话都有是可信，请用归结原理求出谁是盗窃犯(知识点，利用归结原理求取问题答案)解：设谓词P(x)表示x是盗窃犯则题意可表述为如下的谓词公式：F1:P(zhao) P(qian)F2: P(qian) P(sun)F3: P(sun) P(li)F4: P(zhao) P(sun)F5: P(qian) P(li)求证的公式为： $xP(x)子句集如下： P(zhao) P(qian) P(qian) P(sun) P(sun) P(li) P(zhao) P(sun) P(qian) P(li) P(x) GA(x) P(qian) P(sun) , P(sun) P(li) , P(sun) , GA(sun) ,sun/x(11)P(qian) ,(12)GA(qian) ,(11),qian/x所以，sun和qian都是盗窃犯即：孙和钱都是盗窃犯（利用归结原理来证明或求取问题答案只能使用归结反演的方法）此题需定义一个辅助谓词GA(x)来求出谁是盗窃犯。设A、B、C中有人从来不说真话，也有人从来不说谎话，某人向这三人分别同时提出一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个人说谎”。用归结原理求谁是老实人，谁是说谎者？解：用T（x）表示x说真话。 如果A说的是真话则有：T(A) (T(B) T(C) 如果A说的是假话则有： T(A) (T(B) T(C) 对B和C所说的话做相同的处理，可得： T(B) (T(A) T (C) T(B) (T(A) T(C) T(C) (T(A) T(B) T(C) (T(A) T(B)将上面的公式化为子句集，得到S：(1) T(A) T(B) (2) T(A) T(C )(3)T(A) T(B ) T(C )(4) T(B) T(C )(5) T(A) T(B ) T(C )(6)T(C) T(A)(7)T(C) T(B)首先求谁是老实人。把 T(x) ANS(x)并入S中，得到子句集S 1 ，即S 1比S中多了一个子句：(8) T(x) ANS(x)应用归结原理对S 1进行归结：