《如果采用上一章讨论过的搜索方法那么很难甚至无法使问》由会员分享，可在线阅读，更多相关《如果采用上一章讨论过的搜索方法那么很难甚至无法使问（129页珍藏版）》请在金锄头文库上搜索。
1、1,讨论了一些简单搜索的基本原理，包括某些推理规则以及置换合一等概念。但对于许多比较复杂的系统和问题，如果采用上一章讨论过的搜索方法，那么很难甚至无法使问题获得解决的。需要应用一些更先进的推理技术和系统求解这种比较复杂的问题。 本章讨论消解原理，规则演绎系统、产生式系统、不确定性推理和非单调推理等， 而对于那些发展特别快的高级求解技术，如专家系统、机器学习和规划系统等，则将在后续章节讨论它们。,2,内容提要,3.4 消解原理 3.5 规则演绎系统 3.6 产生式系统 3.7 系统组织技术 3.8 不确定性推理 3.9 非单调推理,3,3.4 消解原理,化为子句集 消解推理规则 含有变量的消解式
2、 消解反演求解过程,4,第二章中讨论过谓词公式，某些推理规则以及置换合一等概念。在这个基础上，能够进一步研究消解原理(resolution principle)。有些专家把它叫做归结原理。 消解是一种可用于一定的子句公式的重要推理规则。一个子句定义为由文字的析取组成的公式(一个原子公式和原子公式的否定都叫文字)。当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理E1E2和另一公理E2E3，那么E1E3在逻辑上成立。这就是消解，而称E1E3为E1E2和E2E3的消解式(resolvent)。,5,3.4.1 子句集的求取,在说明消解过程之前,我们首先说明任一
3、谓词演算公式可以化成一个子句集。其变换过程由下列九个步骤组成： (1)消去蕴涵符号 只应用和符号，以AB替换A=B。 (2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。例如: 以AB代替(AB)以AB代替(AB)以(x)A代替(x)A以(x)A代替(x)A以A代替(A),6,(3)对变量标准化 在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量)，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化，意味着对哑元改名以保证每个量词有其自己唯一的哑元。,7,(4)消去存在量词 Skolem函数: 在公式(
4、y)(x)P(x,y)中，存在量词是在全称量词的辖域内，我们允许所存在的x可能依赖于y值。令这种依赖关系明显地由函数g(y)所定义，它把每个y值映射到存在的那个x。这种函数叫做Skolem函数。 如果用Skolem函数代替存在的x,我们就可以消去全部存在量词，并写成： 从一个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量，而这个Skolem函数的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内。Skolem函数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数符号。,8,如果要消去的存在量词不在
5、任何一个全称量词的辖域内，那么我们就用不含变量的Skolem函数即常量。例如，(x)P(x)化为P(A)，其中常量符号A用来表示我们知道的存在实体。A必须是个新的常量符号，它未曾在公式中其它地方使用过。 例如：(z)(y)(x)P(x,y,z)被(y)P(g(y),y,A)代替，其中g(y)为一Skolem函数。,9,(5)化为前束形 到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即 前束形= (前缀)
6、 (母式) 全称量词串 无量词公式,10,(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。我们可以反复应用分配律。把任一母式化成合取范式。例如，我们把 ABC化为ABAC,11,(7)消去全称量词 到了这一步，所有余下的量词均被全称量词量化了。同时，全称量词的次序也不重要了。因此，我们可以消去前缀，即消去明显出现的全称量词。 (8)消去连词符号 用(AB), (AC)代替(AB)(AC)，以消去明显的符号。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。,
7、12,(9)更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。例如，对于子集P(x)P(y)Pf(x,y),P(x)Qx,g(x),P(x)Pg(x)，在更改变量名后，可以得到子句集： P(x1)P(y)Pf(x1,y), P(x2)Qx2,g(x2), P(x3)Pg(x3) ,13,3.4.2 消解推理规则,令L1为任一原子公式，L2为另一原子公式； L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2如果L1和L2具有最一般合一者，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。它是由取这两个子句的析取，然后消去
8、互补对而得到的。 下面举出几个从父辈子句求消解式的例子:,14,15,16,上各例可见，消解可以合并几个运算为一简单的推理规则,17,4.4.3 含有变量的消解式,为了对含有变量的子句使用消解规则，我们必须找到一个置换，作用于父辈子句使其含有互补文字。令父辈子句由Li和Mi给出，而且假设这两个子句中的变量已经分离标准化。设li是Li的一个子集，mi是Mi的一个子集，使得集li和mi的并集存在一个最一般的合一者。消解两个子句Li和Mi，得到的新子句: Li-liMi-mi 就是这两个子句的消解式。,18,消解两个子句时，可能有一个以上的消解式，因为有多种选择li和mi的方法。不过，在任何情况下，
9、它们最多具有有限个消解式。作为例子，我们考虑两个子句: 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),19,可见这两个子句消解一共可得4个不同的消解式，其中3个是消解P得到的，而另一个是由消解Q得到的。 下面举几个对含有变量的子句使用消解的例子。,20,例3：,本节中所例举的对基子句和对含有变量的子句进行消解的例子，其父辈子句和消解式列
10、表示于表4.1。这些例子表示出消解推理的某些常用规则。,21,表 4.1 消解推理常用规则,22,3.4.4 消解反演求解过程,1 基本思想 把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去,把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决。这与数学中反证法的思想十分相似。,23,2 消解反演 (1) 反演求解的步骤 给出一个公式集S和自标公式L，通过反证或反演来求证目标公式L，其证明步骤如下： (a)否定L，得L； (b)把L添加到S中去； (c)把新产生的
11、集合L，S化成子句集； (d)应用消解原理，力图推导出一个表示矛盾的空子句NIL。,24,(2) 反演求解的正确性 设公式L在逻辑上遵循公式集S，那么按照定义满足S的每个解释也满足L。决不会有满足S的解释能够满足L的，所以不存在能够满足并集SL的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，如果L在逻辑上遵循S，那么SL是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句NIL。因此，如果L在逻辑上遵循S，那么由并集SL消解得到的子句，最后将产生空子句；反之，可以证明，如果从SL的子句消解得到空子句，那么L在逻辑上遵循S。,25,(
12、3) 反演求解的举例 下面举个例子来说明消解反演过程： 前提：每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱。 证明：令S(x,y)表示“x储蓄y“ M(x)表示“x是钱“ I(x)表示“x是利息“ E(x，y)表示“x获得y“ 于是上述命题写成下列形式： 结论:,26,用化为子句集的九步法，可把前提和结论化为下列的子句集： 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),27,以下按上述的四个步骤来对问题进行反演求解： 否定L，即有 L I(z),S(a,b),M
13、(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) ,28,应用消解原理，力图推导出一个表示矛盾的空子句NIL。该消解反演可以表示为一棵反演树，如下图4.1所示，其根节点为NIL。因此，储蓄问题的结论获得证明。,图 4.1 储蓄问题反演树,29,(4) 反演求解过程 从反演求解的举例中可以看出，用反演树求取对某个问题的答案，其过程如下： (a) 把由
14、目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。 (b) 按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。 (c) 用根部的子句作为一个回答语句。,30,答案求取涉及到把一棵根部有NIL的反演树变换为在根部带有可用作答案的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部的语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。下面讨论一个简单的问题，作为例子： “如果无论约翰(John)到哪里去，菲多(Fido)也就去那里，那么如果
15、约翰在学校里，菲多在哪里呢?”,31,很清楚，这个问题说明了两个事实，然后提出一个问题，而问题的答案大概可从这两个事实推导出。这两个事实可以解释为下列公式集S： ( x)AT(JOHN,X)=AT(FIDO,X)和T(JOHN,SCHOOL) 如果我们首先证明公式( x)AT(FIDO,X)在逻辑上遵循S，然后寻求一个存在x的例，那么就能解决“菲多在哪里”的问题。关键想法是把问题化为一个包含某个存在量词的目标公式，使得此存在量词量化变量表示对该问题的一个解答。如果问题可以从给出的事实得到答案，那么按这种方法建立的目标函数在逻辑上遵循S。在得到一个证明之后，我们就试图求取存在量词量化变量的一个例，作为一个回答。对于上述例题能够容易地证明( x)AT(FIDO,X) 遵循S。我们也可以说明，用一种比较简单的方法来求取合适的答案。,32,消解反演可用一般方式得到，其办法是首先对被证明的公式加以否定，再把这个否定式附加到集S中去，化这个扩充集的所有成员为子句形，然后用消解证明这个子句集是不可满足的。图4.2表示出上例的反演树。从S中的公式得到
