1、第三章确定性推理方法习题参考解答3.1练习题3.1 什么是命题？请写出 3 个真值为 T 及真值为 F 的命题。3.2 什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？3.3 谓词逻辑和命题逻辑的关系如何？有何异同？3.4 什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。3.5 什么是谓词公式？什么是谓词公式的解释？设 D=1,2,试给出谓词公式(x)(y)(P(x,y)Q(x,y)的所有解释，并且对每一种解释指出该谓词公式的真值。3.6 对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。(1)(x)(P(x,y)(y)(Q(x,y)R(x,y)(z)
2、(y)(P(z,y)Q(z,x)R(u,v)(x)(P(x,f(x)(z)(Q(x,z)R(x,z)(4)(z)(y)(t)(P(z,t)Q(y,t)R(z,y)5(z)(y)(P(z,y)(z)(y)(P(z,y)Q(z,y)(z)Q(z,y)3.7 什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含?3.8 什么是置换？什么是合一？什么是最一般的合一?3.9判断以下公式对是否可合P(x,y)一；若可合一，则求出最一般的合一:P(y,x)(1)P(a,b),(2)P(f(z),b),P(y,f(a) P(x,f(a),f(b)P(f(x),y),(4)P(f(y),y,x), (5)
3、P(x,y),P(y,x)3.10 什么是范式？请写出前束型范式与 SKOLEM 范式的形式3.11 什么是子句？什么是子句集？请写出求谓词公式子句集的步骤3.12 谓词公式与它的子句集等值吗？在什么情况下它们才会等价？3.13 把下列谓词公式分别化为相应的子句集：(1)(z)(y)(P(z,y)Q(z,y)(2)(x)(y)(P(x,y)Q(x,y)(x)(y)(P(x,y)(Q(x,y)R(x,y)(4)(x)(y)(z)(P(x,y)Q(x,y)R(x,z)(5)(x)(y)(z)(u)(v)(w)(P(x,y,z,u,v,w)(Q(x,y,z,u,v,w)R(x,z,w)3.14 判断
4、下列子句集中哪些是不可满足的：(1) SPQ,Q,P,P(2) SPQ,PQ,PQ,PQ (3)SP(y)Q(y),P(f(x)R(a)(4)SP(x)Q(x)，P(y)R(y),P(a),S(a),S(z)R(z)(5)SP(x)Q(y)L(x,y),P(a),R(z)L(a,z),R(b),Q(b)(6)SP(x)Q(f(x),a),P(h(y)Q(f(h(y),a)P(z)(7)SP(x)Q(x)R(x),P(y)R(y),Q(a),R(b)1.1 SP(x)Q(x)，Q(y)R(y),P(z)Q(z),R(u)3.15 为什么要引入 Herbrand 理论？彳 f 么是 H 域？如何求
5、子句集的 H 域？3.16 什么是原子集？如何求子句集的原子集？3.17 什么是 H 域解释？如何用域 D 上的一个解释 I 构造 H 域上的解释 I*呢？3.18 假设子句集 S=P(z)VQ(z),R(f(t),S 中不出现个体常量符号。设个体域 D=1,2。由 H 域和原子集的定义：H=a,f(a),f(f(a), A=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),如果设 I 是 D 上的解释，并作如下的设定1: f(1)f(2)P(1)P(2)Q(1)Q(2)R(1)R(2)22TFFTFT请构造 H 域上的一个解释 I*与 I 相对应，且使 S|I*=TO3
6、.19 引入 Robinson 的归结原理有何意义？其基本思想是什么？3.20 请写出应用归结原理进行定理证明的步骤。3.21 对下列各题分别证明 G 是否为 Fi,F2,，Fn 的逻辑结论Fi:(x)(y)P(x,y)G：(y)(x)P(x,y)Fi:(x)(P(x)(Q(a)Q(b) G：(x)(P(x)Q(x)Fi:(x)(y)(P(f(x)Q(f(b)G:P(f(a)P(y)Q(y)Fi:(x)(P(x)(y)(Q(y)L(x,y)F2：(x)(P(x)(y)(R(y)L(x,y)Fi:(x)(P(x)F2:(x)(P(x)G：(x)(S(x)(Q(x)R(x) S(x)R(x)G：(
7、x)(R(x)Q(x)(6)Fl:(z)(A(z)-B(Fz2) :(z)(E(z)A(z)(y)(D(z,y)E(y) F3:(z)(E(x)B(z)G：(z)(E(z)C(z)(y)(D(z,y)C(y)3.22 证明：(y)(Q(y)(B(y)C(y)(y)(Q(y)D(y)(y)(D(y)C(y)3.23 某单位招聘工作人员，张三、李四、王五三人应试，经面试后单位有如下想法:(i) 如果录取张三而不录取李四，则一定录取王五。(2)如果录取李四，则一定录取王五。(3) 三人中至少要录取一人。求证：王五一定会被单位录取。3.24 每个储蓄钱的人就是为了获得利息。求证：对某个人来说，如果不能
8、获得利息，则他就不会储蓄钱。3.25 请写出利用归结原理求解问题答案的步骤。3.26 应用归结原理求解下列问题：设张三、李四和王五三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题:谁是说假话者？张三答：“李四和王五都是说假话者”；李四答：“张三和王五都是说假话者 ；王五答：“张三和李四中至少有一个说假话者”。求谁是说假话者，谁是说真话者？3.27 已知樊臻的老师是张先生，樊臻与李伟是同班同学。如果 x 与 y 是同班同学，则 x 的老师也是 y的老师。请问李伟的老师是谁？3.28 什么是完备的归结控制策略？有哪些归结控制策略是完备的？3.29 设已知：(1)能阅读的人是识
9、字的。(2)海豚不识字。(3)有些海豚是很聪明的。用输入归结策略证明：有些很聪明的人并不识字。3.30 用输入归结策略是否可证明下列子句集的不可满足性？S=PVQ,QVR,RVW,RVP,WVQ,QVR习题参考解答3.23.3答：(略)3.4答：(略)3.5答：(略)3.6答：(略)3.7 解：在谓词公式(x)(y)(P(x,y)Q(x,y)中没有包括个体常量和函数，所以，可以直接为谓词指派真值。设：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=FQ(1,1)=T,Q(1,2)=F,Q(2,1)=T,Q(2,2)=F在这种解释下，对某一个 x(x=1 或 x=2)对所有的
10、 y(即 y=1 或 y=2)都不能使 P(x,y)的真值为 T,所以，在此解释下，P(x,y)的真值为 F。同理，Q(x,y)的真值也为 F。根据谓词逻辑真值表可知：在该解释下，上述谓词公式的真值为 To上述谓词公式在 D=1,2上共有 256 种解释，这里不再一一列出，读者可自己列出其中的几个，并求出其真值。3.8 解：(1) P(x,y),Q(x,y)和 R(x,y)中的 x 以及 Q(x,y),R(x,y)中的 y 是约束变元。P(x,y)中的 y 是自由变元。量词x 的辖域使整个公式，量词 y 的辖域是(Q(x,y)R(x,y)。(2) z 和y 是约束变元。x,u,v 是自由变元。
11、z 和y 辖域都是 P(z,y)Q(z,x)。(3) x 和z 均是约束变元。没有自由变元。x 的辖域是整个公式，z 的辖域是 Q(x,z)R(x,z)。(4) z、y 和t 均是约束变元。没有自由变元。z 和y 的辖域是整个公式，t 的辖域是 P(z,t)Q(y,t)。(5)本小题比较复杂，表面上只涉及两个变元 z 和 y,实际上公式中后面的两个 z 和一个y 都可看成是另外的变量，因此，可作变元替换将公式变换为：(z)(y)(P(z,y)(z)(y1)(P(z,y)Q(z,y)(z)Q(z,y)公式中的变元就成为 z、y、z、y、z五个变元。z 和y 的辖域是整个公式，z和 y的辖域是 P
12、(z,y)Q(z,y)(z)Q(z,y),而 z为 Q(z,y)3.7 答：(略)3.8 答：(略)3.9 解：(1) P(a,b)与 P(x,y)是可合一的。(T=a/x,b/y(2) P(f(z),b)与 P(x,y)是可合一的。b=f(z)/x,b/y(3) P(f(x),y)与 P(y,f(a)是可合一的。根据最一般合一求取算法，可得 b=f(a)/y,a/x(4) P(f(y),y,x)与 P(x,f(a),f(b)是不可合一的。(5) P(x,y)与 P(y,x)是可合一的。(T=y/x或=x/y3.10 答：范式就是标准型。谓词演算中，一般有两种范式，一种叫前束形范式，另一种叫斯
13、克林(Skolem)范式。一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且 它的辖域一直延伸到公式之末，同时公式中不出现连接词及，这种形式的公式称作前 束形范式。它的一般形式是(QIX1)(Q2X2)(Qxn)M(x1,x2,，x)其中，Qi(i=1,2,n)是存在量词或全称量词，而母式 M(xi,X2,x)不再含有量词。从前束形范式中消去全部存在量词所得到的公式称为 Skolem 标准型，它的一般形式是(Xl)(X2)(Xn)M(X1,X2，,Xi)3.11 答：子句就是由一些文字组成的析取式。而所谓文字是指原子或原子的否定。不含有任何 连接词的谓词公式叫做原子或原子公式。由子
14、句构成的集合称为子句集。求谓词公式G 的子句集的步骤如下：(a) 消去谓词公式 G 中的蕴涵(-)和双条件符号()，以AVB 代替 A-B,以(AAB)V(AAB)替换 AB。(b) 减少否定符号()的辖域，使否定符号“”最多只作用到一个谓词上。(c) 重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。(d) 消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域内，此时，只要用一个新的个体常量替换该存在量词约束的变元，就可以消去存在量词；另 一种情况是，存在量词位于一个或多个全称量词的辖域内，例如，(X1)(X2)(Xn)(y)P(X1,X2，Xi,y)
15、此时，变元 y 实际受前面的变元 XI , X2,，xn 的约束，需要用 Skolem 函数 f(x1,X2,K)替换 y 即可将存在量词y 消去，得到：(X1)(X2)(Xn)P(X1,X2，X,f(x1,X2,x)(e) 把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整 个部分。(f) 母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的有限集组成的 合取。(g) 消去全称量词。(h) 对变元进行更名，是不同子句中的变元不同名。(1)消去合取符号 A,将各子句写成子居积合的形式。3.12 答：(略)3.13 解：(1) 因为(z)(y)(P(z,
16、y)Q(z,y)已经是一个 Skolem 标准型，P(z,y)Q(z,y)已是合取范式，以逗号代替，得子句集：S=P(z,y),Q(z,y)(2) 首先将谓词公式(x)(y)(P(x,y)Q(x,y)化为 Skolem 标准型：(x)(y)(P(x,y)Q(x,y)消去全称量词，并将母式化为子句集S= P(x,y)Q(x,y)(3) 首先将谓词公式(x)(y)(P(x,y)(Q(x,y)R(x,y)化为 Skolem 标准型： 第一步：消去号(x)(y)(P(x,y)(Q(x,y)R(x,y)第二步：消去存在量词，用 Skolem 函数 f(x)代替 y (x)(P(x,f(x)Q(x,f(x
17、)R(x,f(x)第三步：消去全称量词，并将母式化为子句集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)化为 Skolem 标准型: 第一步：消去号(x)(y)(z)(P(x,y)Q(x,y)R(x,z)第二步：消去存在量词，用 Skolem 函数 f(x,y)代替 z (x)(y)(P(x,y)Q(x,y)R(x,f(x,y)第三步：消去全称量词，并将母式化为子句集S=P(x,y)Q(x,y)R(x,f(x,y)将谓词公式(x)(y)(z)(u)(v)(w)(P(x,y,z,u,v,w)(Q(x,y,z,u,
18、v,w)R(x,z,w) 化为 Skolem 标准型：第一步：消去存在量词 x,y,以常量 a,b 分别代之(z)(u)(v)(w)(P(a,b,z,u,v,w)(Q(a,b,z,u,v,w)R(a,z,w)第二步：消去存在量词 u,由于 u 在全称量词 z 的辖域内，令 Skolem 函数 u=f(z) (z)(v)(w)(P(a,b,z,f 亿),v,w)(Q(a,b,z,f 亿),v,w)R(a,z,w)再消去存在量词 w,由于 w 在全称量词 z 和v 的辖域内，令 Skolem 函数 w=g(z,v) (z)(v)(P(a,b,z,f(z),v,g(z,v)(Q(a,b,z,f(z)
19、,v,g(z,v)R(a,z,g(z,v)第三步：消去全称量词，并将母式化为合取范式，再化为子句集S=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)3.14 解(1) 依照归结推理过程，对子句集 SPQ,Q,P,P进行归结推理1) PQ2) Q3) P4) -P5) NIL3),4)归结所以，该子句集是不可满足的。同理，可以推知第(2)、(4)、(5)、(8)小题的子句集 也是不可满足的，因为它们都可以归结出空子句。3.15 答：引入 Herbrand 理论的目的是为了简化对谓词公式不可满足性的证明。对于一个谓词公式来说，要证明它
20、的不可满足性是困难的，故考虑它的子句集的不可满足性。然而，对子句集的不可满 足性的判定仍然是困难的，因为要判断子句集的不可满足性就要对子句集中的每一个子句逐个进行判定。由于个体变元域 D 的任意性以及解释个数的无限性，这实际上是一项难以完成的工作。能否针对某一个具体的谓词公式，找到一个比较简单的特殊域，只要 使谓词公式在该特殊域上是不可满足的，就能保证它在任一域上也是不可满足的呢？ Herbrand 理论就构造了这样的一个域，称为 Herbrand 域(H 域)。只要对H 域上的所有解释进行判定，即可得知谓词公式是否是不可满足的。H 域的定义中就包含了子句集 H 域的求取方法：设谓词公式 G
21、的子句集为 S,则按下述方法构造的个体变元域 H 称为公式 G 或子句集S 的 Herbrand 域，简称H 域。(a) 令H0 是S 中所出现的常量的集合。若 S 中没有常量出现，就任取一个常量 aD,规定H0=a。(b) 令Hi+1=HiUS 中所有的形如 f(t1,t)的元素其中 f(t1,用是出现于 G 中的任一函数符号，而 t1,，tn 是Hi 中的元素。i=0,1,2,。3.16 答：下列集合称为子句集 S 的原子集： A=所有形如 P(ti,t2,&的元素其中，P(tl,t2,t)是出现在 S 中的任一谓词符号，而 tl,t2,，tn 则是S 的H 域上的任意元素。该定义就给出了
22、子句集的原子集的求法。3.17 答：如果子句集S 的原子集为 A,则对 A 中各元素的真假值的一个具体设定都是 S 的一个H解释。用域D 上的一个解释 I 构造 H 域上的解释 I*的方法如下： (1)求子句集 S 的H 域和原子集A(2) 根据 D 域上的解释 I,对 H 域中的每个元素设定相应的值。如果 H 域中有常量符号， 可按D 中的元素给 a 设定某一值。(3) 依据 H 中各元素的值与解释 I 的规定，确定原子集 A 中各元素的取值。这样，原子集A 中的各个元素都得到了一个取值，它就是与 D 上的解释 I 相对应的 H域上的解释 I*。3.18 解：已知个体域 D=1,2,I 是
23、D 上的解释，并作如下的设定f(1)f(2)P(1)P(2)Q(1)Q(2)R(1)R(2)22TFFTFT将以上各值代入 S,有 S|I=T。现在要构造 H 域上的一个解释 I*与 I 相对应，且使 SI*=T。依据D 域上的解释 I 之规定，对H 域中的每个元素设定相应的值。在H 中的常量符号有 a,f(a),f(f(a), 这时，由于a 在解释 I 中并未给出规定，所以我们要按D 中的元素给 a 设定值，a 可以设定为 1,也可以设定为 2(因为 1,2 都是D 的元素)。若a 设定成 1,则依照解释 I,H 中的其他元素的值即确定如下： f(a)-f(1)-2f(f(a)-f(2)-2
24、f(f(f(a)f(2)2再依据H 中各元素的值与解释 I 的规定，确定原子集 A 中各元素的取值: P(a)-PfTQ(a)-Q(1)-FR(a)-R(1)-FP(f(a)-P(2)-FQ(f(a)-Q(2)-TR(f(a)-R(2)-T于是，便得到与D 域上解释I 相对应的 H 域上的解释 I*i： I*i=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),同理，若将H 中的元素 a 设成 2,我们可以得到与 I 相对应的另一个 H 解释 I*2:I*2=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),*2可以验证 S|I*i=T,S|I =T
25、O 解释I*i、I*2 便是所求的与 D 域上解释 I 相对应的 H 域之解释。3.19 答：(略)3.20 答：设要被证明的定理可用谓词公式表示为形式 A1AA2AAAn-B,则应用归结原理进行定理证明的步骤如下：(1) 首先否定结论 B,并将否定后的公式B 与前提公式集组成如下形式的谓词公式：G=A1AA2AAAnAB(2) 求谓词公式 G 的子句集 So(3) 应用归结原理，证明子句集 S 的不可满足性，从而证明谓词公式G 的不可满足性。这就说明对结论B 的否定是错误的，推断出定理的成立。3.21 解：1(1)F :(x)(y)P(x,y)G:(y)(x)P(x,y)首先将 F1 和G
26、化为子句集1)P(a,b)2)P(x,b)然后利用归结原理进行归结3)NIL1)与 2)归结，d=a/x所以G 是Fi 的逻辑结论。(2)首先将 Fi 和G 化为子句集Fi：(x)(P 但(Q(a)Q(b),由于 Fi 本身就是 Skelom 标准型，所以有Si=P(x),Q(a)Q(b)G=(x)(P(x)Q(x)所以，S2=-P(x)Q(x) 下面进行归结1) P(x)2) Q(a)Q(b)3)P(x)Q(x)4)-Q(x)1),3)归结5)Q(b)2),4)归结 b=a/x6)NIL4),5)归结(r=b/x所以G 是Fi 的逻辑结论。其余各题的证明留给读者自己练习。3.22 证明：第一
27、步：先对结论否定并与前提合并得谓词公式 GG=(y)(Q(y)-(B(y)AC(y)A(y)(Q(y)AD(y)A(y)(D(y)AC(y)第二步：将公式G 化为子句集，可将G 看作三项的合取，对每一项分别求子句集Gi：(y)(Q(y)-(B(y)AC(y)=(y)(Q(y)V(B(y)AC(y)=(y)(Q(y)VB(y)A(Q(y)VC(y)所以，Si=(Q(y)VB(y),Q(y)VC(y)。G2：(y)(Q(y)AD(y)所以，S2=Q(a),D(a)。B:(y)(D(y)AC(y)=(y)(D(y)VC(y)所以，SB= D(y)VC(y)。从而得公式G 的子句集：S=SiUS2US
28、B=(Q(y)VB(y),Q(y)VC(y),Q(a),D(a),D(y)VC(y)第三步：使用归结原理，对子句集 S 进行归结。(1) Q(y)VB(y)(2) Q(y)VC(y)(3) Q(a)(4) D(a)(5) D(y)VC(y)(6)C(a)(2)与(3)归结 b=a/y(7)C(a)(4)与(5)归结 b=a/y (8)NIL(6)与(7)归结由此得出子句集 S 是不可满足的，因而公式G 也是不可满足的，从而命题得证。3.23 证明：第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。a) )定义谓词和常量： 谓词 Matr(x)表示 x 被录取。Z 表不张
29、三，L 表不李四，W 表不王五。b) )将前提及要证的问题表示成谓词公式：c) Matr(Z)AMatr(L)-Matr(W)d) Matr(L).Matr(W)e) Matr(Z)VMatr(L)VMatr(W)把要求证的问题否定，并用谓词公式表示出来：d)Matr(W)第二步：将上述公式化成子句集。1) Matr(Z)VMatr(L)VMatr(W)2) Matr(L)VMatr(W)3) Matr(Z)VMatr(L)VMatr(W)4) Matr(W)第三步：利用归结原理对上面的子句集中的子句进行归结。5) Matr(L)VMatr(W)1)与 3)归结6) Matr(W)2)与 5)
30、归结7) NIL4)与 6)归结所以，王五一定会被录取。3.24 证法一：第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。 定义谓词：设：Save(x):表示 x 储蓄钱；Interest(x)：表示 x 获得利息。将前提表示成谓词公式：(x)(Save(x)Interest(x)把要求证的问题用谓词公式表示出来：(y)(Interest(y)Save(y)第二步：将前提和要求证的问题之否定化成子句集。求前提子句集：(x)(Save(x)Interest(x)(x)(Save(x)Interest(x)前提的子句集：S1=Save(x)Interest(x) 求结论之
31、否定子句集：(y)(Interest(y)Save(y)(y)(Interest(y)Save(y)(y)(Interest(y)Save(y)结论之否定子句集：S2=Interest(y),Save(y)第三步：利用归结原理对上面的子句集中的子句进行归结(1) Save(x)Interest(x)(2) Interest(y)Save(y)(4) Save(y)(1),(2)归结=x/y (5)NIL(3),(4)归结证毕。证法二：第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。 定义谓词：设：Save(x,y)：表示 x 储蓄 y;Money(y):表示 y 是钱
32、； Interest(y)：表示 y 是利息； Obtain(x,y):表示 x 获彳导 y。将前提表示成谓词公式：(x)(y)(Money(y)Save(x,y)(u)(Interest(u)Obtain(x,u)把要求证的问题用谓词公式表示出来：(x)(u)(Interest(u)Obtain(x,u)(y)(Money(y)Save(x,y)第二步：将前提和要求证的问题之否定化成子句集。求 前 提 子 句 集 ： (x)(y)(Money(y)Save(x,y)(u)(Interest(u)Obtain(x,u)(x)(y)(Money(y)Save(x,y)(u)(Interest(u
33、)Obtain(x,u)(x)(y)(Money(y)Save(x,y)(u)(Interest(u)Obtain(x,u)设 skolem 函数为 u=f(x),则:前提的子句集：S1=Money(y)Save(x,y)Interest(f(x),Money(y)Save(x,y)Obtain(x,f(x)求结论之否定子句集：(x)(u)(Interest(u)Obtain(x,u)(y)(Money(y)Save(x,y)(x)(u)(Interest(u)Obtain(x,u)(y)(Money(y)Save(x,y)(x)(u)(Interest(u)Obtain(x,u)(y)(Mo
34、ney(y)Save(x,y)设 skolem 函数为 y=g(x),则上式变为：(x)(u)(Interest(u)Obtain(x,u)(Money(g(x)Save(x,g(x)结论之否定子句集：S2=Interest(u)Obtain(x,u),Money(g(x),Save(x,g(x)第三步：利用归结原理对上面的子句集中的子句进行归结(1) Money(y)Save(x,y)Interest(f(x)(2) Money(y)Save(x,y)Obtain(x,f(x)(3) Interest(u)Obtain(x,u)(4) Money(g(x)(5) Save(x,g(x)Sav
35、e(x,y)Obtain(x,f(x)(6)Money(y)(1),(3)归结f(x)/u(7) Money(y)Save(x,y)(2),(6)归结归结(8) Money(g(x)(5),(7)b=g(x)/y(9) NIL(4),(8)归结证毕。(10) 答：利用归结原理求取问题答案的步骤如下:(1) 把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S。I(2) 把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词 ANSWER 构成析取式。谓词ANSWER 是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。(3) 把问题公式与谓词 ANS
36、WER 构成的析取式化为子句集，并把该子句集与 Si 合并构成子句集 So(4) 对子句集 S 应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变 ANSWER 中的变元。(5) 如果得到归结式 ANSWER,则问题的答案即在 ANSWER 谓词中。(11) 解：第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。(1) 定义谓词和常量：设 P(x)表小 x 说真 tIfoZ 表小张三，L 表小李四，W 表小王五。(2) 将已知事实用谓词公式表示出来。若张三说的是真话，则有 P(Z)fP(L)AP(W)若张三说的是假话，则有P(Z)-P(L)VP(W)对李四和王五说
37、的话做同样的处理，可得：P(L)-P(Z)AP(W)P(L)-P(Z)VP(W)P(W)-P(Z)VP(L)P(W)-P(Z)AP(L)(3) 将它们化成子句集得 S:1) P(Z)VP(L)2) P(Z)VP(W)3) P(Z)VP(L)VP(W)4) P(L)VP(W)5) P(W)VP(Z)VP(L)6) P(W)VP(Z)第二步：把问题用谓词公式表示出来，并将其否定与谓词 ANSWER 作析取。设u 是说真话者，则有：P(u)。将其否定与 ANSWER 作析取，得：G:P(u)VANSWER(u)将上述公式G 化为如下的子句，并将其合并到 So8) P(u)VANSWER(u)第三步：
38、应用归结原理对上述子句集进行归结9) P(Z)VP(W)1)与 7)归结10)P(W)6)与 9)归结11)ANSWER(W)8)与 10)归结 b=W/u第四步：得到的归结式 ANSWER(W),答案即在其中，u=W,所以，求得王五是说真除此之外，无论对上述子句集如何进行归结，都推不出 ANSWER(Z)和 ANSWER(L)来,说明张三和李四不是说真话者。其实可以证明张三和李四是说假话者。证明的方法是设张三或李四是说假话者，则有：P(Z)或P(L)作为要证明的结论，将它的否定之子句并入前面的子句集 1)7),并进行归结推理，推出空子句，从而证明假设的正确性，即张三和李四是说假话者。3.27
39、 解：第一步：定义谓词，并将已知条件用谓词公式表示出来，并化成子句集。(1) 定 义 谓 词 和 常 量 ： Teacher(x,y)表示 x 是y 的老师。Classmate(x,y)表示 x 和y 同班同学Fz 表示樊臻，Lw 表示李伟，Zm 表示张先生。(2) 将已知事实用谓词公式表示出来。樊臻的老师是张先生：Teacher(Zm,Fz)樊臻与李伟是同班同学：Classmate(Fz,Lw)如果x 与y 是同班同学，则 x 的老师也是y 的老师：(x)(y)(z)(Classmate(x,y)Teacher(z,x)Teacher(z,y)(3)1)2)3)将它们化成子句集得 S:Tea
40、cher(Zm,Fz) Classmate(Fz,Lw)Classmate(x,y)VTeacher(z,x)VTeacher(z,y)第二步：把问题用谓词公式表示出来，并将其否定与谓词 ANSWER 作析取。设李伟的老师是 u,则有：Teacher(u,Lw)。将其否定与 ANSWER 作析取，并求子句且把所得子句并入上述子句集：4) Teacher(u,Lw)VANSWER(u)第三步：应用归结原理对上述子句集进行归结5) Classmate(Fz,y)VTeacher(Zm,y)6) Classmate(Fz,Lw)VANSWER(Zm)7) ANSWER(Zm)1) 与 3)归结 b=
41、Fz/x,Zm/z4)与 5)归结 b=Lw/y,Zm/u2)与 6)归结第四步：得到的归结式 ANSWER(W)，答案即在其中，u=Zm,即李伟的老师是张先生。3.28 答：(略)3.29 证明第一步：定义谓词，并将已知条件用谓词公式表示出来，并化成子句集。1) )定义谓词和常量： Read(x)表示 x 是能阅读的； Know(y)表示 y 是识字的；Wise(z)表示 z 是很聪明的；用r 表示人类，用 h 表示海豚.2) )将已知事实用谓词公式表示出来。能阅读的人是识字的：(r)(Read(r)Know(r) 海豚不识字：(h)(Know(h)有些海豚是很聪明的：(h)(Wise(h)
42、3) )将要证明的目标转化为谓词有些很聪明的人并不识字：(r)(Wise(r)Know(r)第二步：将它们化成子句集4) Read(r)VKnow(r)5) -Know(h)6) Wise(a)7) -Wise(r)VKnow(r)第三步：对以上子句集进行归结8) Know(a)3)与 4)归结 o-=a/r9) NIL2)与 5)归结(T=a/h从而命题得证。3.30 解利用输入归结策略不能证明子句集S=PVQ,QVR,RVW,RVP,WVQ,QVR的不可满足性。因为按照输入归结策略的要求，每次参加归结推理的两个子句中，必须至少 有一个子句是初始子句集中的子句。另外，要特别注意的是，在进行归结时，不能同时消去 两个互补文字对，因为消去两个互补文字对所得到的结果，不是两个亲本子句的逻辑推论。例如，在本题中，子句 QVR 和QVR 不能进行归结，因为它们归结时将消去两个文字对。所以，根据这些要求，将不能从该子句集中归结出空子句，也就是说，不能证明该子句集的不可满足性。
