资源描述:
《《应用归结原理例》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、应用归结原理的习题10/8/20211(一)应用归结原理进行定理证明应用归结原理进行定理证明的步骤:设要被证明的定理表示为:A1∧A2∧…∧AnB(1)首先否定结论B,并将否定后的公式~B与前提公式集组成如下形式的谓词公式:G=A1∧A2∧…∧An∧~B(2)求谓词公式G的子句集S。(3)应用归结原理,证明子句集S的不可满足性。10/8/20212应用归结原理进行定理证明-习题1例.已知:某些病人喜欢所有的医生,没有一个病人喜欢任意一个骗子。证明:任意一个医生都不是骗子。证明:知识表示:令P(x):x是病人D(x):x是医
2、生Q(x):x是骗子L(x,y):x喜欢yA1:x(P(x)y(D(y)L(x,y)))A2:x(P(x)y(Q(y)~L(x,y)))B:x(D(x)~Q(x))我们要证明B是A1和A2的逻辑结果,即公式A1A2~B是不可满足的。10/8/20213A1=x(P(x)y(~D(y)L(x,y)))=xy(P(x)(~D(y)L(x,y)))---y(P(a)(~D(y)L(a,y)))A2=x(P(x)y(~Q(y)~L(x,y)))=x(~P(x)y(~Q(y
3、)~L(x,y)))=xy(~P(x)~Q(y)~L(x,y))~B=~(x(D(x)~Q(x)))=x(D(x)Q(x))---D(b)Q(b)因此,公式A1A2~B的子句集为S={P(a),~D(y)L(a,y),~P(x)~Q(y)~L(x,y),D(b),Q(b)}10/8/20214S不可满足的归结演绎序列为:P(a)~D(y)L(a,y)~P(x)~Q(y)~L(x,y)D(b)Q(b)L(a,b)由(2)、(4)mgu:{b/y}~Q(y)~L(a,y)由(1)、(3)m
4、gu:{a/x}~L(a,b)由(5)、(7)mgu:{b/y}由(6)、(8)10/8/20215应用归结原理进行定理证明-习题2练习:设有下列知识:F1:自然数都是大于等于零的整数;F2:所有整数不是偶数就是奇数;F3:偶数除以2是整数。求证:所有自然数不是奇数就是其一半为整数的数。定义谓词:N(x):x是自然数;I(x):x是整数;GZ(x):x大于等于零;E(x):x是偶数;O(x):x是奇数。定义函数f(x):x除以2。10/8/20216应用归结原理进行定理证明-习题3练习:(1)马科斯(Marcus)是男人;
5、(2)马科斯是庞贝人;(3)所有庞贝人都是罗马人;(4)恺撒(Caesar)是一位统治者;(5)所有罗马人忠于或仇恨恺撒;(6)每个人都忠于某个人;(7)男人们只想暗杀他们不忠于的统治者;(8)马科斯试图暗杀恺撒。证明:马科斯仇恨恺撒。定义谓词:Man(x):x是男人;Pompeian(x):x是庞贝人;Roman(x):x是罗马人;Ruler(x):x是统治者;Loyalto(x,y):x忠于y;Hate(x,y):x仇恨y;Tryassassinate(x,y):x试图暗杀y。10/8/20217练习:“快乐学生”问题假
6、设:任何通过计算机考试并获奖的人都是快乐的;任何肯学习或幸运的人都可以通过所有考试;张不肯学习但他是幸运的;任何幸运的人都能获奖。证明:张是快乐的。定义谓词Pass(x,y):x通过考试y;Win(x):x获奖;Happy(x):x快乐;Study(x):x肯学习;Lucky(x):x幸运。应用归结原理进行定理证明-习题410/8/20218应用归结原理进行定理证明-习题5练习--“激动人心的生活”问题假设:所有不贫穷并且聪明的人都是快乐的;那些看书的人是聪明的;李明能看书且不贫穷;快乐的人过着激动人心的生活。求证:李明过着
7、激动人心的生活。定义谓词:Poor(x):x贫穷;Smart(x):x聪明;Happy(x):x快乐;Read(x):x看书;Exciting(x):x过着激动人心的生活。10/8/20219(二)利用归结原理求取问题答案利用归结原理求取问题答案的步骤:(1)把已知前提条件用谓词公式表示出来,并化成相应的子句集,设该子句集的名字为S1。(2)把待求解的问题也用谓词公式表示出来,然后将其否定,并与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词,其变量必须与问题公式的变量完全一致。(3)把(2)中的
8、析取式化为子句集,并把该子句集与S1合并构成子句集S。10/8/202110(4)对子句集S应用归结原理进行归结,在归结的过程中,通过合一,改变ANSWER中的变元。(5)如果得到归结式ANSWER,则问题的答案即在ANSWER谓词中。10/8/202111利用归结原理求取问题答案-习题1