人工智能自动推理(第3部分 归结原理及其应用).ppt

这样所要证明的定理就是： 那么首先求出 和 的子句形，再求它们的并，便得到子句集合 ： 那么子句集 对命题逻辑应用归结原理的重要步骤是在一个子句中找出与另一子句中的某个文字互补的文字。对于不含变量的子句是容易做到的。当子句中含有变量时，问题要复杂很多。如研究子句 中没有文字与 中的任何文字互补。但是若 在 中用 置换x，在 中用a置换y，便得出 其中 和 分别是 和 的基例。从上述例子可以看到，用适当的项置换 和 的变量可以产生新子句。 3.3.2 置换和合一 Substitution and Unification 定义3.5 置换(substitution)是形为 的有限集合，其中 是互不相同的变量，是不同于 的项（可以为常量、变量、函数） 表示用 置换 ，不允许 与 相同，也不允许 循环地出现在另一个 中。 当 是基项时，置换称为基置换(ground substitution)。不含任何元素的置换称为空置换(Null substitution)，用 表示。 例如: 就是一个置换。但是， 不是一个置换，因为置换的目的是为了使某些变元被另外的变元、常量或函数取代，使之不再出现在公式中，而该置换在x和y之间出现了循环置换的情况，既没有消去x，也没有消去y。 定义3.6 令 为置换，E为表达式。设 是用项 同时代换E中出现的所有变量 而得出的表达式。 称为E的特例或例(Instance)。 例3.10 令 则有 定义3.7 令 为两个置换。和 复合也是一个置换，称为复合置换(composite substitution)，用 表示，它由在集合： 中删除下面两类元素得出的： ，当 ，当 例3.11 令 在构造 时，首先建立集合 由于 ，所以要删除 。上述集合中的第三、四元素中的变量x，y都出现在{x,y}中，所以还应删除 。最后得出 ＝ 不难验证出置换有下述性质。 (1) 空置换 是左么元和右么元，即对任意置换 恒有 ＝ ＝ (2) 对任意表达式E，恒有E( )＝(E ) 。 (3) 若对任意表达式E恒有E ＝E ，则 ＝ 。 (4) 对任意置换 ， ， 恒有 即置换的合成满足结合律。 (5) 设A和B为表达式集合，则 注意，置换的合成不满足交换律。 定义3.8 若表达式集合 存在一个置换 ，使得 则称集合 是可合一的(unifiable)，置换 称为合一置换(Unifier)。 例3.12 集合 是可合一的，因为 是它的合一置换。 例3.13 集合 是可合一的，因为 是它的合一置换。另外， 也是一个合一置换。所以合一置换是不唯一的。但是 比 更一般，因为用任意常量置换y都可以得到无穷个基置换。 定义3.9 表达式集合 的合一置换 是最一般的合一置换(MGU, Most General Unifier)，当且仅当对该集合的每个合一置换 都存在置换 使得 。 例如，在例3.13中，mgu = = ，但 ＝ 不是mgu，并存在置换 ，有