第四章经典逻辑推理

1、 经典逻辑推理是根据经典逻辑的逻辑规则进行的一种推理，又称为机械-自动定理证明，主要的方法有：主要的推理方法有：自然演绎推理归结演绎推理与/或性推理呛口小辣椒博客 第四章： 经典逻辑推理其值只有真假是一种精确推理4.1 基本概念基本概念1 什么是推理什么是推理/理的基本概念理的基本概念 (1) 推理：按某种策略由已知判断推出另一种判断的思维过程 (2) 判断分为已知判断由已知判断推出新判断，推理的结论 (3) 在人工智能系统中，推理是由程序实现的，称为推理机。4.1.2 推理的方法及其分类 1. 按照推理的逻辑基础分类 可分为演绎推理演绎推理、归纳推理归纳推理和默认推理默认推理。（1）演绎推理

2、 演绎推理是从已知的一般性知识出发，推理出适合于某种个别情况的结论的过程。它是一种由一般到个别的推理方法。4.1 推理概述推理概述 1. 大前提 ：已知的一般性的知识或假设2. 小前提：具体情况或个别事实的判断3. 结论：由大前提推出适合于小前提所示情况的判断例如：所有的足球运动员的身体都是强壮的高波是一名足球运动员所以高波的身体是强壮的在任何情况下，由演绎推理推到出的结论都是蕴含在大前提的一般性知识之中的。 3.1 推理概述推理概述 （2）归纳推理 归纳推理是从足够的事例中归纳出一般性结论的推理过程，是一种由个别到一般的推理方法。其基本思想是：首先从已知事实中猜测出一个结论，然后对这个结论的

3、正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。 归纳推理又可分为： 从特殊事例考察范围看：完全归纳推理、不完全归纳推理； 从使用的方法看：枚举归纳推理、类比归纳推理。归纳推理可以分为：1. 完全归纳推理：是指在进行归纳时考察了事物的全部对象，并根据这些对象是否具有某些属性，从而推出这个事物是否具有这个属性。2. 不完全归纳推理：只考察了相应事物的部分对象就得到了结论。 例如： 对某厂的每一个产品都进行严格检查，且都严格，则推到出改产生产的产品时合格的必然结论。 我们也可以抽查，随机地抽查了部分产品，只要他们都合格，我们就说该厂的产品是合格的。（3）默认推理 默认推理又称缺省推理，是

4、在知识不完全的情况下假设某些条件已经具备所进行的推理。也就是说，在进行推理时，如果对某些证据不能证明其不成立的情况下，先假设它是成立的，并将它作为推理的依据进行推理，但在推理过程中，当由于新知识的加入或由于所推出的中间结论与已有知识发生矛盾时，就说明前面的有关证据的假设是不正确，这时就要撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理4.1 推理概述推理概述 定理一：定理一： D 是 AB 中点 DE / AC 求证： E 是 AC 中点定理二：定理二： D 是 AB 中点 E 是 AC 中点 求证： DE / ACA, B, C 不共线A, B, C 可以共线无法证明A，B，

5、C共线 ，则默认A，B，C是不共线的2. 按所用知识的确定性分类 按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理。 1. 推理时所用的知识都是精确的，推出的结论也是正确的，其真值或为真或为假。 2. 不确定性推理：推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假之间，命题的外延模糊不清。4.1 推理概述推理概述 3. 按推理过程的单调性 按照推理过程中所推出的结论是否单调地增加，或者说按照推理过程所得到的结论是否越来越接近最终目标来分类，推理可分为单调推理与非单调推理。 1. 单调推理：在推理的过程中随着推理的向前推进以及新知识的加入，推出的结论呈

6、单调增加的趋势，并且越来越接近最终目标，在推理的过程中不会出现反复情况。2. 非单调推理：在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而否定了它，使得推理退回到前面的某一步，重新开始。 多是在知识不完全的情况下发生。 4. 启发式推理、非启发式推理 启发性知识是指与问题有关且能加快推理进程，求解问题最优解的知识。5 5. 基于知识的推理，统计推理，直觉推理 1. 基于知识的推理：根据掌握的事实，通过运用知识进行推理，例如：医生诊断疾病 2. 统计推理：根据对某事物的数据统计进行推理。例如:对农作物产量的统计，决定是否增产。 3. 直觉推理：根据常识进行的推理。 例如：走路时重物落

