规则演绎系统.doc

教案名称
规则演绎系统
科目

教学对象

主讲人

课时

一、教学内容
规则演绎系统属于高级搜索推理技术，用于解决比较复杂的系统和问题。本节介绍规则演绎系统的定义及其三种推理方法：规则正向演绎系统、规则逆向演绎系统和规则双向演绎系统。
教学重点：规则演绎系统的定义、正向推理和逆向推理过程。
　　教学难点：双向演绎的匹配问题等。
　　教学方法：课堂教学为主。通过比较揭示正向推理、逆向推理和双向推理的特点。
　　教学要求：掌握规则演绎系统的定义和正向推理、逆向推理的过程，了解规则双向演绎系统。
二、 教学流程（教学策略选择与设计
1、复习一下上次课老师讲过的消解原理
2、由消解原理的不足，引出本次课讲的规则演绎系统，并给出其定义
3、给出正向推理和逆向推理过程
4、总结以上推理，给出双向推理过程，并给出相应例子
教学过程
一、 复习消解原理
在说明归结过程之前 ， 我们首先说明任一谓词演算公式可以化成一个子句集。
1. 消去蕴涵符号 只应用 ∨ 和~符号 ， 以~A∨B替换A=>B。
2. 减少否定符号的辖域
每个否定符号 ~最多只用到一个谓词符号上 ， 并反复
应用狄摩根律。 如
以~A∨~B 代替~（A∧B）
以~A∧~B 代替~（A∨B）
以A代替~（~A）
以(x){~A}代替~（x） A
以(x){~A}代替~（x） A
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， 我们就可以消去全部存
在量词（y） P[g（y）， y]
Skolem函数的变量是由那些全称量词所约束的全称量词量化变量 ， 这些全称量词的辖域包括要被消去的存在量词的辖域在内 。 Skolem函数所使用的函数符号必须是新的 ， 即不允许是公式中已经出现过的函数符号 。如果要消去的存在量词不在任何一个全称量词的辖域内 ，那么我们就用不含变量的 Skolem函数即常量
例如，（x） P（x） 化为 P（A）， 其中常量符号 A用来表示我们知道的存在实体。 A必须是个新的常量符号 ，它未曾在公式其他地方使用过。
5. 化为前束形
现在已不存在任何存在量词 ， 而且每个全称量词都有自己的变量 ， 把所有全称量词移到公式的左边， 并使每个量词的辖域包括这个量词后面公式的整个部分。 所得公式称前束形 。 前束形公式由全称量词串组成的前缀和不含量词的母式组成。
6. 把母式化为合取范式
任何母式都可以写成由一些谓词公式和谓词公式的否定的析取的有限集组成的合取。 这种母式叫做合取范式。 反复应用分配率 ， 如把
A∨{B∧C}化为 {A∨B}∧{A∨C}
7. 消去全称量词
所有余下的量词均被全称量词量化了 。 全称量词的次序也不重要了 。 因此， 我们可以消去前缀。
8. 消去连词符号 ∧
用 {A， B}代替{A∧B}， 以消去明显的符号 ∧ 。 反复代替的结果 ， 最后得到一个有限集， 其中每个公式是文字的析取。 任一只由文字的析取构成的合适公式叫
做一个子句 。
9. 更换变量名称
更换变量名称 ， 是一个变量符号不出现在一个以上的子句中 。
问题：
归结方法不自然， 并非人类的自然思维方式
可能会丢失蕴涵关系中所包含的控制信息
例：以下蕴涵式：
~A~BC ~C AB
~A~CB ~A CB
~B~BA ~B AC
均与子句(ABC)等价， 但显然上面的蕴涵式信息更丰富
二、 规则演绎系统的定义：

其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。
在所有基于规则系统中，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中，通常称每个if部分为前项(antecedent)，称每个then部分为后项(consequent)

先举一简单例子，帮助我们理解一下：

