第3章 确定性推理 智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型，本章重点讨论前一种，不确定性推理放到下一章讨论。 3.1 推理的基本概念 3.2 推理的逻辑基础 3.3 自然演绎推理 3.4 归结演绎推理 3.5 基于规则的演绎推理

3.1 推理的基本概念 3.1.1 什么是推理 3.1.2 推理方法及其分类 3.1.3 推理的控制策略及其分类 3.1.4 正向推理 3.1 推理的基本概念 3.1.1 什么是推理 3.1.2 推理方法及其分类 3.1.3 推理的控制策略及其分类 3.1.4 正向推理 3.1.5 逆向推理 3.1.6 混合推理

3.1.1 什么是推理 推理的概念 是指按照某种策略从已知事实出发去推出结论的过程。 推理所用的事实： 初始证据：推理前用户提供的 3.1.1 什么是推理 推理的概念 是指按照某种策略从已知事实出发去推出结论的过程。 推理所用的事实： 初始证据：推理前用户提供的 中间结论：推理过程中所得到的 推理过程：由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。 例如，医疗专家系统，专家知识保存在知识库中。推理开始时，先把病人的症状和检查结果放到综合数据库中，然后再从综合数据库的初始证据出发，按照某种策略在知识库中寻找，并使用知识，直到推出最终结论为止。 推理的两个基本问题 推理的方法：解决前提和结论的逻辑关系，不确定性传递 推理的控制策略：解决推理方向，冲突消解策略

3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(1/4) 3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(1/4) 可分为演绎推理、归纳推理等 演绎推理 演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论，如假言推理、拒取式和假言三段论。 例： 假言三段论 A→B，B→C ⇒ A→C 常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。 例如，有如下三个判断： ① 计算机系的学生都会编程序； （一般性知识） ② 程强是计算机系的一位学生； （具体情况） ③ 程强会编程序。 （结论） 这是一个三段论推理。其中，①是大前提，②是小前提；③是经演绎推出来的结论。 可见，其结论是蕴含在大前提中的。

3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(2/4) 3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(2/4) 归纳推理 是一种由个别到一般的推理方法。归纳推理的类型 按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理 按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等 完全归纳推理 是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。 不完全归纳推理 是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，计算机，随机抽查。 枚举归纳推理 是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。 例如，设有如下事例： 王强是计算机系学生，他会编程序； 高华是计算机系学生，她会编程序； …… …… 当这些具体事例足够多时，就可归纳出一个一般性的知识： 凡是计算机系的学生，就一定会编程序。

3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(3/4) 3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(3/4) 类比归纳推理 是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。 设A、B分别是两类事物的集合： A={a1,a2,……} B={b1,b2,……} 并设ai与bi总是成对出现，且当ai有属性P时，bi就有属性Q与此对应，即 P(ai)→Q(bi) i=1,2,….. 则当A与B中有一新的元素对出现时，若已知a'有属性P，b'有属性Q，即 P(a')→Q(b') 类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。

3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(4/4) 3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(4/4) 演绎推理与归纳推理的区别 演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。 归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。 例如，一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种归纳推理方式。运用这些一般性知识知识去维修计算机的过程则是演绎推理。

3.1.3 推理的控制策略及其分类 推理的控制策略 推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略。 3.1.3 推理的控制策略及其分类 推理的控制策略 推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略。 推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。 控制策略的分类 由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。 推理策略 主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等 推理方向控制策略用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理。 求解策略是指仅求一个解，还是求所有解或最优解等。 限制策略是指对推理的深度、宽度、时间、空间等进行的限制。 冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。 搜索策略 主要解决推理线路、推理效果、推理效率等问题。 本章主要讨论推理策略，至于搜索策略将放到第4章单独讨论。

3.1.4 正向推理 推理算法 从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。 算法描述 3.1.4 正向推理 推理算法 从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。 算法描述 (1) 把用户提供的初始证据放入综合数据库； (2) 检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步； (3) 检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。 (4) 按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转(2)。 (5) 询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转(3)；否则表示无解，失败退出。 至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。 其流程图如下：

Y 把初始证据放入DB Y 成功退出 DB中有解吗？ N 把用户补充的新事 实加入到DB中 N KB中有可用知识吗？ Y Y 形成可用知识集 用户可补充新事实吗？ 可用知识集空吗？ N Y 失败退出 N 按照冲突消解策略从该知识 集中选出一条知识进行推理 N 推出的是新事实吗？ Y 将新事实加入到DB

3.1.4 正向推理 推理例子 例3.1请用正向推理完成以下问题的求解 假设知识库中包含有以下2条规则： r1： IF B THEN C 3.1.4 正向推理 推理例子 例3.1请用正向推理完成以下问题的求解 假设知识库中包含有以下2条规则： r1： IF B THEN C r2： IF A THEN B 已知初始证据A，求证目标C。 解：本例的推理过程如下： 推理开始前，综合数据库为空。 推理开始后，先把A放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为“N”。 接着检查知识库中是否有可用知识，显然r2可用，形成仅含r2的知识集。从该知识集中取出r2，推出新的实事B，将B加入综合数据库，检查综合数据库中是否含有目标C，回答为“N”。 再检查知识库中是否有可用知识，此时由于B的加入使得r1为可用，形成仅含r1的知识集。从该知识集中取出r1，推出新的实事C，将C加入综合数据库，检查综合数据库中是否含有目标C，回答为“Y”。 它说明综合数据库中已经含有问题的解，推理成功结束，目标C得证。

3.1.4 正向推理 优缺点 正向推理的主要优点 比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。 3.1.4 正向推理 优缺点 正向推理的主要优点 比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。 正向推理的主要缺点 推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。

3.1.5 逆向推理 推理算法 从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。 算法描述： 3.1.5 逆向推理 推理算法 从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。 算法描述： (1) 将要求证的目标（称为假设）构成一个假设集； (2) 从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步； (3) 检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一步； (4) 将知识库中可以导出该假设的所有知识构成一个可用知识集； (5) 检查可用知识集是否为空，若是，失败退出；否则执行下一步； (6) 按冲突消解策略从可用知识集中取出一个知识，继续； (7) 将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。 其流程图如下：

初始化DB和假设集 从假设集中取出一个假设 Y Y 该假设 成立 该假设是DB中的事实吗？ 还有新的假设吗？ N N 该假设能被KB中的知识导出吗？ N 询问用户有此事实吗？ Y 该假设成立 并放入DB Y 将KB中所有能导出此假设的知识构成一个可用知识集 N Y 可用知识集空吗？ 失败退出 成功退出 N 按照冲突消解策略从该知识集中选出一条知识 将该知识前提中的每个子条件作为新的假设加入假设集

3.1.5 逆向推理 推理例子 对上例，采用逆向推理，其推理过程如下： 推理开始前，综合数据库和假设集均为空。 3.1.5 逆向推理 推理例子 对上例，采用逆向推理，其推理过程如下： 推理开始前，综合数据库和假设集均为空。 推理开始后，先将初始证据A和目标C分别放入综合数据库和假设集，然后从假设集中取出一个假设C，查找C是否为综合数据库中的已知事实，回答为“N”。 再检查C是否能被知识库中的知识所导出，发现C可由r1导出，于是r1被放入可用知识集。由于知识库中只有r1可用，故可用知识集中仅含r1。 接着从可用知识集中取出r1，将其前提条件B作为新的假设放入假设集。从假设集中取出B，检查B是否为综合数据库中的实事，回答为“N”。再检查B是否能被知识库中的知识所导出，发现B可由r2导出，于是r2被放入可用知识集。由于知识库中只有r2可用，故可用知识集中仅含r2。 从可用知识集中取出r2，将其前提条件A作为新的假设放入假设集。然后从假设集中取出A，检查A是否为综合数据库中的实事，回答为“Y”。 他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。

3.1.5 逆向推理 优缺点 逆向推理的主要优点 不必寻找和使用那些与假设目标无关的信息和知识 推理过程的目标明确 3.1.5 逆向推理 优缺点 逆向推理的主要优点 不必寻找和使用那些与假设目标无关的信息和知识 推理过程的目标明确 也有利于向用户提供解释，在诊断性专家系统中较为有效。 逆向推理的主要缺点 当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。

3.1.6 混合推理 混合推理的概念 把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。 混合推理的方法 3.1.6 混合推理 混合推理的概念 把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。 混合推理的方法 1. 先正向后逆向 这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。 2. 先逆向后正向 这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。 3. 双向混合 是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。 对于这些方法我不再详细讨论。

第3章 确定性推理 3.1 推理的基本概念 3.2 推理的逻辑基础 3.3 自然演绎推理 3.4 归结演绎推理 3.5 基于规则的演绎推理

3.2 推理的逻辑基础 3.2.1 谓词公式的解释 3.2.2 谓词公式的永真性和可满足性 3.2.3 谓词公式的等价性和永真蕴含性 3.2 推理的逻辑基础 3.2.1 谓词公式的解释 3.2.2 谓词公式的永真性和可满足性 3.2.3 谓词公式的等价性和永真蕴含性 3.2.4 谓词公式的范式 3.2.5 置换与合一

3.2.1 谓词公式的解释 概念 命题公式的解释 在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。 3.2.1 谓词公式的解释 概念 命题公式的解释 在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。 有了命题公式的解释，就可据此求出该命题公式的真值。 谓词公式的解释 由于谓词公式中可能包含由个体常量、变元或函数，因此，必须先考虑这些个体常量和函数在个体域上的取值，然后才能根据它们的具体取值为谓词分别指派真值。 定义3.1 设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值： (1) 为每个个体常量指派D中的一个元素； (2) 为每个n元函数指派一个从Dn到D的一个映射，其中 Dn ={(x1, x2, …, xn)| x1, x2, …, xn∈D} (3) 为每个n元谓词指派一个从Dn到{F，T}的映射。 则称这些指派为P在D上的一个解释I

