AI第五章作业讲解.docx

AI第五章作业讲解习题五 求下列谓词公式的子句集。 (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$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) 3. 试判断下列子句集中哪些是不可满足的。 (1) S=P(y) Ú¬Q(y), ¬P(f(x) ÚQ(y) 解： P(y) Ú¬Q(y) ¬P(f(x) ÚQ(z) (适当改名使子句之间不含相同变元 利用归结原理： P(y) Ú¬P(f(x) (1)(2) y/z T f(x)/y 归结不出空子句，所以原子句集是可以满足的。 (2) S=¬ P(x) ÚQ(x), ¬ Q(y) ÚR(y),P(a),R(a) 解：¬ P(x) ÚQ(x) ¬ Q(y) ÚR(y) P(a) R(a) 利用归结原理判断 Q(a) (1)(3) a/x 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) 解：¬ P(x) Ú¬Q(y) Ú¬L(x,y) P(a) ¬ R(z) ÚL(a,z) R(b) Q(b) 利用归结原理来进行判断 ¬Q(y) Ú¬L(a,y) (1)(2)a/x L(a,b) (3)(4) b/z ¬L(a,b) b/y Nil 得到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) 利用归结原理来判断 (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(z) ÚQ(z) ¬R(u) 利用归结原理来判断 ¬Q(u) u/y ¬P(u) u/z Q(u) u/x NIL 所以原子句集S不可满足 4对下列各题请分别证明，G是否可肯定是F1，F2，的逻辑结论 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的逻辑结论。 F1 ("x)(P(x)®(Q(x)R(x) F2 ($x) (P(x) S(x) G ($x)(S(x) R(x) 证明：利用归结反演法，先证明F1 F2 ¬G是不可满足的。 求子句集： (1) ¬P(x) Q(x) (2) ¬P(z) R(z) (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) F2 F1 S 所以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)AÚBÚC (2)AÙ¬B® C (3)B® C 结论：C是子句集的逻辑AÚBÚC , AÙ¬B® C , B® C的逻辑结果。 证： AÚBÚC ¬ AÚ BÚ C ¬BÚC ¬ C B Ú C 由, C 由, Null 由, 即：对子句集S=AÚBÚC ,¬ AÚ BÚC ,¬BÚC, ¬C施以归结，最后推出空子句，所以子句集不可满足，所以C是子句集AÚBÚC ,¬ AÚ BÚC ,¬BÚC的逻辑结果，所以公司一定要录取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说真话。 如果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进行归结： (9) ¬ T(A) T(C) (1),(7) (10)T(C) (6),(9) (11)ANS(C) (8),(10) 这样就得到了答案，即C是老实人，即C从来不说假话。 下面来证明B和A不是老实人，设A不是老实人，则有¬ T(A) ,将其否定并入S中，得到子句集S2，即S2比S多了一个子句： (8) ¬ (¬ T(A) )即T(A) 利用归结原理对进行归结： (9) T(A) T(C) (1),(7) (10)T(C) (6),(9) (11)NIL (8),(10)