3.5 基于规则的演绎推理

上一节讨论了归结演绎推理，需要把谓词公式化为子句集，尽管这种转化在逻辑上是等价的，但是原来蕴涵在谓词公式中的一些重要信息会在求取子句集的过程中丢失。例如，下面的几个蕴涵式：

￢A∧￢B→C，￢A∧￢C→B，￢A→B∨C，￢B→A∨C，

都与子句：

A∨B∨C

等价。但在A∨B∨C中，是根本得不到原逻辑公式中所蕴涵的那些超逻辑的含义的。况且，在不少情况下，人们大多希望使用那种接近于问题原始描述的形式来进行求解，而不希望把问题描述为子句集。

规则是一种比较接近于人们习惯的问题描述方式，按照这种问题描述方式进行求解的系统称为基于规则的系统，或者叫做基于规则的演绎系统。规则演绎系统的推理可分为正向演绎推理、逆向演绎推理和双向演绎推理三种形式，本书主要讨论前面两种。

3.5.1 规则正向演绎推理

规则正向演绎和前面所讨论过的正向推理相对应。它是从已知事实出发，正向使用规则，直接进行演绎，直至到达目标为止的一种证明方法。一个直接演绎系统不一定比反演系统更有效，但其演绎过程容易被人们理解。

1.事实表达式的与/或形变换

在一个基于规则的正向演绎系统中，其前提条件中的事实表达式是作为系统的初始综合数据库来描述的。对事实的化简，只需转换成不含蕴涵符号“→”的与/或形表示即可，而不必化为子句集。把事实表达式化为非蕴涵形式的与/或形的主要步骤如下：

（1）利用规则“P→Q⇔￢P∨Q”，消去蕴涵符号。实际上，在事实表达式中很少有蕴涵符号“→”出现，因为可把蕴涵式表示成规则。

（2）利用摩根定律及量词转换律把“￢”移到紧靠谓词的位置，直到每个否定符号的辖域最多只含一个谓词为止。

（3）对所得到的表达式进行前束化。

（4）对全称量词辖域内的变元进行改名和标准化，使不同量词约束的变元有不同的名字，并利用Skolem函数消去存在量词。

（5）消去全称量词，余下的变元都被认为是全称量词量化的变元。

（6）对变元进行换名，使得各主合取式之间的变元名互不相同。例如，表达式：

（∃x）（∀y）（Q（y，x）∧￢（（R（y）∨P（y））∧S（x，y）））

可转换为：

Q（z，a）∧（（￢R（y）∧￢P（y））∨￢S（a，y））

这就是与/或形表示。

2.事实表达式的与/或树表示

事实表达式的与/或形可用一棵与/或树表示出来。例如，对上面所给出的与/或形，可用如图3.6所示的与/或树来表示。在该图中，每个节点表示该事实表达式的一个子表达式，子表达式之间的与、或关系规定如下。

当某个表达式为k个子表达式的析取时，如E1∨E2∨…∨Ek，其中的每个子表达式Ei均被表示为E1∨E2∨…∨Ek的后继节点，并由一个k线连接符（即用一个圆弧将指向这k个后继节点的边连接起来）将这些后继节点都连接到其父节点，即表示成与的关系。

当某个表达式为k个子表达式的合取时，如E1∧E2∧…∧Ek，其中的每个子表达式Ei均被表示成E1∧E2∧…∧Ek的一个单一的后继节点，并由k个单线连接符（即指向单个后继节点的有向边）将这些后继节点连接到其父节点，即表示成或的关系。

这样，与/或树的根节点就是整个事实表达式，端节点均为事实表达式中的一个文字。有了与/或树的表示，就可以求出其解树（结束于文字节点上的子树）集。并且可以发现，事实表达式的子句集和解树集之间存在着一一对应关系，即解树集中的每个解树都对应着子句集中的一个子句。其对应方式为：解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。例如，如图3.6所示的与/或树有三个解树，分别对应以下三个子句：

Q（z，a）

￢R（y）∨￢S（a，y）

￢P（y）∨￢S（a，y）