3.2.1 谓词公式的解释 例子一(1/2) 例3.2 设个体域D={1, 2}，求公式A=(∀x)( y)P(x, y)在D上的解释，并指出在每一种解释下公式A的真值。 解：由于公式A中没有包含个体常量和函数，故可直接为谓词指派真值，设有 这就是公式A 在D 上的一个解释。从这个解释可以看出： 当x=1、y=1时，有P(x,y)的真值为T; 当x=2、y=1时，有P(x,y)的真值为T; 即对x在D上的任意取值，都存在y=1使P(x,y)的真值为T。因此，在此解释下公式A的真值为T。 P(1,1) P(1,2) P(2,1) P(2,2) T F

3.2.1 谓词公式的解释 例子一(2/2) 说明：一个谓词公式在其个体域上的解释不是唯一的。例如，对公式A，若给出另一组真值指派 3.2.1 谓词公式的解释 例子一(2/2) 说明：一个谓词公式在其个体域上的解释不是唯一的。例如，对公式A，若给出另一组真值指派 这也是公式A 在D 上的一个解释。从这个解释可以看出： 当x=1、y=1时，有P(x,y)的真值为T; 当x=2、y=1时，有P(x,y)的真值为F; 即对x在D上的任意取值，不存在一个y使得P(x,y)的真值为T。因此，在此解释下公式A的真值为F。 实际上，A在D上共有16种解释，这里就不在一一列举。 P(1,1) P(1,2) P(2,1) P(2,2) T F

3.2.1 谓词公式的解释 例子二 解：设对个体常量a和函数f(x)的值指派为： 对谓词的真值指派为： 3.2.1 谓词公式的解释 例子二 例3.3 设个体域D={1, 2}，求公式B=(∀x)P(f(x), a)在D上的解释，并指出在该解释下公式B的真值。 解：设对个体常量a和函数f(x)的值指派为： 对谓词的真值指派为： 由于已指派a=1，因此P(1,2)和P(2,2)不可能出现，故没给它们指派真值。 上述指派是公式B在D上的一个解释。在此解释下有 当x=1时，a=1使P(1,1)=T 当x=2时，a=1 使P(2,1)=T 即对x在D上的任意取值，都存在a=1使P(f(x), a)的真值为T。因此，在此解释下公式B的真值为T。 由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为T，而在另一个解释下为F。 a f(1) F(2) 1 2 P(1,1)) P(1,2) P(2,1) P(2,2) T ×

3.2.2 谓词公式的永真性和可满足性 为了以后推理的需要，下面先定义： 3.2.2 谓词公式的永真性和可满足性 为了以后推理的需要，下面先定义： 定义3.2 如果谓词公式P对非空个体域D上的任一解释都取得真值T，则称P在D 上是永真的；如果P在任何非空个体域上均是永真的，则称P永真。 可见，要判定一谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就很难判定了。 定义3.3 对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的。 谓词公式的可满足性也称为相容性。 定义3.4 如果谓词公式P对非空个体域D上的任一解释都取真值F，则称P在D上是永假的；如果P在任何非空个体域上均是永假的，则称P永假。 谓词公式的永假性又称不可满足性或不相容。 后面我们要给出的归结推理，就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。

3.2.3 谓词公式的等价性和永真蕴含性 1. 等价式(1/2) 3.2.3 谓词公式的等价性和永真蕴含性 1. 等价式(1/2) 谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真蕴含式来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规则。 谓词公式的等价式可定义如下： 定义3.5 设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D 上是等价的。如果D是任意非空个体域，则称P与Q是等价的，记作P⇔Q。

3.2.3 谓词公式的等价性和永真蕴含性 1. 等价式(2/2) 3.2.3 谓词公式的等价性和永真蕴含性 1. 等价式(2/2) (1) 双重否定律 ¬ ¬ P ⇔ P (2) 交换律 (P∨Q) ⇔ (Q∨P)， ( P∧Q) ⇔ ( Q∧P) (3) 结合律 (P∨Q)∨R ⇔ P∨(Q∨R) (P∧Q)∧R ⇔ P∧(Q∧R) (4) 分配律 P∨(Q∧R) ⇔ (P∨Q)∧(P∨R) P∧(Q∨R) ⇔ (P∧Q)∨(P∧R) (5) 摩根定律 ¬ (P∨Q) ⇔ P∧Q ¬ (P∧Q) ⇔ P∨Q (6) 吸收律 P∨(P∧Q) ⇔ P P∧(P∨Q) ⇔ P (7) 补余律 P∨P ⇔ T, P∧P ⇔ F (8) 连词化归律 P→Q ⇔ ¬P∨Q P↔Q ⇔ (P→Q)∧(Q→P) P↔Q ⇔ (P∧Q)∨(Q∧P) (9) 量词转换律 ¬ (∃x)P ⇔ (∀x)( ¬ P) ¬ (∀x)P ⇔ (∃x) (¬ P) (10) 量词分配律 (∀x) (P∧Q) ⇔ (∀x)P∧(∀x)Q (∃x) (P∨Q) ⇔ (∃x)P∨(∃x)Q

3.2.3 谓词公式的等价性和永真蕴含性 2. 永真蕴含式 常用的永真蕴含式如下： (1) 化简式 P∧Q ⇒ P， P∧Q ⇒ Q 3.2.3 谓词公式的等价性和永真蕴含性 2. 永真蕴含式 定义3.6 对谓词公式P和Q，如果P→Q永真，则称P 永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提，记作P ⇒ Q。 常用的永真蕴含式如下： (1) 化简式 P∧Q ⇒ P， P∧Q ⇒ Q (2) 附加式 P ⇒ P∨Q， Q ⇒ P∨Q (3) 析取三段论 ﹁ P, P∨Q ⇒ Q (4) 假言推理 P, P→Q ⇒ Q (5) 拒取式 ¬Q, P→Q ⇒ P (6) 假言三段论 P→Q, Q→R ⇒P→R (7) 二难推理 P∨Q, P→R, Q→R ⇒ R (8) 全称固化 (∀x)P(x) ⇒ P(y) 其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。 (9) 存在固化 (∃x)P(x) ⇒ P(y) 其中，y是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。

3.2.4 谓词公式的范式 范式是谓词公式的标准形式。在谓词逻辑中，范式分为两种： 前束范式 3.2.4 谓词公式的范式 范式是谓词公式的标准形式。在谓词逻辑中，范式分为两种： 前束范式 定义3.7 设F为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称F为前束范式。一般形式： (Q1x1)……(Qnxn)M(x1,x2,……,xn) 其中，Qi(i=1,2,……,n)为前缀，它是一个由全称量词或存在量词组成的量词串； M(x1,x2,……,xn)为母式，它是一个不含任何量词的谓词公式。 例如，(∀x) (∀y) (∃z)(P(x)∧Q(y,z)∨R(x,z))是前束范式。 任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集的化简中讨论。 Skolem范式 定义3.8 如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为Skolem范式。 例如，(∃x) (∃z) (∀y)(P(x)∨Q(y,z)∧R(x,z))是Skolem范式。 任一谓词公式均可化为与其对应的Skolem范式，其化简方法也将在后面子句集的化简中讨论。

3.2.5 置换与合一 概念 例如，可根据全称固化推理和假言推理由谓词公式 W1(A) 和 (∀x)(W1(x)→W2(x)) 3.2.5 置换与合一 概念 在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理过程是不能直接进行匹配的，需要先进行置换。 例如，可根据全称固化推理和假言推理由谓词公式 W1(A) 和 (∀x)(W1(x)→W2(x)) 推出W2(A)。对谓词W1(A)可看作是由全程固化推理（即(∀x)(W1(x) ⇒ W1(A))推出的，其中A是任一个体常量。要使用假言推理，首先需要找到项A对变元x的置换，使W1(A)与W1(x)一致。 这种寻找项对变元的置换，使谓词一致的过程叫做合一的过程。 下面讨论置换与合一的有关概念与方法。

3.2.5 置换与合一 1. 置换(1/2) 置换可简单的理解为是在一个谓词公式中用置换项去替换变量。 定义3.9 置换是形如 3.2.5 置换与合一 1. 置换(1/2) 置换可简单的理解为是在一个谓词公式中用置换项去替换变量。 定义3.9 置换是形如 {t1/x1,t2/x2,…,tn/xn} 的有限集合。其中，t1,t2,…,tn是项；x1,x2,…,xn是互不相同的变元；ti/xi表示用ti替换xi。并且要求ti与xi不能相同，xi不能循环地出现在另一个ti中。 例如， {a/x, c/y, f(b)/z} 是一个置换。 但{g(y)/x, f(x)/y}不是一个置换。原因是它在x与y之间出现了循环置换现象。即当用g(y)置换x,用f(g(y))置换y时，既没有消去x，也没有消去y。 若改为{g(a)/x, f(x)/y}即可，原因是用g(a)置换x ，用f(g(a))置换y ，则消去了x和y。 通常，置换是用希腊字母θ、σ、 α、 λ等来表示的。 定义3.10 设θ={t1/x1,t2/x2,…,tn/xn}是一个置换，F是一个谓词公式，把公式F中出现的所有xi换成ti(i=1,2,…,n)，得到一个新的公式G，称G为F在置换θ下的例示，记作G=Fθ。 一个谓词公式的任何例示都是该公式的逻辑结论。

