（精选幻灯片）人工智能_第三搜索推理技术.ppt

第三搜索推理技术,从问题的表示到问题的解决是一个求解的过程，也就是搜索过程。在这一过程中，采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。本章首先介绍图搜索策略的一般过程，接着讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理，然后研究一些比较新的能够求解比较复杂问题的推理技术。,1,第三确定性推理,3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4消解原理3.5规则演绎系统3.6产生式系统3.7非单调推理,2,第三搜索推理技术,一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。,Sg,3,3.1图搜索策略,3.1图搜索策略一.问题描述(图搜索问题描述)把求解问题看成一个状态图，求初始节点到目标节点的路径。,4,3.1.1图搜索策略,回顾一下图论中几个术语的含义。节点深度：根节点的深度为0,其他节点的深度规定为父节点深度加1,即dn+1=dn+1。路径：设一节点序列为(n0、n1,ni,nk),对i=1,2,k,若节点ni-1都具有一个后继节点ni,则该节点序列称为节点n0到节点nK长度为k的一条路径。路径耗散值：令C(ni,nj)为节点ni到nj这段路径(或弧线)的耗散值,一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。路径耗散值可按如下式递归公式计算:C(ni,t)=C(ni,nj)+C(nj,t)C(nj,t)为nit这条路径的耗散值。,5,3.1.1图搜索策略,回顾一下图论中几个术语的含义。扩展一个节点:后继节点操作符(相当于可应用规则)作用到节点(对应于某一状态描述)上,生成出其所有后继节点(新状态),并给出连接弧线的耗散值(相当于使用规则的代价),这个过程叫做扩展一个节点。扩展节点可使定义的隐含图生成为显式表示的状态空间图。,6,3.1.1图搜索策略,二.图搜索过程S起始结点G搜索图OPEN表存放未扩展节点CLOSED表存放已扩展节点1.图搜索过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP:若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n。,7,3.1.1图搜索策略,(5)若n为一目标节点n，则有解并成功退出。此解是追踪图G中沿着指针从n到s这条路径而得到的。(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继结点添入图G中。(7)对于那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已经在CLOSED表上的每一个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP,8,3.1.1图搜索策略,举例：,S,A,B,C,D,E,M,F,S,1.SOPEN(S)CLOSED()2.AOPEN(A,B)CLOSED(S)3.BOPRN(B,C,D)CLOSED(S,A)4.COPEN(C,D,E)CLOSED(S,A,B)5.DOPEN(D,E)CLOSED(S,A,B,C)6.EOPEN(E,M,F)CLOSED(S,A,B,C,D)7.N求解,目标节点,2,3,5,6,4,7,3,8,4,9,3.1.1图搜索策略,2.流程图,开始,把S放表入OPEN表中,OPEN表为空表,把第一个节点n从OPEN表移至CLOSED表,N为目标节点,把节点n的后继节点放入OPEN表，提供返回节点n的指针,修正指针方向,重排OPEN表,失败,成功,是,是,10,3.1.1图搜索策略,11,3.1.1图搜索策略,12,3.1.1图搜索策略,13,3.1.1图搜索策略,14,3.1.1图搜索策略,15,3.1.1图搜索策略,3.遗留问题n的某后继节点已在OPEN表中或CLOSED表中有了是否需要修改指针，对已存在的后继节点按什么方式重排OPEN表,宽度优先搜索深度优先搜索等代价搜索,搜索控制方法,16,3.2盲目搜索,盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索，又叫做无信息搜索。一般只适用于求解比较简单的问题。典型的盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜索方法。,17,3.2盲目搜索,一.宽度优先搜索(一).宽度优先搜索以接近起始节点的程度依次扩展节点,从根结点开始,每次都要扫遍同层的各个结点,若没有找到目标,则再往下一层扫描(扫描下一层的所有子结点),直到找到目标或没有找到目标退出系统(此种属于没有解的情况)。,18,3.2盲目搜索,(二).流程算法扩展节点：把它的后继节点放入OPEN表的末端1.搜索算法把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)如果OPEN表是一个空表，则没有解，失败退出；否则继续。把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。扩展节点n。如果没有后继节点，则转向第步。把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第步,19,3.2盲目搜索,2.流程图,开始,把S放表入OPEN表,OPEN表为空表,把第一个节点n从OPEN表移至CLOSED表,把节点n的后继节点放入OPEN表的末端，提供返回节点n的指针,失败,成功,是,是,是否有任何后继节点为目标节点？,20,3.2盲目搜索,3.举例：八数码难题初始棋局目标棋局,28314765,12384765,28314765,23184765,28316475,28314765,28314765,83214765,81324765,28374615,28371465,12378465,12384756,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,25,26,27,28,S0,Sg,21,3.2盲目搜索,(三).宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法,22,3.2盲目搜索,二深度优先搜索(一).深度优先搜索总是先扩展最新产生的节点,23,3.2盲目搜索,(二).OPEN表的排列算法对于许多问题，其状态搜索树的深度可能为无限深或者可能至少要比某个可接受的解答序列的已知深度上限还要深，为了避免考虑太长的路径：1.深度界限：规定的一个节点扩展的最大深度2.扩展节点：若不等于最大深度，将后裔节点放入OPEN表的前头。,24,3.2盲目搜索,3.搜索算法把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)如果OPEN表是一个空表，则失败退出。把第一个节点(节点n)从OPEN表移到CLOSED表。如果节点n的深度等于最大深度，则转向第步。扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2.)如果后继节点中有任一个为目标节点，则求得一个解答，成功退出；否则转向第步,25,3.2盲目搜索,4.流程图,开始,把S放表入OPEN表,OPEN表为空表,把OPEN表中第一个节点n移至CLOSED表,扩展节点n，把后裔放入OPEN表的前头,失败,成功,是,是,是否有任何后继节点为目标节点？,S是否为目标节点？,节点n的深度是否等于深度界限？,是,成功,是,否,26,3.2盲目搜索,5.举例,27,3.2盲目搜索,(三).深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法,28,3.2盲目搜索,三、等代价搜索(一).等代价搜索1.问题的提出：有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解，这可通过代价来描述2.代价(1)从节点I到它的后继节点j的连线弧线代价记为C(i,j).(2)从起始节点到任一节点i的路径代价记为g(i).3.等价搜索每次扩展的是代价最小的节点。,29,3.2盲目搜索,(二).扩展算法扩展节点I对于节点I的每个后继节点，计算g(j)=g(i)+c(i,j)按g(j)升序插入到OPEN表中。,30,3.3启发式搜索,启发式搜索是利用问题拥有的启发信息来引导搜索,达到减少搜索范围,降低问题复杂度的目的,这种利用启发信息的搜索过程都称为启发式搜索方法。,31,3.3启发式搜索,3.3.1启发式搜索策略一.启发信息1.启发信息：具体问题领域的可用来简化搜索的特性信息2.种类：(1)用于决定要扩展的下一个节点(以免象宽度优先或深度优先搜索中那样盲目地扩展)(2)在扩展一个节点的过程中，用于决定要生成那一个或那几个后继节点(以免盲目地同时生成所有可能的节点)(3)用于决定某些应该从搜索树中抛弃或修剪的节点,32,3.3启发式搜索,3.3.1启发式搜索策略二.启发式搜索1.启发式搜索：利用启发信息的搜索方法。本节只讨论利用第一种启发信息的搜索2.有序搜索：利用第一种启发信息，总是选择“最有希望”的节点作为下一个被扩展的节点。,33,3.3启发式搜索,3.3.2估价函数一.估价函数用来估算节点希望程度的量度二.估价函数考虑因素1.起始节点到此节点的距离(以减少搜索工作量为出发点)2.经过此节点到达目标的代价(以最小代价为出发点)三.估价函数表示f(n)我们可以用f函数来排列GRAPHSEARCH第8步中OPEN表上的节点。,34,3.3启发式搜索,3.3.3有序搜索一.有序搜索算法,开始,把S放表入OPEN表，计算f(s),OPEN=NIL?,选取OPEN表中f值最小的节点I放入CLOSED表,扩展i,得后继节点j，计算f(j),提供返回i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针,失败,成功,是,是,i=Sg,35,3.3启发式搜索,其中扩展节点i有下列几步对有i的每一个后继节点j:1.计算f(j)2.如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。3.如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则以此新值取代旧值从j指向i,而不是指向它的父辈节点。如果节点j在CLOSED表中，则把它移回OPEN表。,36,3.3启发式搜索,有序搜索的有效性直接取决于f的选择二.举例八数码难题起始节点目标节点选用的估价函数f(n)=d(n)+w(n)d(n)是搜索树中节点n的深度W(n)用来计算对应于节点n中错放棋子个数这样起始节点f=0+4=4,28316475,1234765,37,38,3.3启发式搜索,1.OPEN=CLOSED=2.OPEN=、CLOSED=3.OPEN=、CLOSED=、4.OPEN=、CLOSED=、5.OPEN=、CLOSED=、6.OPEN=、CLOSED=、7.OPEN=、CLOSED=、,39,3.3启发式搜索,三.小结1.宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索，我们选择f(i)作为节点i的深度。对于等代价搜索，f(i)是从起始节点至节点i这段路径的代价。2.有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意。,40,3.3启发式搜索,三.小结3.节点希望量度以及某个具体估价函数的合适程度取决于手头的问题情况。根据所要求的解答类型，可以把问题分为下列三种：假设状态空间含有几条不同代价的解答路径，其问题是要求得最优解答。类似第一种情况，但难度相当大，实践上不可能。处理该种情况的关键问题：如何通过适当的搜索试验找到好的(但不是最优的)解答；如何限制搜索试验的范围和所产生的解答与最优解答的差异程度。不考虑解答的最优化；或者只存在一个解，或者任何一个解与其他解一样好。问题是如何使搜索试验的次数最少，而不是像第二种情况那样试图使某些搜索试验和解答代价的综合指标最小。,41,3.3启发式搜索,3.3.4A*算法一.符号定义k(ni,nj):任意两点ni和nj之间最小代价路径的实际代价h*(n):节点n到目标集合ti上所有k(n,tj)中最小的一个g*(n)=k(s,n)f*(n)=g*(n)+h*(n),42,3.3启发式搜索,3.3.4A*算法二.定义设函数f是f*的一个估计f(n)=g(n)+h(n)其中g(n)是g*(n)的估计、h(n)是h*(n)的估计1.A算法：如果在图搜索的第8步，依据f(n)=g(n)+h(n)重排OPEN表在A算法中，如果对所有x存在h(x)h*(n)，则称h(x)为h*(n)的下界2.A*算法采用h*(n)的下界h(x)为启发函数的A算法,43,3.3启发式搜索,三.A*算法选取f最小的节点扩展对每个后继节点：1.建立后继节点返回到该节点的指针2.计算g(suc)=g(bes)+g(best,suc)3.若suc已在OPEN表，suc=old，若g(suc)g(old)，重新确定OLD的父辈节点为BES，并修改g值和f值4.若suc已在CLOSE表,suc=old，若g(suc)E1和E2=E3=E1E2）在证明某个逻辑式为真时，先假设它为假，再与已知事实进行消解，得出矛盾，由此证明了逻辑式。即反证思想。,49,3.4消解原理,消解原理由J.A.Robinson由1965年提出。与演绎法完全不同，新的逻辑演算算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而消解方法是自动推理、自动推导证明用的。（“数学定理机器证明”）,50,3.4消解原理,消解过程将命题写成合取范式求出子句集对子句集使用消解推理规则消解式作为新子句参加消解消解式为空子句，S是不可满足的（矛盾），原命题成立。,51,3.4消解原理,3.4.1化为子句集3.4.2消解推理规则3.4.3含有变量的消解式3.4.4消解反演求解过程3.4.5含状态项的回答语句的求取,52,3.4.1化为子句集,例：(z)(x)(y)(P(x)Q(x)R(y)U(z)1.消蕴涵符理论根据：ab=ab(z)(x)(y)(P(x)Q(x)R(y)U(z)2.移动否定符减少否定符号的辖域(反复应用狄.摸根定律)理论根据：(ab)=ab(ab)=ab(a)=a(x)P(x)=(x)P(x)(x)P(x)=(x)P(x)(z)(x)(y)(P(x)Q(x)R(y)U(z),53,3.4.1化为子句集,3.变量标准化(让每个量词有自己唯一的哑元)即：对于不同的约束，对应于不同的变量(x)A(x)(x)B(x)=(x)A(x)(y)B(y)4.量词左移(x)A(x)(y)B(y)=(x)(y)A(x)B(y)5.消存在量词(skolem化）原则：对于一个受存在量词约束的变量，如果他不受全程量词约束，则该变量用一个常量代替，如果他受全程量词约束，则该变量用一个skolem函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)若消去的存在量词不在任何一个全程量词的辖域内，skolem函数即是常数,54,3.3.1化为子句集,6.化为合取范式即(ab)(cd)(ef)的形式(x)(P(x)Q(x)R(f(x)U(a)=(x)(P(x)Q(x)R(f(x)U(a)=(x)P(x)R(f(x)U(a)Q(x)R(f(x)U(a)7.隐去全程量词P(x)R(f(x)U(a)Q(x)R(f(x)U(a),55,3.4.1化为子句集,8.消去连词符号，表示为子句集用A，B代替ABP(x)R(f(x)U(a),Q(x)R(f(x)U(a)最后得到一个有限集，其中每个公式是文字的析取，称作一个子句。9.变量标准化（变量换名）P(x1)R(f(x1)U(a),Q(x2)R(f(x2)U(a)使一个变量符号不出现在一个以上的子句中,56,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)3.(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)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)前缀母式6.(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),57,3.4.1化为子句集,7.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.P(x1)P(y)P(f(x1,y)P(x2)Q(x2,g(x2)P(x3)P(g(x3)可以证明，如果公式x在逻辑上遵循公式集s，那么x在逻辑上也遵循由s的公式变换成的子句集，因此子句是表示公式的一个完善的一般形式。在定理证明系统中，消解作为推理规则使用时，从公式集来证明某个定理，首先要把公式集化为子句集。,58,3.4.2消解推理规则,L1、L2分别是原子公式，具有相同的谓词符号，但一般具有不同的变量。已知：L1、L2，如果L1和L2具有最一般合一者，可以导出(),消解式,59,3.4.2消解推理规则,1.假言推理父辈子句PPQ(P=Q)消解式Q2.合并父辈子句PQPQ消解式QQ=Q,60,3.4.2消解推理规则,3.重言式父辈子句PQPQ消解式QQPP4.空子句(矛盾)父辈子句PP消解式NIL,61,3.4.2消解推理规则,5.链式(三段论)父辈子句PQ(P=Q)QR(Q=P)消解式PR(P=R),62,3.4.3含有变量的消解式,设li是Li的一个子集，mi是Mi的一个子集，使得集li和mi的并集存在最一般的合一者，消解两个子句Li和Mi，得到的消解式Li-liMi-mi注意：消解两个子句时，因为有多种选择li和mi的方法，可能有一个以上的消解式，但最多有有限个消解式。,63,3.4.3含有变量的消解式,例：两个子句Px，f(A)Px，f(y)Q(y)Pz，f(A)Q(z)(1)取li=Px，f(A)mi=Pz，f(A)得消解式Pz，f(y)Q(z)Q(y)(2)取li=Q(y)mi=Q(z)得消解式Px，f(A)Px，f(y)Py，f(A)进一步消解得消解式为Py，f(y),64,3.4.4消解反演求解过程,要证明某个命题，其目标公式被否定并化成子句形，添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，从而使定理得到证明。,65,3.4.4消解反演求解过程,一.消解反演公式集S，目标公式L，通过反演求证目标公式L.证明步骤：1.否定L，得L;2.把L添加到S中去；3.把新产生的集合L，S化成子句集；4.应用消解原理，力图推导出一个表示矛盾的空子句；,66,3.4.4消解反演求解过程,举例：前提：每个储蓄钱的人都获得利息结论：如果没有利息，那么就没有人去储蓄钱令：S(x,y)表示(x储蓄y)M(x)表示“x是钱”L(x)表示“x是利息”E(x,y)表示“x获得y”证明：前提：(x)(y)(S(x,y)M(y)=(y)(I(y)E(x,y)结论：(x)I(x)=(x)(y)(M(y)=S(x,y),67,3.4.4消解反演求解过程,前提：(x)(y)(S(x,y)M(y)=(y)(I(y)E(x,y)化为子句形(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)令y=f(x)为skolem函数，则可得子句形如下(1)S(x,y)M(y)I(f(x)(2)S(x,y)M(y)E(x,f(x),68,3.4.4消解反演求解过程,结论的否定：(x)I(x)=(x)(y)(M(y)=S(x,y)化为子句形(x)I(x)(x)(y)(M(y)S(x,y)(x)I(x)(x)(y)(M(y)S(x,y)(x)(I(x)(x)(y)(M(y)S(x,y)(x)(I(x)(x)(y)(M(y)S(x,y)(x)(I(x)(x)(y)(M(y)S(x,y)(x)(I(x)(x)(y)(M(y)S(x,y)变量分离标准化后得子句：(3)I(z)(4)S(a,b)(5)M(b),69,3.4.4消解反演求解过程,消解过程(1)S(x,y)M(y)I(f(x)(3)I(z)f(x)/z,(6)S(x,y)M(y)(4)S(a,b)a/x,b/y,(7)M(b)(5)M(b),NIL,储蓄问题反演树,70,3.4.4消解反演求解过程,例2：设公理集：(x)(R(x)L(x)(x)(D(x)L(x)(x)(D(x)I(x)求证：(x)(I(x)R(x)化子句集：(x)(R(x)L(x)=(x)(R(x)L(x)=R(x)L(x)(1),71,3.4.4消解反演求解过程,(x)(D(x)L(x)=(x)(D(x)L(x)=D(x)L(x)(2)(x)(D(x)I(x)=D(A)I(A)=D(A)(3)I(A)(4),72,3.4.4消解反演求解过程,目标求反：(x)(I(x)R(x)=(x)(I(x)R(x)=(x)(I(x)R(x)=I(x)R(x)(5)换名后得字句集：R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5),73,例题得归结树,R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5),I(A),I(x5)R(x5),R(A),A/x5,R(x1)L(x1),L(A),A/x1,D(x2)L(x2),D(A),A/x2,D(A),nil,74,3.4.4消解反演求解过程,二.反演求解过程从反演树求取对某个问题的答案过程：1.由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去;2.按照反演树，执行和以前相同的消解，直到根部得到某个子句止；3.用根部的子句作为一个回答语句；根部的子句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。,75,3.4.4消解反演求解过程,举例：如果无论约翰到哪里去，菲多也就去那里，那么如果约翰在学校里，菲多在哪里呢？公式集：(x)AT(John,x)=AT(Fido,x)AT(John,school)通过证明(x)(AT(Fido,x)在逻辑上遵循S,寻求一个存在x的例，就能解决“菲多在哪里”的问题目标公式的否定：(x)(AT(Fido,x),76,3.4.4消解反演求解过程,目标公式的否定：(x)(AT(Fido,x)子句形为AT(Fido,x)用反演树进行消解,AT(Fido,x),AT(John,x)AT(Fido,x),AT(John,x),AT(John,school),Nil,77,3.4.4消解反演求解过程,目标公式的否定：(x)(AT(Fido,x)子句形为AT(Fido,x)重言式为AT(Fido,x)AT(Fido,x)用反演树进行消解,AT(Fido,x)AT(Fido,x),AT(John,x)AT(Fido,x),AT(John,x)AT(Fido,x),AT(John,school),AT(Fido,school),在根部得到子句AT(Fido,school)，它就是这个问题的合适答案。,78,3.4.4消解反演求解过程,提取回答的过程先进行归结，证明结论的正确性；用重言式代替结论求反得到的子句；按照证明过程，进行归结；最后，在原来为空的地方，得到的就是提取的回答。修改后的证明树称为修改证明树,79,作业,80,作业,证明：前提：1)小李(Li)喜欢容易(Easy)的课程(Course)。x(Course(x)Easy(x)Like(Li,x)2)小李不喜欢难(Difficult)的课程.x(Course(x)Difficult(x)Like(Li,x)3)工程类(Eng)课程都是难的。x(Course(x)Eng(x)Difficult(x)4)物理类(Phy)课程都是容易的。x(Course(x)Phy(x)Easy(x)5)小吴(Wu)喜欢所有小李不喜欢的课程。x(Course(x)Like(Li,x)Like(Wu,x)6)Phy200是物理类课程。Course(Phy200)Phy(Phy200)7)Eng300是工程类课程Course(Eng300)Eng(Eng300),81,作业,化为子句集：Course(x1)Easy(x1)Like(Li,x1)(1)Course(x2)Difficult(x2)Like(Li,x2)(2)Course(x3)Eng(x3)Difficult(x3)(3)Course(x4)Phy(x4)Easy(x4)(4)Course(x5)Like(Li,x5)Like(Wu,x5)(5)Course(Phy200)(6)Phy(Phy200)(7)Course(Eng300)(8)Eng(Eng300)(9)目标：2小吴喜欢Eng300课程Like(Wu,Eng300)目标取反：Like(Wu,Eng300)（10）,82,作业,归结过程：,Like(Wu,Eng300)(10),Course(x5)Like(Li,x5)Like(Wu,x5)(5),Course(Eng300)Like(Li,Eng300),Course(x2)Difficult(x2)Like(Li,x2)(2),Course(Eng300)Difficult(Eng300),Course(x3)Eng(x3)Difficult(x3)(3),Course(Eng300)Eng(Eng300),Course(Eng300)(8),Eng(Eng300),Eng(Eng300)(9),NIL,目标1得证.,83,作业,目标2小李喜欢什么课程xLike(Li,x)目标取反：Like(li,x)（11）归结过程,Course(x1)Easy(x1)Like(Li,x1)(1),Like(li,x)（11）,Course(x1)Easy(x1),Course(x4)Phy(x4)Easy(x4)(4),Course(x4)Phy(x4),Course(Phy200)(6),Phy(Phy200),Phy(Phy200)(7),Nil,84,作业,反演求解：,Course(x1)Easy(x1)Like(Li,x1)(1),Like(li,x)Like(li,x),Course(x1)Easy(x1)Like(li,x1),Course(x4)Phy(x4)Easy(x4)(4),Course(x4)Phy(x4)Like(li,x4),Course(Phy200)(6),Phy(Phy200)Like(li,Phy200),Phy(Phy200)(7),Like(li,Phy200),由此得出小李喜欢Phy200.,85,3.5规则演绎系统,基于规则的问题求解系统用下述规则来建立：IfThen其中：if可能与某断言集中的一个或多个断言匹配有时then部分用于产生新断言，这种基于规则的系统叫做规则演义系统；有时then部分用于规定动作，这种系统叫做产生式系统。,86,3.5规则演绎系统,将有关问题的知识和信息划分成规则与事实两种类型。规则有包含蕴涵形式的表达式表示，事实由无蕴涵形式的表达式表示，这种推理系统称为基于规则的演绎系统。,87,3.5.1规则正向演绎系统,正向推理：从if部分向then部分推理的过程,事实,目标,规则,88,3.5.1规则正向演绎系统,一.事实表达式的与或形变换二.事实表达式的与或图表示三.与或图的F规则变换四.作为终止条件的目标公式,89,一.事实表达式的与或形变换,1.事实化为与或形表示与或形无量词约束否定符只作用于单个文字只有“与”、“或”,90,一.事实表达式的与或形变换,2.变换过程消去蕴涵符“”减少否定符号“”的辖域进行skolem化和前束化对变量标准化、使得同一变量不出现在事实表达式的不同主要合取式中删除全程量词,91,一.事实表达式的与或形变换,例：事实表达式(u)(v)Q(v,u)(R(v)V(P(v)S(u,v)减少否定符号“”的辖域(u)(v)Q(v,u)(R(v)(P(v)VS(u,v)进行skolem化Q(v,A)(R(v)(P(v)VS(A,v)对变量标准化Q(w,A)(R(v)(P(v)VS(A,v),92,二.事实表达式的与或图表示,将表达式作为节点，子表达式作为后继节点，若为析取关系，要用“K”线连接符来标注，叶节点均由表达式中的文字来标注。,93,二.事实表达式的与或图表示,例：Q(w,A)(R(v)P(v)S(A,v),Q(w,A)(R(v)P(v)S(A,v),Q(w,A),(R(v)P(v)S(A,v),R(v)P(v),S(A,v),R(v),P(v),子句集：Q(w,A)、R(v)S(A,v)、P(v)S(A,v)因此，可把与或图看做是对子句集的简洁表示一般把事实表达式的与或图表示倒过来画，根节点在最下面、后继节点在上,94,三.与或图的F规则变换,1.规则的形式LW其中，L是单文字，W是与或形且假设出现在蕴涵式中的任何变量都有全称量词作用于整个蕴涵式如果不符合要求，可转化为符合要求步骤：暂时消去蕴涵符号减少否定辖域进行Skolem化把所有全程量词移至前面后消去恢复蕴涵式,95,三.与或图的F规则变换,例：(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)(u)(P(x,y,z)Q(x,u)=P(x,y,f(x,y)Q(x,u)=P(x,y,f(x,y)Q(x,u)P(x1,y1,f(x1,y1)Q(x1,u1)换名例：(L1L2)W=L1W和L2W,96,三.与或图的F规则变换,2.将F规则作用到与或图上将LW形式的规则应用到标有L标记的叶节点的与或图上，得到一个新的与或图例如：下列与或图,(PQ)R)(S(TU),(PQ)R,S(TU),PQ,R,S,TU,P,Q,T,U,97,三.与或图的F规则变换,应用S(XY)Z规则后得到的与或图,(PQ)R)(S(TU),(PQ)R,S(TU),PQ,R,S,TU,P,Q,T,U,S,XY,Z,X,Y,PQSPQTUSRRTUPQXZPQYZRXZRYZ,规则的子句：S(XY)Z=S(XY)Z=SXZSYZ,98,四.作为终止条件的目标公式,目标公式为文字析取形式目标文字和规则可用来对与或图添加后继结点，当一个目标文字与该图中文字节点n上的一个文字相匹配时，对该图添这个节点n的新后裔，并标记为匹配的目标文字，用匹配弧接到它的父辈节点上直到包含有终止在目标节点上的解图时，系统便成功地结束。例如：事实：AB规则集：ACDBEG目标公式：CG,99,四.作为终止条件的目标公式,正向演绎证明；当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。,AB,A,B,A,C,D,B,E,G,C,G,目标,100,五.含有变量的情况,事实表达式化成与或形规则化成LW的形式，其中L为单文字目标用Skolem化的对偶形式，即消去全称量词，用Skolem函数代替保留存在量词对析取元作变量换名例：(y)(x)(P(x,y)Q(x,y)=(y)(P(f(y),y)Q(f(y),y)=P(f(y1),y1)Q(f(y2),y2)换名规则每使用一次，都要进行一次换名,101,五.含有变量的情况,例：事实：P(x,y)(Q(x,A)R(B,y)规则集：P(A,B)(S(A)X(B)Q(B,A)U(A)R(B,B)V(B)目标：S(A)X(B)U(A)V(B),P(x,y)(Q(x,A)R(B,y),P(x,y),Q(x,A)R(B,y),Q(x,A),R(B,y),P(A,B),A/x,B/y,S(A),X(B),Q(B,A),B/x,U(A),R(B,B),B/y,V(B),102,五.含有变量的情况,一致解图如果一个解图中所涉及的置换是一致的，则该解图称为一致解图。设有置换集u1,u2,un,其中:ui=ti1/vi1,in/vin，定义表达式：U1=(v1,1,v1,m1,vn,1,vn,mn)U2=(t1,1,t1,m1,tn,1,tn,mn)置换集u1,u2,un称为一致的，当且仅当U1和U2是可合一的。U1、U2的mgu是u1,u2,un的合一复合。置换集的合一复合运算是可结合和可交换的。,103,一致置换举例,104,举例,事实：D(F)(B(F)I(F)规则：R1:D(x)T(x)R2:B(y)N(y)目标：T(u)N(v),105,D(F)(B(F)I(F),D(F),B(F)I(F),B(F),I(F),D(x),F/x,T(F),R1,T(u),F/u,B(y),F/y,N(F),R2,N(v),F/v,目标,目标,U1=(x,u,y,v)U2=(F,F,F,F)合一复合u：F/x,F/u,F/y,F/v作用于目标：T(u)N(v)u=T(F)N(F),106,正向演绎系统小结,事实表达式为与或形规则形式：LW,其中L为单文字目标公式为文字析取对事实和规则进行Skolem化，消去存在量词，变量受全称量词约束，对主合取元和规则中的变量换名用“对偶形”对目标进行Skolem化，消去全称量词，变量受存在量词约束，对析取元中的变量换名事实表达成与或树，其中，“”对应树中“与”，“”对应树中“或”从事实出发，正向应用规则，到得到目标节点为结束的一致解图为止存在合一复合时，则解图是一致的,107,3.5.2规则逆向演绎系统,一.推理过程二.目标表达式的与或形三.与或图的B规则变换四.作为终止条件的事实节点的一致解图,108,一.推理过程,从目标公式出发，逆向应用规则不断推导出子目标，直至所有子目标就是给定的事实为止。换言之，目标公式通过逆向推理找到了支持其成立的所有依据。,109,二.目标表达式的与或形,1.将目标表达式化为与或形消去蕴涵符“”把否定符移进符号括号内对全程量词Skolem化删去存在量词主要析取式中的变量分离标准化2.将与或形的目标公式用下述形式的与或图表示“合取”关系的子表达式要用K线连接符注明,110,举例：(y)(x)P(x)=Q(x,y)R(x)S(y)化为与或形为P(f(y)Q(f(y),y)R(f(y)S(y)分离标准化后P(f(z)Q(f(y),y)R(f(y)S(y)与或图为：,P(f(z)Q(f(y),y)R(f(y)S(y),P(f(z),Q(f(y),y)R(f(y)S(y),Q(f(y),y),R(f(y)S(y),R(f(y),S(y),111,二.目标表达式的与或形,目标公式的子句形是目标子句的析取，而目标子句则是文字的合取上例中的子句集为：P(f(z)Q(f(y),y)R(f(y)Q(f(y),y)S(y),112,三.与或图的B规则变换,1.规则的形式W=L其中W为任一与或形公式，L为文字且蕴涵式中任何变量的量词辖域为整个蕴涵式W=(L1L2)可化为两个规则：W=L1和W=L22.把B规则作用到目标与或图上在目标公式的与或图中，如果有一个文字L能够与L合一，则可应用B规则W=L。应用的结果是将L结点通过一个标有L和L的最简合一者u的匹配弧与结点L相连，结点L作为W的与或图的根结点。一条规则可使用多次，每次都使用不同的变量。,113,四.作为终止条件的事实节点的一致解图,逆向系统中的事实表达式均限制为文字合取形，它可以表示为一个文字集。当一个事实文字和标在该图文字节点上的文字相匹配时，就可把相应的后裔事实节点添加到该与或图中去。这个事实节点通过标有mgu的匹配弧与匹配的子目标文字节点连接起来。同一个事实文字可以多次重复使用，每次用不同变量。逆向系