与/或树的这个性质很重要，它可以把与/或树看成是对子句集的简捷表示。不过，表达式的与/或树表示要比子句集表示的通用性差一些，原因是与/或树中的合取元没有进一步展开，因此不能像在子句集中那样对某些变量进行改名，这就限制了与/或树表示的灵活性。例如，上面的最后一个子句，在子句集中，其变量y可以全部改名为x，但无法在与/或树中加以表示，因而失去了通用性，并且可能带来一些困难。

还需要指出，这里的与/或树是作为综合数据库的一种表示形式，其中的变量受全称量词的约束，而在可分解产生式系统中，所描述的与/或树则是搜索过程的一种表示形式。这两种与/或树之间有着不同的目的和含义，因此应用时应加以区分。

3.规则的与/或形变换

在与/或形正向演绎系统中，是以正向方式使用规则（F规则）对综合数据库中的与/或树结构进行变换的。为简化这种演绎过程，通常要求F规则应具有如下形式：

L→W

式中，L为单文字；W为与/或形公式。需要注意，这里规定出现在蕴涵式中的任何变量全都受全称量词的约束，并且这些变量已经被换名，使得它们与事实公式和其他规则中的变量不同。

如果领域知识的规则表示形式与上述要求不同，则应将它转换成要求的形式。其变换步骤如下。

（1）暂时消去蕴涵符号“→”。设有公式如下：

（∀x）（（∃y）（∀z）P（x，y，z）→∀（u）Q（x，u））

运用等价关系“P→Q⇔￢P∨Q”可将上式变为：

（∀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∨Q⇔P→Q”将上式变为：

P（x，y，f（x，y））→Q（x，u）

在前面对F规则的要求中，之所以限制前件为单文字，是因为在进行正向演绎推理时要用F规则作用于表示事实的与/或树，而该与/或树的叶节点都是单文字，这样就可用F规则的前件与叶节点进行简单匹配。对非单文字情况，若形式为L1∨L2→W，则可将其转换成与之等价的两个规则L1→W与L2→W进行处理。

4.目标公式的表示形式

与/或树正向演绎系统要求目标公式用子句形式表示。如果目标公式不是子句形式，则需要将其化成子句形式。把一个目标公式转化为子句形式的步骤与前面所述的化简子句集的步骤类似，但Skolem化的过程不同。目标公式的Skolem化过程是化简子句集的Skolem化过程的对偶形式，即把目标公式中属于存在量词辖域内的全称变量用存在量化变量的Skolem函数来代替，使经Skolem化的目标公式只剩下存在量词，然后在对析取元进行变量替换，最后把存在量词消掉。

例如，设目标公式为：

（∃y）（∀x）（P（x，y）∨Q（x，y））

用Skolem函数消去全称量词后有：

（∃y）（P（f（y），y）∨Q（f（y），y））

进行变量换名，使每个析取元具有不同的变量符号，于是有：

（∃y）P（f（y），y）∨（∃z）Q（f（z），z）

最后，消去存在量词得：

P（f（y），y）∨Q（f（z），z）

这样，目标公式中的变量都假定受存在量词的约束。

5.规则正向演绎推理过程

规则正向演绎推理过程是从已知事实出发，不断运用F规则，推出欲证明目标公式的过程。即先用与/或树把已知事实表示出来，然后再用F规则的前件和与/或树的叶节点进行匹配，并通过一个匹配弧把匹配成功的F规则加入到与/或树中，依次使用F规则，直到产生一个含有以目标节点为终止节点的解图为止。

下面分命题逻辑和谓词逻辑两种情况来讨论规则正向演绎过程。

（1）命题逻辑的规则演绎过程

由于命题逻辑中的公式不含变元，因此其规则演绎过程比较简单。

例3.29 设已知事实为：

A∨B

F规则为：

r1：A→C∧D

r2：B→E∧G

目标公式为：

C∨G

证明：先将已知事实用与/或树表示出来，然后再用匹配弧把r1和r2分别连接到事实与/或树中与r1和r2前件匹配的两个不同端节点，由于出现了以目标节点为终节点的解树，故推理过程结束。这一过程如图3.7所示。在该图中，双箭头表示匹配弧，它相当于一个单线连接符。

为了验证上述推理的正确性，下面再用归结演绎推理给予证明。由已知事实、规则及目标的否定可得到如下子句集：

{A∨B，￢A∨C，￢A∨D，￢B∨E，￢B∨G，￢C，￢G}

其归结树如图3.8所示。

