[人工智能]人工智能及其应用——第三章学习笔记（下）

3.4 消解原理

消解原理又称为归结原理

消解是一种可用于一定的子句公式的重要推理规则

子句定义为由文字的析取组成的公式（一个原子公式和原子公式的否定都是文字），当消解可用时，消解过程被应用于母体子句对，以产生一个导出子句

3.4.1 子句集的求取

任一谓词演算公式可以化成一个子句集。变换过程如下：

1. 消去蕴涵符号
   只应用$\vee$和$～$，以$～A\vee B$替换$A\to B$
2. 减少否定符号的辖域
   每个否定符号最多只用到一个谓词符号上，并反复应用狄$?$摩根定律
3. 对变量标准化
   在任一量词辖域内，受该量词约束的变量称为一哑元（虚构变量），它可以在该辖域内处处统一的被另一个没有出现过的任意变量所代替，而不改变公的真值。
   合式公式中变量的标准化意味着对哑元改名以保证每个量词都有其唯一的哑元
4. 消去存在量词
   从一个公式消去一个存在量词的一般规则是以一个$Skolem$函数¹代替每个出现的存在量词的量化变量，而这个$Skolem$函数的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内
   如果要消去的存在量词不在任何一个全称量词的辖域内，那么就用不含变量的$Skolem$函数即常量
   $Skolem$函数所使用的函数符号必须是新的
5. 化为前束型
   把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分，所得公式称为前束型。前束型公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成
6. 把母式化为合取范式
   任何母式都可写成由一些谓词公式和谓词公式的否定的析取的有限集组成的合取，这种母式叫做合取范式
7. 消去全称量词
8. 消去连词符号$\wedge$
   用 { A , B } \left\{ A,B\right\} {A,B}代替$(A,B)$，以消去$\wedge$
9. 更换变量名称
   可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中

必须指出，一个句子内的文字可含有变量，但这些变量总是被理解为全称量词量化了变量。
如果一个表达式中的变量被不含变量的项所置换，则得到称为文字基例的结果
如果公式$X$在逻辑上遵循公式集$S$，那么$X$在逻辑上也遵循由$S$的公式变换成的子句集

3.4.2 消解推理规则

令$L_1$为任一原子公式，$L_2$为另一原子公式；$L_1$和$L_2$具有相同的谓词符号，但一般具有不同的变量。
已知两子句$L_1\vee \alpha$和$～L_2\vee \beta$，如果$L_1$和$L_2$具有最一般合一者$\sigma$²，那么通过消解可以从这两个父辈子句中推导出一个新子句$(\alpha \vee \beta )\sigma$。这个薪子句叫做消解式

• 假言推理
• 合并
• 重言式
• 空子句
• 链式（三段论）

3.4.3 含有变量的消解式

为了对含有变量的子句使用消解规则，必须找到一个置换，用作于父辈子句使其含有互补文字

3.4.4 消解反演求解过程

可以把要解决的问题作为一个要证明的命题。消解通过反演产生证明

消解反演：
给出一个公式集合$S$和目标公式$L$，通过反证或反演来求证目标公式$L$，其证明步骤如下：

1. 否定$L$，得$～L$
2. 把$～L$添加到$S$中
3. 把新产生的集合 { ～ L , S } \left\{\sim L,S \right\} {～L,S}化成子句集
4. 应用消解原理，推导出一个表示矛盾的空子句

反演求解过程：
用反演树求取对某个问题的答案

1. 把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中，形成重言式
2. 按照反演树，执行和以前相同的消解，直至在根部得到某个子句为止
3. 用根部的子句作为一个回答语句

答案求取涉及把一棵根部有$NIL$的反演树变换为在根部带有可用答案的某个语句的一棵证明树

3.5 规则演绎系统

对于许多比较复杂的系统和问题，如果采用前面讨论过的搜索推理方法，那么很难甚至无法使问题获得解决。需要应用一些更先进的推理技术和系统（如规则演绎系统、产生式系统等）
对于许多公式来说，子句形是一种低效率的表达式，因为一些重要信息可能在求取子句形过程中丢失

在规则演绎系统中，通常称每个$if$部分为前项，称每个$then$部分为后项