3.2.5 置换与合一 1. 置换(2/2) 定义3.11 设 θ={t1/x1,t2/x2,…,tn/xn} 3.2.5 置换与合一 1. 置换(2/2) 定义3.11 设 θ={t1/x1,t2/x2,…,tn/xn} λ={ u1/y1, u2/y2, … , um/ym } 是两个置换。则θ与λ的合成也是一个置换，记作θ°λ。它是从集合 { t1λ/x1, t2λ/x2, … , tnλ/xn, u1/y1, u2/y2, … , um/ym } 中删去以下两种元素 ① 当tiλ=xi时，删去tiλ/xi (i=1, 2 ,…, n)； ② 当yj∈{ x1, x2 ,…, xn }时，删去uj/yj (j=1, 2 ,…, m) 最后剩下的元素所构成的集合。 例3.4 设θ={ f(y)/x, z/y }，λ={a/x, b/y ,y/z }，求θ与λ的合成。 解:先求出集合 {f(b/y)/x, (y/z)/y, a/x, b/y , y/z}={f(b)/x, y/y, a/x, b/y , y/z} 其中，f(b)/x中的f(b)是置换λ作用于f(y)的结果；y/y 中的y是置换λ作用于z的结果。在该集合中，y/y满足定义中的条件①，需要删除；a/x和b/y满足定义中的条件②，也需要删除。最后得 θ°λ={f(b)/x, y/z}

3.2.5 置换与合一 2. 合一 合一可理解为是寻找项对变量的置换，使两个谓词公式一致。可定义为： 3.2.5 置换与合一 2. 合一 合一可理解为是寻找项对变量的置换，使两个谓词公式一致。可定义为： 定义3.12 设有公式集F={F1, F2,…,Fn}，若存在一个置换θ，可使 F1θ=F2θ=…=Fnθ， 则称θ是F的一个合一。称F1,F2,…,Fn是可合一的。 例如，设有公式集F={P(x,y,f(y)), P(a,g(x),z)}，则 λ={a/x, g(a)/y, f(g(a))/z} 是它的一个合一。 一般来说，一个公式集的合一不是唯一的。 定义3.13 设σ是公式集F的一个合一，如果对F的任一个合一θ都存在一个置换λ，使得θ=σ°λ，则称σ是一个最一般合一。 一个公式集的最一般合一是唯一的。 对如何求取最一般合一的问题，不再讨论。

第3章 确定性推理 3.1 推理的基本概念 3.2 推理的逻辑基础 3.3 自然演绎推理 3.4 归结演绎推理 3.5 基于规则的演绎推理

3.3 自然演绎推理 自然演绎推理 从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 3.3 自然演绎推理 自然演绎推理 从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 自然演绎推理最基本的推理规则是三段论推理，它包括： 假言推理 P, P→Q ⇒ Q 拒取式 ﹁ Q, P→Q ⇒ P 假言三段论 P→Q, Q→R ⇒ P→R 自然演绎推理的例子 例3.5 设已知如下事实： A, B, A→C, B∧C→D, D→Q 求证：Q为真。 证明：因为 A, A→C⇒ C 假言推理 B, C⇒ B∧C 引入合取词 B∧C，B∧C→D ⇒ D 假言推理 D, D→Q ⇒ Q 假言推理 因此，Q为真

3.3 自然演绎推理 例3.6 设已知如下事实： (1) 只要是需要编程序的课，王程都喜欢。 3.3 自然演绎推理 例3.6 设已知如下事实： (1) 只要是需要编程序的课，王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序的课。 (3) C是一门程序设计语言课。 求证：王程喜欢C这门课。 证明：首先定义谓词 Prog(x) x是需要编程序的课。 Like(x, y) x喜欢y。 Lang(x) x是一门程序设计语言课 把已知事实及待求解问题用谓词公式表示如下： Prog(x)→Like(Wang , x) (∀x)( Lang(x)→Prog(x)) Lang(C) 应用推理规则进行推理： Lang(y)→Prog(y) 全称固化 Lang(C)，Lang(y)→Prog(y) ⇒ Prog(C) 假言推理 {C/y} Prog(C), Prog(x)→Like(Wang , x) ⇒ Like(Wang , C) 假言推理 {C/x} 因此，王程喜欢C这门课。

3.3 自然演绎推理 优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。 3.3 自然演绎推理 优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。 缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。

第3章 确定性推理 3.1 推理的基本概念 3.2 推理的逻辑基础 3.3 自然演绎推理 3.4 归结演绎推理 3.5 基于规则的演绎推理

3.4 归结演绎推理 归结演绎推理是一种基于鲁宾逊（Robinson）归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。 在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明P→Q永真。 由3.2节可知，要证明P→Q永真，就是要证明P→Q在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。 为此，人们进行了大量的探索，后来发现可以采用反证法的思想，把关于永真性的证明转化为关于不可满足性的证明。 即要证明P→Q永真，只要能够证明P∧﹁Q是不可满足的就可以了(原因是﹁ (P→Q) ⇔ ﹁(﹁ P∨Q) ⇔ P∧﹁ Q 。 这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。

3.4 归结演绎推理 3.4.1 子句集及其化简 3,4.2 鲁滨逊归结原理 3.4.3 归结反演推理的归结策略 3.4 归结演绎推理 3.4.1 子句集及其化简 3,4.2 鲁滨逊归结原理 3.4.3 归结反演推理的归结策略 3.4.4 用归结反演求取问题的答案

3.4.1 子句集及其化简 1. 子句和子句集 鲁滨逊归结原理是在子句集的基础上讨论问题的。因此，讨论归结演绎推理之前，需要先讨论子句集的有关概念。 子句和子句集 定义3.14 原子谓词公式及其否定统称为文字。 例如，P(x)、Q(x)、﹁ P(x)、 ﹁ Q(x)等都是文字。 定义3.15 任何文字的析取式称为子句。 例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。 定义3.16 不含任何文字的子句称为空子句。 由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。 空子句一般被记为□或NIL。 定义3.17 由子句或空子句所构成的集合称为子句集。

3.4.1 子句集及其化简 2. 子句集的化简（1/6） 在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下： (1) 消去连接词“→”和“↔” 反复使用如下等价公式： P→Q ⇔﹁ P∨Q P↔Q ⇔ (P∧Q)∨(﹁P∧﹁Q) 即可消去谓词公式中的连接词“→”和“↔”。 例如公式 (∀x)((∀y)P(x,y)→﹁ (∀y)(Q(x,y)→R(x,y))) 经等价变化后为 (∀x)(﹁(∀y)P(x,y)∨﹁ (∀y)(﹁Q(x,y)∨R(x,y)))

3.4.1 子句集及其化简 2. 子句集的化简（2/6） (2) 减少否定符号的辖域 反复使用双重否定率 ﹁(﹁P) ⇔ P 摩根定律 3.4.1 子句集及其化简 2. 子句集的化简（2/6） (2) 减少否定符号的辖域 反复使用双重否定率 ﹁(﹁P) ⇔ P 摩根定律 ﹁(P∧Q) ⇔﹁P∨﹁Q ﹁(P∨Q) ⇔﹁P∧﹁Q 量词转换率 ﹁ (∀x)P(x) ⇔ (∃x) ﹁P(x) ﹁ (∃x)P(x) ⇔ (∀x)￢P(x) 将每个否定符号“﹁”移到仅靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。 例如，上式经等价变换后为 (∀x)((∃y)﹁P(x，y)∨(∃y)( Q(x，y) ∧﹁R(x，y)))

3.4.1 子句集及其化简 2. 子句集的化简（3/6） (3) 对变元标准化 3.4.1 子句集及其化简 2. 子句集的化简（3/6） (3) 对变元标准化 在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。 例如，上式经变换后为 (∀x)((∃y)﹁P(x，y)∨(∃z)( Q(x，z) ∧﹁R(x，z))) (4) 化为前束范式 化为前束范式的方法:把所有量词都移到公式的左边，并且在移动时不能改变其相对顺序。由于第(3)步已对变元进行了标准化，每个量词都有自己的变元，这就消除了任何由变元引起冲突的可能，因此这种移动是可行的。 例如，上式化为前束范式后为 (∀x)(∃y) (∃z)(﹁P(x，y)∨( Q(x，z) ∧﹁R(x，z)))

3.4.1 子句集及其化简 2. 子句集的化简（4/6） (5) 消去存在量词 消去存在量词时，需要区分以下两种情况： 3.4.1 子句集及其化简 2. 子句集的化简（4/6） (5) 消去存在量词 消去存在量词时，需要区分以下两种情况： 若存在量词不出现在全称量词的辖域内（即它的左边没有全称量词），只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。 若存在量词位于一个或多个全称量词的辖域内，例如 (∀x1)…(∀xn) (∃y)P(x1，x2 ,…, xn ,y) 则需要用Skolem函数f(x1，x2 ,…, xn)替换受该存在量词约束的变元y，然后再消去该存在量词。 例如，上步所得公式中存在量词(∃y)和(∃z)都位于(∀x)的辖域内，因此都需要用Skolem函数来替换。设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后的式子为 (∀x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))

