《应用归结原理例-2014》由会员分享，可在线阅读，更多相关《应用归结原理例-2014（20页珍藏版）》请在金锄头文库上搜索。
1、应用归结原理的习题*1（一）应用归结原理进行定理证明应用归结原理进行定理证明的步骤：设要被证明的定理表示为：A1A2An B(1)首先否定结论B，并将否定后的公式B与前提公式集组成如下 形式的谓词公式： G= A1A2AnB(2) 求谓词公式G的子句集S。(3) 应用归结原理，证明子句集S的不可满足性。Date2应用归结原理进行定理证明-习题1 例.已知:某些病人喜欢所有的医生，没有一个病人喜欢任意一个骗子。证明: 任意一个医生都不是骗子。 证明: 知识表示：令P(x)：x是病人 D(x)：x是医生Q(x)：x是骗子 L(x, y)：x喜欢y A1: x (P(x) y(D(y)L(x, y)
2、 A2: x(P(x) y(Q(y) L(x, y) B: x(D(x) Q(x) 我们要证明B是A1和A2的逻辑结果，即公式A1A2B是不可满足的 。 Date3A1=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) 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) 因此，公式A1A2B的子句集为 SP(a),D(y)L(a,y),P(x
3、)Q(y)L(x, y),D(b),Q(b)Date4S不可满足的归结演绎序列为：lP(a)lD(y) L(a, y)lP(x) Q(y) L(x, y)lD(b)lQ(b)lL(a, b) 由(2)、(4) mgu:b/ylQ(y) L(a, y) 由(1)、(3) mgu:a/xlL(a, b) 由(5)、(7) mgu:b/yl 由(6)、(8)Date5应用归结原理进行定理证明-习题2练习：设有下列知识： F1：自然数都是大于等于零的整数； F2：所有整数不是偶数就是奇数； F3：偶数除以2是整数。 求证：所有自然数不是奇数就是其一半为整数的数。定义谓词： N(x)：x是自然数；I(x
4、)：x是整数；GZ(x):x大于等于零; E(x)：x是偶数; O(x)：x是奇数。 定义函数f(x)：x除以2。Date6应用归结原理进行定理证明-习题3练习练习 ： (1)马(Marcus)是男人；(2)马是庞贝庞贝 人； (3)所有庞贝庞贝 人都是罗马罗马 人；(4)恺恺撒(Caesar)是一位统统治者； (5)所有罗马罗马 人忠于或仇恨恺恺撒；(6)每个人都忠于某个人； (7)男人们们只想暗杀杀他们们不忠于的统统治者；(8)马试图试图 暗杀恺杀恺 撒 。 证证明：马仇恨恺恺撒。定义谓词义谓词 ： Man(x)：x是男人； Pompeian(x)：x是庞贝庞贝 人； Roman(x):x
5、是罗马罗马 人; Ruler(x):x是统统治者; Loyalto(x,y):x忠于y; Hate(x,y):x仇恨y; Tryassassinate(x,y):x试图试图 暗杀杀y。Date7练习：“快乐学生”问题 假设设：任何通过计过计 算机考试试并获奖获奖 的人都是快乐乐的；任何肯学习习或幸运的人都可以通过过所有考试试；张张不肯学习习但他是幸运的；任何幸运的人都能获奖获奖 。 证证明：张张是快乐乐的。定义谓词义谓词 Pass(x,y):x通过过考试试y;Win(x):x获奖获奖 ;Happy(x):x快乐乐； Study(x):x肯学习习; Lucky(x):x幸运。应用归结原理进行定理
6、证明 -习题4Date8应用归结原理进行定理证明-习题5 练习练习 -“激动动人心的生活”问题问题 假设设：所有不贫穷贫穷 并且聪聪明的人都是快乐乐的；那些看书书的人是聪聪明的；李明能看书书且不贫穷贫穷 ；快乐乐的人过过着激动动人心的生活。 求证证：李明过过着激动动人心的生活。定义谓词义谓词 ： Poor(x):x贫穷贫穷 ； Smart(x):x聪聪明； Happy(x):x快乐乐； Read(x):x看书书； Exciting(x):x过过着激动动人心的生活。Date9（二）利用归结原理求取问题答案利用归结原理求取问题答案的步骤：（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集
7、，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并 与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致 。（3）把（2）中的析取式化为子句集，并把该子句集与S1合并构 成子句集S。Date10（4）对子句集S应用归结原理进行归结，在归 结的过程中，通过合一，改变ANSWER中的变元。（5）如果得到归结式ANSWER，则问题的答 案即在ANSWER谓词中。Date11利用归结原理求取问题答案-习题1例. 任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问:Peter
8、的父亲是谁？解 第一步：将已知条件用谓词公式表示出来，并化成 子句集，那么要先定义谓词。（1） 定义谓词：设Father(x,y)表示x是y的父亲。Brother(x,y)表示x和y是兄弟。Date12（2） 将已知事实用谓词公式表示出来。F1 ：任何兄弟都有同一个父亲。xyz (Brother(x,y)Father(z,x)Father(z,y)F2：John和Peter是兄弟。Brother(John,Peter)F3： John的父亲是David。Father(David, John)（3） 将它们化成子句集得：S1=Brother(x,y)Father(z,x)Father(z,y),
9、Brother(John,Peter), Father(David,John)Date13第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。设Peter的父亲是u，则有：Father(u,Peter)。将其否定与ANSWER作析取，得：G：Father(u,Peter)ANSWER(u)Date14第三步：将上述公式G化为子句集S2,并将S1和S2合并到S。S2 =Father(u,Peter)ANSWER(u)S= S1S2将S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）
10、Father(David,John)。（4）Father(u,Peter)ANSWER(u)。Date15第四步：应用归结原理进行归结（5）Brother(John,y)Father(David,y) （1）与（3）归结 =David/z,John/x（6）Brother(John,Peter)ANSWER(David) （4）与（5）归结 =David/u,Peter/y（7）ANSWER(David) （2）与（6）归结第五步：得到了归结式ANSWER(David)，答案即在其中，所以 u=David。即Peter的父亲是David。Date16利用归结原理求取问题答案-习题2练习： 已知
11、： F1:王先生是小李的老师； F2:小李与小张是同班同学； F3:如果x与y是同班同学，则x的老师也是y的老师。 求：小张的老师是谁？定义谓词：T(x,y)：x是y的老师；C(x,y)：x与y是同班同学。Date17利用归结原理求取问题答案-习题3练习：某记者到一个孤岛上采访，遇到了一个难题，即岛上有 许多人说假话，因而难以保证新闻报道的正确性。不过有一点 她是清楚的，这个岛上的人有一特点，说假话的人从来不说真 话，说真话的人也从来不说假话。有一次，记者遇到了孤岛上 的三个人，为了弄清楚谁说真话，谁说假话，她向三个人中的 每一个都提了同样的问题，即“谁是说谎者？”结果，a 回答： “b和c都
12、是说谎者”；b回答：“a和c都是说谎者”；c回答：“a 和b至少有一个是说谎者”。试问记者如何才能从这些回答中理 出头绪。定义谓词： T(x):x说真话。Date18利用归结原理求取问题答案-习题4破案问题：在一栋房子里发生了一件神秘的谋 杀案，现在可以肯定以下几点事实： (1)在这栋房子里仅住有A,B,C三人； (2)是住在这栋房子里的人杀了A； (3)谋杀者非常恨受害者A； (4)A所恨的人，C一定不恨； (5)除了B以外，A恨所有的人； (6)B恨所有不比A富有的人；Date19(7)A所恨的人，B也恨； (8)没有一个人恨所有的人； (9)杀人嫌疑犯一定不会比受害者富有。 为了推理需要，增加如下常识： (10)A不等于B。 问：谋杀者是谁？定义谓词： L(x):住在这栋房子里； SK(x,y):x杀了y; H(x,y):x恨y; R(x,y):x比y富有。Date20