由图3.8可以看出，用归结演绎推理对由已知事实、F规则及目标的否定得到的子句集进行归结，得到了空子句NIL，从而证明了目标公式。它与正向推理所得到的结果是一致的。

（2）谓词逻辑的规则演绎过程

在谓词逻辑情况下，由于已知事实、F规则及目标中均含有变元，因此，其规则演绎过程还需要用最一般合一对变量进行置换。

例3.30 设已知事实的与/或形表示为：

P（x，y）∨（Q（x）∨R（v，y））

F规则为：

P（u，v）→S（u）∨N（v）

目标公式为：

S（a）∨N（b）∨Q（c）

其规则演绎过程如图3.9所示。

3.5.2 规则逆向演绎推理

基于规则的逆向演绎推理是从目标公式的与/或树出发，反向使用规则（B规则）对目标表达式的与/或树进行变换，直到得出含有事实节点的一致解图为止。

1.目标公式的与/或形变换

逆向系统中的目标公式采用/或形表示，而不像正向系统那样需要化成子句形式。在把任意目标公式化简为与/或形表示时，采用与正向系统中对事实表达式处理的对偶形式。即要用存在量词约束变元的Skolem函数来替换由全称量词约束的相应变元，消去全称量词，再消去存在量词，并进行变元换名，使主析取元之间具有不同的变元名。

例如，有如下目标公式：

（∃y）（∀x）（P（x）→（Q（x，y）∧￢（R（x）∧S（y））））

Skolem化后为：

￢P（f（y））∨（Q（f（y），y）∧（￢R（f（y））∨￢S（y）））

变元换名后为：

￢P（f（z））∨（Q（f（y），y）∧（￢R（f（y））∨￢S（y）））

2.目标公式的与/或树表示

目标公式的与/或形也可用与/或树表示出来，但其表示方法与正向演绎推理中事实的与/或树表示略有不同。它规定子表达式之间的析取关系用单线连接符连接，表示为或的关系。而子表达式之间的合取关系则用k线连接符连接，表示为与的关系。例如，对上述目标公式的与/或形，可用如图3.10所示的与/或树来表示。

在图3.10中，若把叶节点用它们之间的合取及析取关系连接起来，就可得到原目标公式的三个子目标：

￢P（f（z））

Q（f（y），y）∧￢R（f（y））

Q（f（y），y）∧￢S（y）

可见，子目标是文字的合取式。

3.B规则的表示形式

B规则的表示形式为：

W→L

式中，前项W为任一与/或形公式，后项L为一单文字。当B规则为W→L1∧L2时，则可化简为两条规则W→L1和W→L2进行处理。

4.已知事实的表示形式

逆向演绎系统的事实表达式均限制为文字合取形，即形如：

F1∧F2∧…∧Fn

式中，每个Fi（i=1，2，…，n）都为单文字，且都可单独起作用，因此可表示为如下集合形式：

{F1，F2，…，Fn}

5.规则逆向演绎推理过程

规则逆向演绎推理过程是从目标公式的与/或树出发，不断用B规则的右部和与/或树的叶节点进行匹配，并将匹配成功的B规则用最一般合一匹配弧加入到与/或树中，直到产生某个终止在事实节点上的一致解图为止。所谓一致解图是指在推理过程中所用到的置换应该是一致的。

在谓词逻辑下，用B规则的右部和与/或树的叶节点进行匹配，需要使用它们之间的最一般合一。下面通过一个例子来说明逆向演绎系统的推理过程。

例3.31 设有如下事实和规则。

事实：f1：DOG（Fido）　　　Fido是一只狗

f2：BARKS（Fido）　　　　　Fido是不叫的

f3：WAGS-TALL（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））

该目标公式经变换后得到：

CAT（x）∧DOG（y）∧￢AFRAID（x，y）

用逆向推理求解的演绎过程如图3.11所示。

该推理过程所得到的解图是一致解图。此解图中有8条匹配弧，每条匹配弧上都有一个置换。其中，终止在事实节点上的置换为{Myrtle/x}和{Fido/y}。把它们应用到目标公式，就得到了该问题的解：

CAT（Myrtle）∧DOG（Fido）∧￢AFRAID（Myrtle，Fido）

它表示：有这样一只名叫Myrtle的猫和一条名叫Fido的狗，这只猫不怕这只狗。