廉师友<<人工智能>>作业一参考答案1．已知前提：（1）如果x与y是同班同学，则x的老师也是y的老师；（2）小李和小张是同班同学；（3）王先生是小李的老师，运用自然演绎推理证明: 王先生也是小张的老师。

证明：首先定义谓词：Teacher x是y的老师x,)(yx(yClassmates x和y是同班同学,)则已知的前提可以符号化为：（1）))ClassmatesTeacheryyx∀y∀∀∧x→z())(z,,,x(zTeacher(（2）)TeacherWang,(Xiaoli（3）)XiaoliClassmates(Xiaozhang,要证的结论为：)TeacherWang,(Xiaozhang推导过程如下：①))FxzFy∀∀P规则∀yx→y∧,(),z)(,xG(z(②ClassmatesXiaoliXiaozhangXiaoliTeacher→∧WangWangTeacher(,(Xiaozhang,))(,)①UI规则③)WangTeacher P规则(Xiaoli,④)XiaoliClassmates P规则,(Xiaozhang⑤)ClassmatesXiaoliXiaoliTeacher∧Wang,(Xiaozhang)(,③④合取引入⑥)Teacher②⑤假言推理Wang,(Xiaozhang（补充）利用自然演绎推理证明(,)W a b∀∀→和(,)⌝⌝是((,)(,))x y P x y W x yP a b的逻辑结果。

证明：①((,)(,))x y P x y W x y∀∀→P规则②)bP→①全称固化（UI规则）aaW,(),(b③)⌝P规则Wa(b,④(,)⌝②③拒取式规则P a b得证：(,)W a b∀∀→和(,)⌝的逻辑结论。

P a b⌝是((,)(,))x y P x y W x y2．教材P85页第1 题（6）uzwPQxywvwuzyx∧∃∀∀∃∃∃Rzuyx⌝∨vv,,,()(,,,x,(),))) )()()()(,(w)(z,,,)((解：①fzzvQabzazRvgzvP∨z⌝∧∀g ∀vazvfzbg,),((,,,,)),))))z,(,((,,()(((v,)(((,))),,②vbzzfgaagzRvzbP⌝a∨∧zzfzvgvzQ,,(),(,,))(,)))),(,,,(,,(),,(()),((v③vgzfzzvgzzaRbabxaP⌝∨fxyQxgy∧(v(,,),())(,))))(,,,,(),,,,,((,()),(求得子句集为{}))vgzfzzvzgzaRbabxaP⌝∨。

fxyxgyQ((,,),()),(v,(,,(),,(,,,,,()),(,（补充1）()()((,)((,)(,)))∀∃∨→x y P x y Q x y R x y解：①)))xyxyPQx∨∀R∃∨⌝y(,()(x),)()((y,(②)))QxxRfxf⌝∨∀xx∨Px((,))(f(,))(x()((,③))fxRQxP∨∨x⌝xfx(x))(,((,,())(f求得子句集为{}))xfxRQx⌝P∨xfx∨。

))((,(,((x,())f（补充2）))xPyQxzy∀∀∃→x∨Ry(),)(,((zx)()()(,解：①))PzxyxQyx∨∀∀∃⌝∨y,(),)(,((zx)()()(R②)))yxQxRyPyx∀⌝∨x∨∀,,()(f,)(,x)((y()(③))xRQx∨f⌝P∨xyy(,(,),(y,)(x求得子句集为{}))xyRxQy∨P∨xf⌝。

)(,(,,((y,)x3． 教材P85 页 第3 题：（3）{()()(,),(),()(,),(),()}S P x Q y L x y P a R z L a z R b Q b =⌝∨⌝∨⌝⌝∨ 解： ①),()()(y x L x Q x P ⌝∨⌝∨⌝ ②)(a P③),()(z a L z R ∨⌝ ④)(b R ⑤)(b Q⑥),()(y a L y Q ⌝∨⌝ ①② }{x a / ⑦),(b a L ⌝ ⑤⑥ }{y b /⑧),(b a L③④ }{z b / ⑨NIL⑦⑧所以，原子句集是不可满足的。

（4）{()()(),()(),(),()}S P x Q x R x P y R y Q a R b =∨∨⌝∨⌝⌝解：①)()()(x R x Q x P ∨∨ ②)()(y R y P ∨⌝③)(a Q ⌝ ④)(b R ⌝ ⑤)()(y R y Q ∨ ①② }{x y /⑥)(a R③⑤ }{y a /无法归结出空子句，所以原子句集是可满足的。

（5）{()(),()(),()(),()}S P x Q x Q y R y P z Q z R u =∨⌝∨⌝∨⌝ 解： ①)()(x Q x P ∨②)()(y R y Q ∨⌝③)()(z Q z P ∨⌝ ④)(u R ⌝ ⑤)(u Q ⌝ ②④ }{y u /⑥)(u P①⑤ }{x u / ⑦)(u P ⌝ ③⑤ }{x u / ⑧NIL⑥⑦所以，原子句集是不可满足的。

（补充1）{()(),()(),(),(),()()}S P x Q x P y R y P a S a S z R z =⌝∨⌝∨⌝∨⌝ 解： ①)()(x Q x P ∨⌝ ②)()(y R y P ∨⌝ ③)(a P ④)(a S⑤)()(z R z S ⌝∨⌝ ⑥)(a R ②③ }{y a / ⑦)(a R ⌝ ④⑤ }{x a /⑧NIL⑥⑦所以，原子句集是不可满足的。

（补充2）{()((),),(())((()),)()}S P x Q f x a P h y Q f h y a P z =⌝∨⌝∨∨⌝ 解： ①)),(()(a x f Q x P ∨⌝②)())),((())((z P a y h f Q y h P ⌝∨∨⌝ ③))),((())((a y h f Q y h P ∨⌝ ② }{z y h /)(④))),((())((a y h f Q y h P ∨⌝① }{x y h /)(无法归结出空子句，所以原子句集是可满足的。

4、教材P86 页 第4 题： （3）1:()(()()(()(,)))F 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 ∀→⌝解：首先将F 1，F 2和G ⌝化为子句集： F 1 ： ① ),()()(y x L y Q x P ⌝∨⌝∨⌝F 2 ：② )(a P③ ),()(z a L z R ∨⌝G ⌝ ：④ )(b R⑤ )(b Q然后进行归结： ⑥ ),()(y a L y Q ⌝∨⌝ ①② }{x a / ⑦ ),(b a L ③④ }{z b / ⑧ ),(b a L ⌝ ⑤⑥ }{y b /⑨ NIL⑦⑧所以，G 是F 1和F 2的逻辑结论。

（补充1）1:()(()(()())):()(()())F x P x Q a Q bG x P x Q x ∀∧∨∃∧证明：首先将F 1和G ⌝化为子句集： F 1：① )(x P ② )()(b Q a Q ∨G ⌝：③ )()(y Q y P ⌝∨⌝然后进行归结： ④ )(x Q ⌝ ①③ }{y x / ⑤ )(b Q ②④ }{x a / ⑥ NIL④⑤ }{x b /所以，G 是F 1的逻辑结论。

（补充2）1:()(()()()((,)()))F 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 ∃∧解：首先将F 1，F 2，F 3和G ⌝化为子句集： F 1 ： ① ))(,()()(x f x D x B x A ∨∨⌝ ② ))(()()(y f C y B y A ∨∨⌝F 2 ：③ )(b E ④ )(b A⑤ )(),(z E z b D ∨⌝F3 ：⑥ )()(u B u E ⌝∨⌝G ⌝ ：⑦ )()(v C v E ⌝∨⌝因为归结不出空子句，所以，G 不是F 1，F 2和F 3的逻辑结论。