第2章-谓词演算与消解(归结)原理课件

第二章第二章 谓词演算与消解谓词演算与消解(归结归结)原理原理q命题演算命题演算qq谓词演算谓词演算qq推理规则产生谓词演算表达式推理规则产生谓词演算表达式qq应用应用qq归结原理归结原理2经典数理经典数理逻辑逻辑uAI研究内容之一是推理，即研究怎样使计算机获得自动推理的能力u数理逻辑用数学方法研究各种推理中的逻辑问题，以推理本身作为研究对象uAI要使用逻辑推理，就必然涉及数理逻辑/数理逻辑的经典部分经典的命题逻辑和一阶谓词逻辑，同时作为人工智能的知识表示方法和推理方法而存在；因此数理逻辑是人工智能的一个基础32.1 2.1 命题演算命题演算 u2.1.1 符号和命题命题演算的符号命题演算的符号：是命题符号：是命题符号,命题符号代表命题，是命题符号代表命题，是关于现实世界的能分辨真假值的陈述句。关于现实世界的能分辨真假值的陈述句。命题符号：命题符号：P，Q，R，S，T命题演算的符号：命题演算的符号：真值符号：真值符号：true,falsetrue,false 联结词：联结词：，=，通过联结词可把多个命题组成合成的命题，也称为通过联结词可把多个命题组成合成的命题，也称为合式公式。合式公式。4u2.1.2 2.1.2 命题演算的语义命题演算的语义2.1 2.1 命题演算命题演算 如两个命题表达式如两个命题表达式在任何真值指派下都有相同的值，在任何真值指派下都有相同的值，则称为是等价的则称为是等价的（P29）表）表2.2所示的真值表证明：所示的真值表证明：P=Q与与P Q等价。等价。对于命题表达式对于命题表达式P，Q，R(P)=P;(P Q)(P=Q)5否定律：否定律：(PQ)(PQ)(PQ)(PQ)分配律：分配律：P(QR)(PQ)(PR)分配律：分配律：P(QR)(PQ)(PR)交换律：交换律：(PQ)(QP)交换律：交换律：(PQ)(QP)结合律：结合律：(PQ)R)(P(QR)结合律：结合律：(PQ)R)(P(QR)置换律：置换律：(P=Q)(Q=P)2.1 2.1 命题演算命题演算 6 2.2 2.2 谓词演算谓词演算命题演算中，命题演算中，P，Q代表一定的命题，如：代表一定的命题，如：P：星期四下雨：星期四下雨而谓词：而谓词：Weather（X，Y）代表日期与天气的关系）代表日期与天气的关系Weather（Tuesday，Rain）q 可以操纵命题演算表达式可以操纵命题演算表达式q允许包含变元允许包含变元Weather（X，Rain）72.2.1谓词的语法和命题谓词的语法和命题 2.2 2.2 谓词演算谓词演算谓词演算的字母表组成：谓词演算的字母表组成：（1）英文字母组合，包括大写与小写）英文字母组合，包括大写与小写（2）数字集合）数字集合0,1,9（3）下划线）下划线如：如：George,fires,bill,xxxx8 谓词演算符号包括：谓词演算符号包括：真值符号真值符号true和和false。常元符号常元符号,第一个字符为小写字母的符号表达式。第一个字符为小写字母的符号表达式。变元符号变元符号,第一个字符为大写字母的符号表达式。第一个字符为大写字母的符号表达式。函词符号函词符号,第一个字符为小写字母的符号表达式第一个字符为小写字母的符号表达式,函词函词有一个元数有一个元数,指出从定义域中映射到值域中的每个元素。指出从定义域中映射到值域中的每个元素。2.2 2.2 谓词演算谓词演算9例：例：llikes(george,kate).likes(X,george).l likes(george,susie).likes(X,X).l likes(george,sarah,tuesday).l friends(bill,richard).l friends(bill,george).l friends(father(david),father(andrew)l helps(bill,george).l helps(richard,bill).2.2 2.2 谓词演算谓词演算原子命题：是一个原子命题：是一个n元谓词，后跟元谓词，后跟n个项，用括号括起来个项，用括号括起来并用逗号分开。并用逗号分开。102.2.1谓词的语法和命题谓词的语法和命题u与谓词相关的一个正整数称为元数或与谓词相关的一个正整数称为元数或“参数数目参数数目”，具，具有相同的名但元数不同的谓词是不同的。有相同的名但元数不同的谓词是不同的。u真值真值true和和false也是原子命题。也是原子命题。u任何原子命题都能够用逻辑操作符将其变成谓词演算任何原子命题都能够用逻辑操作符将其变成谓词演算的命题。用的联结词也和命题演算一样的命题。用的联结词也和命题演算一样:,=和。和。u当一个变元在一个命题中作为参数出现时当一个变元在一个命题中作为参数出现时,它代表的它代表的是域中不特定的对象。是域中不特定的对象。u谓词演算包括两个符号谓词演算包括两个符号,量词量词（全称量词）（全称量词）和和彐（存彐（存在量词）在量词）,用于限定包含变元的命题的含义。用于限定包含变元的命题的含义。112.2.1谓词的语法和命题谓词的语法和命题一个量词后面紧跟着一个变元和一个命题。例如：一个量词后面紧跟着一个变元和一个命题。例如：Xlikes(X,ice_cream).彐彐Yfriends(Y,peter).u全称量词全称量词,表明命题对于变元的变域中的所有的表明命题对于变元的变域中的所有的值都为真。值都为真。u存在量词彐存在量词彐,表明该命题对于变元的变域中的一些表明该命题对于变元的变域中的一些值为真。值为真。12例：命题例：命题2.2.1谓词的语法和命题谓词的语法和命题plus(two,three)equal(plus(two,three)彐彐xfoo(x,two,plus(two,three)equal(plus(two,three),five)132.2.2谓词演算的语义谓词演算的语义(P34)表达式的真值依赖于常元、变元、谓词、函词到论域中表达式的真值依赖于常元、变元、谓词、函词到论域中的映射；在论域中的关系的真假决定了相应表达式的的映射；在论域中的关系的真假决定了相应表达式的真假。真假。例如：例如：ufriends(george,susie)ufriends(george,kate)142.2.2谓词演算的语义谓词演算的语义(P34)一个论域一个论域D上的解释：上的解释：假设论域假设论域D是一个非空集合，在是一个非空集合，在D上的一个解释把论域上的一个解释把论域D的的实体指派给一个谓词演算表达式的每一个常元、变元、谓词实体指派给一个谓词演算表达式的每一个常元、变元、谓词及函词符号，于是有：及函词符号，于是有：1）每一个常元指派了）每一个常元指派了D的一个元素。的一个元素。2）对每一个变元，指派）对每一个变元，指派D的一个非空集合，这是该变元的的一个非空集合，这是该变元的变域。变域。3）每个）每个n元谓词元谓词P定义在论域定义在论域D中的中的n个参数上，并定义了从个参数上，并定义了从Dn到到T，F的一个映射。的一个映射。4)每个每个m元函词元函词f定义在论域定义在论域D的的m个参数上，并定义了从个参数上，并定义了从Dm到到T，F的一个映射。的一个映射。在一种解释下，一个表达式的意义是在该解释下的一个真值在一种解释下，一个表达式的意义是在该解释下的一个真值指派。指派。152.2.2谓词演算的语义谓词演算的语义谓词演算表达式的真值谓词演算表达式的真值设有表达式设有表达式E和在非空论域和在非空论域D上对上对E的一个解释的一个解释I，E的真值的真值按以下规律决定：按以下规律决定：1）一个常元的值是根据）一个常元的值是根据I指派给它的指派给它的D的一个元素。的一个元素。2）一个变元的值是根据）一个变元的值是根据I指派给它的指派给它的D的一个元素集合。的一个元素集合。3）一个函词的值是根据由）一个函词的值是根据由I指派给它的参数值计算得到的指派给它的参数值计算得到的D的元素。的元素。4）真值符号）真值符号true的值是的值是T，false的值是的值是F。5）原子命题的值或者为）原子命题的值或者为T，或者为，或者为F，取决于解释，取决于解释I。6）如果一个命题的值为）如果一个命题的值为F，则其否定式为，则其否定式为T，否则为，否则为F。7）如果）如果11)如果对于在解释如果对于在解释I下的下的X的每一个指派，的每一个指派，S的值为的值为T，则，则 XS为为T，否则为，否则为F。12）如果在解释）如果在解释I下存在下存在X的一个指派使得的一个指派使得S的值为的值为T，则，则彐彐XS为为T，否则为，否则为F。162.2.2谓词演算的语义谓词演算的语义(P34)变元：变元：likes(george,X)这个变元名可以由任何其他变元名代替，不会改变表达这个变元名可以由任何其他变元名代替，不会改变表达式的意思。式的意思。l变元的量词约束是谓词演算语义的重要部分变元的量词约束是谓词演算语义的重要部分 在谓词演算中在谓词演算中,变元有两种约束使用的方法变元有两种约束使用的方法:q在特定解释下在特定解释下,命题对变元的变域中的所有常元指派命题对变元的变域中的所有常元指派为真为真,则称该变元是则称该变元是全称性变元全称性变元。代表全称量词的符号。代表全称量词的符号是是 ,括号常常用于表示量词的约束范围括号常常用于表示量词的约束范围 q存在性变元存在性变元。至少存在变元的变域中的一个值使包含。至少存在变元的变域中的一个值使包含变元的表达式为真时，表达式才为真。变元的表达式为真时，表达式才为真。代表存在量词的代表存在量词的符号是符号是彐彐172.2.2谓词演算的语义谓词演算的语义否定与全称量词、存在量词之间的关系否定与全称量词、存在量词之间的关系(P36)。对于谓词对于谓词P,Q,变元变元X,Y有：有：l彐彐XP(X)XP(X)l XP(X)彐彐XP(X)l彐彐XP(X)彐彐YP(Y)l XQ(X)YQ(Y)l X(P(X)Q(X)XP(X)YQ(Y)l彐彐X(P(X)Q(X)彐彐XP(X)彐彐YQ(Y)182.3 2.3 推理规则产生谓词演算表达式推理规则产生谓词演算表达式 2.3.1推理规则推理规则(p38)u实际上是一个从其他谓词演算命题产生新的谓词演算命实际上是一个从其他谓词演算命题产生新的谓词演算命题的机械方法。题的机械方法。u产生基于给定逻辑断言的句法形式的新命题。产生基于给定逻辑断言的句法形式的新命题。u当每个由逻辑表达式集当每个由逻辑表达式集S上的推理规则产生的命题上的推理规则产生的命题X都都是是S的逻辑结果的逻辑结果,则称该逻辑规则是合理的。则称该逻辑规则是合理的。S:xhuman(x)=mortal(x).human(Socrates).x:mortal(Socrates).19假言推理和归结原理都是合理的推理规则的例子。假言推理和归结原理都是合理的推理规则的例子。假言推理：如果命题假言推理：如果命题P，P=Q为真，应用假言推理得为真，应用假言推理得出出Q为真。为真。S:xhuman(x)=mortal(x).human(Socrates).x:mortal(Socrates).human(Socrates)=mortal(Socrates)？human(x)Socrates合一合一算法算法202.3.2合一合一（p40)q是判断两个谓词表达式匹配所需的一种代入算法是判断两个谓词表达式匹配所需的一种代入算法q合一表明了两个或多个表达式在什么条件下可以称为合一表明了两个或多个表达式在什么条件下可以称为等价的。等价的。q替换：替换：一个替换一个替换(Substitution)就是形如就是形如t1/x1,t2/x2,.tn/xn的有限集合，的有限集合，x1,x2.,xn是互不相同的个体变元，是互不相同的个体变元，ti不同不同于于xi,xi也不循环出现在也不循环出现在tj中中如：如：a/x,g(y)/y,f(g(b)/zg(y)/x,f(x)/yx21合一：合一：q设设S=F1，F2，。，。，Fn是一个原子谓词公式集合，是一个原子谓词公式集合，若存在一个替换若存在一个替换，可使，可使F1=F2=Fn,则称则称为为S的一个合的一个合一（一（Unifier），称），称S为可合一的为可合一的22u伪代码写的函数伪代码写的函数Unify用于计算两个谓词表达式的最一般合一用于计算两个谓词表达式的最一般合一以两个谓词演算表达式为参数以两个谓词演算表达式为参数,若这两个表达式可以合若这两个表达式可以合一一,则返回则返回最一般合一代入最一般合一代入,否则返回否则返回FAIL。232.3.2合一合一(p42)functionunify(E1,E2);begincaseend%endcaseendq首先首先,它递归地试图对表达式的初始成分合一。如果成它递归地试图对表达式的初始成分合一。如果成功功,这次合一返回的任何代入式被用到两个表达式的剩这次合一返回的任何代入式被用到两个表达式的剩下部分下部分,然后以这两个表达式为参数。然后以这两个表达式为参数。q终止条件是两个参数之一为一个符号终止条件是两个参数之一为一个符号(谓词名谓词名,函词名函词名,变元变元,常元常元),或两个表达式的每一元素都已匹配了。或两个表达式的每一元素都已匹配了。242.3.2合一合一caseE1,E2或者是常元或者是空表或者是常元或者是空表:%递归终止。递归终止。IfE1E2thenreturnelsereturnFAIL;E1是一个变元是一个变元:ifE1在在E2中出现中出现thenreturnFAILelsereturnE2/E1;E2是一个变元是一个变元:ifE2在在E1中出现中出现thenreturnFAILelsereturnE1/E2;其他情况其他情况:%E1和和E2都是表都是表252.3.2合一合一beginHE1:=E1的第一个元素的第一个元素;HE2:=E2的第一个元素的第一个元素;SUBS1:=unify(HE1,HE2);ifSUBS1FAILthenreturnFAILTE1:=apply(SUBS1,E1的后半部的后半部)TE2:=apply(SUBS1,E2的后半部的后半部)SUBS2:=unify(TE1,TE2),ifSUBS2FAILthenreturnFAILelsereturnSUBS1与与SUBS2的合成的合成end262.3.3合一的一个例子合一的一个例子(p43)通过以下调用来跟踪算法的运行过程：通过以下调用来跟踪算法的运行过程：unify(parentsX(fatherX)(motherbill),(parentsbill(fatherbill)Y)第一次调用第一次调用:unify(parents,parents)这次调用成功这次调用成功,返回代入集返回代入集。第二次调用第二次调用:unify(X,bill)这次调用成功这次调用成功,返回代入返回代入bill/X。272.3.3合一的一个例子合一的一个例子在此基础上又调用在此基础上又调用:unify(fatherbill)(motherbill),(fatherbill)Y)导致调用导致调用:(1)unify(fatherbill),(fatherbill)unify(father,father)unify(bill,bill)unify(),()所有的调用都成功所有的调用都成功,返回空代入集返回空代入集。(2)unify(motherbill),Y)bill/X,(motherbill)/Y282.4 2.4 应用应用(p46):(p46):一个基于逻辑的金融投资辅助决策程序一位有三个人需赡养一位有三个人需赡养,有有$22000存款存款,每年有每年有$25000的稳定收入的的稳定收入的投资者的情况投资者的情况,可产生一个由下列命题组成的逻辑系统可产生一个由下列命题组成的逻辑系统:1.savings(inadequate)=investment(savings).2.savings(adequate)income(adequate)=investment(stocks).3.savings(adequate)income(inadequate)=investment(combination).4.Xamountsaved(X)彐彐Y(dependents(Y)greater(X,minsavings(Y)=savings(adequate).5.Xamountsaved(X)彐彐Y(dependents(Y)greater(X,minsavings(Y)=savings(inadequate).292.4应用应用(p47)6.Xearnings(X,steady)彐彐Y(dependents(Y)greater(X,minincome(Y)=income(adequate).7.Xearnings(X,steady)彐彐Y(dependents(Y)greater(X,minincome(Y)=income(inadequate).8.Xearnings(X,unsteady)=income(inadequate).9.amountsaved(22000).10.earnings(25000,steady).11.dependents(3).其中:minsavings(X)=5000*X;minincome(X)=15000+(4000*X)302.4应用应用(p47)u第一步把第第一步把第10、11与第与第7的前提合一的前提合一,得得:u第二步把第第二步把第9、11与第与第4的前提合一的前提合一,得得:13.savings(adequate)3.savings(adequate)income(inadequate)=investment(combination).结论结论:investment(combination),这就是给投资者的建议。这就是给投资者的建议。(存款的人应该把他们多余的钱分别用于存款和买股票，在增加存款做保存款的人应该把他们多余的钱分别用于存款和买股票，在增加存款做保险的同时试图通过做股票以增加收入。险的同时试图通过做股票以增加收入。)12.Income(inadequate).10.earnings(25000,steady).11.dependents(3).7.Xearnings(X,steady)彐彐Y(dependents(Y)greater(X,minincome(Y)=income(inadequate).9.amountsaved(22000).11.dependents(3).4.Xamountsaved(X)彐彐Y(dependents(Y)greater(X,minsavings(Y)=savings(adequate).31AssignmentuP62.7对以下每对表达式合一，如果成功，给出最一般合一式对以下每对表达式合一，如果成功，给出最一般合一式1P(X,Y),P(a,Z)2P(X,X),P(a,b)3ancestor(X,Y),ancestor(bill,father(bill)4ancestor(X,father),ancestor(david,george)5g(X),g(a)6P(X,a,Y),P(Z,Z,b)uP62.9*用高级语言实现合一算法（思考题）用高级语言实现合一算法（思考题）322.5 2.5 消解定理证明消解定理证明 (p 48)(p 48)u消解是一种应用于谓词演算中的定理证明技术，是人工智能问题求解的消解是一种应用于谓词演算中的定理证明技术，是人工智能问题求解的一个组成部分。消解描述了如何用最少的合一次数在一个子句数据库中一个组成部分。消解描述了如何用最少的合一次数在一个子句数据库中发现矛盾的方法。发现矛盾的方法。u具体方法如下：具体方法如下：对所要证明的命题取反，把它加到已知为真的公理集中，然后用消解推对所要证明的命题取反，把它加到已知为真的公理集中，然后用消解推理规则证明这将导致一个矛盾，一旦证明了否定目标与已知公理集不一理规则证明这将导致一个矛盾，一旦证明了否定目标与已知公理集不一致，就能推导出原来的目标与已知公理集是一致的，从而定理得证。致，就能推导出原来的目标与已知公理集是一致的，从而定理得证。332.5消解定理证明消解定理证明(p48)2.5.1引言引言消解否证包含以下步骤：消解否证包含以下步骤：u把前提或公理转换成子句形式。把前提或公理转换成子句形式。u把求证目标的否定的子句形式加到公理集合中。把求证目标的否定的子句形式加到公理集合中。u对所有这些子句进行消解，产生它们的逻辑结果子句。对所有这些子句进行消解，产生它们的逻辑结果子句。u用产生空子句的方法来得出矛盾。用产生空子句的方法来得出矛盾。u否定目标的否证在用于产生空子句的代换下为真。否定目标的否证在用于产生空子句的代换下为真。342.5.1引言引言u消解否证需要所有公理和否定目标为子句形式消解否证需要所有公理和否定目标为子句形式子句形式把一个逻辑数据库子句形式把一个逻辑数据库表示为一个文字表示为一个文字析取式析取式的集的集合。一个文字是一个原子表合。一个文字是一个原子表达式或原子表达式的否定。达式或原子表达式的否定。u消解作用于两个子句消解作用于两个子句,其中一个包含某文字其中一个包含某文字,另一个另一个包含该文字的否定包含该文字的否定,如果这些文字包含变元如果这些文字包含变元,必须用合必须用合一使它们相等。一使它们相等。u一个新的子句就此产生了一个新的子句就此产生了,它包含两个子句中所有它包含两个子句中所有谓词的谓词的析取析取,除了该文字和它的否定以外。除了该文字和它的否定以外。352.5.1引言引言用消解所做的等价的推理把以下谓词演算公式变换成子句形式用消解所做的等价的推理把以下谓词演算公式变换成子句形式(P49)：谓词形式谓词形式子句形式子句形式1.Alldogsareanimals(X)(dog(X)animal(X)dog(X)animal(X)2.Fidoisadogdog(fido)dog(fido)3.allanimalswilldie(Y)(animal(Y)die(Y)animal(Y)die(Y)证明：证明：fidowilldie对目标对目标“取反取反”：die(fido)36dog(X)animal(X).animal(Y)die(Y).Y/Xdog(fido).dog(Y)die(Y).fido/Ydie(fido).die(fido).图图2.6“死狗死狗”问题消解证明问题消解证明(P50)2.5.1引言引言372.5.2为消解否证产生子句形式为消解否证产生子句形式(P4952)u本节提出一个由一系列变换组成的算法，这些变换可本节提出一个由一系列变换组成的算法，这些变换可以把任何谓词演算表达式归约为子句形式，在此过程以把任何谓词演算表达式归约为子句形式，在此过程中中保持其真值、一般性和不可满足性不变保持其真值、一般性和不可满足性不变。即如果在原谓词演算表达式中即如果在原谓词演算表达式中存在一个矛盾，则其子句形式存在一个矛盾，则其子句形式中也存在一个矛盾，变换不牺中也存在一个矛盾，变换不牺牲消解否证的完备性。牲消解否证的完备性。382.5.2为消解否证产生子句形式为消解否证产生子句形式（P50)设设X,Y,Z,W表示变元；表示变元；l,m,n表示常元；表示常元；a,b,c,d,e表示表示谓词名。要归纳为子句的表达式：谓词名。要归纳为子句的表达式：1.(X)(a(X)b(X)c(X,l)(彐彐Y)(彐彐Z)c(Y，Z)d(X,Y)(X)(e(X)2.(X)(a(X)b(X)c(X，l)(彐彐Y)(彐彐Z)c(Y,Z)d(X,Y)(）(e(X)）3.(X)(a(X)b(X)c(X,l)(彐彐Y)(Z)c(Y,Z)d(X,Y)(X)(e(X)4.(X)(a(X)b(X)c(X,l)(彐彐Y)(Z)c(Y,Z)d(X,Y)(W)(e(W)所有量词移到最左边而不改变其次序所有量词移到最左边而不改变其次序5.(X)(彐彐Y)(Z)(W)(a(X)b(X)c(X,l)c(Y,Z)d(X,Y)e(W)前束范式前束范式斯柯伦标准化去掉所有的存在量词斯柯伦标准化去掉所有的存在量词392.5.2为消解否证产生子句形式为消解否证产生子句形式斯柯伦标准化：去掉所有的存在量词斯柯伦标准化：去掉所有的存在量词彐彐Z（foo(Y，Z)foo(Y，k)彐彐X（dog(X)dog(fido)斯柯伦常元斯柯伦常元如果谓词中含有多个参数，而如果谓词中含有多个参数，而彐约束变元在彐约束变元在 约束变约束变元的约束范围内，元的约束范围内，则彐约束变元必须是那些其他变元则彐约束变元必须是那些其他变元的函数。的函数。如：如：（X）(彐彐Y)(mother(X,Y)（X）(mother(X,m(X)402.5.2为消解否证产生子句形式为消解否证产生子句形式6.(X)(Z)(W)(a(X)b(X)c(X,l)c(f(X),Z)d(X,f(X)e(W)5.(X)(彐彐Y)(Z)(W)(a(X)b(X)c(X,l)c(Y,Z)d(X,Y)e(W)斯柯伦标准化后斯柯伦标准化后去掉全称量词去掉全称量词7.(a(X)b(X)c(X,l)(c(f(X),Z)d(X,f(X)e(W)8.a(X)b(X)c(X,l)e(W)a(X)b(X)c(f(X),Z)d(X,f(X)e(W)转换成析取式的合取转换成析取式的合取每个合取式为一个分离的子句每个合取式为一个分离的子句9a:a(X)b(X)c(X,l)e(W)9b:a(X)b(X)c(f(X),Z)d(X,f(X)e(W)重新命名所有变元，重新命名所有变元，避免重名避免重名10a:a(X)b(X)c(X,l)e(W)10b:a(U)b(U)c(f(U),Z)d(U,f(U)e(V)41将公理转换成子句形式：将公理转换成子句形式：u消去蕴涵消去蕴涵u把否定式降至原子公式把否定式降至原子公式u消去存在量词消去存在量词u如果需要，重新命名变元如果需要，重新命名变元u把全称量词移到左边把全称量词移到左边u将析取降至文字式将析取降至文字式u消去合取消去合取u如果需要，重新命名变元如果需要，重新命名变元42 xBrick(x)(彐彐yOn(x,y)Pyramid(y)彐彐yOn(x,y)On(y,x)xBrick(y)Equal(x,y)Homework432.5.3消解证明过程消解证明过程u例例1:“幸运学生幸运学生”的故事（的故事（P54):“任何通过了历史考试并中了彩票的人是快乐的。任何通过了历史考试并中了彩票的人是快乐的。任何肯学习或幸运的人可以通过所有考试任何肯学习或幸运的人可以通过所有考试,John不不学习但很幸运学习但很幸运,任何人只要是幸运的就能中彩。任何人只要是幸运的就能中彩。John快乐吗快乐吗?1.第一步把这些句子变成谓词形式第一步把这些句子变成谓词形式:定义一些谓词：定义一些谓词：pass(x,y),win(x,lottery),happy(x),study(x),lucky(x)442.5.3消解证明过程消解证明过程“任何通过了历史考试并中了彩票的人是快乐的。任何肯学习或任何通过了历史考试并中了彩票的人是快乐的。任何肯学习或幸运的人可以通过所有考试幸运的人可以通过所有考试,John不学习但很幸运不学习但很幸运,任何人只要任何人只要是幸运的就能中彩。是幸运的就能中彩。John快乐吗快乐吗?X(pass(X,history)win(X,lottery)happy(X)X Y(study(X)lucky(X)pass(X,Y)study(john)lucky(john)X(lucky(X)win(X,lottery)452.5.3消解证明过程消解证明过程1.pass(X,history)win(X,lottery)happy(X)2.study(Y)pass(Y,Z)3.lucky(V)pass(V,W)4.study(john)5.lucky(john)6.lucky(U)win(U,lottery)X(pass(X,history)win(X,lottery)happy(X)X Y(study(X)lucky(X)pass(X,Y)study(john)lucky(john)X(lucky(X)win(X,lottery)将这四个谓词演算命题转换成子句形式将这四个谓词演算命题转换成子句形式:加入子句形式的否定目标加入子句形式的否定目标:7.happy(john)462.5.3消解证明过程消解证明过程 pass(X,history)pass(X,history)win(U,lottery)win(U,lottery)lucky(U)lucky(U)win(X,lottery)happy(X)win(X,lottery)happy(X)U/XU/X pass(U,history)pass(U,history)happy(john).happy(john).happy(U)happy(U)lucky(U).lucky(U).john/Ujohn/U lucky(john).lucky(john).pass(john,history)pass(john,history)lucky(john).lucky(john).pass(john,history).pass(john,history).lucky()pass(V,W).lucky()pass(V,W).john/V,history/Wjohn/V,history/W lucky(john).lucky(john).lucky(john).lucky(john).图图2.8 2.8“快乐学生快乐学生”问题的消解否证问题的消解否证*将将(P55)C改为改为U子句子句1子句子句6子句子句7子句子句5子句子句3子句子句5John是快是快乐的乐的472.5.3消解证明过程消解证明过程例例2 2：(P54)(P54)假设假设:“所有不贫穷并且聪明的人是快乐的。那些看书的人所有不贫穷并且聪明的人是快乐的。那些看书的人是不笨的。是不笨的。John能看书并且富有。快乐的人过着激动能看书并且富有。快乐的人过着激动人心的生活。你能发现谁过着激动人心的生活吗人心的生活。你能发现谁过着激动人心的生活吗?把上述故事翻译成谓词演算表达式把上述故事翻译成谓词演算表达式:X(X(poor(X)smart(X)happy(X)poor(X)smart(X)happy(X)Y(read(Y)smart(Y)Y(read(Y)smart(Y)read(john)read(john)poor(john)poor(john)Z(happy(Z)exciting(Z)Z(happy(Z)exciting(Z)否定目标是：否定目标是：彐彐 W(exciting(W)W(exciting(W)482.5.3消解证明过程消解证明过程1.poor(X)smart(X)happy(X)2.read(Y)smart(Y)3.read(john)4.poor(john)5.happy(Z)exciting(Z)6.exciting(W)X(X(poor(X)smart(X)happy(X)poor(X)smart(X)happy(X)Y(read(Y)smart(Y)Y(read(Y)smart(Y)read(john)read(john)poor(john)poor(john)Z(happy(Z)exciting(Z)Z(happy(Z)exciting(Z)彐彐 W(exciting(W)W(exciting(W)变换成如下的子句变换成如下的子句:492.5.3消解证明过程消解证明过程 exciting(W)exciting(W)happy(Z)exciting(Z)happy(Z)exciting(Z)Z/WZ/W happy(Z)poor(X)happy(Z)poor(X)smart(X)happy(X)smart(X)happy(X)X/ZX/Z poor(X)poor(X)smart(X)smart(X)read(Y)smart(Y)read(Y)smart(Y)Y/XY/X poor(Y)poor(Y)read(Y)read(Y)poor(john)poor(john)子句子句6子句子句5子句子句1子句子句2这个例子的消解否证如图这个例子的消解否证如图2.9(P56)所示：所示：john/Yjohn/Y read(john)read(john)read(john)read(john)子句子句4子句子句3从消解否证从消解否证中提取答案中提取答案502.6 2.6 用消解法求更为复杂问题例子用消解法求更为复杂问题例子u例例1：某记者到一孤岛采访，遇到了一个难题，即岛上有：某记者到一孤岛采访，遇到了一个难题，即岛上有许多人说假话，因而难以保证新闻报道的正确性，不过许多人说假话，因而难以保证新闻报道的正确性，不过有一点他是清楚的，这个岛上的人有一特点：说假话的有一点他是清楚的，这个岛上的人有一特点：说假话的人从来不说真话，说真话的人也从来不说假话。一次记人从来不说真话，说真话的人也从来不说假话。一次记者遇到了孤岛上的三个人，为了弄清楚谁说真话，谁说者遇到了孤岛上的三个人，为了弄清楚谁说真话，谁说假话，他向这三个人中的每一个都问了一个同样的问题，假话，他向这三个人中的每一个都问了一个同样的问题，即即“谁是说谎者？谁是说谎者？”结果结果A答答“B和和C都是说谎者都是说谎者”，B答答“A和和C都是说谎者都是说谎者”，C答答“A和和B中至少有一个中至少有一个是说谎者是说谎者”，试问记者如何从回答中理出头绪。试问记者如何从回答中理出头绪。512.6用消解法求更为复杂问题例子用消解法求更为复杂问题例子以以A，B，C三个命题来表示三个命题来表示A，B，C三个是老实人（不说谎）三个是老实人（不说谎）A答答“B和和C都是说谎者都是说谎者”B答答“A和和C都是说谎者都是说谎者”C答答“A和和B中至少有一个中至少有一个是说谎者是说谎者”u如果如果A说真话，则说真话，则B和和C一定说谎，因此有：一定说谎，因此有：AB C 如果如果A A说假话，则说假话，则B B和和C C中至少有一人说真话中至少有一人说真话,因此有因此有:AB C以同样的推理方式可得到：以同样的推理方式可得到：u如果如果B说真话说真话,如果如果B说假话说假话BA C BA Cu如果如果C说真话说真话,如果如果C说假话说假话CAB CA B522.6用消解法求更为复杂问题例子用消解法求更为复杂问题例子对以上蕴含式加以推理对以上蕴含式加以推理,并化成子句形式并化成子句形式,可得：可得：AB（1）AC（2）ABC（3）BC（4）ABC（5）AC（6）BC（7）532.6 2.6 用消解法求更为复杂问题例子用消解法求更为复杂问题例子u（1）和（）和（7）消解，得：）消解，得：A C（8）u（2）和（）和（8）消解，得：）消解，得：A （9）u（6）和（）和（9）消解，得：）消解，得：C （10）u（4）和（）和（10）消解，得：）消解，得：B （11）说明？说明？谁是说谎者？谁是说谎者？A和和B都是说谎者，而都是说谎者，而C是老实人是老实人542.6用消解法求更为复杂问题例子用消解法求更为复杂问题例子u例例2:四对夫妇中，王结婚时，周送了礼；周和钱是同一四对夫妇中，王结婚时，周送了礼；周和钱是同一排球队的队员；李的爱人是陈的爱人的表哥；陈夫妇与邻排球队的队员；李的爱人是陈的爱人的表哥；陈夫妇与邻居吵架，徐、周、吴的爱人都去助战；李、徐、周结婚前居吵架，徐、周、吴的爱人都去助战；李、徐、周结婚前住一间宿舍，试用消解法求王、周、钱、陈、李、徐、吴、住一间宿舍，试用消解法求王、周、钱、陈、李、徐、吴、孙八人谁是男？谁是女？谁和谁是夫妇？孙八人谁是男？谁是女？谁和谁是夫妇？(P.63)（1）女（李）女（李）（2）女（李）女（李）女（徐）即：女（徐）即：NOT女（李）女（李）女（徐）女（徐）（3）女（李）女（李）女（周）即：女（周）即：NOT女（李）女（李）女（周）女（周）（4）女（周）女（周）女（钱）即：女（钱）即：NOT女（周）女（周）女（钱）女（钱）（5）女（李）女（李）女（徐）女（徐）女（周）女（周）女（钱）女（钱）男男（王）（王）男（陈）男（陈）男（吴）男（吴）男（孙）男（孙）u则可解得男的是：王、陈、吴、孙则可解得男的是：王、陈、吴、孙u则可解得女的是：李、徐、周、钱则可解得女的是：李、徐、周、钱55（6）couple（王，周）（王，周）（7）couple（陈，李）（陈，李）（8）couple（陈，徐）（陈，徐）（9）couple（陈，周）（陈，周）（10）couple（吴，周）（吴，周）（11）couple（吴，徐）（吴，徐）（12）couple（X，Y）男（男（X）女女(Y）（1313）couple（陈，李）（陈，李）夫妻（陈，徐）夫妻（陈，徐）夫妻（陈，周）夫妻（陈，周）夫妻（陈，钱）夫妻（陈，钱）例例2:四对夫妇中，王结婚时，周送了礼；周和钱是同一排球队的队员；李的爱人是四对夫妇中，王结婚时，周送了礼；周和钱是同一排球队的队员；李的爱人是陈的爱人的表哥；陈夫妇与邻居吵架，徐、周、吴的爱人都去助战；李、徐、周结陈的爱人的表哥；陈夫妇与邻居吵架，徐、周、吴的爱人都去助战；李、徐、周结婚前住一间宿舍，试用消解法求王、周、钱、陈、李、徐、吴、孙八人谁是男？谁婚前住一间宿舍，试用消解法求王、周、钱、陈、李、徐、吴、孙八人谁是男？谁是女？谁和谁是夫妇？是女？谁和谁是夫妇？(P.63)u男：王、陈、吴、孙男：王、陈、吴、孙u女：李、徐、周、钱女：李、徐、周、钱（14）couple（陈，钱）（陈，钱）(13)(7)(8)(9)消解消解;（15）couple(吴吴,周周)couple(吴吴,徐徐)couple(吴吴,李李)（16）couple(吴吴,李李)（15）（）（10）（）（11）进行消解）进行消解;（17）couple（王，周）（王，周）couple（王，徐）（王，徐）（18）couple（王，徐）（王，徐）（17）与（）与（6）消解）消解（19）couple（孙，周）（孙，周）562.6用消解法求更为复杂问题例子用消解法求更为复杂问题例子u例例3:某村农民王某被害，有四个嫌疑犯某村农民王某被害，有四个嫌疑犯A，B，C，D，公安局派出五个侦察员，他们带回的信息各不一样，公安局派出五个侦察员，他们带回的信息各不一样，甲说甲说A，B中至少有一人作案，乙说中至少有一人作案，乙说B，C中至少有一中至少有一人作案，丙说人作案，丙说C，D中至少有一人作案，丁说中至少有一人作案，丁说A，C中中至少有一人与此案无关，戊说至少有一人与此案无关，戊说B，D中至少有一人与此中至少有一人与此案无关，如果这五个侦察员的话都是可靠的，试用消案无关，如果这五个侦察员的话都是可靠的，试用消解法求出谁是罪犯。解法求出谁是罪犯。572.6用消解法求更为复杂问题例子用消解法求更为复杂问题例子（1）AB（2）BC（3）CD（4）AC（5）BD（6）BC（1）、（）、（4）消解；）消解；（7）B是罪犯。是罪犯。（2）、（）、（6）消解；）消解；（8）CD（2）、（）、（5）消解；）消解；（9）C是罪犯。是罪犯。（3）、（）、（8）消解。）消解。58Assignmentu已知已知:任何兄弟都有同一个父亲，任何兄弟都有同一个父亲，John和和Peter是兄弟，是兄弟，且且John的父亲是的父亲是David.请问请问:Peter的父亲是谁？用归结原理证明的父亲是谁？用归结原理证明定义谓词定义谓词Father(x,y):x是是y的父亲；的父亲；Brother(x,y):x和和y是兄弟；是兄弟；