人工智能教程习题及答案第3章习题参考解答

第三章确定性推理方法习题参考斛答

3.1练习题

3.1什么是命题？请写出3个真值为T及真值为F的命题。

3.2什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？

3.3谓词逻辑和命题逻辑的关系如何？有何异同？

3.4什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。

3.5什么是谓词公式？什么是谓词公式的解释？设口={1,2},试给出谓词公式

(3x)(Vy)(P(x,y)-Q(%y))

的所有解释，并且对每一种解释指出该谓词公式的真值。

3.6对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。

⑴(Vx)(P(x,y)v(3y)(Q(x,y)AR(X,y)))

(2)(3z)(Vy)(P(z,y)vQ(z,x))vR(u,v)

(3)(Vx)(~P(x,f(x))v(3z)(Q(x,Z)A~R(x,z)))

(4)(Vz)((3y)(0t)(P(z,t)vQ(y,t))AR(z,y))

(5)(Vz)(3y)(P(z,y)v(3z)((Vy)(P(z,y)AQ(z,y)V(3z)Q(z,y))))

3.7什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含？

3.8什么是置换？什么是合一？什么是最一般的合一？

3.9判断以下公式对是否可合一；若可合一，则求出最一般的合一：

(1)P(a,b),P(x,y)

(2)P(f(z),b),P(y,x)

(3)P(f(x),y),P(yJ(a))

(4)P(f(y),y,x),P(x,f(a),f(b))

(5)P(x,y),P(y,x)

3.10什么是范式？请写出前束型范式与SKOLEM范式的形式。

3.11什么是子句？什么是子句集？请写出求谓词公式子句集的步骤。

3.12谓词公式与它的子句集等值吗？在什么情况下它们才会等价？

3.13把下列谓词公式分别化为相应的子句集：

(1)(Vz)(Vy)(P(z,y)AQ(z,y))

(2)(Vx)(Vy)(P(x,y)->Q(x,y))

<3)(Vx)(3y)(P(x,y)v(Q(x,y)fR(x,y)))

(4)(Vx)(Vy)(3z)(P(x,y)Q(x,y)vR(x,z))

(5)(3x)(3y)(Vz)(3u)(Vv)(3w)(P(x,y,z,u,v,w)A(Q(X,y,Z,U,V,W)V~R(x,z,w)))

3.14判断下列子句集中哪些是不可满足的：

(1)S={~PvQ,~Q,P,~P)

(2)S={PvQ,~PvQ,Pv~Q,~Pv~Q}

(3)S={P(y)vQ(y),~P(f(x))vR(a)}

(4)S={~P(x)vQ(x),~P(y)vR(y),P(a),S(a),~S(z)v~R(z)}

