人工智能及其应用_知识表示113

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第二章 知识表示,本章主要讨论知识表示问题，介绍7种知识表示方法：状态空间法、问题归约法、谓词演算法、语义网络法、框架表示、本体技术、过程表示。掌握状态空间法、问题归约法、谓词演算法、语义网络法的要点及其之间的关系，了解框架表示、本体技术、过程表示。,知识表,示,示的基,本,本概念,知识表,示,示：研究,用,用机器,表,表示知,识,识的可,行,行性、,有,有效性,的,的一般,方,方法，,是,是一种,数,数据结,构,构与控,制,制结构,的,的统一,体,体，既,考,考虑知,识,识的存,储,储又考,虑,虑知识,的,的使用,。,。,知识表,示,示可看,成,成是一,组,组描述,事,事物的,约,约定，,以,以把人,类,类知识,表,表示成,机,机器能,处,处理的,数,数据结,构,构。,人工智,能,能系统,所,所关心,的,的知识,事实有关问,题,题环境,的,的一些,事,事物的,知,知识，,常,常以“是”的形式,出,出现。,如,如事物,的,的分类,、,、属性,、,、事物,间,间关系,、,、科学,事,事实、,客,客观事,实,实等。,如,如雪是,白,白色的,、,、鸟有,翅,翅膀、,张,张三李,四,四是好,朋,朋友、,这,这辆车,是,是张三,的,的。,规则有关问,题,题中与,事,事物的,行,行动、,动,动作相,联,联系的,因,因果关,系,系知识,，,，是动,态,态的，,常,常以“,如,如果那么”形式出,现,现。,控制有关问,题,题的求,解,解步骤,、,、技巧,性,性知识,，,，告诉,怎,怎么做,一,一件事,。,。,元知识有关知,识,识的知,识,识，是,知,知识库,中,中的高,层,层知识,。,。包括,怎,怎样使,用,用规则,、,、解释,规,规则、,校,校验规,则,则、解,释,释程序,结,结构等,知,知识。,2.1,状,状态,空,空间法,问题求,解,解,问题求,解,解(problemsolving)是个大,课,课题，,它,它涉及,归,归约、,推,推断、,决,决策、,规,规划、,常,常识推,理,理、定,理,理证明,和,和相关,过,过程的,核,核心概,念,念。,在分析,了,了人工,智,智能研,究,究中运,用,用的问,题,题求解,方,方法之,后,后，就,会,会发现,许,许多问,题,题求解,方,方法是,采,采用试,探,探搜索,方,方法的,。,。也就,是,是说，,这,这些方,法,法是通,过,过在某,个,个可能,的,的解空,间,间内寻,找,找一个,解,解来求,解,解问题,的,的。,状态空,间,间法：基于,解,解答空,间,间的问,题,题表示,和,和求解,方,方法，,它,它是以,状,状态和,算,算符(operator,),)为基础,来,来表示,和,和求解,问,问题的,。,。,2.1,状,状态,空,空间法,1.问,题,题求解,技,技术两,个,个主要,的,的方面,(1)问题的,表,表示：,如,如果描,述,述方法,不,不对，,对,对问题,求,求解会,带,带来很,大,大的困,难,难；,(2)求解的,方,方法：,采,采用试,探,探搜索,方,方法。,2.状,态,态空间,法,法三要,点,点,(1)状态（state）,(2)算符（operator）,(3)状态空,间,间方法,2.1,状,状态,空,空间法,2.1,.,.1,问,问题状,态,态描述,1.定,义,义,状态(state,),)：为描,述,述某类,不,不同事,物,物间的,差,差别而,引,引入的,一,一组最,少,少变量q0，q1，qn的有序,集,集合，,其,其矢量,形,形式如,下,下：,Q=q0,q1,qnT,式中每,个,个元素qi(i=0,1,n,),)为集合,的,的分量,称为状,态,态变量,给定每,个,个分量,的,的一,组值就,得,得到一,个,个具体,的,的状态,如,Qk=q0k,q1k,qnkT,式中每,个,个元素qi(i=0,1，n)为集合,的,的分量,，,，称为,状,状态变,量,量。,算符：使问,题,题从一,种,种状态,变,变化为,另,另一种,状,状态的,手,手段称,为,为操作,符,符或算,符,符。操,作符可,为,为走步,、,、过程,、,、规则,、,、数学,算,算子、,运,运算符,号,号或逻,辑,辑符号,等,等。,问题的,状,状态空,间,间(statespace,),)：是一,个,个表示,该,该问题,全,全部可,能,能状态,及,及其关,系,系,的图，,它,它包含,三,三种说,明,明的集,合,合，即,所,所有可,能,能的问,题,题初始,状,状态集,合,合S、操作,符,符,集合F以及目,标,标状态,集,集合G。可把,状,状态空,间,间记为,三,三元状,态,态(S，F，G)。,2.1,状,状态,空,空间法,2.状,态,态空间,表,表示详,释,释,让我们,先,先用数,码,码难题(puzzle problem,),)来说明,状,状态空,间,间表示,的,的概念,。,。由15个编有1至15并放在44方格棋,盘,盘上的,可,可走动,的,的棋子,组,组成。,棋,棋盘上,总,总有一,格,格是空,的,的，以,便,便可能,让,让空格,周,周围的,棋,棋子走,进,进空格,，,，这也,可,可以理,解,解为移,动,动空格,。,。图中,绘,绘出了,两,两种棋,局,局，即,初,初始棋,局,局和目,标,标棋局,，,，它们,对,对应于,该,该下棋,问,问题的,初,初始状,态,态和目,标,标状态,。,。如何把,初,初始棋,局,局变换,为,为目标,棋,棋局呢,？,？问题,的,的解答,就,就是某,个,个合适,的,的棋子,走,走步序,列,列，如左移棋,子,子12，下移,棋,棋子15，右移,棋,棋子4，等等。,2.1,状,状态,空,空间法,2.状,态,态空间,表,表示详,释,释,状态空,间,间法：,从,从某个,初,初始状,态,态开始,，,，每次,加,加一个,操,操作符,，,，递增,的,的建立,起,起操作,符,符的试,验,验序列,，,，直到,达,达到目,标,标状态,为,为止。,寻找状,态,态空间,的,的全部,过,过程包,括,括从旧,的,的状态,描,描述产,生,生新的,状,状态描,述,述，以,及,及此后,检,检验这,些,些新的,状,状态描,述,述，看,是,是否达,到,到了该,目,目标状,态,态。对,于,于最优,化,化问题,找,找到任,一,一目标,状,状态是,不,不够的,，,，必须,按,按某个,准,准则实,现,现最优,化,化路径,。,。P26,完成目,标,标状态,的,的三件,事,事：,状态,描,描述方,式,式，特,别,别是初,始,始状态,描,描述；,操作,符,符集合,及,及其对,状,状态描,述,述的作,用,用；,目标,状,状态的,特,特性。,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法,为了对状,态,态空间,图,图有更,深,深入的,了,了解，,这,这里介,绍,绍一下,图,图论中,的,的几个,术,术语和,图,图的正,式,式表示,法,法。1.图,论,论中的,几,几个术,语,语节点(node),：,：图形上,的,的汇合,点,点，用,来,来表示,状,状态、,事,事件和,时,时间关,系,系的汇,合,合，也,可,可用来,指,指示通,路,路的汇,合,合；,弧线(arc)：节点间,的,的连接,线,线；,有向图(directedgraph,),)：一对节,点,点用弧,线,线连接,起,起来，,从,从一个,节,节点指,向,向另一,个,个节点,。,。,后继节,点,点(descendantnode)与父辈节,点,点(parent node,),)：如果,某,某条弧,线,线从节,点,点ni指向节,点,点nj，那么,节,节点nj就叫做,节,节点ni的后继,节,节点或,后,后裔，,而,而节点ni叫做节,点,点nj的父辈,节,节点或,祖,祖先。,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法,1.图,论,论中的,几,几个术,语,语路径：某个,节,节点序,列,列(ni1,ni2,nik)当j=2，3，k时，如,果,果对于,每,每一个ni，j-1都有一,个,个后继,节,节点nij存在，,那,那么就,把,把这个,节,节点序,列,列叫做,从,从节点ni1至节点nik的长度,为,为k的路径,。,。,代价：用c(ni,nj)来表示,从,从节点ni指向节,点,点nj的那段,弧,弧线的,代,代价。,两,两节点,间,间路径,的,的代价,等,等于连,接,接该路,径,径上各,节,节点的,所,所有弧,线,线代价,之,之和。,显式表,示,示：各节,点,点及其,具,具有代,价,价的弧,线,线由一,张,张表明,确,确给出,。,。此表,可,可能列,出,出该图,中,中的每,一,一节点,、,、它的,后,后继节,点,点以及,连,连接弧,线,线的代,价,价。,隐式表,示,示：节点,的,的无限,集,集合si作为起,始,始节点,是,是已知,的,的。后,继,继节点,算,算符也是已,知,知的，,它,它能作,用,用于任,一,一节点,以,以产生,该,该节点,的,的全部,后,后继节,点,点和各,连,连接弧,线,线的代,价,价。,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法,2.图的显,式,式和隐,式,式表示一个图,可,可由显,式,式说明,也,也可由,隐,隐式说,明,明。显,然,然，显,式,式说明,对,对于大,型,型的图,是,是不切,实,实际的,，,，而对,于,于具有,无,无限节,点,点集合,的,的图则,是,是不可,能,能的。此外，,引,引入后,继,继节点,算,算符的,概,概念是,方,方便的,。,。后继,节,节点算,符,符也是已,知,知的，,它,它能作,用,用于任,一,一节点,以,以产生,该,该节点,的,的全部,后,后继节,点,点和各,连,连接弧,线,线的代,价,价把后,继,继算符,应,应用于si,的成员,和,和它们,的,的后继,节,节点以,及,及这些,后,后继节,点,点的后,继,继节点,，,，如此,无,无限制,地,地进行,下,下去，,最,最后使,得,得由和si,所规定,的,的隐式,图,图变为,显,显示图,。,。,问题的,表,表示对,求,求解工,作,作量有,很,很大的,影,影响。,人,人们显,然,然希望,有,有较小,的,的状态,空,空间表,示,示。许,多,多似乎,很,很难的,问,问题，,当,当表示,适,适当时,就,就可能,具,具有小,而,而简单,的,的状态,空,空间。,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法,根据问,题,题状态,、,、操作,符,符和目,标,标条件,选,选择各,种,种表示,，,，是高,效,效率问,题,题求解,必,必须的,。,。,各种问,题,题都可,以,以用状,态,态空间,加,加以表,示,示，并,用,用状态,空,空间搜,索,索法来,求,求解。,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法,1.产生式,系,系统（Production System）,一个总,数,数据库(global database)：它含,有,有与具,体,体任务,有,有关的,信,信息；,随,随着应,用,用情况,的,的不同,，,，这些,数,数据库,可,可能小,得,得像数,字,字矩阵,那,那样简,单,单，或,许,许大得,如,如检索,文,文件结,构,构那么,复,复杂。,一套规,则,则：它对,数,数据库,进,进行操,作,作运算,。,。每条,规,规则由,左,左右两,部,部分组,成,成，左,部,部鉴别,规,规则的,适,适用性,或,或先决,条,条件，,右,右部描,述,述规则,应,应用时,所,所完成,的,的动作,。,。用规,则,则来改,变,变数据,库,库就象,用,用算符,来,来改变,状,状态一,样,样。,一个控,制,制策略：它确,定,定应该,采,采用哪,一,一条适,用,用规则,，,，而且,当,当数据,库,库的终,止,止条件,满,满足时,，,，就停,止,止计算,。,。控制,策,策略由,控,控制系,统,统选择,和,和确定,。,。,推销员,旅,旅行问,题,题,总数据,库,库：到,目,目前为,止,止所访,问,问的城,市,市；,规则对,应,应于决,策,策：即,下,下一步,走,走向城,市,市，,下,下一步,走,走向城,市,市，下一,步,步走向,城,城市,，,，一条,规,规则必,须,须能把,某,某个数,据,据库变,为,为一个,合,合法数,据,据库，,否,否则不,适,适应这,个,个数据,库,库；,任一以,为起,点,点和终,点,点，并,出,出现所,有,有其它,城,城市的,总,总数据,库,库，都,满,满足终,止,止条件,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法2.状态空,间,间表示,举,举例例2猴子和,香,香蕉问,题,题(monkey andbananaproblem)在一个,房,房间内,有,有一只,猴,猴子(可把这,只,只猴子,看,看做一,个,个机器,人,人)、一个,箱,箱子和,一,一束香,蕉,蕉。香,蕉,蕉挂在,天,天花板,下,下方，,但,但猴子,的,的高度,不,不足以,碰,碰到它,。,。那么,这,这只猴,子,子怎样,才,才能摘,到,到香蕉,呢,呢?图2.4表示出,猴,猴子、,香,香蕉和,箱,箱子在,房,房间内,的,的相对,位,位置。,猴子和,香,香蕉.用一个,四,四元表,列,列(W,X,Y,Z)来表示,这,这个问,题,题,的状态,，,，其中W猴子,的,的水平,位,位置X当猴,子,子在箱,子,子顶上,时,时取X=1；否则,取,取X=0Y箱子,的,的水平,位,位置Z当猴,子,子摘到,香,香蕉时,取,取Z=1；否则,取,取Z=0,图2.4猴子和,香,香蕉问,题,题,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法,这个问,题,题中的,操,操作(算符)如下：(1)goto(U)猴子走,到,到水平,位,位置U，或者,用,用产生,式,式规则,表,表示为,：,：,(W，0，Y，z)(U，0，Y，z),(,(2.3,),),即应用,操,操作goto(U,),)，能把,状,状态(W，0，Y，z)变换为,状,状态(U，0，Y，z)。,(2)pushbox(V)猴子把,箱,箱子推,到,到水平,位,位置V，即有,(W，0，W，z)(V，0，V，z),(,(2.4),应当注,意,意的是,，,，要应,用,用算符pushbox(V,),)，就要求,产,产生式,规,规则的,左,左边，,猴,猴子与,箱,箱子必,须,须在同,一,一位置,上,上，并,且,且，猴,子,子不是,在,在箱子,顶,顶上。,这,这种强,加,加于操,作,作的适,用,用性条,件,件，叫,做,做产生,式,式规则,的,的先决,条,条件。,2.1,状,状态,空,空间法,2.1,.,.2,状,状态图,示,示法,这个问,题,题中的,操,操作(算符)如下：(3)climbbox猴子爬,上,上箱顶,，,，即有,(W，0，W，z)(W，1，W，z),(,(2.5,),)在应用,算,算符climbbox时也必,须,须注意,到,到，猴,子,子和箱,子,子应当,在,在同一,位,位置上,，,，而且,猴,猴子不,在,在箱顶,上,上 。,(4)grasp猴子摘,到,到香蕉,，,，即有,(c,1,c,0)(c,1,c,1),(,(2.6)其中，c是香蕉,正,正下方,的,的地板,位,位置，,在,在应用,算,算符grasp时，要,求,求猴子,和,和箱子,都,都在位,置,置c上，并,且,且猴子,已,已在箱,子,子顶上,。,2.1,状,状态,空,空间法,对于规,则,则(2)，只有,当,当算符pushbox(V,),),的先决,条,条件，,即,即猴子,与,与箱子,在,在同一,位,位,置上而,且,且猴子,不,不在箱,顶,顶上这,些,些条件,得,得,到满足,时,时，算,符,符pushbox(V,),)才是适,用,用,的。这,一,一操作,算,算符的,作,作用是,猴,猴子把,箱,箱,子推到,位,位置V。在这,一,一表示,中,中，目,标,标,状态的,集,集合可,由,由任何,最,最后元,素,素为1的,表列来,描,描述。,令,令初始,状,状态为(a,0,b,0)这时，goto(U,),)是唯一,适,适用的,操,操作，,并导致,下,下一状,态,态(U,0,b,0)。现在,有,有3,个适用,的,的操作,，,，即goto(U,),)，,pushbox(V,),)和climbbox(若U=b,),)。,猴子和,香,香蕉问,题,题的状,态,态空间,图,图,2.2,问,问题,归,归约法,2.2,.,.1,问,问题归,约,约描述,先把问,题,题分解,为,为子问,题,题和子-子问题,，,，然后,解,解决较,小,小的问,题,题。对,该,该问题,的,的某个,具,具体子,集,集的解,答,答就意,味,味着对,原,原始问,题,题的一,个,个解答,。,。问题,归,归约表,示,示的组,成,成部分,：,：,一个初,始,始问题,描,描述；,一套把,问,问题变,换,换为子,问,问题的,操,操作符,；,；,一套本,原,原问题,描,描述。,问题归,约,约的实,质,质：从,目,目标(要解决,的,的问题)出发逆,向,向推理,，,，建立,子,子问题,以,以及子,问,问题的,子,子问题,，,，直至,最,最后把,初,初始问,题,题归约,为,为一个,平,平凡的,本,本原问,题,题集合,。,。,2.2,问,问题,归,归约法,2.2,.,.1,问,问题归,约,约描述,梵塔,难,难题,有3个柱子(1，2和3)和3个不同,尺,尺寸的,圆,圆盘（A，B和C）。在,每,每个圆,盘,盘的中,心,心有一,个,个孔，,所,所以圆,盘,盘可以,堆,堆叠在,柱,柱子上,。,。最初,，,，3个圆盘,都,都堆在,柱,柱子1上：最,大,大的圆,盘,盘C在底部,，,，最小,的,的圆盘A在顶部,。,。要求,把,把所有,圆,圆盘都,移,移到柱,子,子3上，每,次,次只许,移,移动一,个,个，而,且,且只能,先,先搬动,柱,柱子顶,部,部的圆,盘,盘，还,不,不许把,尺,尺寸较,大,大的圆,盘,盘堆放,在,在尺寸,较,较小的,圆,圆盘上,。,。这个,问,问题的,初,初始配,置,置和目,标,标配置,如,如图2.6所示。,2.2,问,问题,归,归约法,解题过,程,程：,将原始,问,问题归,约,约为一,个,个较简,单,单问题,集,集合，,要,要把所,有,有圆盘,都,都移至,柱,柱子3，我们,必,必须首,先,先把圆,盘,盘C移至柱,子,子3；而且,在,在移动,圆,圆盘C至柱子3之前，,要,要求柱,子,子3必须是,空,空的。,只,只有在,移,移开圆,盘,盘A和B之后，,才,才能移,动,动圆盘C；而且,圆,圆盘A和B最好不,要,要移至,柱,柱子3，否则,就,就不能,把,把圆盘C移至柱,子,子3。因此,，,，首先,应,应该把,圆,圆盘A和B移到柱,子,子2上。然,后,后才能,够,够进行,关,关键的,一,一步，,把,把圆盘C从柱子1移至柱,子,子3，并继,续,续解决,难,难题的,其,其余部,分,分。,将原始,难,难题归,约,约（简,化,化）为,下,下列子,难,难题：,移,移动圆,盘,盘A和B至柱子2的双圆,盘,盘难题,，,，如图(a)所示。,2.2,问,问题,归,归约法,图 2,.,.7,梵,梵塔问,题,题解答,(,(a),图 2,.,.8,梵,梵塔问,题,题解答,(,(b),图 2,.,.9,梵,梵塔问,题,题解答,(,(c),2.2,问,问题,归,归约法,梵塔问,题,题归约,图,图：子,问,问题2可作为,本,本原问,题,题考虑,，,，因为,它,它的解,只,只包含,一,一步移,动,动。应,用,用一系,列,列相似,的,的推理,，,，子问,题,题1和子问,题,题3也可被,归,归约为,本,本原问,题,题，如,图,图2.10所示。,这,这种图,式,式结构,，,，叫做,与,与或图(AND/OR graph)。它能有,效,效地说,明,明如何,由,由问题,归,归约法,求,求得问,题,题的解,答,答。,梵塔问,题,题归约,图,图,2.2,问,问题,归,归约法,2.2,.,.1,问,问题归,约,约描述,问题归,约,约描述,问题归,约,约方法,应,应用算,符,符把问,题,题描述,变,变换为,子,子问题,描,描述，,问,问题描,述,述可以,用,用多种,数,数据结,构,构形式,，,，包括,表,表列、,树,树、字,符,符串、,矢,矢量、,数,数组等,。,。梵塔,问,问题采,用,用包含,两,两个数,列,列的表,列,列来描,述,述,(113,),),（333,),)表示把,配,配置（113）变换,为,为配置,（,（333）。,用状态,空,空间表,示,示的三,元,元组合,（,（S，F，G）来规,定,定与描,述,述问题,，,，有关,子,子问题,可,可以当,作,作状态,空,空间中,的,的两个,一,一定的,“,“脚踏,石,石”之,间,间寻找,路,路径来,辨,辨别。,梵,梵塔问,题,题中的,子,子问题（111）=（122），（122）=（322），（322）=（333），规定,了,了最后,的,的路径,将,将要通,过,过“脚,踏,踏石”,状,状态（122）和（322）。,2.2,问,问题,归,归约法,2.2,.,.2,与,与或图,表,表示,与图、,或,或图、,与,与或图,：,：一般地,，,，我们,用,用一个,类,类似图,的,的结构,来,来表示,把,把问题,归,归约为,后,后继问,题,题的替,换,换集合,，,，这种,结,结构图,叫,叫做问,题,题归约,图,图，或,叫,叫与或,图,图。如,下,下图所,示,示:,（引入,附,附加节,点,点使含,有,有一个,以,以上后,继,继问题,的,的每个,集,集合能,够,够聚集,在,在它们,各,各自的,父,父辈节,点,点之下,。,。）,子问题,替,替换集,合,合结构,图,图,与或图,2.2,问,问题,归,归约法,2.2,.,.2,问,问题归,约,约描述,一些关,于,于与或,图,图的术,语,语：,终叶节,点,点：对应于,原,原问题,的,的本原,节,节点。,或节点：只要解,决,决某个,问,问题就,可,可解决,其,其父辈,问,问题的,节,节点集,合,合，如,（,（M，N，H）。,与节点：只有解,决,决所有,子,子问题,，,，才能,解,解决其,父,父辈问,题,题的节,点,点集合,，,，如（B,C,),)和（D,E,F）各个,结,结点之,间,间用一,端,端小圆,弧,弧连接,标,标记。,2.2,问,问题,归,归约法,2.2,.,.2,问,问题归,约,约描述,与或图：由与节,点,点及或,节,节点组,成,成的结,构,构图。,可解节,点,点的一,般,般定义,：,：,(1)终叶节,点,点是可,解,解节点(因为它,们与本,原,原问题,相,相关连)。,(2)如果某,个,个非终,叶,叶节点,含,含有或,后,后,继节点,，,，那么,只,只要当,其,其后继,节,节点,至少有,一,一个是,可,可解的,时,时，此,非,非终,叶节点,才,才是可,解,解的。,(3)如果某,个,个非终,叶,叶节点,含,含有与,后继节,点,点，那,么,么只有,当,当其后,继,继节,点全部,为,为可解,时,时，此,非,非终叶,节,节点,才是可,解,解的。,图 2,.,.15,与,与或,图,图例子,2.2,问,问题,归,归约法,2.2,.,.2问题归,约,约描述,不可解,节,节点的,一,一般定,义,义:,(1)没有后,裔,裔的非,终,终叶节,点,点为不,可,可解节,点,点。,(2)如果某,个,个非终,叶,叶节点,含,含有或,后,后继节,点,点，那,么,么只有,当,当其全,部,部后裔,为,为不可,解,解时，,此,此非终,叶,叶节点,才,才是不,可,可解的,。,。,(3)如果某,个,个非终,叶,叶节点,含,含有与,后,后继节,点,点，那,么,么只要,当,当其后,裔,裔至少,有,有一个,为,为不可,解,解时，,此,此非终,叶,叶节点,才,才是不,可,可解的,。,。,2.2,问,问题,归,归约法,2.2,.,.2,问,问题归,约,约描述,与或图,构,构成规,则,则(1)与或图,中,中的每,个,个节点,代,代表一,个,个要解,决,决的单,一,一问题,或,或问题,集,集合。,图,图中所,含,含起始,节,节点对,应,应于原,始,始问题,。,。,(2)对应于,本,本原问,题,题的节,点,点，叫,做,做终叶,节,节点，,它,它没有,后,后裔。,(3)对于把,算,算符应,用,用于问,题,题A的每种,可,可能情,况,况，都,把,把问题,变,变换为,一,一个子,问,问题集,合,合；有,向,向弧线,自,自A指向后,继,继节点,表,表示所,求,求得的,子,子,问题集,合,合，如,下,下图所,示,示，把,问,问题A归约为3个不同,的子问,题,题集合N，M，H(或节点)。,图 2,.,.16,与,与或,树,树,2.2,问,问题,归,归约法,2.2,.,.2,问,问题归,约,约描述,与或图,构,构成规,则,则,(4)一般对,于,于代表,两,两个或,两,两个以,上,上子问,题,题集合,的,的每个,节,节点，,有,有向弧,线,线从此,节,节点指,向,向此子,问,问题集,合,合中的,各,各个节,点,点。由,于,于只有,当,当集合,中,中所有,的,的项都,有,有解时,，,，这个,子,子问题,的,的集合,才,才能获,得,得解答,，,，所以,这,这些子,问,问题节,点,点叫做,与,与节点,。,。,(5)在特殊,情,情况下,，,，当只,有,有一个,算,算符可,应,应用于,问,问题A，而且,这,这个算,符,符产生,具,具有一,个,个以上,子,子问题,的,的某个,集,集合时,，,，由上,述,述规则,3和规则4所产生,的,的图可,以,以得到,简,简化。,因此，,代,代表子,问,问题集,合,合的中,间,间或节,点可以,被,被略去,，,，如右,图,图所示,。,。,图 2,.,.16,与,与或,树,树,2.3谓词逻,辑,辑法,2.3,.,.1,谓,谓词演,算,算（PredicateCalculus）1.语,法,法和语,义,义(Syntax,&,& Semantics)谓词逻,辑,辑的基,本,本组成,部,部分：,谓,谓词符,号,号、变,量,量符号,、,、函数,符,符号和,常,常量符,号,号，并,用,用圆括,号,号、方,括,括号、,花,花括号,和,和逗号,隔,隔开，,表,表示论,域,域内的,关,关系。,原子公,式,式(atomic formulas)由若干,谓,谓词符,号,号和项,组,组成的,谓,谓词演,算,算。原,子,子公式,是,是谓词,演,演算基,本,本积木,块,块。,例如，,要,要表示,机器,人,人(ROBOT,),)在号,房,房间(r1,),)内，,如,如图2.19所示，,可,可以应,用,用原子,公,公式:,2.3谓词逻,辑,辑法,2.3,.,.1,谓,谓词演,算,算（PredicateCalculus）1.语,法,法和语,义,义(Syntax,&,& Semantics)当机器,人,人ROBOT,移,移到房,间,间r2,时,时，原,子,子公式,可,可以表,示,示为：,INROOM,(,(ROBOT,r2),这两个,原,原子公,式,式的通,用,用形式,就,就是,又如,“,“李的,母,母亲和,他,他的父,亲,亲结婚,”,”这句,话,话的原,子,子公式,表,表示,如下：,2.3谓词逻,辑,辑法,2.3,.,.1谓词演,算,算（PredicateCalculus）2.连词和,量,量词(Connective,&,& Quantifiers),(1)连词与合取（conjunction）合,取,取就是,用,用连词,把几,个,个公式,连,连接起,来,来而构,成,成的公,式,式。合,取,取项是,合,合取式,的,的每个,组,组成部,分,分。,例：LIKE(I，MUSIC),LIKE(I，PAINTING),(我喜爱,音,音乐和,绘,绘画。),2.3谓词逻,辑,辑法,2.3,.,.1谓词演,算,算（PredicateCalculus）2.连词和,量,量词(Connective,&,& Quantifiers),或析取（disjunction） 析,取,取就是,用,用连词,把几,个,个公式,连,连接起,来,来而构,成,成的公,式,式。析,取,取项是,析,析取式,的,的每个,组,组成部,分,分。,例：PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL),(李力打,篮,篮球或,踢,踢足球,。,。),2.3谓词逻,辑,辑法,2.3,.,.1,谓,谓词演,算,算（PredicateCalculus）2.连,词,词和量,词,词(Connective,&,&Quantifiers),(1)连词蕴涵=,表示如果-那么的语句,。,。用连,词,词=连接两,个,个公式,所,所构成,的,的公式,叫,叫做蕴,涵,涵。,IF=THEN,前项,后,后项,(左式)(右式),例：RUNS(LIUHUA，FASTEST),=,=TWINS(LIUHUA，CHAMPION),(如果刘,华,华跑得,最,最快，,那,那么他,取,取得冠,军,军),非（NOT） 表,示,示否定,，,，、,均可,表,表示否,定,定。,例：INROOM,(,(ROBOT，r2),(机器人,不,不在2号房间,内,内。),2.3谓词逻,辑,辑法,2.3,.,.1谓词演,算,算（PredicateCalculus）2.连词和,量,量词(Connective,&,& Quantifiers),(2)量词全称量,词,词(Universal Quantifier,),)若一个,原,原子公,式,式P(x,),)，对于,所,所有可,能,能变量x都具有T值，则,用,用(x)P,(,(x)表示。,例：(x)ROBOT(x),=,=COLOR(x,GRAY,),),(所有的,机,机器人,都,都是灰,色,色的）,(x)Student(x,),) =, Uniform,(,(x,Color),(所有学,生,生都穿,彩,彩色制,服,服),2.3谓词逻,辑,辑法,2.3,.,.1谓词演,算,算（PredicateCalculus）2.连词和,量,量词(Connective,&,& Quantifiers),(2)量词,存在量,词,词(ExistentialQuantifier)若一个,原,原子公,式,式P(x,),)，至少,有,有一个,变,变元X，可使P(X,),)为T值，则,用,用(x)P,(,(x)表示。,例：(x)INROOM(x,r1),(1号房间,内,内有个,物,物体),量化变,元,元(QuantifiedVariables,),)被量化,了,了的变,元,元x-约束变,量,量。,2.3谓词逻,辑,辑法,2.3,.,.2,谓,谓词公,式,式（PredicateFormulas）,1.谓词公,式,式的定,义,义原子谓,词,词公式：用P(x1,x2,xn,),)表示一,个,个n元谓词,公,公式，,其,其中P为n元谓词,，,，x1,x2,xn为客体,变,变量或,变,变元。,通,通常把P(x1,x2,xn,),)叫做谓,词,词演算,的,的原子,公,公式，,或,或原子,谓,谓词公,式,式。分子谓,词,词公式：可以,用,用连词,把,把原子,谓,谓词公,式,式组成,复,复合谓,词,词公式,，,，并把,它,它叫做,分,分子谓,词,词公式,。,。合适公,式,式(WFF,well,-,-formed formulas)的递归,定,定义：(1)原子谓,词,词公式,是,是合适,公,公式。(2)若A为合适,公,公式，,则,则A也是一,个,个合适,公,公式。(3)若A和B都是合,适,适公式,，,，则(AB),(,(AB),(,(A=,B), (AB)也都是,合,合适公,式,式。(4)若A是合适,公,公式，x为A中的自,由,由变元,，,，则(x)A,(x)A都是合,适,适公式,。,。(5)只有按,上,上述规,则,则(1)至(4)求得的,那,那些公,式,式，才,是,是合适,公,公式。,2.3谓词逻,辑,辑法,2.3,.,.2,谓,谓词公,式,式（PredicateFormulas）1.谓,词,词公式,的,的定义,例题：,对于所,有,有的x，如果x是整数,，,，则x或为正,的,的或者,为,为负的,。,。,(x),(,(I(x)=,(P,(,(x),N(x),),),I(x,),)表示x是整数，P(x,),)表示x是正数，N(x,),)表示x是负数。,2.3谓词逻,辑,辑法,2.3,.,.2,谓,谓词公,式,式（PredicateFormulas）2.合,适,适公式,的,的性质合适公,式,式的真,值,值：p36,表2-1 真,值,值表,2.3谓词逻,辑,辑法,2.3,.,.3,置,置换与,合,合一（Substitution,&,&Unification）1.置换在谓词,逻,逻辑中,，,，有些,推,推理规,则,则可应,用,用于一,定,定的合,适,适公式,和,和合适,公,公式集,，,，以产,生,生新的,合,合适公,式,式。一,个,个重要,的,的推理,规,规则是,假,假元推,理,理，这,就,就是由,合,合适公,式,式W1和W1=,W2产生合,适,适公式W2的运算,。,。另一,个,个推理,规,规则叫,做,做全称,化,化推理,，,，它是,由,由合适,公,公式(x)W,(,(x)产生合,适,适公式W(A,),)，其中A为任意,常,常量符,号,号。假元推,理,理：,全称化,推,推理：,综合推,理,理：,2.3谓词逻,辑,辑法,2.3,.,.3,置,置换与,合,合一（Substitution,&,&Unification）,1.置换置换：,用,用项(A)替换函,数,数表达,式,式中的,变,变量(x)，记为ES，即表,示,示一个,表,表达式E(Expression,),)用一个,置,置换S(Substitution)而得到,的,的表达,式,式的置,换,换。例1表达式Px,f(y),B的4个置换,为,为,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),Bs1=P,z,f(w,),),B,Px,f(y),Bs2=P,x,f(A,),),B,Px,f(y),Bs3=P,q(z),f(A,),),B,Px,f(y),Bs4=P,c,f(A,),),B,2.3谓词逻,辑,辑法,2.3,.,.3置换与,合,合一（Substitution,&,&Unification）2.性质,可结合,律,律(LS1)S2=L,(,(S1S2),(,(L表示一,表,表达式),(S1S2)S3=S1(S2S3),置换是,可,可结合,的,的。用s1s2表示两,个,个置换s1和s2的合成,。,。L表示一,表,表达式,，,，则有(Ls1)s2=L,(,(s1s2),以及(s1s2)s3=s1(s2s3)即用s1和s2相继作,用,用于表,达,达式L是同用s1s2作用于L一样的,。,。一般说,来,来，置,换,换是不,可,可交换,的,的，即,s1s2s2s1,3.合一(unification,),)P38,合一：,寻,寻找项,对,对变量,的,的置换,，,，以使,两,两表达,式,式一致,。,。可合一,：,：如果,一,一个置,换,换s作用于,表,表达式,集,集Ei,的每个,元,元素，,则,则我们,用,用Ei,s来表示,置,置换例,的,的集。,我,我们称,表,表达式,集,集Ei,是可合,一,一的。,2.3谓词逻,辑,辑法,2.3,.,.3置换与,合,合一（Substitution,&,&Unification）,例:表达式,集,集Px,f(y),B,Px,f,(,(B),B的合一,者,者为:,s=A/x,B/y,因为Px,f(y),Bs,=,= P,x,f(B,),),B,=P,A,f(B,),),B,即s使表达,式,式成为,单,单一形,式,式:,PA,f(B),B,但最简,单,单的合,一,一者为:,s=,B/Y,2.4,语,语义,网,网络法,语义网,络,络是1968年Quilian在研究,人,人类联,想,想记忆,时,时提出,的,的心理,学,学模型,，,，认为,记,记忆是,由,由概念,间,间的联,系,系来实,现,现的。1972年，Simmons首先将,语,语义网,络,络表示,法,法用于,自,自然语,言,言理解,系,系统。语义网,络,络的结,构,构：语,义,义网络,是,是知识,的,的一种图解表,示,示，它由,节,节点和,弧,弧线或,链,链线组,成,成。节,点,点用于,表,表示实,体,体、概,念,念和情,况,况等，,弧,弧线用,于,于表示,节,节点间,的,的关系,。,。组成,部,部分:,1词法部,分,分：决,定,定表示,词,词汇表,中,中允许,有,有哪些,符,符号，,它,它涉及,各,各个节,点,点和弧,线,线。,2结构部,分,分：叙,述,述符号,排,排列的,约,约束条,件,件，指,定,定各弧,线,线连接,的,的节点,对,对。,3过程部,分,分：说,明,明访问,过,过程，,这,这些过,程,程能用,来,来建立,和,和修正,描,描述，,以,以及回,答,答相关,问,问题。,4语义部,分,分：确,定,定与描,述,述相关,的,的(联想)意义的,方,方法即,确,确定有,关,关节点,的,的排列,及,及其占,有,有物和,对,对应弧,线,线。,2.4,语,语义,网,网络法,2.4,.,.1,二,二元语,义,义网络,的,的表示,(,(Representation of Two-Element Semantic Network,),)1.表,示,示简单,的,的事实例1.,所,所有,的,的燕子,都,都是鸟,2.4,语,语义,网,网络法,2.4,.,.1,二,二元语,义,义网络,的,的表示,(,(Representation of Two-Element Semantic Network,),),2.表示占,有,有关系,和,和其它,情,情况P40,例2.小燕是,一,一只燕,子,子，燕,子,子是鸟,；,；巢-1是小燕,的,的巢，,巢,巢-1是巢中,的,的一个,。,。3.选择语,义,义基元试图用,一,一组基,元,元来表,示,示知识,，,，以便,简,简化表,示,示，并,可,可用简,单,单的知,识,识来表,示,示更复,杂,杂的知,识,识。,2.4,语,语义,网,网络法,例3.我椅子,的,的颜色,是,是咖啡,色,色的；,椅,椅子包,套,套是皮,革,革；椅,子,子是一,种,种家具,；,；椅子,是,是座位,的,的一部,分,分；椅,子,子的所,有,有者是X；X是个人,，,，如下,图,图所示,：,：,2.4,语,语义,网,网络法,2.4,.,.2,多,多元语,义,义网络,的,的表示,语义网,络,络是一,种,种网络,结,结构。,节,节点之,间,间以链,相,相连。,多,多元语,义,义网络,表,表示的,实,实质：,把,把多元,关,关系转,化,化为一,组,组二元,关,关系的,组,组合，,或,或二元,关,关系的,合,合取。,如,如果所,要,要表示,的,的知识,是,是一元,关,关系，,例,例如，,要,要表示,李,李明是,一,一个人,，,，这在,谓,谓词逻,辑,辑中可,表,表示为MAN,(,(LIMING)。用语,义,义网络,，,，这就,可,可以表,示,示为:,与这样,的,的表示,法,法相等,效,效的关,系,系在谓,词,词逻辑,中,中表示,为,为ISA,(,(LIMING，MAN,),)。这说,明,明语义,网,网络可,以,以毫无,困,困难地,表,表示一,元,元关系,。,。,2.4,语,语义,网,网络法,例如：,要,要表达,北,北京大,学,学(BEIJINGUniversity,简称BU)和清华,大,大学(TSINGHUA,University,简称TU)两校篮,球,球队在,北,北大进,行,行的一,场,场比赛,的,的比分,是,是85比89。,若用谓,词,词逻辑,可,可表示,为,为SCORE(BU，TU，(85,-,-89,),)。这个,表,表示式,中,中包含3项，而,语,语义网,络,络从本,质,质上来,说,说，只,能,能表示,二,二元关,系,系。解,决,决这个,矛,矛盾的,一,一种方,法,法是把,这,这个多,元,元关系,转,转化成,一,一组二,元,元关系,的,的组合,，,，或二,元,元关系,的,的合取,。,。,具体来,说,说，多,元,元关系R(X1，X2，Xn)总可以,转,转换成R1(X11，X12,),)R2(X21，X22,),),Rn,(,(Xn1,Xn2),图2.20多元关,系,系的语,义,义网络,表,表示,2.4,语,语义,网,网络法,2.4,.,.3语,义,义网络,的,的推理,过,过程,在语义,网,网络知,识,识表达,方,方法中,，,，赋予,网,网络结,构,构的含,义,义完全,决,决定于,管,管理这,个,个网络,的,的过程,的,的特性,。,。,为了便,于,于以下,的,的叙述,，,，对所,用,用符号,作,作进一,步,步的规,定,定。区,分,分在链,的,的头部,和,和在链,的,的尾部,的,的节点,，,，把在,链,链的尾,部,部的节,点,点称为,值,值节点,。,。另外,，,，我们,还,还规定,节,节点的,槽,槽相当,于,于链，,不,不过取,不,不同的,名,名字而,已,已。在,图,图2.28中砖块12(BRICK12)有3个链，,构,构,成两个,槽,槽。其,中,中一个,槽,槽只有,一,一个,值，另,外,外一个,槽,槽有两,个,个值。,我,我们,说颜色,槽,槽(COLOR,),)填入红,色,色(RED)，,ISA槽填入,了,了砖块(BRICK,),)和玩具,(TOY)。,图2.28语义网,络,络的槽,和,和数值,2.4,语,语义,网,网络法,2.4,.,.3语,义,义网络,的,的推理,过,过程,语义网,络,络中的,推,推理过,程,程主要,有,有两种:一种是,继,继承，,另,另一种,是,是匹配,。,。以下,我,我们分,别,别介绍,这,这两种,过,过程。1.继承在语义,网,网络中,所,所谓的,继,继承是,把,把对事,物,物的描,述,述从概,念,念节点,或,或类节,点,点传递,到,到实例,节,节点。,例,例如在,图,图2.29上所示,的,的语义,网,网络中BRICK是概念,节,节点，BRICK12是一个,实,实例节,点,点。BRICK节点在SHAPE(外形)槽，其,中,中填入,了,了RECTANGULAR(矩形)，说明,砖,砖块的,外,外形是,矩,矩形的,。,。这个,描,描述可,以,以通过ISA链传递,给,给实例,节,节点BRICK12。因此,，,，虽然BRICK12节点没,有,有SHAPE槽，但,可,可以从,这,这个语,义,义网,络,络推理,出,出BRICK12的外形,是,是矩形,的,的。,图 2,.,.29,语,语义,网,网络的,值,值继承,2.4,语,语义,网,网络法,2.4,.,.3语,义,义网络,的,的推理,过,过程,1.继承,这种推,理,理过程,，,，类似,于,于人的,思,思维过,程,程。一,旦,旦知道,了,了某种,事,事物的,身,身份以,后,后，可,以,以联想,起,起很多,关,关于这,件,件事物,的,的一般,描,描述。,例如，,我,我们通,常,常认为,鲸,鲸鱼很,大,大，鸟,比,比较小,，,，城堡,很,很古老,，,，运动,员,员很健,壮,壮。这,就,就像我,们,们用每,种,种事物,的,的典型,情,情况来,描,描述各,种,种事物-鲸鱼、,鸟,鸟、城,堡,堡和运,动,动员-那样。一共有3种继承,过,过程：,值,值继承,、,、如果需,要,要继承和默认继承。,2.4,语,语义,网,网络法,2.4,.,.3语,义,义网络,的,的推理,过,过程,语义网,络,络中的,推,推理过,程,程主要,有,有两种:一种是,继,继承，,另,另一种,是,是匹配,。,。以下,我,我们分,别,别介绍,这,这两种,过,过程。1.继承(1)值继承除了ISA链以外,，,，另外,还,还有一,种,种AKO,(,(是某种)链也可,被,被用于,语,语义网,络,络中的,描,描述或,特,特性的,继,继承。AKO是A-KIND,-,-OF的缩写,。,。总之，ISA和AKO链直接,地,地表示,类,类的成,员,员关系,以,以及子,类,类和类,之,之间的,关,关系，,提,提供了,一,一种把,知,知识从,某,某一层,传,传递到,另,另一层,的,的途径,。,。为了能,利,利用语,义,义网络,的,的继承,特,特性进,行,行推理,我,我们还,需,需要一,个,个搜索,程,程序用,来,来在合,适,适的节,点,点寻找,合,合适的,槽,槽。,2.4,语,语义,网,网络法,2.4,.,.3语,义,义网络,的,的推理,过,过程,1.继承(2),“,“如果需,要,要”继,承,承在某些,情,情况下,，,，当我,们,们不知,道,道槽值,时,时，可,以,以利用,已,已知信,息,息来计,算,算。例,如,如，我,们,们可以,根,根据体,积,积和物,质,质的密,度,度来计,算,算积木,的,的重量,。,。进行,上,上述计,算,算的程,序,序称为if-needed,(,(如果需,要,要)程序。,为了储,存,存进行,上,上述计,算,算的程,序,序，我,们,们需要,改,改进节,点,点槽值,的,的结构,，,，允许,槽,槽有几,种,种类型,的,的值，,而,而不只,是,是一个,类,类型。,为,为此，,每,每个槽,又,又可以,有,有若干,个,个侧面,，,，以储,存,存这些,不,不同类,型,型的值,。,。这样,，,，以前,我,我们讨,论,论的原,始,始意义,上,上的值,就,就放“,值,值侧面,”,”中，if-needed程序，,存,存放在IF-NEEDED侧面中,。,。,例如在,图,图2.30(a,),)中，一,个,个重量,确,确定程,序,序存放,在,在BLOCK节点的WEIGHT槽的IF-NEEDED侧面中,。,。,图 2,.,.30,语,语义,网,网络的,如果,需,需要,继,继承,2.4,语,语义,网,网络法,2.4,.,.3语,义,义网络,的,的推理,过,过程,1.继,承,承(3),“,“缺省”,继,继承某些情,况,况下，,当,当我们,对,对事物,所,所作的,假,假设不,是,是十分,有,有把握,时,时，最,好,好对所,作,作的假,设,设加上,“,“可能,”,”这样,的,的字眼,。,。例如,，,，我们,可,可以认,为,为法官,可,可能是,诚,诚实的,，,，但不,一,一定是,；,；或认,为,为宝石,可,可能是,很,很昂贵,的,的，但,不,不一定,是,是。,我们把,这,这种具有相,当,当程度,的,的真,实性，,但,但又不,能,能十分,肯,肯定的,值,值称为,“缺省,”,”值。这种,类,类型的,值,值被放,入,入槽,的DEFAULT(缺省)侧