3.5.1 规则正向演绎系统

在基于规则的系统中，无论是规则演绎系统或规则产生式系统，均有两种推理方式，即正向推理和逆向推理

• 对于从$if$部分向$then$部分推理的过程，叫做正向推理
• 对于从$then$部分向$if$部分推理的过程，叫做逆向推理

逆向推理是从目标或动作向事实或状况进行操作的

事实表达式的与或形变换

在基于规则的正向演绎系统中，把事实表示为非蕴涵形式的与或形，作为系统的总数据库。不把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式

与或形——即子句集
呈与或形的表达式并不是子句形，而是接近于原始表达式形式，特别是它的子表达式不是复合产生的

事实表达式的与或图表示

与或形的事实表达式可用与或图来表示
表示某个事实表达式的与或图的叶节点均由表达式中的文字来标记。标记有整个事实表达式的节点，称为根节点。

公式的与或图表示有一个有趣的性质，即由变换该公式得到的子句集可作为此与或图的解图集合（终止于叶节点）读出，即所得到的每个子句是作为解图的各个叶节点上文字的析取

实际上表达式的与或图表示此子句集的通用性稍差，因为没有复合出共同的子表达式会妨碍在子句形中可能做到的某些变量的更名

一般把事实表达式的与或图表示倒过来画，即把根结点画在最下面，而把其后继节点往上画

与或图的$F$规则变换

这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式：
$$L\to W$$
式中，$L$是单文字；$W$为与或形的唯一公式

单文字前项的任何蕴涵式，不管其量化情况如何都可以化为某种量化辖域为整个蕴涵式的形式。这个变换过程首先把这些变量的量词局部地调换到前项，然后再把全部存在量词$Skolem$化

一般可以通过以下步骤变换：

1. 暂时消去蕴涵符号
2. 把否定符号移进第一个析取式内，调换变量的量词
3. 进行$Skolem$化
4. 把所有全称量词移至前面，然后消去
5. 恢复蕴涵式

把形式为$L\to W$的规则应用到任一个具有叶节点$n$并由文字$L$标记的与或图上，可以得到一个新的与或图。在新的图上，节点$n$由一个单线连接符接到后继节点（也由$L$标记），它是表示为$W$的一个与或图结构的根结点

在应用某条规则之前，一个与或图表示一个具体的事实表达式。其中，在叶节点结束的一组解图表示该事实表达式的子句形。希望在应用规则之后得到的图，既能表示原始事实，又能表示从原始事实和该规则退出的事实表达式

假设有一条规则$L\to W$，根据此规则及事实表达式$F(L)$可以推出$F(W)$。$F(W)$是用$W$代替$F$中的所有$L$得到的。当用规则$L\to W$来变换以上述方式描述的$F(L)$的与或图表示时，就产生一个含有$F(W)$表示的新图。也就是说，它的以叶节点终止的解图集以$F(W)$子句形式代表该子句集。这个子句集包括在$F(L)$的子句形和$L\to W$的子句形间对$L$进行所有可能的消解而得到的整集

要使应用一条规则得到的与或图继续表示事实表达式和推得的表达式，这可利用匹配弧两侧有相同标记的节点来实现。对一个节点应用一条规则之后，此节点就不再是该图的叶节点。不过，它仍然由单一文字标记而且可以继续具有一些应用于它的规则

把图中标有单文字的任一节点都称为文字节点，由一个与或图表示的子句集就是对应于该图中以文字节点终止的解图集

作为终止条件的目标公式

应用$F$规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。

当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止

3.5.2 规则逆向演绎系统

基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从$then$到$if$的推理过程

目标表达式的与或形式

逆向演绎系统能够处理任意形式的目标表达式

首先，采用与变换事实表达式同样的过程，把目标公式化成与或形，即消去蕴涵符号$\to$，把否定符号移进括号内，对全称量词$Skolem$化并删去存在量词

与或形的目标公式也可以表示为与或图。不过，与事实表达式的与或图不同的是，对于目标表达式，与或图中的$k$线连接符用来分开合取关系的子表达式

与或图的$B$规则变换

应用$B$规则即逆向推理规则来变换逆向演绎系统的与或图结构，这个$B$规则是建立在确定的蕴涵式基础上的，正如正向系统的$F$规则一样。

