推理技术习题以及答案

1、习题三求下列谓词公式的子句集。xy(P(x,y)Q(x,y)解：去掉存在量词变为：P(a,b)Q(a,b)变成子句集P(a,b),Q(a,b)xy(P(x,y)Q(x,y)解：去掉蕴涵符号变为：xy(?P(x,y)Q(x,y)去掉全称量词变为：？P(x,y)Q(x,y)变成子句集?P(x,y)Q(x,y)(3)xy(P(x,y)Q(x,y)R(x,y)解：去掉蕴涵符号变为：xy(?(P(x,y)Q(x,y)R(x,y)否定符号作用于单个谓词变为：xy(?P(x,y)?Q(x,y)R(x,y)去掉存在量词变为：x(?P(x,f(x)?Q(x,f(x)R(x,f(x)去掉全称量词变为：(?P(x,

2、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)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)

3、P(f(x)(?(P(y)R(y,f(y)变为子句集：?(P(x)P(f(x),?(P(y)R(y,f(y)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)xyzuvw(p(x,y,z,u,v,w)(Q(x,y,z,u,v,w)?R(x,z,w)解：去掉存在量词变为：zv(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)去掉全称量词变

4、为：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.试判断下列子句集中哪些是不可满足的。S=P(y)?Q(y),?P(f(x)Q(y)解：(1)P(y)?Q(y)?P(f(x)Q(z)(适当改名使子句之间不含相同变元利用归结原理：(3) P(y)?P(f(x)(2)y/z(4) Tf(x)

5、/y归结不出空子句，所以原子句集是可以满足的。S=?P(x)Q(x),?Q(y)R(y),P(a),R(a)解：(1)?P(x)Q(x)？Q(y)R(y)(3) P(a)(4) R(a)利用归结原理判断Q(a)(3)a/x(6)R(a)(5)a/x归结不出空子句，所以是可满足的子句集。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)Q(b)利用归结原理来进行判断(6) ?Q(y)?L(a,y)(1)(2)a/x(7) L(a,b)b/z(8)?L

6、(a,b)(6)b/yNil解：（1）P(x)Q(x)R(x)(2)?P(y)R(y)(3)?Q(a)(4)?R(b)(8) (7)得到NIL所以原子句集不可满足。S=P(x)Q(x)R(x),?P(y)R(y),?Q(a),?R(b)利用归结原理来判断(5)S=P(x)Q(x),?Q(y)R(y),?P(z)Q(z),?R(u)解：（1）P(x)Q(x)?Q(y)R(y)?P(z)Q(z)?R(u)利用归结原理来判断?Q(u)u/y(6)?P(u)(3)(5)u/zQ(u)(1)(6)u/x(5)(7)(8)NIL所以原子句集S不可满足4.对下列各题请分别证明，G是否可肯定是F1,F2,的逻

7、辑结论(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/xNIL，,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/xL(a,b)，,b/z？Q(b)，

8、,b/yNIL，所以G是F1,F2的逻辑结论.此题的方法是：F1F2?G能推出空子句，就可以说明G是F1,F2的逻辑结论。(4) Fi(x)(P(x)(Q(x)AR(x)F2(x)(P(x)AS(x)G(x)(S(x)AR(x)证明：利用归结反演法，先证明F1VF2V?G是不可满足的求子句集：(1) ?P(x)VQ(x)11卜F1(2) ?P(z)VR(z)S(3)P(a)faF2(4)S(a)(5) ?S(y)V?R(y)(?G)利用归结原理进行归结(6)R(a)(2),(3),<71=a/z(8)Nil？R(a)(4),(5),o2=a/y(6),(7)所以S是不可满足得，从而G是F

9、1和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)xy(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)，,a/x，,a/y然后应用消解原理得P(f(a)L(f(a),a)？F(v)?L

10、(f(a),v)？L(f,a)NIL，,f(a)/u，,a/v,所以苍蝇是不清洁的.此题需注意谓词的定义：x喜欢y定义成L(x,y),另外要定义谓词:人。6证明：用命题公式表述题意为：(1)ABC(2)A?BC(3)BC结论：C是子句集的逻辑ABC,A?BC,BC的逻辑结果证：ABC？ABC？BC?CBCCNull由由，即：对子句集S=ABC,?ABC,?BC,?C施以归结，最后推出空子句，所以子句集不可满足，所以C是子句集ABC,?ABC,?BC的逻辑结果，所以公司一定要录取C.7.张某被盗，公安局派出五个侦探去调查.研究案情时，侦察员A说“赵与钱中至少有一人做案；侦察员B说“钱与孙中至少有

11、一人做案“；侦察员C说“孙与李中至少有一人做案“；侦察员D说“赵与孙中至少有一个与此案无关；侦察员E说“钱与李中至少有一人与此案无关.如果这五个侦察员的话都有是可信，请用归结原理求出谁是盗窃犯.解：设谓词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

12、)GA(x)P(qian)?P(sun)，,sun/xP(sun)?P(li)，P(sun)GA(sun)(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)A?T(C)如果A说

13、的是假话则有：？T(A)(T(B)VT(C)对B和C所说的话做相同的处理，可得：T(B)(?T(A)A?T(C)?T(B)(T(A)VT(C)T(C)(?T(A)V?T(B)?T(C)(T(A)AT(B)将上面的公式化为子句集，得到S:(1)?T(A)V?T(B)(2)?T(A)V?T(C)(3)T(A)VT(B)VT(C)(4)?T(B)V?T(C)(5)?T(A)V?T(B)V?T(C)(6)T(C)VT(A)(7)T(C)VT(B)首先求谁是老实人。把?T(x)VANS(x)并入S中，得到子句集S1，即S1比S中多了一个子句：(8) ?T(x)VANS(x)应用归结原理对S1进行归结：(9) ?T(A)VT(C)(1),(7)(10)T(C)(6),(9)AN