内容发布更新时间 : 2024/12/23 8:33:57星期一 下面是文章的全部内容请认真阅读。

p(x)?S(x,f(x)) Q(x) P(w)?B(w)

I. 子句变量标准化后, 最终的子句集为：

p(x)?S(x,f(x)) Q(y)

P(w)?B(w)

(2) 参见课本P122 A. 消去蕴涵符符号：

(?x)[~P(x)?[?y[~P(y)?P(f(x,y))]?~?y[~Q(x,y)?P(y)]]] B. 减少否定符号的辖域:

(?x)[~P(x)?[?y[~P(y)?P(f(x,y))]??y[Q(x,y)?~P(y)]]] C. 变量标准化:

(?x)[~P(x)?[?y[~P(y)?P(f(x,y))]??w[Q(x,w)?~P(w)]]] D. 消去存在量词:

(?x)[~P(x)?[?y[~P(y)?P(f(x,y))]?[Q(x,g(x))?~P(g(x))]]] E. 化为前束型:

(?x)(?y)[~P(x)?[[~P(y)?P(f(x,y))]?[Q(x,g(x))?~P(g(x))]]] F. 把母式化为合取范式:

(?x)(?y)[~P(x)?~P(y)?P(f(x,y))]?[~P(x)?Q(x,g(x))]?[~P(x)?~P(g(x))]]

G. 消去全称量词:

[~P(x)?~P(y)?P(f(x,y))]?[~P(x)?Q(x,g(x))]?[~P(x)?~P(g(x))]]

H. 消去合取词:~P(x)?~P(y)?P(f(x,y))

~P(x)?Q(x,g(x)) ~P(x)?~P(g(x)) I. 更改变量名:

~P(x1)?~P(y)?P(f(x1,y)) ~P(x2)?Q(x2,g(x2))

~P(x3)?~P(g(x3))

4.7 把下面的表达式转化成子句形式

（1）((?x)[p(x)]?(?x)[Q(x)]?(?x)[P(x)?Q(x)]

（2）(?x)[P(x)]?(?x)[(?z)[Q(x,z)]?(?z)[R(x,y,z)]]

（3）(?x)[P(x)?(?y)[(?z)[Q(x,y)]?~(?z)[R(y,x)]]] [解]

(1) ((?x)P(x)?(?x)Q(x))?(?x)(P(x)?Q(x)) ?((?x)P(x)?(?x)Q(x))?(?x)(P(x)?Q(x)) (?(?x)P(x)??(?x)Q(x))?(?x)(P(x)?Q(x))

((?x)?P(x)?(?x)?Q(x))?(?x)(P(x)?Q(x)) ((?x)?P(x)?(?x)?Q(x))?(?z)(P(z)?Q(z))

((?x)?P(x)?(?y)?Q(y))?(P(a)?Q(a)) (?x)(?y)(?P(x)??Q(y))?(P(a)?Q(a))) (?P(x)??Q(y))?(P(a)?Q(a))

(?P(x)?P(a)?Q(a))??Q(y))?(P(a)?Q(a))

则子句集为

9

S?{?P(x)?P(a)?Q(a)),?Q(y))?(P(a)?Q(a)} (2) (?x)P(x)?(?x)[(?z)Q(x,z)?(?z)R(x,y,z)]

(?y)((?x)P(x)?(?x)[(?z)Q(x,z)?(?z)R(x,y,z)]) (?y)(?(?x)P(x)?(?x)[(?z)Q(x,z)?(?z)R(x,y,z)])

(?y)((?x)?P(x)?(?x)[(?z)Q(x,z)?(?z)R(x,y,z)])

(?y)((?x)?P(x)?(?t)[(?z)Q(t,z)?(?u)R(t,y,u)])

(?y)(?P(f1(y))?(?z)Q(f2(y),z)?(?u)R(f2(y),y,u))

(?y)(?z)(?u)(?P(f1(y))?Q(f2(y),z)?R(f2(y),y,u)) (?P(f1(y))?Q(f2(y),z)?R(f2(y),y,u)) 则子句集为

S?{?P(f1(y))?Q(f2(y),z)?R(f2(y),y,u)}

(3) (?x)[P(x)?(?y)[(?z)[Q(x,y)]??(?z)R(y,x)]]

(?x)[?P(x)?(?y)[?(?z)[Q(x,y)]??(?z)R(y,x)]] (?x)[?P(x)?(?y)[(?z)[?Q(x,y)]?(?z)R(y,x)]] (?x)[?P(x)?(?y)[(?z)[?Q(x,y)]?(?u)R(y,x)]] (?x)[?P(x)?(?y)[?Q(x,y)?R(y,x)]] (?x)(?y)[?P(x)??Q(x,y)?R(y,x)] ?P(x)??Q(x,y)?R(y,x)

则子句集为

S?{?P(x)??Q(x,y)?R(y,x)} 4.10 求证G是F1和F2的逻辑结论。 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))

[证明] 首先将F1,F2和?G化为子句集： F1： (?x)(P(x)?(?y)(Q(y)??L(x,y)))

