人工智能经典习题集及各章总结(期末考试必备) 下载本文

此公式已为Skolem标准型。

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

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)),先消去连接词“→”得:

(?x) (?y) (?z)(?P(x, y)∨Q(x, y)∨R(x, z)) 再消去存在量词,即用Skolem函数f(x)替换y得:

(?x) (?y) (?P(x, y)∨Q(x, y)∨R(x, f(x,y)))

此公式已为Skolem标准型。

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

S={?P(x, y)∨Q(x, y)∨R(x, f(x,y))}

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

(1) {?P∨Q, ?Q, P, ?P}

(2) { P∨Q , ?P∨Q, P∨?Q, ?P∨?Q } (3) { P(y)∨Q(y) , ?P(f(x))∨R(a)}

(4) {?P(x)∨Q(x) , ?P(y)∨R(y), P(a), S(a), ?S(z)∨?R(z)} (5) {?P(x)∨Q(f(x),a) , ?P(h(y))∨Q(f(h(y)), a)∨?P(z)} (6) {P(x)∨Q(x)∨R(x) , ?P(y)∨R(y), ?Q(a), ?R(b)}

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

?P∨Q ?Q

?P P

NIL

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

P∨Q ?P∨Q P∨?Q ?P∨?Q

?Q Q

NIL

(3) 不是不可满足的,原因是不能由它导出空子句。 (4) 不可满足,其归结过程略

(5) 不是不可满足的,原因是不能由它导出空子句。 (6) 不可满足,其归结过程略

3.14 对下列各题分别证明G是否为F1,F2,…,Fn的逻辑结论:

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

G: (?y)(?x)(P(x, y)

(2) F: (?x)(P(x)∧(Q(a)∨Q(b)))

G: (?x) (P(x)∧Q(x))

(3) F: (?x)(?y)(P(f(x))∧(Q(f(y)))

G: P(f(a))∧P(y)∧Q(y)

(4) F1: (?x)(P(x)→(?y)(Q(y)→?L(x.y)))

F2: (?x) (P(x)∧(?y)(R(y)→L(x.y))) G: (?x)(R(x)→?Q(x))

(5) F1: (?x)(P(x)→(Q(x)∧R(x)))

F2: (?x) (P(x)∧S(x)) G: (?x) (S(x)∧R(x))

解:(1) 先将F和?G化成子句集: S={P(a,b), ?P(x,b)} 再对S进行归结:

P(a,b) ?P(x,b)

{a/x} NIL

所以,G是F的逻辑结论

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

由F得:S1={P(x),(Q(a)∨Q(b))} 由于?G为:? (?x) (P(x)∧Q(x)),即

(?x) (? P(x)∨? Q(x)),

可得: S2={? P(x)∨? Q(x)}

因此,扩充的子句集为:

S={ P(x),(Q(a)∨Q(b)),? P(x)∨? Q(x)}

再对S进行归结:

Q(a)∨Q(b)

{a/b}

? P(x)∨? Q(a)

{a/x}

P(x) ? P(a)

{a/x} NIL

所以,G是F的逻辑结论

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

3.15 设已知:

(1) 如果x是y的父亲,y是z的父亲,则x是z的祖父; (2) 每个人都有一个父亲。

使用归结演绎推理证明:对于某人u,一定存在一个人v,v是u的祖父。

解:先定义谓词

F(x,y):x是y的父亲 GF(x,z):x是z的祖父 P(x):x是一个人

再用谓词把问题描述出来:

已知F1:(?x) (?y) (?z)( F(x,y)∧F(y,z))→GF(x,z)) F2:(?y)(P(x)→F(x,y))

求证结论G:(?u) (?v)( P(u)→GF(v,u)) 然后再将F1,F2和?G化成子句集: ① ?F(x,y)∨?F(y,z)∨GF(x,z)

② ?P(r)∨F(s,r)

③ P(u)

④ ?GF(v,u))

对上述扩充的子句集,其归结推理过程如下:

?F(x,y)∨?F(y,z)∨GF(x,z) ?GF(v,u)

{x/v,z/u}

?F(x,y)∨?F(y,z) ?P(r)∨F(s,r)

{x/s,y/r} ?F(y,z)∨?P(y) ?P(r)∨F(s,r)

{y/s,z/r} ?P(y)∨?P(z

{y/z} P(u) ?P(y)

{y/u} NIL

由于导出了空子句,故结论得证。

3.16 假设张被盗,公安局派出5个人去调查。案情分析时,贞察员A说:“赵与钱中至少有一个人作案”,贞察员B说:“钱与孙中至少有一个人作案”,贞察员C说:“孙与李中至少有一个人作案”,贞察员D说:“赵与孙中至少有一个人与此案无关”,贞察员E说:“钱与李中至少有一个人与此案无关”。如果这5个侦察员的话都是可信的,使用归结演绎推理求出谁是盗窃犯。

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

设C(x)表示x作案,Z表示赵,Q表示钱,S表示孙,L表示李 (2) 将已知事实用谓词公式表示出来

赵与钱中至少有一个人作案:C(Z)∨C(Q) 钱与孙中至少有一个人作案:C(Q)∨C(S) 孙与李中至少有一个人作案:C(S)∨C(L)

赵与孙中至少有一个人与此案无关:? (C (Z)∧C(S)),即 ?C (Z) ∨?C(S)

钱与李中至少有一个人与此案无关:? (C (Q)∧C(L)),即 ?C (Q) ∨?C(L) (3) 将所要求的问题用谓词公式表示出来,并与其否定取析取。 设作案者为u,则要求的结论是C(u)。将其与其否)取析取,得:

? C(u) ∨C(u)

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

C(Z)∨C(Q) ?C (Z) ∨?C(S)

C(Q)∨?C(S) C(Q)∨C(S)

?C(u)∨C(uC(Q) {Q/u} C(Q)

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

C(S)∨C(L) ?C (Q) ∨?C(L)

C(S)∨?C(Q) C(Q)∨C(S)

?C(u)∨C(uC(S) {S/u} C(S)

因此,孙也是盗窃犯。

3.18 设有子句集:

{P(x)∨Q(a, b), P(a)∨?Q(a, b), ?Q(a, f(a)), ?P(x)∨Q(x, b)} 分别用各种归结策略求出其归结式。

解:支持集策略不可用,原因是没有指明哪个子句是由目标公式的否定化简来的。 删除策略不可用,原因是子句集中没有没有重言式和具有包孕关系的子句。 单文字子句策略的归结过程如下:

?Q(a, f(a)) P(x)∨Q(a, b)

{b/f(a)}

P(a) ?P(x)∨Q(x, b)