3.4.1 子句集及其化简 2. 子句集的化简（5/6） (6) 化为Skolem标准形 Skolem标准形的一般形式为 3.4.1 子句集及其化简 2. 子句集的化简（5/6） (6) 化为Skolem标准形 Skolem标准形的一般形式为 (∀x1)…(∀xn) M(x1,x2,……,xn) 其中， M(x1,x2,……,xn)是Skolem标准形的母式，它由子句的合取所构成。 把谓词公式化为Skolem标准形需要使用以下等价关系 P∨(Q∧R) ⇔ (P∨Q)∧(P∨R) 例如，前面的公式化为Skolem标准形后为 (∀x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))) (7) 消去全称量词 由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。但剩下的母式，仍假设其变元是被全称量词量化的。 例如，上式消去全称量词后为 (﹁P(x,f(x))∨Q(x,g(x)) ∧(﹁P(x,f(x))∨﹁R(x,g(x)))

3.4.1 子句集及其化简 2. 子句集的化简（6/6） (8) 消去合取词 3.4.1 子句集及其化简 2. 子句集的化简（6/6） (8) 消去合取词 在母式中消去所有合取词，把母式用子句集的形式表示出来。其中，子句集中的每一个元素都是一个子句。 例如，上式的子句集中包含以下两个子句 ﹁P(x,f(x))∨Q(x,g(x)) ﹁P(x,f(x))∨﹁R(x,g(x)) (9) 更换变量名称 对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此任意两个不同子句的变量之间实际上不存在任何关系。这样，更换变量名是不会影响公式的真值的。 例如，对前面的公式，可把第二个子句集中的变元名x更换为y，得到如下子句集 ﹁P(y,f(y))∨﹁R(y,g(y))

3.4.1 子句集及其化简 3. 子句集的应用（1/4） 在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此化简后的标准子句集是不唯一的。 这样，当原谓词公式为非永假时，它与其标准子句集并不等价。但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。 这个结论很重要，是归结原理的主要依据，可用定理的形式来描述。 定理3.1 设有谓词公式F，其标准子句集为S，则F为不可满足的充要条件是S为不可满足的。 为证明此定理，先作如下说明： 为讨论问题方便，设给定的谓词公式F已为前束形 (Q1x1)… (Qrxr)… (Qnxn)M(x1,x2,…,xn) 其中，M(x1,x2,…,xn)已化为合取范式。 由于将F化为这种前束形是一种很容易实现的等价运算，因此这种假设是可以的。

3.4.1 子句集及其化简 3. 子句集的应用（2/4） 又设(Qrxr)是第一个出现的存在量词(∃xr)，即F为 3.4.1 子句集及其化简 3. 子句集的应用（2/4） 又设(Qrxr)是第一个出现的存在量词(∃xr)，即F为 F=(x1)…(xr-1) (∃xr)(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,xr,xr+1…,xn) 为把F化为Skolem形，需要先消去这个(∃xr)，并引入Skolem函数，得到 F1=(x1)…(xr-1) (Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…xr-1),xr+1…,xn) 若能证明 F不可满足 ⇔ F1不可满足 则同理可证 F1不可满足 ⇔ F2不可满足 重复这一过程，直到证明了 Fm-1不可满足 ⇔ Fm不可满足 为止。 此时，Fm已为F的Skolem标准形。而S只不过是Fm的一种集合表示形式。因此有 Fm不可满足 ⇔ S不可满足 下面开始用反证法证明

3.4.1 子句集及其化简 3. 子句集的应用（3/4） 先证明 ⇒ 3.4.1 子句集及其化简 3. 子句集的应用（3/4） 先证明 ⇒ 已知F不可满足，假设F1是可满足的，则存在一个解释I，使F1在解释I下为真。即对任意x1,…,xr-1在I的设定下有 (Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…,xr-1),xr+1…,xn) 为真。亦即对任意的x1,…,xr-1都有一个f(x1,…,xr-1)使 为真。即在I下有 (∀x1)…(∀xr-1) (∃xr)(Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,xr,xr+1…,xn) 为真。即F在I下为真。 但这与前提F是不可满足的相矛盾，即假设F1为可满足是错误的。从而可以得出“若F不可满足，则必有F1不可满足”。

3.4.1 子句集及其化简 3. 子句集的应用（4/4） 再证明 已知F1不可满足，假设F是可满足的。于是便有某个解释I使F在I下为真。即对任意的x1,…,xr-1在I的设定下都可找到一个xr使 (Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,xr,xr+1…,xn) 为真。若扩充I，使它包含一个函数f(x1,…,xr-1)，且有 xr= f(x1,…,xr-1) 这样，就可以把所有的(f(x1,…,xr-1)映射到xr，从而得到一个新的解释I’，并且在此解释下对任意的x1,…,xr-1都有 　 (Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…xr-1),xr+1…,xn) 为真。即在I’下有 (∀x1)…(∀xr-1) (Qr+1xr+1)…(Qnxn)M(x1,…,xr-1,f(x1,…xr-1),xr+1…,xn) 为真。它说明F1在解释I’下为真。但这与前提F1是不可满足的相矛盾，即假设F为可满足是错误的。从而可以得出“若F1不可满足，则必有F不可满足” 于是，定理得证。 由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。至于如何证明一个子句集的不可满足性，由下面的海伯伦理论和鲁宾逊归结原理来解决。

3.4.2 鲁滨逊归结原理 1. 基本思想 注意以下两个关键 第一，子句集中的子句之间是合取关系。因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的； 第二，空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。 鲁滨逊归结原理基本思想 首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S'。然后设法检验子句集S'是否含有空子句，若含有空子句，则表明S'是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。 鲁滨逊归结原理包括 命题逻辑归结原理 谓词逻辑归结原理

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（1/8） 归结推理的核心是求两个子句的归结式 (1) 归结式的定义及性质 定义3.18 若P是原子谓词公式，则称P与﹁P为互补文字。 定义3.19 设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。 例3.7 设C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的归结式C12。 解：这里L1=P，L2=﹁P，通过归结可以得到 C12= Q∨R∨S 例3.8 设C1=﹁Q，C2=Q，求C1和C2的归结式C12。 解：这里L1=﹁Q，L2=Q，通过归结可以得到 C12= NIL

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（2/8） 例3.9 设设C1 =﹁P ∨ Q ，C2=﹁Q，C3=P，求C1、C2、C3的归结式C123。 解：若先对C1、C2归结，可得到 C12=﹁P 然后再对C12和C3归结，得到 C123=NIL 如果改变归结顺序，同样可以得到相同的结果，即其归结过程是不唯一的。 其归结归结过程可用右图来表示，该树称为归结树。 ﹁P ∨ Q ﹁Q ﹁P P NIL P ﹁P ∨ Q ﹁Q Q NIL

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（3/8） 定理3.2 归结式C12是其亲本子句C1和C2的逻辑结论。 证明：（按定义）设C1=L∨C1 ’ ，C2=﹁L∨C2’关于解释I为真，则只需证明C12= C1 ’ ∨C2’关于解释I也为真。 对于解释I，L和﹁L中必有一个为假。 若L为假，则必有C1'为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1'为真。 同理，若﹁L为假，则必有C2'为真。 因此，必有C12= C1'∨C2'关于解释I也为真。即C12是C1和C2的逻辑结论。

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（4/8） 上述定理是归结原理中的一个重要定理，由它可得到以下两个推论： 推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即： S1的不可满足性 ⇒ S的不可满足性 证明：设S={ C1，C2，C3，……，Cn}，C12是C1和C2的归结式，则用C12代替C1和C2后可得到一个新的子句集 S1={ C12，C3，…, Cn} 设S1是不可满足的，则对不满足S1的任一解释I，都可能有以下两种情况： ① 解释I使C12为真，则C3，……，Cn中必有一个为假，即S是不可满足的。 ② 解释I使C12为假，即﹁C12为真，根据定理3.2有﹁ (C1∧C2)永真，即﹁C1∨﹁C2永真，它说明解释I使C1为假，或C2为假。即S也是不可满足的。 因此可以得出 S1的不可满足性⇒S的不可满足性

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（5/8） 推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即： S2的不可满足性⇔S的不可满足性 先证明 设S={ C1，C2，C3，…，Cn}是不可满足的，则C1，C2，C3，…，Cn中必有一子句为假，因而S2={ C12，C1，C2，C3，……，Cn}必为不可满足。 再证明 ⇒ 设S2是不可满足的,则对不满足S2的任一解释I,都可能有以下两种情况： ① 解释I使C12为真，则C1，C2，C3，…，Cn中必有一个为假，即S是不可满足的。 ② 解释I使C12为假，即﹁C12为真，根据定理3.2有 ﹁(C1∧C2)永真，即﹁C1∨﹁C2永真，它说明解释I使C1为假，或C2为假。即S也是不可满足的。 由此可见S与S2的不可满足性是等价的。即 S的不可满足性 ⇔ S2的不可满足性

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（6/8） 上述两个推论说明，为证明子句集S的不可满足性，只要对其中可进行归结得子句进行归结，并把归结式加入到子句集S中，或者用归结式代替他的亲本子句，然后对新的子句集证明其不可满足性就可以了。 如果经归结能得到空子句，根据空子句的不可满足性，即可得到原子句集S是不可满足的结论。 在命题逻辑中，对不可满足的子句集S，其归结原理是完备的。 这种不可满足性可用如下定理描述： 定理3.3 子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（7/8） (2) 命题逻辑的归结反演 归结原理：假设F为已知前提，G为欲证明的结论，归结原理把证明G为F的逻辑结论转化为证明F∧﹁G为不可满足。 再根据定理3.1，在不可满足的意义上，公式集F∧﹁G与其子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足。 应用归结原理证明定理的过程称为归结反演。 在命题逻辑中，已知F，证明G为真的归结反演过程如下： ①否定目标公式G，得﹁G; ②把﹁G并入到公式集F中，得到{F，﹁G}； ③把{F，﹁G}化为子句集S。 ④ 应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。

