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