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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/3/10,#,2024/10/2,人 工 智 能,Artificial Intelligence (AI),刘 静,liuj,理工学院,200,9,年春季,2024/10/2,第,2,章 知识表示方法,2.1 状态空间法,2.2 问题归约法,2.3,谓词逻辑法,2024/10/2,2.3,谓词逻辑法,数理逻辑,（符号逻辑）是用数学方法研究形式逻辑的一个分支。,它,通过符号系统来表达客观对象以及相关的逻辑推理。常用的是,命题逻辑,和,谓词逻辑,2024/10/2,谓词逻辑,是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言,人工智能中的谓词逻辑法,是指用一阶谓词来描述问题求解和定理证明（,限于本课程,）,2024/10/2,2.3.0,命题逻辑的复习,1、,命题逻辑的基本概念,命题,是能够判断,真或假,的,陈述句,通常用,大写字母,来表示，如,A, B, P, Q,等,命题的真假值一般用,T,或,F,来表示,2024/10/2,例,：,雪是白的。（陈述句，,T）,雪是可蓝的。（陈述句，,F）,雪是黑的。（陈述句，,F）,他,是学生。（陈述句，他泛指，无法判断真假）,你今天上课没有？（疑问句）,请坐校车！（祈使句）,2024/10/2,命题逻辑,是研究命题及命题之间关系的符号逻辑系统。,在命题逻辑中，表示单一意义的命题，称之为,原子命题,。,原子命题通过,“,联结词,”,构成,复合命题,。,2024/10/2,五个联结词,：,“,”,表示,“,非,”,复合命题,P,为真，当且仅当,P,为假。,“,”,表示,“,合取,”,复合命题,“,P,Q”,为真，当且仅当,P,和,Q,都为真。,2024/10/2,p:,李平聪明,q:,李平用功,pq,：李平不但聪明，而且用功,p,q,：李平聪明,但不用功,2024/10/2,“,”,表示,“,析取,”,复合命题,“,P,Q,”,为真，当且仅当,P,、,Q,两者之一为真。,p:,李平聪明,q,:,李平用功,p,q,：李平聪明或者用功,p,q,：李平聪明或者不用功,2024/10/2,“,”,表示,“,蕴含,”,复合命题,“,P,Q”,为假，当且仅当,P,为真且,Q,为假。,与自然语言不一样，蕴涵式的前件和后件可以没有内在联系,例如：如果,2,24,，则太阳从西边出来,2024/10/2,将下列命题符号化,只要不下雨，我就骑自行车上班,只有不下雨，我才骑自行车上班,p:,下雨,q:,骑自行车上班,p q,qp,2024/10/2,“,”,表示,“,等价,”,复合命题,“,P,Q,”,为真，当且仅当,P,、,Q,同时为真、或者同时为假。,2024/10/2,“,”,表示,“,等价,”,复合命题,“,P,Q,”,为真，当且仅当,P,、,Q,同时为真、或者同时为假。,与自然语言不一样，等价式的,2,个命题可以没有内在联系,例如：,2,24,，当且仅当太阳从西边出来,2024/10/2,联接词的,优先顺序,：,非,、,合取,、,析取,、,蕴含,、,等价,注,：可以用括号表示优先级,2024/10/2,真值表,P,Q,P,PQ,PQ,P,Q,P,Q,F,F,T,F,F,T,T,F,T,T,F,T,T,F,T,F,F,F,T,F,F,T,T,F,T,T,T,T,2024/10/2,命题变元,：用符号,P,、,Q,等表示的不具有固定、具体含义的命题。它可以表示具有,“,真,”,、,“,假,”,含义的各种命题。,命题变元可以利用联结词构成所谓的,合适公式,。,2024/10/2,合适公式的定义,若,P,为原子命题，则,P,为合适公式，称为原子公式。,若,P,是合适公式，则,P,也是一个合适公式。,2024/10/2,若,P,和,Q,是合适公式，则,PQ、 PQ 、P,Q 、P,Q,都是合适公式。,经过有限次使用规则1、2、3，得到的由原子公式、联结词和圆括号所组成的符号串，也是合适公式。,2024/10/2,对于合适公式，规定下列,运算优先级,：,逻辑联结词的运算优先次序为：,、 、,、,同级联结词按出现顺序优先运算,2024/10/2,在命题逻辑中，主要研究推理的有效性。,即：能否根据一些合适公式（,前提,）推导出新的合适公式（,结论,）。,一些合适公式,（前提条件）,合适公式,（结论）,？,2024/10/2,在命题逻辑中，最基本的单元是命题，它是作为一个不可分割的整体。,例如：,雪是黑的,命题逻辑具有较大的局限性，不合适于表达比较复杂的问题。,2024/10/2,例,：,所有科学都是有用的,（假设1）,。,数理逻辑是科学,（假设2）,。,所以，数理逻辑是有用的,（结论）,。,很明显，我们无法用,两个假设,推断出,结论,。,2024/10/2,例,：,苏格拉底三段论,p:,凡人都是要死的,q:,苏格拉底是人,r:,苏格拉底是要死的,命题符号化：,(pq)r,真值不定！,2024/10/2,解决问题的办法,将命题进一步分解成：个体词，谓词和量词等,研究它们的形式结构和逻辑关系，总结出正确地推理形式和规则,一阶谓词逻辑,2024/10/2,谓词逻辑,是命题逻辑的扩充和发展。它将一个原子命题分解成,客体,和,谓词,两个组成部分。,例如：,雪,是黑的,客体 谓词,本课程主要介绍一阶谓词逻辑。,2024/10/2,2.3.1,谓词演算,1、语法与语义,谓词逻辑的基本组成部分,谓词,变量,函数,常量,圆括号,、方括号、花括号和逗号,2024/10/2,例,“机器人（,Robot）,在第一个房间（,Room1）,内”，可以表示为：,INROOM（ROBOT，r1）,其中,INROOM,是,谓词,ROBOT,和,r1,是,常量,2024/10/2,谓词,是指个体（客体）所具有的,性质,或者若干个体之间的,关系,。用,大写字母,来表示。,个体,是可以具体的（如，小张、,3,、,5,）也可以是抽象的（如，,x, y,）。,2024/10/2,例,：,小明是学生，,A,表示是“是学生”，,x,表示“小明”，记作,A(x)。,x,大于,y,，,G,表示,“,大于,”,，记作,G,（,x, y,）。,2024/10/2,论域,：由个体组成的集合。,（,个体,）,变量,：定义在某一个论域上的变量。用,x, y, z,来表示。,函数,（或函词）,：以个体为变量，以个体为值的函数。一般用小写字母来表示，例如,f(x), f(x,a)。,2024/10/2,如果谓词有,n,个变量，称之为,n,元谓词，并约定,0,元谓词就是命题（谓词的特例）。,如果函数有,n,个个体，称之为,n,元函数，并约定,0,元函数就是常量。常量习惯上用小写字母来表示，如,a, b, c,。,2024/10/2,项,的定义：,常量是项,变量是项,如果,f,是,n,元函数，且,t,1, t,n,(,n,1),是项，则,f,(,t,1, t,n,),也是项,所有的项都必须是有限次应用上述规则产生的,2024/10/2,项的例子,：,常量：,a,变量：,x,函数：,f(x,a),g(f(x,a),2024/10/2,原子（谓词）公式,的（递归）定义：,原子命题是原子公式,如果,t,1,t,n,(,n,1),是项，,P,是谓词，则,P(,t,1,t,n,),是原子公式,其它表达式都不是原子公式,2024/10/2,原子公式的例子,1、原子公式：,P（,原子命题）,2、项：,x, a, f(x, a)，,谓词：,P,原子公式：,P(x, a, f(x,a),2024/10/2,2,、连词和量词,联结词（连词）,就是命题逻辑中的五个，它们的含义也是一样的。,2024/10/2,两个量词,：,全称量词,，记作“,x,”,含义是 “,对每一个,x,”,或“,对一切,x,”。,存在量词,，记作“,x,”，,含义是 “,存在某个,x,” 、“,有一个,x,”,或者 “,某些,x,”,。,2024/10/2,例1,：“,所有的机器人都是灰色的,”，用谓词逻辑可以表示成：,（,x,）ROBOT(,x,),COLOR(,x,，,gray,),2024/10/2,例2,： “,一号房间里有一个物体,”，可以表示成,（,x,）,INROOM,（,x, r1,）,2024/10/2,所有的人都是要死的,定义谓词：,F(x,），,x,是要死的,个体域为全体人类时：,xF(x,）,全总个体域,(,没有申明个体域,),：,x(M(x) F(x),特性谓词：,M(x),2024/10/2,有的人活到,100,岁以上,定义谓词：,G(x,）,x,活到,100,岁以上,个体域为全体人类时：,xG(x,）,全总个体域,(,没有申明个体域,),：,x(M(x)G(x),2024/10/2,量词使用的注意事项,1.,不同的个体域，符号化的形式可能不一样,2.,如果没有给出个体域，都应以全总个体域为个体域,3.,引入特性谓词后，使用全称量词和存在量词符号化的形式不一样,4.,个体词和谓词的涵义确定之后，,n,元谓词转化成命题至少要,n,个量词,2024/10/2,5.,当个体域为有限集时，,D=a1,a2,an,由量词的意义可以看出，对于任意的谓词,F(x),，都有,xF(x),F(a1)F(a2)F(an),xF(x),F(a1)F(a2)F(an),6.,多个量词同时出现，不能够随意颠倒它们的次序,x,yH(x, y),x,yH(x, y),2024/10/2,我们称,x,是被量化了的变量，称为,约束变量,。否则称之为,自由变量,。,一阶谓词,：只允许对,变量,施加,量词,，不允许对谓词和函数施加量词。,2024/10/2,2.3.2 谓词公式,1,、,谓词公式的定义,利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公式、,谓词公式,、合适公式,。,2024/10/2,（谓词）,合适公式,的（递归）定义：,原子（谓词）公式是合适公式。,若,A,是合适公式，则,A,也是合适公式。,若,A,和,B,是合适公式，则,AB,、,AB,、,A,B,、,A,B,也是合适公式。,2024/10/2,若,A,是合适公式，,x,为,A,的自由变元（变量），则,（,x）A,和,（,x）A,都是合适公式。,只有按上述规则求得的公式才是合适公式。,2024/10/2,例：任何整数或者为正或者为负。,数学表达,：对于所有的,x,，,如果,x,是整数，则,x,或者为正、或者为负。,记作,：,I(x)：“,x,是整数”。,P(x)：“,x,是正数”。,N(x)：“,x,是负数”。,谓词公式,：,（,x,）（,I(,x,),(P(,x,),N(,x,),）,2024/10/2,2,、合适公式的性质,如果,P,和,Q,是合适公式，则由这两个合适公式构成的合适公式的,真值表,与前面介绍的,真值表,相同。,如果两个合适公式的真值表相同，则我们称这,两个合适公式是等价的,，可以用,“,”,来表示。,2024/10/2,对于命题合适公式和谓词合适公式有下列等价关系：,否定之否定,：,（,P）,等价于,P,PQ,等价于,P,Q,狄.摩根定律,（,PQ）,等价于,PQ,（PQ）,等价于,PQ,2024/10/2,分配律,P(QR),等价于,(,PQ)(PR),P(QR),等价于,(PQ)(PR),交换律,PQ,等价于,QP,PQ,等价于,QP,2024/10/2,结合律,(,PQ)R,等价于,P(QR),(PQ)R,等价于,P(QR),逆否律,P,Q,等价于,Q,P,说明,：,上述等价关系对命题合适公式、谓词合适公式都成立。,2024/10/2,对于谓词合适公式有下列等价关系：,(,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),2024/10/2,(,x)P(x),等价于,(,y)P(y),(,x)P(x),等价于,(,y)P(y),注释,：,这两个关系说明，在一个量化的表达式中的约束变量是一类虚元，它们可以用任何不在表达式中出现的其它变量来代替。,2024/10/2,2.3.3,置换与合一,1,、置换,置换的定义,：形如,t,1,/,v,1, , t,n,/,v,n,的集合，称为一个置换，其中,v,i,是不同的变量，,t,i,是与,v,i,不同的项。,2024/10/2,例或例子的定义,：,设,t,1,/v,1, , t,n,/v,n,为一个置换，,E,是一个原子谓词公式。则,E,表示将,E,中的,v,i,同时用,t,i,（,i,=1,n,）,代入后所得到的结果，,E,称为,E,的一个,例子,。,2024/10/2,例,：表达式（原子谓词公式）,Px,f(y),B,的四个置换及其对应的四个例子 （,B,是常量,）,s,1,=z/x, w/y,s,2,=A/y,s,3,=q(z)/x, A/y,s,4,=c/x, A/y,P,x, f(,y,), Bs,1,=Pz, f(w), B,Px, f(,y,), Bs,2,=Px, f(A), B,P,x, f(,y,), Bs,3,=Pq(z), f(A), B,P,x, f(,y,), Bs,4,=Pc, f(A), B,Px,f(y),B,2024/10/2,置换的合成,：设,t,1,/x,1, ,t,n,/x,n,和,s,1,/y,1, ,s,m,/y,m,是两个置换，则,和,的合成是如下置换：,t,1,/x,1, t,i,/x,i, t,n,/x,n,s,1,/y,1, , s,n,/y,m,其中，对于任何,t,j,=x,j,者消去，,y,j,是 ,x,1,x,n,之一者消去，并记成,。,2024/10/2,如何求,t,i, :,s,1,/y,1, , s,m,/y,m,如果,t,i,出现,y,1, ., y,m,中的变量,y,i,， 则用其对应的项,s,i,来代替。,2024/10/2,例：,= t,1,/x,1, t,2,/x,2,f(y)/x , z/y,= s,1,/y,1, s,2,/y,2, s,3,/y,3, = a/x , b/y , y/z,=t,1,/x,1, t,2,/x,2,s,1,/y,1, s,2,/y,2, s,3,/y,3,=f(b)/x ,y/y,a/,x, b/,y, y/z,=f(b)/x , y/z,2024/10/2,注意,：,置换的合成满足结合律，不满足交换律。,(,s,1,s,2,)s,3,= s,1,(s,2,s,3,),(,满足,结合律,）,s,1,s,2,s,2,s,1,（,不,满足,交换律,）,2024/10/2,例,：,s,1,=z/x , w/y s,2,=A/y,s,1,s,2,=z/x , w/y , A/,y,=z/x , w/y,s,2,s,1,=A/y, z/x , w/,y,=A/y , z/x,2024/10/2,2,、合一,当某一个置换,s,作用于表达式集合,E,i,的每一个元素，此时我们用,E,i,s,来表示置换例子的集合。如果存在一个置换,s,，,使得,E,1,s,=,E,2,s,=,=,E,i,s,=,则我们称表达式集合,E,i,是可合一的，并称,s,为,E,i,的合一者。原因是它的作用是使集合,E,i,成为单一形式。 其中，,E,i,是原子谓词公式。,2024/10/2,例,：,表达式集合,Px , f(y) , B,Px , f(B) , B,的合一者为是,s = A/x , B/y,Px , f(y) , B,s = PA , f(B) , B,Px , f(B) , B,s = PA , f(B) , B,2024/10/2,如果,s,是,E,i,的,任意,一个合一者，又存在某一个,s,，,使得,s = g s,或者,E,i, s =,E,i, g s,则 称,g,是,E,i,的最通用（最一般）的合一者，记作,mgu,。,2024/10/2,例,：,s = A/x , B/y,是表达式集合,Px , f(y) , B , Px , f(B) , B,的一个合一者，该集合的,最一般的合一者,是：,g = B/y,2024/10/2,3,、合一算法,分歧集（或不一致集合）的定义,。,设有一非空有限公式集合,F = F,1, , F,n,，,从,F,中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从,F,中的各个公式中取出那些以第一个不一致符号开始的,最大的子表达式,为元素，组成一个集合,D,，,称为,F,的分歧集（不一致集合）。,其中，,F,i,(,i,=1 , ,n,),是原子谓词公式,2024/10/2,例,：公式集：,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),2024/10/2,设,F,为非空有限表达式集合，则可以按下列步骤求出,mgu,：,置,k=0,，,F,k,= F,k,=,(,空置换，即不含元素的置换)。,若,F,k,只有一个表达式，则算法终止，其中,k,就是,要求的,mgu,。,找出,F,k,的分歧集,D,k,。,合一算法,：,2024/10/2,若,D,k,中存在元素,a,k,和,t,k,，,其中,a,k,是变元，,t,k,是项，且,a,k,不在,t,k,中出现，则置：,k,+1,=,k, t,k,/ a,k,F,k,+1,= F,k, t,k,/ a,k,k = k+1,然后转向,。否则，继续。,算法终止，,F,的,mgu,不存在。,2024/10/2,合一算法的流程图,k=0, F,k,=F,k,=,|F,k,|,1？,求得,mgu、,结束,求出不一致集合,有置换？,求出新置换；更新公式集合与旧置换，,k+,无解、结束,2024/10/2,说明,：,1,、合一算法是消解原理的基础。,2,、,合一算法中的公式集就是从谓词合适公式化成的子句集。,2024/10/2,例,：求,F= P(a , x , f(g(y),P(z , h(z , u) , f(u),的最一般的合一者。,解,：我们根据合一算法一步一步地求出,mgu。,2024/10/2,第一步,：,k = 0, F,0,= F, ,0,=,F,0,的分歧集合,D,0,=a , z,置换,：,a/z,1,=,0,a/z = a/z,F,1,= F,0,a/z = P(a , x , f(g(y),P(a , h(a , u) , f(u),k=1,F,1,不是单一表达式,F=P(a,x,f(g(y)，,P(z,h(z,u),f(u),2024/10/2,第二步,：,D,1,x , h(a,u),置换,：,h(a , u)/x,2,1,h(a , u)/x=a/z , h(a , u)/x,F,2,=F,1,h(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),2024/10/2,第三步,：,D,2,g(y) , u,置换,：,g(y)/u,3,2,g(y)/u=a/z , h(a,g(y)/x , g(y)/u,F,3,=F,2,g(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),2024/10/2,F,3,是单一表达式，所以,3,a/z , h(a , g(y)/x , g(y)/u,是,F,的最一般合一者,2024/10/2,例：,F=Q(f(a) , g(x) , Q(y , y),是否可合一？,第一步,：,k=0, F,0,=F, ,0,=,F,0,的分歧集合,D,0,=f(a) , y,置换,：,f(a)/y,1,0,f(a)/y= f(a)/y ,F,1,=F,0, f(a)/y =Q(f(a) , g(x) , Q(f(a) , f(a),k=1,F,1,不是单一表达式,2024/10/2,第二步：,D,1,g(x), f(a),不存在着变量，所以不可合一。,F,1,=Q(f(a),g(x),Q(f(a),f(a),2024/10/2,课堂作业,求公式集,W= Q(x , y, z) ,Q(a , f(b) , a) ,的最一般的合一者,?,其中，,x,y,z,为变量，,a,为常量，,f,为函数,2024/10/2,回顾：用谓词逻辑表示知识,例,1,用谓词逻辑表示“张华是个人”,首先定义谓词：用,person,表示“是个人”，则,person,（,x,）表示“,x,是个人”,用谓词,person,（张华）表示“张华是个人”,2024/10/2,例,2,用谓词逻辑表示“李明和张华是同学”,定义谓词：,classmate,（,x,，,y,）表示,x,和,y,是同学,则“李明和张华是同学”可表示为：,classmate,（李明，张华）,2024/10/2,例,3,用谓词逻辑表示“,10x20”,定义谓词：,P1,（,x,，,y,）表示,xy,（,yx,）,则“,10x20”,可表示为：,P1,（,x,，,10,）,P1,（,20,，,x,）,2024/10/2,例,4,用谓词逻辑表示“李明或者游泳，或者爬山”,定义谓词：,P3,（,x,）表示,x,游泳，,P4,（,x,）表示,x,爬山,则“李明或者游泳，或者爬山”可表示为：,P3,（李明）,P4,（李明）,2024/10/2,例,5,用谓词逻辑表示“莎莎不是人，是狗”,定义谓词：,person,（,x,）表示“,x,是个人”，,dog,（,y,）表示“,y,是狗”,则“莎莎不是人，是狗”可表示为：,person,（莎莎）,dog,（莎莎）,2024/10/2,例,6,用谓词逻辑表示“所有的有理数都是实数”,定义谓词：,P,（,x,）表示,x,是有理数,Q,（,x,）表示,x,是实数,则“所有的有理数都是实数”可表示为：,（,x,）（,P,（,x,）,Q,（,x,）,2024/10/2,例,7,用谓词逻辑表示“有的实数是有理数”,定义谓词：,P,（,x,）表示,x,是有理数,Q,（,x,）表示,x,是实数,则“有的实数是有理数”可表示为：,（,x,）（,Q,（,x,）,P,（,x,）,2024/10/2,例,8,用谓词逻辑表示“所有的整数不是偶数就是奇数”,定义谓词：,I,（,x,）表示,x,是整数,E,（,x,）表示,x,是偶数,O,（,x,）表示,x,是奇数,将“所有的整数不是偶数就是奇数”这句话改造为：,“对于所有的数，如果是整数，则或者是偶数，或者是奇数”,则“所有的整数不是偶数就是奇数”可表示为：,（,x,）（,I,（,x,）（,E,（,x,）,O,（,x,）,2024/10/2,例,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,是学生这件事成立”,实际就是将“所有教师都有自己的学生”这句话改为：,“所有是教师的，总存在一些和教师是师生关系的学生”,2024/10/2,例,10,用谓词逻辑表示“每个人都有一个父亲,”,定义谓词：,person,（,x,）表示,x,是人,hasfather,（,x,，,y,）表示,x,有父亲,y,则“每个人都有一个父亲”可表示为：,（,x,）（,y,）（,person,（,x,）,person,（,y,）,hasfather,（,x,，,y,）,例中的、,、等称为联结词，分别称为“与”、“或”、“非”、“蕴涵”等。和 称为量词，其中,称为全称量词，,称为存在量词,2024/10/2,例,1 1,有下列知识：,刘欢比他父亲出名。,高扬是计算机系的一名学生，但他不喜欢编程序。,人人爱劳动。,为了用谓词公式表示上述知识，首先需要定义谓词：,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),2024/10/2,例,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),2024/10/2,例,13.,设在房内,c,处有一机器人，在,a,及,b,处各有一张桌子，,a,桌上有一个盒子，为了让机器人从,c,处出发把盒子从,a,处拿到,b,处的桌上，然后再回到,c,处，需要制定相应的行动规划。下面用一阶谓词逻辑描述机器人的行动过程。,该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。,c,a,b,设相关谓词的定义如下：,table(x):x,是桌子,empty(y):y,手中是空的,at(y,，,z),：,y,在,z,的附近,holds(y,w):y,拿着,w,on(w,x):w,在,x,的上面,其中，,x,的个体域是,a,b;,y,的个体域是,robot;,z,的个体域是,a,b,c;,w,的个体域是,box,2024/10/2,问题的初始状态是：,at(robot,c),empty(robot),on(box,a),table(a),table(b),问题的目标状态是：,at(robot,c),empty(robot),on(box,b),table(a),table(b),机器人的目标是把问题的初始状态转化为目标状态，其间它必须完成一系列的操作。,c,a,b,2024/10/2,操作一般可以分为,条件和动作,两部分。,条件,可以很容易的用谓词公式表示，,动作,可以通过动作前后的状态变化表示出来，即只要指出动作后应从动作前的状态中删去和增加什么谓词就描述了相应的动作。,机器人为了把盒子从,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),2024/10/2,3. Set_down(x),条件：,at(robot,x)table(x)holds(robot,box),动作 删除：,holds(robot,box),增加：,empty(robot)on(box,x),操作步骤：,机器人在执行每一个操作前，总要先检查当前状态是否可使所要求的条件得到满足。若能满足，就执行相应的操作，否则就检查下一个操作所要求的条件。,所谓检查当前状态是否满足所要求的条件，其实是一个定理证明的过程，即证明当前状态是否蕴含操作所要求的条件，若蕴含表示当前所要求的条件得到了满足。,机器人行动规划问题的求解过程如下：,(,其中，在检查条件的满足性时要进行变量的代换。,),2024/10/2,At(robot,c),Empty(robot),状态,1(,初始状态,),On(box,a),用,c,代换,x,Table(a),用,a,代换,y,Table(b),goto(x,y),At(robot,a),Empty(robot),状态,2,On(box,a),用,a,代换,x,Table(a),Table(b),pick-up(x),At(robot,a),Hold(robot,box),状态,3,Table(a),用,a,代换,x,Table(b),用,b,代换,y,goto(x,y,),At(robot,b),Hold(robot,box),状态,4,Table(a),用,b,代换,x,Table(b),setdown(x),At(robot,b),empty(robot),状态,5,on(box,b),用,b,代换,x,Table(a),用,c,代换,y,Table(b),goto(x,y),At(robot,c),empty(robot),状态,6,on(box,b) (,目标状态,),Table(a),Table(b),c,a,b,2024/10/2,自然性：,符合人类对问题的直觉理解；,描述性：,表示与知识分离；谓词逻辑本身具有比较扎实的数学基础，知识的表达方式决定了系统的主要结构。因此，对知识表达方式的严密科学性要求就比较容易得到满足。这样对形式理论的扩展导致了整个系统框架的发展。一阶谓词逻辑具有完备的逻辑推理算法。,精确性：,只有“真与假”的值；,谓词表示的特性,谓词逻辑法是应用最广的方法之一，其原因是：,2024/10/2,严密性：,谓词逻辑具有严格的形式定义以及推理规则；如果对逻辑的某些外延扩展后，则可把大部分的知识表达成一阶谓词逻辑的形式。（知识易表达）。逻辑推理是公理集合中演绎而得出结论的过程。由于逻辑及形式系统具有的重要性质，可以保证知识库中新旧知识在逻辑上的一致性（或通过相应的一套处理过程检验）、和所演绎出来的结论的正确性。而其它的表示方法在这点上还不能与其相比。,谓词表示的特性,2024/10/2,容易实现：,用谓词逻辑表示的知识可以比较容易地转换为计算机内部形式，易于模块化，便于对知识的增加、修改、删除；谓词逻辑与数据库，特别是关系数据库就有密切的关系。在关系数据库中，逻辑代数表达式是谓词表达式之一。因此，如果采用谓词逻辑作为系统的理论背景，则可将数据库系统扩展改造成知识库。,谓词表示的特性,2024/10/2,不能表示不确定的知识；,组合爆炸：,不易表示启发式知识，当状态空间大时，当前数据库与知识库中操作的匹配以及操作层列的确定会出现时空上的膨胀。,效率低。,谓词表示的特性,存在问题：,谓词表示越细，推理越慢、效率越低，但表示清楚。实际中是要折衷的。,2024/10/2,本章小结,三种基本的知识表达方法：,状态空间法,（状态、操作符、图表示）,问题归约法,（原始问题、本原问题、操作符、与或图表示）,谓词逻辑法,（谓词公式、置换、合一算法）,