英语四级学习资料-养胃的水果有哪些

习题三
求下列谓词公式的子句集。
(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) {yz}
（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) {ax}
（6）R(a) (2)(5) {ax}
归结不出空子句，所以是可满足的子句集。
(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){ax}

（7）L(a,b) (3)(4) {bz}
（8）¬L(a,b) （6）（5）{by}
（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）{uy}
（6）¬P(u) （3）（5）{uz}
（7）Q(u) （1）（6）{ux}

（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) [ ①,③ ,{zx}]
⑤ NIL [②,④,{zy}]
所以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) [①,②,{ax}]
⑦ L(a,b) [③,④,{bz}]
⑧ ¬ Q(b) [⑥,⑦,{by}]
⑨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
={az}]
(7) ¬ R(a) [(4),(5), σ
2
={ay}]
(8)Nil [(6),(7)]
F2

F1

S

< br>所以S是不可满足得，从而G是F
1
和F
2
的逻辑结果。
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)) [①,⑤,{ax}]
⑦ L(f(a),a) [②,⑤,{ay}]

⑧ ¬ F(v)  ¬ L(f(a),v) [③,⑥,{f(a)u}]
⑨ ¬ L(f(a),a) [④,⑧,{av}]
⑩ 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)
[①,④]
②,⑤]
[③,⑧]
[⑥,⑨,{sunx}]

[

(11)P(qian) [⑦,⑨]
(12)GA(qian) [⑥,(11),{qianx}
所以，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中，得到子句集S
2
，即S
2
比S多了一个子句：
(8) ’¬ (¬ T(A) )即T(A)
利用归结原理对进行归结：
(9) ’T(A) ∨T(C) [(1),(7)]
(10)’T(C) [(6),(9)’]
(11)’NIL [(8)’,(10)’]