知识表示方法par.ppt

《知识表示方法par.ppt》由会员分享，可在线阅读，更多相关《知识表示方法par.ppt（30页珍藏版）》请在三一办公上搜索。

1、Artificial Intelligence(AI)人工智能,主讲：刘刚,Email：andyliu,第4章：知识 表示,内容提要,第4章：知识表示,1.状态空间法,2.问题归约法,3.谓词逻辑法,4.语义网络法,5.其他方法,谓词逻辑法,命题逻辑与谓词逻辑命题命题逻辑的局限性谓词,谓词逻辑法,谓词演算谓词逻辑语言的语法和语义谓词逻辑语言的基本符号：谓词符号变量符号函数符号常量符号括号和逗号,谓词逻辑法,谓词演算谓词逻辑语言的语法和语义原子公式：原子公式由若干谓词符号和项组成谓词符号规定定义域内的一个相应关系常量符号是最简单的项，表示论域内的物体或实体变量符号也是项，不明确涉及是哪一个实体函

2、数符号表示论域内的函数，是从论域内的一个实体到另外一个实体的映射例如：原子公式 Married father(LI),mother(LI)表示“李（LI）的父亲和他的母亲结婚”,谓词逻辑法,连词和量词连词合取：符号“”，表示所连结的两个命题之间具有“与”的关系。析取：符号“”，表示所连结的两个命题之间具有“或”的关系蕴涵：符号“”，表示“若则”的语义。PQ读作“如果P，则Q”其中，P称为条件的前件，Q称为条件的后件。非：符号“”，表示对其后面的命题的否定双条件：符号“”，表示“当且仅当”的语义。PQ读作“P当且仅当Q”。连词的优先级：,谓词逻辑法,连词和量词量词全称量词：符号“”，意思是“所有

3、的”、“任一个”x读作“对一切x”,或“对每一x”，或“对任一x”。命题(x)P(x)为真，当且仅当对论域中的所有x，都有P(x)为真命题(x)P(x)为假，当且仅当至少存在论域中的一个x，使得P(x)为假,谓词逻辑法,连词和量词量词存在量词：符号“”，意思是“至少有”、“存在”x读作“存在一个x”,或“对某些x”，或“至少有一x”。命题(x)P(x)为真，当且仅当至少存在论域中的一个x，使得P(x)为真命题(x)P(x)为假，当且仅当对论域中的所有x，都有P(x)为假,谓词逻辑法,谓词公式原子谓词公式：是由谓词符号和若干项组成的谓词演算。若t1,t2,tn是项，P是谓词，则称P(t1,t2,

4、tn)为原子谓词公式。分子谓词公式：可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,谓词逻辑法,谓词公式合式公式（WFF，Well-formed Formulas）：通常把合式公式叫做谓词公式，递归定义如下：(1)原子谓词公式是合式公式(2)若A为合式公式，则 A也是一个合式公式(3)若A,B是合式公式，则AB，AB，AB，AB也都是合式公式(4)若A是合式公式，x为A中的自由变元，则(x)A和(x)A都是合式公式(5)只有按上述规则(1)至(4)求得的那些公式，才是合式公式。,谓词逻辑法,谓词公式用谓词公式表示知识时，需要首先定义谓词，然后再用连接词把有关的谓词连接起来，