(5)S={~P(x)v~Q(y>/~L(x,y),P(a),~R(z)vL(a,z),R(b),Q(b)}

(6)S={~P(x)vQ(f(x),a),~P(h(y))vQ(f(h(y))3)v~P(z)}

(7)S={P(x)vQ(x)vR(x),~P(y)vR(y),~Q(a),~R(b)}

(8)S={P(x)vQ(x),~Q(y)vR(y),~P(z)vQ(z),~R(u)}

3.15为什么要引入Herbrand理论？什么是H域？如何求子句集的H域？

3.16什么是原子集？如何求子句集的原子集？

3.17什么是H域解释？如何用域D上的一个解释I构造H域上的解释I*呢？

3.18假设子句集S={P(z)VQ(z),R(f(t))},S中不出现个体常量符号。设个体域口={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上的解释，并作如下的设定

I：f(Df(2)P(l)P(2)Q(l)Q(2)R(l)R(2)

22TFFTFT

请构造H域上的一个解释I*与I相对应，且使Sh*=T。

3.19引入Robinson的归结原理有何意义？其基本思想是什么？

3.20请写出应用归结原理进行定理证明的步骤。

3.21对下列各题分别证明G是否为Fi,2,…,冉的逻辑结论。

⑴F1:(3x)(3y)P(x,y)

G:(Vy)(3x)P(x,y)

⑵Fl:(Vx)(P(x)A(Q(a)vQ(b)))

G:(3x)(P(x)AQ(X))

(3)Fl:(3x)(3y)(P(f(x))AQ(f(b)))

G:P(f(a»AP(y)AQ(y)

(4)Fl:(Vx)(P(x)f"y)(Q(yA~L(x,y)))

F2:(3x)(P(x)A(Vy)(R(y)TL(x,y)))

G:(Vx)(R(x)Q(x))

(5)Fl:(Vx)(P(x)f(Q(X)AR(X)))

F2:(3X)(P(X)AS(X))

G:(3x)(S(x)AR(x))

(6)Fl:(Vz)(A(z>\~B(z)->(3y)(D(z^)AC(y)))

F2:(3Z)(E(Z)AA(Z)A(Vy)(D(z,y)fE(y)))

F3:(Vz)(E(x)-»〜B(z))

G:(3Z)(E(Z)AC(Z))

3.22证明：

(Vy)(Q(y)-(B(y)AC(y)))A(3y)(Q(y)AD(y))f(3y)(D(y)AC(y))

3.23某单位招聘工作人员，张三、李四、王五三人应试，经面试后单位有如下想法：

(1)如果录取张三而不录取李四，则一定录取王五。

(2)如果录取李四，则一定录取王五。

(3)三人中至少要录取一人。

求证：王五一定会被单位录取。

3.24每个储蓄钱的人就是为了获得利息。求证：对某个人来说，如果不能获得利息，则他就不会储

蓄钱。

3.25请写出利用归结原理求解问题答案的步骤。

3.26应用归结原理求解下列问题:

设张三、李四和王五三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：

谁是说假话者？张三答：“李四和王五都是说假话者”；李四答：''张三和王五都是说假话者"；王五答：“张

三和李四中至少有一个说假话者”。求谁是说假话者，谁是说真话者？

3.27己知樊臻的老师是张先生，樊臻与李伟是同班同学。如果x与y是同班同学，则x的老师也是y

的老师。请问李伟的老师是谁？

3.28什么是完备的归结控制策略？有哪些归结控制策略是完备的？

3.29设已知：

(1)能阅读的人是识字的。

(2)海豚不识字。

(3)有些海豚是很聪明的。

用输入归结策略证明：有些很聪明的人并不识字。

3.30用输入归结策略是否可证明下列子句集的不可满足性？

S=(PVQ,QVR.RVW,-RV-P,~WV-Q,-QV-R)

3.2习题参考斛答

3.1答：(略)

3.2答：(略)

3.3答：(略)

3.4答：(略)

3.5解：

在谓词公式0x)(Vy)(Pay)fQJy))中没有包括个体常量和函数，所以，可以直接为谓

词指派真值。设：

P(U)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F

Q(1,D=T,Q(1,2)=F,Q(2,1)=T,Q(2,2)=F

在这种解释下，对某一•个x(x=l或x=2)对所有的y(即y=l或y=2)都不能使P(x,y)的真值

为T,所以，在此解释下，P(x,y)的真值为F。同理，Q(x,y)的真值也为F。根据谓词逻辑真

值表可知：在该解释下，上述谓词公式的真值为T。

上述谓词公式在口={1,2}上共有256种解释，这里不再一一列出，读者可自己列出其中的几

个，并求出其真值。

3.6解：

(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是自由变元。z和y辖域都是P(z,y)vQ(z,x)。

(3)x和z均是约束变元。没有自由变元。x的辖域是整个公式,z的辖域是Q(x,z)A~R(X,Z)。

(4)z、y和t均是约束变元。没有自由变元。z和y的辖域是整个公式，t的辖域是P(z,t)v

Q(y,t)o

(5)本小题比较复杂，表面上只涉及两个变元z和y,实际上公式中后面的两个z和一个

y都可看成是另外的变量，因此，可作变元替换将公式变换为：

(Vz)(3y)(P(z,y)v(3z')((Vy')(P(z',y')AQ(Z',y')v(3z-)Q(z",y,))))

公式中的变元就成为z、y、z\y\z"五个变元。z和y的辖域是整个公式，z，和y，的辖

域是P(z',y')AQ(z',y')v(3z")Q(z",y'),而z”为Q(z”,y)

3.7答：(略)

3.8答：(略)

3.9解:

(1)P(a,b)与P(x,y)是可合一的。。={a/x,b/y}

(2)P(f(z),b)与P(x,y)是可合一的。。={f(z)/x,b/y}

(3)P(f(x),y)与P(y,f(a))是可合一的。根据最一般合一求取算法，可得o={f(a)/y,a/x}

(4)P(f(y),y,x)与P(x,f(a),f(b))是不可合一的。

(5)P(x,y)与P(y,x)是可合一■的。。={y/x}或。={x/y}

3.10答：

范式就是标准型。谓词演算中，一般有两种范式，一种叫前束形范式，另一种叫斯克林

(Skolem)范式。一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且

它的辖域一直延伸到公式之末，同时公式中不出现连接词一及一,这种形式的公式称作前

束形范式。它的一般形式是

(QIX1)(Q2X2)...(QttXn)M(X|,X2,...,Xn)

其中，Qi(i=l,2,…n)是存在量词或全称量词，而母式M(X|,X2,…,xj不再含有量词。

从前束形范式中消去全部存在量词所得到的公式称为Skolem标准型，它的一般形式是

(VX|)(VX2)...(VXn)M(Xl,X2,...,Xn)

3.11答：

子句就是由一些文字组成的析取式。而所谓文字是指原子或原子的否定。不含有任何

连接词的谓词公式叫做原子或原子公式。由子句构成的集合称为子句集。

求谓词公式G的子句集的步骤如下：

(a)消去谓词公式G中的蕴涵(一)和双条件符号(c),以〜AVB代替A-B,以

(AAB)V(〜A八〜B)替换A—B。

(b)减少否定符号(〜)的辖域，使否定符号“〜”最多只作用到一个谓词上。

(c)重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。

(d)消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域

内，此时，只要用一个新的个体常量替换该存在量词约束的变元，就可以消去存在量词；另

一种情况是，存在量词位于一个或多个全称量词的辖域内，例如，

(Vxi)(VX2)...(Vxn)(3y)P(X1,X2,…,Xn,y)

此时，变元y实际受前面的变元X|,X2，…，Xn的约束，需要用Skolem函数f(xi,X2,…,Xn)

替换y即可将存在量词y消去，得到：

(Vxi)(Vx2)...(Vxn)P(X|,X2,...,Xn,f(X|,X2,...,Xn))

(e)把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整

个部分。

(f)母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的

有限集组成的合取。

(g)消去全称量词。

(h)对变元进行更名，是不同子句中的变元不同名。

(i)消去合取符号八，将各子句写成子居积合的形式。

3.12答：(略)

3.13解:

(1)因为(Vz)(Vy)(P(z,y)AQ(z,y))已经是一个Skolem标准型，P(z,y)AQ(z,y)已是合取范

式，以逗号代替A,得子句集：S={P(z,y),Q(z,y)}

(2)首先将谓词公式(Vx)(Vy)(P(\y)->Q(x,y))化为Skolem标准型：

(Vx)(Vy)(~P(x,y)vQ(x,y))

消去全称量词，并将母式化为子句集

S={〜P(x,y)vQ(x,y)}

(3)首先将谓词公式(Vx)(3y)(P(x,y)v(Q(x,y)->R(x,y)))化为Skolem标准型：

第一步：消去一号

(Vx)(3y)(P(x,y)v(~Q(x,y)vR(x,y)))

第二步：消去存在量词，用Skolem函数f(x)代替y

(Vx)(P(xf(x)卜~Q(x,f(x))vR(x,f(x)))

第三步：消去全称量词，并将母式化为子句集

S={P(x,f(x)»~Q(x,f(x))vR(x,f(x))}

(4)首先将谓词公式(Vx)(Vy)0z)(P(%y)->Q(x,y)vR(x,z))化为Skolem标准型：

第一步：消去一号

(Vx)(Vy)(3z)(~P(x,y)vQ(x,y)vR(x,z))

第二步：消去存在量词，用Skolem函数f(x,y)代替z

(Vx)(Vy)(~P(x,y)vQ(x,y)vR(x,f(x,y)))

第三步：消去全称量词，并将母式化为子句集

S={~P(x,y)vQ(x,y)vR(x,f(x,y)))

(5)将谓词公式(3x)(3y)(Vz)(3u)(Vv)(3w)(P(x,y,z,u,v,w)A(Q(X,y,Z,U,V,W)V~R(x,z,w)))

化为Skolem标准型：

第一步：消去存在量词x,y,以常量a,b分别代之

(Vz)(3u)(Vv)(3w)(P(a,b,z,u,v,w)A(Q(a,b,z,u,v,w)v~R(a,z,w)))

第二步：消去存在量词u,由于u在全称量词z的辖域内，令Skolem函数u=f(z)

(Vz)(Vv)(3w)(P(a,b,z,f(z),v,w)人(Q(a,b,z,f(z),v,w)v~R(a,z,w)))

再消去存在量词w,由于w在全称量词z和v的辖域内，令Skolem函数w=g(z,v)

(Vz)(Vv)(P(a,b,z,f(z),v,g(z,v))A(Q(a,b,z,f(z),v,g(z,v))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))v~R(a,z,g(z,v))}

3.14解

(1)依照归结推理过程，对子句集S={~PvQ,~Q,P,~P}进行归结推理

1)~PvQ

2)〜Q

3)P

4)-P

5)NIL3),4)归结

所以，该子句集是不可满足的。同理，可以推知第(2)、(4)、(5)、(8)小题的子句集

也是不可满足的，因为它们都可以归结出空子句。

3.15答：

引入Herbrand理论的目的是为了简化对谓词公式不可满足性的证明。对于一个谓词公

式来说，要证明它的不可满足性是困难的，故考虑它的子句集的不可满足性。然而，对子句

集的不可满足性的判定仍然是困难的，因为要判断子句集的不可满足性就要对子句集中的每

一个子句逐个进行判定。由于个体变元域D的任意性以及解释个数的无限性，这实际上是

一项难以完成的工作。能否针对某一个具体的谓词公式，找到一个比较简单的特殊域，只要

使谓词公式在该特殊域上是不可满足的，就能保证它在任一域上也是不可满足的呢？

Herbrand理论就构造了这样的一个域，称为Herbrand域(H域)。只要对H域上的所有解释

进行判定，即可得知谓词公式是否是不可满足的。

H域的定义中就包含了子句集H域的求取方法：设谓词公式G的子句集为S,则按下

述方法构造的个体变元域H，称为公式G或子句集S的Herbrand域，简称H域。

(a)令Ho是S中所出现的常量的集合。若S中没有常量出现，就任取一个常量aeD,

规定Ho={a}o

(b)令尸HiU{S中所有的形如f(ti,的元素}

其中f(ti,…,tn)是出现于G中的任一函数符号，而ti，…，tn是Hi中的元素。i=0,1,2,...»

3.16答：

下列集合称为子句集S的原子集：

A={所有形如P(tl,t2,...,tn)的元素}

其中，P(t|,t2,…,tn)是出现在S中的任一谓词符号，而t|,t2，…，tn则是S的H域上的任意

元素。该定义就给出了子句集的原子集的求法。

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是D上的解释，并作如下的设定

f(Df⑵P(l)P(2)Q(l)Q(2)R(l)R(2)

22TFFTFT

将以上各值代入S,有Sh=T。现在要构造H域上的一个解释I*与I相对应，且使S|r*=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⑴f2

f(f(a)Lf⑵-2

f(f(f(a)))-f(2)-*2

再依据H中各元素的值与解释I的规定，确定原子集A中各元素的取值:

P(a)fP(l)-T

Q(a)-Q(l)-F

R(aLR⑴fF

P(f(a)LP(2LF

Q(f(a))-Q⑵-T

R(f(a))-R⑵fT

于是，便得到与D域上解释I相对应的H域上的解释I1：

I*i={P(a),-Q(a),-R(a),-P(f(a)),Q(f(a)),R(f(a)),...}

同理，若将H中的元素a设成2,我们可以得到与I相对应的另一个H解释1*2：

1*2={〜P(a),Q(a),R(a),~P(f(a)),Q(f(a)),R(f(a)),...)

可以验证S|r,=T,S|r2=To解释、1*2便是所求的与D域上解释I相对应的H域之解释。

3.19答:(略)

3.20答：

设要被证明的定理可用谓词公式表示为形式AiAA2A…AA.-B,则应用归结原理进

行定理证明的步骤如下：

(1)首先否定结论B,并将否定后的公式〜B与前提公式集组成如下形式的谓词公式：

G=AiAA2A…AAn/\〜B

(2)求谓词公式G的子句集S。

(3)应用归结原理，证明子句集S的不可满足性，从而证明谓词公式G的不可满足性。

这就说明对结论B的否定是错误的，推断出定理的成立。

3.21解：

⑴F,:(3x)(3y)P(x,y)

G:(Vy)(3x)P(x,y)

首先将Fl和〜G化为子句集

1)P(a,b)

2)~P(x,b)

然后利用归结原理进行归结

3)NIL1)与2)归结，o={a/x}

所以G是R的逻辑结论。

(2)首先将R和〜G化为子句集

H：(Vx)(P(x)A(Q(a)vQ(b))),由于Fi本身就是Skelom标准型，所以有

Si={P(x),Q(a)vQ(b)}

~G=(Vx)(~P(x)v~Q(x))

所以，S2={~P(x)v~Q(x)}

下面进行归结

1)P(x)

2)Q(a)vQ(b)

3)~P(x)v~Q(x)

4)~Q(x)1),3)归结

