应用归结原理例讲课课件

应用归结原理的习题在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：（1）若被归结的子句C1和C2中具有相同的变元时，需要将其中一个子句的变元更名，否则可能无法合一，从而没有办法进行归结。（2）在求归结式时，不能同时消去两个互补文字对，消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。（3）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的化简。11/16/20221应用归结原理的习题在谓词逻辑中，对子句进行归结推理时，要注意（一）应用归结原理进行定理证明应用归结原理进行定理证明的步骤：

设要被证明的定理可用谓词公式表示为如下的形式：

A1∧A2∧…∧An→B(1)首先否定结论B，并将否定后的公式～B与前提公式集组成如下形式的谓词公式：G=A1∧A2∧…∧An∧～B(2)

求谓词公式G的子句集S。(3)

应用归结原理，证明子句集S的不可满足性。11/16/20222（一）应用归结原理进行定理证明应用归结原理进行定理证明的步骤应用归结原理进行定理证明-习题1

例.已知:某些病人喜欢所有的医生，没有一个病人喜欢任意一个骗子。证明:任意一个医生都不是骗子。证明:知识表示：令P(x)：x是病人D(x)：x是医生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是不可满足的。11/16/20223应用归结原理进行定理证明-习题1例.已知:某些病人喜欢所有A1=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)～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)｝11/16/20224A1=x(P(x)y(～D(y)L(x,S不可满足的归结演绎序列为：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)mgu:{a/x}～L(a,b)由(5)、(7)mgu:{b/y}由(6)、(8)11/16/20225S不可满足的归结演绎序列为：11/10/20225应用归结原理进行定理证明-习题2练习：设有下列知识：F1：自然数都是大于等于零的整数；F2：所有整数不是偶数就是奇数；F3：偶数除以2是整数。求证：所有自然数不是奇数就是其一半为整数的数。定义谓词：N(x)：x是自然数；I(x)：x是整数；GZ(x):x大于等于零;E(x)：x是偶数;O(x)：x是奇数。定义函数f(x)：x除以2。11/16/20226应用归结原理进行定理证明-习题2练习：设有下列知识：11/1应用归结原理进行定理证明-习题3练习：(1)马科斯(Marcus)是男人；(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。11/16/20227应用归结原理进行定理证明-习题3练习：11/10/20227练习：“快乐学生”问题假设：任何通过计算机考试并获奖的人都是快乐的；任何肯学习或幸运的人都可以通过所有考试；张不肯学习但他是幸运的；任何幸运的人都能获奖。证明：张是快乐的。定义谓词Pass(x,y):x通过考试y;Win(x,prize):x获奖;Happy(x):x快乐；Study(x):x肯学习;Lucky(x):x幸运。应用归结原理进行定理证明-习题411/16/20228练习：“快乐学生”问题应用归结原理进行定理证明-习题411应用归结原理进行定理证明-习题5练习--“激动人心的生活”问题假设：所有不贫穷并且聪明的人都是快乐的；那些看书的人是聪明的；李明能看书且不贫穷；快乐的人过着激动人心的生活。求证：李明过着激动人心的生活。定义谓词：Poor(x):x贫穷；Smart(x):x聪明；Happy(x):x快乐；Read(x):x看书；Exciting(x):x过着激动人心的生活。11/16/20229应用归结原理进行定理证明-习题5练习--“激动人心的生活”（二）利用归结原理求取问题答案利用归结原理求取问题答案的步骤：（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。（3）把（2）中的析取式化为子句集，并把该子句集与S1合并构成子句集S。11/16/202210（二）利用归结原理求取问题答案利用归结原理求取问题答案的步骤（4）对子句集S应用归结原理进行归结，在归结的过程中，通过合一，改变ANSWER中的变元。（5）如果得到归结式ANSWER，则问题的答案即在ANSWER谓词中。11/16/202211（4）对子句集S应用归结原理进行归结，在归结的过程中，通过合利用归结原理求取问题答案-习题1例.任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问:Peter的父亲是谁？解第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。（1）

定义谓词：设Father(x,y)表示x是y的父亲。Brother(x,y)表示x和y是兄弟。11/16/202212利用归结原理求取问题答案-习题1例.任何兄弟都有同一个父亲（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),Brother(John,Peter),Father(David,John)}11/16/202213（2）将已知事实用谓词公式表示出来。11/10/20221第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。设Peter的父亲是u，则有：Father(u,Peter)。将其否定与ANSWER作析取，得：G：～Father(u,Peter)∨ANSWER(u)11/16/202214第二步：把问题用谓词公式表示出来，11/10/202214第三步：将上述公式G化为子句集S2,并将S1和S2合并到S。S2={～Father(u,Peter)∨ANSWER(u)}S=S1∪S2将S中各子句列出如下：（1）～Brother(x,y)∨～Father(z,x)∨Father(z,y)。（2）Brother(John,Peter)。（3）Father(David,John)。（4）～Father(u,Peter)∨ANSWER(u)。11/16/202215第三步：将上述公式G化为子句集S2,并将S1和S2合并到S。第四步：应用归结原理进行归结（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。11/16/202216第四步：应用归结原理进行归结11/10/202216利用归结原理求取问题答案-习题2练习：已知：F1:王先生是小李的老师；F2:小李与小张是同班同学；F3:如果x与y是同班同学，则x的老师也是y的老师。求：小张的老师是谁？定义谓词：T(x,y)：x是y的老师；C(x,y)：x与y是同班同学。11/16/202217利用归结原理求取问题答案-习题2练习：11/10/20221利用归结原理求取问题答案-习题3

练习：某记者到一个孤岛上采访，遇到了一个难题，即岛上有许多人说假话，因而难以保证新闻报道的正确性。不过有一点她是清楚的，这个岛上的人有一特点，说假话的人从来不说真话，说真话的人也从来不说假话。有一次，记者遇到了孤岛上的三个人，为了弄清楚谁说真话，谁说假话，她向三个人中的每一个都提了同样的问题，即“谁是说谎者？”结果，a回答：“b和c都是说谎者”；b回答：“a和c都是说谎者”；c回答：“a和b至少有一个是说谎者”。试问记者如何才能从这些回答中理出头绪。定义谓词：T(x):x说真话。11/16/202218利用归结原理求取问题答案-习题3练习：某记者到一个孤利用归结原理求取问题答案-习题4破案问题：在一栋房子里发生了一件神秘的谋杀案，现在可以肯定以下几点事实：(1)在这栋房子里仅住有A,B,C三人；(2)是住在这栋房子里的人杀了A；(3)谋杀者非常恨受害者；(4)A所恨的人，C一定不恨；(5)除了B以外，A恨所有的人；(6)B恨所有不比A富有的人；11/16/202219利用归结原理求取问题答案-习题4破案问题：在一栋房子里发生了(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富有。11/16/202220(7)A所恨的人，B也恨；11/10/202220应用归结原理的习题在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：（1）若被归结的子句C1和C2中具有相同的变元时，需要将其中一个子句的变元更名，否则可能无法合一，从而没有办法进行归结。（2）在求归结式时，不能同时消去两个互补文字对，消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。（3）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的化简。11/16/202221应用归结原理的习题在谓词逻辑中，对子句进行归结推理时，要注意（一）应用归结原理进行定理证明应用归结原理进行定理证明的步骤：

设要被证明的定理可用谓词公式表示为如下的形式：

A1∧A2∧…∧An→B(1)首先否定结论B，并将否定后的公式～B与前提公式集组成如下形式的谓词公式：G=A1∧A2∧…∧An∧～B(2)

求谓词公式G的子句集S。(3)

应用归结原理，证明子句集S的不可满足性。11/16/202222（一）应用归结原理进行定理证明应用归结原理进行定理证明的步骤应用归结原理进行定理证明-习题1

例.已知:某些病人喜欢所有的医生，没有一个病人喜欢任意一个骗子。证明:任意一个医生都不是骗子。证明:知识表示：令P(x)：x是病人D(x)：x是医生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是不可满足的。11/16/202223应用归结原理进行定理证明-习题1例.已知:某些病人喜欢所有A1=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)～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)｝11/16/202224A1=x(P(x)y(～D(y)L(x,S不可满足的归结演绎序列为：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)mgu:{a/x}～L(a,b)由(5)、(7)mgu:{b/y}由(6)、(8)11/16/202225S不可满足的归结演绎序列为：11/10/20225应用归结原理进行定理证明-习题2练习：设有下列知识：F1：自然数都是大于等于零的整数；F2：所有整数不是偶数就是奇数；F3：偶数除以2是整数。求证：所有自然数不是奇数就是其一半为整数的数。定义谓词：N(x)：x是自然数；I(x)：x是整数；GZ(x):x大于等于零;E(x)：x是偶数;O(x)：x是奇数。定义函数f(x)：x除以2。11/16/202226应用归结原理进行定理证明-习题2练习：设有下列知识：11/1应用归结原理进行定理证明-习题3练习：(1)马科斯(Marcus)是男人；(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。11/16/202227应用归结原理进行定理证明-习题3练习：11/10/20227练习：“快乐学生”问题假设：任何通过计算机考试并获奖的人都是快乐的；任何肯学习或幸运的人都可以通过所有考试；张不肯学习但他是幸运的；任何幸运的人都能获奖。证明：张是快乐的。定义谓词Pass(x,y):x通过考试y;Win(x,prize):x获奖;Happy(x):x快乐；Study(x):x肯学习;Lucky(x):x幸运。应用归结原理进行定理证明-习题411/16/202228练习：“快乐学生”问题应用归结原理进行定理证明-习题411应用归结原理进行定理证明-习题5练习--“激动人心的生活”问题假设：所有不贫穷并且聪明的人都是快乐的；那些看书的人是聪明的；李明能看书且不贫穷；快乐的人过着激动人心的生活。求证：李明过着激动人心的生活。定义谓词：Poor(x):x贫穷；Smart(x):x聪明；Happy(x):x快乐；Read(x):x看书；Exciting(x):x过着激动人心的生活。11/16/202229应用归结原理进行定理证明-习题5练习--“激动人心的生活”（二）利用归结原理求取问题答案利用归结原理求取问题答案的步骤：（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。（3）把（2）中的析取式化为子句集，并把该子句集与S1合并构成子句集S。11/16/202230（二）利用归结原理求取问题答案利用归结原理求取问题答案的步骤（4）对子句集S应用归结原理进行归结，在归结的过程中，通过合一，改变ANSWER中的变元。（5）如果得到归结式ANSWER，则问题的答案即在ANSWER谓词中。11/16/202231（4）对子句集S应用归结原理进行归结，在归结的过程中，通过合利用归结原理求取问题答案-习题1例.任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问:Peter的父亲是谁？解第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。（1）

定义谓词：设Father(x,y)表示x是y的父亲。Brother(x,y)表示x和y是兄弟。11/16/202232利用归结原理求取问题答案-习题1例.任何兄弟都有同一个父亲（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),Brother(John,Peter),Father(David,John)}11/16/202233（2）将已知事实用谓词公式表示出来。11/10/20221第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。设Peter的父亲是u，则有：Father(u,Peter)。将其否定与ANSWER作析取，得：G：～Father(u,Peter)∨ANSWER(u)11/16/202234第二步：把问题用谓词公式表示出来，11/10/202214第三步：将上述公式G化为子句集S2,并将S1和S2合并到S。S2={～Father(u,Peter)∨ANSWER(u)}S=S1∪S2将S中各子句列出如下：（1）～Brother(x,y)∨～Father(z,x)∨Father(z,y)。（2）Brother(John,Peter)。（3）Father(David,John)。（4）～Father(u,Peter)∨ANSWER(u)。11/16/202235第三步：将上述公式G化为子句集S2,并将S1和S2合并到S。第四步：应用归结原理进行归结（5）～Brother(John,y)∨Father(David,y)（1）与（3）归结σ={David/z,John/x}（6）～Brother(John,Peter)∨ANSWER(David)