推理技术习题以及答案

求下列谓词公式的子句集。 (1) xy(P(x,y) Q(x,y))

解：去掉存在量词变为：P(a,b)Q(a,b) 变成子句集{ P(a,b),Q(a,b)} (2) x y(P(x,y) Q(x,y))

解：去掉蕴涵符号变为：x y(¬ P(x,y)  Q(x,y))

去掉全称量词变为：¬ P(x,y)  Q(x,y) 变成子句集{ ¬ 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))

否定符号作用于单个谓词变为：

x y((¬ P(x,y) ¬ Q(x,y))  R(x,y))

去掉存在量词变为：x ((¬ P(x,f(x)) ¬ Q(x,f(x)))  R(x,f(x))) 去掉全称量词变为： (¬ P(x,f(x)) ¬ Q(x,f(x)))  R(x,f(x) 化合取范式为：

(¬ P(x,f(x))  R(x,f(x))(¬ Q(x,f(x))  R(x,f(x)) 变元：(¬ P(x,f(x))  R(x,f(x)))(¬ Q(y,f(y))  R(y,f(y))) 变成子句集{ ¬ P(x,f(x))  R(x,f(x)), ¬ Q(y,f(y))  R(y,f(y))} (4) x (P(x) y (P(y) R(x,y)))

解：去掉蕴涵符号变为：x (¬ (P(x)  y (P(y) R(x,y)))

去掉存在量词变为：x (¬ (P(x)  (P(f(x)) R(x,f(x)))

去掉全称量词变为： (¬ (P(x)  (P(f(x)) R(x,f(x))) 化合取范式为：(¬ (P(x)  P(f(x))) (¬ (P(x) R(x,f(x))) 变元：(¬ (P(x)  P(f(x))) (¬ (P(y) R(y,f(y))) 变为子句集：{¬ (P(x)  P(f(x)),¬ (P(y) R(y,f(y))} (5) x(P(x) x(P(y) R(x,y)))

解：去掉蕴涵符号变为：x(P(x) x(¬P(y) R(x,y)))

去掉存在量词变为：P(a) x(¬P(y) R(a,y)) 去掉全称量词变为：P(a)  (¬P(y) R(a,y)) 变成子句集：{ P(a) ，¬P(y) R(a,y) }

(6) xyz uv w(p(x,y,z,u,v,w) (Q(x,y,z,u,v,w) ¬R(x,z,w))) 解：去掉存在量词变为：

z v (p(a,b,z,f(z),v,g(z,v)) (Q(a,b,z,f(z),v, g(z,v) ¬R(a,z, g(z,v)))

去掉全称量词变为：

p(a,b,z,f(z),v,g(z,v)) (Q(a,b,z,f(z),v, g(z,v) ¬R(a,z, g(z,v)) 变元：

p(a,b,x,f(x),y,g(x,y)) (Q(a,b,z,f(z),v, g(z,v) ¬R(a,z, g(z,v)) 化成子句集：

{p(a,b,x,f(x),y,g(x,y)) , Q(a,b,z,f(z),v, g(z,v) ¬R(a,z, g(z,v)) } 3. 试判断下列子句集中哪些是不可满足的。 (1) S={P(y) ¬Q(y), ¬P(f(x)) Q(y)} 解：

（1） P(y) ¬Q(y)

（2） ¬P(f(x)) Q(z) (适当改名使子句之间不含相同变元 利用归结原理：

（3）P(y) ¬P(f(x)) (1)(2) {y/z} （4）T {f(x)/y}

归结不出空子句，所以原子句集是可以满足的。 (2) S={¬ P(x) Q(x), ¬ Q(y) R(y),P(a),R(a) } 解：（1）¬ P(x) Q(x) （2）¬ Q(y) R(y)

（3）P(a) （4）R(a) 利用归结原理判断

（5）Q(a) (1)(3) {a/x} （6）R(a) (2)(5) {a/x} 归结不出空子句，所以是可满足的子句集。

(3) S={¬ P(x) ¬Q(y) ¬L(x,y),P(a), ¬ R(z) L(a,z) ,R(b),Q(b)} 解：（1）¬ P(x) ¬Q(y) ¬L(x,y)

（2）P(a)

（3）¬ R(z) L(a,z) （4）R(b) （5）Q(b)

利用归结原理来进行判断 （6）¬Q(y) ¬L(a,y) (1)(2){a/x}

（7）L(a,b) (3)(4) {b/z} （8）¬L(a,b) （6）（5）{b/y} （9）Nil （8）（7） 得到NIL所以原子句集不可满足。

(4) S={P(x) Q(x) R(x),¬ P(y) R(y), ¬ Q(a), ¬R(b) } 解：（1）P(x) Q(x) R(x)

（2）¬ P(y) R(y) （3）¬ Q(a)） （4）¬R(b)

利用归结原理来判断 （5） （6） （7）

(5) S={P(x) Q(x),¬ Q(y) R(y), ¬ P(z) Q(z), ¬R(u) } 解：（1）P(x) Q(x)

（2）¬ Q(y) R(y) （3） ¬ P(z) Q(z) （4） ¬R(u)

利用归结原理来判断

（5）¬Q(u) （2）（4）{u/y} （6）¬P(u) （3）（5）{u/z} （7）Q(u) （1）（6）{u/x}

（8）NIL （5）（7） 所以原子句集S不可满足

4．对下列各题请分别证明，G是否可肯定是F1，F2，„的逻辑结论 （1）F: x(P(x)  Q(x)) G: x(P(x)  Q(x)) 解： F的子句集为： ① P(x) ② Q(y)

¬ G的子句集为: ③ ¬ P(z)  ¬ Q(z) 然后应用消解原理得：

④ ¬ Q(z) [ ①,③ ,{z/x}]

⑤ NIL [②,④,{z/y}] 所以G是F的逻辑结论．

此题应注意：化子句集时应改名，使子句①，②，③无同名变元。 (3)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的子句集：① ¬ P(x)¬ Q(y)¬ L(x,y) F2的子句集: ② P(a) ③ ¬R(z)L(a,z) ¬ G的子句集为: ④ R(b) ⑤ Q(b) 然后应用消解原理得:

⑥ ¬ Q(y)  ¬ L(a,y) [①,②,{a/x}] ⑦ L(a,b) [③,④,{b/z}] ⑧ ¬ Q(b) [⑥,⑦,{b/y}] ⑨NIL [⑤,⑧] 所以G是F1,F2的逻辑结论．

此题的方法是：F1  F2  ¬ G能推出空子句，就可以说明G是F1,F2的逻辑结论。

（4） F1 (x)(P(x)(Q(x)∧R(x))

F2 (x) (P(x) ∧S(x) G (x)(S(x) ∧R(x))

证明：利用归结反演法，先证明F1 ∨ F2 ∨¬G是不可满足的。 求子句集： (1) ¬P(x) ∨Q(x) (2) ¬P(z) ∨R(z) (3)P(a) (4)S(a)

(5) ¬S(y) ∨ ¬ R(y) (¬G)

利用归结原理进行归结

(6)R(a) [(2),(3), σ1={a/z}] (7) ¬ R(a) [(4),(5), σ2 ={a/y}] (8)Nil [(6),(7)]

F2

F1

S

所以S是不可满足得，从而G是F1和F2的逻辑结果。 5.设已知：(1)凡是清洁的东西就有人喜欢： (2)人们都不喜欢苍蝇：

用归结原理证明：苍蝇是不清洁的． 证明：首先，定义如下谓词：

C(x)：x是清洁的 P(x)：x是人 L(x,y)：x喜欢y F(x):x是苍蝇 然后将上述各语句翻译为谓词公式： 已知条件：(1)  x(C(x)   y(P(y)  L(y,x))) (2)  x  y(P(x)  F(y)  ¬ L(x,y))) 需证结论：(3)  x(F(x)  ¬ C(x)) 求题设与结论否定的子句集，得: ① ¬ C(x)  P(f(x)) ② ¬ C(y)  L(f(y),y) ③ ¬ P(u)  ¬ F(v)  ¬ L(u,v) ④ F(a) ⑤ C(a) 然后应用消解原理得:

⑥ P(f(a)) [①,⑤,{a/x}] ⑦ L(f(a),a) [②,⑤,{a/y}]

⑧ ¬ F(v)  ¬ L(f(a),v) [③,⑥,{f(a)/u}] ⑨ ¬ L(f(a),a) [④,⑧,{a/v}] ⑩ NIL [⑦,⑨,] 所以 苍蝇是不清洁的．

此题需注意谓词的定义：x喜欢y 定义成L(x,y)，另外要定义谓词：人。

6 证明：用命题公式表述题意为：

(1)ABC (2)A¬B C (3)B C

结论：C是子句集的逻辑{ABC , A¬B C , B C}的逻辑结果。 证：① ABC

② ¬ A B C ③ ¬BC ④ ¬ C

⑤ B  C 由①,② ⑥ C 由③,⑤ ⑦ Null 由④,⑥

即：对子句集S={ABC ,¬ A BC ,¬BC, ¬C}施以归结，最后推出空子句，所以子句集不可满足，所以C是子句集{ABC ,¬ A BC ,¬BC}的逻辑结果，所以公司一定要录取C.

７．张某被盗，派出五个侦探去调查．研究案情时，侦察员Ａ说＂赵与钱中至少有一人做案＂；侦察员Ｂ说＂钱与孙中至少有一人做案＂；侦察员Ｃ说＂孙与李中至少有一人做案＂；侦察员Ｄ说＂赵

与孙中至少有一个与此案无关＂；侦察员Ｅ说＂钱与李中至少有一人与此案无关＂．如果这五个侦察员的话都有是可信，请用归结原理求出谁是盗窃犯．

解：设谓词P(x)表示x是盗窃犯． 则题意可表述为如下的谓词公式： F1:P(zhao)  P(qian) F2: P(qian)  P(sun) F3: P(sun)  P(li) F4: ¬ P(zhao)  ¬ P(sun) F5: ¬ P(qian)  ¬ P(li) 求证的公式为： xP(x) 子句集如下： ① P(zhao)  P(qian) ② P(qian)  P(sun) ③ P(sun)  P(li) ④ ¬ P(zhao)  ¬ P(sun) ⑤ ¬ P(qian)  ¬ P(li) ⑥ ¬ P(x) GA(x)

⑦ P(qian)  ¬ P(sun) ⑧ P(sun)  ¬ P(li) ⑨ P(sun) ⑩ GA(sun) [①,④] ②,⑤] [③,⑧] [⑥,⑨,{sun/x}]

[ (11)P(qian) [⑦,⑨]

(12)GA(qian) [⑥,(11),{qian/x} 所以，sun和qian都是盗窃犯．即：孙和钱都是盗窃犯． 此题需定义一个辅助谓词GA(x)来求出谁是盗窃犯。

设A、B、C中有人从来不说真话，也有人从来不说谎话，某人向这三人分别同时提出一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个人说谎”。用归结原理求谁是老实人，谁是说谎者？ 解：用T（x）表示x说真话。

如果A说的是真话则有：T(A)  (¬T(B) ∧ ¬T(C)) 如果A说的是假话则有： ¬ T(A)  (T(B) ∨ T(C)) 对B和C所说的话做相同的处理，可得：

T(B)  (¬T(A) ∧¬T (C) )¬T(B) 

(T(A) ∨ T(C))

T(C)  (¬T(A) ∨ ¬T(B)) ¬ T(C)  (T(A) ∧ T(B)) 将上面的公式化为子句集，得到S： (1)¬ T(A) ∨ ¬T(B) (2)¬ T(A) ∨ ¬T(C ) (3)T(A) ∨ T(B ) ∨ T(C ) (4)¬ T(B) ∨ ¬T(C )

(5)¬ T(A) ∨ ¬T(B ) ∨ ¬T(C ) (6)T(C) ∨ T(A)

(7)T(C) ∨ T(B)首先求谁是老实人。把¬ T(x) ∨ANS(x)并

入S中，得到子句集S 1 ，即S 1比S中多了一个子句：

(8) ¬ T(x) ∨ANS(x)

应用归结原理对S 1进行归结：

(9) ¬ T(A) ∨ T(C) [(1),(7)] (10)T(C) [(6),(9)] (11)ANS(C) [(8),(10)] 这样就得到了答案，即C是老实人，即C从来不说假话。 下面来证明B和A不是老实人，设A不是老实人，则有¬ T(A) ,

将其

否定并入S中，得到子句集S2，即S2比S多了一个子句： (8) ’¬ (¬ T(A) )即T(A) 利用归结原理对进行归结：

(9) ’T(A) ∨T(C) [(1),(7)] (10)’T(C) [(6),(9)’] (11)’NIL [(8)’,(10)’]