5)Q(b)2),4)归结G={a/x}

6)NIL4),5)归结G={b/x}

所以G是B的逻辑结论。

其余各题的证明留给读者自己练习。

3.22证明：

第一步：先对结论否定并与前提合并得谓词公式G

G=(Vy)(Q(y)f(B(y)AC(y)))A(3y)(Q(y)AD(y))A-(3y)(D(y)AC(y))

第二步：将公式G化为子句集，可将G看作三项的合取，对每一项分别求子句集

Gi：(Vy)(Q(y)-(B(y)AC(y)))

=(Vy)(〜Q(y)V(B(y)AC(y)))

=(Vy)((~Q(y)VB(y))A(~Q(y)VC(y)))

所以，S尸{(〜Q(y)VB(y)),〜Q(y)VC(y)}。

G2：(3y)(Q(y)AD(y))

所以，S2={Q(a),D(a)}。

~B：-(3y)(D(y)AC(y))

=(Vy)(~D(y)V~C(y))

所以，S~B={〜D(y)V〜C(y)}«

从而得公式G的子句集：

S=S,US2USB={(-Q(y)VB(y)),~Q(y)VC(y),Q(a),D(a),〜D(y)V〜C(y)}

第三步：使用归结原理，对子句集S进行归结。

(1)〜Q(y)VB(y)

