1、 讨论了一些简单搜索的基本原理，包括某些推理讨论了一些简单搜索的基本原理，包括某些推理规则以及置换合一等概念。但对于许多比较复杂规则以及置换合一等概念。但对于许多比较复杂的系统和问题，如果采用上一章讨论过的搜索方的系统和问题，如果采用上一章讨论过的搜索方法，那么很难甚至无法使问题获得解决的。需要法，那么很难甚至无法使问题获得解决的。需要应用一些更先进的推理技术和系统求解这种比较应用一些更先进的推理技术和系统求解这种比较复杂的问题。复杂的问题。本章讨论消解原理，规则演绎系统、产生式系统、本章讨论消解原理，规则演绎系统、产生式系统、不确定性推理和非单调推理等，不确定性推理和非单调推理等，而对于那些
2、发展特别快的高级求解技术，如专家而对于那些发展特别快的高级求解技术，如专家系统、机器学习和规划系统等，则将在后续章节系统、机器学习和规划系统等，则将在后续章节讨论它们。讨论它们。内容提要内容提要3.4 消解原理消解原理 3.5 规则演绎系统规则演绎系统 3.6 产生式系统产生式系统 3.7 系统组织技术系统组织技术3.8 不确定性推理不确定性推理 3.9 非单调推理非单调推理3.4 消解原理消解原理化为子句集化为子句集消解推理规则消解推理规则含有变量的消解式含有变量的消解式消解反演求解过程消解反演求解过程 第二章中讨论过谓词公式，某些推理规则以及置第二章中讨论过谓词公式，某些推理规则以及置换合
3、一等概念。在这个基础上，能够进一步研究换合一等概念。在这个基础上，能够进一步研究消解原理消解原理(resolution principle)。有些专家把它叫。有些专家把它叫做做归结原理归结原理。消解是一种可用于一定的子句公式的重要推理规消解是一种可用于一定的子句公式的重要推理规则。一个子句定义为由文字的则。一个子句定义为由文字的析取析取组成的公式组成的公式(一一个原子公式和原子公式的否定都叫文字个原子公式和原子公式的否定都叫文字)。当消解。当消解可使用时，消解过程被应用于母体子句对，以便可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理产生一个导出子句。例如，如
4、果存在某个公理E1E2和另一公理和另一公理E2E3，那么，那么E1E3在逻在逻辑上成立。这就是消解，而称辑上成立。这就是消解，而称E1E3为为E1E2和和E2E3的消解式的消解式(resolvent)。3.4.1 子句集的求取子句集的求取在说明消解过程之前在说明消解过程之前,我们首先说明我们首先说明任一谓词演算任一谓词演算公公式可以化成一个子句集。其变换过程由下列九式可以化成一个子句集。其变换过程由下列九个步骤组成：个步骤组成：(1)消去蕴涵符号消去蕴涵符号 只应用只应用和符号，以和符号，以AB替换替换A=B。(2)减少否定符号的辖域减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，每
5、个否定符号最多只用到一个谓词符号上，并反复应用狄并反复应用狄摩根定律。例如摩根定律。例如:以以AB代替代替(AB)以以AB代替代替(AB)以以(x)A代替代替(x)A以以(x)A代替代替(x)A以以A代替代替(A)(3)对变量标准化对变量标准化在任一量词辖域内，受该量词约束的变量为一哑在任一量词辖域内，受该量词约束的变量为一哑元元(虚构变量虚构变量)，它可以在该辖域内处处统一地被，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变另一个没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化，意味着公式的真值。合适公式中变量的标准化，意味着对哑元改名以保证每个
6、量词有其自己唯一的哑元。对哑元改名以保证每个量词有其自己唯一的哑元。(4)消去存在量词消去存在量词Skolem函数函数:在公式在公式(y)(x)P(x,y)中，存在量词是在中，存在量词是在全称量词的辖域内，我们允许所存在的全称量词的辖域内，我们允许所存在的x可能依可能依赖于赖于y值。令这种依赖关系明显地由函数值。令这种依赖关系明显地由函数g(y)所定所定义，它把每个义，它把每个y值映射到存在的那个值映射到存在的那个x。这种函数。这种函数叫做叫做Skolem函数。函数。如果用如果用Skolem函数代替存在的函数代替存在的x,我们就可以消去全我们就可以消去全部存在量词，并写成：部存在量词，并写成：
7、从一个公式消去一个存在量词的一般规则是以一个从一个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量，函数代替每个出现的存在量词的量化变量，而这个而这个Skolem函数的变量就是由那些全称量词所函数的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量词的辖域约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内。包括要被消去的存在量词的辖域在内。Skolem函函数所使用的函数符号必须是新的，即不允许是公数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数符号。式中已经出现过的函数符号。如果要消去的存在量词不在任何一个全称
8、量词的如果要消去的存在量词不在任何一个全称量词的辖域内，那么我们就用不含变量的辖域内，那么我们就用不含变量的Skolem函数即函数即常量。例如，常量。例如，(x)P(x)化为化为P(A)，其中常量符号，其中常量符号A用来表示我们知道的存在实体。用来表示我们知道的存在实体。A必须是个新的必须是个新的常量符号，它未曾在公式中其它地方使用过。常量符号，它未曾在公式中其它地方使用过。例如：例如：(z)(y)(x)P(x,y,z)被被(y)P(g(y),y,A)代替，其代替，其中中g(y)为一为一Skolem函数。函数。(5)化为前束形化为前束形 到这一步，已不留下任何存在量词，而且每个到这一步，已不留
9、下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前后面公式的整个部分。所得公式称为前束形。前束形公式由前缀和母式组成，前缀由全称量词串束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即组成，母式由没有量词的公式组成，即前束形前束形=(前缀前缀)(母式母式)全称量词串全称量词串 无量词公式无量词公式(6)把母式化为合取范式把母式化为合取范式任何母式都可写成由一些谓词公式和任何母式都可写成由
10、一些谓词公式和(或或)谓词公谓词公式的否定的析取的有限集组成的合取。这种母式式的否定的析取的有限集组成的合取。这种母式叫做合取范式。我们可以反复应用分配律。把任叫做合取范式。我们可以反复应用分配律。把任一母式化成合取范式。例如，我们把一母式化成合取范式。例如，我们把 ABC化为化为ABAC(7)消去全称量词消去全称量词 到了这一步，所有余下的量词均被全称量词量化到了这一步，所有余下的量词均被全称量词量化了。同时，全称量词的次序也不重要了。因此，了。同时，全称量词的次序也不重要了。因此，我们可以消去前缀，即消去明显出现的全称量词。我们可以消去前缀，即消去明显出现的全称量词。(8)消去连词符号消去
11、连词符号 用用(AB),(AC)代替代替(AB)(AC)，以消，以消去明显的符号去明显的符号。反复代替的结果，最后得到一。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。只由文字的析取构成的合适公式叫做一个子句。(9)更换变量名称更换变量名称可以更换变量符号的名称，使一个变量符号不出可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。例如，对于子集现在一个以上的子句中。例如，对于子集P(x)P(y)Pf(x,y),P(x)Qx,g(x),P(x)Pg(x)，在更改变量名后，可以得
12、到子，在更改变量名后，可以得到子句集：句集：P(x1)P(y)Pf(x1,y),P(x2)Qx2,g(x2),P(x3)Pg(x3)3.4.2 消解推理规则消解推理规则 令令L1为任一原子公式，为任一原子公式，L2为另一原子公式；为另一原子公式；L1和和L2具有相同的谓词符号，但一般具有不同的变具有相同的谓词符号，但一般具有不同的变量。已知两子句量。已知两子句L1和和L2如果如果L1和和L2具具有最一般合一者有最一般合一者，那么通过消解可以从这两个，那么通过消解可以从这两个父辈子句推导出一个新子句父辈子句推导出一个新子句()。这个新子句。这个新子句叫做消解式。它是由取这两个子句的析取，然后叫做
13、消解式。它是由取这两个子句的析取，然后消去互补对而得到的。消去互补对而得到的。下面举出几个从父辈子句求消解式的例子下面举出几个从父辈子句求消解式的例子:(a)假言推理假言推理 父辈子句父辈子句消解式消解式(b)合并合并(c)重言式重言式 父辈子句父辈子句消解式消解式(d)链式链式(三段论三段论)父辈子句父辈子句消解式消解式(e)空子句空子句(矛盾矛盾)上各例可见，消解可以合并几个运算为一简单的推理规则上各例可见，消解可以合并几个运算为一简单的推理规则 4.4.3 含有变量的消解式含有变量的消解式 为了对含有变量的子句使用消解规则，我们必须为了对含有变量的子句使用消解规则，我们必须找到一个找到一
14、个置换置换，作用于父辈子句使其含有，作用于父辈子句使其含有互补互补文文字。令父辈子句由字。令父辈子句由Li和和Mi给出，而且假给出，而且假设这两个子句中的变量已经分离标准化。设设这两个子句中的变量已经分离标准化。设li是是Li的一个子集，的一个子集，mi是是Mi的一个子的一个子集，使得集集，使得集li和和mi的并集存在一个最的并集存在一个最一般的一般的合一合一者者。消解两个子句。消解两个子句Li和和Mi，得到的新子句得到的新子句:Li-liMi-mi 就是这两个子句的消解式。就是这两个子句的消解式。消解两个子句时，可能有一个以上的消解式，因消解两个子句时，可能有一个以上的消解式，因为有多种选择
15、为有多种选择li和和mi的方法。不过，在的方法。不过，在任何情况下，它们最多具有有限个消解式。作为任何情况下，它们最多具有有限个消解式。作为例子，我们考虑两个子句例子，我们考虑两个子句:Px,f(A)Px,f(y)Q(y)和和 Pz,f(A)Q(z)如果取如果取 li=Px,f(A)，mi=Pz,f(A)那么得到消解式那么得到消解式:Pz,f(y)Q(z)Q(y)如果取如果取 li=Q(y)，mi=Q(z)那么得到消解式：那么得到消解式：Px,f(A)Px,f(y)Py,f(A)进一步消解得消解式为：进一步消解得消解式为：Py,f(y)可见这两个子句消解一共可得可见这两个子句消解一共可得4个不
16、同的消解式，个不同的消解式，其中其中3个是消解个是消解P得到的，而另一个是由消解得到的，而另一个是由消解Q得得到的。到的。下面举几个对含有变量的子句使用消解的例子。下面举几个对含有变量的子句使用消解的例子。例例1：例例2：例例3：本节中所例举的对基子句和对含有变量的子句进行消解的例子，其父辈子句和消解式列表示于表4.1。这些例子表示出消解推理的某些常用规则。表表 4.1 消解推理常用规则消解推理常用规则3.4.4 消解反演求解过程消解反演求解过程1 基本思想基本思想 把要解决的问题作为一个要证明的命题，其目标把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式公
17、式被否定并化成子句形，然后添加到命题公式集中去集中去,把消解反演系统应用于联合集，并推导出把消解反演系统应用于联合集，并推导出一个空子句一个空子句(NIL)，产生一个矛盾，这说明目标，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决。这与数学中反证法的思想得证，问题得到解决。这与数学中反证法的思想十分相似。十分相似。2 消解反演消解反演(1)反演求解的步骤反演求解的步骤 给出一个公式集给出一个公式集S和自标公式和自标公式L，通过反证或反演，通过反证或反演来求证目标公式来求证目标公式L，其证明步骤如下：，其证明步骤如下
18、：(a)否定否定L，得，得L；(b)把把L添加到添加到S中去；中去；(c)把新产生的集合把新产生的集合L，S化成子句集；化成子句集；(d)应用消解原理，力图推导出一个表示矛盾的空应用消解原理，力图推导出一个表示矛盾的空子句子句NIL。(2)反演求解的正确性反演求解的正确性设公式设公式L在逻辑上遵循公式集在逻辑上遵循公式集S，那么按照定义满足，那么按照定义满足S的每个解释也满足的每个解释也满足L。决不会有满足。决不会有满足S的解释能的解释能够满足够满足L的，所以不存在能够满足并集的，所以不存在能够满足并集SL的解释。如果一个公式集不能被任一解释所的解释。如果一个公式集不能被任一解释所满足，那么这
19、个公式是不可满足的。因此，如果满足，那么这个公式是不可满足的。因此，如果L在逻辑上遵循在逻辑上遵循S，那么，那么SL是不可满足是不可满足的。可以证明，如果消解反演反复应用到不可满的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句足的子句集，那么最终将要产生空子句NIL。因。因此，如果此，如果L在逻辑上遵循在逻辑上遵循S，那么由并集，那么由并集SL消解得到的子句，最后将产生空子句；反之，消解得到的子句，最后将产生空子句；反之，可以证明，如果从可以证明，如果从SL的子句消解得到空的子句消解得到空子句，那么子句，那么L在逻辑上遵循在逻辑上遵循S。(3)反演求解的举例反演求解
20、的举例 下面举个例子来说明消解反演过程：下面举个例子来说明消解反演过程：前提：每个储蓄钱的人都获得利息。前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱。结论：如果没有利息，那么就没有人去储蓄钱。证明：令证明：令S(x,y)表示表示x储蓄储蓄y M(x)表示表示x是钱是钱 I(x)表示表示x是利息是利息 E(x，y)表示表示x获得获得y于是上述命题写成下列形式：于是上述命题写成下列形式：结论结论:用化为子句集的九步法，可把前提和结论化用化为子句集的九步法，可把前提和结论化为下列的子句集：为下列的子句集：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f
21、(x)其中，其中，y=f(x)为为Skolem函数。而函数。而,L I(z),S(a,b),M(b)以下按上述的四个步骤来对问题进行反演求解：以下按上述的四个步骤来对问题进行反演求解：否定否定L，即有，即有 L I(z),S(a,b),M(b)把把 L添加到添加到S中去，即中去，即 S=L，S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),M(b)把新产生的集合把新产生的集合S化成子句集化成子句集,即即 S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),M(b)应用消解原理，力图推导出一个表示矛
22、盾的空子应用消解原理，力图推导出一个表示矛盾的空子句句NIL。该消解反演可以表示为一棵反演树，如。该消解反演可以表示为一棵反演树，如下图下图4.1所示，其根节点为所示，其根节点为NIL。因此，储蓄问题。因此，储蓄问题的结论获得证明。的结论获得证明。图图 4.1 储蓄问题反演树储蓄问题反演树(4)反演求解过程反演求解过程 从反演求解的举例中可以看出，用反演树求取从反演求解的举例中可以看出，用反演树求取对某个问题的答案，其过程如下：对某个问题的答案，其过程如下：(a)把由目标公式的把由目标公式的否定否定产生的每个子句添加到产生的每个子句添加到目标公式否定之否定的子句中去。目标公式否定之否定的子句中
23、去。(b)按照反演树，执行和以前相同的消解，直至按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。在根部得到某个子句止。(c)用根部的子句作为一个回答语句。用根部的子句作为一个回答语句。答案求取涉及到把一棵根部有答案求取涉及到把一棵根部有NIL的反演树变换的反演树变换为在根部带有可用作答案的某个语句的一颗证明为在根部带有可用作答案的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否定产树。由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言式，所以被变换的生的每个子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部的语句证明树就是一棵消解的证明树，
24、其在根部的语句在逻辑上遵循公理加上重言式，因而也单独地遵在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证明了求取循公理。因此被变换的证明树本身就证明了求取办法是正确的。下面讨论一个简单的问题，作为办法是正确的。下面讨论一个简单的问题，作为例子：例子：“如果无论约翰如果无论约翰(John)到哪里去，菲多到哪里去，菲多(Fido)也也就去那里，那么如果约翰在学校里，菲多在哪里就去那里，那么如果约翰在学校里，菲多在哪里呢呢?”很清楚，这个问题说明了两个事实，然后提出一个问题，很清楚，这个问题说明了两个事实，然后提出一个问题，而问题的答案大概可从这两个事实推导出。这两个事实
25、而问题的答案大概可从这两个事实推导出。这两个事实可以解释为下列公式集可以解释为下列公式集S：(x)AT(JOHN,X)=AT(FIDO,X)和和T(JOHN,SCHOOL)如果我们首先证明公式如果我们首先证明公式(x)AT(FIDO,X)在逻辑上遵循在逻辑上遵循S，然后寻求一个存在，然后寻求一个存在x的例，那么就能解决的例，那么就能解决“菲多在哪菲多在哪里里”的问题。关键想法是把问题化为一个包含某个存在的问题。关键想法是把问题化为一个包含某个存在量词的目标公式，使得此存在量词量化变量表示对该问量词的目标公式，使得此存在量词量化变量表示对该问题的一个解答。如果问题可以从给出的事实得到答案，题的一
26、个解答。如果问题可以从给出的事实得到答案，那么按这种方法建立的目标函数在逻辑上遵循那么按这种方法建立的目标函数在逻辑上遵循S。在得到。在得到一个证明之后，我们就试图求取存在量词量化变量的一一个证明之后，我们就试图求取存在量词量化变量的一个例，作为一个回答。对于上述例题能够容易地证明个例，作为一个回答。对于上述例题能够容易地证明(x)AT(FIDO,X)遵循遵循S。我们也可以说明，用一种比较简。我们也可以说明，用一种比较简单的方法来求取合适的答案。单的方法来求取合适的答案。消解反演可用一般方式得到，其办法是首先对被消解反演可用一般方式得到，其办法是首先对被证明的公式加以否定，再把这个否定式附加到
27、集证明的公式加以否定，再把这个否定式附加到集S中去，化这个扩充集的所有成员为子句形，然中去，化这个扩充集的所有成员为子句形，然后用消解证明这个子句集是不可满足的。图后用消解证明这个子句集是不可满足的。图4.2表表示出上例的反演树。从示出上例的反演树。从S中的公式得到的子句叫中的公式得到的子句叫做公理。注意目标公式做公理。注意目标公式(x)AT(FIDO,x)的否定产的否定产生生(x)AT(FIDO,x)其子句形式为其子句形式为:AT(FIDO,x)对本例应用消解反演求解过程，我们有：对本例应用消解反演求解过程，我们有：(1)目目标公式否定的子句形式为标公式否定的子句形式为:AT(FIDO,x)
28、把它添把它添加至目标公式的否定之否定的子句中去，得重言加至目标公式的否定之否定的子句中去，得重言式式 AT(FIDO,x)AT(FIDO,x)(2)用图用图4.3的反的反演树进行消解，并在根部得到子句演树进行消解，并在根部得到子句:AT(FIDO，SCHOOL)(3)从根部求得答案从根部求得答案AT(FIDO，SCHOOL)，用此子句作为回答语句。因此，子，用此子句作为回答语句。因此，子句句 AT(FIDO，SCHOOL)就是这个问题的合适答就是这个问题的合适答案，见图案，见图4.3。图图 4.2 菲多在哪里菲多在哪里例题的反演树例题的反演树图图 4.3 从消解求取答案例题的反演树从消解求取答
29、案例题的反演树3.5 规则演绎系统规则演绎系统 规则演绎系统规则演绎系统规则正向演绎系统规则正向演绎系统 规则逆向演绎系统规则逆向演绎系统规则双向演绎系统规则双向演绎系统 对于许多公式来说，子句形是一种对于许多公式来说，子句形是一种低效率低效率的表达式，因为一些重要信息可能在求取的表达式，因为一些重要信息可能在求取子句形过程中子句形过程中丢失丢失。本章将研究采用易于。本章将研究采用易于叙述的叙述的if-then(如果如果-那么那么)规则规则来求解问题来求解问题 基于规则的问题求解系统运用下述规则基于规则的问题求解系统运用下述规则:在所有基于规则系统中，每个在所有基于规则系统中，每个if可能与某
30、断言可能与某断言(assertion)集中的一个或多个断言匹配。有时把集中的一个或多个断言匹配。有时把该断言集称为该断言集称为工作内存工作内存。在许多基于。在许多基于规则规则系统中，系统中，then部分用于规定放入工作内存的部分用于规定放入工作内存的新断言新断言。这种。这种基于规则的系统叫做规则演绎系统基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中，通常称每个。在这种系统中，通常称每个if部分为部分为前项前项(antecedent)，称每个，称每个then部分为部分为后项后项(consequent)。有时，有时，then部分用于部分用于规
31、定动作规定动作；这时，称这种基；这时，称这种基于规则的系统为反应式系统于规则的系统为反应式系统(reaction system)或产或产生式系统生式系统(production system)。产生式系统将在。产生式系统将在后续篇章中予以介绍，本节讨论规则演绎系统。后续篇章中予以介绍，本节讨论规则演绎系统。3.5.1 规则正向演绎系统规则正向演绎系统 基于规则的演绎系统和产生式系统，均有两种推基于规则的演绎系统和产生式系统，均有两种推理方式：理方式：正向推理正向推理(forward chanining)和逆向推理和逆向推理(backward chaining)。正向推理正向推理：从：从if部分向
32、部分向then部分推理的过程，它部分推理的过程，它是从是从事实或状况事实或状况向向目标或动作目标或动作进行操作的。进行操作的。逆向推理逆向推理：从：从then部分向部分向if部分推理的过程，它部分推理的过程，它是从目标或动作向事实或状况进行操作的。是从目标或动作向事实或状况进行操作的。1.事实表达式的事实表达式的与或形与或形变换变换 在基于规则的正向演绎系统中，我们把事实表示在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的为非蕴涵形式的与或形，作为系统的总数据库总数据库。我们不想把这些事实化为子句形，而是把它们表我们不想把这些事实化为子句形，而是把它们表示为谓词演算公
33、式，并把这些公式变换为叫做与示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。要把一个公式化为与或形，或形的非蕴涵形式。要把一个公式化为与或形，可采用下列步骤：可采用下列步骤：(1)利用利用(W1W2)和和(W1W2)的等价关系，的等价关系，消去符号消去符号(如果存在该符号的话如果存在该符号的话)。实际上，在。实际上，在事实中间很少有符号事实中间很少有符号出现，因为可把蕴涵式表出现，因为可把蕴涵式表示为规则。示为规则。(2)用狄用狄摩根摩根(De Morgan)定律把否定符号移进括定律把否定符号移进括号内，直到每个号内，直到每个否定符号否定符号的的辖域辖域最多只含有一个最多只含有一个
34、谓词为止。谓词为止。(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)对变量更名标准化，使得同一变量不出现在事
35、实对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中。更名后得表达式：表达式的不同主要合取式中。更名后得表达式：Q(w,A)R(v)P(v)S(A,v)必须注意必须注意到到Q(v，A)中的变量中的变量v可用新变量可用新变量w代替，而合取代替，而合取式式R(v)P(v)中的变量中的变量v却不可更名，因为却不可更名，因为后者也出现在析取式后者也出现在析取式S(A,v)中。中。与或形表达式与或形表达式是由符号是由符号和和连接的一些文字的子表达式组成连接的一些文字的子表达式组成的的。呈与或形的表达式并不是子句形，而是接近。呈与或形的表达式并不是子句形，而是接近于原始表达式形式，特别是它
36、的子表达式不是复于原始表达式形式，特别是它的子表达式不是复合产生的。合产生的。2.事实表达式的与或图表示事实表达式的与或图表示 与或形的事实表达式可用与或图来表示。如图与或形的事实表达式可用与或图来表示。如图4.4的与或树表示出上述例子的与或形事实表达。的与或树表示出上述例子的与或形事实表达。图图4.4中，每个节点表示该事实表达式的一个子表中，每个节点表示该事实表达式的一个子表达式。某个事实表达式达式。某个事实表达式(E1Ek)的析取关系的析取关系子表达式子表达式E1，Ek是用后继节点表示的，并是用后继节点表示的，并由一个由一个k线连接符线连接符把它们连接到父辈节点上。某把它们连接到父辈节点上
37、。某个事实表达式个事实表达式(E1En)的每个合取子表达式的每个合取子表达式E1，En是由单一的后继节点表示的，并由是由单一的后继节点表示的，并由一个单线连接符接到父辈接点。在事实表达式中，一个单线连接符接到父辈接点。在事实表达式中，我们用我们用k线连接符线连接符(一个合取记号一个合取记号)来分解析取式，来分解析取式，很可能会令人感到意外。在后面的讨论中，我们很可能会令人感到意外。在后面的讨论中，我们将会了解到采用这种约定的原因。将会了解到采用这种约定的原因。图图 4.4 一个事实表达式的与或树表示一个事实表达式的与或树表示 表示某个事实表达式的与或图的叶节点均由表达表示某个事实表达式的与或图
38、的叶节点均由表达式中的文字来标记。图中标记有整个事实表达式式中的文字来标记。图中标记有整个事实表达式的节点，称为根节点，它在图中没有祖先。的节点，称为根节点，它在图中没有祖先。公式的与或图表示有个有趣的性质，即由变公式的与或图表示有个有趣的性质，即由变换该公式得到的子句集可作为此与或图的解图的换该公式得到的子句集可作为此与或图的解图的集合集合(终止于叶节点终止于叶节点)读出；也就是说，所得到的读出；也就是说，所得到的每个子句是作为解图的各个叶节点上文字的析取。每个子句是作为解图的各个叶节点上文字的析取。这样，由表达式这样，由表达式 Q(w,A)R(v)P(v)S(A,v)得到的子句为得到的子句
39、为 Q(w,A),S(A,v)R(v),S(A,v)P(v)上述每个子句都是图上述每个子句都是图4.4解图之一的叶节点上文字解图之一的叶节点上文字的的析取析取。所以，我们可把与或图看做是对子句集。所以，我们可把与或图看做是对子句集的的简洁表示简洁表示。不过，实际上表达式的与或图表示。不过，实际上表达式的与或图表示此子句集表示的通用性稍差，因为没有复合出共此子句集表示的通用性稍差，因为没有复合出共同的同的子表达式子表达式会妨碍在子句形中可能做到的某些会妨碍在子句形中可能做到的某些变量的更名。例如，上面的最后一个子句，其变变量的更名。例如，上面的最后一个子句，其变量量v可全部改为可全部改为u，但无
40、法在与或图中加以表示，但无法在与或图中加以表示，因而失去了通用性，并且可能带来一些困难。因而失去了通用性，并且可能带来一些困难。我们一般把事实表达式的与或图表示我们一般把事实表达式的与或图表示倒过来画倒过来画，即把根节点画在最下面，而把其后继节点往上画。即把根节点画在最下面，而把其后继节点往上画。在本章的第二节，我们将要讨论到目标公式的与在本章的第二节，我们将要讨论到目标公式的与或图表示，它是按通常方式画出的，即目标在上或图表示，它是按通常方式画出的，即目标在上面。面。3.与或图的与或图的F规则变换规则变换 这些规则是建立在某个问题辖域中普通陈述性知这些规则是建立在某个问题辖域中普通陈述性知识
41、的蕴涵公式基础上的。我们把允许用作规则的识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：公式类型限制为下列形式：L W 式中：式中：L是单文字；是单文字；W为与或形的唯一公式。我为与或形的唯一公式。我们也假设出现在蕴涵式中的任何变量都有全称量们也假设出现在蕴涵式中的任何变量都有全称量化作用于整个蕴涵式。这些事实和规则中的一些化作用于整个蕴涵式。这些事实和规则中的一些变量被分离标准化，使得没有一个变量出现在一变量被分离标准化，使得没有一个变量出现在一个以上的规则中，而且使规则变量不同于事实变个以上的规则中，而且使规则变量不同于事实变量。单文字前项的任何蕴涵式，不管其量化情况量。
42、单文字前项的任何蕴涵式，不管其量化情况如何都可以化为某种量化辖域为整个蕴涵式的形如何都可以化为某种量化辖域为整个蕴涵式的形式。这个变换过程首先把这些变量的量词局部地式。这个变换过程首先把这些变量的量词局部地调换到前项，然后再把全部存在量词调换到前项，然后再把全部存在量词Skolem化。化。举例说明如下：举例说明如下：公式公式(x)(y)(z)P(x,y,z)(u)Q(x,u可以通过下列步骤加以变换：可以通过下列步骤加以变换：(1)暂时消去蕴涵符号暂时消去蕴涵符号 (x)(y)(z)P(x,y,z)(u)Q(x,u)(2)把否定符号移进第一个析把否定符号移进第一个析 取式内，调换变量的取式内，调
43、换变量的量词量词 (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)以下用一个自由变量的命题演算情况来说明如何以下用一个自由变量的命题演算情况来说明如何把这类规则应用于与或图。把这类规则应用于与或图。把形式为把形式为L W的规则应用到任一个具有叶节点的规则应用到任一个具有叶节点n并由文字并由文字L标记的与或图上，可以得到一个新的标记的与或图上
44、，可以得到一个新的与或图。在新的图上，节点与或图。在新的图上，节点n由一个由一个单线连接符单线连接符接到后继节点接到后继节点(也由也由L标记标记)，它是表示为，它是表示为W的一个的一个与或图结构的根节点。作为例子，考虑把规则与或图结构的根节点。作为例子，考虑把规则 S (XY)Z应用到图应用到图4.5所示的与或图中标有所示的与或图中标有S的叶节点上。所得到的新与或图结构表示于图的叶节点上。所得到的新与或图结构表示于图4.6，图中标记，图中标记S的两个节点由一条叫做匹配弧的的两个节点由一条叫做匹配弧的弧线连接起来。弧线连接起来。图图 4.5 不含变量的与或图不含变量的与或图 4.6 应用一条应用
45、一条 规则得到的与或图规则得到的与或图 在应用某条规则之前，一个与或图在应用某条规则之前，一个与或图(如图如图4.5)表示表示一个具体的事实表达式。其中，在叶节点结束的一个具体的事实表达式。其中，在叶节点结束的一组解图表示该事实表达式的子句形。我们希望一组解图表示该事实表达式的子句形。我们希望在应用规则之后得到的图，既能表示原始在应用规则之后得到的图，既能表示原始事实事实，又能表示从原始事实和该规则又能表示从原始事实和该规则推出推出的事实表达式。的事实表达式。假设我们有一条规则假设我们有一条规则LW，根据此规则及事实表，根据此规则及事实表达式达式F(L)，可以推出表达式，可以推出表达式F(W)
46、。F(W)是用是用W代代替替F中的所有中的所有L而得到的。当用规则而得到的。当用规则L W来变换来变换以上述方式描述的以上述方式描述的F(L)的与或图表示时，我们就的与或图表示时，我们就产生一个含有产生一个含有F(W)表示的新图；也就是说，它是表示的新图；也就是说，它是以叶节点终止的解图集以以叶节点终止的解图集以F(W)子句形式代表该子子句形式代表该子句集。这个子句集包括在句集。这个子句集包括在F(L)的子句形和的子句形和LW的子的子句形间对句形间对L进行所有可能的消解而得到的整集。进行所有可能的消解而得到的整集。再讨论图再讨论图4.6的情况。规则的情况。规则S(XY)Z的子的子句形是：句形是
47、：SXZ,SYZ(PQ)RS(TU)的子句形解图集为的子句形解图集为:PQS,RS,PQTU,RTU应用两个规则子句中任一个对上述子句形中应用两个规则子句中任一个对上述子句形中的的S进行消解：进行消解：于是我们得到于是我们得到4个子句对个子句对S进行消进行消解的消解式的完备集为：解的消解式的完备集为：XZPQ,YZPQ,RXZ,RYZ 这些消解式全部包含在图这些消解式全部包含在图4.4的解图所表示的子句的解图所表示的子句之中。之中。从上述讨论我们可以得出结论：应用一条规则到从上述讨论我们可以得出结论：应用一条规则到与或图的过程，以极其经济的方式达到了用其它与或图的过程，以极其经济的方式达到了用
48、其它方法要进行方法要进行多次多次消解才能达到的目的。消解才能达到的目的。我们要使应用一条规则得到的与或图我们要使应用一条规则得到的与或图继续表示继续表示事事实表达式和推得的表达式，这可利用匹配弧两侧实表达式和推得的表达式，这可利用匹配弧两侧有相同标记的节点来实现。对一个节点应用一条有相同标记的节点来实现。对一个节点应用一条规则之后，此节点就不再是该图的叶节点。不过，规则之后，此节点就不再是该图的叶节点。不过，它仍然由单一文字标记而且可以继续具有一些应它仍然由单一文字标记而且可以继续具有一些应用于它的规则。我们把图中标有单文字的任一节用于它的规则。我们把图中标有单文字的任一节点都称为文字节点，由
49、一个与或图表示的子句集点都称为文字节点，由一个与或图表示的子句集就是对应于该图中以文字节点终止的解图集。就是对应于该图中以文字节点终止的解图集。4.作为终止条件的目标公式作为终止条件的目标公式应用应用F规则的目的在于从某个事实公式和某个规则规则的目的在于从某个事实公式和某个规则集出发来集出发来证明证明某个目标公式。在正向推理系统中，这某个目标公式。在正向推理系统中，这种目标表达式只限于种目标表达式只限于可证明可证明的表达式，尤其是可证明的表达式，尤其是可证明的的文字析取形文字析取形的目标公式表达式。我们用文字集表示的目标公式表达式。我们用文字集表示此目标公式，并设该集各元都为析取关系。此目标公
50、式，并设该集各元都为析取关系。(在以后各在以后各节所要讨论的逆向系统和双向系统，都不对目标表达节所要讨论的逆向系统和双向系统，都不对目标表达式作此限制。式作此限制。)目标文字和规则可用来对与或图添加后目标文字和规则可用来对与或图添加后继节点，当一个目标文字与该图中文字节点继节点，当一个目标文字与该图中文字节点n上的一个上的一个文字相匹配时，我们就对该图添加这个节点文字相匹配时，我们就对该图添加这个节点n的新后裔，的新后裔，并标记为匹配的目标文字。这个后裔叫做目标节点，并标记为匹配的目标文字。这个后裔叫做目标节点，目标节点都用匹配弧分别接到它们的父辈节点上。当目标节点都用匹配弧分别接到它们的父辈
