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

第三章确定性推理方法习题参考解答3.1 练习题3TF的命题。什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？谓词逻辑和命题逻辑的关系如何？有何异同？什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。D={1,2},试给出谓词公式(x)(y)(P(x,y)Q(x,y))的所有解释，并且对每一种解释指出该谓词公式的真值。对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。(1)(x)(P(x,y)(y)(Q(x,y)R(x,y)))⑵(z)(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))))什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含?什么是置换？什么是合一？什么是最一般的合一?

判断以下公式对是否可合

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)P(x,y),

P(y,x)SKOLEM范式的形式什么是子句？什么是子句集？请写出求谓词公式子句集的步骤谓词公式与它的子句集等值吗？在什么情况下它们才会等价？把下列谓词公式分别化为相应的子句集：(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)))判断下列子句集中哪些是不可满足的：S{〜PQ,〜Q,P,〜P}S{PQ,〜PQ,P〜Q,〜P〜Q}(3)S{P(y)Q(y),〜P(f(x))R(a)}(4)S{〜P(x)Q(x)，〜P(y)R(y),P(a),S(a),〜S(z)〜R(z)}(5)S{〜P(x)〜Q(y)〜L(x,y),P(a),〜R(z)L(a,z),R(b),Q(b)}(6)S{〜P(x)Q(f(x),a),〜P(h(y))Q(f(h(y)),a)〜P(z)}(7)S{P(x)Q(x)R(x),~P(y)R(y),〜Q(a),〜R(b)}1.1S{P(x)Q(x)，〜Q(y)R(y),〜P(z)Q(z),〜R(u)}HerbrandfHH域？什么是原子集？如何求子句集的原子集？HDIHI*呢？S={P(z)VQ(z),R(f(t))},SD={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*=TORobinson的归结原理有何意义？其基本思想是什么？请写出应用归结原理进行定理证明的步骤。GFi,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)))

(Q(x)R(x)))S(x))R(x))G：(x)(R(x)~Q(x))(6)Fl:(z)(A)F3:(z)(E(x)~B(z))G：(z)(E(z)C(z))

