3.4.3 含有变量的消解式

1、消解式求法

为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句使其含有互补文字。

2、例子

P(x)∨Q(x) ～Q［f(y)］

置换σ=｛f(y)/x｝

P［f(y)］

3.4.4 消解反演求解过程

1、基本思想

把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决，与数学中反证法的思想十分相似。

2、消解反演

反演求解的步骤

给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下： (1)否定L，得～L；

(2)把～L添加到S中去；

(3)把新产生的集合｛～L，S｝化成子句集；

(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。 反演求解的正确性

设公式L在逻辑上遵循公式集S，那么按照定义满足S的每个解释也满足L。决不会有满足S的解释能够满足～L的，所以不存在能够满足并集S∪｛～L｝的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，如果L在逻辑上遵循S，那么S∪｛～L｝是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句NIL。因此，如果L在逻辑上遵循S，那么由并集S∪｛～L｝消解得到的子句，最后将产生空子句；反之，可以证明，如果从S∪｛～L｝的子句消解得到空子句，那么L在逻辑上遵循S。

3、反演求解过程 步骤：

(1)把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。 (2)按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。 (3)用根部的子句作为一个回答语句。 分析：

答案求取涉及到把一棵根部有NIL的反演树思考：应用消解反演求解如下问题： 变换为在根部带有可用作答案的某个语句的一颗“如果无论约翰(John)到哪里去，菲证明树。由于变换关系涉及到把由目标公式的否多(Fido)也就去那里，那么如果约翰定产生的每个子句变换为一个重言式，所以被变在学校里，菲多在哪里呢?” 换的证明树就是一棵消解的证明树，其在根部的

29

语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。

例：储蓄问题

前提：每个储蓄钱的人都获得利息。

结论：如果没有利息，那么就没有人去储蓄钱

3.5 规则演绎系统

教学内容：规则演绎系统属于高级搜索推理技术，用于解决比较复杂的系统和问题。本节介绍规则演绎系统的定义及其三种推理方法：规则正向演绎系统、规则逆向演绎系统和规则双向演绎系统。

教学重点：规则演绎系统的定义、正向推理和逆向推理过程。 教学难点：双向演绎的匹配问题等。

教学方法：课堂教学为主。通过比较揭示正向推理、逆向推理和双向推理的特点。 教学要求：掌握规则演绎系统的定义和正向推理、逆向推理的过程，了解规则双向演绎系统。

规则演绎系统的定义：

基于规则的问题求解系统运用下述规则来建立： If→Then

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

3.5.1规则正向演绎系统

1、定义

正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。

2、正向推理过程

（1）事实表达式的与或形变换把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句形类似。

注意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。

例：有事实表达式

( u)(?v)｛Q(v，u)∧～［(R(v)∨P(v))∧S(u，v)］｝把它化为 Q(v,A)∧｛［～R(v)∧～P(v)］∨～S(A,v)｝

对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中，得： Q(w,A)∧｛［～R(v)∧～P(v)］∨～S(A,v)｝ （2）事实表达式的与或图表示

30

将上例与或形的事实表达式用与或图来表示，见图3.1。

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) 图 3.1 一个事实表达式的与或树表示

一般把事实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。上节的与或图表示，就是按通常方式画出的，即目标在上面。

（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进行所有可能的消解而得到的整集。该过程以极其有效的方式达到了用其它方法要进行多次消解才能达到的目的。

（4）作为终止条件的目标公式

应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。用文字集表示此目标公式，并设该集各元都为析取关系。

结论：

当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。

3.5.2 规则逆向演绎系统

1、定义

基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从then到if的推理过程。

2、逆向推理过程

（1）目标表达式的与或形式

逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过

31

程，把目标公式化成与或形。

（2）与或图的B规则变换

B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，我们现在把这些B规则限制为

W?L (3.4) 形式的表达式。其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。

（3）作为终止条件的事实节点的一致解图

逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。

提问：逆向推理与正向推理的区别有哪些？ 3.5.3 规则双向演绎系统

1、 基于规则的正向演绎系统和逆向演绎系统的特点和局限性

正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。双向(正向和逆向)组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。

2、 双向(正向和逆向)组合演绎系统的构成

正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正。

3、 终止条件

组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。

在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求得这样的一个证明时，证明过程才算成功地终止。若能够断定在给定方法限度内找不到证明时过程则以失败告终。

3.6 产生式系统

教学内容：本节介绍产生式系统的定义、组成和推理技术。

教学重点：产生式系统与规则演绎系统的差别和产生式系统的组成。 教学难点：产生式系统的控制策略等。

学方法：课堂教学和实验相结合。重点讲解原理，通过实验进一步领会系统的精髓。充分利用网络课程中的多媒体素材来表示抽象概念。

教学要求：掌握产生式系统的组成结构，通过实践掌握产生式系统的设计和工作过程。

定义：

在基于规则系统中，每个if可能与某断言(assertion)集中的一个或

提问：产生式系多个断言匹配，then部分用于规定放入工作内存的新断言。当then部

统与规则演绎系分用于规定动作时，称这种基于规则的系统为反应式系统(reaction

统有什么区别？ system)或产生式系统(production system)。

32