7、下，躲闪。4.1.3 推理的控制策略 推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。控制策略包括推理方向、搜索策略、冲突消解策略、求解策略、限制策略；而推理方法则是指在推理控制策略确定之后，在进行具体推理时所要采取的匹配方法或不确定性传递算法等方法。 推理方向用来确定推理的驱动方式，即是数据（证据）驱动或是目标驱动。所谓数据驱动即指推理过程从初始证据开始直到目标结束，而目标驱动则是指推理过程从目标开始进行反向推理，直到出现与初始证据相吻合的结果。 按照对推理方向的控制，推理可分为正向推理、反向推理、混合推理及双向推理四种情况。4.1 推理概述推理概述 推理的驱动方式(1) 正向

8、推理：又称数据驱动推理，向前链推理，模式制导推理，前件推理基本思想：1. 从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用的知识集KS2. 按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新的事实加入到数据库KB中，作为下一步推理的已知事实。正向推理逆向推理混合推理双向推理要求数据库知识库状态库推理机3. 再在知识库中选取可适用知识进行推理，直到求解所要求的解惑知识库中再无可用的知识为止。推理过程算法1. 将用户提供的初始已知事实进入数据库DB中2. 检查DB中是否已经包含了该问题的解，若有，则求解结束，成功推出，否则执行下一步。 3. 根据DB中的已知事

9、实，扫描知识库KB，检查KB中是否有可适用的知识，若有则转到4， 否则到64. 把KB中所有的适用知识都选出来，构成可适用的知识集KS5. 若KS不为空，则按某种冲突消解策略从中选出一条知识进行推理，并将推出的新知识加入DB中，转2；若KS空，转6.6. 询问用户是否可进一步补充新事实，若可以补充，则补充新的事实加入DB，然后转3， 否则表示求解不出，失败。 (2) 逆向推理： 又称目标驱动推理，逆向链推理，目标制导推理以及后件推理。1. 选定一个假设目标2. 寻找支持该假设的证据，若所需要的证据都能找到，则说明原假设是成立的，若无论如何都找不到所需要的证据，则说明原假设不成立。 算法描述1.

10、 提出要求证的目标（假设）2. 检查该目标是否已在数据库中，若在，该目标成立，成功推出推理。否则转 33. 判断目标是否有证据，若有，则咨询用户，否则转 44. 在知识库中寻找有可能导出该目标的知识，形成适用知识集合 KS，然后转下一步 55从 KS 中选出一条知识，并将知识适用的条件作为新的假设目标， 转 2. 逆向推理的优点：不必使用与目标无关的知识，目的性强，便于向用户提供解释。逆向推理的缺点：初始目标的选择有盲目性，若不符合要求，就需要多次提出假设，影响到系统效率。 (3) 混合推理：既具有正向推理又具有逆向推理。什么时候用混合推理？1. 已知的事实不充分2. 由正向推理推出的结论可信

11、度不3. 希望得到更多的知识开始正向推理需要逆向推理？以正向推理所得到的结果作为假设进行逆向推理还需要逆正？输出结果开始逆向推理需要正向推理？进行正向推理还需要逆向？输出结果NYYYNY(4) 双向推理：正向推理与逆向推理同时进行基本思想：一方面根据已知事实进行正向推理，单并不推到最终目标；另一方面从假设目标出发进行逆向推理，单并不推到原始事实，而是让他们中途相遇，即由正向推理所得到的中间结论恰好是逆向推理所要求的证据，这时推理可结束。 困难在于“碰头”的判断。 (5) 求解策略：是指推理只有一个解，还是求所有解以及最优解等。 (6) 限制策略：为了防止无穷推理过程，以及由于推理过程太长增加时

12、间以及空间的复杂性，可在控制策略中制定推理的限制条件， 以对推理的深度，宽度，时间，空间进行限制。4. 模式匹配(1) 模式匹配：指对两个指示模式（两个谓词公式，两个框架片段，两个语义网络片段）的比较与耦合，如果两者完全一致，或者虽不完全一致，但相似的程度在指定的限度内，称他们是可匹配的，否则称不可匹配的。 (2) 确定性匹配：是指两个指示模式完全一致，或经过变量代换以后变得完全一致。 (3) 不确定性匹配：指两个知识模式不完全一致，但从总体上看，它们的相似程度又落在规定的限度内。 无论是确定性匹配还是不确定性匹配，在进行匹配时都需啊要进行变量代换。5 . 推理的冲突消解策略 推理过程中的冲突

