人工智能chapter3resolution

DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring第三章谓词演算与消解(归结)原理命题演算谓词演算推理规则产生谓词演算表达式应用归结原理2DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.1命题演算3.1.1符号和命题命题演算的符号：是命题符号,命题符号代表命题，是关于现实世界的能分辨真假值的陈述句。命题符号：P，Q，R，S，T命题演算的符号：真值符号：True,false联结词：∨，∧，~，=，＝通过联结词可把多个命题组成合成的命题，也称为合式公式。3DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.1.2命题演算的语义3.1命题演算—如两个命题表达式在任何真值指派下都有相同的值，则称为是等价的（P29）表2.2所示的真值表证明：P=Q与~P∨Q等价。—对于命题表达式P，Q，R~(~P)=P;(P∨Q)＝(~P=Q)4DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring否定律：~(P∨Q)＝(~P∧~Q)~(P∧Q)＝(~P∨~Q)分配律：P∨(Q∧R)＝(P∨Q)∧(P∨R)分配律：P∧(Q∨R)＝(P∧Q)∨(P∧R)交换律：(P∧Q)＝(Q∧P)交换律：(P∨Q)＝(Q∨P)结合律：((P∧Q)∧R)＝(P∧(Q∧R))结合律：((P∨Q)∨R)＝(P∨(Q∨R))置换律：(P=Q)＝(~Q=~P)3.1命题演算5DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2谓词演算命题演算中，P，Q代表一定的命题，如：P：星期四下雨而谓词：Weather（X，Y）代表日期与天气的关系Weather（Tuesday，Rain）可以操纵命题演算表达式允许包含变元Weather（X，Rain）6DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2.1谓词的语法和命题3.2谓词演算谓词演算的字母表组成：（1）英文字母组合，包括大写与小写（2）数字集合0,1,…,9（3）下划线如：Georgefiresbillxxxx7DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring谓词演算符号包括：1.真值符号true和false。2.常元符号,第一个字符为小写字母的符号表达式。3.变元符号,第一个字符为大写字母的符号表达式。4.函词符号,第一个字符为小写字母的符号表达式,函词有一个元数,指出从定义域中映射到值域中的每个元素。3.2谓词演算8DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring例：likes(george,kate).likes(X,george).likes(george,susie).likes(X,X).likes(george,sarah,tuesday).friends(bill,richard).friends(bill,george).friends(father(david),father(andrew))helps(bill,george).helps(richard,bill).3.2谓词演算原子命题：是一个n元谓词，后跟n个项，用括号括起来并用逗号分开。谓词符号常元符号项9DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2.1谓词的语法和命题与谓词相关的一个正整数称为元数或“参数数目”，具有相同的名但元数不同的谓词是不同的。真值true和false也是原子命题。任何原子命题都能够用逻辑操作符将其变成谓词演算的命题。用的联结词也和命题演算一样:∨,∧,~,=和＝。当一个变元在一个命题中作为参数出现时,它代表的是域中不特定的对象。谓词演算包括两个符号,量词（全称量词）和彐（存在量词）,用于限定包含变元的命题的含义。10DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2.1谓词的语法和命题一个量词后面紧跟着一个变元和一个命题。例如：Xlikes(X,ice_cream).彐Yfriends(Y,peter).全称量词,表明命题对于变元的变域中的所有的值都为真。存在量词彐,表明该命题对于变元的变域中的一些值为真。11DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring例：命题3.2.1谓词的语法和命题plus(two,three)equal(plus(two,three))彐xfoo(x,two,plus(two,three))∧equal(plus(two,three),five)12DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2.2谓词演算的语义谓词演算的语义提供了确定合式表达式真值的形式基础。表达式的真值依赖于常元、变元、谓词、函词到论域中的映射，在论域中的关系的真假决定了相应表达式的真假。例如：friends(george,susie)friends(george,kate)13DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2.2谓词演算的语义一个论域D上的解释：假设论域D是一个非空集合，在D上的一个解释把论域D的实体指派给一个谓词演算表达式的每一个常元、变元、谓词及函词符号，于是有：1）每一个常元指派了D的一个元素。2）对每一个变元，指派D的一个非空集合，这是该变元的变域。3）每个n元谓词P定义在论域D中的n个参数上，并定义了从Dn到{T，F}的一个映射。4)每个m元函词f定义在论域D的m个参数上，并定义了从Dm到{T，F}的一个映射。在一种解释下，一个表达式的意义是在该解释下的一个真值指派。14DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.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。15DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2.2谓词演算的语义变元：likes(george,X)这个变元名可以由任何其他变元名代替，不会改变表达式的意思。变元的量词约束是谓词演算语义的重要部分在谓词演算中,变元有两种约束使用的方法:在特定解释下,命题对变元的变域中的所有常元指派为真,则称该变元是全称性变元。代表全称量词的符号是,括号常常用于表示量词的约束范围存在性变元。至少存在变元的变域中的一个值使包含变元的表达式为真时，表达式才为真。代表存在量词的符号是彐16DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.2.2谓词演算的语义否定与全称量词、存在量词之间的关系。对于谓词P,Q,变元X,Y有：~彐XP(X)＝X~P(X)~XP(X)＝彐X~P(X)彐XP(X)＝彐YP(Y)XQ(X)＝YQ(Y)X(P(X)∧Q(X))＝XP(X)∧YQ(Y)彐X(P(X)∨Q(X))＝彐XP(X)∨彐YQ(Y)17DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.3推理规则产生谓词演算表达式3.3.1推理规则推理规则：实际上是一个从其他谓词演算命题产生新的谓词演算命题的机械方法。亦即推理规则产生基于给定逻辑断言的句法形式的新命题。当每个由逻辑表达式集S上的推理规则产生的命题X都是S的逻辑结果,则称该逻辑规则是合理的。S:Xhuman(X)=mortal(X).human(Socrates).X:mortal(Socrates).18DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring假言推理和消解原理都是合理的推理规则的例子。假言推理：如果命题P，P=Q为真，应用假言推理得出Q为真。S:Xhuman(X)=mortal(X).human(Socrates).X:mortal(Socrates).human(Socrates)=mortal(Socrates)？human(X)Socrates合一算法19DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.3.2合一伪代码写的函数Unify用于计算两个谓词表达式的最一般合一是判断两个谓词表达式匹配所需的一种代入算法合一表明了两个或多个表达式在什么条件下可以称为等价的。以两个谓词演算表达式为参数,若这两个表达式可以合一,则返回最一般合一代入,否则返回FAIL。20DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.3.2合一functionunify(E1,E2);begincase…end%endcaseend首先,它递归地试图对表达式的初始成分合一。如果成功,这次合一返回的任何代入式被用到两个表达式的剩下部分,然后以这两个表达式为参数。终止条件是两个参数之一为一个符号(谓词名,函词名,变元,常元),或两个表达式的每一元素都已匹配了。21DepartmentofComputerScience&Technolo