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