三、 规则正向演绎系统
1、定义
　　正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。
2、正向推理过程(步骤)

　　（1）事实表达式的与或形变换
　　把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句形类似。
注意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。要把一个公式化为与或形，可采用下列步骤：

例如，我们有事实表达式(u)(v){Q(v，u)∧～[(R(v)∨P(v))∧S(u，v)]}把它化为
Q(w,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}
　（2）事实表达式的与或图表示
将上例与或形的事实表达式用与或图来表示，见图3.1。

公式的与或图表示有个有趣的性质，即由变换该公式得到的子句集可作为此与或图的解图的集合(终止于叶节点)读出；也就是说，所得到的每个子句是作为解图的各个叶节点上文字的析取。这样，由表达式
Q(w,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}
得到的子句为
　　　　　　　　　　 Q(w,A)～S(A,v)∨～R(v),～S(A,v)∨～P(v)
　　一般把事实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。上节的与或图表示，就是按通常方式画出的，即目标在上面。
　　（3）与或图的F规则变换
　　这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式：L=>W
式中：L是单文字；W为与或形的唯一公式。
将这类规则应用于与或图进行推演。假设有一条规则L=>W，根据此规则及事实表达式F(L)，可以推出表达式F(W)。F(W)是用W代替F中的所有L而得到的。当用规则L=>W来变换以上述方式描述的F(L)的与或图表示时，就产生一个含有F(W)表示的新图；也就是说，它的以叶节点终止的解图集以F(W)子句形式代表该子句集。这个子句集包括在F(L)的子句形和L=>W的子句形间对L进行所有可能的消解而得到的整集。该过程以极其有效的方式达到了用其它方法要进行多次消解才能达到的目的。
我们也假设出现在蕴涵式中的任何变量都有全称量化作用于整个蕴涵式。这些事实和规则中的一些变量被分离标准化，使得没有一个变量出现在一个以上的规则中，而且使规则变量不同于事实变量。单文字前项的任何蕴涵式，不管其量化情况如何都可以化为某种量化辖域为整个蕴涵式的形式。这个变换过程首先把这些变量的量词局部地调换到前项，然后再把全部存在量词Skolem化
举例说明如下：将原规则转化成L=>W形式
公式 (x){[(y)(z)P(x,y,z)](u)Q(x,u}
可以通过下列步骤加以变换：
　　(1) 暂时消去蕴涵符号
(x){～[(y)(z)P(x,y,z)]∨(u)Q(x,u)}

　　(2) 把否定符号移进第一个析 取式内，调换变量的量词
(x){(y)(z)[～P(x,y,z)]∨(u)Q(x,u)}

　　(3) 进行Skolem化
(x){(y)[～P(x,y,f(x,y))]∨(u)Q(x,u)}

　　(4) 把所有全称量词移至前面然后消去
～P(x,y,f(x,y))∨Q(x,u)

(5) 恢复蕴涵式
P(x,y,f(x,y))Q(x,u)

以下用一个自由变量的命题演算情况来说明如何把这类规则应用于与或图。
　　把形式为LW的规则应用到任一个具有叶节点n并由文字L标记的与或图上，可以得到一个新的与或图。在新的图上，节点n由一个单线连接符接到后继节点(也由L标记)，它是表示为W的一个与或图结构的根节点。作为例子，考虑把规则S(X∧Y)∨Z应用到图4.5所示的与或图中标有S的叶节点上。所得到的新与或图结构表示于图4.6，图中标记S的两个节点由一条叫做匹配弧的弧线连接起来。

图 4.5 不含变量的与或图 图 4.6 应用一条规则得到的与或图
在应用某条规则之前，一个与或图(如图4.5)表示一个具体的事实表达式。其中，在叶节点结束的一组解图表示该事实表达式的子句形。我们希望在应用规则之后得到的图，既能表示原始事实，又能表示从原始事实和该规则推出的事实表达式。
　　假设我们有一条规则LW，根据此规则及事实表达式F(L)，可以推出表达式F(W)。F(W)是用W代替F中的所有L而得到的。当用规则LW来变换以上述方式描述的F(L)的与或图表示时，我们就产生一个含有F(W)表示的新图；也就是说，它是以叶节点终止的解图集以F(W)子句形式代表该子句集。这个子句集包括在F(L)的子句形和LW的子句形间对L进行所有可能的消解而得到的整集。
　　再讨论图4.6的情况。规则S[(X∧Y)∨Z]的子句形是：
　　　　～S∨X∨Z,～S∨Y∨Z
[(P∨Q)∧R]∨[S∧(T∨U)]的子句形解图集为:
　　　　P∨Q∨S,R∨S,P∨Q∨T∨U,R∨T∨U
　　应用两个规则子句中任一个对上述子句形中的S进行消解： 于是我们得到4个子句对S进行消解的消解式的完备集为：
　　　　X∨Z∨P∨Q ,Y∨Z∨P∨Q ,R∨X∨Z ,R∨Y∨Z
这些消解式全部包含在图4.4的解图所表示的子句之中。
（4）作为终止条件的目标公式

应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。用文字集表示此目标公式，并设该集各元都为析取关系。目标文字和规则可用来对与或图添加后继节点，当一个目标文字与该图中文字节点n上的一个文字相匹配时，我们就对该图添加这个节点n的新后裔，并标记为匹配的目标文字。这个后裔叫做目标节点，目标节点都用匹配弧分别接到它们的父辈节点上。当产生式系统产生一个与或图，并包含有终止在目标节点上的一个解图时，系统便成功地结束。此时，该系统实际上已推出一个等价于目标子句的一部分的子句
图4.7给出一个满足以目标公式C∨G)为基础的终止条件的与或图，可把它解释为用一个“以事实来推理”的策略对目标表达式(C∨G)的一个证明。最初的事实表达式为(A∨B)。由于不知道A或B哪个为真，因此我们可以试着首先假定A为真，然后再假定B为真，分别地进行证明。如果两个证明都成功，那么我们就得到根据析取式(A∨B)的一个证明。而A或B到底哪个为真都无关紧要。图4.7中标有(A∨B)的节点，其两个后裔由一个2线连接符来连接。因而这两个后裔都必须出现在最后解图中，如果对节点n的一个解图通过k线连接符包含n的任一后裔，那么此解图必须包含通过这个k线连接符的所有k个后裔。
图 4.7 满足中终止条件的与或图
　图4.7的例子证明过程如下：
　　　　　　　　　　　　　　　　　　事实：A∨B
　　 规则：AC∧D，BE∧G
目标: C∨G
把规则化为子句形，得子句集：
　　　　　　　　　　　　　　　　　　～A∨C，～A∨D
　　　　　　　　　　　　　　　　　　～B∨E，～B∨G
目标的否定为:　　　　　　　　　　　　～(C∨G)
其子句形为:　　　　　　　　　　　　　～C，～G
　结论：我们得到的结论是：当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止
当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。
例子：已知事实 A Ú B ，规则 A ® C Ù Ø D 和 B ® E Ù F ，使用规则正向演绎系统证
明目标 Ø D Ú E 。：