(2)〜Q(y)VC(y)

(3)Q(a)

(4)D(a)

(5)〜D(y)V~C(y)

(6)C(a)(2)与⑶归结o={a/y}

(7)~C(a)(4)与⑸归结<j={a/y}

(8)NIL(6)与(7)归结

由此得出子句集S是不可满足的，因而公式G也是不可满足的，从而命题得证。

3.23证明：

第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。

(I)定义谓词和常量：

谓词Matr(x)表示x被录取。

Z表示张三，L表示李四，W表示王五。

(2)将前提及要证的问题表示成谓词公式：

a)Matr(Z)A~Matr(L)fMatr(W)

b)Matr(L)fMalr(W)

c)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)归结

7)NIL4)与6)归结

所以，王五一定会被录取。

3.24证法一：

第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。

定义谓词：

设：Save(x)：表示x储蓄钱；

Interest(x)：表示x获得利息。

将前提表示成谓词公式：

(Vx)(Save(x)—>Interes(x))

把要求证的问题用谓词公式表示出来：

(By)(~Interest(y)―〜Save(y))

第二步：将前提和要求证的问题之否定化成子句集.

求前提子句集：

(Vx)(Save(x)-Interes<x))=>

(Vx)(~Save(x)vInteresl(x))

前提的子句集：Sl={~Save(x)vInterest(x))

