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

《人工智能教程习题及答案第3章习题参考解答.docx》由会员分享，可在线阅读，更多相关《人工智能教程习题及答案第3章习题参考解答.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章确定性推理方法习题参考斛答3.1练习题3.1 什么是命题？请写出3个真值为T及真值为F的命题。3.2 什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？3.3 谓词逻辑和命题逻辑的关系如何？有何异同？3.4 什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。3.5 什么是谓词公式？什么是谓词公式的解释？设D=1,2,试给出谓词公式GxXVyXPJy)-Q(%y)的所有解释，并且对每一种解释指出该谓词公式的真值。3.6 对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。(1) (Vx)(P(x,y) v (为)(Q(x,y) a R(x,y)(2) (

2、3z)(Vy)(P(z,y)v Q(z,x)v R(u,v)(3) (Vx)(P(x,f(x) v (3z)(Q(x,z)a R(x, z)(4) (Vz)(3y)(3t)(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 判断以下公式对是否可合一；若可合一，则求出最一般的合一：P(x,y)P(y,x)P(y,f(a)P(x,f(a),f(b)P(y,x)(1) P(a,b

3、),(2) P(f(z),b),(3) P(f(x),y),(4) P(f(y),y,x),(5) P(x,y),3.10 什么是范式？请写出前束型范式与SKOLEM范式的形式。3.11 什么是子句？什么是子句集？请写出求谓词公式子句集的步骤。3.12 谓词公式与它的子句集等值吗？在什么情况下它们才会等价?再依据H中各元素的值与解释I的规定，确定原子集A中各元素的取值:Q(aL Qf FR(a)f Rf FP(f(a)f P(2)f FQ(f(a)L Q(2)-TR(f(a)一 R(2)- T于是，便得到与D域上解释I相对应的H域上的解释I；：I*尸P(a),Q(a),R(a),P(f(a)，

4、Q(f(a),R(f(a),.同理，若将H中的元素a设成2,我们可以得到与I相对应的另一个H解释1*2 ：尸P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),.可以验证S|r尸T, S| r2=To解释I；、1*2便是所求的与D域上解释I相对应的H域之解释。3.19 答：(略)答：设要被证明的定理可用谓词公式表示为形式AiAA2AAAn-B,则应用归结原理进 行定理证明的步骤如下：(1)首先否定结论B,并将否定后的公式B与前提公式集组成如下形式的谓词公式：G二 Ai AA2 A. A AnAB(2)求谓词公式G的子句集S。(3)应用归结原理，证明子句集S的不可满足性，从而

5、证明谓词公式G的不可满足性。这就说明对结论B的否定是错误的，推断出定理的成立。3.20 解： 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是Fi的逻辑结论。(2)首先将Fi和G化为子句集K：(Vx)(P(x) A(Q(a)vQ(b),由于日本身就是Skelom标准型，所以有Si= P(x),Q(a)vQ(b)G=(X/x)(P(x)v Q(x)所以，s2= P(x)vQ(x)下面进行归结1) P(x)2) Q(a)vQ(b)3) P(x)v Q

6、(x)4)Q(x)1), 3)归结5) Q(b)2), 4)归结o=a/x6) NIL4), 5)归结 o=b/x所以G是B的逻辑结论。其余各题的证明留给读者自己练习。3.22证明:第一步：先对结论否定并与前提合并得谓词公式GG=( V y)(Q(y)f (B(y) A C(y) A (3 y)(Q(y) A D(y) A-(3 y)(D(y) A C(y)第二步：将公式G化为子句集，可将G看作三项的合取，对每一项分别求子句集Gi： (Vy)(Q(y)-(B(y)AC(y)=(Vy)(-Q(y)V(B(y)AC(y)=(V y)(Q(y)VB(y) A (Q(y)V C(y)所以，Si=(-Q

7、(y)VB(y),Q(y)VC(y)。G2： (3y)(Q(y)AD(y)所以，S2=Q(a),D(a)oB： (3y)(D(y)AC(y)=(V y)(D(y) V C(y)所以，Sb=D(y)VC(y)。从而得公式G的子句集：S= Si U S2U S=(-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) Q(a)(4) D(a)(5)D(y)V C(y)(6) C(a)(2)与归结 o=a/yC(a)与归结尸h/y(8) NIL(6)与(7)归结由此得出子句集S

8、是不可满足的，因而公式G也是不可满足的，从而命题得证。3.23证明：第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。(1)定义谓词和常量：谓词Matr(x)表示x被录取。Z表示张三，L表示李四，W表示王五。(2)将前提及要证的问题表示成谓词公式：a) Matr(Z)A- Matr(L) - Matr(W)Matr(L)- Matr(W)b) Matr(Z) V Matr(L) V Matr(W)把要求证的问题否定，并用谓词公式表示出来:d)Matr(W)第二步：将上述公式化成子句集。1) Matr(Z) V Matr(L) V Matr(W)-Matr(L)VMatr

9、(W)2) MatKZ) V Matr(L) V Matr(W)Matr(W)第三步：利用归结原理对上面的子句集中的子句进行归结。3) Matr(L)VMatr(W)1)与 3)归结Matr(W)2)与 5)归结4) NIL4)与6)归结所以，王五一定会被录取。3.24证法一：第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。定义谓词：设：Save(x)：表示x储蓄钱；Interest(x)：表示x获得利息。将前提表示成谓词公式：(Vx)(Save(x) - Interest(x)把要求证的问题用谓词公式表示出来：0y)(Interest(y)Save(y)第二步：将前

10、提和要求证的问题之否定化成子句集。求前提子句集：(Vx)(Save(x) - Interes(X/x)(Save(x) v Interest(x)前提的子句集：Sl= - Save(x) vInterest(x)求结论之否定子句集：0y)(Interest(y)-Save(y) n(3y)(InteresKy)v Save(y)=(Dy)(Interest(y) a Save(y)结论之否定子句集：S2= Interest(y), Save(y)第三步：利用归结原理对上面的子句集中的子句进行归结(1)Save(x) v Interest(x)(2)Interest(Save(y)(3) Sav

11、e(y)(1), (2)归结。=x/yNIL(3), (4)归结证毕。证法二：第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。定义谓词：设：Save(x,y)：表示x储蓄y；Money(y)：表示y是钱；Interest(y)：表示y是利息；Obtain(x,y)：表示 x 获得 y。将前提表示成谓词公式：(Vx)(3y)(Money(y) a Save(x, y) (3u)(Interest(u) a Obtain(x, u)把要求证的问题用谓词公式表示出来：(3x)(- (3u)(Interest(u) a Obtain(x, u)-(3y)(Money(y) a

12、 Save(x, y)第二步：将前提和要求证的问题之否定化成子句集。求前提子句集：(Vx)(3y)(Money(y) a Save(x9 y) t (3u)(Interest(u) a Obtain(x, u) n(Vx)(- (3y)(Money(y) a Save(x,y) v (3u)(Interest(u) a Obtain(x, u) n (X/x)(Vy)(Money(y)v Save(x,y) v (3u)(InteresKu) a Obtain(x, u) 设skolem函数为u=f(x),则：前提的子句集：Sl= - Money(y)v - Save(x,y) vIntere

13、st(f(x),Money(y)v Save(x, y) v Obtain(x, f (x) 求结论之否定子句集：(3x)(- (3u)(Interest(u) a Obtain(x9 u) (3y)(Money(y) ASave(x, y)=(3x)(3u)(Interest(u) a Obtain(x, u)v (3y)(Money(y) a Save(x, y)=(Vx)(Vu)(- Interest(u)v Obtain(x, u) a (3y)(Money(y) a Save(x, y)设skolem函数为y=g(x),则上式变为：(Vx)(Vu)(- Interes1(u)v Ob

14、tain(x, u) a (Money(g(x) a Save(x,g(x)结论之否定子句集：S2= Interest(u)v Obtain(x,u), Money(g(x),Save(x,g(x)第三步：利用归结原理对上面的子句集中的子句进行归结(1)Money(y)v Save(x, y) v Interest(x)(2)Money(y)v Save(x, y) v Obtain(x,f(x)(3) - Interest(u)v - Obtain(x,u)(4) Money(g(x)(5) Save(x,g(x)(1), (3)归结。=f(x)/u)(2), (6)归结(5), (7)归结

15、 o=g(x)/y(4), (8)归结(6)Money(y)v Save(x,y)v Obtain(x,f(x)(7)Money(y)v Save(x,y)(8)Money(g(x)1.1 NIL证毕。3.25 答：利用归结原理求取问题答案的步骤如下：(1)把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为Si O(2)把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构 成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变 量完全一致。(3)把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与Si合并构

16、成子句集S。(4)对子句集S应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变 ANSWER中的变元。(5)如果得到归结式ANSWER,则问题的答案即在ANSWER谓词中。3.26 解:第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。(1)定义谓词和常量：设P(x)表示x说真话。Z表示张三，L表示李四，W表示王五。(2)将已知事实用谓词公式表示出来。若张三说的是真话，则有P(Z)fP(L)AP(W)若张三说的是假话，则有P(Z) - P(L)VP(W)对李四和王五说的话做同样的处理，可得：P(L)-P(Z)A P(W)P(L)f P(Z)VP(W)P(W)一P(

17、Z) P(L)P(W)- P(Z)AP(L)(3)将它们化成子句集得S：1) P(Z)VP(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化为如下的子句，并将其合并到S。8) -P(u)VANSWER(u)第三步：应用归结原理对上述子句集进行归结9) -P(Z)VP(W)1)与 7

18、)归结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 解：第一步：定义谓词，并将已知条件用谓词公式表示出

19、来，并化成子句集。(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的老师：(Vx)(Vy)(Vz)(Classmate(x,y) a T eacher(z,x) T eacher(z,y)(3) 将它们化成子句集得S：1) Teacher(Zm, Fz)Classmate(Fz, Lw)2) Classmate

20、(x,y) V Teacher(z, x) VTeacher(z, y)第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。设李伟的老师是u,则有：Teacher(u, Lw)o将其否定与ANSWER作析取，并求子句且 把所得子句并入上述子句集：3) -Teacher(u, Lw) V ANSWER(u)第三步：应用归结原理对上述子句集进行归结1)与 3)归结 o=Fz/x,Zm/z1)与 3)归结 o=Fz/x,Zm/z4)与 5)归结 o=Lw/y,Zm/u2)与6)归结4) Classmate(Fz, y) VTeacher(Zm, y)-Classmate(Fz,Lw

21、)VANSWER(Zm)5) ANSWER(Zm)第四步：得到的归结式ANSWER(W),答案即在其中，u=Zm,即李伟的老师是张先生。3.28 答：(略)证明第一步：定义谓词，并将已知条件用谓词公式表示出来，并化成子句集。(1) 定义谓词和常量：Read(x)表示x是能阅读的；Know(y)表示y是识字的；Wise(z)表示z是很聪明的；用表示人类，用h表示海豚.(2) 将已知事实用谓词公式表示出来。能阅读的人是识字的：(Vr)(Read(r) - Know(r)海豚不识字：(Vh)(Know(h)有些海豚是很聪明的：(3h)(Wise(h)(3)将要证明的目标转化为谓词有些很聪明的人并不识

22、字:(3r)(Wise(r)A Know(r)第二步：将它们化成子句集1) Read(r) V Know(r)2)Know(h)Wise(a)4)Wise(r) V Know(r)第三步：对以上子句集进行归结5) Know(a)3)与 4)归结 o=a/rNIL2)与 5)归结 o=a/h从而命题得证。3.30 W利用输入归结策略不能证明子句集S=PVQ,QVR,RVW,-RV-P,-WV-Q,-QV-R的不可满足性。因为按照输入归结策略的要求，每次参加归结推理的两个子句中，必须至少 有一个子句是初始子句集中的子句。另外，要特别注意的是，在进行归结时，不能同时消去 两个互补文字对，因为消去两个

23、互补文字对所得到的结果，不是两个亲本子句的逻辑推论。 例如，在本题中，子句QVR和QVR不能进行归结，因为它们归结时将消去两个文字 对。所以，根据这些要求，将不能从该子句集中归结出空子句，也就是说，不能证明该子句 集的不可满足性。3.13 把下列谓词公式分别化为相应的子句集：(1) (Vz)(Vy)(P(z,y)AQ(z,y)(2) (Vx)(Vy)(P&y)f QJy)(3) (Vx)(3y)(P(&y)v (Q(x, y) - R(% y)(4) (/x)(X/y)6z)(P- Q(%y)v R(x,z)(5) (3x)(3y)(Vz)(3u)(Vv)(3w)(P(x,y,z,u,v,w)

24、a(Q(x,y,z,u,v,w)v R(%z,w)3.14 判断下列子句集中哪些是不可满足的：(1) S = PvQ,Q,P,P(2) S = PvQ,PvQ,Pz Q,Pv Q(3) S = P(y)vQ(y)P(f(x)vR(a)(4) S = P(x) = Q(x),P(y)v R(y),P(a),S(a),S(z)v R(z)(5) S = P(x)v Q(yV Ux, y),P(a),R(z)v L(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)v R(x),P(y) v

25、R(y),Q(a),R(b)(8) S = P(x) v Q(x)，Q(y) v R(y),P(z) v Q(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上的解释，并作如下的设

26、定I： f(Df(2)P(l)P(2)Q(l)Q(2)R(l)R(2)22TFFTFT请构造H域上的一个解释I*与I相对应，且使S|i*=To3.19 引入Robinson的归结原理有何意义？其基本思想是什么？3.20 请写出应用归结原理进行定理证明的步骤。3.21 对下列各题分别证明G是否为F” F2, H的逻辑结论。(1) Fl:(3x)(3y)P(x,y)G:(Vy)(3x)P(x,y)(2) 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

27、)(P(x) T (Vy )(Q(y -L(x,y)F2: (3x)(P(x) a (Vy)(R(y) f L(x, y)G : (Vx)(R(x) + Q(x)(5) F1:(Vx)(P(x)(Q(x)aR(x)F2:(3x)(P(x) a S(x)G : (3x)(S(x) a R(x)(6) Fl: (Vz)(A(z” B(z)T (3y)(D(z,y)AC(y)F2:0z)(E(z)八 A(z)A(Vy)(D(zy)f E(y)F3:(Vz)(E(x)f B(z)G: (3z)(E(z)aC(z)3.22 证明：(Vy)(Q(y) 一 (B(y) a C(y) a (3y)(Q(y)

28、a D(y) f (By)(D(y) a C(y)3.23 某单位招聘工作人员，张三、李四、王五三人应试，经面试后单位有如下想法：(1)如果录取张三而不录取李四，则一定录取王五。(2)如果录取李四，则一定录取王五。(3)三人中至少要录取一人。求证：王五一定会被单位录取。3.24 每个储蓄钱的人就是为了获得利息。求证：对某个人来说，如果不能获得利息，则他就不会储 蓄钱。3.25 请写出利用归结原理求解问题答案的步骤。3.26 应用归结原理求解下列问题:设张三、李四和王五三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说假话者？张三答：“李四和王五都是说假话者”；李四答

29、：”张三和王五都是说假话者；王五答：“张 三和李四中至少有一个说假话者:求谁是说假话者，谁是说真话者？3.27 已知樊臻的老师是张先生，樊臻与李伟是同班同学。如果x与y是同班同学，则x的老师也是y 的老师。请问李伟的老师是谁？3.28 什么是完备的归结控制策略？有哪些归结控制策略是完备的？3.29 设已知：(1)能阅读的人是识字的。(2)海豚不识字。(3)有些海豚是很聪明的。用输入归结策略证明：有些很聪明的人并不识字。3.30 用输入归结策略是否可证明下列子句集的不可满足性？S二PVQ,QVR,RVW,R-WV-Q,QVR3.2习题参考解答3.1 答：(略)答：(略)3.2 答：(略)答：(略

30、)3.3 解:在谓词公式qx)(Vy)(P(4y)f Q(4y)中没有包括个体常量和函数，所以，可以直接为谓 词指派真值。设：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=FQ(1,D =T,Q(l,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种解释，这里不再一一列出，读者可自己列出其中的儿

31、个，并求出其真值。3.4 解：(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)AR(x,y)o(2) z和y是约束变元。x, u, v是自由变元。z和y辖域都是P(z,y)vQ(z,x)。(3)x和z均是约束变元。没有自由变元。x的辖域是整个公式,z的辖域是Q(x,z) R(x,z)。(4)z、y和t均是约束变元。没有自由变元。z和y的辖域是整个公式，t的辖域是P(z,t) vQ(y,t)。(5)本小题比较复杂，表面上只涉及两个变元z和y,实际上公式中后面

32、的两个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(是 /) a Q(z; y!) v (3zM)Q(zy,),而 z”为 Q(zy)。3.7 答：(略)答：(略)3.8 解：(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)是可合一的。根据最一般

33、合一求取算法，可得。=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答：范式就是标准型。谓词演算中，一般有两种范式，一种叫前束形范式，另一种叫斯克林 (Skolem)范式。一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且 它的辖域一直延伸到公式之末，同时公式中不出现连接词一及一，这种形式的公式称作前 束形范式。它的一般形式是(Q1X1XQ2X2)(QnXn)M(Xi,X2,Xn) 其中，Qi(i=12n)是存在量词或全称量词，而母式乂支1拼2,西)不再含有量词。从前

34、束形范式中消去全部存在量词所得到的公式称为Skolem标准型，它的一般形式是 (V X1)( V X2).(V Xn)M(X 1 ,X2,Xn)答：子句就是由一些文字组成的析取式。而所谓文字是指原子或原子的否定。不含有任何 连接词的谓词公式叫做原子或原子公式。由子句构成的集合称为子句集。求谓词公式G的子句集的步骤如下：(a) 消去谓词公式G中的蕴涵(一)和双条件符号()，以AVB代替A-B,以 (AAB)V(AAB)替换 A B。(b) 减少否定符号()的辖域，使否定符号“”最多只作用到一个谓词上。(c) 重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。(d) 消去存在

35、量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域 内，此时，只要用一个新的个体常量替换该存在量词约束的变元，就可以消去存在量词；另 一种情况是，存在量词位于一个或多个全称量词的辖域内，例如，(Vxi)( Vx2).( Vxn) ( 3y ) P(Xi,X2,.,Xn,y)此时，变元y实际受前面的变元X1，X2，,Xn的约束,需要用Skolem函数f(X,X2,Xn) 替换y即可将存在量词y消去，得到：(V X1)( V X2).(V Xn)P(Xi,X2,.,Xn, f(X,X2,.,Xn)(e)把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整 个部分。(

36、f)母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的 有限集组成的合取。(g)消去全称量词。(h)对变元进行更名，是不同子句中的变元不同名。(1) 消去合取符号八，将各子句写成子居积合的形式。3.9 答：(略)解:(1)因为(Vz)(Dy)(P(z,y)/Q(z,y)已经是一个 Skolem 标准型，P(z,y) AQ(z,y)已是合取范 式,以逗号代替人,得子句集:S= P(z,y), Q(z,y)(2)首先将谓词公式(X/x)(Vy)(P(%y) -Q(%y)化为Skolem标准型：(Vx)(Vy)(P(x,y)vQ(x,y)消去全称量词，并将母式化为子句集S= P

37、(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) v R(x, y)第二步：消去存在量词，用Skolem函数f(x)代替y(Vx)(P(xf(x) Q(x,f(x)v R(x,f(x)第三步：消去全称量词，并将母式化为子句集S= P(x,f(x) Q(x,f(x)vR(x,f(x)(4)首先将谓词公式(VxXVygzXPJy) - Q(4 y)v R(x, z)化为 Skolem 标准型：第一步：消去一号(Vx)(Vy)(3z)(P(x,y

38、)vQ(x,y)v R(x,z)第二步：消去存在量词，用Skolem函数f(x,y)代替z(Vx)(Vy)(P(x,y)v Q(x, y) v R(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

39、,w)第二步：消去存在量词u,由于u在全称量词z的辖域内，令Skolem函数u=f(z) (Vz)(Vv)(3w)(P(a,b, z,f(z),v,w) A(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

40、(a,z,g(z, v) 3.10 解(1)依照归结推理过程，对子句集5 = PvQ,Q,P,P进行归结推理1) PvQ2)Q3) P4)P5) NIL3),4)归结所以，该子句集是不可满足的。同理，可以推知第(2)、(4)、(5)、(8)小题的子句集 也是不可满足的，因为它们都可以归结出空子句。3.15 答：引入Herbrand理论的目的是为了简化对谓词公式不可满足性的证明。对于一个谓词公 式来说，要证明它的不可满足性是困难的，故考虑它的子句集的不可满足性。然而，对子句 集的不可满足性的判定仍然是困难的，因为要判断子句集的不可满足性就要对子句集中的每 一个子句逐个进行判定。由于个体变元域D的

41、任意性以及解释个数的无限性，这实际上是 一项难以完成的工作。能否针对某一个具体的谓词公式，找到一个比较简单的特殊域，只要 使谓词公式在该特殊域上是不可满足的，就能保证它在任一域上也是不可满足的呢？ Herbrand理论就构造了这样的一个域，称为Herbrand域(H域)。只要对H域上的所有解释 进行判定，即可得知谓词公式是否是不可满足的。H域的定义中就包含了子句集H域的求取方法：设谓词公式G的子句集为S,则按下 述方法构造的个体变元域H。称为公式G或子句集S的Herbrand域，简称H域。(a) 令Ho是S中所出现的常量的集合。若S中没有常量出现，就任取一个常量aeD, 规定 Ho=a。(b)

42、 令Hi+i=HiUS中所有的形如f(ti,询)的元素其中f(ti,金)是出现于G中的任一函数符号，而5，tn是Hi中的元素。i=0, 1, 2, .o3.16 答:下列集合称为子句集S的原子集：A= 所有形如P(ti, t2,.,tn)的元素其中，P(tl,t2,是出现在S中的任一谓词符号，而t, t2，1则是S的H域上的任意 元素。该定义就给出了子句集的原子集的求法。3.17 答：如果子句集S的原子集为A,则对A中各元素的真假值的一个具体设定都是S的一个H 解释。用域D上的一个解释I构造H域上的解释I*的方法如下：(1)求子句集S的H域和原子集A(2)根据D域上的解释I,对H域中的每个元素

43、设定相应的值。如果H域中有常量符号， 可按D中的元素给a设定某一值。(3)依据H中各元素的值与解释I的规定，确定原子集A中各元素的取值。这样，原子集A中的各个元素都得到了一个取值，它就是与D上的解释I相对应的H 域上的解释I*。3.18 解：已知个体域D= 1,2, I是D上的解释，并作如下的设定f(D f(2) P(l) P(2) Q(l) Q(2) R(l) R(2)22 T F F T F T将以上各值代入S,有S|尸T。现在要构造H域上的一个解释I*与I相对应，且使S|*=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(l)一 2f(f(a)L ff 2