5、形成一个谓词公式表达一个完整的意义。例1：设有下列知识刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程。任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词：FAMOUS(x,y):x比y出名COMPUTER(x):x 是计算机系的LIKE(x,y):x 喜欢 y,谓词逻辑法,I(x)表示“x是整数”P(x)表示“x是正数”N(x)表示“x是负数”此时可用谓词公式把上述知识表示为:刘欢比他父亲出名:FAMOUS(liuhuan,father(liuhuan)高扬是计算机系的一名学生，但他不喜欢编程:COMPUTER(gaoyang)LIKE(gaoyang,prog

6、raming)任何整数或者为正或者为负:(x)(I(x)(P(x)N(x),谓词逻辑法,谓词公式例2：用谓词逻辑描述右图中的房子的概念个体：A,B谓词：SUPPORT(x,y)：表示 x 被 y支撑着 WEDRE(x)：表示 x 是楔形块 BRICK(y)：表示 y 是长方块 其中 x,y是个体变元，它们的个体域A,B房子的概念可以表示成一组合式谓词公式的合取式：SUPPORT(A,B)WEDGE(A)BRICK(B),谓词逻辑法,合式公式的性质若P、Q是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出。,谓词逻辑法,合式公式的性质如果两个合式公式，无论如何解释，其真值表都

7、是相同的，那么我们就称此两合式公式是等价的。应用上述真值表可以确立下列等价关系：（1）否定之否定：(P)=P（2）(P Q)=(P Q)或者(P Q)=(P Q）（3）狄 摩根定律：(P Q)=P Q(P Q)=P Q,谓词逻辑法,（4）分配律：P(Q R)=(P Q)(P R)P(Q R)=(P Q)(P R)（5）交换律：P Q=Q PP Q=Q P（6）结合律：P(Q R)=(P Q)RP(Q R)=(P Q)R（7）逆否率：(P Q)=(Q P),谓词逻辑法,（8）泛界律：P F=P,P T=P P F=F,P T=T（9）互余律：P P=T,P P=F此外还可以确立下列等价关系：(x

8、)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)(x)P(x)=(y)P(y)(x)P(x)=(y)P(y),谓词逻辑法,置换与合一置换 推理规则：用合式公式的集合产生新的合式公式假元推理全称化推理综合推理,寻找A对x的置换，使W1(A)与W1(x)一致,谓词逻辑法,置换与合一置换（Substitution）置换的定义：置换是用变元、常量、函数来替换变元，使该变元不在公式中出现。置换是形如 t1/x1,t2/x2,，tn/xn的有限集合。t1，t2，tn是项x1，x2，xn是互不相同

9、的变元ti/xi表示用ti项替换变元xi，不允许ti和xi相同，也不允许变元xi循环地出现在另一个tj中,谓词逻辑法,置换与合一置换（Substitution）例如a/x,f(b)/y，w/z 是一个置换g(y)/x,f(x)/y 不是一个置换g(a)/x,f(x)/y 不是一个置换,谓词逻辑法,置换与合一置换（Substitution）例2.2，表达式 Px,f(y),B的置换为s1=z/x,w/y；s2=A/y；s3=q(z)/x,A/y；s4=c/x,A/y 用Es表示一个表达式E用置换s所得到的表达式的置换。于是，Px,f(y),B的4个置换如下：Px,f(y),B s1=Pz,f(w

10、),B Px,f(y),B s2=Px,f(A),B Px,f(y),B s3=Pq(z),f(A),B Px,f(y),B s4=Pc,f(A),B,谓词逻辑法,置换与合一置换（Substitution）置换是可结合的用s1s2表示两个置换s1和s2的合成，L表示一个表达式，则有（Ls1）s2=L（s1s2）即用s1和s2相继作用于表达式L是与用s1s2作用于L一样的进一步推广：（s1s2）s3=s1（s2s3）一般说来，置换是不可交换的，即 s1s2 s2s1,谓词逻辑法,置换与合一合一（Unification）合一的定义：寻找项对变量的置换，以使两表达式一致。如果一个置换s作用于表达式集

11、合Ei的每个元素，用Eis表示置换的集。称表达式Ei是可合一的，如果存在一个置换s使得：E1s=E2s=E3s=那么，称此s为Ei的合一者（unifier），因为s的作用是使集合Ei成为单一形式。,谓词逻辑法,置换与合一合一（Unification）例如，设有公式集 E=P(x,y,f(y),P(a,g(x),z)则下式是它的一个合一：s=a/x,g(a)/y,f(g(a)/z,谓词逻辑法,谓词逻辑法举例：猴子和香蕉问题描述状态的谓词：AT(x,y)：x在y处ONBOX：猴子在箱子上HB：猴子得到香蕉个体域：x：monkey,box,bananay：a,b,c问题的初始状态AT(monkey,

12、a)AT(box,b)ONBOX HB,问题的目标状态AT(monkey,c)AT(box,c)ONBOX HB,猴子和香蕉问题,描述操作的谓词 Goto(u,v)：猴子从u处走到v处 条件：ONBOX，AT(monkey,u)动作：删除表：AT(monkey,u)；添加表：AT(monkey,v)Pushbox(v,w)：猴子推着箱子从v处移到w处条件：ONBOX，AT(monkey,v)，AT(box,v)动作：删除表：AT(monkey,v)，AT(box,v)添加表：AT(monkey,w)，AT(box,w)Climbbox：猴子爬上箱子条件：ONBOX，AT(monkey,w)，A

13、T(box,w)动作：删除表：ONBOX；添加表：ONBOXGrasp：猴子摘取香蕉条件：ONBOX，AT(box,c)动作：删除表：HB；添加表：HB,猴子和香蕉问题,猴子和香蕉问题求解过程：,初始状态AT(monkey,a)AT(box,b)ONBOX HB,Goto(a,b),状态1AT(monkey,b)AT(box,b)ONBOX HB,Pushbox(b,c),状态2AT(monkey,c)AT(box,c)ONBOX HB,Climbbox,状态3AT(monkey,c)AT(box,c)ONBOX HB,目标状态AT(monkey,c)AT(box,c)ONBOX HB,Gra

14、sp,谓词逻辑法,主要优点自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解明确：有一种标准的知识解释方法，因此用这种方法表示的知识明确、易于理解精确：谓词逻辑的真值只有“真”与“假”，其表示、推理都是精确的灵活：知识和处理知识的程序是分开的，无须考虑处理知识的细节模块化：知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行,谓词逻辑法,主要缺点知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识知识库管理困难：缺乏知识的组织原则，知识库管理比较困难存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率,问题？,