3.4.2 鲁滨逊归结原理 2. 命题逻辑的归结（8/8） 例3.10 设已知的公式集为{P, (P∧Q)→R, (S∨T)→Q, T}，求证结论R。 解：假设结论R为假, 将﹁R加入公式集，并化为子句集 S={P,﹁P∨﹁Q∨R, ﹁S∨Q, ﹁T∨Q, T, ﹁R} 其归结过程如右图的归结演绎树所示。该树根为空子句。 其含义为：先假设子句集S中的所有子句均为真，即原公式集为真,﹁R也为真；然后利用归结原理，对子句集进行归结，并把所得的归结式并入子句集中；重复这一过程，最后归结出了空子句。 根据归结原理的完备性，可知子句集S是不可满足的，即开始时假设﹁R为真是错误的，这就证明了R为真。 ﹁P ∨﹁Q∨R ﹁ R P ﹁P ∨﹁Q ﹁Q ﹁T ∨Q ﹁T T NIL

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（1/16） 谓词逻辑的归结原理 谓词逻辑中的归结式可用如下定义来描述： 在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一对变元进行代换，然后才能进行归结。可见，谓词逻辑的归结要比命题逻辑的归结麻烦一些。 谓词逻辑的归结原理 谓词逻辑中的归结式可用如下定义来描述： 定义3.20 设C1和C2是两个没有公共变元的子句，L1和L2分别是C1和C2中的文字。如果L1和L2存在最一般合一σ，则称 C12=({C1σ}-{ L1σ})∪({ C2σ}-{ L2σ}) 为C1和C2的二元归结式，而L1和L2为归结式上的文字。

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（2/16） 例3.11 设C1=P(a)∨R(x)，C2=﹁P(y)∨Q(b)，求 C12 解：取L1= P(a), L2=﹁P(y)，则L1和L2的最一般合一是σ={a/y}。根据定义3.20,可得 C12=( {C1σ}-{L1σ}) ∪ ({C2σ}-{L2σ}) =({P(a), R(x)}-{P(a)})∪({﹁P(a), Q(b)}-{﹁P(a)}) =({R(x)})∪({Q(b)})= {R(x), Q(b)} =R(x)∨Q(b) 例3.12 设C1=P(x)∨Q(a)，C2=﹁P(b)∨R(x) ，求 C12 解：由于C1和C2有相同的变元x，不符合定义3.20的要求。为了进行归结，需要修改C2中变元x的名字为，令C2=﹁P(b)∨R(y)。此时L1= P(x), L2 =﹁P(b)，L1和L2的最一般合一是σ={b/x}。则有 C12=( {C1σ}-{L1σ})∪ ({C2σ}-{L2σ}) =({P(b), Q(a)}-{P(b)}) ∪ ({﹁P(b), R(y)}-{﹁P(b)}) =({Q(a)}) ∪ ({R(y)})= {Q(a), R(y)} =Q(a)∨R(y)

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（3/16） (1) 这里之所以使用集合符号和集合的运算，目的是为了说明问题的方便。 对以上讨论做以下两点说明: (1) 这里之所以使用集合符号和集合的运算，目的是为了说明问题的方便。 即先将子句Ciσ和Liσ写成集合的形式，在集合表示下做减法和并集运算，然后再写成子句集的形式。 (2) 定义中还要求C1和C2无公共变元，这也是合理的。 例如C1=P(x)，C2=﹁P(f(x))，而S={ C1, C2}是不可满足的。但由于C1和C2的变元相同，就无法合一了。没有归结式，就不能用归结法证明S的不可满足性，这就限制了归结法的使用范围。 如果对C1或C2的变元进行换名，便可通过合一，对C1和C2进行归结。如上例，若先对C2进行换名，即C2=﹁P(f(y))，则可对C1和C2进行归结，得到一个空子句，从而证明了S是不可满足的。 事实上，在由公式集化为子句集的过程中，其最后一步就是做换名处理。因此，定义中假设C1和C2没有相同变元是可以的。

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（4/16） 例3.13 设C1=P(x)∨﹁Q(b)，C2=﹁P(a)∨Q(y)∨R(z) 解：对C1和C2通过最一般合一（σ={a/x, b/y}）的作用，可以得到两个互补对。 注意：求归结式不能同时消去两个互补对，这样的结果不是二元归结式。如在σ={a/x, b/y}下，若同时消去两个互补对，所得的R(z)不是C1和C2的二元归结式。 例3.14 设C1=P(x)∨P(f(a))∨Q(x) ，C2=﹁P(y)∨R(b)，求C12 解：对参加归结的某个子句，若其内部有可合一的文字，则在进行归结之前应先对这些文字进行合一。本例的C1中有可合一的文字P(x)与P(f(a))，若用它们的最一般合一σ={f(a)/x}进行代换，可得到 C1σ=P(f(a))∨Q(f(a)) 此时可对C1σ与C2进行归结。选L1= P(f(a)), L2 =﹁P(y)，L1和L2的最一般合一是σ={f(a)/y}，则可得到C1和C2的二元归结式为 C12=R(b)∨Q(f(a)) 我们把C1σ称为C1的因子。一般来说，若子句C中有两个或两个以上的文字具有最一般合一σ，则称Cσ为子句C的因子。如果Cσ是一个单文字，则称它为C的单元因子。 应用因子概念，可对谓词逻辑中的归结原理给出如下定义：

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（5/16） 定义3.21若C1和C2是无公共变元的子句，则 ① C1和C2的二元归结式; 例3.15 设C1=P(y)∨P(f(x))∨Q(g(x)) ，C2=﹁P(f(g(a)))∨Q(b)，求C12。 解：对C1 ，取最一般合一σ={f(x)/y}，得C1的因子 C1σ=P(f(x))∨Q(g(x)) 对C1的因子和C2归结（σ={g(a)/x }），可得到C1和C2的二元归结式 C12=Q(g(g(a)))∨Q(b) 说明： 对谓词逻辑，定理3.2仍然适用，即归结式C12是其亲本子句C1和C2的逻辑结论。用归结式取代它在子句集S中的亲本子句，所得到的子句集仍然保持着原子句集S的不可满足性。 此外，对谓词逻辑定理3.3也仍然适用，即从不可满足的意义上说，一阶谓词逻辑的归结原理也是完备的

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（6/16） 谓词逻辑的归结反演 谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比，其步骤基本相同，但每步的处理对象不同。例如，在步骤(3)化简子句集时，谓词逻辑需要把由谓词构成的公式集化为子句集；在步骤(4)按归结原理进行归结时，谓词逻辑的归结原理需要考虑两个亲本子句的最一般合一。 例3.16 已知 F: (∀x)((∃y)(A(x, y)∧B(y))→(∃y)(C(y)∧D(x, y))) G: ﹁(∃x)C(x)→(∀x)(∀y)(A(x, y)→﹁B(y)) 求证G是F的逻辑结论。 证明：先把G否定，并放入F中，得到的{F, ﹁G}为 {(∀ x)((∃ y)(A(x,y)∧B(y))→(∃ y)(C(y)∧D(x,y))), ﹁(﹁(∃ x)C(x)→(∀ x)(∀ y)(A(x,y)→﹁ B(y)))}

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（7/16） 再把{F,﹁G}化成子句集，得到 (1) ﹁A(x,y)∨﹁ B(y) ∨C(f(x)) (2) ﹁ A(u,v)∨﹁ B(v) ∨D(u,f(u)) (3) ﹁ C(z) (4) A(m,n) (5) B(k) 其中，(1)、(2)是由F 化出的两个子句，(3)、(4)、(5)是由﹁G化出的3个子句。 最后应用谓词逻辑的归结原理对上述子句集进行归结，其过程为 (6) ﹁ A(x,y)∨ ﹁ B(y) 由(1)和(3)归结，取σ={f(x)/z} (7) ﹁ B(n) 由(4)和(6)归结，取σ={m/x,n/y} (8) NIL 由(5)和(7)归结，取σ={n/k} 因此，G是F 的逻辑结论。 上述归结过程可用如下归结树来表示

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（8/16） ﹁A(x,y)∨﹁ B(y)∨C(f(x)) ﹁ C(z) {f(x)/z} A(m,n) {m/x,n/y} ﹁ B(n) B(k) {n/k} NIL

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（9/16） 为了进一步加深对谓词逻辑归结的理解，下面再给出一个经典的归结问题 例3.17 “快乐学生”问题 假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。 求证：张是快乐的。 解：先定义谓词： Pass(x, y) x可以通过y考试 Win(x, prize) x能获得奖励 Study(x) x肯学习 Happy(x) x是快乐的 Lucky(x) x是幸运的

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（10/16） 再将问题用谓词表示如下： “任何通过计算机考试并奖的人都是快乐的” (∀x)(Pass(x, computer)∧Win(x, prize)→Happy(x)) “任何肯学习或幸运的人都可以通过所有考试” (∀x) (∀ y) (Study(x)∨Lucky(x)→Pass(x, y)) “张不肯学习但他是幸运的” ﹁Study(zhang)∧Lucky(zhang) “任何幸运的人都能获奖” (∀x) (Lucky(x)→Win(x, prize)) 结论“张是快乐的”的否定 ﹁Happy(zhang)

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（11/16） 将上述谓词公式转化为子句集如下： (1) ﹁Pass(x, computer)∨﹁Win(x, prize)∨Happy(x) (2) ﹁Study(y)∨Pass(y, z) (3) ﹁Lucky(u)∨Pass(u, v) (4) ﹁Study(zhang) (5) Lucky(zhang) (6) ﹁Lucky(w)∨Win(w, prize) (7) ﹁ Happy(zhang) (结论的否定)

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（12/16） ﹁Pass(x, computer)∨﹁Win(x, prize)∨Happy(x) ﹁Lucky(w)∨Win(w, prize) {w/x} ﹁Pass(w, Computer)∨Happy(w) ∨﹁Lucky(w) ﹁ Happy(zhang) {zhang/w} Lucky(zhang) ﹁Pass(zhang, Computer)∨﹁Lucky(zhang) ﹁Pass(zhang, Computer) ﹁Lucky(u)∨Pass(u, v) {zhang/u, computer/v} ﹁Lucky(zhang) Lucky(zhang) NIL

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（13/16） 为了进一步加深对谓词逻辑归结的理解，下面再给出一个经典的归结问题 例3.18 “激动人心的生活”问题 假设：所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李明能看书且不贫穷，快乐的人过着激动人心的生活。 求证：李明过着激动人心的生活。 解：先定义谓词： Poor(x) x是贫穷的 Smart(x) x是聪明的 Happy(x) x是快乐的 Read(x) x能看书 Exciting(x) x过着激动人心的生活

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（14/16） 再将问题用谓词表示如下： “所有不贫穷并且聪明的人都是快乐的” (∀x)((﹁Poor(x)∧Smart(x))→Happy(x)) “那些看书的人是聪明的” (∀y) (Read(y) → Smart(y)) “李明能看书且不贫穷” Read(Liming)∧﹁Poor(Liming) “快乐的人过着激动人心的生活” (∀z) (Happy(z)→Exciting(z)) 目标“李明过着激动人心的生活”的否定 ﹁Exciting(Liming)

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（15/16） 将上述谓词公式转化为子句集如下： (1) Poor(x)∨﹁Smart(x)∨Happy(x) (2) ﹁Read(y)∨Smart(y) (3) Read(Liming) (4) ﹁Poor(Liming) (5) ﹁Happy(z)∨Exciting(z) (6) ﹁Exciting(Liming) (结论的否定)

