人工智能.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第二部分 知识表示方法,2,知识是一切智能行为的基础，也是人工智能的重要研究对象。要使计算机具有智能，就必须使它具有知识，而要使计算机具有知识，首先必须解决知识的表示问题。,知识表示包括知识表示的概念和知识表示方法。对知识表示方法，又可根据所表示知识的确定化程度，分为确定性知识表示和不确定性知识表示。,3,知识与知识表示的概念,状态空间法,问题规约法,谓词逻辑法,语义网络法,框架表示法,内容提要,4,1,.,知识与知识表示的概念,知识,1,）,.,知识的属性,2,）,.,知识的类型,二,.,知识表示,1,）,.,知识表示的要求,2,）,.,知识表示观点,3,）,.,知识表示的方法,5,知识是人们在改造客观世界的实践中积累起来的认识和经验。,通常，人们对客观世界的描述是通过数据和信息来实现的。,数据和信息是两个密切相关的概念。数据是信息的载体和表示，信息是数据在特定场合下的含义，或者说信息是数据的语义。,一.知识,6,知识是对信息进行智能性加工所形成的对客观世界规律性的认识。,把有关信息关联在一起所形成的信息结构称为知识。,“,信息,”,与,“,关联,”,是构成知识的两个要素。,信息之间关联的形式可以多种多样，其中最常用的一种形式是：,如果,，那么,。,例如，,“,如果他学过人工智能课程，那么他应该知道什么叫知识,”,。,7,（1）真假性与相对性,1,）,.,知识的属性：,真假性是指可以通过实践或推理来证明知识为真或为假。,相对性是指知识的真与假是相对于某些条件、环境及时间而言的，即知识一般不是无条件的真或无条件的假，而是相对于一定条件的。,8,知识的不确定性包括不完备性、不确定性与模糊性：,（2）不确定性,知识的不完备性是指在解决问题时不具备解决该问题所需要的全部知识。,知识的不确定性是指知识所具有的既不能完全被确定为真，又不能完全被确定为假的特性。,知识的模糊性是指知识的“边界”不明确的特性。,9,矛盾性是指同一个知识集中的不同知识之间相互对立或不一致，即从这些知识出发，会推出不一致的结论。,相容性是指同一个知识集中的所有知识之间互相不矛盾。,（3）矛盾性和相容性,10,可表示性是指知识可以用适当的形式表示出来。例如语言、文字、图形、神经元网络等。,可利用性是指知识可以被用来解决各种各样的问题。,（4）可表示性与可利用性,11,（1）按知识的性质：,2,）,.,知识的类型：,概念,命题,公理,定理,规则,方法,12,常识性知识：是指通用通识的知识。即人们普遍知道的、适应于所有领域的知识。,领域性知识：是指面向某个具体专业的专业性知识，这些知识只有该领域的专业人员才能够掌握和运用它。,（2）按知识的作用范围：,13,事实性知识：也称叙述性知识，是用来描述问题或事物的概念、属性、状态、环境及条件等情况的知识。,过程性知识：是用来描述问题求解过程所需要的操作、演算或行为等规律性的知识，它指出在问题求解过程中如何使用那些与问题有关的事实性知识，即用来说明在那些叙述性知识成立的时候该怎么办。,控制性知识：也称元知识或超知识，是关于如何运用已有知识进行问题求解的知识，因此，也称为关于知识的知识。,（3）按知识的作用,14,表层知识是指客观事物的现象以及这些现象与结论之间关系的知识。,深层知识是指事物本质、因果关系内涵、基本原理之类的知识。例如，理论知识、理性知识等。,（4）按知识的层次,15,确定性知识：是可以给出其真值为“真”或“假”的知识。这些知识是可以精确表示的知识。,不确定性知识：是指具有“不确定”特性的知识。不确定性的概念包含不精确、不完备和模糊。,（5）按知识的确定性,16,逻辑性知识：是反映人类逻辑思维过程的知识，例如人类的经验性知识。它对应着逻辑思维。,形象性知识：是通过事物的形象建立起来的知识，它对应着形象思维。例如，一个人的相貌，要用文字来描述非常困难，但要亲眼见到这个人，就很容易在头脑中形成这个人的概念。,（6）按知识的结构及表现形式,17,所谓知识表示是对知识的一种描述，即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。,同一知识可以有多种不同的表示形式，而不同表示形式所产生的效果又可能不一样。,二.知识表示,18,（1）表示能力,知识表示能力是指能否正确、有效地将问题求解所需要的各种知识表示出来。知识表示能力包括以下三个方面：,一是知识表示范围的广泛性；,二是领域知识表示的高效性；,三是对非确定性知识表示的支持程度。,1,）,.,知识表示的要求,19,（2）可利用性,知识的利用是指使用知识进行推理，以求得问题的解。知识的可利用性包括对推理的适应性和对高效算法的支持性。,（3）可组织性与可维护性,知识的组织是指把有关知识按照某种方式组成一种知识结构。知识维护是指在保证知识的一致性与完整性的前提下对知识所进行的增加、删除、修改等操作。,20,（4）可实现性,所谓可实现性是指知识表示要便于在计算机上实现，便于直接由计算机对其进行处理。,（5）自然性与可理解性,自然性是指知识表示形式要符合人们的日常习惯和思维方式。可理解性是指所表示的知识应易读、易懂、易获取、易维护。,21,（1）陈述性观点,陈述性知识表示（,Declarative knowledge representation）,是指以陈述的方式把知识用一定的数据结构表示出来，即把知识看作一种特殊的数据，知识表示说明描述的对象是什么，不涉及如何运用知识的问题。,2,）,.,知识表示观点：,22,（2）过程性观点,过程性知识表示（,Procedural knowledge representation）,是指以程序（亦称为过程）的方式把知识表示出来，即把知识寓于程序之中，把知识表示和运用知识结合起来。,23,知识表示方法又称为知识表示技术，其表示形式被称为知识表示模式。目前，使用较多的知识表示方法有:,状态空间法,问题归约法,谓词逻辑法,语义网络法,框架表示法,剧本表示法,过程表示法,面向对象表示法,3,）,.,知识表示方法：,24,问题的状态描述,二,.,状态图示法,三,.,状态空间表示举例,2.状态空间法,25,对人工智能研究中运用的问题求解方法进行综合分析，可以发现许多问题求解方法是采用试探搜索方法的。,是通过在某个可能的解空间内寻找一个解来求解问题的。,这种基于解答空间的问题表示和求解方法就是状态空间法。,状态空间法是以状态和算符为基础来表示和求解问题的。,26,实例：十五数码难题,一.问题的状态描述,如何把初始棋局变换为目标棋局？,27,最直接的求解方法：尝试各种不同的走步，直到偶然得到目标棋局为止，即试探搜索。,28,对十五数码难题的问题描述和求解过程进行分析：,初始状态：初始棋局,11，9，4，15，1，3，0，12，7，5，8，6，13，2，10，14,操作符：走步,右移棋子3，下移棋子4，左移棋子12，,.（60条）,或者：移动空格 （4条）,目标状态：目标棋局,1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，0,状态空间法,：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。,状态图,：初始状态可达到的各状态所对应的节点组成的图。,29,问题状态的描述：,状态,：为描述某类不同事物间的差别而引入的一组最少变量,q,0,，q,1,，,，q,n,的有序集合，其矢量形式如下：,Q=q,0,，q,1,，,，q,n,状态变量,：状态集合中的每个元素,q,i,（i=0,1,n）。,具体状态,：给定每个分量的一组值。如,Q,k,=q,0k,，q,1k,，,，q,nk,操作符,：使问题从一种状态变换到另一种状态的手段，也叫,算符,。算符可以是走步、过程、规则、数学算子、运算符号或逻辑符号等。,问题的状态空间,：表示该问题全部可能状态及其关系的图。它包含三种说明的集合，即所有可能的问题初始状态集合,S、,操作符集合,F,以及目标状态集合,G。,状态空间可记为三元组（,S，F，G）,30,图论中的几个术语：,图；有向图；后继节点（后裔）；父辈节点（祖先）；,路径（长度为,k,的路径）；节点,n,j,是从节点,n,i,可达到的路径；,代价；两节点间路径的代价。,当用一个图来表示某个状态空间时，图中各节点标上相应的状态描述，而有向弧线旁边标上算符。,寻找从一种状态变换为另一种状态的某个算符序列问题等价于寻找图的某一路径问题。,二.状态图示法,31,图的显式说明：图中的各节点及其具有代价的弧线由一张图或表明确给出。,图的隐式说明：图中的节点集合是无限的，但起始节点是已知的，而且引入后继算符的概念是方便的。把后继节点算符作用于任一节点可以产生该节点的全部后继节点和各连接弧线的代价。,搜索某个状态空间以求得算符序列的一个解答过程，就是使隐式图足够大的一部分变为显式以便包含目标的过程，这是状态空间问题求解的基础。,问题的表示对求解工作量有很大的影响,。,32,问题的状态表示方法涉及在状态描述中如何应用变量。须用一个包含变量的表达式来描述状态的全部集合，而不仅仅描述一个状态。,用常量取代表达式中的变量，就可得到一个具体的状态描述。用来描述一个状态集合的含有变量的表达式，叫做状态描述模式。,33,三.状态空间表示举例,实例：猴子摘香蕉问题,a c b,箱子,34,问题状态的表示：四元组（,W，x，Y，z）,W：,猴子的水平位置。,W=a，b，c。,x：,当猴子在箱子顶上时取,x=1；,否则取,x=0。,Y：,箱子的水平位置。,Y=a，b，c。,z：,当猴子摘到香蕉时取,z=1；,否则取,z=0。,初始状态：（,a，0，b，0,）,目标状态：（,c，1，c，1,）,35,算符集合：,goto(b)：,猴子走到水平位置,b。,（a，0，b，z）goto(U)（b，0，b，z）,pushbox(c)：,猴子把箱子推到水平位置,c,。,（,b，0，b，,z）pushbox(V)（c，0，c，z）,climbbox：,猴子爬上箱顶。,（,c，0，c，z,）climbbox （,c，1，c，z,）,grasp：,猴子摘到香蕉。,（c，1，c，0）grasp（c，1，c，1）,算符的适用性条件：强加于操作的实用性条件。,如：应用算符,pushbox(c),时，要求猴子与箱子必须在同一位置,36,操作序列：,goto(b)，pushbox(c)，climbbox，grasp,猴子摘香蕉问题的状态空间图,37,练习题,(,野人和传教士渡河问题）：,有3个传教士和3个野人来到河边，打算乘一艘小船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？,38,3,.,问题归约法,问题规约的描述,二,.,与或图表示,三,.,问题归约机理,39,问题归约法：,有许多问题可以通过一系列变换变为一个子问题集；,这些子问题的解可以直接得到；,通过解决这些子问题，从而就解决了初始问题。,40,实例：梵塔问题,一.问题的归约描述,如何由初始配置变换为目标配置？,1,2,3,1,2,3,初始配置,目标配置,41,求解思路：把原始问题归约为一个比较简单的问题的集合,A,B,C,1,2,3,A,B,C,1,2,3,111,122,A,B,C,1,2,3,A,B,C,1,2,3,122,322,A,B,C,1,2,3,A,B,C,1,2,3,322,333,要把所有圆盘都移至柱子3，必须先把圆盘,C,移至柱子3；而且在移动圆盘,C,至柱子3之前，柱子3必须是空的。,只有在移开圆盘,A,和,B,之后，才能移动圆盘,C；,而且圆盘,A,和,B,不能在柱子3。因此，应该把,A,和,B,移到柱子2上。,把圆盘,C,从柱子1移动到柱子3，并继续解决其余部分的移动问题。,（移动,A、B-2）,（移动,C-3）,（移动,A、B-3）,42,通过以上分析，把原始问题归约为3个子问题：,（1）移动,A、B-2,双圆盘问题：可进一步归约,（2）移动,C-3,单圆盘问题：可直接求解-本原问题,（3）移动,A、B-3,双圆盘问题：可进一步归约,与或图：可以有效说明问题归约法的求解过程。,梵塔问题归约图,43,问题归约描述：,采用问题归约法描述与求解问题，问题归约表示由三部分组成：,（1）一个初始问题描述 如：（111），（333）,（2）一套把问题变换为子问题的操作符,问题归约算符,如：移动,A、B-2,等,（3）一套本原问题描述 如：（122），（322）,本原问题,：是可直接求解或具有已知解答的问题，出现本原问题即可停止搜索。,问题归约法的实质：从目标（要解决的问题）出发,逆向推理,，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个本原问题集合。,问题归约的目的：最终产生具有明显解答的本原问题。,44,二.与或图表示,用问题归约法描述和求解问题的过程可以用与或图来表示。,例如：问题,A,既可由求解问题,B,和,C，,也可由求解问题,D、E,和,F，,或者由单独求解问题,G,来解决。这一关系可由右图所示的结构图来表示。,45,为了使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下，在上述结构图中引入附加节点。,如右图，可以认为问题,A,被归约为单一子问题,N、M,和,H，N、M,和,H,叫,或节点,。问题,N,被归约为子问题,B,和,C,的单一集合，要求解,N,就必须求解所有的子问题，因此，,B,和,C,叫做,与节点,。各个与节点用跨接指向其后继节点的弧线的小段圆弧加以标记。,这样形成的结构图就叫与或图。,46,关于与或图的几点说明：,在与或图中，如果一个节点有后继节点，那么这些后继节点既可全为与节点，也可全为或节点。,特殊情况下，可能不出现任何与节点，如在状态空间图中就不存在与节点，即状态空间图是,普通图,，因此可以说问题归约法是比状态空间法更通用的问题求解方法。,通过与或图，在某个问题描述中应用问题归约算符，可以依次产生出一个中间或节点和与节点后继，从而可以用与或图来表示问题归约方法的相关结构。,在与或图中，起始节点对应于原始问题描述，叶子节点对应于本原问题描述。,47,引入与或图后，问题求解过程就转换为与或图上的搜索过程，搜索的目的是要表明起始节点有解，在与或图中一个可解节点的一般定义可以归纳为：,（1）叶子节点是可解节点（本原问题）。,（2）如果某个非叶节点含有,或,后继节点，那么只有当其后继节点至少有一个可解时，该非叶节点才是可解的。,（3）如果某个非叶节点含有,与,后继节点，那么只有当其后继节点全部可解时，该非叶节点才是可解的。,在上述定义基础上，可以给出解图的定义：,解图,是那些可解节点的子图，这些节点能够证明其初始节点是可解的。,48,当与或图中某些非叶节点完全没有后继节点时，我们就说它是不可解的。这些不可解节点的出现可能意味着图中另外一些节点也是不可解的。不可解节点的一般定义可以归纳为：,（1）没有后继的非叶节点是不可解节点。,（2）如果某个非叶节点含有,或,后继节点，那么只有当其全部后继节点不可解时，该非叶节点才是不可解的。,（3）如果某个非叶节点含有,与,后继节点，那么只有当其后继节点至少有一个不可解时，该非叶节点才是不可解的。,与状态空间图求解类似，一般很少用显式图来搜索，而是用由初始问题描述和问题归约算符所定义的隐式图来搜索，从而，问题求解过程实际上就是生成与或图的足够部分，以证明初始节点可解。,49,综上所述，与或图的构成规则可以概括如下：,（1）与或图中的每个节点代表一个要解决的单一问题或问题集合，起始节点对应于原始问题。,（2）对应于本原问题的节点，叫做叶子节点，它没有后继。,（3）对于把问题归约算符应用于问题,A,的每种可能情况，都把问题变换为一个子问题的集合，有向弧线由,A,指向后继节点，表示所求得的子问题集合。如问题,A,可归约为不同的子问题集合,N、M,和,H，,只要,N、M,和,H,有一个可解，则,A,可解，所以,N、M,和,H,称为或节点。,50,（4）对于代表两个或两个以上子问题集合的每个节点，有向弧线从该节点指向该子问题集合中的各个节点。因为只有当集合中的所有项都有解时，该子问题才有解，所以这些子问题节点叫与节点。为了和或节点进行区分，把具有共同父辈的与节点后裔的所有弧线用另外一段小弧线连接起来。,（5）特殊情况下，当只有一个算符可应用于问题,A，,而且这个算符产生具有一个以上子问题的某个集合时，由（3）和（4）所产生的图可以得到简化，将代表子问题集合的中间或节点略去。,利用上述规则生成的与或图中，每个节点代表一个问题或问题集合，除起始节点外，每个节点只有一个父节点，所以这样的与或图实际是,与或树,。,51,三.问题归约机理,出发点引入关键算符：,对于状态空间的搜索问题，虽然寻求某个解答中的整个算符序列比较困难，但规定这些算符中的一个却往往比较容易。如果某个算符被认为是求解问题的决定性步骤，那么就很容易找到这样一个算符。例如，梵塔难题中“移动,C-3”,这个算符就是求解问题的决定性步骤，也很容易找到该算符，这种具有决定性作用的算符叫做,关键算符,。,52,关键算符的作用：,确定了某个关键算符后，就可以以该关键算符为基础进行问题归约。,例如，在三元状态（,S，F，G）,表示的问题中，假设,F,中的某个,f,是关键算符，那么可以认为（,S，F，G）,的第一个后继问题是一个对应于寻找一条通向某一,f,适用的状态的路径问题，令,G,f,表示,f,适用的所有状态的集合，则该后继问题是由（,S，F，G,f,）,描述的子问题。,一旦该子问题得到解决，就可以进一步解决由（,g，F，f（g）,所表示的子问题，其中,g,G,f,，f（g）,表示把,f,应用于,g,而得到的状态，因为该子问题是仅由应用关键算符,f,就可以解决，所以是本原问题。于是，剩下的就是解决由（,f（g），F，G,）所描述的子问题。,53,关键算符的作用：,一旦确定了某个关键算符,f，,就可以把问题归约为如下三个子问题：,（1）（,S，F，G,f,）；,（2）（,g，F，f（g）；,（3）（,f（g），F，G,）。,问题（2）是本原问题,问题（1）和（3）可以用直接的状态空间搜索技术或进一步的问题归约来求解（寻找子问题的关键算符，进一步归约下去）,54,关键算符的作用：,对于许多问题，往往无法预先知道哪个算符是关键算符，只能推测某个算符的子集，该子集中的某个算符可能是关键算符。因此，用该子集中的每个算符产生后继子问题，这样就建立起了一个与或图。,可见，要应用这种方法，首先必须寻找状态空间搜索问题的候选关键算符集合。,如何寻找候选关键算符呢？计算某个问题的差别,55,什么是差别？,实例：猴子摘香蕉问题,把4个算符的作用结果和使用条件重写如下：,f1：（W，0，Y，z）goto(U)（U，0，Y，z）,f2：（W，0，W，z）pushbox(V)（V，0，V，z）,f3：（W，0，W，z）climbbox （W，1，W，z）,f4：（c，1，c，0）grasp（c，1，c，1）,初始状态,：（,a，0，b，0）,算符集合：,F=f1，f2，f3，f4,满足目标条件的状态集合：,G,56,应用关键算符和差别的归约过程：,首先计算初始问题的差别，,（,a，0，b，0）,不满足目标测试的原因在于其最后一个元素不是1。与归约这个差别相关的关键算符是,f4=grasp，,用,f4,来归约初始问题，得到如下子问题：,（1）（,a，0，b，0），F，G,f4,）,（2）（S1，F，f4（S1）（,本原问题）,（3）（f4（S1），F，G）（,本原问题）,其中,G,f4,是适用于算符,f4,的状态描述集合，,S1,G,f4,57,要求解问题（1），就要先计算其差别。由,（,a，0，b，0）,所描述的状态不在,Gf4,中，差别如下：,箱子不在,c,处,猴子不在,c,处,猴子不在箱子上,f2=pushbox（c）,f1=goto（c）,f3=climbbox,与差别相关的关键算符,用关键算符,f2,归约问题（1），得到如下子问题：,（1-1）（,a，0，b，0），F，Gf2）,（1-2）（S11，F，f2（S11）（,本原问题）,（1-3）（f2（S11），F，Gf4）,Gf2,是适用于算符,f2,的状态描述集合，,S11 Gf2,58,现在必须求解问题（1-1），所以仍需要先计算其差别。此差别为：,猴子不在,b,处,f1=goto（b）,与差别相关的关键算符,用关键算符,f1,归约问题（1-1），得到如下子问题：,（1-11）（,a，0，b，0），F，Gf1）,（,差别为0，本原问题，可直接用,f1,求解）,（1-12）（S111，F，f1（S111）（,本原问题）,（1-13）（f1（S111），F，Gf2）,Gf1,是适用于算符,f1,的状态描述集合，,S111 Gf1。,59,现在需要求解问题（1-13），由于,f1（S111）=（b，0，b，0），,所以问题（1-13）变为：,（b，0，b，0），F，Gf2），,这个问题也是本原问题，可以直接用,f2,求解。,把先前产生的问题求解过程继续下去，直到最后解答此初始问题为止。,60,通过该实例分析，可以看出：,问题（,S，F，G）,的,差别,就是用,S,的元对由集合,G,规定的目标进行测试失败原因的部分表列（如果,S,的某个元是在,G,中，那么该问题就获得解决，也就不存在差别）。,例如，如果目标集合,G,由某个状态条件集合所规定，而且某个,s,S,满足这些条件中的某些但不是全部条件，那么差别可由不能被,s,满足的条件的部分表列组成。如果这些条件能够按其重要性分类，那么应该选择最重要的不满足条件作为差别。,当把每个可能的差别与某些算符或算符集合结合起来时，这些算符就是候选关键算符。只有当应用某个算符是与消去某个差别相关时，该算符才与该差别结合在一起。,61,4,.,谓词逻辑法,谓词逻辑表示法的逻辑基础,1,）,.,命题与真值,2,）,.,论域和谓词,3,）,.,连接词和量词,4,）,.,项与合式公式,二,.,谓词逻辑表示方法,三,.,谓词逻辑的应用,四,.,谓词表示的特性,62,谓词逻辑表示法是一种基于数理逻辑的知识表示方式。数理逻辑是一门研究推理的科学，它作为人工智能的基础，在人工智能的发展中占有重要地位。人工智能中用到的逻辑可分为两大类：一类是一阶经典命题逻辑和谓词逻辑；另一类是除经典逻辑以外的那些逻辑。,这里所说的谓词逻辑法涉及一阶经典命题逻辑和谓词逻辑。,63,一阶谓词逻辑知识表示中所需要的逻辑基础包括：命题、谓词、连词、量词、谓词公式等。,逻辑推理所需要的逻辑基础部分放到,“,逻辑推理,”,章讨论。,一.谓词逻辑表示法的逻辑基础,64,1命题与真值,定义：,一个陈述句称为一个断言。凡有真假意义的断言称为命题。,命题的意义通常称为真值，它只有真假两种情况。当命题的意义为真时，则称该命题的真值为真，记为,T；,反之，则称该命题的真值为假，记为,F。,在命题逻辑中，命题通常用大写的英文字母来表示。,一个命题不能同时既为真又为假。,例如：,“,天安门城楼在长安街的北边,”,是一个真值为,T,的命题,“,天安门广场在长安街的北边,”,则是一个真值为,F,的命题,65,关于命题：,一个命题可在一定条件下为真，在另一种条件下为假。例如，命题,“,北京今天有雨,”,，需要根据当天的实际情况来决定其真值。,没有真假意义的感叹句、疑问句等都不是命题。例如，,“,今天好冷啊！,”,和,“,今天的温度有多少度？,”,都不是命题。,命题的优点是简单、明确；其主要缺点是无法描述客观事物的结构及其逻辑特征，也无法表示不同事物间的共性。,66,2论域和谓词,论域是由所讨论对象全体构成的非空集合。论域中的元素称为个体，论域也常称为个体域。例如，整数的个体域是由所有整数构成的集合，每个整数都是该个体域中的一个个体。,在谓词逻辑中，命题是用谓词来表示的。一个谓词可分为谓词名和个体两部分。其中，个体是命题中的主语，用来表示某个独立存在的事物或者某个抽象的概念；谓词名是命题的谓语，用来表示个体的性质、状态或个体之间的关系等。,例如，对于命题,“,王宏是学生,”,可用谓词表示为,STUDENT（Wanghong）。,其中，,Wanghong,是个体，代表王宏；,STUDENT,是谓词名，说明王宏是学生的这一特征。通常，谓词名用大写英文字母表示，个体用小写英文字母表示。,67,谓词定义：,定义：,设,D,是个体域，,P：D,n,T，F,是一个映射，其中,D,n,=(x,1,x,2,x,n,)|x,1,x,2,x,n,D,则称,P,是一个,n,元谓词（,n=1,2,）,记为,P(x,1,x,2,x,n,)。,其中,x,1,x,2,x,n,为个体变元。,在谓词中，个体可以是常量、变元或函数。,例如，,“,x6,”,，,可用谓词表示为,Greater（x，6）,其中,x,是变元。再如，,“,王宏的父亲是教师,”,可用谓词表示为,TEACHER（father（Wanghong)，,其中,father（Wanghong）,是一个函数。,68,函数定义：,定义：,设,D,是个体域，,f：D,n,D,是一个映射，则称,f,是,D,上的一个,n,元函数，记作:,f(x,1,x,2,x,n,)(n=1,2,),其中,X,1,，X,2,，,，X,n,是个体变元。谓词和函数从形式上看很相似，容易混淆。但它们是两个完全不同的概念。谓词的真值是真和假，而函数无真值可言，其值是个体域中的某个个体。谓词实现的是从个体域中的个体到,T,或,F,的映射，而函数所实现的是同一个体域中从一个个体到另一个个体的映射。在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词之中。,69,在谓词,P(x,1,x,2,x,n,),中，如果,x,i,(i=1,2,n),都是个体常量、变元或函数，称它为一阶谓词。如果某个,x,i,本身又是一个一阶谓词，则称它为二阶谓词。只讨论一阶谓词,70,3.连接词和量词,在一阶谓词逻辑中共有5个连接词和2个量词。命题逻辑可看作谓词逻辑的一种特殊形式，一阶谓词逻辑中的5个连接词也都适应于命题逻辑，但2个量词仅适应于谓词逻辑。,71,（1）连接词 连接词是用来连接简单命题，并由简单命题构成复合命题的逻辑运算符号。包括：称为,“,非,“,或者,“,否定,”,。它表示对其后面的命题的否定，使该命题的真值与原来相反。例如，对命题,P，,若其原来的真值为,T，,则,P（,读作非,P）,的真值为,F；,若其原来的真值为,F，,则,P,的真值为,T：,称为,“,析取,”,。它表示所连结的两个命题之间具有,“,或,”,的关系：称为,“,合取,”,。它表示所连结的两个命题之间具有,“,与,”,的关系：称为,“,条件,”,或,“,蕴含,”,。它表示,“,若,则,”,的语义。例如，对命题,P,和,Q，,蕴含式,PQ,表示,“,P,蕴含,Q,”,，,读作,“,如果,P，,则,Q,”,，,其中,P,称为条件的前件，,Q,称为条件的后件。：称为,“,双条件,”,。它表示,“,当且仅当,”,的语义。例如，对命题,P,和,Q，PQ,表示,“,P,当且仅当,Q,”,，,即读作,“,P,当且仅当,Q,”,。,72,对以上连接词的定义，可用下表所给出的谓词逻辑真值表来表示：,P,Q,P,PQ,PQ,PQ,PQ,T,T,F,T,T,T,T,T,F,F,T,F,F,F,F,T,T,T,F,T,F,F,F,T,F,F,T,T,73,（2）量词 量词是由量词符号和被其量化的变元所组成的表达式，用来对谓词中的个体作出量的规定。在一阶谓词逻辑中引入了2个量词符号，一个是,全称量词,符号,“,”,，意思是,“,所有的,”,、,“,任一个,”,；另一个是,存在量词,符号,“,彐,”,，意思是,“,至少有一个,”,、,“,存在有,”,。例如,X,是一个全称量词，表示,“,对论域中的所有个体。,”,，读作,“,对于所有,x,”,；,彐,x,是一个存在量词，表示,“,在论域中存在个体,X,”,，,读作,“,存在,x,”,。,全称量词的定义：命题（,x）P(x),为真，当且仅当对论域中的所有,x，,都有,P（x）,为真。命题（,x）P（x）,为假，当且仅当至少存在一个,x,0,D，,使得,P（x,0,）,为假。存在量词的定义：命题（彐,x）P（x）,为真，当且仅当至少存在一个,x,0,D，,使得,P（x,0,）,为真。命题(彐,x）P（x）,为假，当且仅当对论域中的所有,x，,都有,P（x）,为假。,74,在一阶谓词演算中，合法的表达式称为合式公式（即谓词公式）。对合式公式的定义将涉及到,“,项,”,的概念，下面分别给出它们的定义。,定义：项,满足如下规则：（1）单独一个个体词是项；（2）若,t,1,，t,2,，t,n,是项，,f,是,n,元函数，则,f(t,1,t,2,t,n,),是项；（3）由（1）、（2）生成的表达式是项。可见，项是把个体常量、个体变量和函数统一起来的概念。,定义：原子谓词公式的含义为：若,t1，t2，tn,是项，,P,是谓词符号，则称,P（t1,t2,tn）,为原子谓词公式。,4.,项与合式公式,75,定义：,满足如下规则的谓词演算可得到合式公式：（1）单个原子谓词公式是合式公式；（2）若,A,是合式公式，则,A,也是合式公式；（3）若,A、B,都是合式公式，则,AB，AB，AB，AB,也都是合式公式；（4）若,A,是合式公式，,x,是项，则（,x)A,和(彐,x）A,也都是合式公式。,这个定义是合式公式的形成规则，按照这些规则可以形成任意复杂的合式公式。例如，,P（x，y）Q（y)，(x）(A（x）B（x)，（,彐,x）A(x）（y）R（x，y）B（y）,都是合式公式。在合式公式中，连接词之间的优先级别是：，,76,当一个谓词公式含有量词时，区分个体变元是否受量词的约束是很重要的。位于量词后面的单个谓词或者用括号括起来的合式公式称为该量词的辖域，辖域内与量词中同名的变元称为约束变元，不受约束的变元称为自由变元。例如：（,x)(P(x,y)Q(x,y)R(x,y),5.,自由变元和约束变元,77,谓词逻辑不仅可以用来表示事物的状态、属性、概念等事实性知识，也可以用来表示事物的因果关系，即规则。对事实性知识，通常是用否定、析取或合取符号连接起来的谓词公式表示。对事物间的因果关系，通常用蕴含式表示，例如，对,“,如果,x，,则,y,”,可表示为,“,xy,”,。,当用谓词逻辑表示知识时，首先需要根据所表示的知识定义谓词，然后再用连接词或量词把这些谓词连结起来，形成一个谓词公式。,二.谓词逻辑表示方法,78,此时，该知识可用谓词表示为：(,x)(,彐,y)(PERSON（x）HASFATHER(x,y),例1：用谓词逻辑表示知识,“,每个人都有一个父亲,”,首先定义谓词：,PERSON（x）：,表示,x,是人。,HASFATHER(x,y)：,表示,x,有父亲,y。,79,首先定义谓词：,TEACHER（x）：,表示,x,是教师。,STUDENT（y）：,表示,y,是学生。,TEACHES（x，y）：,表示,x,是,y,的老师。,例2：用谓词逻辑表示知识“所有教师都有自己的学生”,此时，该知识可用谓词表示为：(,x)(,彐,y)(TEACHER(x)TEACHES(x,y)STUDENT(y),该谓词公式可读作：对所有,x，,如果,x,是一个教师，那么一定存在一个个体,y，x,是,y,的老师，且,y,是一个学生。,80,首先定义谓词：,I（x）：x,是整数。,E（x）：x,是偶数。,O（x）：x,是奇数。此时，该知识可用谓词表示为：（,x）(I(x)E(x)O(x),例3：用谓词逻辑表示知识“所有的整数不是偶数就是奇数”,81,首先定义谓词：,COMPUTER（x）：,表示,x,是计算机系的学生。,CLASSMATE（x，y）：,表示,x,是,y,的同班同学。,LIKE（x，y）：,表示,x,喜欢,y。,例4：用谓词逻辑表示如下知识：王宏是计算机系的一名学生。李明是王宏的同班同学。凡是计算机系的学生都喜欢编程序。,此时，可用谓词公式把上述知识表示为：,COMPUTER（Wanghong）.CLASSMATE（Liming，Wanghong）.（x）（COMPUTER（x)LIKE(x,programing).,82,例：机器人移盒子问题 设在一房间里，,c,处有一个机器人，,a,和,b,处各有一张桌子，分别称为,a,桌和,b,桌，,a,桌子上有一盒子。要求机器人从,c,处出发把盒子从,a,桌上拿到,b,桌上，然后再回到,c,处。请用谓词逻辑来描述机器人的行动过程。,前面讨论了一阶谓词逻辑的基础和逻辑知识表示方法，为加深对这些内容的理解，下面举个逻辑表示法的应用例子。,A,B,C,三.谓词逻辑表示的应用,83,在这个例子中，不仅要用谓词公式来描述事物的状态、位置，而且还要用谓词公式表示动作。为此，需要定义如下谓词公式：,TABLE(x):x,是桌子,EMPTY(y):y,手中是空的,AT(y,z):y,在,z,的附近,HOLDS(y,w):y,拿着,w ON（w，x）：w,在,x,桌面上。,其中：,x,的个体域是：,y,的个体域是：,z,的个体域是：,w,的个体域是：,a，b,robot,a，b，c,box,84,问题的初始状态：,AT（robot,c）EMPTY（robot）ON（box，a）TABLE（a）TABLE（b）,问题的目标状态：,AT（robot，c）EMPTY（robot）ON（box，b）TABLE（a）TABLE（b）,使用规则！,85,机器人行动的目标是把问题的初始状态转换为目标状态，而要实现问题状态的转换需要完成一系列的操作。对于每个操作，一般都可分为条件和动作两个部分：条件部分用来说明执行该操作必须具备的先决条件，动作部分给出了该操作对问题状态的改变情况。条件部分可用谓词公式来表示，动作部分则是通过在执行该操作前的问题状态中删去和增加相应的谓词来实现的 在本问题中，机器人需要执行以下三个操作：,Goto（x，y）：,从,x,处走到,y,处。,Pickup（x）：,在,x,处拿起盒子。,Setdown（x）：,在,x,处放下盒子。,86,这三个操作对应的条件与动作如下：,Goto（x,y）,条件：,AT（robot,x）,动作：删除表：,AT（robot,x）,添加表：,AT（robot,y）,Pickup（x）,条件：,ON（box,x），TABLE（x），AT（robot,x），EMPTY（robot）,动作：删除表：,EMPTY（robot），ON（box，x）,添加表：,HOLDS（robot,box）Setdown（x）,条件：,AT（robot,x），TABLE（x），HOLDS（robot,box）,动作：删除表：,HOLDS（robot,box）,添加表：,EMPTY（robot），ON（box,x）,87,机器人在执行每一操作之前，都需要检查当前状态是否可以满足该操作的先决条件。如果满足，就执行相应的操作，否则就检查下一个操作所要求的先决条件。,作为谓词逻辑知识表示方法的应用，下面给出这个机器人行动规划问题的求解过程。其中，在检查先决条件是否满足时还需要进行变量的置换。,88,状态,l（,初始状态）,AT(robot,c),开始,EMPTY（robot）=ON（box，a）TABLE（a）TABLE（b）,Goto（x，y）=,用,c,代换,x，a,代换,y,状态2,AT（robot,a）EMPTY（robot）ON（box,a）TABLE（a）TABLE（b）,Pickup（x）,用,a,代换,x,状态3,AT（robot，a）HOLDS（robot，box）TABLE（a）TABLE（b）,Goto（x，y）,用,a,代换,x，b