第3章参考答案

13.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))}23-13判断下列子句集中哪些是不可满足的：(1){¬P∨Q,¬Q,P,¬P}(2){P∨Q,¬P∨Q,P∨¬Q,¬P∨¬Q}(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)不可满足，其归结过程为：(2)不可满足，其归结过程为：(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))¬P∨Q¬Q¬PPNILP∨Q¬P∨QQP∨¬Q¬P∨¬Q¬QNIL3(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进行归结：{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进行归结：{a/b}{a/x}{a/x}所以，G是F的逻辑结论同理可求得(3)、(4)和(5)，其求解过程略。3.15设已知：(1)如果x是y的父亲，y是z的父亲，则x是z的祖父；(2)每个人都有一个父亲。使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。解：先定义谓词F(x,y)：x是y的父亲P(a,b)¬P(x,b)NILQ(a)∨Q(b)Q(a)¬P(x)∨¬Q(x)¬P(a)P(x)NILQ(a)∨Q(b)Q(a)¬P(x)∨¬Q(x)¬P(a)P(x)NIL4GF(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))对上述扩充的子句集，其归结推理过程如下：{x/v,z/u}{x/s,y/r}{y/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)¬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)NIL5孙与李中至少有一个人作案：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)对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：{Q/u}因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：{S/u}因此，孙也是盗窃犯。3.18设有子句集：{P(x)∨Q(a,b),P(a)∨Q(a,b),Q(a,f(a)),P(x)∨Q(x,b)}分别用各种归结策略求出其归结式。解：支持集策略不可用，原因是没有指明哪个子句是由目标公式的否定化简来的。删除策略不可用，原因是子句集中没有没有重言式和具有包孕关系的子句。单文字子句策略的归结过程如下：C(Z)∨C(Q)¬C(Z)∨¬C(S)C(Q)∨¬C(S)C(Q)∨C(S)C(Q)¬C(u)∨C(u)C(Q)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(S)∨C(L)¬C(Q)∨¬C(L)C(S)∨¬C(Q)C(Q)∨C(S)C(S)¬C(u)∨C(u)C(S)6{b/f(a)}{a/x}{b/f(a)}用线性输入策略（同时满足祖先过滤策略）的归结过程如下：{a/x}{a/x}{b/f(a)}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)P(x)∨Q(a,b)P(a)∨Q(a,b)P(a)P(x)∨Q(x,b)Q(a,b)Q(a,f(a))NILP(x)∨Q(a,b)Q(a,f(a))P(a)P(x)∨Q(x,b)Q(a,b)Q(a,f(a))Q(a,b)7¬K(y)W(z)¬W(z)∨K(x))第四步，用归结演绎推理进行证明3.20对子句集：{P∨Q,Q∨R,R∨W,R∨P,W∨Q,Q∨R}用线性输入策略是否可证明该子句集的不可满足性？解：用线性输入策略不能证明子句集{P∨Q,Q∨R,R∨W,R∨P,W∨Q,Q∨R}的不可满足性。原因是按线性输入策略，不存在从该子句集到空子句地归结过程。3.23设已知事实为((P∨Q)∧R)∨(S∧(T∨U))F规则为S→(X∧Y)∨Z试用正向演绎推理推出所有可能的子目标。解：先给出已知事实的与/或树，再利用F规则进行推理，其规则演绎系统如下图所示。由该图可以直接写出所有可能的目标子句如下：P∨Q∨Ｔ∨ＵP∨Q∨Ｘ∨ＺP∨Q∨Y∨ＺR∨T∨UR∨X∨ZR∨Y∨Z¬W(z)∨K(x))W(z)K(z)W(z)NILX∧YZXYPQRXYZTU所有目标PQRXYZTU所有目标SX∧YZXYPQRXYZTU所有目标F规则X∧YZXYPQRXYZTU所有子目标83.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(