4.2 规则演绎系统

　　对于许多公式来说，子句形是一种低效率的表达式，因为一些重要信息可能在求取子句形过程中丢失。本章将研究采用易于叙述的if-then(如果-那么)规则来求解问题。
　　基于规则的问题求解系统运用下述规则来建立：

   

 

 

 

  If→Then    
  即    
 

If

 if1 if2 …
 

Then

 then1 then2 …
 

其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。

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

　　有时，then部分用于规定动作；这时，称这种基于规则的系统为反应式系统(reaction system)或产生式系统(production  system)。产生式系统将在后续篇章中予以介绍，本节讨论规则演绎系统。


4.2.1规则正向演绎系统
　　基于规则的演绎系统和产生式系统，均有两种推理方式：正向推理(forward chanining)和逆向推理(backward chaining)。
　　正向推理：从if部分向then部分推理的过程，它是从事实或状况向目标或动作进行操作的。
　　逆向推理：从then部分向if部分推理的过程，它是从目标或动作向事实或状况进行操作的。
 　　1.事实表达式的与或形变换
　　在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。要把一个公式化为与或形，可采用下列步骤：
　　(1) 利用(W1→W2)和(～W1∨W2)的等价关系，消去符号→(如果存在该符号的话)。实际上，在事实中间很少有符号→出现，因为可把蕴涵式表示为规则。
　　(2) 用狄·摩根(De Morgan)定律把否定符号移进括号内，直到每个否定符号的辖域最多只含有一个谓词为止。
　　(3) 对所得到的表达式进行Skolem化和前束化。
　　(4) 对全称量词辖域内的变量进行改名和变量标准化，而存在量词量化变量用Skolem函数代替。
　　(5) 删去全称量词，而任何余下的变量都被认为具有全称量化作用。
例如，我们有事实表达式(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)}必须注意到Q(v，A)中的变量v可用新变量w代替，而合取式[～R(v)∧～P(v)]中的变量v却不可更名，因为后者也出现在析取式～S(A,v)中。与或形表达式是由符号∧和∨连接的一些文字的子表达式组成的。呈与或形的表达式并不是子句形，而是接近于原始表达式形式，特别是它的子表达式不是复合产生的。
　　2.事实表达式的与或图表示
　　与或形的事实表达式可用与或图来表示。图4.4的与或树表示出上述例子的与或形事实表达。图4.4中，每个节点表示该事实表达式的一个子表达式。某个事实表达式(E1∨…∨Ek)的析取关系子表达式E1，…，Ek是用后继节点表示的，并由一个k线连接符把它们连接到父辈节点上。某个事实表达式(E1∧…∧En)的每个合取子表达式E1，…，En是由单一的后继节点表示的，并由一个单线连接符接到父辈接点。在事实表达式中，我们用k线连接符(一个合取记号)来分解析取式，很可能会令人感到意外。在后面的讨论中，我们将会了解到采用这种约定的原因。


　　表示某个事实表达式的与或图的叶节点均由表达式中的文字来标记。图中标记有整个事实表达式的节点，称为根节点，它在图中没有祖先。
公式的与或图表示有个有趣的性质，即由变换该公式得到的子句集可作为此与或图的解图的集合(终止于叶节点)读出；也就是说，所得到的每个子句是作为解图的各个叶节点上文字的析取。这样，由表达式
Q(w,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}
得到的子句为
　　　　Q(w,A)
　　　　～S(A,v)∨～R(v)
　　　　～S(A,v)∨～P(v)
　　上述每个子句都是图4.4解图之一的叶节点上文字的析取。所以，我们可把与或图看做是对子句集的简洁表示。不过，实际上表达式的与或图表示此子句集表示的通用性稍差，因为没有复合出共同的子表达式会妨碍在子句形中可能做到的某些变量的更名。例如，上面的最后一个子句，其变量v可全部改为u，但无法在与或图中加以表示，因而失去了通用性，并且可能带来一些困难。
　　我们一般把事实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。在本章的第二节，我们将要讨论到目标公式的与或图表示，它是按通常方式画出的，即目标在上面。