人工智能-第三搜索推理技术

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三搜索推理技术,从问题的表示到问题的解决是一个求解的过程，也就是搜索过程。在这一过程中，采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。本章首先介绍图搜索策略的一般过程，接着讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理，然后研究一些比较新的能够求解比较复杂问题的推理技术。,第三确定性推理,3.1,图搜索策略,3.2,盲目搜索,3.3,启发式搜索,3.4,消解原理,3.5,规则演绎系统,3.6,产生式系统,3.7,非单调推理,第三搜索推理技术,一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：,(1),搜索空间小,;(2),解最佳。,Sg,3.1,图搜索策略,3.1,图搜索策略,一,.,问题描述,(,图搜索问题描述,),把求解问题看成一个状态图，求初始节点到目标节点的路径。,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,这条路径的耗散值。,3.1.1,图搜索策略,回顾一下图论中几个术语的含义。,扩展一个节点,:,后继节点操作符,(,相当于可应用规则,),作用到节点,(,对应于某一状态描述,),上,生成出其所有后继节点,(,新状态,),并给出连接弧线的耗散值,(,相当于使用规则的代价,),这个过程叫做扩展一个节点。扩展节点可使定义的隐含图生成为显式表示的状态空间图。,3.1.1,图搜索策略,二,.,图搜索过程,S,起始结点,G,搜索图,OPEN,表存放未扩展节点,CLOSED,表存放已扩展节点,1.,图搜索过程,(1),建立一个只含有起始节点,S,的搜索图,G,，把,S,放到一个叫做,OPEN,的未扩展节点表中。,(2),建立一个叫做,CLOSED,的已扩展节点表，其初始为空表。,(3)LOOP:,若,OPEN,表是空表，则失败退出。,(4),选择,OPEN,表上的第一个节点，把它从,OPEN,表移出并放进,CLOSED,表中，称此节点为节点,n,。,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)GO LOOP,3.1.1,图搜索策略,举例：,S,A,B,C,D,E,M,F,S,1.S OPEN(S) CLOSED( ),2.A OPEN(A, B) CLOSED(S),3.B OPRN(B, C, D) CLOSED(S, A),4.C OPEN(C, D, E) CLOSED(S, A, B),5.D OPEN(D,E) CLOSED(S, A,B,C),6.E OPEN(E,M,F) CLOSED(S, A,B,C,D),7.N,求解,目标节点,2,3,5,6,4,7,3,8,4,3.1.1,图搜索策略,2.,流程图,开始,把,S,放表入,OPEN,表中,OPEN,表为空表,把第一个节点,n,从,OPEN,表移至,CLOSED,表,N,为目标节点,把节点,n,的后继节点放入,OPEN,表,，提供返回节点,n,的指针,修正指针方向,重排,OPEN,表,失败,成功,是,是,3.1.1,图搜索策略,3.1.1,图搜索策略,3.1.1,图搜索策略,3.1.1,图搜索策略,3.1.1,图搜索策略,3.1.1,图搜索策略,3.,遗留问题,n,的某后继节点已在,OPEN,表中或,CLOSED,表中有了,是否需要修改指针，对已存在的后继节点, 按什么方式重排,OPEN,表,宽度优先搜索,深度优先搜索,等代价搜索,搜索控制方法,3.2,盲目搜索,盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索，又叫做无信息搜索。一般只适用于求解比较简单的问题。,典型的盲目搜索方法是深度优先搜索和宽度优先搜索,(,亦称广度优先搜索,),这是两处基本搜索方法。,3.2,盲目搜索,一,.,宽度优先搜索,(,一,).,宽度优先搜索,以接近起始节点的程度依次扩展节点,从根结点开始,每次都要扫遍同层的各个结点,若没有找到目标,则再往下一层扫描,(,扫描下一层的所有子结点,),直到找到目标或没有找到目标退出系统,(,此种属于没有解的情况,),。,3.2,盲目搜索,(,二,).,流程算法,扩展节点：把它的后继节点放入,OPEN,表的末端,1.,搜索算法,把起始节点放到,OPEN,表中,(,如果该起始节点为一目标节点，则求得一个解答,),如果,OPEN,表是一个空表，则没有解，失败退出；否则继续。,把第一个节点,(,节点,n),从,OPEN,表移出，并把它放入,CLOSED,的扩展节点表中。,扩展节点,n,。如果没有后继节点，则转向第步。,把,n,的所有后继节点放到,OPEN,表的末端，并提供从这些后继节点回到,n,的指针。,如果,n,的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第步,3.2,盲目搜索,2.,流程图,开始,把,S,放表入,OPEN,表,OPEN,表为空表,把第一个节点,n,从,OPEN,表移至,CLOSED,表,把节点,n,的后继节点,放入,OPEN,表的末端，,提供返回节点,n,的指针,失败,成功,是,是,是否有,任何后继节点,为目标节点,？,3.2,盲目搜索,3.,举例：八数码难题,初始棋局 目标棋局,2 8 3,1 4,7 6 5,1 2 3,8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 4,7 6 5,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,1 2 3,8 4,7 6 5,2 3 4,1 8,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,8 3,2 1 4,7 6 5,8 1 3,2 4,7 6 5,2 8 3,7 4,6 1 5,2 8 3,7 14,6 5,1 2 3,7 8 4,6 5,1 2 3,8 4,7 5 6,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,S,0,S,g,3.2,盲目搜索,(,三,).,宽度优先搜索的性质,当问题有解时，一定能找到解,当问题为单位耗散值，且问题有解时，一定能找到最优解,方法与问题无关，具有通用性,效率较低,属于图搜索方法,3.2,盲目搜索,二深度优先搜索,(,一,).,深度优先搜索,总是先扩展最新产生的节点,3.2,盲目搜索,(,二,).OPEN,表的排列算法,对于许多问题，其状态搜索树的深度可能为无限深或者可能至少要比某个可接受的解答序列的已知深度上限还要深，为了避免考虑太长的路径：,1.,深度界限：规定的一个节点扩展的最大深度,2.,扩展节点：若不等于最大深度，将后裔节点放入,OPEN,表的前头。,3.2,盲目搜索,3.,搜索算法,把起始节点放到,OPEN,表中,(,如果该起始节点为一目标节点，则求得一个解答,),如果,OPEN,表是一个空表，则失败退出。,把第一个节点,(,节点,n),从,OPEN,表移到,CLOSED,表。,如果节点,n,的深度等于最大深度，则转向第步。,扩展节点,n,，产生其全部后裔，并把它们放入,OPEN,表的前头。如果没有后裔，则转向,(2.),如果后继节点中有任一个为目标节点，则求得一个解答，成功退出；否则转向第步,3.2,盲目搜索,4.,流程图,开始,把,S,放表入,OPEN,表,OPEN,表为空表,把,OPEN,表中第一个,节点,n,移至,CLOSED,表,扩展节点,n,，把后裔,放入,OPEN,表的前头,失败,成功,是,是,是否有,任何后继节点为,目标节点？,S,是否,为目标节点？,节点,n,的深度是否等于,深度界限？,是,成功,是,否,3.2,盲目搜索,5.,举例,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,a,b,c,d,1 2 3,8 4,7 6 5,目标,3.2,盲目搜索,(,三,).,深度优先搜索的性质,一般不能保证找到最优解,当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制,最坏情况时，搜索空间等同于穷举,是一个通用的与问题无关的方法,3.2,盲目搜索,三、等代价搜索,(,一,).,等代价搜索,1.,问题的提出：有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解，,这可通过代价来描述,2.,代价,(1),从节点,I,到它的后继节点,j,的连线弧线代价记为,C(i, j).,(2),从起始节点到任一节点,i,的路径代价记为,g(i).,3.,等价搜索,每次扩展的是代价最小的节点。,3.2,盲目搜索,(,二,).,扩展算法,扩展节点,I,对于节点,I,的每个后继节点，计算,g(j)=g(i)+c(i,j),按,g(j),升序插入到,OPEN,表中。,3.3,启发式搜索,启发式搜索是利用问题拥有的启发信息来引导搜索,达到减少搜索范围,降低问题复杂度的目的,这种利用启发信息的搜索过程都称为启发式搜索方法。,3.3,启发式搜索,3.3.1,启发式搜索策略,一,.,启发信息,1.,启发信息：具体问题领域的可用来简化搜索的特性信息,2.,种类：,(1),用于决定要扩展的下一个节点,(,以免象宽度优先或深度优先搜索中那样盲目地扩展,),(2),在扩展一个节点的过程中，用于决定要生成那一个或那几个后继节点,(,以免盲目地同时生成所有可能的节点,),(3),用于决定某些应该从搜索树中抛弃或修剪的节点,3.3,启发式搜索,3.3.1,启发式搜索策略,二,.,启发式搜索,1.,启发式搜索：利用启发信息的搜索方法。,本节只讨论利用第一种启发信息的搜索,2.,有序搜索：利用第一种启发信息，总是选择“最有希望”的节点作为下一个被扩展的节点。,3.3,启发式搜索,3.3.2,估价函数,一,.,估价函数,用来估算节点希望程度的量度,二,.,估价函数考虑因素,1.,起始节点到此节点的距离,(,以减少搜索工作量为出发点,),2.,经过此节点到达目标的代价,(,以最小代价为出发点,),三,.,估价函数表示,f(n),我们可以用,f,函数来排列,GRAPHSEARCH,第,8,步中,OPEN,表上的节点,。,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,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,表。,3.3,启发式搜索,有序搜索的有效性直接取决于,f,的选择,二,.,举例,八数码难题,起始节点 目标节点,选用的估价函数,f(n)=d(n)+w(n),d(n),是搜索树中节点,n,的深度,W(n),用来计算对应于节点,n,中错放棋子个数,这样起始节点,f=0+4=4,2 8 3,1 6 4,7 5,1 2 3,4,7 6 5,3.3,启发式搜索,1.OPEN= CLOSED=,2.OPEN=,、,、,CLOSED=,3. OPEN=,、,、,、,、,CLOSED=,、,4. OPEN=,、,、,、,、,、,CLOSED=,、,、,5. OPEN=,、,、,、,、,、,、,CLOSED=,、,、,、,6. OPEN=,、,、,、,、,、,、,CLOSED=,、,、,、,、,7. OPEN=,、,、,、,、,、,、,、, ,CLOSED=,、,、,、,、,、, ,3.3,启发式搜索,三,.,小结,1.,宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。,对于宽度优先搜索，我们选择,f(i),作为节点,i,的深度。,对于等代价搜索，,f(i),是从起始节点至节点,i,这段路径的代价。,2.,有序搜索的有效性直接取决于,f,的选择，如果选择的,f,不合适，有序搜索就可能失去一个最好的解甚至全部的解。,如果没有适用的准确的希望量度，那么,f,的选择将涉及两个方面的内容：,一方面是一个时间和空间之间的折衷方案,；,另一方面是保证有一个最优的解或任意,。,3.3,启发式搜索,三,.,小结,3.,节点希望量度以及某个具体估价函数的合适程度取决于手头的问题情况。根据所要求的解答类型，可以把问题分为下列三种：,假设状态空间含有几条不同代价的解答路径，其问题是要求得最优解答。,类似第一种情况，但难度相当大，实践上不可能。处理该种情况的关键问题：如何通过适当的搜索试验找到好的,(,但不是最优的,),解答；如何限制搜索试验的范围和所产生的解答与最优解答的差异程度。,不考虑解答的最优化；或者只存在一个解，或者任何一个解与其他解一样好。问题是如何使搜索试验的次数最少，而不是像第二种情况那样试图使某些搜索试验和解答代价的综合指标最小。,3.3,启发式搜索,3.3.4A*,算法,一,.,符号定义,k(n,i,n,j,):,任意两点,n,i,和,n,j,之间最小代价路径的实际代价,h*(n):,节点,n,到目标集合,t,i,上所有,k(n,t,j,),中最小的一个,g*(n)= k(s,n),f*(n)= g*(n) + h*(n),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,算法,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) g(old),，重新确定,OLD,的父辈节点为,BES,，并修改,g,值和,f,值,5.,把,suc,放入,OPEN,表，添进,bestnode,的后裔表,6.,计算,f,值。,A*,算法流程,是,开始,把,S,放入,OPEN,表，记,f=h,Open=NIL,选取,OPEN,表上未设置过的具有最小,f,值的节点,BESTNODE,放入,CLOSED,表,BESTNODE,是目标节点吗,扩展,BESTNODE,产生其后继节点,SUCCESSOR,建立从,SUCCESSOR,返回,BESTNODE,的指针,计算,f(suc)=g(suc)+h(bes,suc),sucOPEN?,sucCLOSED?,Suc=old,把它添到,BESTNODE,的后继节点表中,g(suc),E,1,E,2,（, E,2,=,E,1,和,E,2,=,E,3,=,E,1,E,2,）,在证明某个逻辑式为真时，先假设它为假，再与已知事实进行消解，得出矛盾，由此证明了逻辑式。即反证思想。,3.4,消解原理,消解原理由,J.A.Robinson,由,1965,年提出。,与演绎法完全不同，新的逻辑演算算法。,一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。,语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。 而消解方法是自动推理、自动推导证明用的。（“数学定理机器证明”）,3.4,消解原理,消解过程,将命题写成合取范式,求出子句集,对子句集使用消解推理规则,消解式作为新子句参加消解,消解式为空子句 ，,S,是不可满足的（矛盾），原命题成立。,3.4,消解原理,3.4.1,化为子句集,3.4.2,消解推理规则,3.4.3,含有变量的消解式,3.4.4,消解反演求解过程,3.4.5,含状态项的回答语句的求取,3.4.1,化为子句集,例：,(,z) (x)(y)(P(x) Q(x) R(y) U(z),1.,消蕴涵符,理论根据：,a,b = a b,(,z) (x)(y)(P(x) Q(x) R(y) U(z),2.,移动否定符减少否定符号的辖域,(,反复应用狄,.,摸根定律,),理论根据：,(a b) = a b,(a b) = a b,( 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),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,函数即是常数,3.3.1,化为子句集,6.,化为合取范式,即,(a,b) (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),3.4.1,化为子句集,8.,消去连词符号，表示为子句集,用,A,，,B,代替,A B,P(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),使一个变量符号不出现在一个以上的子句中,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),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,的公式变换成的子句集，因此子句是表示公式的一个完善的一般形式。在定理证明系统中，消解作为推理规则使用时，从公式集来证明某个定理，首先要把公式集化为子句集。,3.4.2,消解推理规则,L,1,、,L,2,分别是原子公式，具有相同的谓词符号，但一般具有不同的变量。已知：,L,1,、,L,2,，如果,L,1,和,L,2,具有最一般合一者,，可以导出,( ),消解式,3.4.2,消解推理规则,1.,假言推理,父辈子句,P, PQ (P = Q),消解式,Q,2.,合并,父辈子句,P,Q, PQ,消解式,QQ=Q,3.4.2,消解推理规则,3.,重言式,父辈子句,P,Q, P Q,消解式,Q Q,P, P,4.,空子句,(,矛盾,),父辈子句,P, P,消解式,NIL,3.4.2,消解推理规则,5.,链式,(,三段论,),父辈子句,P,Q (P = Q), Q R(Q = P),消解式,P, R( P = R),3.4.3,含有变量的消解式,设,l,i,是,L,i,的一个子集，,m,i,是,M,i,的一个子集，使得集,l,i,和,m,i,的并集存在最一般的合一者,，消解两个子句,L,i,和,M,i,，得到的消解式,L,i,-,l,i,M,i,-,m,i,注意：消解两个子句时，因为有多种选择,l,i,和,m,i,的方法，可能有一个以上的消解式，但最多有有限个消解式。,3.4.3,含有变量的消解式,例：两个子句,Px,，,f(A) Px,，,f(y) Q(y),P,z,，,f(A) ,Q(z),(1),取,l,i,= Px,，,f(A) m,i,= ,P,z,，,f(A),得消解式,Pz,，,f(y) ,Q(z) Q(y),(2),取,l,i,= Q(y) m,i,= ,Q(z),得消解式,Px,，,f(A) Px,，,f(y) ,P,y,，,f(A),进一步消解得消解式为,Py,，,f(y),3.4.4,消解反演求解过程,要证明某个命题，其目标公式被否定并化成子句形，添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句,(NIL),，产生一个矛盾，从而使定理得到证明。,3.4.4,消解反演求解过程,一,.,消解反演,公式集,S,，目标公式,L,，通过反演求证目标公式,L.,证明步骤：,1.,否定,L,，得,L;,2.,把,L,添加到,S,中去；,3.,把新产生的集合,L,，,S,化成子句集；,4.,应用消解原理，力图推导出一个表示矛盾的空子句；,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,),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),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),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,储蓄问题反演树,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),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),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),例题得归结树,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,3.4.4,消解反演求解过程,二,.,反演求解过程,从反演树求取对某个问题的答案,过程：,1.,由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去,;,2.,按照反演树，执行和以前相同的消解，直到根部得到某个子句止；,3.,用根部的子句作为一个回答语句；,根部的子句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。,3.4.4,消解反演求解过程,举例：,如果无论约翰到哪里去，菲多也就去那里，那么如果约翰在学校里，菲多在哪里呢？,公式集：,(x) AT(John, x),=,AT(Fido, x) ,AT(John, school),通过证明,(x) (AT(Fido, x) ),在逻辑上遵循,S,寻求一个存在,x,的例，就能解决“菲多在哪里”的问题,目标公式的否定：,(x)(,AT(Fido, x) ),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,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),，它就是这个问题的合适答案。,3.4.4,消解反演求解过程,提取回答的过程,先进行归结，证明结论的正确性；,用重言式代替结论求反得到的子句；,按照证明过程，进行归结；,最后，在原来为空的地方，得到的就是提取的回答。,修改后的证明树称为修改证明树,作业,作业,证明：,前提：,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),作业,化为子句集：,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,）,作业,归结过程：, 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,得证,.,作业,目标,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,作业,反演求解：, 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.,3.5,规则演绎系统,基于规则的问题求解系统用下述规则来建立：,If Then,其中：,if,可能与某断言集中的一个或多个断言匹配,有时,then,部分用于产生新断言，这种基于规则的系统叫做规则演义系统；,有时,then,部分用于规定动作，这种系统叫做产生式系统。,3.5,规则演绎系统,将有关问题的知识和信息划分成规则与事实两种类型。规则有包含蕴涵形式的表达式表示，事实由无蕴涵形式的表达式表示，这种推理系统称为基于规则的演绎系统。,3.5.1,规则正向演绎系统,正向推理：,从,if,部分向,then,部分推理的过程,事实,目标,规则,3.5.1,规则正向演绎系统,一,.,事实表达式的与或形变换,二,.,事实表达式的与或图表示,三,.,与或图的,F,规则变换,四,.,作为终止条件的目标公式,一,.,事实表达式的与或形变换,1.,事实化为与或形表示,与或形,无量词约束,否定符只作用于单个文字,只有“与”、“或”,一,.,事实表达式的与或形变换,2.,变换过程,消去蕴涵符“,”,减少否定符号“,”的辖域,进行,skolem,化和前束化,对变量标准化、使得同一变量不出现在事实表达式的不同主要合取式中,删除全程量词,一,.,事实表达式的与或形变换,例：事实表达式,(,u,)(,v,)Q(v,u),(R(v) V (P(v), S(u,v),减少否定符号“,”的辖域,(,u,)(,v,)Q(v,u),(R(v),(P(v) V,S(u,v),进行,skolem,化,Q(v,A),(R(v),(P(v) V,S(A,v),对变量标准化,Q(w,A),(R(v),(P(v) V,S(A,v),二,.,事实表达式的与或图表示,将表达式作为节点，子表达式作为后继节点，若为析取关系，要用“,K”,线连接符来标注，叶节点均由表达式中的文字来标注,。,二,.,事实表达式的与或图表示,例：,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),因此，可把与或图看做是对子句集的简洁表示,一般把事实表达式的与或图表示倒过来画，根节点在最下面、后继节点在上,三,.,与或图的,F,规则变换,1.,规则的形式,L W,其中，,L,是单文字，,W,是与或形,且假设出现在蕴涵式中的任何变量都有全称量词作用于整个蕴涵式,如果不符合要求，可转化为符合要求,步骤：暂时消去蕴涵符号,减少否定辖域,进行,Skolem,化,把所有全程量词移至前面后消去,恢复蕴涵式,三,.,与或图的,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),=