如果采用上一章讨论过的搜索方法那么很难甚至无法使问ppt课件

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)消去全称量词消去全称量词 到了这一步，一切余下的量词均被全称量词量化到了这一步，一切余下的量词均被全称量词量化了。同时，全称量词的次序也不重要了。因此，了。同时，全称量词的次序也不重要了。因此，我们可以消去前缀，即消去明显出现的全称量词。我们可以消

11、去前缀，即消去明显出现的全称量词。(8)消去连词符号消去连词符号 用用(AB), (AC)替代替代(AB)(AC)，以消，以消去明显的符号去明显的符号。反复替代的结果，最后得到一。反复替代的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的适宜公式叫做一个子句。只由文字的析取构成的适宜公式叫做一个子句。 (9)改换变量称号改换变量称号可以改换变量符号的称号，使一个变量符号不出可以改换变量符号的称号，使一个变量符号不出如今一个以上的子句中。例如，对于子集如今一个以上的子句中。例如，对于子集P(x)P(y)Pf(x,y),P(x

12、)Qx,g(x),P(x)Pg(x)，在更改动量名后，可以得到子，在更改动量名后，可以得到子句集：句集：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) 进一步消

16、解得消解式为：进一步消解得消解式为：Py,f(y) 可见这两个子句消解一共可得可见这两个子句消解一共可得4个不同的消解式，个不同的消解式，其中其中3个是消解个是消解P得到的，而另一个是由消解得到的，而另一个是由消解Q得得到的。到的。 下面举几个对含有变量的子句运用消解的例子。下面举几个对含有变量的子句运用消解的例子。 例例1：例例2：例例3： 本节中所例举的对基子句和对含有变量的子句进展消解的例子，其父辈子句和消解式列表示于表4.1。这些例子表示出消解推理的某些常用规那么。 表表 4.1 消解推理常用规那么消解推理常用规那么3.4.4 消解反演求解过程消解反演求解过程1 根本思想根本思想把要处

17、理的问题作为一个要证明的命题，其目的公把要处理的问题作为一个要证明的命题，其目的公式被否认并化成子句形，然后添加到命题公式集式被否认并化成子句形，然后添加到命题公式集中去中去,把消解反演系统运用于结合集，并推导出一把消解反演系统运用于结合集，并推导出一个空子句个空子句(NIL)，产生一个矛盾，这阐明目的公，产生一个矛盾，这阐明目的公式的否认式不成立，即有目的公式成立，定理得式的否认式不成立，即有目的公式成立，定理得证，问题得到处理。这与数学中反证法的思想非证，问题得到处理。这与数学中反证法的思想非常类似。常类似。2 消解反演消解反演(1) 反演求解的步骤反演求解的步骤 给出一个公式集给出一个公

18、式集S和自标公式和自标公式L，经过反证或反演，经过反证或反演来求证目的公式来求证目的公式L，其证明步骤如下：，其证明步骤如下：(a)否认否认L，得，得L；(b)把把L添加到添加到S中去；中去；(c)把新产生的集合把新产生的集合L，S化成子句集；化成子句集；(d)运用消解原理，力图推导出一个表示矛盾的空运用消解原理，力图推导出一个表示矛盾的空子句子句NIL。(2) 反演求解的正确性反演求解的正确性设公式设公式L在逻辑上遵照公式集在逻辑上遵照公式集S，那么按照定义满足，那么按照定义满足S的每个解释也满足的每个解释也满足L。决不会有满足。决不会有满足S的解释可的解释可以满足以满足L的，所以不存在可以

19、满足并集的，所以不存在可以满足并集SL的解释。假设一个公式集不能被任一解释所的解释。假设一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，假设满足，那么这个公式是不可满足的。因此，假设L在逻辑上遵照在逻辑上遵照S，那么，那么SL是不可满足是不可满足的。可以证明，假设消解反演反复运用到不可满的。可以证明，假设消解反演反复运用到不可满足的子句集，那么最终将要产生空子句足的子句集，那么最终将要产生空子句NIL。因。因此，假设此，假设L在逻辑上遵照在逻辑上遵照S，那么由并集，那么由并集SL消解得到的子句，最后将产生空子句；反之，消解得到的子句，最后将产生空子句；反之，可以证明，假设从可以