不过，现在把这些$B$规则限制为：
$$W\to L$$
形式的表达式。其中，$W$为任一与或形公式，$L$为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。其次，把$B$规则限制为这种形式的蕴涵式还可以简化匹配，使之不会引起重大的实际困难，此外，可以把像$W\to (L1\wedge L2)$这样的蕴涵式化为两个规则$W\to L1$和$W\to L2$

作为终止条件的事实节点的一致解图

逆向系统中的事实表达式均限制为文字合取形，它可以表示为一个文字集。当一个事实文字和标在该图文字节点上的文字相匹配时，就可把相应的后裔事实节点添加到该与或图中去

这个事实节点通过标有$mgu$的匹配弧与匹配的子目标文字节点连接起来

同一个事实文字可以重复使用（每次用不同变量），以建立多重事实节点

3.5.3 规则双向演绎系统

前两种系统的局限性：

• 正向演绎系统：能够处理任意形式的$if$表达式，但被限制在$then$表达式为由文字析取组成的一些表达式上
• 逆向演绎系统：能够处理任意形式的$then$表达式，但被限制在$if$表达式为文字合取组成的一些表达式上

希望能构成一个组合的系统，使它具有正向和逆向两系统的有点，以克服各自的缺点。这个系统就是双向（正向和逆向）组合演绎系统

• 双向组合系统是建立在两个系统相结合的基础上的
• 此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成
• 这些与或图最初用来表示给出的事实和目标的某些表达式集合，现在这些表达式的形式不受约束
• 这些与或图结构分别用正向系统的$F$规则和逆向系统的$B$规则来修正

尽管新系统在修正由两部分构成的数据库时实际上只沿一个方向进行，但仍然把这些规则分别称为$F$规则和$B$规则。继续限制$F$规则为单文字前项和$B$规则为单文字后项

组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。这些结构可由标有合一文字的节点上的匹配棱线来连接。用对应的$mgu$来标记匹配棱线

对于初始图，事实图和目标图间的匹配棱线必须在叶节点之间。当用$F$规则和$B$规则对图进行扩展之后，匹配就可以出现在任何文字节点上

在完成两个图间的所有可能匹配之后，仍然需要判定目标图中根节点上的表达式是否已经根据事实图中根结点上的表达式和规则得到了证明

一个简单的终止条件是判断与或图根结点是否为可解过程的直接归纳

定义：如果$(n,m)$中有一个为事实节点，另一个为目标节点，而且如果$n$和$m$都由可合一的文字所标记，或者$n$有个外向$k$线连接符接至一个后继节点集 { S i } \left\{S_i \right\} {Si?}使得对此集的每个元$CANCEL(S_i,m)$都成立，那么就称这两节点$n$和$m$互相$CANCEL$（即互相抵消）

当事实图的根结点和目标图的根结点互相$CANCEL$时，就得到一个候补解。
在事实和目标图内证明该目标根结点和事实根节点互相$CANCEL$的图结构叫做候补$CANCEL$图。
如果候补$CANCEL$图中所有匹配的$mgu$都是一致的，那么这个候补解就是一个实际解。

我们应用$F$规则和$B$规则来扩展与或搜索图，因此，置换关系到每条规则的应用。解图中的所有置换，包括在规则匹配中得到的$mgu$和匹配事实与目标文字间所得到的$mgu$都必须是一致的

3.6 产生式系统

产生式系统由波斯特$(Post)$于$1943$年提出的产生式规则而得名，人们用这种规则对符号串进行置换运算。

$1965$年美国的纽厄尔和西蒙利用这个原理建立了一个人类的认知模型。同时，斯坦福大学利用产生式系统结构设计出第一个专家系统$DENDRAL$

产生式系统用来描述若干个不同的以一个基本概念为基础的系统。 这个基本概念就是产生式规则或产生式条件和操作对的概念

在产生式系统中，论域的知识分为两部分：

1. 用事实表示静态知识，如事物、事件和它们之间的关系
2. 用产生式规则表示推理过程和行为

由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统

3.6.1 产生式系统的组成

产生式系统由三个部分组成：

