《规则演绎系统课件》由会员分享，可在线阅读，更多相关《规则演绎系统课件（39页珍藏版）》请在金锄头文库上搜索。
1、3.5 规则演绎系统,例如： A BC A C B A B C B A C,都与子句A B C等价。,归结演绎将谓词公式化为子句集，原来蕴涵在谓词公式中的一些重要信息会在求取子句集的过程中丢失。,但在A B C中，是根本得不到原逻辑公式中所蕴涵的那些超逻辑的含义的。,多数情况下，人们大多希望使用那种接近于原始问题描述的形式来进行求解，而不希望把问题描述化为子句集,保留蕴涵式，将其作为推理规则，用于直接推导目标公式，不仅符合人的自然思维方式，也能通过规则（作为启发式知识）更有效地引导演绎推理过程。,说明：其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。,基于规
2、则的问题求解系统运用下述规则：,antecedent,concequent,有时，then部分用于规定动作；这时，称这种基于规则的系统为反应式系统(reaction system)或产生式系统(production system)。,3.5.1 规则正向演绎系统,逆向推理：,正向推理：,从事实出发，应用规则不断推导出中间结果作为新的事实，直至推导出目标公式,从目标公式出发，逆向应用规则不断推导出子目标，直至所有子目标就是给定的事实为止。,正向推理,燕子飞回来了,燕子飞回来了（中间结果）,3 燕子飞回来后就筑巢,燕子筑巢了,事实 1.春天来了;2 春天来了,燕子就飞回来了; 3 燕子飞回来后就筑
3、巢(2、3为规则） 目标:燕子筑巢了吗? 正向推理: 1.春天来了(事实) 2 春天来了,燕子就飞回来了,逆向推理,燕子飞回来了（子目标）,2 春天来了,燕子就飞回来了,事实 1.春天来了;2 春天来了,燕子就飞回来了; 3 燕子飞回来后就筑巢(2、3为规则） 目标:燕子筑巢了吗? 正向推理: 1.燕子筑巢了 3 燕子飞回来后就筑巢,春天来了(事实),燕子飞回来了(子目标),正向演绎推理要求将问题求解的描述分为三个部分：事实、规则集和目标。,为便于演绎推理，需将表示它们的合适公式简化为下述标准形式，并加以适当限制。,一、问题求解的规范表示,1.事实为支持演绎推理，事实表达式不必化简为子句集，只
4、需规范地表示为不含蕴涵符号的 文字与或形。,例如有事实表达式：（x）（$y）（z）Q(x, y)(R(y)P(z)S(x, z),化简成：,Q(A,w)(R(y)P(f(y)S(A, f(y),事实表达式的文字与或形可以用与或图表示，两者间的对应关系规定如下：,（1）若母式（化简得到的文字与或形）为析取式：E1E2Ek则以一个K-连接指向各析取项Ei（i = 1, 2, , k）。,（2）若母式为合取式：E1E2 Ek, 则以K个1-连接指向各合取项Ei(i = 1, 2, , k)。,例如：,事实表达式的与或形变换 ：,要把一个公式化为与或形，可采用下列步骤 ：,(1) 利用(W1W2)和(
5、W1W2)的等价关系，消去符号(如果存在该符号的话)。实际上，在事实中间很少有符号出现，因为可把蕴涵式表示为规则。,(2) 用狄摩根(De Morgan)定律把否定符号移进括号内，直到每个否定符号的辖域最多只含有一个谓词为止。,(5) 删去全称量词，而任何余下的变量都被认为具有全称量化作用。,(3) 对所得到的表达式进行Skolem化和前束化。 (4) 对全称量词辖域内的变量进行改名和变量标准化，而存在量词量化变量用Skolem函数代替。,2.规则,正向演绎推理以正向方式使用规则(称为F规则)，要求规则化简为以下形式： L = W,其中，L为单文字，W是与或形。,之所以限制规则左部为单文字，是
6、为了在演绎推理过程中便于通过L和与或图叶节点的匹配来激活规则。,设表示规则的原始蕴涵式为：（x）($y)（z）P(x, y, z) =（u）Q(x, u)R(x, u),例：,有时化简的结果会出现形如L1L2 = W的情况,可以进一步化简为与其等价的两条规则L1 = W, L2 = W,单文字的限制对知识的表示有所限定，例如，L1L2 = W,这样的规则就不允许出现，只有转变为L1 = L2W或L2 = L1W,这种转变丢失了启发式知识（L1或L2同时为真导致W为真）。不过，这种限制对演绎推理方法本身并不产生影响。,3.目标,目标公式化简后限定表示为文字的析取式，即子句。,化简时量词消去方法取
7、事实表达式的对偶形式，即将全称量词的约束变量以Sklem函数或常量取代，并使子句隐含地受存在量词约束。,例如目标公式：（x）(y)（z）P(x, y, z)Q(x, y),则先以Sklem常量A和Sklem函数g(y)分别取代约束变量x和z，再消去全称量词，,于是得:(y)P(A,y,g(y)Q(A,y),然后消去存在量词，并隐含着y是存在量词的约束变量。,关于为何需用对偶方式消去量词，这里不作形式证明，仅通过与归结反演方法作对比来加以直观说明。在归结反演中，需将目标公式取反，自然上例中x和z成为存在量词约束变量，而y成为全称量词约束变量。,最后子句中变量须作换名处理，使各文字不含同名变量。,
8、化简结果为： P(A,y,g(y)Q(A,w),二、正向演绎推理的实现,借助于与或图表示方式，正向演绎推理从事实表达式出发，不断用激活（左部单文字和与或图叶节点匹配）的F规则对与或图进行变换（从而扩展了与或图），直至得到一个将目标表达式（子句）包含的所有文字都作为叶节点的一致解图。,1.命题逻辑的情况,例：设事实表达式为：（PQ）(RS)T,给定规则集：P = C1C2, S = C3C4, T = C5,目标公式为：C1C3C5,正向演绎推理的实现：首先建立相应于事实表达式的初始与或图（树），然后选用激活的规则变换与或图,对与或图的变换实际上就是将该规则加入与或图：将规则左部单文字作为节点插
9、入与或图，并通过匹配弧（以宽箭头表示）和与或图相应叶节点连接起来；再将规则右部以与或图子图的方式插入。,P = C1C2,当目标公式中的所有文字（本例中的C1、C3和C5）全部作为目标节点进入同一个解图时，演绎推理成功结束。,事实表达式：PQ）(RS)T,规则集： P = C1C2, S = C3C4, T = C5,目标公式：C1C3C5,2.谓词逻辑的情况,由于公式含有变量，谓词逻辑情况下的演绎推理增加了复杂性。首先在判断规则能否激活时，要对规则左部的单文字和与或图中的相应叶节点作合一处理,其次，演绎推理过程可能会对同一变量进行不一致的置换，从而导致不一致解图的生成。,应用实例 ：,事实：
10、P(x,y)(Q(x)R(v,y),F规则：P(u,v)S(u) N(v),目标公式：S(a) N(b) Q(c ),P(x,y)(Q(x)R(v,y),P(x,y),Q(x)R(v,y),P(u,v),S(u),N(v),S(a),N(b),Q(x),R(v,y),Q(c ),u/x,v/y,a/u,b/v,c/x,作业：,设已知事实为： (PQ)R) (S (T U) F规则为： S(X Y) Z 试用正向演绎推理推出所有可能的目标子句。,4.1.2 规则逆向演绎系统,从目标公式出发，逆向应用规则对相应于目标公式的原始与或图进行变换，直至得到一个所有叶节点都是事实节点（以事实表达式中的文字
11、作为节点内容的节点）的一致解图为止。,逆向演绎推理情况下问题求解的描述也分为三部分：目标公式、规则和事实，它们的标准化表示形式与正向演绎呈现对偶关系。,一、问题求解的规范表示,1.目标公式,将目标公式化简为不含蕴涵符号的文字与或形。,例如有目标公式：（$x）（y）P(x) = Q(x, y)(R(x) = S(x, y),先化简为：（x）（y）P(x)Q(x, y)(R(x)S(x, y),将全称量词的约束变量y以Sk?lem函数取代，消去全称量词和存在量词，隐含着变量x受存在量词的约束,于是得：P(x) Q(x, f(x) (R(x)S(x, f(x),再通过换名，使顶层析取式的各析取项不含
12、同名变量：P(z)(Q(x,f(x)(R(x)S(x,f(x),目标公式的文字与或形也可以用与或图表示，两者间的对应关系规定如下：（1）若母式（化简得到的文字与或形）为合取式：E1E2 Ek则以一个K-连接指向各合取项Ei(i = 1, 2, , k)。 （2）若母式为析取式：E1E2 Ek则以K个1-连接指向各析取项Ei(i = 1, 2, , k)。,目标公式：P(z)(Q(x,f(x)(R(x)S(x,f(x),2.规则,逆向演绎推理以逆向方式使用规则（称为B规则），要求规则化简为以下形式：W = L,其中，L为单文字，W是与或形,规则的激活取决于L和与或图叶节点的匹配。,先暂时消去蕴涵
13、符号并化简为与或形：P(x, y, f(x, y)Q(y, f(x, y)R(x, u),设表示规则的原始蕴涵式为：（x）(y)（z）P(x, y, z)Q(y, z) =（u）R(x, u),再恢复蕴涵式表示：P(x, y, f(x, y)Q(y, f(x, y) = R(x, u),有时化简的结果会出现形如W = L1L2的情况,可以进一步化简为与其等价的两条规则W = L1, W = L2,3.事实表达式事实表达式化简后限定表示为文字的合取式，消去量词时将存在量词的约束变量以Sklem函数或常量取代，并使合取式隐含地受全称量词约束。,二、逆向演绎推理的实现,借助于与或图表示方式，逆向演绎
14、推理不断用激活（右部单文字和与或图叶节点匹配）的B规则对与或图进行变换，使与或图不断扩展。,被激活规则的右部单文字通过匹配弧插入，而规则左部则以与或图子图的方式插入。当事实表达式包含的文字和与或图叶节点匹配时，事实文字作为事实节点插入与或图（通过匹配弧）。,E1(E2E3 )= L,W = L,(A B) L,A B,L,A,B,L,目标,规则,例：给定事实、规则和目标如下：,事实：,规则：,F1:DOG(Fido) F2:BARKS(Fido) F3:WAGS-TAIL(Fido) F4:MEOWS(Myrtle),R1:WAGS-TAIL(X1) DOG(X1)FRIENDLY(X1) R2: FRIENDLY(X2) BARKS(X2) AFRAID(Y2,X2) R3:DOG(X3) ANIMAL(X3) R4:CAT(X4) ANIMAL(X4) R5:MEOWS(X5) CAT(X5),问题：是否存在这样一只狗和一只猫，这只猫不害怕这只狗？,目标公式：,(x)(y)(CAT(x) DOG(y) AFRAID(x,y),CAT(x) DOG(y) AFRAID(x,y),