四、 规则逆向演绎系统
1、定义
　　基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从then到if的推理过程。
　　2、逆向推理过程
　　（1）目标表达式的与或形式
逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标公式化成与或形。即消去蕴涵符号，把否定符号移进括号内，对全称量词Skolem化并删去存在量词。留在目标表达式与或形中的变量假定都已存在量词量化。
举例如下：
目标表达式
　　(y)(x){P(x)[Ｑ(x,y)∧～[P(x)∧S(y)]]}
被化成与或形：
　　～P(f(y))∨{Q(f(y),y)∧[～P(f(y))∨～S(y)]}
式中，f(y)为一Skolem函数。
　　对目标的主要析取式中的变量分离标准化可得:
～P(f(z))∨{Q(f(y),y)∧[～P(f(y))∨～S(y)]}
应注意不能对析取的子表达式内的变量y改名而使每个析取式具有不同的变量。
　　与或形的目标公式也可以表示为与或图。不过，与事实表达式的与或图不同的是，对于目标表达式，与或图中的k线连接符用来分开合取关系的子表达式。上例所用的目标公式的与或图如图4.9所示。在目标公式的与或图中，我们把根节点的任一后裔叫做子目标节点，而标在这些后裔节点中的表达式叫做子目标。

图 4.9 一个目标公式的与或图表示
这个目标公式的子句形表示中的子句集可从终止在叶节点上的解图集读出：

