习题三求下列谓词公式的子句集。

(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） F 1 (∀x)(P(x)→(Q(x)∧R(x))F 2 (∃x) (P(x) ∧S(x)G (∃x)(S(x) ∧R(x))证明：利用归结反演法，先证明F 1 ∨ F 2 ∨¬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)] SF1 F2所以S是不可满足得，从而G是F1和F2的逻辑结果。

5.设已知：(1)凡是清洁的东西就有人喜欢：(2)人们都不喜欢苍蝇：用归结原理证明：苍蝇是不清洁的．证明：首先，定义如下谓词：C(x)：x是清洁的P(x)：x是人L(x,y)：x喜欢yF(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)来求出谁是盗窃犯。