《应用归结原理例》PPT课件

《《应用归结原理例》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、应用归结原理的习题10/8/20211（一）应用归结原理进行定理证明应用归结原理进行定理证明的步骤：设要被证明的定理表示为：A1∧A2∧…∧AnB(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的逻辑结果，即公式A1A2～B是不可满足的。10/8/20213A1=x(P(x)y(～D(y)L(x,y)))=xy(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)))=xy(～P(x)～Q(y)～L(x,y))～B=～(x(D(x)～Q(x)))=x(D(x)Q(x))---D(b)Q(b)因此，公式A1A2～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