～P(f(z)),Q(f(y),y)∧～R(f(y)),Q(f(y),y)∧～S(y)
　　可见目标子句是文字的合取，而这些子句的析取是目标公式的子句形。
　　（2）与或图的B规则变换
　　B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，我们现在把这些B规则限制为        WL             
　　形式的表达式。其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。其次，把B规则限制为这种形式的蕴涵式还可以简化匹配，使之不会引起重大的实际困难。此外，可以把像W(L1∧L2)这样的蕴涵式化为两个规则WL1和WL2。
　　（3）作为终止条件的事实节点的一致解图
逆向系逆向系统中的事实表达式均限制为文字合取形，它可以表示为一个文字集。当一个事实文字和标在该图文字节点上的文字相匹配时，就可把相应的后裔事实节点添加到该与或图中去。这个事实节点通过标有mgu的匹配弧与匹配的子目标文字节点连接起来。同一个事实文字可以多次重复使用(每次用不同变量)，以便建立多重事实节点。
　　逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。下面我们讨论一个简单的例子,看看基于规则的逆向演绎系统是怎样工作的。

举例如下：这个例子的事实、应用规则和问题分别表示于下：

事实：
　　F1: DOG(FIDO)；狗的名字叫 Fido
　　F2: ～BARKS(FIDO)；Fido是不叫的
　　F3: WAGS TAIL(FIDO)；Fido摇尾巴
　　F4: MEOWS(MYRTLE)；猫咪的名字叫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)]

图 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}。把它应用到目标表达式，我们就得到该问题的回答语句如下：
[CAT(MYRTLE)∧DOG(FIDO)∧～AFRAID(MYRTLE,FIDO)]
统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。

四、规则双向演绎系统
在上两节中我们所讨论的基于规则的正向演绎系统和逆向演绎系统都具有局限性。正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。我们希望能够构成一个组合的系统，使它具有正向和逆向两系统的优点，以求克服各自的缺点(局限性)。这个系统就是本节要研究的双向(正向和逆向)组合演绎系统。正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图最初用来表示给出的事实和目标的某些表达式集合，现在这些表达式的形式不受约束。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。设计者必须决定哪些规则用来处理事实图以及哪些规则用来处理目标图。尽管我们的新系统在修正由两部分构成的数据库时实际上只沿一个方向进行，但是我们仍然把这些规则分别称为F规则和B规则。我们继续限制F规则为单文字前项和B规则为单文字后项。
组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。这些结构可由标有合一文字的节点上的匹配棱线来连接。我们是用对应的mgu来标记匹配棱线的。对于初始图，事实图和目标图间的匹配棱线必须在叶节点之间。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。　
1、基于规则的正向演绎系统和逆向演绎系统的特点和局限性
　　正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。双向(正向和逆向)组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。
2、双向(正向和逆向)组合演绎系统的构成
　　正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正。
3、终止条件
　　组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。
在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求得这样的一个证明时，证明过程才算成功地终止。若能够断定在给定方法限度内找不到证明时过程则以失败告终。
要求：

图 4.11 CANCEL图举例用
作业思考题：
1、

2、

18