人工智能导论复习资料

(2) 树和草都有叶和根； 解：

叶

Have

植物 是一种

树

根 Have 是一种 草 (3) 水草是草，且生长在水中；

解： AKO Live AKO 水草 草 水中 植物

(4) 果树是树，且会结果； 解：

AKO AKO Can 果树 树 结果 植物

(5) 梨树是果树中的一种，它会结梨。 解： AKO AKO Can 梨树 果树 结梨 树

17. 假设有以下一段天气预报：“北京地区今天白天晴，偏北风3级，最高气温12o，最低气温-2o，降水概率15%。”请用框架表示这一知识。

解：

Frame<天气预报> 地域：北京 时段：今天白天 天气：晴 风向：偏北 风力：3级

气温：最高：12度 最低：-2度 降水概率：15%

18. 按“师生框架”、“教师框架”、“学生框架”的形式写出一个框架系统的描述。 解：师生框架

Frame

Name：Unit（Last-name，First-name） Sex：Area（male，female） Default：male

Age：Unit（Years）

Telephone：Home Unit（Number）

Mobile Unit（Number）

教师框架

Frame

AKO Major：Unit（Major-Name） Lectures：Unit（Course-Name） Field：Unit（Field-Name）

Project ：Area（National，Provincial，Other） Default：Provincial

Paper：Area（SCI，EI，Core，General） Default：Core

学生框架

Frame

AKO< Teachers-Students > Major：Unit（Major-Name） Classes：Unit（Classes-Name）

Degree：Area（doctor，mastor, bachelor） Default：bachelor

19. 把下列谓词公式化成子句集：

(1) (?x)(?y)(P(x, y)∧Q(x, y)) (2) (?x)(?y)(P(x, y)→Q(x, y))

(3) (?x)(?y)(P(x, y)∨(Q(x, y)→R(x, y)))

(4) (?x) (?y) (?z)(P(x, y)→Q(x, y)∨R(x, z))

解：(1) 由于(?x)(?y)(P(x, y)∧Q(x, y))已经是Skolem标准型，且P(x, y)∧Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得 { P(x, y), Q(x, y)} 再进行变元换名得子句集： S={ P(x, y), Q(u, v)}

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

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

此公式已为Skolem标准型。 再消去全称量词得子句集： S={?P(x, y)∨Q(x, y)}

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

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

此公式已为前束范式。

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

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

此公式已为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))}

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

(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) 不可满足，其归结过程略

21. 对下列各题分别证明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(a) P(x)

{a/x} NIL

所以，G是F的逻辑结论

同理可求得(3)、(4)和(5)，其求解过程略。 22. 设已知：

(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?GF(v,u

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

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

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

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

{y/u} NI

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

23. 设有子句集：

{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)

{a/x} Q(a, b) ?Q(a, f(a))

{b/f(a)}

Q(a, b)