• 总数据库（全局数据库或综合数据库）：用于存放求解过程中各种当前信息的数据结构
• 产生式规则：是一个规则库，用于存放求解问题有关的某个领域知识的规则集合及其交换规则
• 控制策略：为一推理机构，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，实现对问题的求解

控制策略的主要任务：

1. 按一定策略从规则库中选择与总数据库中的已知事实相匹配的规则
2. 当存在多条匹配成功的规则时，能够按照某种策略从中选出一条适合的规则去执行
3. 如果要执行规则的右部不是问题的目标，且为一个或多个结论时，则把这些结论加入到总数据库中；当其为一个或多个操作时，执行这些操作
4. 如果要执行规则的右部满足问题的结束条件时，则停止推理
5. 记住问题求解过程应用过的规则序列，以便求解结束时能够给出问题的解答路径

产生式系统的各部分关系如下图

产生式系统的控制策略随搜索方式的不同分为可撤回策略、回溯策略、图搜索策略等

产生式规则是一个以“如果满足这个条件，就应当采取某些操作”形式表示的语句，其基本形式为
$$IF前提THEN结论$$
产生式的$IF$称为条件、前项或产生式的左边，它说明应用这条规则必须满足的条件；$THEN$称为操作、结果、后项或产生式的右边。

在产生式系统的执行过程中，如果某条规则的条件满足了，那么就可以应用这条规则

需要注意：这里所说的产生式规则和谓词逻辑中所谈论的产生式规则，从形式上看都采用了$IF?THEN$的形式，但这里讨论的产生式更为通用。在谓词运算中，实质上是表示了蕴涵关系，要满足相应的真值表。这里所讨论的条件和操作部分除了可以用谓词逻辑表示外，还可以有其他多种表示形式，并不受相应的真值表的限制

总数据库有时也称为上下文、当前数据库或暂时存储器。总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。执行产生式规则的操作会引起总数据库的变化，这就使其他产生式规则的条件可能被满足

控制策略的作用是说明下一步应该选用什么规则。通常从选择规则到执行操作分为三步：

1. 匹配：把当前数据库与规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被满足，这就要在“冲突解决”步骤中来解决问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配
2. 冲突解决：当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。冲突的解决策略有：专一性排序、规则排序、数据排序、规模排序和就近排序等
3. 操作：执行规则的操作部分，经过操作以后，当前数据库将被修改。然后其他的规则有可能被使用

3.6.2 产生式系统的推理

产生式系统的问题求解过程即对解空间的搜索过程，也就是推理过程。按照搜索方向可分为正向推理、逆向推理和双向推理。

正向推理又称为事实（或数据）驱动推理、前项链接推理；逆向推理又称为目标驱动推理、逆向链接推理

正向推理

正向推理从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立

实现正向推理的一般策略是：

• 先提供一批事实（数据）带总数据库中
• 系统利用这些事实与规则的前提相匹配，出发匹配成功的规则，把其结论作为新的事实添加到总数据库中
• 继续上述过程，用更新过的总数据库的所有事实再与规则库中另一条规则匹配，用其结论再次修改总数据库的内容，直到没有可匹配的新规则，不再有新的事实加到总数据库中为止

逆向推理

逆向推理从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后注意验证这些假设

要实现逆向推理，其策略如下：

• 首先假设一个可能的目标，然后由产生式系统试图证明此假设目标是否在总数据库中
• 若在总数据库中，则该假设目标成立
• 若该假设为终叶节点，则询问用户
• 若不是，则再假定另一个目标，即寻找结论部分包含该假设的那些规则，把它们的前提作为新的假设，并力图证明其成立

这样反复进行推理，直到所有目标均获得证明或者所有路径都得到测试为止

从上面的讨论可知，正向推理和逆向推理各有其特点和适用场合

• 正向推理：算法简单、容易实现，允许用户一开始就把有关的事实数据放入数据库，在执行过程中系统能很快获得这些数据。主要特点是盲目搜索，可能会求解许多与总目标无关的子问题，推理效率较低
• 逆向推理：搜索目的性强，推理效率高，缺点是目标的选择具有盲目性，可能会求解许多假目标；当可能的结论数目很多时，推理效率不高；当规则的右部是执行某种动作而不是结论时，逆向推理不便使用