3.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结（16/16） ﹁Exciting(Liming) ﹁Happy(z)∨Exciting(z) {Liming/z} ﹁Happy(Liming) Poor(x))∨﹁Smart(x)∨Happy(x) {Liming/x} Poor(Liming)∨﹁Smart(Liming) ﹁Read(y)∨Smart(y ) {Liming/y} Poor(Liming)∨﹁Read(Liming) ﹁Poor(Liming) ﹁Read(Liming) Read(Liming) NIL

3.4.3 归结演绎推理的归结策略 归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对，并通过对这些子句对的归结，最终得出一个空子句的过程。由于事先并不知道哪些子句对可进行归结，更不知道通过对哪些子句对的归结能尽快得到空子句，因此就需要对子句集中的所有子句逐对进行比较，直到得出空子句为止。这种盲目的全面进行归结的方法，不仅会产生许多无用的归结式，更严重的是会产生组核爆炸问题。因此，需要研究有效的归结策略来解决这些问题。 目前，常用的归结策略可分为两大类，一类是删除策略，另一类是限制策略。删除策略是通过删除某些无用的子句来缩小归结范围；限制策略是通过对参加归结的子句进行某些限制，来减少归结的盲目性，以尽快得到空子句。为了说明选择归结策略的重要性，在讨论各种常用的归结策略之前，还是先提一下广度优先策略。

3.4.3 归结演绎推理的归结策略 1. 广度优先策略（1/3） 广度优先是一种穷尽子句比较的复杂搜索方法。设初始子句集为S0，广度优先策略的归结过程可描述如下： (1) 从S0出发，对S0中的全部子句作所有可能的归结，得到第一层归结式，把这些归结式的集合记为S1; (2) 用S0中的子句与S1中的子句进行所有可能的归结，得到第二层归结式，把这些归结式的集合记为S2; (3) 用S0和S1中的子句与S2中的子句进行所有可能的归结，得到第三层归结式，把这些归结式的集合记为S3; 如此继续，知道得出空子句或不能再继续归结为止。 例3.19 设有如下子句集： S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用宽度优先策略证明S为不可满足。 宽度优先策略的归结树如下：

3.4.3 归结演绎推理的归结策略 1. 广度优先策略（2/3） ﹁I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) S S1 R(a) ﹁I(x) ∨L(x) ﹁R(a) ﹁I(a) NIL S2 L(a) L(a) ﹁I(a)

3.4.3 归结演绎推理的归结策略 1. 广度优先策略（3/3） 从这个例子可以看出，宽度优先策略归结出了许多无用的子句，既浪费事间，又浪费空间。但是，这种策略由一个有趣的特性，就是当问题有解时保证能找到最短归结路径。 因此，它是一种完备的归结策略。宽度优先对大问题的归结容易产生组合爆炸，但对小问题却仍是一种比较好的归结策略。

3.4.3 归结演绎推理的归结策略 2. 支持集策略（1/3） 支持集策略是沃斯(Wos)等人在1965年提出的一种归结策略。它要求每一次参加归结的两个亲本子句中，至少应该有一个是由目标公式的否定所得到的子句或它们的后裔。可以证明支持集策略是完备的，即当子句集为不可满足时，则由支持集策略一定能够归结出一个空子句。也可以把支持集策略看成是在宽度优先策略中引入了某种限制条件，这种限制条件代表一种启发信息，因而有较高的效率 例3.20 设有如下子句集： S={﹁I(x)∨R(x), I(a),﹁ R(y)∨L(y), ﹁L(a) } 其中，﹁I(x)∨R(x)为目标公式的否定。用支持集策略证明S为不可满足。

3.4.3 归结演绎推理的归结策略 2. 支持集策略（2/3） ﹁I(x)∨R(x) I(a) ﹁ R(y)∨L(y) ﹁L(a) R(a) ﹁I(x)∨L(x) L(a) L(a) ﹁I(a) NIL

3.4.3 归结演绎推理的归结策略 2. 支持集策略（3/3） 从上述归结过程可以看出，各级归结式数目要比宽度优先策略生成的少，但在第二级还没有空子句。就是说这种策略限制了子句集元素的剧增，但会增加空子句所在的深度。此外，支持集策略具有逆向推理的含义，由于进行归结的亲本子句中至少有一个与目标子句有关，因此推理过程可以看作是沿目标、子目标的方向前进的。

3.4.5 归结演绎推理的归结策略 3. 删除策略（1/3） 主要想法是：归结过程在寻找可归结子句时，子句集中的子句越多，需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉，这就会缩小搜索范围，减少比较次数，从而提高归结效率。 常用的删除方法有以下几种（纯文字、重言式、包孕） 纯文字删除法 如果某文字L在子句集中不存在可与其互补的文字﹁L，则称该文字为纯文字。 在归结过程中，纯文字不可能被消除，用包含纯文字的子句进行归结也不可能得到空子句，因此对包含纯文字的子句进行归结是没有意义的，应该把它从子句集中删除。 对子句集而言，删除包含纯文字的子句，是不影响其不可满足性的。例如，对子句集 S={P∨Q∨R, ﹁Q∨R, Q, ﹁R} 其中P是纯文字，因此可以将子句P∨Q∨R从子句集S中删除。

3.4.3 归结演绎推理的归结策略 3. 删除策略（2/3） 重言式删除法 如果一个子句中包含有互补的文字对，则称该子句为重言式。例如 P(x)∨﹁P(x), P(x)∨Q(x)∨﹁P(x) 都是重言式，不管P(x)的真值为真还是为假，P(x)∨﹁P(x)和P(x)∨Q(x)∨﹁P(x)都均为真。 重言式是真值为真的子句。对一个子句集来说，不管是增加还是删除一个真值为真的子句，都不会影响该子句集的不可满足性。因此，可从子句集中删去重言式。

3.4.3 归结演绎推理的归结策略 3. 删除策略（3/3） 包孕删除法 设有子句C1和C2，如果存在一个置换σ，使得C1σ⊆C2，则称C1包孕于C2。例如 P(x) 包孕于 P(y)∨Q(z) σ={x/y} P(x) 包孕于 P(a) σ={a/x} P(x) 包孕于 P(a)∨Q(z) σ={a/x} P(x) ∨Q(a) 包孕于 P(f(a))∨Q(a)∨R(y) σ={f(a)/x} P(x) ∨Q(y) 包孕于 P(a)∨Q(u)∨R(w) σ={a/x, u/y} 对子句集来说，把其中包孕的子句删去后，不会影响该子句集的不可满足性。因此，可从子句集中删除哪些包孕的子句。

3.4.3 归结演绎推理的归结策略 4. 单文字子句策略（1/2） 如果一个子句只包含一个文字，则称此子句为单文字子句。单文字子句策略是对支持集策略的进一步改进，它要求每次参加归结的两个亲本子句中至少有一个子句是单文字子句。 例3.21 设有如下子句集： S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用单文字子句策略证明S为不可满足。 采用单文字子句策略，归结式包含的文字数将少于其亲本子句中的文字数，这将有利于向空子句的方向发展，因此会有较高的归结效率。但这种策略是不完备的，即当子句集为不可满足时，用这种策略不一定能归结出空子句。

3.4.3 归结演绎推理的归结策略 4. 单文字子句策略（2/2） ﹁I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) R(a) ﹁R(a) NIL

3.4.3 归结演绎推理的归结策略 5. 线形输入策略（1/2） 这种策略要求每次参加归结的两个亲本子句中，至少应该有一个是初始子句集中的子句。所谓初始子句集是指开始归结时所使用的子句集。 例3.22 设有如下子句集： S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用线性输入策略证明S为不可满足。 线性输入策略可限制生成归结式的数目，具有简单和高效的优点。但是，这种策略也是一种不完备的策略。例如，子句集 S={Q(u)∨P(a), ﹁Q(w)∨P(w), ﹁Q(x)∨﹁ P(x), Q(y)∨﹁ P(y)} 从S出发很容易找到一棵归结反演树，但却不存在线性输入策略的归结反演树。

3.4.3 归结演绎推理的归结策略 5. 线形输入策略（2/2） ﹁I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) ﹁ R(a) R(a) ﹁I(x)∨L(x) ﹁I(a) L(a) L(a) ﹁I(a) NIL

3.4.3 归结演绎推理的归结策略 6. 祖先过滤策略（1/2） 这种策略与线性输入策略有点相似，但是，放宽了对子句的限制。每次参加归结的两个亲本子句，只要满足以下两个条件中的任意一个就可进行归结： (1) 两个亲本子句中至少有一个是初始子句集中的子句。 (2) 如果两个亲本子句都不是初始子句集中的子句，则一个子句应该是另一个子句的先辈子句。所谓一个子句(例如C1)是另一个子句(例如C2)的先辈子句是指C2是由C1与别的子句归结后得到的归结式。 例3.23 设有如下子句集： S={﹁Q(x)∨﹁P(x), Q(y)∨﹁P(y)，﹁Q(w)∨P(w) , Q(a)∨P(a) } 用祖先过滤策略证明S为不可满足 证明：从S出发，按祖先过滤策略归结过程如下图所示。 可以证明祖先过滤策略也是完备的。 上面分别讨论了几种基本的归结策略，但在实际应用中，还可以把几种策略结合起来使用。总之，在选择归结反演策略时，主要应考虑其完备性和效率问题。

