AI第五章作业讲解.doc

《AI第五章作业讲解.doc》由会员分享，可在线阅读，更多相关《AI第五章作业讲解.doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题五求下列谓词公式的子句集。(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)

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

3、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$yz $uv $w(p(x,y,z,u,v,w) (Q(x,y,z,u,

4、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. 试判断下列子句集中哪些

5、是不可满足的。(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

6、) 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)利用归结

7、原理来判断（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) 然后应用消解原理

8、得： 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

9、的逻辑结论。（4） F1 (x)(P(x)(Q(x)R(x)F2 ($x) (P(x) S(x)G ($x)(S(x) R(x)证明：利用归结反演法，先证明F1 F2 G是不可满足的。 求子句集：F1 (1) P(x) Q(x)S (2) P(z) R(z)F2 (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)所以S是不可满足得，从而G是F1和F2的逻辑结果。5.设已知：(1)凡是清洁的东西就有人喜欢： (2)人们都不喜欢苍蝇： 用归

10、结原理证明：苍蝇是不清洁的 证明：首先，定义如下谓词： 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)

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

12、人做案；侦察员说孙与李中至少有一人做案；侦察员说赵与孙中至少有一个与此案无关；侦察员说钱与李中至少有一人与此案无关如果这五个侦察员的话都有是可信，请用归结原理求出谁是盗窃犯(知识点，利用归结原理求取问题答案)解：设谓词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

13、) 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中至少有一个人说谎”。用归结原理

14、求谁是老实人，谁是说谎者？解：用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(

15、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)12 )( )(

16、 ()() (结归理)() 句子多比即集子得入定 ) ，老 人老不 话说从，老 答得)( ) ) ) )() )( ( 结行 ( 句子了比， 集到，入( ) 实老 ( ( ) ( )( ( ( )( ( 句化公)( )( ) ( ( ) )( )( ：可，相话 )( 有是说) ( (：则说 。说表（ 者者，实求结用谎一少和：；”说和答；说 “ 者是题个同别向，说来也，来人、犯盗谁来(谓助义法的结归只题或来结犯窃钱孙即是都和 ) ( , ) (/ )( ) ) ( ( ( ( ) (下如集 ( 式公 ( ) ( ) ( () 式词的为可犯盗 词案题求结用识犯是理用信有的侦个如无此一中钱员关案与至

17、孙说员做少至察做有中与说察案人少中员时究查调个局，某 一以，辑 子 所不句，空后，以 , ,由 ,由 , 果辑, 集是 ( ) 为意表命明人词义要 义 喜定谓注的洁不, / , ( ,( ) /, , , )(得理用 ),( ( )( 得得的论与)( ( ：) ( ( ) )()( ( (：式词为语上苍是 欢 ) 是：( 洁清) 词谓定先证的清蝇明原蝇苍都) 欢喜西东是 ：果果 ，足不) ) / ,( ) /)( (归行理 ( ) () ( () ) 集集 的足可 ，演用)( )( ) )( ) () 论辑 是以，空推 ：方论结逻,是 ( / , ), / )( ( 得原用 ( 集的 , (

18、:子 )( 句 先)() ( )( ( :元名，句，改句：论辑的 所/ , 得原消 )( :集的 )( ：集的) )( )( 结辑 可 证请列满可句 （ / （ ) ）（ ） (判理 )( ( )() ) )( 判原 )( ()( ) ( ),( ) ) 足足集以 ） ） ) )( ),)(判行原 ), ( ,() (), ) ( , ) )( 集子足以句子 ) ) 判原 ( ）（ ) ） ,() ( ) 的满是子所子出 )( ( )(理原变相含句改适 () 解) )(的满是哪集下试 ), , ) , (, ) ,集句),(, , ,() (, 元) ,(), , , (,( (, 为词) ( , ,( ( , ( 为词存), ,() ,( $ ), ：),( () 为称) ) (：量)( () 号涵掉) ( ) , () 集)( ) ) )() )( ) ()(：范),()( ( 变), ) (变在) ( ) (：号掉) ( $ () ,() ( ) ( ) , , ()( )(, )( , (), 为为 ) , ：词) ( ) )( ：在), ) ) ($为变个作号) ) ($：符掉) () ) ( 句 ),(：量称) ( , 为符掉) ),(),( 子 ()(为在) ( 集子式谓