规则演绎系统

1、教案名称规则演绎系统科目教学对象主讲人课时一、教学内容匚 规则演绎系统属于高级搜索推理技术， 用于解决比较复杂的系统和问题。 本节介绍规则演绎系统的定义及其三种推理方法：规则正向演绎系统、规则逆向演绎系统和规则双向演绎系统。教学重点：规则演绎系统的定义、正向推理和逆向推理过程。教学难点：双向演绎的匹配问题等。教学方法：课堂教学为主。通过比较揭示正向推理、逆向推理和双向推理的特点。教学要求：掌握规则演绎系统的定义和正向推理、逆向推理的过程，了解规则双向演绎系 统。一、教学流程(教学策略选择与设计)1、复习一下上次课老师讲过的消解原理2、由消解原理的不足，引出本次课讲的规则演绎系统，并给出其定义3

2、、给出正向推理和逆向推理过程4、总结以上推理，给出双向推理过程，并给出相应例子教学过程一、复习消解原理在说明归结过程之前，我们首先说明任一谓词演算公式可以化成一个子句集。1. 消去蕴涵符号 只应用 V和符号，以A V B替换A=B。2. 减少否定符号的辖域每个否定符号 最多只用到一个谓词符号上，并反复应用狄摩根律。如以 A V B 代替 (A A B)以 A A B 代替 (A V B)以A代替 (A )以(x)A代替 (x) A以(x)A代替 (x) A3. 对变量标准化在任一量词辖域内 ，受该量词约束的变量为一哑元（虚构变量 ），它可以在该辖域内处处统一的被另 一个没有出现过的任意变量所代

3、替，而不改变公式的真值。 没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。女口，把（x）p（x）=（ x） Q （ x） 标准化而得到（x）p（x）=（ y） Q（ y）4. 消去存在量词在公式（y）（ x） P（ x， y）中，存在量词是在全称量词的辖域内 ，我们允许所存在的 x可能依赖于y值。令这种依赖关系明显地由函数 g（ y）所定义，它把每个y值映射到存在的那个 x。这 种函数就是Skolem函数。 如y值映射到存在的那个 X。这种函数就是 Skolem函数。 如果用 Skolem 函数代替存在的 x，我们就可以消

4、去全部存在量词（ y） Pg（ y），y这些全称量词的辖域包括要被消去的存在量词的辖域在内Skolem函数所使用的函数符号必须是新的即不允许是公式中已经出现过Skolem函数的变量是由那些全称量词所约束的全称量词量化变量24，那么我们就用不含变量的的函数符号。如果要消去的存在量词不在任何一个全称量词的辖域内Skolem函数即常量例如，（x） P（ x）化为P（ A），其中常量符号 A用来表示我们知道的存在实体。A必须是个新的常量符号，它未曾在公式其他地方使用过。5. 化为前束形现在已不存在任何存在量词，而且每个全称量词都有自己的变量，把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词

5、后面公式的整个部分。所得公式称前束形。前束形公式由全称量词串组成的前缀和不含量词的母式组成。6. 把母式化为合取范式任何母式都可以写成由一些谓词公式和谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。反复应用分配率，如把A V B A C化为A V B A A V C7. 消去全称量词所有余下的量词均被全称量词量化了。全称量词的次序也不重要了。因此，我们可以消去前缀。8. 消去连词符号 A用A , B代替A A B,以消去明显的符号A。反复代替的结果 ，最后得到一个有限集，其中每个公式是文字的析取。任一只由文字的析取构成的合适公式叫做一个子句。9. 更换变量名称更换变量名称，是一个

6、变量符号不出现在一个以上的子句中问题：归结方法不自然，并非人类的自然思维方式可能会丢失蕴涵关系中所包含的控制信息 例：以下蕴涵式：ABCCABACBACBBBABAC均与子句(A B C)等价， 但显然上面的蕴涵式信息更丰富、规则演绎系统的定义:基丁规则的求解秦统是应用匸血“规则建立的 例如主 illuiilrivdcnh tluii (ainscquent)前柠后件基于规则的系统称为规则演绎系统*若后件用于规定 动作.则称为产生式系统.规则演绎系统可以分为如 下的3种： 规则正向演绎系统 规则逆向演绎系统 规则双向演绎系统其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的