求结论之否定子句集：

~(By)(~InteresKy)—〜Save(y))n

~(By)(Interest(y)v~Save(y))=

(Vy)(~Interest(y)ASave(y))

结论之否定子句集：S2={^Interest(y),Save(y)}

第三步：利用归结原理对上面的子句集中的子句进行归结

(1)〜Save(x)vInterest(x)

(2)〜Interested

(3)Save(y)

(4)~Save(y)(1),(2)归结。={x/y}

(5)NIL(3),(4)归结

证毕。

证法二：

第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。

定义谓词：

设：Save(x,y)：表示x储蓄y；

Money(y)：表示y是钱；

Interest(y)：表示y是利息；

Obtain(x,y)：表示x获得y。

将前提表示成谓词公式：

(Vx)((3y)(Money(y)ASave(x,y))—>(3u)(Interes<u)AObtain(x,u)))

把要求证的问题用谓词公式表示出来：

(3x)(-(3u)(Interest(u)AObtain(X,U))-〜(3y)(Money(y)ASave(x,y)))

第二步：将前提和要求证的问题之否定化成子句集。

求前提子句集：

(Vx)((3y)(Money(y)ASave(x,y))—(3u)(Interest(u)AObtain(x,u)))=

(Vx)(-(3y)(Money(y)ASave(x,y))v(3u)(Interest(u)AObtain(x,u)))=>

