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

第3章 确定性推理部分参考答案3.8 判断下列公式是否为可合一，若可合一，则求出其最一般合一。(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b)(4) P(f(y), y, x), P(x, f(a), f(b) (5) P(x, y), P(y, x)解：(1) 可合一，其最一般和一为：=a/x, b/y。(2) 可合一，其最一般和一为：=y/f(x), b/z。(3) 可合一，其最一般和一为：= f(b)/y, b/x。(4) 不可合一。(5) 可合一，其最一般和一为：= y/x。3.11 把下列谓词公式化成子句集：(1) (x)(y)(P(x, y)Q(x, y)(2) (x)(y)(P(x, y)Q(x, y)(3) (x)(y)(P(x, y)(Q(x, y)R(x, y)(4) (x) (y) (z)(P(x, y)Q(x, y)R(x, z) 解：(1) 由于(x)(y)(P(x, y)Q(x, y)已经是Skolem标准型，且P(x, y)Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得 P(x, y), Q(x, y) 再进行变元换名得子句集： S= P(x, y), Q(u, v) (2) 对谓词公式(x)(y)(P(x, y)Q(x, y)，先消去连接词“”得：(x)(y)(P(x, y)Q(x, y)此公式已为Skolem标准型。 再消去全称量词得子句集： S=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)此公式已为前束范式。再消去存在量词，即用Skolem函数f(x)替换y得：(x)(P(x, f(x)Q(x, f(x)R(x, f(x)此公式已为Skolem标准型。 最后消去全称量词得子句集： S=P(x, f(x)Q(x, f(x)R(x, f(x) (4) 对谓词(x) (y) (z)(P(x, y)Q(x, y)R(x, z)，先消去连接词“”得：(x) (y) (z)(P(x, y)Q(x, y)R(x, z)再消去存在量词，即用Skolem函数f(x)替换y得：(x) (y) (P(x, y)Q(x, y)R(x, f(x,y)此公式已为Skolem标准型。 最后消去全称量词得子句集：S=P(x, y)Q(x, y)R(x, f(x,y)3-13 判断下列子句集中哪些是不可满足的：(1) PQ, Q, P, P(2) PQ , PQ, PQ, PQ (3) P(y)Q(y) , P(f(x)R(a)(4) P(x)Q(x) , P(y)R(y), P(a), S(a), S(z)R(z)(5) P(x)Q(f(x),a) , P(h(y)Q(f(h(y), a)P(z)(6) P(x)Q(x)R(x) , P(y)R(y), Q(a), R(b) 解：(1) 不可满足，其归结过程为：PQQPPNIL(2) 不可满足，其归结过程为：PQPQQPQPQQNIL(3) 不是不可满足的，原因是不能由它导出空子句。(4) 不可满足，其归结过程略(5) 不是不可满足的，原因是不能由它导出空子句。(6) 不可满足，其归结过程略 3.14 对下列各题分别证明G是否为F1,F2,Fn的逻辑结论：(1) F: (x)(y)(P(x, y)G: (y)(x)(P(x, y)(2) F: (x)(P(x)(Q(a)Q(b)G: (x) (P(x)Q(x)(3) F: (x)(y)(P(f(x)(Q(f(y)G: P(f(a)P(y)Q(y)(4) 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)(5) F1: (x)(P(x)(Q(x)R(x)F2: (x) (P(x)S(x)G: (x) (S(x)R(x) 解：(1) 先将F和G化成子句集： S=P(a,b), P(x,b) 再对S进行归结：P(x,b)P(a,b)NIL a/x 所以，G是F的逻辑结论(2) 先将F和G化成子句集由F得：S1=P(x)，(Q(a)Q(b)由于G为： (x) (P(x)Q(x)，即 (x) ( P(x) Q(x)，可得： S2= P(x) Q(x)因此，扩充的子句集为：S= P(x)，(Q(a)Q(b)， P(x) Q(x) 再对S进行归结：Q(a)Q(b)Q(a) P(x) Q(x) P(a)P(x)NILQ(a)Q(b) a/b P(x) Q(x)Q(a)a/x P(a)P(x) a/xNIL 所以，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)：x是一个人 再用谓词把问题描述出来： 已知F1：(x) (y) (z)( F(x,y)F(y,z)GF(x,z) F2：(y)(P(x)F(x,y) 求证结论G：(u) (v)( P(u)GF(v,u) 然后再将F1，F2和G化成子句集： F(x,y)F(y,z)GF(x,z) P(r)F(s,r) P(u) GF(v,u) 对上述扩充的子句集，其归结推理过程如下：F(x,y)F(y,z)GF(x,z)GF(v,u)F(x,y)F(y,z)P(r)F(s,r)F(y,z)P(y)P(r)F(s,r)P(y)P(z)P(y)P(u)NIL x/v,z/ux/s,y/ry/s,z/r y/z y/u 由于导出了空子句，故结论得证。3.16 假设张被盗，公安局派出5个人去调查。案情分析时，贞察员A说：“赵与钱中至少有一个人作案”，贞察员B说：“钱与孙中至少有一个人作案”，贞察员C说：“孙与李中至少有一个人作案”，贞察员D说：“赵与孙中至少有一个人与此案无关”，贞察员E说：“钱与李中至少有一个人与此案无关”。如果这5个侦察员的话都是可信的，使用归结演绎推理求出谁是盗窃犯。解：(1) 先定义谓词和常量设C(x)表示x作案，Z表示赵，Q表示钱，S表示孙，L表示李(2) 将已知事实用谓词公式表示出来赵与钱中至少有一个人作案：C(Z)C(Q)钱与孙中至少有一个人作案：C(Q)C(S)孙与李中至少有一个人作案：C(S)C(L)赵与孙中至少有一个人与此案无关： (C (Z)C(S)，即 C (Z) C(S)钱与李中至少有一个人与此案无关： (C (Q)C(L)，即 C (Q) C(L)(3) 将所要求的问题用谓词公式表示出来，并与其否定取析取。设作案者为u，则要求的结论是C(u)。将其与其否)取析取，得： C(u) C(u)(4) 对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：C(Z)C(Q)C (Z) C(S)C(Q)C(S)C(Q)C(S)C(Q)C(u)C(u)C(Q) Q/u 因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：C(S)C(L)C (Q) C(L)C(S)C(Q)C(Q)C(S)C(S)C(u)C(u)C(S)C (Q) C(L)C(S)C(L)C(Q)C(S)C(S)C(Q)C(u)C(u)C(S) S/u C(S) 因此，孙也是盗窃犯。3.18 设有子句集： P(x)Q(a, b), P(a)Q(a, b), Q(a, f(a), P(x)Q(x, b)分别用各种归结策略求出其归结式。解：支持集策略不可用，原因是没有指明哪个子句是由目标公式的否定化简来的。删除策略不可用，原因是子句集中没有没有重言式和具有包孕关系的子句。单文字子句策略的归结过程如下：Q(a, f(a)P(x)Q(a, b) b/f(a)P(x)Q(x, b)P(a)Q(a, f(a)Q(a, b) a/x b/f(a)Q(a, b)用线性输入策略（同时满足祖先过滤策略）的归结过程如下：P(a)Q(a, b)P(x)Q(a, b)P(x)Q(x, b)P(a) a/xa/xQ(a, f(a)Q(a,b) b/f(a)NIL 3.19 设已知：(1) 能阅读的人是识字的；(2) 海豚不识字；(3) 有些海豚是很聪明的。请用归结演绎推理证明：有些很聪明的人并不识字。解：第一步，先定义谓词， 设R(x)表示x是能阅读的；K(y)表示y是识字的；W(z) 表示z是很聪明的；第二步，将已知事实和目标用谓词公式表示出来能阅读的人是识字的：(x)(R(x)K(x)海豚不识字：(y)(K (y)有些海豚是很聪明的：(z) W(z)有些很聪明的人并不识字：(x)( W(z)K(x) 第三步，将上述已知事实和目标的否定化成子句集： R(x)K(x)K (y)W(z)W(z)K(x) 第四步，用归结演绎推理进行证明W(z)W(z)K(x)W(z)K(z)NIL3.20 对子句集： PQ, QR, RW, RP, WQ, QR 用线性输入策略是否可证明该子句集的不可满足性？ 解：用线性输入策略不能证明子句集PQ, QR, RW, RP, WQ, QR 的不可满足性。原因是按线性输入策略，不存在从该子句集到空子句地归结过程。3.21 对线性输入策略和单文字子句策略分别给出一个反例，以说明它们是不完备的。3.22 分别说明正向、逆向、双向与/或形演绎推理的基本思想。3.23 设已知事实为 (PQ)R) (S(TU) F规则为 S(XY)Z试用正向演绎推理推出所有可能的子目标。解：先给出已知事实的与/或树，再利用F规则进行推理，其规则演绎系统如下图所示。由该图可以直接写出所有可能的目标子句如下： PQPQPQYRTU RXZRYZ 所有子目标UTZYXRQP所有目标UTZYXRQPYXZXYSUTTUS所有目标UTZYXRQP所有目标YZUTXPRQYXXYF规则ZXYXYZSSUTQPTUQP已知事实已知事实TUSR(PQ)TURS(PQ) (S(TU)(PQ)R) (S(TU)(PQ)R)(PQ)R) (S(TU)(PQ)R) (S(TU)3.24 设有如下一段知识：“张、王和李都属于高山协会。该协会的每个成员不是滑雪运动员，就是登山运动员，其中不喜欢雨的运动员是登山运动员，不喜欢雪的运动员不是滑雪运动员。王不喜欢张所喜欢的一切东西，而喜欢张所不喜欢的一切东西。张喜欢雨和雪。”试用谓词公式集合表示这段知识，这些谓词公式要适合一个逆向的基于规则的演绎系统。试说明这样一个系统怎样才能回答问题：“高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？”解：(1) 先定义谓词A(x) 表示x是高山协会会员S(x) 表示x是滑雪运动员C(x) 表示x是登山运动员L(x,y) 表示x 喜欢y (2) 将问题用谓词表示出来“张、王和李都属于高山协会A(Zhang)A(Wang)A(Li)高山协会的每个成员不是滑雪运动员，就是登山运动员(x)(A(x)S(x)C(x)高山协会中不喜欢雨的运动员是登山运动员(x)(L(x, Rain)C(x)高山协会中不喜欢雪的运动员不是滑雪运动员(x)(L(x, Snow) S(x)王不喜欢张所喜欢的一切东西(y)( L(Zhang, y) L(Wang ,y) 王喜欢张所不喜欢的一切东西(y)( L(Zhang, y)L(Wang, y)张喜欢雨和雪L(Zhang , Rain)L(Zhang , Snow)(3) 将问题要求的答案用谓词表示出来高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？ (x)( A(x)C(x) S(x) (4) 为了进行推理，把问题划分为已知事实和规则两大部分。假设，划分如下：已知事实：A(Zhang)A(Wang)A(Li)L(Zhang , Rain)L(Zhang , Snow)规则：(x)(A(x)S(x)C(x)(x)(L(x, Rain)C(x)(x)(L(x, Snow) S(x)(y)( L(Zhang, y) L(Wang ,y)(y)( L(Zhang, y)L(Wang, y) (5) 把已知事实、规则和目标化成推理所需要的形式事实已经是文字的合取形式：f1: A(Zhang)A(Wang)A(Li)f2: L (Zhang , Rain)L(Zhang , Snow)将规则转化为后件为单文字的形式：r1: A(x)S(x)C(x)r2: L(x, Rain)C(x)r3: L(x, Snow) S(x)r4: L(Zhang, y) L(Wang ,y)r5: L(Zhang, y)L(Wang , y) 将目标公式转换为与/或形式 A(x)(C(x) S(x) (6) 进行逆向推理逆向推理的关键是要能够推出L(Zhang , Rain)L(Zhang , Snow)，其逆向演绎过程如下图所示。 A(x)(C(x) S(x)C(x) S(x) A(x)C(x) S(x)r2r34L(x, Rain)L(x, Snow)Wang/x, y/RainWang /x, y/SnowL(Wang, y)L(Wang, y)r4r4L(Zhang, y)L(Zhang, y)Rain/ySnow/yL(Zhang, Snow)L(Zhang, Rain)10