13、消解策略，就是确定如何从多条匹配规则中选出一条规则作为启用规则，将它用于当前的推理。 目前已有的多种冲突消解策略的基本思想都是对匹配的知识或规则进行排序，以决定匹配规则的优先级别，优先级高的规则将作为启用规则。常用排序方法有如下几种:(1)按针对性进行排序：有限选用针对性较强的产生式规则，因为它要求的条件较多，其结论一般更接近目标。 (2)按已知事实的新鲜性排序：我们把数据库中后生成的事实称为新鲜的事实，后生成的事实比先生成的事实具有较大的新鲜性。(1)逐个比较，看A，和B谁的新鲜事实多(2)A和B中最新鲜的事实，看谁最新鲜(3)A和B中最不新鲜的事实，那个最不新鲜(3)按匹配度排序(1)当两

14、个模式的相似程度达到预先规定的值时候，我们就认为它们是可可以匹配的哦(2)相似度又称为匹配度。3.1 推理概述推理概述 (4) 根据领域问题的特点排序1.当领域问题有固定的解题次序时，可按该次序排列相应的知识， 排在前面的知识优先被应用。 2.当一只某些产生式规则被应用后会明显有利于问题的求解时，就使这些产生式规则优先被使用。(5) 按上下文限制排序：把产生规则按它们所描述的上下文分为若干组，在不同条件下只能从相应的组中选取有关的产生式规则。 (6) 按冗余限制排序：一条产生式应用后，产生的冗余知识越多，则产生式有限度越低。 (7)按条件个数排序：如果有多条件产生式规则生成相同的结论，则要求条

15、件少的产生式规则优先。 4.2 自然演绎推理方法 自然演绎推理的概念 自然演绎推理是指从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。 假言三段论的基本形式为 PQ，QRPR 它表示如果谓词公式PQ和QR均为真，则谓词公式PR也为真。 假言推理可用下列形式表示 P，PQ Q它表示如果谓词公式P和PQ都为真，则可推得Q为真结论。例如：如果“X是金属，则X能导电”以及“铜是金属”可以推出“铜能导电”的结论拒取式的一般形式为 PQ，Q P它表示如果谓词公式PQ为真且Q为假，则可推得P为假的结论。例如，“如果下雨，则地上湿”以及“地上没湿”可以推出“没有下雨”2.4.2

16、 2.4.2 利用演绎推理解决问题利用演绎推理解决问题 在利用自然演绎推理方法求解问题时，一定要注意避免两种类型的错误：肯定后件的错误和否定前件的错误。 4.2 自然演绎推理方法 肯定后件的错误是指当PQ为真时，希望通过肯定后件Q为真来推出前件P为真。这显然是错误的推理逻辑，因为当 PQ及 Q为真时，前件 P既可能为真，也可能为假。 否定前件的错误是指当PQ为真时，希望通过否定前件P来推出后件Q为假。这也是不允许的，因为当PQ及P为假时，后件Q既可能为真，也可能为假。 4.2 自然演绎推理方法 1. A2.B3.A-C4.BC -D5.D -Q证明：Q为真。A, A-C=CB, C = BC

17、BC = DD, D -Q = Q4.3 归结推理方法 研究用计算机实现定理证明的机械化，已是人工智能研究的一个重要领域。对于定理证明问题，如果用一阶谓词逻辑表示的话，就是要求对前提P和结论Q证明PQ是永真的。然而，要证明这个谓词公式的永真性，必须对所有个体域上的每一个解释进行验证，这是极其困难的。为了化简问题，和数学上常采用的方法一样，我们考虑反证法。即，我们先否定逻辑结论Q，再由否定后的逻辑结论Q及前提条件P出发推出矛盾，即可证明原问题。1文字 ：原子谓词公式及其否定定义4.5：任何文字的析取式称为子句定义4.6: 不包含任何文字的子句称为空子句，记为NIL；空子句是永假的。2.由子句构成

18、的集合称为子句集，谓词公式构成子句集的步骤：1. 利用等价关系消去谓词公式中的 2. P Q = (P Q) v(P Q)4.3 归结推理方法 2. 利用下列等价关系把“”移动紧靠谓词的位置上(P) = P;(PQ) = P v Q(PvQ) = P Q(forall x)P = (exists x)P3. 重新命名变元名，使不同两次元素的变元有不同的名字4 . 消去存在量词5. 把全称量词移到公式的左边6. 利用等价关系7. 消去全称量词8. 对变量更名9. 消去合取，留下析取 斯克林范式 从前束形范式中消去全部存在量词所得到的公式即为Skolem范式，或称Skolem标准型。例如，如果用f