(Vx)((Vy)(-Money(y)v〜Save(x,y))v(3u)(Interest(u)AObtain(x,u)))

设skolem函数为u=f(x),则:

前提的子句集：Sl={-Money(y)v-Save(x,y)vInteres<f(x)),

〜Money(y)v〜Save(x,y)vObtain(x,f(x))}

求结论之否定子句集:

〜(3x)(-(3u)(Interest(u)AObtain(x,u))—(3y)(Money(y)ASave(x,y)))n

〜(3x)((3u)(Interest(u)AObtain(x,u))v〜(3y)(Money(y)ASave(x,y)))

(Vx)((Vu)(^Interest(u)v〜Obtain(x,u))A(3y)(Money(y)ASave(x,y)))

设skolem函数为y=g(x),则上式变为：

(Vx)(Vu)((-Interest(u)v〜Obtain(x,u))A(Money(g(x))ASave(x,g(x))))

结论之否定子句集：

Sa={〜Interest(u)v〜Obtain(x,u),Money(g(x)),Save(x,g(x)))

第三步：利用归结原理对上面的子句集中的子句进行归结

(1)〜Money(y)v〜Save(x,y)vInterest(f(x))

(2)〜Money(y)v〜Save(x,y)vObtain(x,f(x))

(3)〜Interest(u)v〜Obtain(x,u)

(4)Money(g(x))

(5)Save(x,g(x))

(6)〜Money(y)v〜Save(x,y)v〜Obtain(x,f(x))(1),(3)归结。={f(x)/u)

(7)〜Money(y)v〜Save(x,y)(2),(6)归结

(8)〜Money(g(x))(5),(7)归结o={g(x)/y)

(9)NIL(4),(8)归结

证毕。

3.25答：

利用归结原理求取问题答案的步骤如下：

(1)把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为

SiO

(2)把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构

成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变

量完全一致。

(3)把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与S,合并构

成子句集S。

(4)对子句集S应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变

ANSWER中的变元。

⑸如果得到归结式ANSWER,则问题的答案即在ANSWER谓词中。

3.26解：

第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。

(1)定义谓词和常量：

设P(x)表示x说真话。Z表示张三，L表示李四，W表示王五。

(2)将已知事实用谓词公式表示出来。

若张三说的是真话，则有P(Z)f-P(L)A-P(W)

若张三说的是假话，则有〜P(Z)fP(L)VP(W)

对李四和王五说的话做同样的处理，可得：

P(L)--P(Z)A~P(W)

〜P(L)fP(Z)VP(W)

P(W)-〜P(Z)V〜P(L)

〜P(W)-P(Z)AP(L)

(3)将它们化成子句集得S：

1)〜P(Z)V〜P(L)

2)〜P(Z)V〜P(W)

3)P(Z)VP(L)VP(W)

4)〜P(L)V〜P(W)

5)〜P(W)V〜P(Z)V〜P(L)

6)P(W)VP(Z)

7)P(W)VP(L)

第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。

设u是说真话者，则有：P(u)o将其否定与ANSWER作析取，得：

G：~P(u)VANSWER(u)

将上述公式G化为如下的子句，并将其合并到So

8)-P(u)VANSWER(u)}

第三步：应用归结原理对上述子句集进行归结

9)-P(Z)VP(W)1)与7)归结

10)P(W)6)与9)归结

11)ANSWER(W)8)与10)归结o={W/u)

第四步：得到的归结式ANSWER(W),答案即在其中，u=W,所以，求得王五是说真

话者。

除此之外，无论对上述子句集如何进行归结，都推不出ANSWER(Z)和ANSWER(L)来，

说明张三和李四不是说真话者。其实可以证明张三和李四是说假话者。证明的方法是设张三

或李四是说假话者，则有：〜P(Z)或〜P(L)作为要证明的结论，将它的否定之子句并入前面

的子句集1)-7),并进行归结推理，推出空子句，从而证明假设的正确性，即张三和李四

是说假话者。

3.27解：

第一步：定义谓词，并将已知条件用谓词公式表示出来，并化成子句集。

(1)定义谓词和常量：

Tea