7、then组成。在所有基于规则系统中，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中，通常称每个if部分为前项(antecedent)，称每个then 部分为后项(consequent)。基于规则的演绎推理把右关问题的你讥和肓 息划分为规则与书冥两种类型辛规则：包含證含形式的表达式表示 1:无绘含式的表达式表示。画山相应的I打或图*然斤通过规则进行演绅推理先举一简单例子，帮助我们

8、理解一下：正向推理逆向推理事拱L春天来了法春天寒了 子新飞问JK 了： m熱子飞回来招就锐巢3为现園） 目标:燕子筑巢了吗？正向擔理:1*舂天未了（事茨1瓏斗卞的血下2春天来了，燕子就飞回来了 j我子飞来了事实1-春天来了讼春天来了族子號飞回来了： 3燕子飞回来后就筑巣（氛3为规则口标:煞片畝巢了吗？正直推理：址驾鑒甜堂範子飞回来了（子目标）3施子飞回来后就筑巢燕子飞因来了（申何黠料栽子筑嚴了3燕子飞回来危就筑巢燕子飞回来了（子目标）1土工生土工也池厂血它J春天来了（事实） 2春天来了.，熱子聯飞回来J三、规则正向演绎系统1、定义正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行

9、推理的，也就是从if到then的方向进行推理的。2、正向推理过程（步骤）事卖表达式的与或彩变隸事虫的与或图表示与脱宙的F规刚支換作为烬止条件的目娠公式（1）事实表达式的与或形变换把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句形类似。注意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。要把一个公式化为与或形，可采用下列步骤： 利用等价式蛀Q消去蕴含符 把否运符号移到毎个谓词符号的前面 变量飯准化，UP砲新命名变最，使不同最词约腹变啟有不同的名字引入Skclem数消去存在鼠词 将瓷式化为前康形 略去全称星词默认

