【精品】求下列谓词公式的子句集15

【精品】求下列谓词公式的子句集15 习题三 求下列谓词公式的子句集。 (1) ，x，y(P(x,y) ,Q(x,y)) 解:去掉存在量词变为:P(a,b),Q(a,b) 变成子句集{ P(a,b),Q(a,b)} (P(x,y) ,Q(x,y)) (2) ,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 (,x)(P(x),(Q(x)?R(x)) 1 F (，x) (P(x) ?S(x) 2 G (，x)(S(x) ?R(x)) 证明:利用归结反演法，先证明F ? F??G是不可满足的。 12 求子句集: (1) ?P(x) ?Q(x) F1 (2) ?P(z) ?R(z) S (3)P(a) F2 (4)S(a) (5) ?S(y) ? ? R(y) (?G) 利用归结原理进行归结 (6)R(a) [(2),(3), σ={a/z}] 1 (7) ? R(a) [(4),(5), σ ={a/y}] 2 (8)Nil [(6),(7)] 所以S是不可满足得，从而G是F和F的逻辑结果。 125.设已知:(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 ，即S 比S中多了一个子句: 11 (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，即S比S多了一个子句: 22 (8) ’? (? T(A) )即T(A) 利用归结原理对进行归结: (9) ’T(A) ?T(C) [(1),(7)] (10)’T(C) [(6),(9)’] (11)’NIL [(8)’,(10)’]