人工智能原理教案章 归结推理方法2归结推理方法.ppt

? 2.5.5 单元归结策略 单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，词中方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。 　　单元归结? 完备；反之不成立。 初始子句集中没有单元子句时，单元归结策略无效。所以说反之不成立，即此问题不能采用单元归结策略。 第六十三页，共九十三页。 ? 单元归结的例子 例1 S={P ∨Q,～P ∨ R,～Q ∨ R,～R} 单元归结过程 (1)P∨Q (2)～P∨R (3)～Q∨R (4)～R (5)～P (4)(2) (6)～Q (4)(3) (7)Q (5)(1) (8)P (6)(1) (9)R (7)(3) (10)口 (7)(6) 第六十四页，共九十三页。 ? 2.5.6 输入归结策略 与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。 　　输入归结? 完备；反之不成立。 如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。简单的例子，归结结束时，即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。 第六十五页，共九十三页。 ? 例2 S={P∨Q,～P∨R,～Q∨R，～R} 输入归结过程 (1)P∨Q (2)～P∨R (3)～Q∨R (4)～R (5)Q∨R (1)(2) (6)R (3)(5) (7)口 (4)(6) 第六十六页，共九十三页。 ? 2.3.2子句集 文字：不含任何连接词的谓词公式。 子句：一些文字的析取（谓词的和）。 子句集：所有子句的集合。 对于任一个公式G，都可以通过Skolem标准形，标准化建立起一个子句集与之相对应。因为子句不过是一些文字的析取，是一种比较简单的形式，所以对G的讨论就用对子句集S的讨论来代替，以便容易处理。 　　 第三十一页，共九十三页。 ? 子句集S的求取 子句集S可由下面的步骤求取： 　　1. 谓词公式G转换成前束范式 　　2. 消去前束范式中的存在变量，略去其中的任意变量，生成SKOLEM标准形 　　3. 将SKOLEM标准形中的各个子句提出，表示为集合形式。 教师提示：为了简单起见，子句集生成可以理解为是用“，”取代SKOLEM标准形中的“Λ”，并表示为集合形式 。 注意：SKOLEM标准形必须满足合取范式的条件。即，在生成子句集之前逻辑表达式必须是各谓词表达式或谓词或表达式的与。 第三十二页，共九十三页。 ? 定理：谓词表达式G是不可满足的，当且仅当 其子句集S是不可满足的。 G与S并不等值，但它们在不可满足的意义下是一致的。 因此如果要证明 A1∧A2∧A3→B，只需证明 G＝ A1∧A2∧A3∧～B 的子句集S是不可满足的。 注意：G真不一定S真，而S真必有G真， 即：S ?G。 因为：在生成SKOLEM标准形时将存在量词用常量或其他变量的函数代替，使得变量讨论的论域发生了变化，即论域变小了。所以G不能保证S真。 第三十三页，共九十三页。 ? 谓词归结子句形 G = G1Λ G2Λ G3Λ …Λ Gn 的子句形 G的子句集的求取过程可以分解成几个部分单独处理。 如果Gi的子句集为Si，则　　有 S‘ = S1 ∪ S2 ∪ S3 ∪ …∪ Sn，虽然G的子句集不为S’，但是可以证明：　　SG 与S1 ∪ S2 ∪ S3 ∪ …∪Sn在不可满足的意义上是一致的。 即SG 不可满足?S1 ∪ S2 ∪S3 ∪ …∪ Sn不可满足 由上面的定理，我们对SG的讨论，可以用较为简单的S1 ∪ S2 ∪ S3 ∪ …∪ Sn来代替。为方便起见，也称S1 ∪ S2 ∪ S3 ∪ …∪ Sn为G的子句形，即：　　SG＝S1 ∪ S2 ∪ S3 ∪ …∪ Sn。 第三十四页，共九十三页。 ? 求取子句集的例子（1） 例2－3：对所有的x,y,z来说，如果y是x的父亲，z又是