第2章(知识表示方法3-谓词逻辑)

2020/6/13,人工智能ArtificialIntelligence(AI),刘静liuj理工学院2009年春季,2020/6/13,第2章知识表示方法2.1状态空间法2.2问题归约法2.3谓词逻辑法,2020/6/13,2.3谓词逻辑法数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑,2020/6/13,谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）,2020/6/13,2.3.0命题逻辑的复习,1、命题逻辑的基本概念命题是能够判断真或假的陈述句通常用大写字母来表示，如A,B,P,Q等命题的真假值一般用T或F来表示,2020/6/13,例：雪是白的。（陈述句，T）雪是可蓝的。（陈述句，F）雪是黑的。（陈述句，F）他是学生。（陈述句，他泛指，无法判断真假）你今天上课没有？（疑问句）请坐校车！（祈使句）,2020/6/13,命题逻辑是研究命题及命题之间关系的符号逻辑系统。在命题逻辑中，表示单一意义的命题，称之为原子命题。原子命题通过“联结词”构成复合命题。,2020/6/13,五个联结词：,“”表示“非”复合命题P为真，当且仅当P为假。,“”表示“合取”复合命题“PQ”为真，当且仅当P和Q都为真。,2020/6/13,p:李平聪明q:李平用功pq：李平不但聪明，而且用功pq：李平聪明,但不用功,2020/6/13,“”表示“析取”复合命题“PQ”为真，当且仅当P、Q两者之一为真。p:李平聪明q:李平用功pq：李平聪明或者用功pq：李平聪明或者不用功,2020/6/13,“”表示“蕴含”复合命题“PQ”为假，当且仅当P为真且Q为假。与自然语言不一样，蕴涵式的前件和后件可以没有内在联系例如：如果224，则太阳从西边出来,2020/6/13,将下列命题符号化只要不下雨，我就骑自行车上班只有不下雨，我才骑自行车上班p:下雨q:骑自行车上班pqqp,2020/6/13,“”表示“等价”复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时为假。,2020/6/13,“”表示“等价”复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时为假。与自然语言不一样，等价式的2个命题可以没有内在联系例如：224，当且仅当太阳从西边出来,2020/6/13,联接词的优先顺序：非、合取、析取、蕴含、等价注：可以用括号表示优先级,2020/6/13,真值表,2020/6/13,命题变元：用符号P、Q等表示的不具有固定、具体含义的命题。它可以表示具有“真”、“假”含义的各种命题。命题变元可以利用联结词构成所谓的合适公式。,2020/6/13,合适公式的定义若P为原子命题，则P为合适公式，称为原子公式。若P是合适公式，则P也是一个合适公式。,2020/6/13,若P和Q是合适公式，则PQ、PQ、PQ、PQ都是合适公式。经过有限次使用规则1、2、3，得到的由原子公式、联结词和圆括号所组成的符号串，也是合适公式。,2020/6/13,对于合适公式，规定下列运算优先级：逻辑联结词的运算优先次序为：、同级联结词按出现顺序优先运算,2020/6/13,在命题逻辑中，主要研究推理的有效性。即：能否根据一些合适公式（前提）推导出新的合适公式（结论）。,一些合适公式（前提条件）,合适公式（结论）,？,2020/6/13,在命题逻辑中，最基本的单元是命题，它是作为一个不可分割的整体。例如：雪是黑的命题逻辑具有较大的局限性，不合适于表达比较复杂的问题。,2020/6/13,例：所有科学都是有用的（假设1）。数理逻辑是科学（假设2）。所以，数理逻辑是有用的（结论）。很明显，我们无法用两个假设推断出结论。,2020/6/13,例：苏格拉底三段论p:凡人都是要死的q:苏格拉底是人r:苏格拉底是要死的命题符号化：(pq)r真值不定！,2020/6/13,解决问题的办法将命题进一步分解成：个体词，谓词和量词等研究它们的形式结构和逻辑关系，总结出正确地推理形式和规则一阶谓词逻辑,2020/6/13,谓词逻辑是命题逻辑的扩充和发展。它将一个原子命题分解成客体和谓词两个组成部分。例如：雪是黑的客体谓词本课程主要介绍一阶谓词逻辑。,2020/6/13,2.3.1谓词演算,1、语法与语义谓词逻辑的基本组成部分谓词变量函数常量圆括号、方括号、花括号和逗号,2020/6/13,例“机器人（Robot）在第一个房间（Room1）内”，可以表示为：INROOM（ROBOT，r1）其中INROOM是谓词ROBOT和r1是常量,2020/6/13,谓词是指个体（客体）所具有的性质或者若干个体之间的关系。用大写字母来表示。个体是可以具体的（如，小张、3、5）也可以是抽象的（如，x,y）。,2020/6/13,例：小明是学生，A表示是“是学生”，x表示“小明”，记作A(x)。x大于y，G表示“大于”，记作G（x,y）。,2020/6/13,论域：由个体组成的集合。（个体）变量：定义在某一个论域上的变量。用x,y,z来表示。函数（或函词）：以个体为变量，以个体为值的函数。一般用小写字母来表示，例如f(x),f(x,a)。,2020/6/13,如果谓词有n个变量，称之为n元谓词，并约定0元谓词就是命题（谓词的特例）。如果函数有n个个体，称之为n元函数，并约定0元函数就是常量。常量习惯上用小写字母来表示，如a,b,c。,2020/6/13,项的定义：常量是项变量是项如果f是n元函数，且t1,tn(n1)是项，则f(t1,tn)也是项所有的项都必须是有限次应用上述规则产生的,2020/6/13,项的例子：常量：a变量：x函数：f(x,a)g(f(x,a),2020/6/13,原子（谓词）公式的（递归）定义：原子命题是原子公式如果t1,tn(n1)是项，P是谓词，则P(t1,tn)是原子公式其它表达式都不是原子公式,2020/6/13,原子公式的例子1、原子公式：P（原子命题）2、项：x,a,f(x,a)，谓词：P原子公式：P(x,a,f(x,a),2020/6/13,2、连词和量词,联结词（连词）就是命题逻辑中的五个，它们的含义也是一样的。,2020/6/13,两个量词：全称量词，记作“x”,含义是“对每一个x”或“对一切x”。存在量词，记作“x”，含义是“存在某个x”、“有一个x”或者“某些x”。,2020/6/13,例1：“所有的机器人都是灰色的”，用谓词逻辑可以表示成：（x）ROBOT(x)COLOR(x，gray),2020/6/13,例2：“一号房间里有一个物体”，可以表示成（x）INROOM（x,r1）,2020/6/13,所有的人都是要死的定义谓词：F(x），x是要死的个体域为全体人类时：xF(x）全总个体域(没有申明个体域)：x(M(x)F(x)特性谓词：M(x),2020/6/13,有的人活到100岁以上定义谓词：G(x）x活到100岁以上个体域为全体人类时：xG(x）全总个体域(没有申明个体域)：x(M(x)G(x),2020/6/13,量词使用的注意事项,1.不同的个体域，符号化的形式可能不一样2.如果没有给出个体域，都应以全总个体域为个体域3.引入特性谓词后，使用全称量词和存在量词符号化的形式不一样4.个体词和谓词的涵义确定之后，n元谓词转化成命题至少要n个量词,2020/6/13,5.当个体域为有限集时，D=a1,a2,an,由量词的意义可以看出，对于任意的谓词F(x)，都有xF(x)F(a1)F(a2)F(an)xF(x)F(a1)F(a2)F(an)6.多个量词同时出现，不能够随意颠倒它们的次序xyH(x,y)xyH(x,y),2020/6/13,我们称x是被量化了的变量，称为约束变量。否则称之为自由变量。一阶谓词：只允许对变量施加量词，不允许对谓词和函数施加量词。,2020/6/13,2.3.2谓词公式,1、谓词公式的定义,利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公式、谓词公式、合适公式。,2020/6/13,（谓词）合适公式的（递归）定义：原子（谓词）公式是合适公式。若A是合适公式，则A也是合适公式。若A和B是合适公式，则AB、AB、AB、AB也是合适公式。,2020/6/13,若A是合适公式，x为A的自由变元（变量），则（x）A和（x）A都是合适公式。只有按上述规则求得的公式才是合适公式。,2020/6/13,例：任何整数或者为正或者为负。数学表达：对于所有的x，如果x是整数，则x或者为正、或者为负。记作：I(x)：“x是整数”。P(x)：“x是正数”。N(x)：“x是负数”。谓词公式：（x）（I(x)(P(x)N(x)）,2020/6/13,2、合适公式的性质,如果P和Q是合适公式，则由这两个合适公式构成的合适公式的真值表与前面介绍的真值表相同。,如果两个合适公式的真值表相同，则我们称这两个合适公式是等价的，可以用“”来表示。,2020/6/13,对于命题合适公式和谓词合适公式有下列等价关系：,否定之否定：（P）等价于PPQ等价于PQ狄.摩根定律（PQ）等价于PQ（PQ）等价于PQ,2020/6/13,分配律P(QR)等价于(PQ)(PR)P(QR)等价于(PQ)(PR)交换律PQ等价于QPPQ等价于QP,2020/6/13,结合律(PQ)R等价于P(QR)(PQ)R等价于P(QR)逆否律PQ等价于QP,说明：上述等价关系对命题合适公式、谓词合适公式都成立。,2020/6/13,对于谓词合适公式有下列等价关系：,(x)P(x)等价于(x)P(x)(x)P(x)等价于(x)P(x)(x)P(x)Q(x)等价于(x)P(x)(x)Q(x)(x)P(x)Q(x)等价于(x)P(x)(x)Q(x),2020/6/13,(x)P(x)等价于(y)P(y)(x)P(x)等价于(y)P(y),注释：这两个关系说明，在一个量化的表达式中的约束变量是一类虚元，它们可以用任何不在表达式中出现的其它变量来代替。,2020/6/13,2.3.3置换与合一,1、置换,置换的定义：形如t1/v1,tn/vn的集合，称为一个置换，其中vi是不同的变量，ti是与vi不同的项。,2020/6/13,例或例子的定义：设t1/v1,tn/vn为一个置换，E是一个原子谓词公式。则E表示将E中的vi同时用ti（i=1,n）代入后所得到的结果，E称为E的一个例子。,2020/6/13,例：表达式（原子谓词公式）Px,f(y),B的四个置换及其对应的四个例子（B是常量）,s1=z/x,w/ys2=A/ys3=q(z)/x,A/ys4=c/x,A/y,Px,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),BPx,f(y),Bs3=Pq(z),f(A),BPx,f(y),Bs4=Pc,f(A),B,Px,f(y),B,2020/6/13,置换的合成：设t1/x1,tn/xn和s1/y1,sm/ym是两个置换，则和的合成是如下置换：t1/x1,ti/xi,tn/xn,s1/y1,sn/ym其中，对于任何tj=xj者消去，yj是x1,xn之一者消去，并记成。,2020/6/13,如何求ti:s1/y1,sm/ym如果ti出现y1,.,ym中的变量yi，则用其对应的项si来代替。,2020/6/13,例：=t1/x1,t2/x2f(y)/x,z/y=s1/y1,s2/y2,s3/y3=a/x,b/y,y/z=t1/x1,t2/x2,s1/y1,s2/y2,s3/y3=f(b)/x,y/y,a/x,b/y,y/z=f(b)/x,y/z,2020/6/13,注意：置换的合成满足结合律，不满足交换律。(s1s2)s3=s1(s2s3)(满足结合律）s1s2s2s1（不满足交换律）,2020/6/13,例：s1=z/x,w/ys2=A/ys1s2=z/x,w/y,A/y=z/x,w/ys2s1=A/y,z/x,w/y=A/y,z/x,2020/6/13,2、合一,当某一个置换s作用于表达式集合Ei的每一个元素，此时我们用Eis来表示置换例子的集合。如果存在一个置换s，使得E1s=E2s=Eis=则我们称表达式集合Ei是可合一的，并称s为Ei的合一者。原因是它的作用是使集合Ei成为单一形式。其中，Ei是原子谓词公式。,2020/6/13,例：表达式集合Px,f(y),B,Px,f(B),B的合一者为是s=A/x,B/yPx,f(y),Bs=PA,f(B),BPx,f(B),Bs=PA,f(B),B,2020/6/13,如果s是Ei的任意一个合一者，又存在某一个s，使得s=gs或者Eis=Eigs则称g是Ei的最通用（最一般）的合一者，记作mgu。,2020/6/13,例：s=A/x,B/y是表达式集合Px,f(y),B,Px,f(B),B的一个合一者，该集合的最一般的合一者是：g=B/y,2020/6/13,3、合一算法,分歧集（或不一致集合）的定义。设有一非空有限公式集合F=F1,Fn，从F中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从F中的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素，组成一个集合D，称为F的分歧集（不一致集合）。其中，Fi(i=1,n)是原子谓词公式,2020/6/13,例：公式集：F=P(x,g(f(y,z),x),y),P(x,g(a,b),b),P(x,g(g(h(x),a),y),h(x)分歧集为：D=f(y,z),a,g(h(x),a),2020/6/13,设F为非空有限表达式集合，则可以按下列步骤求出mgu：置k=0，Fk=F,k=(空置换，即不含元素的置换)。若Fk只有一个表达式，则算法终止，其中k就是要求的mgu。找出Fk的分歧集Dk。,合一算法：,2020/6/13,若Dk中存在元素ak和tk，其中ak是变元，tk是项，且ak不在tk中出现，则置：k+1=ktk/akFk+1=Fktk/akk=k+1然后转向。否则，继续。算法终止，F的mgu不存在。,2020/6/13,合一算法的流程图,k=0,Fk=F,k=,|Fk|1？,求得mgu、结束,求出不一致集合,有置换？,求出新置换；更新公式集合与旧置换，k+,无解、结束,2020/6/13,说明：1、合一算法是消解原理的基础。2、合一算法中的公式集就是从谓词合适公式化成的子句集。,2020/6/13,例：求F=P(a,x,f(g(y),P(z,h(z,u),f(u)的最一般的合一者。解：我们根据合一算法一步一步地求出mgu。,2020/6/13,第一步：k=0,F0=F,0=F0的分歧集合D0=a,z置换：a/z1=0a/z=a/zF1=F0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)k=1F1不是单一表达式,F=P(a,x,f(g(y)，P(z,h(z,u),f(u),2020/6/13,第二步：D1x,h(a,u)置换：h(a,u)/x21h(a,u)/x=a/z,h(a,u)/xF2=F1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)k=2,F=P(a,x,f(g(y)，P(a,h(a,u),f(u),2020/6/13,第三步：D2g(y),u置换：g(y)/u32g(y)/u=a/z,h(a,g(y)/x,g(y)/uF3=F2g(y)/u=P(a,h(a,g(y),f(g(y)k=3,F=P(a,h(a,u),f(g(y)，P(a,h(a,u),f(u),2020/6/13,F3是单一表达式，所以3a/z,h(a,g(y)/x,g(y)/u是F的最一般合一者,2020/6/13,例：F=Q(f(a),g(x),Q(y,y)是否可合一？,第一步：k=0,F0=F,0=F0的分歧集合D0=f(a),y置换：f(a)/y10f(a)/y=f(a)/yF1=F0f(a)/y=Q(f(a),g(x),Q(f(a),f(a)k=1F1不是单一表达式,2020/6/13,第二步：D1g(x),f(a)不存在着变量，所以不可合一。,F1=Q(f(a),g(x),Q(f(a),f(a),2020/6/13,课堂作业求公式集W=Q(x,y,z),Q(a,f(b),a)的最一般的合一者?其中，x,y,z为变量，a为常量，f为函数,2020/6/13,回顾：用谓词逻辑表示知识例1用谓词逻辑表示“张华是个人”首先定义谓词：用person表示“是个人”，则person（x）表示“x是个人”用谓词person（张华）表示“张华是个人”,2020/6/13,例2用谓词逻辑表示“李明和张华是同学”定义谓词：classmate（x，y）表示x和y是同学则“李明和张华是同学”可表示为：classmate（李明，张华）,2020/6/13,例3用谓词逻辑表示“10x20”定义谓词：P1（x，y）表示xy（yx）则“10x20”可表示为：P1（x，10）P1（20，x）,2020/6/13,例4用谓词逻辑表示“李明或者游泳，或者爬山”定义谓词：P3（x）表示x游泳，P4（x）表示x爬山则“李明或者游泳，或者爬山”可表示为：P3（李明）P4（李明）,2020/6/13,例5用谓词逻辑表示“莎莎不是人，是狗”定义谓词：person（x）表示“x是个人”，dog（y）表示“y是狗”则“莎莎不是人，是狗”可表示为：person（莎莎）dog（莎莎）,2020/6/13,例6用谓词逻辑表示“所有的有理数都是实数”定义谓词：P（x）表示x是有理数Q（x）表示x是实数则“所有的有理数都是实数”可表示为：（x）（P（x）Q（x）,2020/6/13,例7用谓词逻辑表示“有的实数是有理数”定义谓词：P（x）表示x是有理数Q（x）表示x是实数则“有的实数是有理数”可表示为：（x）（Q（x）P（x）,2020/6/13,例8用谓词逻辑表示“所有的整数不是偶数就是奇数”定义谓词：I（x）表示x是整数E（x）表示x是偶数O（x）表示x是奇数将“所有的整数不是偶数就是奇数”这句话改造为：“对于所有的数，如果是整数，则或者是偶数，或者是奇数”则“所有的整数不是偶数就是奇数”可表示为：（x）（I（x）（E（x）O（x）,2020/6/13,例9用谓词逻辑表示“所有教师都有自己的学生”定义谓词：teacher（x）表示x是教师student（y）表示y是学生teaches（x，y）表示x是y的老师则“所有教师都有自己的学生”可表示为：（x）（y）（teacher（x）teaches（x，y）student（y）可读作：“对于所有的x，总存在一些y，使得：如果x是教师，则x是y的老师且y是学生这件事成立”实际就是将“所有教师都有自己的学生”这句话改为：“所有是教师的，总存在一些和教师是师生关系的学生”,2020/6/13,例10用谓词逻辑表示“每个人都有一个父亲”定义谓词：person（x）表示x是人hasfather（x，y）表示x有父亲y则“每个人都有一个父亲”可表示为：（x）（y）（person（x）person（y）hasfather（x，y）例中的、等称为联结词，分别称为“与”、“或”、“非”、“蕴涵”等。和称为量词，其中称为全称量词，称为存在量词,2020/6/13,例11有下列知识：刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程序。人人爱劳动。为了用谓词公式表示上述知识，首先需要定义谓词：Bigger(x,y):x比y出名。Computer(x):x是计算机系的学生。Like(x,y):x喜欢y。Love(x,y):x热爱y。Man(x):x是人。然后用谓词公式把上述知识表示为：Bigger（Liuhong,father(Liuhong)Computer(Gaoyang)Like(Gaoyang,programing)(x)(Man(x)Love(x,labour),2020/6/13,例12设有下列知识自然数都是大于零的整数所有整数不是偶数就是奇数偶数除以2是整数首先定义谓词如下：n(x):x是自然数I(x):x是整数E(x):x是偶数O(x):x是奇数GZ(x):x大于零另外用函数S(x)表示x除以2.此时，上述知识可用谓词公式分别表示为：(x)（n(x)GZ(x)I(x)）(x)(I(x)E(x)O(x)(x)(E(x)I(s(x),2020/6/13,例13.设在房内c处有一机器人，在a及b处各有一张桌子，a桌上有一个盒子，为了让机器人从c处出发把盒子从a处拿到b处的桌上，然后再回到c处，需要制定相应的行动规划。下面用一阶谓词逻辑描述机器人的行动过程。该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。,设相关谓词的定义如下：table(x):x是桌子empty(y):y手中是空的at(y，z)：y在z的附近holds(y,w):y拿着won(w,x):w在x的上面其中，x的个体域是a,b;y的个体域是robot;z的个体域是a,b,c;w的个体域是box,2020/6/13,问题的初始状态是：at(robot,c)empty(robot)on(box,a)table(a)table(b)问题的目标状态是：at(robot,c)empty(robot)on(box,b)table(a)table(b)机器人的目标是把问题的初始状态转化为目标状态，其间它必须完成一系列的操作。,2020/6/13,操作一般可以分为条件和动作两部分。条件可以很容易的用谓词公式表示，动作可以通过动作前后的状态变化表示出来，即只要指出动作后应从动作前的状态中删去和增加什么谓词就描述了相应的动作。机器人为了把盒子从a处拿到b处，应执行如下三个操作：goto(x,y):从x处走到b处；pick_up(x):在x处拿起盒子；set_done(x):在x处放下盒子。这三个操作分别用条件和动作表示如下：1.Goto(x,y)条件：at(robot,x)动作删除：at(robot,x)增加：at(robot,y)2.Pick_up(x)条件：on(box,x)table(x)empty(robot)动作删除：empty(robot)on(box,x)增加:holds(robot,box),2020/6/13,3.Set_down(x)条件：at(robot,x)table(x)holds(robot,box)动作删除：holds(robot,box)增加：empty(robot)on(box,x)操作步骤：机器人在执行每一个操作前，总要先检查当前状态是否可使所要求的条件得到满足。若能满足，就执行相应的操作，否则就检查下一个操作所要求的条件。所谓检查当前状态是否满足所要求的条件，其实是一个定理证明的过程，即证明当前状态是否蕴含操作所要求的条件，若蕴含表示当前所要求的条件得到了满足。机器人行动规划问题的求解过程如下：(其中，在检查条件的满足性时要进行变量的代换。),2020/6/13,At(robot,c)Empty(robot)状态1(初始状态)On(box,a)用c代换xTable(a)用a代换yTable(b)goto(x,y)At(rob