《确定性推理》PPT课件.ppt

1,第3章 确定性推理,智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型，本章重点讨论前一种，不确定性推理放到下一章讨论。3.1 推理的基本概念3.2 推理的逻辑基础3.3 自然演绎推理3.4 归结演绎推理3.5 基于规则的演绎推理,2,3.1 推理的基本概念,3.1.1 什么是推理3.1.2 推理方法及其分类3.1.3 推理的控制策略及其分类3.1.4 正向推理3.1.5 逆向推理3.1.6 混合推理,3,3.1.1 什么是推理,推理的概念 是指按照某种策略从已知事实出发去推出结论的过程。推理所用的事实：初始证据：推理前用户提供的 中间结论：推理过程中所得到的 推理过程：由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。例如，医疗专家系统，专家知识保存在知识库中。推理开始时，先把病人的症状和检查结果放到综合数据库中，然后再从综合数据库的初始证据出发，按照某种策略在知识库中寻找，并使用知识，直到推出最终结论为止。推理的两个基本问题 推理的方法：解决前提和结论的逻辑关系，不确定性传递 推理的控制策略：解决推理方向，冲突消解策略,4,3.1.2 推理方法及其分类1.按推理的逻辑基础分类(1/4),可分为演绎推理、归纳推理等 演绎推理 演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论，如假言推理、拒取式和假言三段论。例：假言三段论 AB，BC AC 常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。例如，有如下三个判断：计算机系的学生都会编程序；（一般性知识）程强是计算机系的一位学生；（具体情况）程强会编程序。（结论）这是一个三段论推理。其中，是大前提，是小前提；是经演绎推出来的结论。可见，其结论是蕴含在大前提中的。,5,3.1.2 推理方法及其分类1.按推理的逻辑基础分类(2/4),归纳推理是一种由个别到一般的推理方法。归纳推理的类型 按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理 按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等 完全归纳推理 是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。不完全归纳推理 是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，计算机，随机抽查。枚举归纳推理 是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。例如，设有如下事例：王强是计算机系学生，他会编程序；高华是计算机系学生，她会编程序；当这些具体事例足够多时，就可归纳出一个一般性的知识：凡是计算机系的学生，就一定会编程序。,6,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)类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。,7,3.1.2 推理方法及其分类 1.按推理的逻辑基础分类(4/4),演绎推理与归纳推理的区别 演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。例如，一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种归纳推理方式。运用这些一般性知识知识去维修计算机的过程则是演绎推理。,8,3.1.3 推理的控制策略及其分类,推理的控制策略 推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略。推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。控制策略的分类 由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。推理策略 主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等 推理方向控制策略用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理。求解策略是指仅求一个解，还是求所有解或最优解等。限制策略是指对推理的深度、宽度、时间、空间等进行的限制。冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。搜索策略 主要解决推理线路、推理效果、推理效率等问题。本章主要讨论推理策略，至于搜索策略将放到第4章单独讨论。,9,3.1.4 正向推理推理算法,从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。算法描述(1)把用户提供的初始证据放入综合数据库；(2)检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；(3)检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。(4)按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转(2)。(5)询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转(3)；否则表示无解，失败退出。至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。其流程图如下：,10,把初始证据放入DB,DB中有解吗？,KB中有可用知识吗？,形成可用知识集,可用知识集空吗？,按照冲突消解策略从该知识集中选出一条知识进行推理,推出的是新事实吗？,将新事实加入到DB,把用户补充的新事实加入到DB中,用户可补充新事实吗？,失败退出,成功退出,Y,N,N,Y,N,N,N,Y,Y,Y,11,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得证。,12,3.1.4 正向推理优缺点,正向推理的主要优点 比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。正向推理的主要缺点 推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。,13,3.1.5 逆向推理推理算法,从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。算法描述：(1)将要求证的目标（称为假设）构成一个假设集；(2)从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步；(3)检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一步；(4)将知识库中可以导出该假设的所有知识构成一个可用知识集；(5)检查可用知识集是否为空，若是，失败退出；否则执行下一步；(6)按冲突消解策略从可用知识集中取出一个知识，继续；(7)将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。其流程图如下：,14,初始化DB和假设集,该假设是DB中的事实吗？,该假设能被KB中的知识导出吗？,从假设集中取出一个假设,可用知识集空吗？,按照冲突消解策略从该知识集中选出一条知识,将该知识前提中的每个子条件作为新的假设加入假设集,该假设成立并放入DB,还有新的假设吗？,失败退出,成功退出,Y,N,Y,Y,N,N,N,N,Y,将KB中所有能导出此假设的知识构成一个可用知识集,询问用户有此事实吗？,该假设 成立,Y,15,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得证。,16,3.1.5 逆向推理优缺点,逆向推理的主要优点 不必寻找和使用那些与假设目标无关的信息和知识 推理过程的目标明确 也有利于向用户提供解释，在诊断性专家系统中较为有效。逆向推理的主要缺点 当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。,17,3.1.6 混合推理,混合推理的概念 把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。混合推理的方法 1.先正向后逆向 这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。2.先逆向后正向 这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。3.双向混合 是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。对于这些方法我不再详细讨论。,18,第3章 确定性推理,3.1 推理的基本概念3.2 推理的逻辑基础3.3 自然演绎推理3.4 归结演绎推理3.5 基于规则的演绎推理,19,3.2 推理的逻辑基础,3.2.1 谓词公式的解释3.2.2 谓词公式的永真性和可满足性3.2.3 谓词公式的等价性和永真蕴含性3.2.4 谓词公式的范式3.2.5 置换与合一,20,3.2.1 谓词公式的解释概念,命题公式的解释 在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。有了命题公式的解释，就可据此求出该命题公式的真值。谓词公式的解释 由于谓词公式中可能包含由个体常量、变元或函数，因此，必须先考虑这些个体常量和函数在个体域上的取值，然后才能根据它们的具体取值为谓词分别指派真值。定义3.1 设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值：(1)为每个个体常量指派D中的一个元素；(2)为每个n元函数指派一个从Dn到D的一个映射，其中 Dn=(x1,x2,xn)|x1,x2,xnD(3)为每个n元谓词指派一个从Dn到F，T的映射。则称这些指派为P在D上的一个解释I,21,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。,22,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种解释，这里就不在一一列举。,23,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。,24,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永假。谓词公式的永假性又称不可满足性或不相容。后面我们要给出的归结推理，就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。,25,3.2.3 谓词公式的等价性和永真蕴含性1.等价式(1/2),谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真蕴含式来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规则。谓词公式的等价式可定义如下：定义3.5 设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D 上是等价的。如果D是任意非空个体域，则称P与Q是等价的，记作PQ。,26,3.2.3 谓词公式的等价性和永真蕴含性 1.等价式(2/2),(1)双重否定律 P P(2)交换律(PQ)(QP)，(PQ)(QP)(3)结合律(PQ)R P(QR)(PQ)R P(QR)(4)分配律 P(QR)(PQ)(PR)P(QR)(PQ)(PR)(5)摩根定律(PQ)PQ(PQ)PQ(6)吸收律 P(PQ)P P(PQ)P(7)补余律 PP T,PP F(8)连词化归律 PQ PQ PQ(PQ)(QP)PQ(PQ)(QP)(9)量词转换律(x)P(x)(P)(x)P(x)(P)(10)量词分配律(x)(PQ)(x)P(x)Q(x)(PQ)(x)P(x)Q,27,3.2.3 谓词公式的等价性和永真蕴含性2.永真蕴含式,定义3.6 对谓词公式P和Q，如果PQ永真，则称P 永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提，记作P Q。常用的永真蕴含式如下：(1)化简式 PQ P，PQ Q(2)附加式 P PQ，Q PQ(3)析取三段论 P,PQ Q(4)假言推理 P,PQ Q(5)拒取式 Q,PQ P(6)假言三段论 PQ,QR PR(7)二难推理 PQ,PR,QR R(8)全称固化(x)P(x)P(y)其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。(9)存在固化(x)P(x)P(y)其中，y是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。,28,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范式，其化简方法也将在后面子句集的化简中讨论。,29,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)一致。这种寻找项对变元的置换，使谓词一致的过程叫做合一的过程。下面讨论置换与合一的有关概念与方法。,30,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。一个谓词公式的任何例示都是该公式的逻辑结论。,31,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,32,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的任一个合一都存在一个置换，使得=，则称是一个最一般合一。一个公式集的最一般合一是唯一的。对如何求取最一般合一的问题，不再讨论。,33,第3章 确定性推理,3.1 推理的基本概念3.2 推理的逻辑基础3.3 自然演绎推理3.4 归结演绎推理3.5 基于规则的演绎推理,34,3.3 自然演绎推理,自然演绎推理 从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括：假言推理 P,PQ Q 拒取式 Q,PQ P 假言三段论 PQ,QR PR 自然演绎推理的例子 例3.5 设已知如下事实：A,B,AC,BCD,DQ 求证：Q为真。证明：因为 A,AC C 假言推理 B,C BC 引入合取词 BC，BCD D 假言推理 D,DQ Q 假言推理因此，Q为真,35,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这门课。,36,3.3 自然演绎推理,优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。,37,第3章 确定性推理,3.1 推理的基本概念3.2 推理的逻辑基础3.3 自然演绎推理3.4 归结演绎推理3.5 基于规则的演绎推理,38,3.4 归结演绎推理,归结演绎推理是一种基于鲁宾逊（Robinson）归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明PQ永真。由3.2节可知，要证明PQ永真，就是要证明PQ在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。为此，人们进行了大量的探索，后来发现可以采用反证法的思想，把关于永真性的证明转化为关于不可满足性的证明。即要证明PQ永真，只要能够证明PQ是不可满足的就可以了(原因是(PQ)(PQ)P Q。这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。,39,3.4 归结演绎推理,3.4.1 子句集及其化简3,4.2 鲁滨逊归结原理3.4.3 归结反演推理的归结策略3.4.4 用归结反演求取问题的答案,40,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 由子句或空子句所构成的集合称为子句集。,41,3.4.1 子句集及其化简2.子句集的化简（1/6）,在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下：(1)消去连接词“”和“”反复使用如下等价公式：PQ PQ PQ(PQ)(PQ)即可消去谓词公式中的连接词“”和“”。例如公式(x)(y)P(x,y)(y)(Q(x,y)R(x,y)经等价变化后为(x)(y)P(x,y)(y)(Q(x,y)R(x,y),42,3.4.1 子句集及其化简2.子句集的化简（2/6）,(2)减少否定符号的辖域反复使用双重否定率(P)P摩根定律(PQ)PQ(PQ)PQ量词转换率(x)P(x)(x)P(x)(x)P(x)(x)P(x)将每个否定符号“”移到仅靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。例如，上式经等价变换后为(x)(y)P(x，y)(y)(Q(x，y)R(x，y),43,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),44,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),45,3.4.1 子句集及其化简2.子句集的化简（5/6）,(6)化为Skolem标准形 Skolem标准形的一般形式为(x1)(xn)M(x1,x2,xn)其中，M(x1,x2,xn)是Skolem标准形的母式，它由子句的合取所构成。把谓词公式化为Skolem标准形需要使用以下等价关系 P(QR)(PQ)(PR)例如，前面的公式化为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),46,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(x,f(x)Q(x,g(x)P(y,f(y)R(y,g(y),47,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化为这种前束形是一种很容易实现的等价运算，因此这种假设是可以的。,48,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不可满足下面开始用反证法证明 F不可满足 F1不可满足,49,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)使(Qr+1xr+1)(Qnxn)M(x1,xr-1,f(x1,xr-1),xr+1,xn)为真。即在I下有(x1)(xr-1)(xr)(Qr+1xr+1)(Qnxn)M(x1,xr-1,xr,xr+1,xn)为真。即F在I下为真。但这与前提F是不可满足的相矛盾，即假设F1为可满足是错误的。从而可以得出“若F不可满足，则必有F1不可满足”。,50,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不可满足”于是，定理得证。由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。至于如何证明一个子句集的不可满足性，由下面的海伯伦理论和鲁宾逊归结原理来解决。,51,3.4.2 鲁滨逊归结原理1.基本思想,注意以下两个关键 第一，子句集中的子句之间是合取关系。因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的；第二，空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。鲁滨逊归结原理基本思想 首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S。然后设法检验子句集S是否含有空子句，若含有空子句，则表明S是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。鲁滨逊归结原理包括 命题逻辑归结原理 谓词逻辑归结原理,52,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=PQR，C2=PS，求C1和C2的归结式C12。解：这里L1=P，L2=P，通过归结可以得到 C12=QRS 例3.8 设C1=Q，C2=Q，求C1和C2的归结式C12。解：这里L1=Q，L2=Q，通过归结可以得到 C12=NIL,53,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 Q,P,Q,Q,NIL,54,3.4.2 鲁滨逊归结原理2.命题逻辑的归结（3/8）,定理3.2 归结式C12是其亲本子句C1和C2的逻辑结论。证明：（按定义）设C1=LC1，C2=LC2关于解释I为真，则只需证明C12=C1 C2关于解释I也为真。对于解释I，L和L中必有一个为假。若L为假，则必有C1为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1为真。同理，若L为假，则必有C2为真。因此，必有C12=C1C2关于解释I也为真。即C12是C1和C2的逻辑结论。,55,3.4.2 鲁滨逊归结原理2.命题逻辑的归结（4/8）,上述定理是归结原理中的一个重要定理，由它可得到以下两个推论：推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若用C12代替C1和C2后得到新的子句集S