20、证明，假设从SL的子句消解得到空的子句消解得到空子句，那么子句，那么L在逻辑上遵照在逻辑上遵照S。(3) 反演求解的举例反演求解的举例 下面举个例子来阐明消解反演过程：下面举个例子来阐明消解反演过程：前提：每个储蓄钱的人都获得利息。前提：每个储蓄钱的人都获得利息。结论：假设没有利息，那么就没有人去储蓄钱。结论：假设没有利息，那么就没有人去储蓄钱。证明：令证明：令S(x,y)表示表示x储蓄储蓄y M(x)表示表示x是钱是钱 I(x)表示表示x是利息是利息 E(x，y)表示表示x获得获得y于是上述命题写成以下方式：于是上述命题写成以下方式： 结论结论:用化为子句集的九步法，可把前提和结论化用化为子

21、句集的九步法，可把前提和结论化为以下的子句集：为以下的子句集： S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(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

22、= S(x,y)M(y)I(f(x),S(x,y)M(y) E(x,f(x),I(z), S(a,b), M(b) 运用消解原理，力图推导出一个表示矛盾运用消解原理，力图推导出一个表示矛盾的空子句的空子句NIL。该消解反演可以表示为一。该消解反演可以表示为一棵反演树，如以下图棵反演树，如以下图4.1所示，其根节点为所示，其根节点为NIL。因此，储蓄问题的结论获得证明。因此，储蓄问题的结论获得证明。图图 4.1 储蓄问题反演树储蓄问题反演树(4) 反演求解过程反演求解过程 从反演求解的举例中可以看出，用反演树求取从反演求解的举例中可以看出，用反演树求取对某个问题的答案，其过程如下：对某个问题的答

23、案，其过程如下： (a) 把由目的公式的否认产生的每个子句添加到把由目的公式的否认产生的每个子句添加到目的公式否认之否认的子句中去。目的公式否认之否认的子句中去。 (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) 其子句方式为

28、其子句方式为:AT(FIDO,x) 对本例运用消解反演求解过程，我们有：对本例运用消解反演求解过程，我们有：(1) 目目的公式否认的子句方式为的公式否认的子句方式为 :AT(FIDO,x) 把它添把它添加至目的公式的否认之否认的子句中去，得重言加至目的公式的否认之否认的子句中去，得重言式式 AT(FIDO,x)AT(FIDO,x) (2) 用图用图4.3的反的反演树进展消解，并在根部得到子句演树进展消解，并在根部得到子句:AT (FIDO，SCHOOL) (3) 从根部求得答案从根部求得答案AT(FIDO，SCHOOL)，用此子句作为回答语句。因此，子，用此子句作为回答语句。因此，子句句 AT

29、 (FIDO，SCHOOL)就是这个问题的适宜答就是这个问题的适宜答案，见图案，见图4.3。图图 4.2 菲多在哪里菲多在哪里例题的反演树例题的反演树图图 4.3 从消解求取答案例题的反演树从消解求取答案例题的反演树3.5 规那么演绎系统规那么演绎系统 规那么演绎系统规那么演绎系统 规那么正向演绎系统规那么正向演绎系统 规那么逆向演绎系统规那么逆向演绎系统 规那么双向演绎系统规那么双向演绎系统 对于许多公式来说，子句形是一种低效率对于许多公式来说，子句形是一种低效率的表达式，由于一些重要信息能够在求取的表达式，由于一些重要信息能够在求取子句形过程中丧失。本章将研讨采用易于子句形过程中丧失。本章

30、将研讨采用易于表达的表达的if-then(假设假设-那么那么)规那么来求解问规那么来求解问题题 基于规那么的问题求解系统运用下述规那基于规那么的问题求解系统运用下述规那么么: 在一切基于规那么系统中，每个在一切基于规那么系统中，每个if能够与某断言能够与某断言(assertion)集中的一个或多个断言匹配。有时把集中的一个或多个断言匹配。有时把该断言集称为任务内存。在许多基于规那么系统该断言集称为任务内存。在许多基于规那么系统中，中，then部分用于规定放入任务内存的新断言。部分用于规定放入任务内存的新断言。这种基于规那么的系统叫做规那么演绎系统这种基于规那么的系统叫做规那么演绎系统(rule

31、 based deduction system)。在这种系统中，通常称。在这种系统中，通常称每个每个if部分为前项部分为前项(antecedent)，称每个，称每个then部分部分为后项为后项(consequent)。 有时，有时，then部分用于规定动作；这时，称这种基部分用于规定动作；这时，称这种基于规那么的系统为反响式系统于规那么的系统为反响式系统(reaction system)或或产生式系统产生式系统(production system)。产生式系统将。产生式系统将在后续篇章中予以引见，本节讨论规那么演绎系在后续篇章中予以引见，本节讨论规那么演绎系统。统。 3.5.1 规那么正向演绎

32、系统规那么正向演绎系统 基于规那么的演绎系统和产生式系统，均有两种基于规那么的演绎系统和产生式系统，均有两种推理方式：推理方式： 正向推理正向推理(forward chanining)和逆向推理和逆向推理(backward chaining)。正向推理：从正向推理：从if部分向部分向then部分推理的过程，它部分推理的过程，它是从现实或情况向目的或动作进展操作的。是从现实或情况向目的或动作进展操作的。 逆向推理：从逆向推理：从then部分向部分向if部分推理的过程，它部分推理的过程，它是从目的或动作向现实或情况进展操作的。是从目的或动作向现实或情况进展操作的。 1.现实表达式的与或形变换现实表

33、达式的与或形变换 在基于规那么的正向演绎系统中，我们把现实表在基于规那么的正向演绎系统中，我们把现实表示为非蕴涵方式的与或形，作为系统的总数据库。示为非蕴涵方式的与或形，作为系统的总数据库。我们不想把这些现实化为子句形，而是把它们表我们不想把这些现实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵方式。要把一个公式化为与或形，或形的非蕴涵方式。要把一个公式化为与或形，可采用以下步骤：可采用以下步骤：(1) 利用利用(W1W2)和和(W1W2)的等价关系，的等价关系，消去符号消去符号(假设存在该符号的话假设存在该符号的话)。

34、实践上，在。实践上，在现实中间很少有符号现实中间很少有符号出现，由于可把蕴涵式表出现，由于可把蕴涵式表示为规那么。示为规那么。(2) 用狄用狄摩根摩根(De Morgan)定律把否认符号移定律把否认符号移进括号内，直到每个否认符号的辖域最多只含有进括号内，直到每个否认符号的辖域最多只含有一个谓词为止。一个谓词为止。 (3) 对所得到的表达式进展对所得到的表达式进展Skolem化和前束化。化和前束化。(4) 对全称量词辖域内的变量进展改名和变量规范对全称量词辖域内的变量进展改名和变量规范化，而存在量词量化变量用化，而存在量词量化变量用Skolem函数替代。函数替代。(5) 删去全称量词，而任何余

35、下的变量都被以为具删去全称量词，而任何余下的变量都被以为具有全称量化作用。有全称量化作用。 举例如下：举例如下： 例如，我们有现实表达式例如，我们有现实表达式( 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)中

36、的变量中的变量v却不可更名，却不可更名，由于后者也出如今析取式由于后者也出如今析取式S(A,v)中。与或形表中。与或形表达式是由符号达式是由符号和和衔接的一些文字的子表达式衔接的一些文字的子表达式组成的。呈与或形的表达式并不是子句形，而是组成的。呈与或形的表达式并不是子句形，而是接近于原始表达式方式，特别是它的子表达式不接近于原始表达式方式，特别是它的子表达式不是复合产生的。是复合产生的。 2.现实表达式的与或图表示现实表达式的与或图表示与或形的现实表达式可用与或图来表示。如图与或形的现实表达式可用与或图来表示。如图4.4的的与或树表示出上述例子的与或形现实表达。与或树表示出上述例子的与或形现

37、实表达。图图4.4中，每个节点表示该现实表达式的一个子表达中，每个节点表示该现实表达式的一个子表达式。某个现实表达式式。某个现实表达式(E1Ek)的析取关系子的析取关系子表达式表达式E1，Ek是用后继节点表示的，并由是用后继节点表示的，并由一个一个k线衔接符把它们衔接到父辈节点上。某个线衔接符把它们衔接到父辈节点上。某个现实表达式现实表达式(E1En)的每个合取子表达式的每个合取子表达式E1，En是由单一的后继节点表示的，并由是由单一的后继节点表示的，并由一个单线衔接符接到父辈接点。在现实表达式中，一个单线衔接符接到父辈接点。在现实表达式中，我们用我们用k线衔接符线衔接符(一个合取记号一个合取

38、记号)来分解析取式，来分解析取式，很能够会令人感到不测。在后面的讨论中，我们很能够会令人感到不测。在后面的讨论中，我们将会了解到采用这种商定的缘由。将会了解到采用这种商定的缘由。图图 4.4 一个现实表达式的与或树表示一个现实表达式的与或树表示 表示某个现实表达式的与或图的叶节点均由表达表示某个现实表达式的与或图的叶节点均由表达式中的文字来标志。图中标志有整个现实表达式式中的文字来标志。图中标志有整个现实表达式的节点，称为根节点，它在图中没有祖先。的节点，称为根节点，它在图中没有祖先。公式的与或图表示有个有趣的性质，即由变公式的与或图表示有个有趣的性质，即由变换该公式得到的子句集可作为此与或图

39、的解图的换该公式得到的子句集可作为此与或图的解图的集合集合(终止于叶节点终止于叶节点)读出；也就是说，所得到的读出；也就是说，所得到的每个子句是作为解图的各个叶节点上文字的析取。每个子句是作为解图的各个叶节点上文字的析取。这样，由表达式这样，由表达式 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解图之一的叶节点上文字解图之一的叶节点上文字的析取。所以，我们可把与或图看做是对子句集的析取。所以，我们可把与或图看做是对子句集的简约表示。不过，实践上表达式的与或图表示的简约表示。

40、不过，实践上表达式的与或图表示此子句集表示的通用性稍差，由于没有复合出共此子句集表示的通用性稍差，由于没有复合出共同的子表达式会妨碍在子句形中能够做到的某些同的子表达式会妨碍在子句形中能够做到的某些变量的更名。例如，上面的最后一个子句，其变变量的更名。例如，上面的最后一个子句，其变量量v可全部改为可全部改为u，但无法在与或图中加以表示，但无法在与或图中加以表示，因此失去了通用性，并且能够带来一些困难。因此失去了通用性，并且能够带来一些困难。 我们普通把现实表达式的与或图表示倒过来画，我们普通把现实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。即把根节点画在最下面，而把

41、其后继节点往上画。在本章的第二节，我们将要讨论到目的公式的与在本章的第二节，我们将要讨论到目的公式的与或图表示，它是按通常方式画出的，即目的在上或图表示，它是按通常方式画出的，即目的在上面。面。 3.与或图的与或图的F规那么变换规那么变换这些规那么是建立在某个问题辖域中普通陈说性知这些规那么是建立在某个问题辖域中普通陈说性知识的蕴涵公式根底上的。我们把允许用作规那么识的蕴涵公式根底上的。我们把允许用作规那么的公式类型限制为以下方式：的公式类型限制为以下方式：L W 式中：式中：L是单文字；是单文字；W为与或形的独一公式。我们为与或形的独一公式。我们也假设出如今蕴涵式中的任何变量都有全称量化也假

42、设出如今蕴涵式中的任何变量都有全称量化作用于整个蕴涵式。这些现实和规那么中的一些作用于整个蕴涵式。这些现实和规那么中的一些变量被分别规范化，使得没有一个变量出如今一变量被分别规范化，使得没有一个变量出如今一个以上的规那么中，而且使规那么变量不同于现个以上的规那么中，而且使规那么变量不同于现实变量。单文字前项的任何蕴涵式，不论其量化实变量。单文字前项的任何蕴涵式，不论其量化情况如何都可以化为某种量化辖域为整个蕴涵式情况如何都可以化为某种量化辖域为整个蕴涵式的方式。这个变换过程首先把这些变量的量词部的方式。这个变换过程首先把这些变量的量词部分地互换到前项，然后再把全部存在量词分地互换到前项，然后再

43、把全部存在量词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) 把否认符号移进第一个析把否认符号移进第一个析 取式内，互换变量取式内，互换变量的量词的量词 (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(

44、x,y)Q(x,u)(5) 恢复蕴涵式恢复蕴涵式 P(x,y,f(x,y) Q(x,u) 以下用一个自在变量的命题演算情况来阐明如何以下用一个自在变量的命题演算情况来阐明如何把这类规那么运用于与或图。把这类规那么运用于与或图。 把方式为把方式为L W的规那么运用到任一个具有叶节的规那么运用到任一个具有叶节点点n并由文字并由文字L标志的与或图上，可以得到一个新标志的与或图上，可以得到一个新的与或图。在新的图上，节点的与或图。在新的图上，节点n由一个单线衔接由一个单线衔接符接到后继节点符接到后继节点(也由也由L标志标志)，它是表示为，它是表示为W的一的一个与或图构造的根节点。作为例子，思索把规那个

45、与或图构造的根节点。作为例子，思索把规那么么 S (XY)Z运用到图运用到图4.5所示的与或图中所示的与或图中标有标有S的叶节点上。所得到的新与或图构造表示的叶节点上。所得到的新与或图构造表示于图于图4.6，图中标志，图中标志S的两个节点由一条叫做匹配的两个节点由一条叫做匹配弧的弧线衔接起来。弧的弧线衔接起来。图图 4.5 不含变量的与或图不含变量的与或图 4.6 运用一条运用一条 规那么得到的与或规那么得到的与或图图 在运用某条规那么之前，一个与或图在运用某条规那么之前，一个与或图(如图如图4.5)表表示一个详细的现实表达式。其中，在叶节点终了示一个详细的现实表达式。其中，在叶节点终了的一组

46、解图表示该现实表达式的子句形。我们希的一组解图表示该现实表达式的子句形。我们希望在运用规那么之后得到的图，既能表示原始现望在运用规那么之后得到的图，既能表示原始现实，又能表示从原始现实和该规那么推出的现实实，又能表示从原始现实和该规那么推出的现实表达式。表达式。 假设我们有一条规那么假设我们有一条规那么LW，根据此规那么及现，根据此规那么及现实表达式实表达式F(L)，可以推出表达式，可以推出表达式F(W)。F(W)是用是用W替代替代F中的一切中的一切L而得到的。当用规那么而得到的。当用规那么L W来变换以上述方式描画的来变换以上述方式描画的F(L)的与或图表示时，的与或图表示时，我们就产生一个

47、含有我们就产生一个含有F(W)表示的新图；也就是说，表示的新图；也就是说，它是以叶节点终止的解图集以它是以叶节点终止的解图集以F(W)子句方式代表子句方式代表该子句集。这个子句集包括在该子句集。这个子句集包括在F(L)的子句形和的子句形和LW的子句形间对的子句形间对L进展一切能够的消解而得到的整集。进展一切能够的消解而得到的整集。 再讨论图再讨论图4.6的情况。规那么的情况。规那么S (XY)Z的的子句形是：子句形是： SXZ,SYZ (PQ)RS(TU)的子句形解图集为的子句形解图集为: PQS, RS, PQTU, RTU运用两个规那么子句中任一个对上述子句形运用两个规那么子句中任一个对上

48、述子句形中的中的S进展消解：进展消解： 于是我们得到于是我们得到4个子句对个子句对S进展进展消解的消解式的完备集为：消解的消解式的完备集为： XZPQ ,YZPQ ,RXZ ,RYZ 这些消解式全部包含在图这些消解式全部包含在图4.4的解图所表示的子句的解图所表示的子句之中。之中。 从上述讨论我们可以得出结论：运用一条规那么从上述讨论我们可以得出结论：运用一条规那么到与或图的过程，以极其经济的方式到达了用其到与或图的过程，以极其经济的方式到达了用其它方法要进展多次消解才干到达的目的。它方法要进展多次消解才干到达的目的。 我们要使运用一条规那么得到的与或图继续表示我们要使运用一条规那么得到的与或

49、图继续表示现实表达式和推得的表达式，这可利用匹配弧两现实表达式和推得的表达式，这可利用匹配弧两侧有一样标志的节点来实现。对一个节点运用一侧有一样标志的节点来实现。对一个节点运用一条规那么之后，此节点就不再是该图的叶节点。条规那么之后，此节点就不再是该图的叶节点。不过，它依然由单一文字标志而且可以继续具有不过，它依然由单一文字标志而且可以继续具有一些运用于它的规那么。我们把图中标有单文字一些运用于它的规那么。我们把图中标有单文字的任一节点都称为文字节点，由一个与或图表示的任一节点都称为文字节点，由一个与或图表示的子句集就是对应于该图中以文字节点终止的解的子句集就是对应于该图中以文字节点终止的解图

50、集。图集。 4.作为终止条件的目的公式作为终止条件的目的公式运用运用F规那么的目的在于从某个现实公式和规那么的目的在于从某个现实公式和某个规那么集出发来证明某个目的公式。在正向某个规那么集出发来证明某个目的公式。在正向推理系统中，这种目的表达式只限于可证明的表推理系统中，这种目的表达式只限于可证明的表达式，尤其是可证明的文字析取形的目的公式表达式，尤其是可证明的文字析取形的目的公式表达式。我们用文字集表示此目的公式，并设该集达式。我们用文字集表示此目的公式，并设该集各元都为析取关系。各元都为析取关系。(在以后各节所要讨论的逆向在以后各节所要讨论的逆向系统和双向系统，都不对目的表达式作此限制。系

51、统和双向系统，都不对目的表达式作此限制。)目的文字和规那么可用来对与或图添加后继节点，目的文字和规那么可用来对与或图添加后继节点，当一个目的文字与该图中文字节点当一个目的文字与该图中文字节点n上的一个文上的一个文字相匹配时，我们就对该图添加这个节点字相匹配时，我们就对该图添加这个节点n的新的新后裔，并标志为匹配的目的文字。这个后裔叫做后裔，并标志为匹配的目的文字。这个后裔叫做目的节点，目的节点都用匹配弧分别接到它们的目的节点，目的节点都用匹配弧分别接到它们的父辈节点上。当产生式系统产生一个与或图，并父辈节点上。当产生式系统产生一个与或图，并包含有终止在目的节点上的一个解图时，系统便包含有终止在

52、目的节点上的一个解图时，系统便胜利地终了。此时，该系统实践上已推出一个等胜利地终了。此时，该系统实践上已推出一个等价于目的子句的一部分的子句。价于目的子句的一部分的子句。 图图4.7给出一个满足以目的公式给出一个满足以目的公式(CG)为根底的为根底的终止条件的与或图，可把它解释为用一个终止条件的与或图，可把它解释为用一个“以现以现实来推理的战略对目的表达式实来推理的战略对目的表达式(CG)的一个证的一个证明。最初的现实表达式为明。最初的现实表达式为(AB)。由于不知道。由于不知道A或或B哪个为真，因此我们可以试着首先假定哪个为真，因此我们可以试着首先假定A为为真，然后再假定真，然后再假定B为真

53、，分别地进展证明。假设为真，分别地进展证明。假设两个证明都胜利，那么我们就得到根据析取式两个证明都胜利，那么我们就得到根据析取式(AB)的一个证明。而的一个证明。而A或或B究竟哪个为真都无究竟哪个为真都无关紧要。图关紧要。图4.7中标有中标有(AB)的节点，其两个后裔的节点，其两个后裔由一个由一个2线衔接符来衔接。因此这两个后裔都必线衔接符来衔接。因此这两个后裔都必需出如今最后解图中，假设对节点需出如今最后解图中，假设对节点n的一个解图的一个解图经过经过k线衔接符包含线衔接符包含n的任一后裔，那么此解图必的任一后裔，那么此解图必需包含经过这个需包含经过这个k线衔接符的一切线衔接符的一切k个后裔

54、。个后裔。 图图 4.7 满足中终止条件的与或图满足中终止条件的与或图 图图4.7的例子证明过程如下：的例子证明过程如下： 现实：现实：AB 规那么：规那么：ACD，BEG 目的目的: CG 把规那么化为子句形，得子句集：把规那么化为子句形，得子句集： AC，AD BE，BG 目的的否以为目的的否以为:(CG) 其子句形为其子句形为:C，G 用消解反演来证明目的公式，如图用消解反演来证明目的公式，如图4.8所示。所示。 图图 4.8 用消解反演求证目的公式的图解用消解反演求证目的公式的图解 从图从图4.8我们推得一个空子句我们推得一个空子句NIL，从而使目的公式，从而使目的公式(CG)得到证明

55、。得到证明。 我们得到的结论是：当正向演绎系统产生一个含有以我们得到的结论是：当正向演绎系统产生一个含有以目的节点作为终止的解图时，此系统就胜利地终止。目的节点作为终止的解图时，此系统就胜利地终止。 对于表达式含有变量的正向产生式系统，我们思索把对于表达式含有变量的正向产生式系统，我们思索把一条一条(L W)方式的规那么运用到与或图的过程，其中方式的规那么运用到与或图的过程，其中L是文字，是文字，W是与或形的一个公式，而且一切表达式都是与或形的一个公式，而且一切表达式都可以包含变量。假设这个与或图含有的某个文字节点可以包含变量。假设这个与或图含有的某个文字节点L同同L合一，那么这条规那么就是可

56、运用的。设其最普合一，那么这条规那么就是可运用的。设其最普通合一者为通合一者为u，那么这条规那么的运用可以扩展这个图。，那么这条规那么的运用可以扩展这个图。为此，建立一个有向的匹配弧，从与或图中标有为此，建立一个有向的匹配弧，从与或图中标有L的的节点出发到达一个新的标有节点出发到达一个新的标有L的后继节点。这个后继节的后继节点。这个后继节点是点是Wu的与或图表示的根节点，我们用的与或图表示的根节点，我们用mgu，或者简，或者简写为写为u来标志这段匹配弧。来标志这段匹配弧。3.5.2 规那么逆向演绎系统规那么逆向演绎系统基于规那么的逆向演绎系统，其操作过程与正向基于规那么的逆向演绎系统，其操作过

57、程与正向演绎系统相反，即为从目的到现实的操作过程，演绎系统相反，即为从目的到现实的操作过程，从从then到到if的推理过程。的推理过程。1.目的表达式的与或方式目的表达式的与或方式逆向演绎系统可以处置恣意方式的目的表达式。首逆向演绎系统可以处置恣意方式的目的表达式。首先，采用与变换现实表达式同样的过程，把目的先，采用与变换现实表达式同样的过程，把目的公式化成与或形，即消去蕴涵符号，把否认符号公式化成与或形，即消去蕴涵符号，把否认符号移进括号内，对全称量词移进括号内，对全称量词Skolem化并删去存在量化并删去存在量词。留在目的表达式与或形中的变量假定都已存词。留在目的表达式与或形中的变量假定都

58、已存在量词量化。在量词量化。 举例如下：举例如下：目的表达式目的表达式( y)( x)P(x)(x,y)P(x)S(y)被化成与或形：被化成与或形：P(f(y)Q(f(y),y)P(f(y)S(y)式中，式中，f(y)为一为一Skolem函数。函数。 对目的的主要析取式中的变量分别规范化可得对目的的主要析取式中的变量分别规范化可得: P(f(z)Q(f(y),y)P(f(y)S(y) 应留意不能对析取的子表达式内的变量应留意不能对析取的子表达式内的变量y改名而改名而使每个析取式具有不同的变量。使每个析取式具有不同的变量。 与或形的目的公式也可以表示为与或图。不过，与或形的目的公式也可以表示为与

59、或图。不过，与现实表达式的与或图不同的是，对于目的表达与现实表达式的与或图不同的是，对于目的表达式，与或图中的式，与或图中的k线衔接符用来分开合取关系的线衔接符用来分开合取关系的子表达式。上例所用的目的公式的与或图如图子表达式。上例所用的目的公式的与或图如图4.9所示。在目的公式的与或图中，我们把根节点的所示。在目的公式的与或图中，我们把根节点的任一后裔叫做子目的节点，而标在这些后裔节点任一后裔叫做子目的节点，而标在这些后裔节点中的表达式叫做子目的。中的表达式叫做子目的。 图图 4.9 一个目的公式的与或图表示一个目的公式的与或图表示 这个目的公式的子句形表示中的子句集可从终止在叶节点上的这个

60、目的公式的子句形表示中的子句集可从终止在叶节点上的解图集读出：解图集读出：P(f(z),Q(f(y),y)R(f(y),Q(f(y),y)S(y)可见目的子句是文字的合取，而这些子句的析取是目的公式的可见目的子句是文字的合取，而这些子句的析取是目的公式的子句形。子句形。 2.与或图的与或图的B规那么变换规那么变换如今让我们运用如今让我们运用B规那么即逆向推理规那么来变换规那么即逆向推理规那么来变换逆向演绎系统的与或图构造，这个逆向演绎系统的与或图构造，这个B规那么是建规那么是建立在确定的蕴涵式根底上的，正如正向系统的立在确定的蕴涵式根底上的，正如正向系统的F规那么一样。不过，我们如今把这些规那