人工智能ppt(新).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能及其应用,制作人：王思文,刘玉奇,于斌,第,1,章绪论,1,、重点掌握,人工智能的几种定义,。,2,、掌握目前,人工智能的三个主要学派,及 其认知观。,3,、一般了解人工智能的主要研究范围和 应用领域。,定义,2,人工智能,(,学科,),人工智能,(,学科,),是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期主要目标在于研究用机器来模仿和执行人脑的某些智力功能，并开发相关理论和技术。,定义,3,人工智能,(,能力,),人工智能,(,能力,),是智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。,人工智能的三大学派及其认知观：,(1),符号主义 认为人工智能起源于数理逻辑。,(2),连接主义 认为人工智能起源于仿生学，特别是对人脑模型的研究。,(3),行为主义 认为人工智能起源于控制论。,第,2,章知识表示方法,重点掌握用状态空间法、问题归约法、谓词逻辑法、语义网络法、框架表示法来描述问题，解决问题；,2.1,状态空间法,许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符,(operator),为基础来表示和求解问题的。,2.1,状态空间法,状态空间法三要点,(1),状态,（,state,）,：表示问题解法中每一步问题状况的数据结构；,(2),算符,（,operator,）：把问题从一种状态变换为另一种状态的手段；,(3),状态空间方法,：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。,2.1,状态空间法,由上可知，对一个问题的状态描述，必须确定,3,件事：,(1),该状态描述方式，特别是初始状态描述；,(2),操作符集合及其对状态描述的作用；,(3),目标状态描述的特性。,例,2,：,(,分油问题,),有,A,、,B,、,C,三个不带刻度的瓶子，分别能装,8kg,5kg,和,3kg,油。如果,A,瓶装满油，,B,和,C,是空瓶，怎样操作三个瓶，使,A,中的油平分两份？,(,假设分油过程中不耗油,),解：第一步：定义问题状态的描述形式：,设,S,k,=(b,c),表示,B,瓶和,C,瓶中的油量的状态。,其中：,b,表示,B,瓶中的油量。,c,表示,C,瓶中的油量。,初始状态集：,S=(0,0),目标状态集：,G=(4,0),第二步：定义操作符：,操作：把瓶子倒满油，或把瓶子的油倒空。,f1,：从,A,瓶往,B,瓶倒油，把,B,瓶倒满。,f2,：从,C,瓶往,B,瓶倒油，把,B,瓶倒满。,f3,：从,A,瓶往,C,瓶倒油，把,C,瓶倒满。,f4,：从,B,瓶往,C,瓶倒油，把,C,瓶倒满。,f5,：从,B,瓶往,A,瓶倒油，把,B,瓶倒空。,f6,：从,B,瓶往,C,瓶倒油，把,B,瓶倒空。,f7,：从,C,瓶往,A,瓶倒油，把,C,瓶倒空。,f8,：从,C,瓶往,B,瓶倒油，把,C,瓶倒空。,第三步：求解过程：,0,3,3,0,2,3,f1,f1,0,0,5,3,1,3,1,0,0,1,5,1,3,3,4,0,4,3,5,2,5,3,0,0,0,2,0,3,2,0,5,0,f1,f3,f4,f7,f8,f6,f5,f3,f1,f4,f7,f5,f3,f2,f8,f3,f8,f3,f2,f5,f8,f3,f8,f7,f7,f6,f1,f4,f7,f4,f5,f1,f7,f1,f1,f1,f7,f5,f5,f7,f5,f6,f7,f5,f1,f3,f3,f1,：从,A,瓶往,B,瓶倒油，,把,B,瓶倒满。,f2,：从,C,瓶往,B,瓶倒油，,把,B,瓶倒满。,f3,：从,A,瓶往,C,瓶倒油，,把,C,瓶倒满。,f4,：从,B,瓶往,C,瓶倒油，,把,C,瓶倒满。,f5,：从,B,瓶往,A,瓶倒油，,把,B,瓶倒空。,f6,：从,B,瓶往,C,瓶倒油，,把,B,瓶倒空。,f7,：从,C,瓶往,A,瓶倒油，,把,C,瓶倒空。,f8,：从,C,瓶往,B,瓶倒油，,把,C,瓶倒空,。,由上述状态空间图，可见从初始状态,(0,1),到目标状态,(4,0),的任何一条通路都是问题的一个解。其中：,f1,f4,f7,f6,f1,f4,f7,是算符最少的解之一。,例：设有,3,个传教士和,3,个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？,解：第一步：定义问题状态的描述形式：,设,S,k,=(M,C,B),表示传教士和野人在河右岸的状态。,其中：,M,表示传教士在右岸的人数。,C,表示野人在右岸的人数。,B,用来表示船是不是在右岸。,(B=1,表示在右岸，,B=0,表示在左岸,),。,初始状态集：,S=(3,3,1),目标状态集：,G=(0,0,0),第二步：定义算符。,算符,R(i,j),表示划船将,i,个传教士和,j,个野人送到左岸的操作。,算符,L(i,j),表示划船从左岸将,i,个传教士和,j,个野人带回右岸的操作。,由于过河的船每次最多载两个人，所以,i+j2,。这样定义的算符集,F,中只可能有如下,10,个算符。,F,：,R(1,0),R(2,0),R(1,1),R(0,1),R(0,2),L(1,0),L(2,0),L(1,1),L(0,1),L(0,2),第三步：求解过程。,1,1,0,2,2,1,3,1,1,0,2,0,3,0,0,R(2,0),L(2,0),R(1,1),L(1,1),L(0,1),R(0,1),L(2,0),R(2,0),2,2,0,3,3,1,3,2,1,3,2,0,3,1,0,L(0,2),R(0,2),R(0,1),L(0,1),L(1,0),R(1,0),L(0,1),R(0,1),L(1,1),R(1,1),L(0,2),R(0,2),1,1,1,0,0,0,0,1,0,0,1,1,0,2,1,R(0,1),L(1,0),L(0,1),R(0,1),R(1,0),L(1,0),R(0,1),L(0,1),R(1,1),L(1,1),R(0,2),L(0,2),0,3,1,R(0,2),L(0,2),由上述状态空间图，可见从初始状态,(3,3,1),到目标状态,(0,0,0),的任何一条通路都是问题的一个解。,其中：,R(1,1),L(1,0),R(0,2),L(0,1),R(2,0),L(1,1),R(2,0),L(0,1),R(0,2),L(1,0),R(1,1),是算符最少的解之一。,2.2,问题归约法,问题归约法的概念,已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。,该方法也就是从目标,(,要解决的问题,),出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。,2.2,问题归约法,问题归约法的组成部分,（,1,）一个初始问题描述；,（,2,）一套把问题变换为子问题的操作符；,（,3,）一套本原问题描述。,2.3,谓词逻辑法,一阶谓词逻辑表示法适于表示确定性的知识。它具有自然性、精确性、严密性及易实现等特点。,2.3,谓词逻辑法,用一阶谓词逻辑法表示知识的步骤如下：,（,1,）定义谓词及个体，确定每个谓词及个体的确切含义。,（,2,）根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。,（,3,）根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。,例,1,：设有下列事实性知识：,张晓辉是一名计算机系的学生，但他不喜欢编程序。李晓鹏比他父亲长得高。,请用谓词公式表示这些知识。,（,1,）定义谓词及个体。,Computer(x):x,是计算机系的学生。,Like(x,y):x,喜欢,y,。,Higher(x,y):x,比,y,长得高。,这里涉及的个体有：张晓辉,(zhangxh),编程序,(programming),李晓鹏,(lixp),，以及函数,father(lixp),表示李晓鹏的父亲。,第二步：将这些个体代入谓词中，得到,Computer(zhangxh),Like(zhangxh,programming),Higher(lixp,father(lixp),第三步：根据语义，用逻辑联结词将它们联结起来，就得到了表示上述知识的谓词公式。,Computer(zhangxh)Like(zhangxh,programming),Higher(lixp,father(lixp),例,2,：,设有下列语句，请用相应的谓词公式把它们表示出来：,（,1,）人人爱劳动。,（,2,）自然数都是大于零的整数。,（,3,）西安市的夏天既干燥又炎热。,（,4,）喜欢读,三国演义,的人必读,水浒,。,（,5,）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。,（,6,）他每天下午都去打篮球。,解：,（,1,）人人爱劳动。,定义谓词如下：,Man(x):x,是人。,Love(x,y):x,爱,y,。,（,x)(Man(x)Love(x,劳动）,（,2,）自然数都是大于等于零的整数。,定义谓词如下：,N(x):x,是自然数。,I(x):x,是整数。,GZ(x):x,大于等于零。,（,x)(N(x)(GZ(x,）,I(x),）,(3),西安市的夏天既干燥又炎热。,定义谓词：,SUMMER(x):x,处于夏天。,DRY(x):x,很干燥。,HOT(x):x,很炎热。,SUMMER(Xian)DRY(Xian)HOT(Xian),（,4,）喜欢读,三国演义,的人必读,水浒,。定义谓词：,MAN(x),：,x,是人。,LIKE(x,y),：,x,喜欢读,y,。,(,x,)(MAN(x)LIKE(x,SANGUOYANYI),LIKE(x,SHUIHU),（,5,）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。,定义谓词：,MAN(x):x,是人。,LIKE(x,y):x,喜欢,y,。,Meihua,表示梅花，,Juhua,表示菊花，,(,x)(MAN(x),LIKE(x,Meihua),(,y)(MAN(y),LIKE(y,Juhua),(,z)(MAN(z),(LIKE(z,Meihua),LIKE(z,Juhua),（,6,）他每天下午都去打篮球。,定义谓词及个体：,设,TIME(x):x,是下午。,PLAY(x,y):x,去打,y,，,Liming,表示李明，,Basketball,表示足球，则,:,（,x,）,TIME(x),PLAY(Liming,Basketball),2.4,语义网络法,语义网络是,1968,年,J.R.Quillian,在研究人类联想记忆时提出的心理学模型。,2.4,语义网络法,语义网络的概念,语义网络是通过概念及其语义关系来表示知识的一种结构化网络图，它由节点和弧线或链线组成，节点用来表示各种概念、事物、属性、情况、动作、状态等，每个节点可以带有若干个属性，以表征其所代表的对象的特性。弧线用于表示节点间的关系，其上的标注则表示被连接的两个节点间的某种语义联系或语义关系。,2.4,语义网络法,语义网络表示知识的方法及步骤,（,a,）确定问题中的所有对象以及各对象的属性。,（,b,）确定所讨论对象间的关系。,（,c,）语义网络中，如果节点间的联系是,ISA/AKO,，则下层节点对上层节点的属性具有继承性。整理同一层节点的共同属性，并抽出这些属性，加入上层节点中，以免造成属性信息的冗余。,（,d,）将各对象作为语义网络的一个节点，而各对象间的关系作为网络中各节点间的弧，连接形成语义网络。节点可代表一个事物或一个具体概念，也可代表某种情况、事件或某一动作。当节点表示某种事件或某一动作时，可以从该节点引出一组向外的弧，用于指出事件的因果或动作的主体及客体。,例,1,、用一个语义网络表示下列命题。,树和草都是植物；,树和草是有根有叶的；,水草是草，且长在水中；,果树是树，且会结果；,苹果树是果树中的一种，它结苹果。,分析：,问题涉及的对象有：,植物、树、草、水草、果树、苹果树,各对象的属性分别为：,树和草的属性：有根、有叶；,水草的属性：长在水中；,果树的属性：会结果；,苹果树的属性：结苹果。,植物,苹果树,水草,果树,草,树,AKO,AKO,AKO,AKO,AKO,有根,有叶,有根,有叶,会结果,结苹果,长在水中,例：用语义网络表示下列知识：,猎狗是一种狗，而狗是一种动物。狗除了动物的有生命、能吃食物、有繁殖能力、能运动外，还有以下特点：身上有毛、有尾巴、四条腿；猎狗的特点是吃肉、奔跑速度快、能狩猎、个头大；而狮子狗也是一种狗，它的特点是吃饲料、身体小、奔跑速度慢、不咬人、供观赏。,解题分析,（,1,）本知识涉及的对象有,4,个：猎狗、狮子狗、狗、动物。猎狗和狮子狗都是一种狗，除了它们本身的属性外，具有狗的一般特性：身上有毛、有尾巴、四条腿。而狗是一种动物，动物所具有的属性它也具有。,（,2,）猎狗与狗之间是一种类属关系，狗和动物之间也是一种类属关系，它们都可以用,AKO,表示。,（,3,）整理各对象节点之间的属性，使上层节点所具有的属性不在下层节点中标出。,（,4,）将各对象作为一个节点，而它们之间的关系作为弧，得到如下图所示的语义网络。,动物,狮子狗,猎狗,狗,AKO,AKO,AKO,身上有毛,有尾巴,有四条腿,跑得快,能狞猎,有生命,吃饲料,能吃食物,有繁殖能力,能运动,个头大,吃肉,个头小,跑得慢,不咬人,供观赏,2.5,框架表示,1974,年，由,Minsky,在“,A framework for representing knowledge”,中提出。,框架是一种描述所论对象属性的数据结构。所论对象可以是一个事物、一个事件或者一个概念。一个框架由若干个“槽”组成，每个“槽”又可划分为若干个“侧面”。一个槽用于描述所论及对象的某一方面的属性，一个侧面用于描述相应属性的一个方面。槽和侧面所具有的属性值分别称为槽值和侧面值。槽值可以是逻辑型或数字型的，具体的值可以是程序、条件、默认值或是一个子框架。,框架表示,用框架表示法表示知识的步骤如下：,（,1,）分析待表达知识中的对象及其属性，对框架中的槽进行合理设置。,（,2,）对各对象间的各种联系进行考察。使用一些常用的名称或根据具体需要定义一些表达联系的槽名，来描述上、下层框架间的联系。,（,3,）对各层对象的“槽”及“侧面”进行合理的组织安排，避免信息描述的重复。,例：用框架表示下述报道的地震事件,【,虚拟新华社,3,月,15,日电,】,昨日,，在,云南玉溪地区,发生,地震,，造成,财产损失约,10,万元,，统计部门,如果需要详细的损失数字,，可,电询,62332931,。另据专家,认为震级,不会超过,4,级,，并认为地,处无人区，不会造成人员伤亡,。,提示：分析概括用下划线标出的要点，经过概念化形成槽（,slot,）、侧面（,facet,）值。特别要注意，,“,值,”,（,value,）、,“,默认值,”,（,default,）、,“,如果需要值,”,（,if-needed,）、,“,如果附加值,”,（,if-added,）的区别与应用，建议采用格式如下，不用的侧面值可删。,Frame,地震,Slot1,：,Value,：,Default,：,If-needed,：,If-added,：,Slot2,：,Value,：,Default,：,If-needed,：,If-added,：,Slot3,：,Value,：,Default,：,If-needed,：,If-added,：,解：,第一步：确定框架的名字和框架的槽。,本报道中，涉及地震的发生时间、地点、财产损失、伤亡人数、震级大小等属性，所以，可将时间、地点、震级、伤亡人数、财产损失等作为槽名。,第二步：分析本报道中各对象间的关系。,由于报道中只涉及地震一件事，所以该步可省略。,框架名：地震,1,时间：,3,月,14,日,地点：云南玉溪地区,震级：,专家经验值：,4,级,准确值：,NIL,伤亡人数：,专家经验值：,0,财产损失：,大约损失：,10,万元,if-needed,：,ASK,（电询,62332931,）,第,3,章搜索推理技术,重点掌握一般图搜索策略和消解原理，掌握各种搜索方法和产生式系统原理，了解规则演绎系统的基本原理，对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解。,第,3,章搜索推理技术,从问题表示到问题的解决，有一个求解的过程。而实现求解的过程，采用的基本方法包括搜索和推理。,第,3,章搜索推理技术,和搜索相对应的知识表示法一般有两种：,状态空间法,：（,S,，,F,，,G,）,与或图表示法：基于一种分解与变换的思想，利用树状结构对复杂问题进行表示，使复杂问题简单化。,第,3,章搜索推理技术,图搜索策略是一种在图中寻找路径的方法。,搜索种类：,盲目搜索：只按预先规定的搜索控制策略进行搜索。,启发式搜索：根据问题本身的特性或搜索过程中产生的一些信息来不断改变和调整搜索的方向。,图搜索过程框图,开始,把,S,放入,OPEN,表,OPEN,为空表？,把第一个节点,(n),从,OPEN,移至,CLOSED,表,n,为目标节点？,把,n,的后继节点放入,OPEN,表的,末端，提供返回节点,n,的指针,修改指针方向,重排,OPEN,表,失败,成功,是,是,否,否,3.2,盲目搜索,盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。宽度优先搜索和深度优先搜索，属于盲目搜索方法。,3.2.1,宽度优先搜索,搜索是以接近起始节点的程度依次扩展节点的，如左图所示。从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,s,L,O,M,F,P,Q,N,F,F,F,例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如右图所示的目标棋局问题：,3.2.2,深度优先搜索,分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的,(,即最深的,),节点。深度相等的节点可以任意排列。我们定义节点的深度如下：,(1),起始节点,(,即根节点,),的深度为,0,。,(2),任何其它节点的深度等于其父辈节点深度加上,1,。,3.2.2,深度优先搜索,有界深度优先搜索,给出一个节点扩展的最大深度,深度界限。,有界,深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路径，等等。,3.2.3,等代价搜索,宽度优先搜索的推广,用来解决从起始状态至目标状态的具有最小代价的路径问题。,从起始节点,S,到任一节点,i,的路径代价记为,g(i),。,从节点,i,到它的后继节点,j,的连接弧线代价记为,c(i,，,j),；,则节点,j,的路径代价为,g(j)=g(i)+c(i,j),。,待扩展的节点是路径代价最小的节点。,3.3,启发式搜索,盲目搜索的不足：效率低，耗费过多的计算空间与时间。,分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法,其主要的差别是,OPEN,表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。,启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。,把利用启发信息的搜索方法叫做启发式搜索方法。,3.3,启发式搜索,启发式搜索策略,启发信息用于决定要扩展的下一个节点，以免象在宽度优先或深度优先搜索中那样盲目地扩展。,这种搜索总是选择,“,最有希望,”,的节点作为下一个被扩展的节点。这种搜索叫做有序搜索,(ordered search),。,3.2.1,有序搜索,有序搜索又称为最好优先搜索，它总是选择最有希望的节点作为下一个要扩展的节点。,估价函数,f,的确定：一个节点的希望程度越大，则其,f,值越小。为此，被选为扩展的节点，是估价函数最小的节点。,f,是从起始节点约束地通过节点,n,而到达目标节点的最小代价路径上的一个估算代价,。,3.3.1,有序搜索,宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。,对于宽度优先搜索，我们选择,f(i),作为节点,i,的深度。对于等代价搜索，,f(i),是从起始节点至节点,i,这段路径的代价。,3.3.2,A,*,算法,A*,算法是一种有序搜索算法，其特点在于对估价函数的定义上。,估价函数,f,：,f(n)=g(n)+h(n),g(n),：就是到目前为止用搜索算法找到的从,S,到,n,的最小路径代价。,h(n),：,依赖于有关问题的领域的启发信息。,从节点,n,到某目标节点的一条最佳路径的代价,的估计。,例：八数码难题,解：,采用估价函数,f(n)=d(n)+W(n),其中：,d(n),是搜索树中节点,n,的深度；,W(n),用来计算对应于节点,n,的数据库中错放的棋子个数。,因此，起始节点棋局的,f,值等于,0+3=3,。,Sg,S,0,3,4,4,5,5,5,6,4,6,4,4,6,3.4,消解原理,重点掌握子句集的求解步骤和消解反演过程，掌握消解推理的规则。,3.4.1,子句集的求取,例、将下列谓词演算公式化为一个子句集,(,x)P(x),(,y)P(y),P(f(x,y),(,y)Q(x,y),P(y),(1)(,x)P(x),(,y)P(y),P(f(x,y),(,y)Q(x,y),P(y),(2)(,x)P(x),(,y)P(y),P(f(x,y),(,y),Q(x,y),P(y),(,x)P(x),(,y)P(y),P(f(x,y),(,y)Q(x,y),P(y),(4)(,x)P(x),(,y)P(y),P(f(x,y),Q(x,g(x),P(g(x),式中,w=g(x),为一个,Skolem,函数,(5)(,x)(,y)P(x),P(y),P(f(x,y),Q(x,g(x),P(g(x),(3)(,x)P(x),(,y)P(y),P(f(x,y),(,w)Q(x,w),P(w),(6)(,x)(,y)P(x),P(y),P(f(x,y),P(x),Q(x,g(x),P(x),P(g(x),(8)P(x),P(y),P(f(x,y),P(x),Q(x,g(x),P(x),P(g(x),(9),更改变量名称，在上述第（,8,）步的,3,个子句中，分别以,x1,x2,x3,代替变量,x,。这种更改变量名称的过程，有时称为变量分离标准化。于是，可以得到下列子句集：,P(x1),P(y),P(f(x1,y),P(x2),Q(x2,g(x2),P(x3),P(g(x3),(7)P(x),P(y),P(f(x,y),P(x),Q(x,g(x),P(x),P(g(x),3.4.2,消解反演求解过程,1,、消解反演,给出一个公式集,S,和目标公式,L,，通过反证或反演来求证目标公式,L,，其证明步骤如下：,(1),否定,L,，得,L,；,(2),把,L,添加到,S,中去；,(3),把新产生的集合,L,，,S,化成子句集；,(4),应用消解原理，力图推导出一个表示矛盾的空子句,NIL,。,例,1,、,判断下列子句集中哪些是不可满足的,分析：子句集中各子句间的关系是合取关系，因此只要有一个子句不可满足，则子句集就是不可满足的。,(1)NIL(,空子句,),是不可满足的。,(2),在子句集中选择合适的子句对其进行消解，若能推出空子句，就说明子句,S,是不可满足的。,(1)S=,PQ,，,Q,，,P,，,P,对子句集,S,进行归结推理：,(1),PQ,(2),Q,(3)P,(4),P,(5)NIL (3)(4),归结,故该子句集是不可满足的。,(2)S=,P(x)Q(f(x),a),，,P(h(y)Q(f(h(y),a),P(z),解：因子句集中无互补对，故在子句集,S,中不存在空子句，故,S,为,可满足的。,例,2,证明,(,x)(P(x),(,Q(x)R(x)(,x,),(P(x)T(x),(x)(T(x)R(x),证明：第一步：先对结论否定并与前提合并得到谓词公式,G,。,G=(,x)(P(x),(,Q(x)R(x)(,x,)(P(x)T(x),(x)(T(x)R(x),第二步：将公式,G,化为子句集。,可将,G,看作是三项的合取，对每一项分别求子句集。,G1,：,(,x)(P(x),(,Q(x)R(x),=,(x)(,P(x),(Q(x)R(x),=(x)(,P(x),Q(x)(,P(x),R(x),所以,S1=,P(x1),Q(x1),P(x2),R(x2),G2:,(,x,)(P(x)T(x),所以,S2=,P(a),T(a),B:,(x)(T(x)R(x),=(x)(,T(x),R(x),所以,S,B,=,T(x),R(x),从而求得公式,G,的子句集：,S=S1S2S,B,=,P(x1),Q(x1),P(x2),R(x2),P(a),T(a),T(x3),R(x3),第三步：例用消解原理，对子句集,S,进行消解,P(x2)R(x2),P(a),R(a),T(x3),R(x3),T(a),1,=a/x2,T(a),2,=a/x3,NIL,由此得出子句集,S,是不可满足的，因此公式,G,也是不可满足的。从而命题得证。,例,3,某公司招聘人员，,A,、,B,、,C,三人应试，经面试后，公司有如下想法：,(1),三人中至少录用一人；,(2),如果录用,A,而不录用,B,，则一定录用,C,；,(3),如果录用,B,，则一定录用,C,。,求证：公司一定录取,C,。,证：定义：,P(x),表示录用,x,。,则前提为,(1)P(A)P(B)P(C),(2)(P(A)(,P(B)=P(C),(3)P(B)=P(C),则结论为,P(C),将前提化为子句集：,(1),P(A)P(B)P(C),(2),P(A)P(B)P(C),(3),P(B),P(C),将结论否定并化为子句集：,(4),P(C),利用消解原理，对子句集进行消解：,P(A)P(B)P(C),P(A)P(B)P(C),P(B)P(C),P(B)P(C),P(C),P(C),NIL,故证得结论：公司一定录取,C,2,、反演求解过程,步骤：,(1),把已知前提用谓词公式表示出来，并化为相应的子句集,S,。,(,2,),把,待求解的问题也用谓词公式表示出来，然后把它的否定与谓词,ANSWER,构成析取式。,(,3,),把第,(2),步得到的析取式化为子句集，并入子句集,S,中，得到子句集,S,。,(4),对子句集,S,应用,消解,原理进行消解。,(,5,),若得答案,ANSWER,，则答案就在,ANSWER,中,。,例,1,：,应用消解反演求解如下问题：,“如果无论约翰,(John),到哪里去，菲多,(Fido),也就去那里，那么如果约翰在学校里，菲多在哪里呢,?”,解：定义谓词：,AT,（,x,y,）表示,x,在,y,那里。,则前提为：,(,x)(AT(JOHN,x),AT,(FIDO,x),和,AT(JOHN,SCHOOL),目标公式：,(,x,)AT(FIDO,x),目标公式否定为：,(,x)(,AT(FIDO,x),其子句形为：,AT(FIDO,x),对本例应用消解反演过程：,（,1,）目标公式否定的子句形为：,AT(FIDO,x),将它与谓词,ANSWER,构成析取式：,AT(FIDO,x)ANSWER(FIDO,x),（,2,）用下图的反演树进行消解，并在根部得到子句：,A,NSWER,(FIDO,SCHOOL),AT(FIDO,x)ANSWER(FIDO,x),AT(JOHN,y)AT(FIDO,y),AT(JOHN,x)ANSWER(FIDO,x),AT(JOHN,SCHOOL),ANSWER(FIDO,SCHOOL),1=x/y,2=SCHOOL/x,例,2,某公司招聘人员，,A,、,B,、,C,三人应试，经面试后，公司有如下想法：,(1),三人中至少录用一人；,(2),如果录用,A,而不录用,B,，则一定录用,C,；,(3),如果录用,B,，则一定录用,C,。,求公司录用谁？,解：定义：,P(x),表示录用,x,。,则前提为,(1)P(A)P(B)P(C),(2)(P(A)(,P(B)=P(C),(3)P(B)=P(C),则结论为,P(x),将前提化为子句集：,(1),P(A)P(B)P(C),(2),P(A)P(B)P(C),(3),P(B),P(C),将结论否定与谓词,ANSWER,构成析取式：,(4),P(x)ANSWER(x),利用消解原理，对子句集进行消解：,P(A)P(B)P(C),P(A)P(B)P(C),P(B)P(C),P(B)P(C),P(C),P(x)ANSWER(x),ANSWER(C),=C/x,可见公司一定录取,C,例,3,已知（,1,）王是李的老师,（,2,）李是张的同学,（,3,）如果,x,与,y,是同学，则,x,的老师也是,y,的老师。,求：张的老师是谁？,解：令,T(x,y):x,是,y,的老师；,C(x,y),：,x,是,y,的同学,则,已知的三个事实可解释为下列公式集,T(Wang,Li),C(Li,Zhang),(x)(y)(z)C(x,y)T(z,x)=T(z,y),目标公式：,(,x)T(x,Zhang),将上述事实化为子句集：,T(Wang,Li),C(Li,Zhang),C(x,y),T(z,x),T(z,y),目标公式否定的子句形为：,T(x,Zhang),将它与谓词,ANSWER,构成析取式：,T(w,Zhang)ANSWER(w,Zhang),用下图的反演树进行消解，并在根部得到子句,：,C(x,y),T(z,x)T(z,y),T(Wang,Li),C(Li,y)T(Wang,y),C(Li,Zhang),T(Wang,Zhang),1,=Wang/z,Li/x,T(w,Zhang)ANSWER(w,Zhang),2,=Zhang/y,ANSWER(Wang,Zhang),3,=Wang/w,3.5,产生式系统,1,、产生式系统的组成,产生式系统由,3,个部分组成，即总数据库,(,或全局数据库,),、产生式规则和控制策略，,总数据库又称为综合数据库、上下文、黑板等，用于存放求解过程中各种当前信息的数据结构，如问题是的初始状态、事实或证据、中间推理结论和最后结果等。,产生式规则是一个规则库，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。,其基本形式为,IF,前提,THEN,结论,控制策略的作用是说明下一步应该选用什么规则。,2,、例：设有八数码难题：,请用产生式规则表示移动小方块的操作。,初始状态,目标状态,解：,1,）建立棋盘变换的产生式规则。,如果把棋盘的每一布局看作是一个状态矩阵，本题就变成了从初始状态矩阵到目标状态矩阵的一种变化。,设,S,ij,为状态矩阵的第,i,行和第,j,列的数码，其中,3i,j1,。,i,0,j,0,表示空格所在的行和列。如果在状态矩阵中用,0,来表示空格的话，则建立如下四条产生式规则：,R1:if(j,0,-11)then begin,S,i0j0,:=S,i0(j0-1),;,S,i0(j0-1),:=0 end,空格左移,R2:if(i,0,-11)then begin,S,i0j0,:=S,(i0-1)j0,;,S,(i0-1)j0,:=0 end,空格上移,R3:if(j,0,+13)then begin,S,i0j0,:=S,i0(j0+1),;,S,i0(j0+1),:=0 end,空格右移,R4:if(i,0,+13)then begin,S,i0j0,:=S,(i0+1)j0,;,S,(i0+1)j0,:=0 end,空格下移,2,）建立综合数据库,将棋盘的布局表示为状态矩阵的形式存入综合数据库。,例如，初始布局和目标布局以矩阵形式表示为：,综合数据库中，存放着初始状态矩阵和目标状态矩阵以及变换过程中的中间矩阵。,3,）推理求解,在进行推理求解时，可能会有多条产生式规则的条件部分和综合数据库中的已有事实相符，这样就有可能激活多条规则。,究竟采用哪一条规则作为启用规则规则，这就是冲突解决策略问题。,在本题中采用一个启发式函数,f(n)=d(n)+W(n),其中：,d(n),是搜索树中节点,n,的深度；,W(n),用来计算对应于节点,n,的数据库中错放的棋子个数。,在综合数据库中的初始矩阵，能满足规则,R1,，,R2,，,R3,，,R4,的条件，所以有四条匹配规则。利用启发函数决定哪一条规则为启用规则。因为规则,R1,的启发式函数值,h(x)=4,，规则,R2,的启发式函数值,h(x)=4,规则,R3,的启发式函数值,h(x)=5,规则,R4,的启发式函数值,h(x)=5,。在这里,R1,与,R2,所得到的新状态与目标状态差距最小，且都为,4,，而在,R1,与,R2,中再选择一条规则作为启用规则，在这里我们使用规则的排列顺序，首先选择,R1,，所以启用规则,R1,，依次类推。,可以得到到达目标状态的规则执行序列如下：,R1,，,R2,，,R1,，,R4,，,R3,其执行过程如下图所示。,图中节点旁所标数字为,h(x),的值，箭头上所标为启用的规则。,Sg,S,0,3,4,4,5,5,5,6,4,6,4,4,6,R1,R2,R3,R4,R2,R4,R1,R3,R4,R3,R4,