人工智能导论第四版第三章课后题答案

3.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) (V x)( V y)(P(x, y)^Q(x, y))

(2) (V x)( V y)(P(x, y)- +Q(x, y))

(3) (V x)(3y)(P(x, y)V (Q(x, y)- +R(x, y))

(4) (V x)(V y)(3z)[P(x, y)→Q(x, y)VR(x, z))

解: (1) 由于(V x)(V y)(P(x, y)^Q(x, y)已经是Skolem标准型，且 P(x, y)AQ(x, y)已经是

合取范式，所以可直接消去全称量词、合取词，得

{P(x,y)，Q(x, y)}

再进行变元换名得子句集:

S={ P(x, y)，Q(u, v)}

(2)对谓词公式(V x)(V y)(P(x, y)→Q(x, y)，先消去连接词“→”得:

(V x)(V y)( P(x, y)VQ(x, y)

此公式已为Skolem标准型。

再消去全称量词得子句集:

s={P(x, y)VQ(x, y)}

(3)对谓词公式(V x)( 3y)(P(x, y)V (Q(x, y)→R(x, y))，先消去连接词“→”得:

(V x)(3 y)(P(x, y)V (-Q(x, y)V R(x, y))

此公式已为前束范式。

再消去存在量词，即用Skolem函数f(x)替换y得:

(V x)(P(x, f(x))V-Q(x, f(x)V R(x, f(x)))

此公式已为Skolem标准型。

最后消去全称量词得子句集: .

S= {P(x, f()V-Q(x, f(x))V R(x, f(x))}

(4)对谓词(V x)(V y)(3 z)P(x, y)- +Q(x, y)VR(x, z))，先消去连接词“→”得:

(V x)(V y)(3 z)(-P(x, y)VQ(x, y)VR(x, z))

再消去存在量词，即用Skolem函数f(x)替换y得:

(V x)(V y)(-P(x, y)VQ(x, y)VR(x, f(x,))))

此公式已为Skolem标准型。

最后消去全称量词得子句集:

S={ P(x, y)VQ(x, y)V R(x, f(x,y))}

3-13判断下列子句集中哪些是不可满足的:

(1) {PVQ,7Q， P, P}

(2) { PVQ，~PVQ， PV-Q, PV-Q }

(3) { P(y)VQ(y), ~P(f(x))V R(a)}

(4) { P(x)VQ(x)， P(y)V R(y), P(a), S(a), ~S(z)V-R(z)}

(5) { P(x)VQ(f(x),a)，-P(h(y))VQ(f(h(y)),a)V ~P(z)}

(6) {P(x)VQ(x)VR(x)， P(y)V(y), - Q(a), ~R(b)}R

解: (1) 不可满足，其归结过程为:

(2)不可满足，其归结过程为:

(3)不是不可满足的，原因是不能由它导出空子句。

(4)不可满足，其归结过程为: .

(5)不是不可满足的，原因是不能由它导出空子句。

(6)不可满足，其归结过程为:

3.14

对下列各题分别证明G是否为F.,.....的逻辑结论:

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

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

(2) F:(V x)(P(x)A(Q(a)VQ(b))

G: (3 x) (P(x)/Q(x))

(3) F:(3x)(3y)(P(x)(Q(fy))

G: P(f(a))A\\P(y)AQ(y)

(4) F:(V x)(P(x)→(V y)(Q(y)→-L(x.y))

F2: (3 x) (P(x)^( V y)(R(y)→L(x.y))

G:(V x)(R(x)→-Q(x)) 

(5) F:(V x)(P(x)→(Q(x)/R(x))

F2: (3x) (P(x)/S(x))

G: (3x) (S(x)/\\ R(x))

解: (1) 先将F和-G化成子句集:

S= {P(a,b), P(x,b)}

再对S进行归结:

所以，G是F的逻辑结论

(2)先将F和G化成子句集

由F得: S={P(x), (Q(a)VQ())}

由于-G为:一(3x) (P(x)/Q(x))，即

(V x)( P(x)V- Q(x)),

可得: Sz={ P(x)V- Q(x)}

因此，扩充的子句集为:

S={ P(x)，(Q(a)VQ(b))， - P(x)V~Q(x)}

再对S进行归结:

所以，G是F的逻辑结论

(3) 先将F和G化成子句集

由F得: Si={(f(x)), Q())}

由于-G为: P(f(a))V P(y)V Q(y)，用置换{f(a)/y}作用于该公式得: 

~P(f(a))V-Q(f(a))

即S2={-P(f(a))V-Q(fa))}

因此，扩充的子句集为:

S={ P(f(x)), Q(f(b)), -P(f(a))V-Q(f(a))}

再对S进行归结:

所以，G是F的逻辑结论

同理可求得(4)和(5)，其求解过程略。

3.16假设张被盗， 派出5个人去调查。案情分析时，贞察员A说:“赵与钱中至

少有一个人作案”，贞察员B说:“钱与孙中至少有一个人作案”，贞察员C说:“孙与李中至少.

有一个人作案”，贞察员D说:“赵与孙中至少有一个人与此案无关”，贞察员E说:“钱与李中

至少有一个人与此案无关”。如果这5个侦察员的话都是可信的，使用归结演绎推理求出谁是盗

窃犯。

解: (1) 先定义谓词和常量

设C(x)表示x作案，Z表示赵，Q表示钱，S表示孙，L表示李

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

赵与钱中至少有一个人作案: C(Z)VC(Q)

钱与孙中至少有一个人作案: C(Q)VC(S)

孙与李中至少有一个人作案: C(S)VC(L)

赵与孙中至少有一个人与此案无关: - (C (Z)AC(S)，即-C(Z) V ~C(S) 

钱与李中至少有-一个人与此案无关: - (C (Q)AC(L))，即-C(Q) V- C(L) 

(3)将所要求的问题用谓词公式表示出来，并与其否定取析取。

设作案者为u,则要求的结论是C(u)。将其与其否)取析取，得:

7 C(u) VC(u)

(4)对.上述扩充的子句集，按归结原理进行归结，其修改的证明树如下:

因此，钱是盗窃犯。实际上，本案的盗窃犯不止-一人。根据归结原理还可以得出: .

因此，孙也是盗窃犯。

3.19

设已知:

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

(2)海豚不识字;

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

请用归结演绎推理证明:有些很聪明的人并不识字。

解:第一步，先定义谓词，

设R(x)表示x是能阅读的; .

K(y)表示y是识字的; .

W(z)表示z是很聪明的;

第二步，将已知事实和目标用谓词公式表示出来

能阅读的人是识字的: (V x)(R(x))→K(x))

海豚不识字: (V y)(-K (y))

有些海豚是很聪明的: (3 z) W(z)

有些很聪明的人并不识字: (3 x)( W(z)A-K(x))

第三步，将上述已知事实和目标的否定化成子句集:

~R(x))VK(x)

~K (y)

W(z)

-W(z)VK(x))

第四步，用归结演绎推理进行证明