3.4.3 归结演绎推理的归结策略 6. 祖先过滤策略（2/2） ﹁Q(x)∨ ﹁P(x) Q(y)∨﹁P(y) ﹁ P(x) ﹁ Q(w)∨P(w) ﹁ Q(w) Q(a)∨P(a) P(a) NIL

3.4.4 用归结反演求取问题的答案 （1/4） 归结原理出了可用于定理证明外，还可用来求取问题答案，其思想与定理证明相似。其一般步骤为： (1) 把问题的已知条件用谓词公式表示出来，并化为相应的子句集； (2) 把问题的目标的否定用谓词公式表示出来，并化为子句集； (3) 对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标否定子句和此目标否定子句的否定之间再进行析取所得到的子句），用这些重言式代替相应的目标否定子句式，并把这些重言式加入到前提子句集中，得到一个新的子句集； (4) 对这个新的子句集，应用归结原理求出其证明树，这时证明树的根子句不为空，称这个证明树为修改的证明树； (5) 用修改证明树的根子句作为回答语句，则答案就在此根子句中。

3.4.4 用归结反演求取问题的答案 （2/4） 下面再通过一个例子来说明如何求取问题的答案。 例3.24 已知：“张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。” 问：“现在李在哪个教室上课？” 解：首先定义谓词： C(x, y) x和y是同班同学； At(x, u) x在u教室上课。 把已知前提用谓词公式表示如下： C(zhang, li) (∀x) (∀y) (∀u) (C(x, y)∧At(x, u)→At(y,u)) At(zhang, 302) 把目标的否定用谓词公式表示如下： ﹁(∃v)At(li, v)

3.4.4 用归结反演求取问题的答案 （3/4） 把上述公式化为子句集： C(zhang, li) ﹁C(x, y)∨﹁At(x, u)∨At(y, u) At(zhang, 302) 把目标的否定化成子句式，并用重言式 ﹁At(li,v) ∨At(li,v) 代替之。 把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。其求解过程如下图所示。 该证明树的根子句就是所求的答案，即“李明在302教室”。

3.4.4 用归结反演求取问题的答案 （4/4） ﹁C(x, y)∨﹁At(x, u)∨At(y, u) ﹁At(li,v)∨At(li,v) {li/y,v/u} At(li,v)∨﹁ C(x, li)∨﹁At(x, v) C(zhang, li) {Zhang/x} ﹁ At(zhang,v)∨At(li, v) At(zhang, 302) {302/v} At(li, 302)

3.5 基于规则的演绎推理 上一节讨论了归结演绎推理，它需要把谓词公式化为子句形，尽管这种转化在逻辑上是等价的，但是原来蕴含在谓词公式中的一些重要信息却会在求取子句形的过程中被丢失。例如，下面的几个蕴含式 ﹁A∧﹁B→C, ﹁A∧﹁C→B, ﹁A→B∨C, ﹁B→A∨C, 都与子句 A∨B∨C 等价。但在A∨B∨C中，是根本得不到原逻辑公式中所蕴含的哪些超逻辑的含义的。况且，在不少情况下人们多希望使用那种接近于问题原始描述的形式来进行求解，而不希望把问题描述化为子句集。 规则是一种比较接近于人们习惯的问题描述方式，按照这种问题描述方式进行求解的系统称为基于规则的系统，或者叫做基于规则的演绎系统。 规则演绎系统的推理可分为正向演绎推理、逆向演绎推理和双向演绎推理三种形式。

3.5.1 规则正向演绎推理 规则正向演绎和前面所讨论过的正向推理相对应。 它是从已知事实出发，正向使用规则，直接进行演绎，直至到达目标为止的一种证明方法。一个直接演绎系统不一定比反演系统更有效，但其演绎过程容易被人们所理解。

3.5.1 规则正向演绎推理 1. 事实表达式的与/或形变换（1/2） 在一个基于规则的正向演绎系统中，其前提条件中的事实表达式是作为系统的初始综合数据库来描述的。对事实的化简，只须转换成不含蕴含符号“→”的与/或形表示即可，而不必化成子句集。把事实表达式化为非蕴含形式的与/或形的主要步骤如下： (1) 利用连接词化规律“P→Q⇔﹁P∨Q”，消去蕴含符号。事实上，在事实表达式中很少有含蕴含符号“→”出现，因为可把蕴含式表示成规则。 (2) 利用狄.摩根定律及量词转换率把“﹁”移到紧靠谓词的位置，直到每个否定符号的辖域最多只含一个谓词为止。 (3) 对所得到的表达式进行前束化。 (4) 对全称量词辖域内的变量进行改名和标准化，对存在量词量化的变量用skolem函数代替，使不同量词约束的变元有不同的名字。 (5) 消去全称量词，而余下的变量都被认为是全程量词量化的变量。 (6) 对变量进行换名，使主合取元具有不同的变量名。

3.5.1 规则正向演绎推理 1. 事实表达式的与/或形变换（2/2） 例如，有如下表达式 (∃x) (∀y)(Q(y, x)∧﹁((R(y)∨P(y))∧S(x, y))) 可把它转化为： Q(z, a)∧((﹁R(y)∧﹁P(y))∨﹁S(a, y)) 这就是与/或形表示。

3.5.1 规则正向演绎推理 2. 事实表达式的与/或树表示（1/3） 事实表达式的与/或形可用一棵与/或树表示出来。例如，对上例所给出的与/或式，可用如下与/或树来表示。 Q(z, a)∧((﹁R(y)∧﹁P(y))∨﹁S(a, y)) Q(z, a) ((﹁R(y)∧﹁P(y))∨﹁S(a, y)) ﹁R(y)∧﹁P(y) ﹁S(a, y) ﹁R(y) ﹁P(y)

3.5.1 规则正向演绎推理 2. 事实表达式的与/或树表示（2/3） 在该图中，每个节点表示该事实表达式的一个子表达式，子表达式之间的与、或关系规定如下： 当某个表达式为k个子表达式的析取时，例如E1∨E2∨…∨Ek，其中的每个子表达式Ei均被表示为E1∨E2∨…∨Ek的后继节点，并由一个k线连接符将这些后继节点都连接到其父节点，即表示成与的关系。 当某个表达式为k个子表达式的合取时，例如E1∧E2∧…∧Ek，其中的每个子表达式Ei均被表示成E1∧E2∧…∧Ek的一个单一的后继节点，并由一个单一连接符连接到其父节点，即表示成或的关系。 这样，与/或树的根节点就是整个事实表达式，端节点均为事实表达式中的一个文字。有了与/或树的表示，就可以求出其解树（结束于文字节点上的子树）集。并且可以发现，事实表达式的子句集与解树集之间存在着一一对应关系，即解树集中的每个解树都对应着子句集中的一个子句。其对应方式为：解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。 例如，上图所示的与/或树有3个解树，分别对应这以下3个子句： Q(z, a) ﹁R(y)∨ ﹁ S(a, y) ﹁P(y)∨ ﹁ S(a, y)

3.5.1 规则正向演绎推理 2. 事实表达式的与/或树表示（3/3） 与/或树的这个性质很重要，它可以把与/或树看作是对子句集的简洁表示。不过，表达式的与/或树表示要比子句集表示的通用性差一些，原因是与/或树中的合取元没有进一步展开，因此不能象在子句形中那样对某些变量进行改名，这就限制了与/或树表示的灵活性。例如，上面的最后一个子句，在子句集中其变量y可全部改名为x，但却无法在与/或树中加以表示，因而失去了通用性，并且可能带来一些困难。 还需要指出，这里的与/或树是作为综合数据库的一种表示，其中的变量受全称量词的约束。而在第2章可分解产生式系统中，所描述的与/或树则是搜索过程的一种表示，两者有着不同的目的和含义，因此应用时应加以区分。

3.5.1 规则正向演绎推理 3. 规则的与/或形变换（1/2） 在与/或形正向演绎系统中，是以正向方式使用规则(F规则)对综合数据库中的与/或树结构进行变换的。为简化这种演绎过程，通常要求F规则应具有如下形式： L→W 其中，L为单文字，W为与/或形公式。假定出现在蕴含式中的任何变量全都受全称量词的约束，并且这些变量已经被换名，使得他们与事实公式和其他规则中的变量不同。 如果领域知识的规则表示形式与上述要求不同，则应将它转换成要求的形式。其变换步骤如下：

3.5.1 规则正向演绎推理 3. 规则的与/或形变换（2/2） (1) 暂时消去蕴含符号“→”。设有如下公式： (∀x)(((∃y) (∀ z)P(x, y,z))→(∀u)Q(x, u)) 运用等价关系“P→Q⇔﹁P∨Q”，可将上式变为： (∀x)(﹁((∃ y) (∀z)P(x, y,z))∨(∀u)Q(x, u)) (2) 把否定符号“﹁”移到紧靠谓词的位置上，使其作用域仅限于单个谓词。通过使用狄.摩根定律及量词转换率可把上式转换为： (∀ x)( (∀y) (∃z)﹁P(x, y,z))∨ (∀u)Q(x, u)) (3) 引入Skolem函数，消去存在量词。消去存在量词后，上式可变为： (∀ x)( (∀y) (﹁P(x, y,f(x,y)))∨(∀u)Q(x, u)) 化成前束式，消去全部全称量词。消去全称量词后，上式变为： ﹁P(x, y,f(x,y))∨Q(x, u) 此公式中的变元都被视为受全称量词约束的变元。 (5) 恢复蕴含式表示。利用等价关系“﹁P∨Q⇔P→Q”将上式变为： P(x, y,f(x,y))→Q(x, u) 在上述对F规则的要求中，之所以限制其前件为单文字，是因为在进行正向演绎推理时要用F规则作用于表示事实的与/或树，而该与/或树的叶节点都是单文字，这样就可用F规则的前件与叶节点进行简单匹配。对非单文字情况，若形式为L1∨L2→W，则可将其转换成与之等价的两个规则L1→W与 L2→W进行处理。