(y)(D(z,y)C(y)))证明：(y)(Q(y)(B(y)C(y)))(y)(Q(y)D(y))(y)(D(y)C(y))某单位招聘工作人员，张三、李四、王五三人应试，经面试后单位有如下想法:(2)如果录取李四，则一定录取王五。三人中至少要录取一人。求证：王五一定会被单位录取。蓄钱。请写出利用归结原理求解问题答案的步骤。应用归结原理求解下列问题：设张三、李四和王五三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题:谁是说假话者？张三答：“李四和王五都是说假话者”；李四答：“张三和王五都是说假话者"；王五答：“张三和李四中至少有一个说假话者”。求谁是说假话者，谁是说真话者？xyxy的老师。请问李伟的老师是谁？什么是完备的归结控制策略？有哪些归结控制策略是完备的？设已知：(1)能阅读的人是识字的。(2)海豚不识字。(3)有些海豚是很聪明的。用输入归结策略证明：有些很聪明的人并不识字。用输入归结策略是否可证明下列子句集的不可满足性？S={PVQ,QVR,RVW,〜RV〜P,〜WV〜Q,〜QV〜R}习题参考解答3.23.3 答：(略)3.4 答：(略)3.5 答：(略)3.6 答：(略)解：在谓词公式(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)对所有的y(即y=1或y=2)都不能使P(x,y)的真值为T,所以，在此解释下，P(x,y)的真值为F。同理，Q(x,y)的真值也为F。根据谓词逻辑真值表可知：在该解释下，上述谓词公式的真值为To上述谓词公式在D={1,2}上共有256种解释，这里不再一一列出，读者可自己列出其中的几个，并求出其真值。解：P(x,y),Q(x,y)R(x,y)xQ(x,y),R(x,y)y是约束变元。P(x,y)y是自由变元。量词xy的辖域是(Q(x,y)R(x,y))。z和y是约束变元。x,u,v是自由变元。z和yP(z,y)Q(z,x)。x和z均是约束变元。没有自由变元。x的辖域是整个公式，zQ(x,z)~R(x,z)。z、y和t均是约束变元。没有自由变元。z和y的辖域是整个公式，tP(z,t)Q(y,t)。(5)zy,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(z',y')Q(z',y')(z'')Q(z'',y'),z'Q(z'',y')3.7答：(略)3.8答：(略)解：P(a,b)P(x,y)是可合一的。(T={a/x,b/y}P(f(z),b)P(x,y)是可合一的。b={f(z)/x,b/y}P(f(x),y)P(y,f(a))b={f(a)/y,a/x}P(f(y),y,x)P(x,f(a),f(b))是不可合一的。P(x,y)P(y,x)是可合一的。(T={y/x}或={x/y}答：范式就是标准型。谓词演算中，一般有两种范式，一种叫前束形范式，另一种叫斯克林(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)答：连接词的谓词公式叫做原子或原子公式。由子句构成的集合称为子句集。求谓词公式G的子句集的步骤如下：G中的蕴涵(-)和双条件符号()，以〜AVBA-B,以(AAB)V(〜AA〜B)替换AB。减少否定符号(〜)的辖域，使否定符号“〜”最多只作用到一个谓词上。重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域一种情况是，存在量词位于一个或多个全称量词的辖域内，例如，(X1)(X2)•••(Xn)(y)P(X1,X2，…，Xi,y)yXIX2,…，xnSkolemf(x1,X2,…K)y即可将存在量词y消去，得到：(X1)(X2)•••(Xn)P(X1,X2，…，X,f(x1,X2,•••,x))个部分。合取。消去全称量词。对变元进行更名，是不同子句中的变元不同名。(1) A,将各子句写成子居积合的形式。3.12答：(略)解：因为(z)(y)(P(z,y)Q(z,y))Skolem标准型，P(z,y)Q(z,y)已是合取范式，以逗号代替，得子句集：S={P(z,y),Q(z,y)}首先将谓词公式(x)(y)(P(x,y)Q(x,y))Skolem标准型：(x)(y)(~P(x,y)Q(x,y))消去全称量词，并将母式化为子句集S={P(x,y)Q(x,y)}首先将谓词公式(x)(y)(P(x,y)(Q(x,y)R(x,y)))Skolem标准型：第一步：消去号(x)(y)(P(x,y)(~Q(x,y)R(x,y)))Skolemf(x)y(x)(P(x,f(x))~Q(x,f(x))R(x,f(x)))第三步：消去全称量词，并将母式化为子句集S={P(x,f(x))~Q(x,f(x))R(x,f(x))}首先将谓词公式(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))Skolemf(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))}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,uzSkolemu=f(z)(z)(v)(w)(P(a,b,z,f亿),v,w)(Q(a,b,z,f亿),v,w)~R(a,z,w)))w,wz和vSkolemw=g(z,v)(z)(v)(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))))第三步：消去全称量词，并将母式化为合取范式，再化为子句集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))}解S{~PQ,~Q,P,~P}进行归结推理〜PQ〜QP-PNIL3),4)归结所以，该子句集是不可满足的。同理，可以推知第(2)、(4)、(5)、(8)小题的子句集也是不可满足的，因为它们都可以归结出空子句。答：引入Herbrand理论的目的是为了简化对谓词公式不可满足性的证明。对于一个谓词公足性的判定仍然是困难的，因为要判断子句集的不可满足性就要对子句集中的每D的任意性以及解释个数的无限性，这实际上是使谓词公式在该特殊域上是不可满足的，就能保证它在任一域上也是不可满足的呢？HerbrandHerbrand域(H域)。只要对H域上的所有解释进行判定，即可得知谓词公式是否是不可满足的。HHGS,HG或子句集SHerbrand域，简称H域。令H0是SSaD,规定H0={a}。令Hi+1=HiU{Sf(t1,…,t)的元素}其中f(t1,…用是出现于G中的任一函数符号，而t1,…，tn是Hi中的元素。i=0,1,2,…。答：下列集合称为子句集S的原子集：A={所有形如P(ti,t2,…&的元素}Stl,t2,…，tn则是S的H答：如果子句集S的原子集为A,则对A中各元素的真假值的一个具体设定都是S的一个H解释。用域DIHI*(1)S的H域和原子集ADI,HH域中有常量符号，可按Da设定某一值。HIA中各元素的取值。这样，原子集A中的各个元素都得到了一个取值，它就是与D上的解释I相对应的H域上的解释I*。解：D={1,2},ID上的解释，并作如下的设定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。依据DI之规定，对H域中的每个元素设定相应的值。在Ha,f(a),f(f(a)),…这时，由于aI中并未给出规定，所以我们要按Da1,21,2都是D的元素)。若a1,I,Hf(a)-f(1)-2f(f(a))-f(2)-2f(f(f(a)))f(2)2再依据HIAP(a)-P⑴fTQ(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=TO解释I*i、I*2便是所求的与D域上解释I相对应的H域之解释。*23.19答：(略)答：设要被证明的定理可用谓词公式表示为形式A1AA2A…AAn->B,则应用归结原理进行定理证明的步骤如下：B,并将否定后的公式〜B与前提公式集组成如下形式的谓词公式：G=A1AA2A…AAnA〜BGSoS的不可满足性，从而证明谓词公式G这就说明对结论B的否定是错误的，推断出定理的成立。解：1(1) F:(x)(y)P(x,y)1G:(y)(x)P(x,y)首先将F1和〜G化为子句集1) P(a,b)2) ~P(x,b)然后利用归结原理进行归结3) NIL1)2)归结，d={a/x}所以G是Fi的逻辑结论。(2)Fi和〜GFi：(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)}下面进行归结P(x)Q(a)Q(b)3) ~P(x)~Q(x)4) -Q(x)1),3)归结5) Q(b)2),4)b={a/x}6) NIL4),5)归结(r={b/x}所以G是Fi的逻辑结论。其余各题的证明留给读者自己练习。证明：第一步：先对结论否定并与前提合并得谓词公式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))。〜B:〜(y)(D(y)AC(y))=(y)(〜D(y)V〜C(y))所以，SB={〜D(y)V〜C(y)}。从而得公式G的子句集：S=SiUS2USB={(〜Q(y)VB(y)),〜Q(y)VC(y),Q(a),D(a),〜D(y)V〜C(y)}第三步：使用归结原理，对子句集S进行归结。Q(a)D(a)〜D(y)V〜C(y)(6)C(a)(2)与(3)归结b={a/y}(7)〜C(a)(4)与(5)归结b={a/y}(8)NIL(6)与(7)归结由此得出子句集S是不可满足的，因而公式G也是不可满足的，从而命题得证。证明：第一步：定义谓词，并将待证明的问题的前提条件和逻辑结论用谓词公式表示出来。)定义谓词和常量：Matr(x)xZ表不'张三，L表不'李四，W表不'王五。)将前提及要证的问题表示成谓词公式：Matr(Z)A~Matr(L)-Matr(W)Matr(L).Matr(W)Matr(Z)VMatr(L)VMatr(W)把要求证的问题否定，并用谓词公式表示出来：d)〜Matr(W)第二步：将上述公式化成子句集。〜Matr(Z)VMatr(L)VMatr(W)〜Matr(L)VMatr(W)Matr(Z)VMatr(L)VMatr(W)〜Matr(W)第三步：利用归结原理对上面的子句集中的子句进行归结。Matr(L)VMatr(W)1)3)归结Matr(W)2)5)归结NIL4)6)归结所以，王五一定会被录取。证法一：定义谓词：设：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)}求结论之否定子句集：~(y)(~Interest(y)~Save(y))~(y)(Interest(y)~Save(y))(y)(~Interest(y)Save(y))结论之否定子句集：S2={〜Interest(y),Save(y)}第三步：利用归结原理对上面的子句集中的子句进行归结~Save(x)Interest(x)~Interest(y)⑶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。将前提表示成谓词公式：(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)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)(Money(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))}第三步：利用归结原理对上面的子句集中的子句进行归结~Money(y)~Save(x,y)Interest(f(x))~Money(y)~Save(x,y)Obtain(x,f(x))~Interest(u)~Obtain(x,u)Money(g(x))Save(x,g(x)) ~Save(x,y)~Obtain(x,f(x))(6) ~Money(y) (1),(3)归结{f(x)/u}~Money(y)~Save(x,y) (2),(6)归结~Money(g(x))(5),(7) b={g(x)/y}NIL(4),(8)归结证毕。答：利用归结原理求取问题答案的步骤如下:把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S。SIANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一■致。ANSWERSi合并构SoSANSWER中的变元。ANSWER,ANSWER谓词中。解：第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。定义谓词和常量：设P(x)表小x说真tIfoZ表小张三，L表小李四，W表小王五。将已知事实用谓词公式表示出来。若张三说的是真话，则有P(Z)f〜P(L)A〜P(W)若张三说的是假话，则有〜P(Z)-P(L)VP(W)对李四和王五说的话做同样的处理，可得：P(L)-〜P(Z)A〜P(W)〜P(L)-P(Z)VP(W)P(W)-〜P(Z)V〜P(L)〜P(W)-P(Z)AP(L)〜P(Z)V〜P(L)〜P(Z)V〜P(W)P(Z)VP(L)VP(W)〜P(W)V〜P(Z)V〜P(L)P(W)VP(Z)第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。设u是说真话者，则有：P(u)。将其否定与ANSWER作析取，得：G:〜P(u)VANSWER(u)将上述公式G化为如下的子句，并将其合并到So〜P(u)VANSWER(u)}第三步：应用归结原理对上述子句集进行归结〜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),并进行归结推理，推出空子句，从而证明假设的正确性，即张三和李四是说假话者。解：第一步：定义谓词，并将已知条件用谓词公式表示出来，并化成子句集。 定义谓词和常量：