《知识表示方法part2人工智能课件西电.ppt》由会员分享，可在线阅读，更多相关《知识表示方法part2人工智能课件西电.ppt（48页珍藏版）》请在三一办公上搜索。
1、Artificial Intelligence(AI)人工智能,主讲：戚玉涛,Email：,第二章：知识表示方法,内容提要,第二章：知识表示方法,1.状态空间法,2.问题归约法,3.谓词逻辑法,4.语义网络法,5.其他方法,问题归约法,问题归约（Problem Reduction）是另外一种基于状态空间的问题描述与求解方法已知问题的描述，通过一系列变换把此问题变为一个子问题集合这些子问题的解可以直接得到（本原问题），从而解决了初始问题,问题归约法,问题归约法的组成部分一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。(本原问题:不能再分解或变换且直接可解的子问题)问题归约的实
2、质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直到最后把初始问题归约为一个本原问题集合。,问题归约法,问题归约法举例：汉诺塔问题（Hanoi）从1移到3 每次移动一个盘子 大盘在下小盘在上,初始状态（111）,目标状态（333）,汉诺塔问题,原始问题可以归约为下列3个子问题：,子问题1：移动圆盘A和 B至柱子2（借助柱子3）,子问题2：移动圆盘C至柱子3,子问题3：把圆盘A和B移至柱子3（借助柱子1）,汉诺塔问题,归约过程（3个圆盘）,汉诺塔问题,汉诺塔问题归约图,本原问题,本原问题,与或图,问题归约法,与或图表示：用一个类似于图的结构来表示把问题归约为后继问题的替换集
3、合。,与图：把一个复杂问题分解为若干个较为简单的子问题，形成“与”树。或图：把原问题变换为若干个较为容易求解的新问题，形成“或”树。,问题归约法,与或图表示：,子问题替代集合结构图,与或图,问题归约法,一些关于与或图的术语,起始节点对应于原始问题描述,终叶节点对应于本原问题,问题归约法,与或图的构成规则1）与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题A。2）对应于本原问题的节点称为终叶节点，它没有后继节点。3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得的子问题集合。,问题归约法,与或图的构成规则
4、4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向次子问题集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。5）特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3）和规则4）所产生的图可以得到简化。,问题归约法,与或图的搜索：目的在于表明起始节点是有解的。可解节点终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解
5、时，此非终叶节点才是可解的。,问题归约法,不可解节点没有后裔的非终叶节点为不可解节点。如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。解树由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。解树中一定包含初始节点，它对应于原始问题。,问题归约法,t,t,t,t,t,t,t,t,t,有解节点,无解节点,终叶节点,与或图例子,原始问题有一个以上的解,原始问题有解,内容提要,第二章：知识表示方法,1.状态空间法,2.问题归约法,3.谓词
6、逻辑法,4.语义网络法,5.其他方法,谓词逻辑法,命题逻辑与谓词逻辑命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的证明发挥了重要作用虽然命题逻辑能够把客观世界的各种事实表示为逻辑命题，但是它具有较大的局限性。命题逻辑只能进行命题间关系的推理，无法解决与命题结构和成分有关的推理问题，不适合表示比较复杂的问题。谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。,谓词逻辑法,命题命题是具有真假意义的语句命题代表人们进行思维时的一种判断，若命题的意义为真，称它的真值为“真”，记作“T”；若命题的意义为假，称它的真值为“假”，记作“F”
7、。例如：“西安是陕西省省会”“10大于6”是真值为“T”的命题“月亮是方的”“煤炭是白的”是真值为“F”的命题一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一种条件下为假。例如：“1+1=10”在二进制情况下为真，十进制情况下为假,谓词逻辑法,命题没有真假意义的语句，如感叹句、疑问句等，不是命题。通常用大写英文字母表示一个命题，例如：P：西安是座古老的城市命题逻辑的局限性？客观事物的结构及逻辑特征？不同事物间的共同特征？,谓词逻辑法,命题逻辑的局限性？命题这种表示方法无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来例如，用字母P表示“小张是老张
8、的儿子”这一命题，则无法表述出老张与小张是父子关系又如，“张三是学生”，“李四是学生”这两个命题，用命题逻辑表示时，无法把两者的共同特征“都是学生”形式的表示出来可否用 Student（“张三”），Student（“李四”）表示上述命题？谓词逻辑,谓词逻辑法,谓词在谓词逻辑中，命题是用形如P(x1,x2,xn)的谓词来表述的。一个谓词可分为谓词名与个体两个部分个体：是命题的主语，表示独立存在的事物或某个抽象的概念“x1,x2,xn”是个体，一般用小写字母表示 个体可以是个体常量、变元或函数谓词名：表示个体的性质、状态或个体之间的关系“P”是谓词名，一般用大写字母表示 称P 是一个n元谓词。,谓
9、词逻辑法,谓词对于命题“张三是学生”，用谓词可以表示为：Student（“张三”）。其中，Student是谓词名，“张三”是个体，Student刻画了“张三”是个学生这一特征。在谓词中，个体可以是常量，也可以是变元，还可以是一个函数。例如，对于命题“x10”可以表示为more（x,10），其中x是变元。又如，命题“小张的父亲是老师”，可以表示为Teacher（father（Zhang），其中，father（Zhang）是一个函数。当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值“T”或“F”。,谓词逻辑法,谓词在n元谓词 P(x1,x2,xn)中，若每个个体均为常量、变元或函数，则
10、称它为一阶谓词。如果某个个体本身又是一个一阶谓词，则称它为二阶谓词，如此类推。个体变元的取值范围称为个体域。个体域可以是有限的，也可以是无限的。例如用I（x）表示“x是整数”，则个体域为所有整数，是无限的。谓词与函数不同，谓词的真值是”T“或”F“，而函数的值是个体域中的一个个体，无真值可言。,谓词逻辑法,谓词演算谓词逻辑语言的语法和语义基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号原子公式：原子公式由若干谓词符号和项组成谓词符号规定定义域内的一个相应关系常量符号是最简单的项，表示论域内的物体或实体变量符号也是项，不明确涉及是哪一个实体函数符号表示论域内的函数，是从论域内的一个实
11、体到另外一个实体的映射例如：原子公式 Married father(LI),mother(LI)表示“李（LI）的父亲和他的母亲结婚”,谓词逻辑法,连词和量词连词合取：符号“”，表示所连结的两个命题之间具有“与”的关系。析取：符号“”，表示所连结的两个命题之间具有“或”的关系蕴涵：符号“”，表示“若则”的语义。PQ读作“如果P，则Q”其中，P称为条件的前件，Q称为条件的后件。非：符号“”，表示对其后面的命题的否定双条件：符号“”，表示“当且仅当”的语义。PQ读作“P当且仅当Q”。,谓词逻辑法,量词全称量词：符号“”，意思是“所有的”、“任一个”x读作“对一切x”,或“对每一x”，或“对任一x”
12、。命题(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)为假,谓词逻辑法,谓词公式原子谓词公式：是由谓词符号和若干项组成的谓词演算。分子谓词公式：可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。合式公式（WFF，Well-formed Formulas）：通常把
13、合式公式叫做谓词公式，递归定义如下：(1)原子谓词公式是合式公式(2)若A为合式公式，则 A也是一个合式公式(3)若A,B是合式公式，则AB，AB，AB，AB也都是合式公式(4)若A是合式公式，x为A中的自由变元，则(x)A和(x)A都是合式公式(5)只有按上述规则(1)至(4)求得的那些公式，才是合式公式。,谓词逻辑法,谓词公式用谓词公式表示知识时，需要首先定义谓词，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。例1：设有下列知识刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程。任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词：FAM
14、OUS(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,programing)任何整数或者为正或者为负:(x)(I(x)(P(x)N(x),谓词逻辑法,谓词公式例2：用谓词逻辑描述右图中的房子的概念个体：A,B谓词：SUPPORT(x,y)：表示 x 被
15、y支撑着 WEDRE(x)：表示 x 是楔形块 BRICK(y)：表示 y 是长方块 其中 x,y是个体变元，它们的个体域A,B房子的概念可以表示成一组合式谓词公式的合取式：SUPPORT(A,B)WEDGE(A)BRICK(B),谓词逻辑法,合式公式的性质若P、Q是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出。,谓词逻辑法,合式公式的性质如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是等价的。应用上述真值表可以确立下列等价关系：（1）否定之否定：(P)=P（2）(P Q)=(P Q)，或者(P Q)=(P Q）（3）狄 摩根定律：(P Q
16、)=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)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)
17、(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是互不相同的变元ti/xi表示用ti项替换变元xi，不允许ti和xi相同，也不允许变元xi循环地出现在另一个tj中,谓词逻辑法,置换与合一置换（Substitution）例如a/x,f(b)/y，w/
18、z 是一个置换g(y)/x,f(x)/y 不是一个置换g(a)/x,f(x)/y 不是一个置换,谓词逻辑法,置换与合一置换（Substitution）例2.2（P40），表达式 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),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,谓词逻辑法,置换与合一置换（
19、Substitution）置换是可结合的用s1s2表示两个置换s1和s2的合成，L表示一个表达式，则有（Ls1）s2=L（s1s2）即用s1和s2相继作用于表达式L是与用s1s2作用于L一样的进一步推广：（s1s2）s3=s1（s2s3）一般说来，置换是不可交换的，即 s1s2 s2s1,谓词逻辑法,置换与合一合一（Unification）合一的定义：寻找项对变量的置换，以使两表达式一致。如果一个置换s作用于表达式集合Ei的每个元素，用Eis表示置换的集。称表达式Ei是可合一的，如果存在一个置换s使得：E1s=E2s=E3s=那么，称此s为Ei的合一者（unifier），因为s的作用是使集合E
20、i成为单一形式。例如，设有公式集 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,a)AT(box,b)ONBOX HB,问题的目标状态AT(monkey,c)AT(box,c)ONBOX HB,猴子和香蕉问题,描述操作的谓词 Goto(u,v)：猴子从u处走到v处 条件：ONBOX，AT(monkey,u)动作：
21、删除表：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)，AT(box,w)动作：删除表：ONBOX；添加表：ONBOXGrasp：猴子摘取香蕉条件：ONBOX，AT(box,c)动作：删除表：HB；添加表：HB,猴子和香蕉问题,猴子和香蕉问题求解过程：,初始状态AT(monkey,a)AT(
22、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,Grasp,谓词逻辑法,主要优点自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解明确：有一种标准的知识解释方法，因此用这种方法表示的知识明确、易于理解精确：谓词逻辑的真值只有“真”与“假”，其表
23、示、推理都是精确的灵活：知识和处理知识的程序是分开的，无须考虑处理知识的细节模块化：知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行,谓词逻辑法,主要缺点知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识知识库管理困难：缺乏知识的组织原则，知识库管理比较困难存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率,内容提要,第二章：知识表示方法,1.状态空间法,2.问题归约法,3.谓词逻辑法,4.语义网络法,5.其他方法,问题？,