3.5.1 规则正向演绎推理 4. 目标公式的表示形式 与/或树正向演绎系统要求目标公式用子句形表示。如果目标公式不是子句形，则需要化成子句形。把一个目标公式转化为子句形的步骤与第3节所述的化简子句形的步骤类似，但Skolem化的过程不同。目标公式的Skolem化过程是化简子句形的Skolem过程的对偶形式，即把目标公式中属于存在量词辖域内的全称变量用存在量词量化变量的Skolem函数来代替，使经Skolem化目标公式只剩下存在量词，然后再对析取元作变量替换，最后把存在量词消掉。 例如：设目标公式为 (∃y) (∀x) (P(x, y)∨Q(x, y)) 用Skolem函数消去全称量词后有 (∃y)(P(f(y), y)∨Q(f(y), y)) 进行变量换名，使每个析取元具有不同的变量符号，于是有 (∃y)P(f(y), y)∨(∃z)Q(f(z), z) 最后，消去存在量词得 P(f(y), y)∨Q(f(z), z) 这样，目标公式中的变量都假定受存在量词的约束

3.5.1 规则正向演绎推理 5. 规则正向演绎系统（1/5） 规则正向演绎推理过程是从已知事实出发，不断运用F规则，推出欲证明目标公式的过程。即先用与/或树把已知事实表示出来，然后再用F规则的前件和与或树的叶节点进行匹配，并通过一个匹配弧把匹配成功的F规则加入到与/或树中，依此使用F规则，直到产生一个含有以目标节点为终止节点的解图为止。 下面分命题逻辑和谓词逻辑两种情况来讨论规则正向演绎过程。

3.5.1 规则正向演绎推理 5. 规则正向演绎系统（2/5） 命题逻辑的规则演绎过程 由于命题逻辑中的公式不含变元，因此其规则演绎过程比较简单。 例3.25 设已知事实为：A∨B F规则为： r1: A→C∧D r2: B→E∧G 目标公式为：C∨G 证明：先将已知事实用与/或树表示出来，然后再用匹配弧把r1和r2分别连接到事实与/或树中与r1和r2前件匹配的两个不同端节点，由于出现了以目标节点为终节点的解树，故推理过程结束。这一证明过程可用下图表示。

3.5.1 规则正向演绎推理 5. 规则正向演绎系统（3/5） 在该图中，双箭头表示匹配弧，它相当于一个单线连接符。 目标 C G 匹配 C D E G F规则 r1 r2 A B 匹配 A B 已知事实 A∨B

3.5.1 规则正向演绎推理 5. 规则正向演绎系统（4/5） 为了验证上述推理的正确性，下面再用归结演绎推理给于证明。由已知事实、规则及目标的否定可得到如下子句集： {A∨B, ﹁A∨C, ﹁A∨D, ﹁B∨E, ﹁B∨G, ﹁C, ﹁G} 其归结过程如下图所示。 可见，用归结演绎推理对已知事实、F规则集目标的否定所过程的子句集进行归结，得到了空子句NIL，从而证明了目标公式。它与正向演绎推理所得到的结果是一致的。 ﹁A∨C ﹁C ﹁B∨G ﹁G A∨B ﹁B ﹁A B NIL

3.5.1 规则正向演绎推理 5. 规则正向演绎系统（5/5） 在谓词逻辑情况下，由于事实、F规则及目标中均含有变元，因此，其规则演绎过程还需要用最一般合一对变进行置换。 例3.26 设已知事实的与/或形表示为：P(x, y)∨(Q(x)∧R(v, y)) F规则为： P(u, v)→(S(u)∨N(v)) 目标公式为：S(a)∨N(b)∨Q(c) 其推理过程如下图所示。 S(a) N(b) Q(c) {a/u} {b/v} {c/x} S(u) N(v) R(v, y) Q(x) P(u, v) {u/x,v/y} Q(x)∧R(v, y) P(x, y) P(x, y)∨(Q(x)∧R(v, y))

3.5.2 规则逆向演绎推理 规则逆向演绎推理过程是从目标公式的与/或树出发，反向使用规则（B规则），对目标公式的与/或树进行变换，直到得出含有事实节点一致解图为止。包括： 目标公式的与/或形变换 目标公式的与/或树表示 B规则的表示形式 规则逆向演绎推理过程

3.5.2 规则逆向演绎推理 1. 目标公式的与/或形变换 逆向系统中的目标公式采用与/或形表示，其化简采用与正向系统中对事实表达式处理的对偶形式。 即要用存在量词约束变元的Skolem函数来替换由全称量词约束的相应变元，消去全称量词，再消去存在量词，并进行变元换名，使主析取元之间具有不同的变元名。 例如，有如下目标公式： (∃y) (∀x)(P(x)→(Q(x)∧¬(R(x)∧S(y)))) Skolem化后为 ¬P(f(y))∨(Q(f(y), y)∧(¬R(f(y))∨¬S(y))) 变元换名后为 ¬P(f(z))∨(Q(f(y), y)∧(¬R(f(y))∨¬S(y)))

3.5.2 规则逆向演绎推理 2. 目标公式的与/或树表示 目标公式的与/或形也可用与/或树表示出来，其表示方法与正向演绎推理中事实的与或树表示略有不同。它规定: 子表达式之间的析取关系用单一连接符连接，表示称或的关系； 子表达式之间的合取关系则用k线连接符连接，表示为与的关系。 例如，对上述目标公式的与/或形，可用如下的与/或树表示。

¬P(f(z))∨Q(f(y), y)∧(¬R(f(y))∨¬S(y)) Q(f(y), y)∧(¬R(f(y))∨¬S(y)) 在目标公式的与/或树中，若把叶节点用它们之间的合取及析取关系连接起来，就可得到原目标公式的三个子目标： ¬P(f(z)) Q(f(y), y)∧¬ R(f(y)) Q(f(y), y)∧¬ S(y) 即：子目标是文字的合取式

3.5.2 规则逆向演绎推理 3. B规则和已知事实的表示形式 W→L 其中，前项W为任一与/或形公式，后项L为一单文字。 当B规则为W→L1∧L2时，则可化件为两条规则W→L1和W→L2进行处理。 已知事实的表示形式 反向演绎系统的事实表达式限制为文字合取形式，如 F1∧F2∧ …∧Fn 其中，每个Fi（i=1,2,…,n）都为单文字，且都可单独起作用，因此可表示为如下集合形式 { F1∧F2∧ …∧Fn }

3.5.2 规则逆向演绎推理 5. 规则逆向演绎推理过程(一) 从目标公式的与/或树出发，不断用B规则的右部和与/或树的叶节点进行匹配，并将匹配成功的B规则用表有最一般合一匹配弧加入到与或树中，直到产生某个终止在事实节点上的一致解图为止。 一致解图是指在推理过程中所用到的置换应该是一致的。 例3.32 设有如下事实： f1: DOG(Fido) Fido是一只狗 f 2: ¬BARKS(Fido) Fido是不叫的 f 3: WAGS-TAIL(Fido) Fido摇尾巴 f 4: MEOWS(Myrtle) 猫咪的名字叫Myrtle

3.5.2 规则逆向演绎推理 5. 规则逆向演绎推理过程(二) 规则：r1: (WAGS-TAIL(x1)∧DOG(x1)→FRIENDLY(x1) 摇尾巴的狗是温顺的狗 r2: (FRIENDLY(x2)∧¬BARKS(x2)→AFRAID(y2, x2) 温顺又不叫的东西是不值得害怕的 r3: DOG(x3)→ANIMAL(x3) 狗为动物 r4: CAT(x4)→ANIMAL(x4) 猫为动物 r5: MEOWS(x5)→CAT(x5) 猫咪是猫 问题：是否存在这样的一只猫和一条狗，使得这只猫不害怕这只狗？ 该问题的目标公式为 (∃x) (∃y) (CAT(x)∧DOG(y)∧¬AFRAID(x, y)) 改目标公式经变换后得到 CAT(x)∧DOG(y)∧AFRAID(x, y) 用逆向推理求解该问题的演绎过程如下图所示：

CAT(x)∧DOG(y)∧¬AFRAID(x,y) {x5/x} {Fido/y} {y2/x , x2/y} CAT(x5) DOG(Fido) ¬AFRAID(y2,x2) r5 r2 MEOWS(x) ¬BARKS(y) FRIENDLY(y) {Myrtle/x} {Fido/y} {x1/y} MEOWS(Myrtle) ¬BARKS(Fido) FRIENDLY(x1) r1 该图有8条匹配弧，每条弧上都有一置换。其中终止在事实节点上的置换为{Myrtle/x}和{Fido/y}。把它们应用到目标公式，就得到该问题的解： WAGS-TAIL(y) DOG(y) {Fido/y} {Fido/y} WAGS-TAIL(Fido) DOG(Fido) CAT({Myrtle}∧DOG(Fido)∧¬AFRAID({Myrtle, Fido}

作 业 3.13 (6) 判断以下子句是否为不可满足 {P(x)∨Q(x )∨R(x), ﹁P(y)∨R(y), ﹁ Q(a), ﹁R(b)} 3.14 (3) 证明G是F的逻辑结论 F: (∃x)(∃y)(P(f(x))∧(Q(f(y))) G: P(f(a))∧P(y)∧Q(y) 3.18 设有子句集 {P(x)∨Q(x, b), P(a)∨﹁Q(a, b),﹁Q(a, f(a)), ﹁P(x)∨Q(x, b)} 请用祖先过滤策略求出其归结式

分章实验2（选 作） 简单动物识别系统的推理 1. 实验目的 理解掌握产生式系统的推理方法，能够用选定的编程语言设计推理机。 2. 实验环境 在微型计算机上，任选一种编程语言。 3. 实验要求 (1) 以分章实验1的动物识别系统的规则库和综合数据库为基础。 (2) 用选定的编程语言开发一个推理机，该推理机能够利用分章实验1的规则库和综合数据库进行推理