AI第五章作业讲解

AI第五章作业讲解AI第五章作业讲解AI第五章作业讲解AI第五章作业讲解编制仅供参考审核批准生效日期地址：电话：传真:邮编:-标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII-标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KIIAI第五章作业讲解习题五求下列谓词公式的子句集。xy(P(x,y)Q(x,y))解：去掉存在量词变为：P(a,b)Q(a,b)变成子句集{P(a,b),Q(a,b)}xy(P(x,y)Q(x,y))解：去掉蕴涵符号变为：xy(¬P(x,y)Q(x,y))去掉全称量词变为：¬P(x,y)Q(x,y)变成子句集{¬P(x,y)Q(x,y)}xy((P(x,y)Q(x,y))R(x,y))解：去掉蕴涵符号变为：xy(¬(P(x,y)Q(x,y))R(x,y))否定符号作用于单个谓词变为：xy((¬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))}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))}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)}xyzuvw(p(x,y,z,u,v,w)(Q(x,y,z,u,v,w)¬R(x,z,w)))解：去掉存在量词变为：zv(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.试判断下列子句集中哪些是不可满足的。S={P(y)¬Q(y),¬P(f(x))Q(y)}解：P(y)¬Q(y)¬P(f(x))Q(z)(适当改名使子句之间不含相同变元利用归结原理：（3）P(y)¬P(f(x))(1)(2){y/z}（4）T{f(x)/y}归结不出空子句，所以原子句集是可以满足的。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}归结不出空子句，所以是可满足的子句集。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所以原子句集不可满足。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）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的逻辑结论．此题的方法是：F1F2¬G能推出空子句，就可以说明G是（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)F1S(2)¬P(z)∨R(z)SF2(3)P(a)F2(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喜欢yF(x):x是苍蝇然后将上述各语句翻译为谓词公式：已知条件：(1)x(C(x)y(P(y)L(y,x)))(2)xy(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)A¬BC(3)BC结论：C是子句集的逻辑{ABC,A¬BC,BC}的逻辑结果。证：①ABC②¬ABC③¬BC④¬C⑤BC由①,②⑥C由③,⑤Null由④,⑥即：对子句集S={ABC,¬ABC,¬BC,¬C}施以归结，最后推出空子句，所以子句集不可满足，所以C是子句集{ABC,¬ABC,¬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)