19、(x)代替上面前束形范式中的y即得到Skolem范式：( x) ( z)(P(x)F(f(x), z)Q(f(x), z)Skolem标准型的一般形式是( x1)( x2)( xn)M(x1,x2,xn)其中，M(x1,x2,xn)是一个合取范式，称为Skolem标准型的母式。3.5 归结推理方法 将谓词公式G化为Skolem标准型的步骤如下：（1） 消去谓词公式G中的蕴涵（）和双条件符号（ ），以AB代替AB，以(AB)(AB)替换AB。（2） 减少否定符号（）的辖域，使否定符号“”最多只作用到一个谓词上。（3） 重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。3.5

20、 归结推理方法 （4） 消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域内，此时，只要用一个新的个体常量替换该存在量词约束的变元，就可以消去存在量词；另一种情况是，存在量词位于一个或多个全称量词的辖域内，这时需要用一个Skolem函数替换存在量词而将其消去。（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。（6）母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的有限集组成的合取。 需要指出的是，由于在化解过程中，消去存在量词时作了一些替换，一般情况下，G的Skolem标准型与G并不等值。3.5 归结推理方法 定理4

21、.1不可满足意义下的一致性定理: 设有谓词公式G，而其相应的子句集为S，则G是不可满足的充分必要条件是S是不可满足的。 要再次强调：公式G与其子句集S并不等值，只是在不可满足意义下等价。 相关的例子参见教材中的例3.94PP1P2Pn的子句集 当PP1P2Pn时，若设P的子句集为SP，Pi的子句集为Si，则一般情况下，SP并不等于S1S2S3Sn，而是要比S1S2S3Sn复杂得多。但是，在不可满足的意义下，子句集SP与S1S2S3Sn是一致的，即 SP不可满足S1S2S3Sn不可满足4.3 归结推理方法 4.3.2 4.3.2 HerbrandHerbrand理论理论 1H域 定义3.20 设

22、谓词公式G的子句集为S，则按下述方法构造的个体变元域H。称为公式G或子句集S的Herbrand域，简称H域。（1） 令H0是S中所出现的常量的集合。若S中没有常量出现，就任取一个常量aD，规定H0=a。（2） 令Hi+1=HiS中所有的形如f(t1,tn)的元素其中f(t1,tn)是出现于G中的任一函数符号，而t1，tn是Hi中的元素。i=0，1，2，。 4.3 归结推理方法 例4.10 求子句集ST(x)Q(z),R(f(y)的H域。解 此例中没有个体常量，任意指定一个常量a作为个体常量；只有一个函数f(y)，有：H0=aH1=a,f(a)H2=a,f(a),f(f(a)H=a,f(a),f

23、(f(a),f(f(f(a),4.3 归结推理方法 2原子集定义3.21 下列集合称为子句集S的原子集： A所有形如P(t1, t2,tn)的元素其中，P(t1, t2,tn)是出现在S中的任一谓词符号，而t1，t2，tn则是S的H域上的任意元素。3.5 归结推理方法 定义3.22 将没有变元出现的原子、文字、子句和子句集分别称作基原子、基文字、基子句和基子句集。定义3.23 当子句集S中的某个子句C中的所有变元符号均以其H域中的元素替换时，所得到的基子句称作C的一个基例。 例如，对于子句集 SP(a),P(x)P(f(x) 它的H域为a,f(a),f(f(a),。 对于子句P(a)，因为其中

24、不含有变元，所以它已是基子句，而且aH，所以它也是基例。 3.5 归结推理方法 3H域上的解释定义3.24 如果子句集S的原子集为A，则对A中各元素的真假值的一个具体设定都是S的一个H解释。可以证明，在给定域D上的任一个解释I，总能在H域上构造一个解释I*与之对应，使得如果D域上的解释能满足子句集S，则在H域的解释I*也能满足S（即若S|I=T，就有S|I*=T）。相关举例参见教材3.5 归结推理方法 定理3.3 设I是子句集S在域D上的一个解释，则存在对应于I的H域解释I*，使得若有 S|I=T，就必有S|I*=T。定理3.4 子句集S不可满足的充要条件是S对H域上的一切解释都为假。 证明

25、充分性：若S在一般域D上是不可满足的，必然在H域上是不可满足的，从而对H域上的一切解释都为假。必要性：若S在任一H解释I*下均为假，必然会使S在D域上的每一个解释为假。否则，如果存在一个解释I0使S为真，那么依据定理3.3可知，一定可以在H域找到相对应的一个解释I*0使S为真。这与S在所有H解释下均为假矛盾。3.5 归结推理方法 定理3.5 子句集S不可满足的充分必要条件是存在一个有限的不可满足的基例集S。 该定理称为Herbrand定理，下面给出它的简要证明。证明 充分性：设子句集S有一个不可满足的基例集S，因为它不可满足，所以一定存在一个解释I使S为假。根据H域上的解释与D域上的解释的对应

26、关系，可知在D域上一定存在一个解释使S不可满足，从而证明了子句集S是不可满足的。3.5 归结推理方法 必要性：设子句集S不可满足，由定理3.4可知，S对H域上的所有解释均为假。这样，就至少会存在一个S中的某子句Ci的基例Ci为假。既然至少有一个基例Ci为假，因而S的基例集S是不可满足的。另外，由于S中的子句是有限的，而每个子句又由有限的文字组成，因而S的不可满足的基例集也是有限的。3.5 归结推理方法 3.5.3 3.5.3 归结原理归结原理定义3.25 若P是原子谓词公式或原子命题，则称P与P为互补文字。1命题逻辑中的归结原理归结与归结式 定义3.26 设C1与C2是子句集中的任意两个子句，

27、如果C1中的文字L1与C2中的文字L2互补，则从C1和C2中可以分别消去L1和L2，并将二子句中余下的部分做析取构成一个新的子句C12，称这一过程为归结，所得到的子句C12称为C1和C2的归结式，而称C1和C2为C12的亲本子句。3.5 归结推理方法 定理3.6 归结式C12是其亲本子句C1和C2的逻辑结论。推论 设C1和C2是子句集S上的子句，C12是C1和C2的归结式。如果把C12加入子句集S后得到新子句集S1，则S1和S在不可满足的意义下是等价的。即： S是不可满足的 S1是不可满足的 归结推理过程归结推理过程 子句集S不可满足性的推理过程如下： (1) 对子句集S中的各子句间使用归结推

28、理规则。 (2) 将归结所得的归结式放入子句集S中，得新子句集S。 (3) 检查子句集S中是否有空子句(NIL),若有则停止推理;否则转（4）。 (4) 置S=S，转步骤（1）。3.5 归结推理方法 2一阶谓词逻辑中的归结原理下面是谓词逻辑关于归结的定义。定义定义3.273.27 设C1和C2是两个没有相同变元的子句，L1 和L2分别是C1 和C2的文字，如果L1与 L2有mgu ，则把 C12 =( C1L1)(C2 L2)称作子句C1 和C2的一个二元归结式，而L1 和L2是被归结的文字。 为了说明的方便。将Ci和Li写成集合形式， 如P(x)Q(y)P(x),Q(y)。在集合的表示下做减

29、法或做并运算，然后再写成子句形，如集合运算结果为P(x),Q(y)，可改写为P(x)Q(y)。 3.5 归结推理方法 在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：（1）若被归结的子句C1 和C2中具有相同的变元时，需要将其中一个子句的变元更名，否则可能无法做合一置换。从而没有办法进行归结。 （2）在求归结式时，不能同时消去两个互补文字对，消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。（3）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的化简。 3.5 归结推理方法 应用因子的概念，可对谓词逻辑中的归结原理定义如下。 定义

30、3.28 设C1和 C2是没有相同变元的子句，则下列四种二元归结式都叫做C1和C2的归结式，仍记作C12。（1） C1与C2的二元归结式。（2） C1的因子C11与C2的二元归结式。（3） C1与C2的因子C22的二元归结式。（4） C1的因子C11与C2的因子C22的二元归结式。3.5 归结推理方法 例例 设C1=P(a)Q(x)R(x)，C2 =P(y)Q(b)， 求其二元归结式。解解 若选L1=P(a)，L2=P(y)，则L1和L2的mgu是=a/y，于是由定义3.27得C1和C2 的二元归结式为C12 =( C1-L1)(C2 -L2)=(P(a),Q(x),R(x)-P(a)(P(a

31、),Q(b)-P(a)=(Q(x),R(x)(Q(b)=Q(x)R(x)Q(b) 若选L1=Q(x)，L2=Q(b)，则二者的mgu=b/x， C12 =P(a)R(b)P(y)3.5 归结推理方法 3 3归结原理的完备性归结原理的完备性 对于一阶谓词逻辑，从不可满足的意义上说，归结原理是完备的。即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结推理过程；反之，若从子句集到空子句存在一个归结推理过程，则该子句集必是不可满足的。 3.5 归结推理方法 3.5.4 利用归结原理进行定理证明 应用归结原理进行定理证明的步骤如下：应用归结原理进行定理证明的步骤如下： 设要被证明的定理可用谓词

32、公式表示为如下的形式： A1A2AnB(1) 首先否定结论B，并将否定后的公式B与前提公式集组成如下形式的谓词公式： G= A1A2AnB(2) 求谓词公式G的子句集S。(3) 应用归结原理，证明子句集S的不可满足性，从而证明谓词公式G的不可满足性。这就说明对结论B的否定是错误的，推断出定理的成立。3.5 归结推理方法 例例 已知：A: (x)( y)(P(x,y)Q(y)( y)(R(y)T(x,y)B: ( x)R(x)( x)( y)(P(x,y)Q(y)求证：B是A的逻辑结论。证明证明 首先将A和B化为子句集(1)P(x,y)Q(y) R(f(x)(2)P(x,y)Q(y) T(x,f

33、(x) /(1)(2)为A(3)R(z)(4)P(a，b)(5)Q(b) /(3)(4)(5)为B3.5 归结推理方法 下面进行归结： （6） P(x,y)Q(y) （1）与（3）归结，=f(x)/z （7） Q(b) （4）与（6）归结，=a/x,b/y （8） NIL（空子句） （5）与（7）归结所以B是A的逻辑结论。3.5 归结推理方法 3.5.5 3.5.5 应用归结原理进行问题求解应用归结原理进行问题求解下面是利用归结原理求取问题答案的步骤：（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并与

34、一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。（3）把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与S1合并构成子句集S。3.5 归结推理方法 （4）对子句集S应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变ANSWER中的变元。（5）如果得到归结式ANSWER ，则问题的答案即在ANSWER谓词中。3.5 归结推理方法 例例 任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？解解 第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先

35、定义谓词。（1） 定义谓词：设Father(x,y)表示x是y的父亲。Brother(x,y)表示x和y是兄弟。3.5 归结推理方法 （2） 将已知事实用谓词公式表示出来。 F1 ：任何兄弟都有同一个父亲。 (x)(y)(z)(Brother(x,y)Father(z,x)Father(z,y) F2：John和Peter是兄弟。 Brother(John,Peter) F3： John的父亲是David。 Father(David, John)（3） 将它们化成子句集得： S1=Brother(x,y)Father(z,x)Father(z,y), Brother(John,Peter),

36、Father(David,John)3.5 归结推理方法 第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。 设Peter的父亲是u，则有：Father(u,Peter)。 将其否定与ANSWER作析取，得： G：Father(u,Peter)ANSWER(u)3.5 归结推理方法 第三步：将上述公式G化为子句集S2,并将S1和S2合并到S。 S2 =Father(u,Peter)ANSWER(u) S= S1S2将S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）Father

37、(David,John)。（4）Father(u,Peter)ANSWER(u)。3.5 归结推理方法 第四步：应用归结原理进行归结（5）Brother(John,y)Father(David,y) （1）与（3）归结 =David/z,John/x（6）Brother(John,Peter)ANSWER(David) （4）与（5）归结=David/u,Peter/y（7）ANSWER(David) （2）与（6）归结第五步：得到了归结式ANSWER(David)，答案即在其中，所以u=David。即Peter的父亲是David。3.5 归结推理方法 3.6 归结过程的控制策略归结过程的控制策略 3.6.1 3.6.1 引入控制策略引入控制策略1引入控制策略的原因 对子句集S进行归结时，首先要从子句集中找出可进行归结的一对子句进行归结。由于事先并不知道子句集中的哪两个子句可以进行归结，也不知道通过对哪些子句的归结可尽快得到空子句，所以就必须对子句集中的所有子句逐一进行比较，以对所有可能归结的子句对进行归结，并将归结式加入S中，再做第二层这样的归结，直到产生空子句