ai第五章作业讲解1.docx
《ai第五章作业讲解1.docx》由会员分享，可在线阅读，更多相关《ai第五章作业讲解1.docx（10页珍藏版）》请在冰点文库上搜索。
ai第五章作业讲解1
习题五
求下列谓词公式的子句集。
（1）xy（P（x,y）Q（x,y））
解：
去掉存在量词变为：
P（a,b）Q（a,b）
变成子句集{P（a,b）,Q（a,b）}
（2）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）}
（3）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））}
（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）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.试判断下列子句集中哪些是不可满足的。
（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的逻辑结论．
此题的方法是：
F1F2¬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是不可满足的。
求子句集：
（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）]
所以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）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由③,⑤
7Null由④,⑥
即：
对子句集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）（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中，得到子句集S1，即
S1比S中多了一个子句：
（8）¬T（x）∨ANS（x）
应用归结原理对S1进行归结：
（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）’]
升级会员 