10、事实表达式中尚存的变就建全称鼠词垦化的变虽) 暇新命名变星，谀同一变虽不出现在不同的主要合取式中例如，我们有事实表达式 Qlu)()Q(v , u)人(R(v) V P(v) A S(u, v)把它化为Q(w,A) A R(v) A P(v) V S(A,v)(2 )事实表达式的与或图表示将上例与或形的事实表达式用与或图来表示，见图3.1。CXmA)A(f-R(Y)A-W1V 坯扎切Q(wA-R(眄 AlP (吧V -EC 已而a在与诫用中，辘赫事蛙碱麒花锁畴点新时隶激川舗勵魏式中的針奸RW式中：L是单文字；W为与或形的唯一公式。将这类规则应用于与或图进行推演。假设有一条规则L=W根据此规则及

11、事实表达式F(L)，可以推出表达式F(W)。F(W)是用 W弋替F中的所有L而得到的。当用规则 L=W来变换以上述方式描述的F(L)的与或图表示时，就产生一个含有F(W)表示的新图；也就是说，它的以叶节点终止的解图集以F(W)子句形式代表该子句集。这个子句集包括在 F(L)的子句形和L=W的子句形间对L进行所有可能的消解而得到的整集。该过程以极其有效的方式达到了用其它方法要进行多次消解才能达到的目的。我们也假设出现在蕴涵式中的任何变量都有全称量化作用于整个蕴涵式。这些事实和规则中的一些变量 被分离标准化，使得没有一个变量出现在一个以上的规则中，而且使规则变量不同于事实变量。单文字前项 的任何蕴

12、涵式，不管其量化情况如何都可以化为某种量化辖域为整个蕴涵式的形式。这个变换过程首先把这 些变量的量词局部地调换到前项，然后再把全部存在量词 Skolem化举例说明如下：将原规则转化成 L=W形式公式(収)( 3y)Uz)P(x,y,z)r(-u)Q(x,u可以通过下列步骤加以变换：(1)暂时消去蕴涵符号(试x)口y)(Vz)P(x,y,z) V Wu)Q(x,u)(2)把否定符号移进第一个析取式内，调换变量的量词(”x)( Wy)(弓z)P(x,y,z) V 慣u)Q(x,u)(3)进行Skolem化(试x)( Wy)P(x,y,f(x,y) V &u)Q(x,u)(4)把所有全称量词移至前面

13、然后消去P(x,y,f(x,y) V Q(x,u)(5)恢复蕴涵式P(x,y,f(x,y) = Q(x,u)以下用一个自由变量的命题演算情况来说明如何把这类规则应用于与或图。把形式为l3w的规则应用到任一个具有叶节点n并由文字L标记的与或图上，可以得到一个新的与或图。在新的图上，节点n由一个单线连接符接到后继节点(也由L标记)，它是表示为W的一个与或图结构的根节点。作为例子，考虑把规则S=X A Y) V Z应用到图4.5所示的与或图中标有 S的叶节点上。所得到的I新与或图结构表示于图4.6,图中标记S的两个节点由一条叫做匹配弧的弧线连接起来。SII V V)(PVQJARSA CT V U)

14、(FVa)ARlV SA (TV ID图4.5不含变量的与或图图4.6应用一条规则得到的与或图在应用某条规则之前，一个与或图(如图4.5)表示一个具体的事实表达式。其中，在叶节点结束的一组解图表示该事实表达式的子句形。我们希望在应用规则之后得到的图，既能表示原始事实，又能表示从原始事 实和该规则推出的事实表达式。假设我们有一条规则L=W，根据此规则及事实表达式F(L)，可以推出表达式 F(W)。F(W)是用W代替F中的所有L而得到的。当用规则L=W来变换以上述方式描述的F(L)的与或图表示时，我们就产生一个含有F(W)表示的新图；也就是说，它是以叶节点终止的解图集以F(W)子句形式代表该子句集

15、。这个子句集包括在F(L)的子句形和L 的子句形间对L进行所有可能的消解而得到的整集。再讨论图4.6的情况。规则 Q(X A Y) V Z的子句形是：SVX V乙SV Y V Z(P V Q) A R V S A (T V U)的子句形解图集为:PV Q V S,RV S,PV QV T V U,R V T V U应用两个规则子句中任一个对上述子句形中的S进行消解：于是我们得到4个子句对S进行消解的消解式的完备集为：X V Z V PV Q，丫 V Z V PV Q ,R V X V Z ,R V Y V Z这些消解式全部包含在图4.4的解图所表示的子句之中。(4 )作为终止条件的目标公式扈正

16、向渣堵系统申，閒槌必式规定持丈学的析 敢形式，当一个目衆文字和与龙對中的一个丈 嗥匹配时，町以昭表示盘口蚪丈学的节点通过 匹配強底摟判导戏圏中相皮丈孕的节点上套 示口标丈学杓排盍嵇箝酊标蛀点。蚩殯聲索庇 广生昭与蜕图包轄一个屋(1标蒔蛊上结卓的斛应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这 种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。用文字集表示此目标公式，并设该集各元都为析取关系。目标文字和规则可用来对与或图添加后继节点，当一个目标文字与该图中文字节点n上的一个文字相匹配时，我们就对该图添加这个节点n的新后裔，并标

17、记为匹配的目标文字。这个后裔叫做目标节点，目标节点都用匹配弧分别接到它们的父辈节点上。当产生式系统产生一个与或图， 并包含有终止在目标节点上的一个解图时，系统便成功地结束。此时，该系统实际上已推出一个等价于目标 子句的一部分的子句图4.7给出一个满足以目标公式(C V G)为基础的终止条件的与或图，可把它解释为用一个以事实来推理”的策略对目标表达式(CV G)的一个证明。最初的事实表达式为(A V B)。由于不知道A或B哪个为真，因此我们可以试着首先假定 A为真，然后再假定 B为真，分别地进行证明。如果两个证明都成功，那么我们就得到根据 析取式(A V B)的一个证明。而 A或B到底哪个为真都

18、无关紧要。图4.7中标有(A V B)的节点，其两个后裔由一个2线连接符来连接。因而这两个后裔都必须出现在最后解图中，如果对节点n的一个解图通过 k线连接符包含n的任一后裔，那么此解图必须包含通过这个k线连接符的所有 k个后裔。图4.7的例子证明过程如下：事实：A V B规则：A=CA D, B0EA G-L 目标:C V G把规则化为子句形，得子句集：1A V C,A V D1B V E,BV Gr目标的否定为：其子句形为：(C V G)C, G4.7满足中终止条件的与或图结论：我们得到的结论是：当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地当正向演绎系统产生一个含有以

19、目标节点作为终止的解图时，此系统就成功地终止。明目标D E 0：例子：已知事实 A B，规则 A C D和B E F ,使用规则正向演绎系统证询川创促为ill单丈丁咛顶钊或阳F琐纽醴的蠟存決成片念示Xj jidiWfcu存1T工的叮或吗农示卜.迂用叼酸图的F现蚪变换得到一牛含有冃标节点作为终止的解閨如TQbVI肚I:而的F誠图的叶了肓点可宵挺淒出H标：12证毕.应用实例：爭尖;P(xy)v(Q(x)/R(v,y)F规測：P(u,v)S(ii)vN(v)P(x,y)v(Q(x)R(v,y)四、规则逆向演绎系统1、定义基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程

20、，从then到if的推理过程。2、逆向推理过程(1 )目标表达式的与或形式逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标公式化成与或形。即消去蕴涵符号，把否定符号移进括号内，对全称量词Skolem化并删去存在量词。留在目标表达式与或形中的变量假定都已存在量词量化。举例如下：目标表达式(y)()P(x) “ q (x,y)人P(x) A S(y)被化成与或形：P(f(y) V Q(f(y),y) A P(f(y) V S(y)式中，f(y)为一 Skolem函数。对目标的主要析取式中的变量分离标准化可得：P(f(z) V Q(f(y),y) A P(f(y

21、) V S(y)应注意不能对析取的子表达式内的变量y改名而使每个析取式具有不同的变量。与或形的目标公式也可以表示为与或图。不过，与事实表达式的与或图不同的是，对于目标表达式，与1r或图中的k线连接符用来分开合取关系的子表达式。上例所用的目标公式的与或图如图4.9所示。在目标公式的与或图中，我们把根节点的任一后裔叫做子目标节点，而标在这些后裔节点中的表达式叫做子目标。-P(f(z)V (Q(fyXy)AR(f(y)V-S(y)X-P(直)I| Qfgyhy)电ggy)W-S(y |Q(石人yR(fy)V-S(y)R(fly)-S(y)图4.9 一个目标公式的与或图表示这个目标公式的子句形表示中的

22、子句集可从终止在叶节点上的解图集读出：P(f(z),Q(f(y),y)人R(f(y),Q(f(y),y)人S(y)可见目标子句是文字的合取，而这些子句的析取是目标公式的子句形。(2 )与或图的B规则变换B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，我们现在把这些B规则限制为W= L形式的表达式。其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。其次，把B规则限制为这种形式的蕴涵式还可以简化匹配，使之不会引起重大的实际困难。此外，可以 把像 W=(L1 A L2)这样的蕴涵式化为两个规则L1和 加- L2。(3 )作为终止条件的事实节点的一致解

23、图逆向系逆向系统中的事实表达式均限制为文字合取形，它可以表示为一个文字集。当一个事实文字和标 在该图文字节点上的文字相匹配时，就可把相应的后裔事实节点添加到该与或图中去。这个事实节点通过标 有mgu的匹配弧与匹配的子目标文字节点连接起来。同一个事实文字可以多次重复使用(每次用不同变量),以便建立多重事实节点。逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。下面我们讨论一个简单的 例子,看看基于规则的逆向演绎系统是怎样工作的。举例如下：这个例子的事实、应用规则和问题分别表示于下：3 .押理过程M审丈；Fl： S(Cfass2 a)： 茁兄戲级 C心曲2中fl勺严牛.F2； T

24、(Class2 b)： b 足坯级 Class2 中的老艸= 现则；R 1: S/T(z+x) -7bfS(x.y)J中 h loft(x,y)：x 址 y 的-EWI：冋谁是a的老师:事实：F1: DOG(FIDO);狗的名字叫 FidoF2:BARKS(FIDO) ; Fido 是不叫的F3: WAGS TAIL(FIDO) ; Fido 摇尾巴F4: MEOWS(MYRTLE);猫咪的名字叫 Myrtle规则：R1: WAGS TAIL(x1) A DOG(x1) i FRIENDLY(x1);摇尾巴的狗是温顺的狗R2: FRIENDLY(x2) ABARKS(x2)=AFRAID(y2

25、,x2);温顺而又不叫的东西是不值得害怕的R3: DOG(x3) ANIMAL(x3);狗为动物R4: CAT(x4) =ANIMAL(x4);猫为动物R5: ME0WS(x5) = CAT(x5);猫咪是猫问题：是否存在这样的一只猫和一条狗，使得这只猫不怕这条狗？用目标表达式表示此问题为：(x)(y)CAT(x) A DOG(y) A AFRAID(x , y)CA7 丘)A MG &)人 ATRAJ5 g y)CATfe)rOG-(y)z ATRkID 随 y)ffIBO/yWkS)CAT(i5)DOG (HDDJlFRAID9 Cy2川町审忆y/s21MEDSCx：)FEIENBLY (

26、y)miLE/w wHEOS (TYETLE)iFIDO/yTALKS (FIDO)1FRIElTOLYesl)HlBOG)UGS-TAIL 呦iFIDO/y聆昴一TAIL (TIJO)DOGtmo)图4.10逆向系统的一个一致解图图4.10表示出这个问题的一致解图。图中，用双线框表示事实节点，用规则编号R1、R2和R5等来标记所应用的规则。此解图中有八条匹配弧，每条匹配弧上都有一个置换。这些置换为x/x5 ,MYRTLE/x， FIDO/y，x/y2,y/x2，FIDO/y(FIDO/y 重复使用四次)。由图4.10可见，终止在事实节点前的置换 为MYRTLE/x和FIDO/y。把它应用到目

27、标表达式，我们就得到该问题的回答语句如下：CAT(MYRTLE) DOG(FIDO员AFRAID(MYRTLE,FIDO)统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。JF规购h L t W 巧作用于：半妻的总數瞬血规如h 作用于*3. 正域向嗣树卅理规则形孔：单丈字tW目标处此为丈学析取对#.規则朗痔蛊逓祠. Skokm Ri用对偶形询*1桩的全秫置稠. Skokmt事婆裹达无与或X v七肌 it 弄应 n- 岂_ -u J.- W对 入对底或.从事渎出发”正的血用规则以可艰为此東的一致耶團ML2 些 26第空*达r式恳會取形觇网形式： T草文亭廿后心式佞恋形I对丰决、舰阳谄

28、再左量词， SkolemRi削对码诺请勺栋的罢計董词 SkolemL酉掠鸟式的与贞b V*.*,!_,* W _ ifc 丄 &4 丹时 * 时辰薮从可籽出发屢的宜用规则以事决为结束的政斛囹珈窗阴渥园俱窗題噩旦痢园尙常响要看开始状态和引标状态谁多？人们希豐从小 的状卷義出发朝丸的状态集擢理，找解更农易。旻対方向分枝阂素大小的釣隶一般朝分枝阖 素低的方向極理。还:央定子是否需向用户证曉程序的推理过租 若旻則比择方向更加苻合用户的思”者方燥。四、规则双向演绎系统在上两节中我们所讨论的基于规则的正向演绎系统和逆向演绎系统都具有局限性。正向演绎系统能够 处理任意形式的if表达式，但被限制在 then表

29、达式为由文字析取组成的一些表达式。逆向演绎系统能够处理 任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。我们希望能够构成一个组合的 系统，使它具有正向和逆向两系统的优点，以求克服各自的缺点（局限性）。这个系统就是本节要研究的双向（正向和逆向）组合演绎系统。正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库 由表示目标和表示事实的两个与或图结构组成。这些与或图最初用来表示给出的事实和目标的某些表达式集 合，现在这些表达式的形式不受约束。这些与或图结构分别用正向系统的F规则和逆向系统的 B规则来修正。设计者必须决定哪些规则用来处理事实图以及哪些规则用

30、来处理目标图。尽管我们的新系统在修正由两部分 构成的数据库时实际上只沿一个方向进行，但是我们仍然把这些规则分别称为F规则和B规则。我们继续限制F规则为单文字前项和 B规则为单文字后项。组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。这些结构可由标有合一文字的节点上的匹配棱线来连接。我们是用对应的mgu来标记匹配棱线的。对于初始图，事实图和目标图间的匹配棱线必须在叶节点之间。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。1、基于规则的正向演绎系统和逆向演绎系统的特点和局限性正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。双向（正向和逆向）组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。2、双向（正向和逆向）组合演绎系统的构成正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正