?(?x)(?P(x)?(?y)(?Q(y)??L(x,y))) ?(?x)(?y)(?P(x)?(?Q(y)??L(x,y))) 所以S1?{?P(x)?(?Q(y)??L(x,y))}

F2：(?x)(P(x)?(?y)(R(y)?L(x,y))) ?(?x)(?y)(P(x)?(?R(y)?L(x,y)) ) ?(?y)(P(a)?(?R(y)?L(a,y)) )所以S2?{P(a),?R(y)?L(a,y)}

?G: (?x)(R(x)??Q(x)) ?(?x)(?R(x)??Q(x)) ?(?x)(R(x)?Q(x)) ?(R(b)?Q(b)) 所以S3?{R(b),Q(b)}

下面进行归结：

① ?P(x)?(?Q(y)??L(x,y) ② P(a)

③ ?R(y)?L(a,y)

④ R(b) ⑤ Q(b)

⑥ L(a,b) ③和④

10

⑦ ?Q(y)??L(a,y) ①和② ⑧ ?L(a,b) ⑤和⑦

⑨ Nil ⑥和⑧ 所以，G是F1,F2的逻辑结论。

4.12利用归结原理证明：“有些患者喜欢任一医生。没有任一患者喜欢任一庸医。所以没有庸医的医生”。

[解] 定义谓词为: P(x): “x是患者”, D(x): “x是医生”, Q(x): “x是庸医”, L(x,y): “x喜欢y”, 则前提与结论可以符号化为:

A1: (?x)(P(x)?(?y)(D(y)?L(x,y))) A2: (?x)(P(x)?(?y)(Q(y)??L(x,y)))

G: (?x)(D(x)??Q(x))

目前是证明G是A1和A2的逻辑结论, 即证明A1?A2??G是不可满足的. 首先, 求出子句集合:

A1: (?x)(P(x)?(?y)(D(y)?L(x,y)))

?(?x)(?y)(P(x)?(?D(y)?L(x,y))) ?(?y)(P(a)?(?D(y)?L(a,y)))

A2: (?x)(P(x)?(?y)(Q(y)??L(x,y)))

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

~G: ?(?x)(D(x)??Q(x))

?(?x)(D(x)?Q(x)) ?(D(b)?Q(b))

因此A1?A2??G的子句集合S为:

S?{P(a),?D(y)?L(a,y),?P(x)??Q(y)??L(x,y),D(b),Q(b)}

归结证明S是不可满足的:

(1)P(a)(2)?D(y)?L(a,y)(3)?P(x)??Q(y)??L(x,y) S (4)D(b)(5)Q(b)(6)L(a,b) (2)(4) (7)?Q(y)??L(a,b) (1)(3)

(8)?L(a,b) (5)(7)

(9) Nil (6)(8)

11

4.14已知：能阅读的都是有文化的； 海豚是没有文化的； 某些海豚是有智能的；

用归结反演法证明：某些有智能的并不能阅读。

[证明] 首先定义谓词:

R(x): x能阅读, L(x): x有文化 D(x): x是海豚, I(x): x有智能 将前提形式化地表示为: A1: (?x)(R(x)?L(x))

A2: (?y)(D(y)??L(y)) A3: (?z)(D(z)?I(z)) 将结论形式化地表示为: G: (?w)(I(w)??R(w))

即要证明A1?A2?A3?G为真. 即证明A1?A2?A3??G是不可满足的. 把它化为子句集为:

S?{?R(x)?L(x),?D(y)??L(y),D(A),I(A),?I(w)?R(w)}

现在用归结证明S是不可满足的:

(1)?R(x)?L(x)(2)?D(y)??L(y) (3)D(A) S

(4)I(A)(5)?I(w)?R(w)(6)R(A) (4)(5) (7)L(A) (1)(6)

(8)?D(A) (2)(7) (9) Nil (3)(8)

4.15某人被盗，公安局派出所派出5个侦察员去调查。研究案情时: 侦察员A说：“赵与钱中至少有一人作案”； 侦察员B说：“钱与孙中至少有一人作案”； 侦察员C说：“孙与李中至少有一人作案”；

侦察员D说：“赵与孙中至少有一人与此案无关”； 侦察员E说：“钱与李中至少有一人与此案无关”。 如果这5个侦察员的话都是可信的，试问谁是盗窃犯呢？

[解]

第一步: 设谓词P(x)表示x是作案者，所以根据题意:

A: P(zhao)∨P(qian) B: P(qian)∨P(sun) C: P(sun)∨P(li) D: ~P(zhao)∨~P(sun) E: ~P(qian)∨~P(li) 以上每个侦查员的话都是一个子句。

第二步：将待求解的问题表示成谓词。设y是盗窃犯，则问题的谓词公式为P(y),将其否定并与ANS(y)做析取得: ~P(y)∨ANS(y)第三步:求前提条件及~P(y)∨ANS(y)的子句集，并将各子句列表如下:

(1) P(zhao)∨P(qian)

12