人工智能-14 命题演练中的归结.pdf

《人工智能-14 命题演练中的归结.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下载第14章命题演算中的归结14.1一种新的推理规则：归结14.1.1作为合式公式的子句在上一章中提到了几种推理规则，包括假言推理。许多这样的规则可以组合成一个规则，叫做归结（resolution）。本书中使用的归结应用于代表合式公式的一个特殊的形式，叫做子句（clause），现在来定义它。首先，回想一下，一个文字或者是一个原子（在这种情况下，它叫做肯定文字（positiveliteral）），或者是一个原子的否定（在这种情况下，它叫做否定文字（negativeliteral））。一个子句是一个文字的集合。这个集合是对这个集合中的所有文字的

2、析取式的一个缩写。因此，一个子句是一种特殊的合式公式。通常把子句写为析取式，但是当它们用集合概念来表达时，有些包含归结的定义就会比较简单。例如，子句{P，Q，ÂR}（相当于P∨Q∨ÂR）是一个合式公式。空子句{}（有时候写为Nil）相当于F（它的值是假）。14.1.2子句上的归结命题演算的归结规则可以陈述如下：从{l}∪∑和{Âl}∪∑（其中∑和∑是文字的集1212合，而l是一个原子），我们可以推出∑∪∑，它被称为两个子句的归结式（resolvent）。原12子l是被归结的原子（atomresolvedupon），这个过程叫做归结。下面是一

3、些例子：¥归结R∨P和ÂP∨Q产生R∨Q。这两个被归结的子句可以写成隐含式ÂRÉP和PÉQ。一条应用于这些隐含的、叫做链式（chaining）的推理规则产生ÂRÉQ，它等价于归结式R∨Q。因此我们知道链是归结的一个特例。¥归结R和ÂR∨P产生P。既然第二个子句与RÉP等价，我们知道假言推理也是归结的一个特例。¥在P上归结ÂP∨Q∨W和P∨Q∨R∨S产生Q∨R∨S∨W。注意只有一个Q的个例出现在归结式中—这个毕竟被定义为一个集合。¥在Q上归结P∨W∨ÂQ∨R和P∨Q∨ÂR产生P∨ÂR∨R∨W。在R上归结它们产生P∨Q∨入Q∨W。在这种情况下，

4、既然ÂR∨R和Q∨ÂQ有真值，那么这些归结式中的每一个的值也是真的。在这个例子中，我们必须在Q上或者在R上归结，但不能两者同时！也就是说，P∨W不是这两个子句的归结式！用Âl来归结一个肯定文字l产生空子句。因为l和Âl是互补的，从l和Âl可以推出F。任何包含l和Âl的合式公式的集合都是不可满足的。另一方面，一个包含一个原子和它的否定的子句（如l∨Âl），不管l的真假值，总是为真值。第14章命题演算中的归结计计141下载14.1.3归结的合理性刚才描述的归结规则是一种合理的推理规则。就是说，假如子句{l}∪∑和{Âl}∪∑都12有真值，那么它

5、们的归结式∑∪∑也有真值。验证这一事实的一种方法是“用实例来推论”。12我们知道原子l或者有真值或者为假值。假如（情形1）l为真值，那么Âl就有假值，故要使子句{Âl}∪∑为真，子句∑必须为真值。假如（情形2）l为假值，那么要使子句{l}∪∑221为真，子句∑必须有真值。结合这两种情形，可以看到或者∑或者∑必须有真值；因此∑∪1121∑就有真值。一种相似的论证可以用真值表来进行。214.2转换任意的合式公式为子句的合取式命题演算中的任何合式公式都可以被转换为一个等价的子句的合取式。一个表示为子句的合取式的合式公式叫做合取范式。（一个表示为文

6、字合取式的析取式的合式公式叫做析取范式）。用一个例子来说明转换一个任意的合式公式为合取范式的过程的每一步，用来说明这个过程的合式公式是Â（PÉQ）∨（RÉP）。1)用∨符号，用等价的形式来消除蕴含符号：Â（ÂP∨Q）∨（ÂR∨P）2)用德·摩根定律和用消除双Â符号的方法来缩小Â符号的辖域：（P∧ÂQ）∨（ÂR∨P）3)首先，用结合律和分配律把它转换为CNF。（P∨ÂR∨P）∧（ÂQ∨ÂR∨P）然后（P∨ÂR）∧（ÂQ∨ÂR∨P）一个子句的合取式（即一个合式公式的CNF形式）常常（用蕴含子句的合取式）表示为一个子句的集合；因而是{（P∨ÂR）

7、,（ÂQ∨ÂR∨P）}在第3步中把合式公式（或合式公式的部分）从DNF形式转换到CNF形式，下面的过程也许是有用的。首先，把DNF合式公式写成一个矩阵，它的行元素是每个合取项中的文字；我们有蕴含行的析取式。例如，DNF形式（P∧QÂR）∨（S∧R∧ÂP）∨（Q∧S∧P）可以表示为如下的矩阵：PQÂRSRÂPQSP现在，在每一行中选一个文字并生成这些文字的析取式。在例子中，这样的一个选择可以是P∨R∨P。作出所有可能的这种选择，每一个选择对应于一个子句，并且把所有这些子句的合取式当作原始合式公式的CNF形式。我们可以把其中某些子句简化，例如，

8、P∨R∨P可简化为P∨R，还可以把某些子句消除，例如，P∨ÂP∨Q可以被消除，因为它是永真的。也可以消除被包容（subsumed）在另外一个子句中的一些子句（一个子句g包容1在子