确定性推理部分参考答案.docx

《确定性推理部分参考答案.docx》由会员分享，可在线阅读，更多相关《确定性推理部分参考答案.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章确定性推理部分参考答案3.8判断下列公式是否为可合一，若可合一，则求出其最一般合一。(1) P(a, b), P(x, y)P(f(x), b), P(y, z)(2) P(&x), y), P(y, f(b)P(f(y), y, x), P(x, f(a), f(b)(3) P(x, y), P(y, x)解：(1)可合一，其最一般和一为：o=a/x,b/y。(2)可合一，其最一般和一为：。=y/f(x), b/z。(3)可合一，其最一般和一为：。= f(b)/y, b/x。(4)不可合一。(5)可合一，其最一般和一为：o=y/x。3.11把下列谓词公式化成子句集：(1) (Vx)(V

2、 y)(P(x, y)AQ(x, y)(Vx)(V y)(P(x, y)-Q(x, y)(2) (Vx)(3y)(P(x,y)V(Q(x.y)-R(x,y)(Vx)(Vy)(3 z)(P(x, y)-*Q(x, y)VR(x, z)解：(1)由于(/乂)(/丫)(&丫)八()(：丫)已经是5卜0111标准型，且 P(x,y)AQ(x,y)已经是 合取范式，所以可直接消去全称量词、合取词，得P(x, y), Q(x, y)再进行变元换名得子句集：S= P(x, y), Q(u, v)(2)对谓词公式(Vx)(Vy)(P(x.y)-*Q(x,y),先消去连接词“一”得：(Vx)(V y)CP(&

3、y)VQ(x, y)此公式已为Skokm标准型。再消去全称量词得子句集：S=-P(x,y)VQ(x,y)(3)对谓词公式(Vx)Gy)(P(x,y)V(Q(x.y)-R(x,y),先消去连接词“一”得：(Vx)(3 yXP(x, y)V (p(x, y)VR(x, y)此公式已为前束范式。再消去存在量词，即用Skolem函数f(x)替换y得：(V x)(P(x, f(x)V-Q(x, Rx)VR(x, f(x)此公式已为Skolem标准型。最后消去全称量词得子句集：S=P(x, f(x)Vp(x, f(x)VR(x, Rx)(4)对谓词(Vx)(Vy)(mz)(P(x,y)fQ(x.y)VR(

4、x.z),先消去连接词“一”得：1逆向推理的关键是要能够推出L(Zhang , Ram)AL(Zhang , Snow),其逆向演绎过程如下图 所示。10(Vx)(Vy)(3 z)(P(x. y)VQ(x, y)VR(x, z) 再消去存在量词，即用Skolem函数f(x)替换y得:(Vx)(Vy)P(x, y)VQ(x. y)VR(x. f(x,y) 此公式已为Skolem标准型。最后消去全称量词得子句集:S=P(x. y)VQ(x, y)VR(x, Rx,y)3-13判断下列子句集中哪些是不可满足的：PVQ.p, PP PVQ,PVQ, PVp, P(y)VQ(y), -P(f(x)VR(

5、a)-P(x)VQ(x),P(y)VR(y),P(a),S(a),-S(z)VR(z)-P(x)VQ(f(x),a), P(h(y) VQ(f (h (y), a)VP(z) P(x)VQ(x)VR(x),P(y) VR(y), -Q(a)R(b)解：(1)不可满足，其归结过程为：-PVQ(2)(2)不可满足，其归结过程为:(3)不是不可满足的，原因是不能由它导出空子句。(4)不可满足，其归结过程略(5)不是不可满足的，原因是不能由它导出空子句。(6)不可满足，其归结过程略3.14对下列各题分别证明G是否为Fi,F2,.,Fn的逻辑结论:(1) F:(3xX3yXP(x,y)G:(Vy)(3

6、x)(P(x, y)(2) F:( V xXP(x)A(Q(a)VQ(b)G:(3x) (P(x)AQ(x)(3) F：(3x)(3yXP国x)A(Q(f(y)G: P(f(a)AP(y)AQ(y)(4) Fi：(Vx)(P(x)(Vy)(Q(y)-Ux.y) F2：(3 x) (P(x) A( V y)(R(y)f L(x.y) G: (V x)(R(x)f Q(x)F,:(V x)(P(x)-(Q(x)AR(x)F2: (3x) (P(x)AS(x)G: (3 x) (S(x)AR(x)解：(1)先将F和P化成子句集：S=P(a,b),P(x.b)再对S进行归结：所以，G是F的逻辑结论(2

7、)先将F和P化成子句集由 F 得：Si=P(x), (Q(a)VQ(b)由于P 为：-(3x)(P(x)AQ(x),即(Vx)P(x)VQ(x),可得：S2=-P(x)V-Q(x)因此，扩充的子句集为：S=P(x), (Q(a)VQ(b), -P(x)V-Q(x) 再对s进行归结：所以，G是F的逻辑结论同理可求得(3)、(4)和(5),其求解过程略。3.15 设已知： 1)如果X是y的父亲，y是z的父亲，则x是z的祖父；2)每个人都有一个父亲。使用归结演绎推理证明：对于某人U, 一定存在一个人V, V是U的祖父。解：先定义谓词F(x,y)： x是y的父亲GF(x,z)： x是z的祖父P(x)：

8、 X是一个人再用谓词把问题描述出来：已知 F1 ： (Vx)(Vy)(Vz)( F(x,y)/F(y,z)f GF(x,z)F2： ( V y)(P(x)-*F(x,y)求证结论 G： ( 3 u) (3 v)( P(u)-GF(vji)然后再将Fl, F2和-G化成子句集：F(x,y)/F(y,z)VGF(x,z)P(r)VF(S4) P(u) PF(v,u)对上述扩充的子句集，其归结推理过程如下:3.16 假设张被盗，公安局派出5个人去调查。案情分析时，贞察员A说：“赵与钱中至 少有一个人作案”，贞察员B说：“钱与孙中至少有一个人作案”，贞察员C说：“孙与李中至少 有一个人作案”，贞察员D

9、说：“赵与孙中至少有一个人与此案无关”，贞察员E说：“钱与李中 至少有一个人与此案无关二如果这5个侦察员的话都是可信的，使用归结演绎推理求出谁是盗 窃犯。解：(1)先定义谓词和常量设C(x)表示x作案，Z表示赵，Q表示钱，S表示孙，L表示李(2)将已知事实用谓词公式表示出来赵与钱中至少有一个人作案：C(Z)VC(Q)钱与孙中至少有一个人作案：C(Q)VC(S)孙与李中至少有一个人作案：C(S)VC(L)赵与孙中至少有一个人与此案无关：(c(z)/c(s),即y(z)v(s) 钱与李中至少有一个人与此案无关：(C(Q)八C(L),即P(Q)VP(L) (3)将所要求的问题用谓词公式表示出来，并与

10、其否定取析取。设作案者为u，则要求的结论是C(u)。将其与其否)取析取，得：C(u) VC(u)(4)对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：C(Z)VC(Q)y(Z) VC(S)C(Q)VP(S) C(Q)VC(S)C(Q) -C(u)VC(u)C(Q)因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出:因此，孙也是盗窃犯。3.18 设有子句集：P(x)VQ(a, b), P(a)V -i Q(a, b), -iQ(a,f(a), -iP(x)VQ(x, b)分别用各种归结策略求出其归结式。解：支持集策略不可用，原因是没有指明哪个子句是由目标公式的否定

11、化简来的。 删除策略不可用，原因是子句集中没有没有重言式和具有包孕关系的子句。单文字子句策略的归结过程如下：用线性输入策略(同时满足祖先过滤策略)的归结过程如下:P(x)VQ(a, b) P(a)VQ(a, b)P(a)-iP(x)VQ(x, b)Q(a,b) -i Q(a, f(a)NIL3.19 设已知：(1)能阅读的人是识字的：(2)海豚不识字；(3)有些海豚是很聪明的。请用归结演绎推理证明：有些很聪明的人并不识字。解：第一步，先定义谓词，设R(x)表示x是能阅读的：K(y)表小y是识字的：W(z)表示z是很聪明的：第二步，将已知事实和目标用谓词公式表示出来 能阅读的人是识字的：(Vx)

12、(R(x)-K(x) 海豚不识字：(Dy)K(y) 有些海豚是很聪明的：(z)W(z)有些很聪明的人并不识字：(3 x)( W(z)A-K(x) 第三步，将上述已知事实和目标的否定化成子句集：-nR(x)VK(x)*(y)w-W(z)VK(x)第四步，用归结演绛推理进行证明3.20 对子句集：PVQ,QVR.RVW, -iRV-iRWV-.Q, -nQV-iR 用线性输入策略是否可证明该子句集的不可满足性？解：用线性输入策略不能证明子句集PVQ.QVR.RVW. -nRV-iR -.WV-.Q, -1QV-1R) 的不可满足性。原因是按线性输入策略，不存在从该子句集到空子句地归结过程。3.21

13、 对线性输入策略和单文字子句策略分别给出一个反例，以说明它们是不完备的。3.22 分别说明正向、逆向、双向与/或形演绎推理的基本思想。3.23 设已知事实为(PVQ)AR) V(SA(TVU)F规则为S-(XAY)VZ试用正向演绎推理推出所有可能的子目标。解：先给出已知事实的与/或树，再利用F规则进行推理，其规则演绎系统如下图所示。由该图可以直接写出所有可能的目标子句如下：PVQVT VUPVQVXVZ PVQVYVZRVTVURVXVZRVYVZ3.24设有如下一段知识：”张、王和李都属于高山协会。该协会的每个成员不是滑雪运动员，就是登山运动员，其 中不喜欢雨的运动员是登山运动员，不喜欢雪的

14、运动员不是滑雪运动员。王不喜欢张所喜欢的 一切东西，而喜欢张所不喜欢的一切东西。张喜欢雨和雪。”试用谓词公式集合表示这段知识，这些谓词公式要适合一个逆向的基于规则的演绎系统。 试说明这样一个系统怎样才能回答问题：“高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？ ”解：(1)先定义谓词A(x)表示x是高山协会会员S(x)表示x是滑雪运动员C(x)表示x是登山运动员L(x,y)表示x喜欢y(2)将问题用谓词表示出来“张、王和李都属于高山协会A(Zhang) A A(Wang) A A(Li)高山协会的每个成员不是滑雪运动员，就是登山运动员(V x)(A(x)/S(x)f C

15、(x)高山协会中不喜欢雨的运动员是登山运动员(V x)(-1L(x, Rain)-C(x)高山协会中不喜欢雪的运动员不是滑雪运动员(V x)(L(x, Snow)-*-1 S(x)王不喜欢张所喜欢的一切东西(V y)( L(Zhang, yLL(Wang ,y)王喜欢张所不喜欢的一切东西(V y)L(Zhang. y)f L(Wang, y)张喜欢雨和雪L(Zhang , Rain)AL(Zhaiig , Snow)(3)将问题要求的答案用谓词表示出来高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员?(3 xX A(x)-C(x)A-, S(x)(4)为了进行推理，把问题划

16、分为已知事实和规则两大部分。假设，划分如下： 已知事实：A(Zhaiig) A A(Waiig) A A(Li)L(Zhang , Ram)AL(Zliaiig , Snow)规则：(V x)(A(x)AS(x)-C(x)(V Rain)-C(x)(V x)L(x, Snow)-*-1 S(x)(V y)( L(Zhang, y)-L(Wang ,y)(V y)L(Zhang. y)-L(Wang, y)(5)把已知事实、规则和目标化成推理所需要的形式事实己经是文字的合取形式：fl： A(Zhang) A A( Waiig) A A(Li)2： L (Zhang , Rain)AL(Zliang , Snow)将规则转化为后件为单文字的形式：ri： A(x) ArS(x)f C(x)n：L(x, Rain)-C(x)口:L(x. Snow)-S(x)口： L(Zhang. y)-L(Wang ,y)is：L(Zhang, y)L(Wang , y)将目标公式转换为与/或形式-A(x)V(C(x)AS(x)(6)进行逆向推理