双向推理

双向推理又称为正反向混合推理，它综合了正向推理和逆向推理的长处，克服了两者的短处

双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配

产生式系统的种类很多。按设计方法可分为用于综合的产生式系统和用于分析的产生式系统

产生式系统可以正向推理，也可以逆向推理。至于哪一个更好一些，取决于推理的目标和搜索空间的形状

3.7 非单调推理

建立在谓词逻辑基础上的传统系统是单调的，这意味着，已知为真的命题数目将随时间而严格增加。那是由于新的命题可加入系统，新的定理可被证明，但这种加入和被证明绝不会导致前面已知为真或已被证明的命题变成无效。

这种系统具有以下优点：

1. 当加入一个新命题时，不必检查新命题与原有只是之间的不相容性
2. 对每一个已被证明了的命题，不必保留一个命题表。它的证明以该命题表中的命题为依据，因为不存在那些命题会被取消的危险

可是，这种单调系统不能很好的处理常常出现在现实问题领域中的3类情况，即不完全的信息、不断变化的情况以及求复杂问题过程中生成的假设

3.7.1 缺省推理

当缺乏信息时，只要不出现相反的证据，就可以做一些有益的猜想。构造这种猜想称为缺省推理

一个既精确又可算的缺省推理的描述，必涉及结论$Y$且缺少某一信息$X$。所以缺省的定义为：

• 缺省推理的的定义1： 如果$X$不知道，那么得到结论$Y$
• 缺省推理的定义2： 如果$X$不能被证明，那么得到结论$Y$
• 缺省推理的定义3： 如果$X$不能在某个给定的时间内被证明，那么得到结论$Y$

值得注意的是，定义推出结论$Y$的推理过程依赖于逻辑领域以外的某些事件，在规定事件内可作多少计算，以及在寻找待求的证明中计算是否有效

3.7.2 真值维持系统

真值维持系统$(TMS)$是一个已经实现了的非单调推理系统，它用以协助其他推理程序维持系统的正确性，所以它的作用不是生成新的推理，而是在其他程序所产生的命题之间保持相容性

一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容

• 在$TMS$中，每一个命题或规则均称为节点，且对任一节点，以下两种状态必居其一：
  • $IN相信为真$
  • $OUT不相信为真，或无理由相信为真，或当前没有可相信的理由$

每个节点附有一张证实表，表中每一项表示一种确定节点有效性的方法

• $IN$节点是指那些至少有一个在当前说来是有效证实的节点
• $OUT$节点则指那些当前无任何有效证实的节点

在非单调推理系统中，所产生的节点最初总是对应一个假定为真的命题

在系统中，有两种方式可用来证实一个节点的有效性可依赖于其他节点的有效性：

1. 支持表：$(SL(IN?节点)(OUT?节点))$
2. 条件证明：$(CP(结论)(IN?假设)(OUT?假设)$

支持表

支持表最通用。如果在$IN$节点表中提到的节点当前都是$IN$，且在$OUT$节点表中提到的节点当前都是$OUT$，那么它们是有效的。

$TMS$的推理与直接的谓词逻辑系统类似，除了它能够撤销前提并对数据库的其余部分作适当的修改以外，其余很相似
$TMS$能做的仅仅是利用证实来维持一个相同的信念数据库

条件证明

条件证明$(CP)$的证实表示有前提的论点。无论何时，只要在$IN$假设中的节点为$IN$，$OUT$假设中的节点为$OUT$，则结论节点往往为$IN$。于是，条件证明的证实有效

处理$CP$比$SL$更难。事实上，$TMS$是通过把它们转换成$SL$证实来进行处理的

$TMS$将显示证实与当前相信为真（即在$IN$表上）的命题一起存储。当查出不相容时，它只消除必须删去者。此过程称为面向从属关系的回溯

3.8 小结

本章所讨论的知识的搜索与推理是人工智能研究的另一核心问题。对这一问题的研究曾经十分活跃，而且至今仍不乏高层次的研究课题。正如知识表示一样，知识的搜索与推理也有众多的方法，同一问题可能采用不同的搜索策略，而其中有的比较有效，有得不大适合具体问题。