规则演绎系统

1教案名称规则演绎系统科目教学对象主讲人课时一、教学内容规则演绎系统属于高级搜索推理技术，用于解决比较复杂的系统和问题。本节介绍规则演绎系统的定义及其三种推理方法：规则正向演绎系统、规则逆向演绎系统和规则双向演绎系统。教学重点：规则演绎系统的定义、正向推理和逆向推理过程。教学难点：双向演绎的匹配问题等。教学方法：课堂教学为主。通过比较揭示正向推理、逆向推理和双向推理的特点。教学要求：掌握规则演绎系统的定义和正向推理、逆向推理的过程，了解规则双向演绎系统。二、教学流程（教学策略选择与设计）1、复习一下上次课老师讲过的消解原理2、由消解原理的不足，引出本次课讲的规则演绎系统，并给出其定义3、给出正向推理和逆向推理过程4、总结以上推理，给出双向推理过程，并给出相应例子教学过程一、复习消解原理在说明归结过程之前，我们首先说明任一谓词演算公式可以化成一个子句集。1.消去蕴涵符号只应用∨和~符号，以~A∨B替换A=B。2.减少否定符号的辖域每个否定符号~最多只用到一个谓词符号上，并反复应用狄摩根律。如以~A∨~B代替~（A∧B）以~A∧~B代替~（A∨B）2以A代替~（~A）以(x){~A}代替~（x）A以(x){~A}代替~（x）A3.对变量标准化在任一量词辖域内，受该量词约束的变量为一哑元（虚构变量），它可以在该辖域内处处统一的被另一个没有出现过的任意变量所代替，而不改变公式的真值。没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。如，把(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}，以消去明显的符号∧。反复代替的结果，最后得到一个有限集，其中每3个公式是文字的析取。任一只由文字的析取构成的合适公式叫做一个子句。9.更换变量名称更换变量名称，是一个变量符号不出现在一个以上的子句中。问题：归结方法不自然，并非人类的自然思维方式可能会丢失蕴涵关系中所包含的控制信息例：以下蕴涵式：~A~BC~CAB~A~CB~ACB~B~BA~BAC均与子句(ABC)等价，但显然上面的蕴涵式信息更丰富二、规则演绎系统的定义：其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。在所有基于规则系统中，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rulebaseddeductionsystem)。在这种系统中，通常称每个if部分为前项(antecedent)，称每个then部分为后项(consequent)4先举一简单例子，帮助我们理解一下：三、规则正向演绎系统1、定义正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。2、正向推理过程(步骤)（1）事实表达式的与或形变换把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句形类似。注意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与5或形的非蕴涵形式。要把一个公式化为与或形，可采用下列步骤：例如，我们有事实表达式(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)6一般把事实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。上节的与或图表示，就是按通常方式画出的，即目标在上面。（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的两个节点由一条叫做匹配弧的弧线连接起来。7图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）作为终止条件的目标公式8应用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∨G9目标的否定为:～(C∨G)其子句形为:～C，～G结论：我们得到的结论是：当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。例子：已知事实AB，规则ACD和BEF，使用规则正向演绎系统证明目标DE。：10四、规则逆向演绎系统1、定义基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从then到if的推理过程。2、逆向推理过程（1）目标表达式的与或形式逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标公式化成与或形。即消去蕴涵符号，把否定符号移进括号内，对全称量词Skolem化并删去存在量词。留在目标表达式与或形中的变量假定都已存在量词量化。举例如下：目标表达式(y)(x){P(x)[Ｑ(x,y)∧～[P(x)