第14章命题演算中的归结.ppt

* * 第14章 命题演算中的归结 第三部分 知识的表示和推理 一种新的推理规则：归结 作为合式公式的子句 许多推理规则（包括假言推理）可以组合成一个规则，叫做归结(resolution)。这里使用的归结应用于代表合式公式的一个特殊的形式——子句(clause) 。 一个文字或者是一个原子(在这种情况下，它叫做肯定文字(positive literal))，或者是一个原子的否定(在这种情况下，它叫做否定文字(negative literal))。 一种新的推理规则：归结 作为合式公式的子句 一个子句是一个文字的集合。这个集合是对这个集合中的所有文字的析取式的一个缩写。 因此，一个子句是一种特殊的合式公式。通常把子句写为析取式，但是当它们用集合概念来表达时，有些包含归结的定义就会比较简单。 例如，子句{P， Q，﹁R}(相当于P∨Q∨﹁R)是一个合式公式。空子句{ }(有时候写为Nil)相当于F(它的值是假)。 一种新的推理规则：归结 子句上的归结 命题演算的归结规则可以陈述如下：从{λ}∪Σ1和{﹁λ}∪Σ2 (其中Σ1和Σ2是文字的集合，而λ是一个原子)，我们可以推出Σ1∪Σ2，它被称为两个子句的归结式(resolvent)。原子λ是被归结的原子(atom resolved upon)，这个过程叫做归结。 例子： · 归结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。在这种情况下，既然﹁R∨R 和 Q∨﹁Q 有真值，那么这些归结式中的每一个的值也是真的。在这个例子中，我们必须在Q上或者在R上归结，但不能两者同时!也就是说， P∨W不是这两个子句的归结式! 一种新的推理规则：归结 用﹁λ来归结一个肯定文字λ产生空子句。因为λ和﹁λ是互补的，从λ和﹁λ可以推出F。任何同时包含λ和﹁λ的合式公式的集合都是不可满足的。 另一方面，一个包含一个原子和它的否定的子句(如λ∨﹁λ)，不管λ的真假值，总是为真值。 子句上的归结 一种新的推理规则：归结 归结的合理性 刚才描述的归结规则是一种合理的推理规则。 就是说，假如子句{λ}∪Σ1和{﹁λ}∪Σ2都有真值，那么它们的归结式Σ1∪Σ2也有真值。验证这一事实的一种方法是“用实例来推论”。 我们知道原子λ或者为真值或者为假值。假如(情形1) λ为真值，那么﹁λ就有假值，故要使{﹁λ}∪Σ2为真，子句Σ2必须为真值。假如(情形2) λ为假值，那么要使子句{λ}∪Σ1为真，子句Σ1必须有真值。结合这两种情形，可以看到或者Σ1或者Σ2必须有真值；因此Σ1∪Σ2就有真值。一种相似的论证可以用真值表来进行。 转换任意的合式公式为子句的合取式 命题演算中的任何合式公式都可以被转换为一个等价的子句的合取式。 一个表示为子句的合取式的合式公式叫做合取范式。 一个表示为文字合取式的析取式的合式公式叫做析取范式。 转换任意的合式公式为子句的合取式 用一个例子来说明转换一个任意的合式公式为合取范式的过程的每一步，用来说明这个过程的合式公式是： 1)用∨符号，用等价的形式来消除蕴含符号： 2)用德·摩根定律和用消除双﹁符号的方法来缩小﹁符号的辖域： 3)首先，用结合律和分配律把它转换为CNF。 然后 一个子句的合取式(即一个合式公式的CNF形式)常常(用蕴含子句的合取式)表示为一个子句的集合；因而是 在第3步中把合式公式(或合式公式的部分)从DNF形式转换到CNF形式 。 转换任意的合式公式为子句的合取式 归结是一种合理的推理规则，也就是说，Δres ? γ蕴含Δ ? γ，其中γ是一个子句。但是归结并不完备。例如，P∧R ? P∨R，但是不能在子句的集合 {P , R}上用归结推出P∨R(因为这里没有什么可以被归结的)。所以不能直接用归结来决定所有的逻辑涵蕴。