第4章-确定性推理.ppt

第4章确定性推理,智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型，本章重点讨论前一种，不确定性推理放到下一章讨论。4.1推理的基本概念4.2推理的逻辑基础4.3自然演绎推理4.4归结演绎推理,4.1推理的基本概念,4.1.1什么是推理4.1.2推理方法及其分类4.1.3推理的控制策略及其分类,4.1.1什么是推理,推理的概念是指按照某种策略从已知事实出发去推出结论的过程。推理所用的事实：初始证据：推理前用户提供的中间结论：推理过程中所得到的推理过程：由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。推理的两个基本问题推理的方法：解决前提和结论的逻辑关系，不确定性传递推理的控制策略：解决推理方向，冲突消解策略,4.1.2推理方法及其分类,可分为演绎推理、归纳推理、默认推理演绎推理演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论。例：假言三段论AB，BCAC常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。,1.按推理的逻辑基础分类(1/5),例如：有如下三个判断：计算机系的学生都会编程序；（一般性知识）程强是计算机系的一位学生；（具体情况）程强会编程序。（结论）这是一个三段论推理。其中，是大前提，是小前提；是经演绎推出来的结论。可见，其结论是蕴含在大前提中的。,归纳推理是一种由个别到一般的推理方法。归纳推理的类型按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等完全归纳推理是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。不完全归纳推理是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，计算机，随机抽查。枚举归纳推理是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。,4.1.2推理方法及其分类,1.按推理的逻辑基础分类(2/5),例如：设有如下事例：王强是计算机系学生，他会编程序；高华是计算机系学生，她会编程序；当这些具体事例足够多时，就可归纳出一个一般性的知识：凡是计算机系的学生，就一定会编程序。,类比归纳推理是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。设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)类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。,4.1.2推理方法及其分类,1.按推理的逻辑基础分类(3/5),默认推理默认推理又被称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。例如：在条件A已成立的情况下，如果没有足够的证据能证明条件B不成立，则默认B是成立的，并在此默认的前提下进行推理，推导出某个结论。由于这种推理允许某些默认条件是成立的，这就摆脱了需要知道全部有关事实才能进行推理的束缚，使得推理在知识不完全的情况下也能进行。在默认推理中，如果到某一时刻发现原先所做的默认不正确，则要撤销所做的默认以及由此默认推出的所有结论，重新按新情况进行推理。,4.1.2推理方法及其分类,1.按推理的逻辑基础分类(4/5),演绎推理与归纳推理的区别演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。例如，一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种归纳推理方式。运用这些一般性知识知识去维修计算机的过程则是演绎推理。,4.1.2推理方法及其分类,1.按推理的逻辑基础分类(5/5),4.1.2推理方式及其分类,按推理过程中推出的结论是否单调地增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调推理。单调推理：在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理又回到前面的某一步。,2、单调推理、非单调推理(1/2),4.1.2推理方式及其分类,非单调推理：在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。注意：非单调推理是在知识不完全的情况下发生的。由于知识不完全，为使推理进行下去，就要先做某些假设，并在此基础上进行推理，当以后由于新知识的加入发现原先的假设不正确的时候，就需要推翻该假设以及基于此假设而推出的一切结论，再用新的知识重新进行推理。,2、单调推理、非单调推理(2/2),4.1.2推理方式及其分类,按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理。确定性推理（精确推理）：如果在推理中所用的知识都是精确的，即可以把知识表示成必然的因果关系，然后进行逻辑推理，推理的结论或者为真，或者为假，这种推理就称为确定性推理。如：在MYCIN中采用确定性方法是一种简单有效的方法，仅采用一些简单直观的证据合并规则，其缺点是缺乏良好的理论基础。,3、确定性推理、不确定性推理(1/3),4.1.2推理方式及其分类,按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理。不确定性推理（不精确推理）：在人类知识中，有相当一部分属于人们的主观判断，是不精确的和含糊的。由这些知识归纳出来的推理规则往往是不确定的。基于这种不确定的推理规则进行推理，形成的结论也是不确定的，这种推理称为不确定性推理。在专家系统中，主要使用的是不确定性推理。,3、确定性推理、不确定性推理(2/3),4.1.2推理方式及其分类,不确定性研究的重点可能会：一是：解决现有处理不确定性的理论中存在的问题；二是：大力研究人类高效、准确的识别能力和判断机智，开拓新的处理不确定性的理论和方法；三是：探索可以综合处理多种不确定性的放法和技术。,3、确定性推理、不确定性推理(3/3),4.1.2推理方式及其分类,按推理过程中推出的结论是否单调地增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调推理。单调推理：在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理又回到前面的某一步。,4、单调推理、非单调推理(1/2),4.1.2推理方式及其分类,按推理过程中推出的结论是否单调地增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调推理。非单调推理：在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。注意：非单调推理是在知识不完全的情况下发生的。由于知识不完全，为使推理进行下去，就要先做某些假设，并在此基础上进行推理，当以后由于新知识的加入发现原先的假设不正确的时候，就需要推翻该假设以及基于此假设而推出的一切结论，再用新的知识重新进行推理。,4、单调推理、非单调推理(2/2),4.1.2推理方式及其分类,如果按推理程中是否运用于问题有关的启发性知识，推理可分为启发式推理与非启发式推理。启发式推理：如果在推理过程中，运用了与问题有关的启发性知识，即解决问题的策略、技巧及经验，以加快推理过程，提高搜索效率，这种推理过程就被称为启发式推理。如第三章的A*、AO*等算法就属于此类推理。,5、启发式推理、非启发式推理(1/2),4.1.2推理方式及其分类,非启发式推理：如果在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理，这种推理过程就被称为非启发式推理。注意：这种推理缺乏对待求解问题的针对性，所以推理效率较低，容易出现组合爆炸问题。如图搜索策略头重的宽度优先搜索法，虽然是完备的算法，但是对复杂问题的求解，将出现组合爆炸现象，其搜索效率较低。,5、启发式推理、非启发式推理(2/2),4.1.3推理的控制策略,推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。1、推理方向推理方向用于确定推理的驱动方式，分为四种：正向推理逆向推理混合推理双向推理,4.1.3推理的控制策略,正向推理正向推理是从初始状态出发，使用规则，到达目标状态。又称为数据驱动推理、前向链推理、模式制导推理及前件推理。逆向推理逆向推理是以某个假设目标为出发点的一种推理，又称为目标驱动推理、逆向链推理、目标制导推理及后件推理。,4.1.3推理的控制策略,混合推理已知的事实不充分。通过正向推理先把其运用条件不能完全匹配的知识都找出来，并把这些知识可导出的结论作为假设，然后分别对这些假设进行逆向推理。推理的形式：先正向再逆向，通过正向推理，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度。先逆向再正向，先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。,4.1.3推理的控制策略,双向推理双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理。正向推理所得的中间结论恰好是逆向推理此时要求的证据2、求解策略推理是只求一个解还是求所有解以及最优解等3、限制策略对推理的深度、宽度、时间、空间等进行限制,4.1.3推理的控制策略,4、冲突消解策略在推理过程中，匹配会出现三种情况：已知事实不能与知识库中的任何知识匹配成功已知事实恰好只与知识库中的一个知识匹配成功已知事实可与知识库中的多个知识匹配成功；或者有多个（组）已知事实都可与知识库中某一知识匹配成功；或者有多个（组）已知事实可与知识库中的多个知识匹配成功,4.1.3推理的控制策略,4、冲突消解策略出现冲突的情况对正向推理而言，如果有多条产生式规则的前件都和已知的事实匹配成功；或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功；或者两种情况同时出现对逆向推理而言，如果有多条产生式的后件都和同一假设匹配成功，或者有多条产生式后件可与多个假设匹配成功。,4.1.3推理的控制策略,冲突消解策略按就近原则排序该策略把最近被使用过的规则赋予较高的优先级。按已知事实的新鲜性排序一般我们认为新鲜事实是对旧知识的更新和改进，比老知识更有效，即后生成的事实比先生成的事实具有较大的优先性。,4.1.3推理的控制策略,冲突消解策略按匹配度排序在不确定推理时，匹配度不仅可确定两个知识模式是否可匹配，还可用于冲突消解。根据匹配程度来决定哪一个产生式规则优先被应用。按领域问题特点排序该方法按照求解问题领域的特点将知识排成固定的次序,4.1.3推理的控制策略,冲突消解策略按上下文限制排序该策略将知识按照所描述的上下文分成若干组，在推理过程中根据当前数据库中的已知事实与上下文的匹配情况，确定选择某组中的某条知识。按条件个数排序多条规则生成的结论相同的情况下，由于条件个数较少的规则匹配所花费的时间较少而且容易实现，所以将条件少的规则赋予较高的优先级，优先被启用。,4.1.3推理的控制策略,冲突消解策略按规则的次序排序该策略是以知识库中预先存入规则的排列顺序作为知识排序的依据，排在前面的规则具有较高的优先级。,第4章确定性推理,4.1推理的基本概念4.2推理的逻辑基础4.3自然演绎推理4.4归结演绎推理,4.2推理的逻辑基础,4.2.1谓词与个体4.2.2谓词公式的永真性和可满足性4.2.3置换与合一,4.2.1谓词与个体,在谓词逻辑中，可以将原子命题分解为谓词与个体两部分。个体：是指可以独立存在的物体，可以是抽象的或具体的。谓词：则用于刻画个体的性质、状态或个体间的关系。例如：“李白是诗人”可表示为poet(LiBai)，poet称为谓词，用以刻画“是诗人”；LiBai称为个体。,4.2.1谓词与个体,一元谓词：一个谓词，可以与一个个体相关联，这种谓词称作一元谓词，它刻画了个体的性质。多元谓词：一个谓词，可以与多个个体相关联，这种谓词称作多元谓词，它刻画了个体间的关系。谓词的一般形式可表示为：P(x1,x2,xn)其中P是谓词，而x1,x2,xn是个体。谓词通常用大写字母表示，个体通常用小写字母表示。,4.2.1谓词与个体,注意事项：谓词的项：在谓词中，个体可以是常量，也可以是变量，还可以是一个函数。例如：“小刘的哥哥是个个人”，可以表示为worker(brother(Liu)，其中brother(Liu)是一个函数。个体常量、变量和函数统称为项。谓词的语义：由使用者根据需要人为地定义。谓词的元数：谓词中包含的个体变量的数目称为谓词的元数。,4.2.1谓词与个体,注意事项：谓词的阶数：在谓词P(x1,x2,xn)中，若xi(i=1,2,n)都是个体常量、变量或函数，则称它为一阶谓词。若某个xi本身又是一个一阶谓词，则称它为二阶谓词，依次类推。谓词与函数的区别：谓词具有逻辑值“真”或“假”，而函数则是某个个体到另一个个体（数学上：自变量到因变量）之间的映射。,4.2.2谓词公式的永真性和可满足性,定义4.1设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值：(1)为每个个体常量指派D中的一个元素；(2)为每个n元函数指派一个从Dn到D的一个映射，其中Dn=(x1,x2,xn)|x1,x2,xnD(3)为每个n元谓词指派一个从Dn到F，T的映射。则称这些指派为P在D上的一个解释。,1、谓词公式的解释,例4.1设个体域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。,4.2.2谓词公式的永真性和可满足性,1、谓词公式的解释,说明：一个谓词公式在其个体域上的解释不是唯一的。例如，对公式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种解释，这里就不在一一列举。,4.2.2谓词公式的永真性和可满足性,定义4.2如果谓词公式P对非空个体域D上的任一解释都取得真值T，则称P在D上是永真的；如果P在任何非空个体域上均是永真的，则称P永真。可见，要判定一谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就很难判定了。,4.2.2谓词公式的永真性和可满足性,2、谓词公式的永真性,定义4.3如果谓词公式P对非空个体域D上的任一解释都取假值F，则称P在D上是永假的；如果P在任何非空个体域上均是永假的，则称P永假。谓词公式的永假性又称不可满足性或不相容。,4.2.2谓词公式的永真性和可满足性,2、谓词公式的永真性,定义4.4对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的。谓词公式的可满足性也称为相容性。按照定义4.4，对谓词公式P，如果不存在任何解释，使得P的取值为T，则称公式P是不可满足的。所以谓词公式P的永假与不可满足是等价的。后面我们要给出的归结推理，就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。,4.2.2谓词公式的永真性和可满足性,3、谓词公式的可满足性,谓词公式的等价式可定义如下：定义4.5设P与Q是D上的两个谓词公式，D是它们共同的个体域。若对D上的任意解释，P与Q的取值都相同，则称公式P与Q在域D上是等价的。如果D是任意非空个体域，则称P与Q是等价的。记作：PQ。,4.2.2谓词公式的永真性和可满足性,4、谓词公式的等价性与永真蕴含,双重否定律(doublenegationlaw):(P(x)P(x)德摩根定律(Mogenlaw):(P(x)Q(x)P(x)Q(x)(P(x)Q(x)P(x)Q(x)逆否律(inverse-negationlaw):P(x)Q(x)Q(x)P(x)分配律(assignmentlaw):P(x)(Q(x)R(x)(P(x)Q(x)(P(x)R(x)P(x)(Q(x)R(x)(P(x)Q(x)(P(x)R(x),附1：谓词演算的基本等价式,4.2.2谓词公式的永真性和可满足性,结合律(associationlaw):（P(x)Q(x)R(x)P(x)(Q(x)R(x)（P(x)Q(x)R(x)P(x)(Q(x)R(x)蕴含等价式(implicationlaw):P(x)Q(x)P(x)Q(x)易名规则(renamelaw):xP(x)xQ(x)xP(x)yQ(y)量词转换律(quantifiertransformlaw):xP(x)xP(x)xP(x)xP(x),附1：谓词演算的基本等价式,4.2.2谓词公式的永真性和可满足性,量词分配律(quantifierassignmentlaw):x(P(x)Q(x)xP(x)xQ(x)x(P(x)Q(x)xP(x)xQ(x)x(PQ(x)PxQ(x)x(PQ(x)PxQ(x)量词交换律(quantifiercommutativelaw):xy(P(x,y)yx(P(x,y)xy(P(x,y)yx(P(x,y)xy(P(x,y)yx(P(x,y)xy(P(x,y)yx(P(x,y),附1：谓词演算的基本等价式,4.2.2谓词公式的永真性和可满足性,量词辖域变换等价式:xP(x)Qx(P(x)Q)xP(x)Qx(P(x)Q)xP(x)Qx(P(x)Q)xP(x)Qx(P(x)Q)Q中不含变量,附1：谓词演算的基本等价式,4.2.2谓词公式的永真性和可满足性,全称量词消去规则:xP(x)P(y)全称量词引入规则:P(y)xP(x)存在量词消去规则:xQ(x)Q(c)(c为常量)存在量词引人规则:Q(c)xQ(x)有限域量词消去规则:设有限个体域为Dd1,d2,dnxP(x)P(d1)P(d2),P(dn)xQ(x)Q(d1)Q(d2),Q(dn),附2：量词消去及引入规则,4.2.2谓词公式的永真性和可满足性,定义4.6对谓词公式P和Q，如果PQ永真，则称P永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提。记作PQ。,4.2.2谓词公式的永真性和可满足性,4、谓词公式的等价性与永真蕴含,推理规则：P规则：在推理的任何步骤上都可引入前提。T规则：推理时，如果前面步骤中有一个或多个永真蕴含公式S，则可把S引入推理过程中。CP规则：如果能从R和前提集合中推出S来，则可从前提集合推出RS。反证法：PQ，当且仅当PQF，即Q为P的逻辑结论，当且仅当PQ是不可满足的。,由此得到如下定理：定理4.1：Q为P1,P2,Pn的逻辑结论，当且仅当（P1P2Pn)Q是不可满足的。,常用的永真蕴含式如下：(1)化简式PQP，PQQ(2)附加式PPQ，QPQ(3)析取三段论P,PQQ(4)假言推理P,PQQ(5)拒取式Q,PQP(6)假言三段论PQ,QRPR(7)二难推理PQ,PR,QRR(8)全称固化(x)P(x)P(y)其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。(9)存在固化(x)P(x)P(y)其中，y是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。,4.2.2谓词公式的永真性和可满足性,4、谓词公式的等价性与永真蕴含,4.2推理的逻辑基础,4.2.1谓词与个体4.2.2谓词公式的永真性和可满足性4.2.3置换与合一,置换可简单的理解为是在一个谓词公式中用置换项去替换变量。定义4.7置换是形如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之间出现了循环置换现象。通常，置换是用希腊字母、等来表示的。不含任何元素的置换称为空置换，以表示。,4.2.3置换与合一,1、置换,(1)空置换是左么元和右么元，即对任意的置换,恒有(2)对任意表达式E，恒有E()(E)。(3)若对任意表达式E恒有EE，则。(4)对任意置换，,恒有即置换的合成满足结合律。(5)设A和B为表达式集合，则注意:置换的合成不满足交换律。,2、置换的性质,4.2.3置换与合一,3、置换乘法,定义4.8设=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)；当yjx1,x2,xn时，删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合。,4.2.3置换与合一,例4.2设=f(y)/x,z/y，=a/x,b/y,y/z，求与的合成。解:先求出集合f(y)/x,(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、置换乘法,4.2.3置换与合一,合一可理解为是寻找项对变量的置换，使两个谓词公式一致。可定义为：定义4.9设有公式集F=F1,F2,Fn，若存在一个置换，可使F1=F2=Fn，则称是F的一个合一。称F1,F2,Fn是可合一的。例4.3设有公式集F=P(x,y,f(y),P(a,g(x),z)，则=a/x,g(a)/y,f(g(a)/z是它的一个合一。一般来说，一个公式集的合一不是唯一的。,4、合一,4.2.3置换与合一,定义4.10设是公式集F的一个合一，如果对F的任一个合一都存在一个置换，使得=，则称是一个最一般合一(MGU)。一个公式集的最一般合一是唯一的。,5、最一般合一(MGU,MostGeneralUnifier),4.2.3置换与合一,6、MGU算法,4.2.3置换与合一,定义4.11表达式的非空集合W的差异集(differenceset)是按下述方法得出的子表达式的集合：（1）在W的所有表达式中找出对应符号不全相同的第一个符号(自左算起)。（2）在W的每个表达式中，提取出占有该符号位置的子表达式。这些子表达式的集合便是W的差异集D。,例4.4：W=P(x,f(y,z),P(x,a),P(x,g(h(k(x),在W的3个表达式中，前4个符号-“P(x,”是相同的，第5个符号不全相同，所以W的不一致集合(差异集)为:f(y,z),a,g(h(k(x).,假设D是W的差异集，显然有下面的结论。(1)若D中无变量符号，则W是不可合一的。例：(2)若D中只有一个元素，则W是不可合一的例：(3)若D中有变量符号x和项t，且x出现在t中，则W是不可合一的。例：,4.2.3置换与合一,(1)置。(2)若Wk中只有一个元素，终止，并且为W的最一般合一。否则求出Wk的差异集Dk。(3)若Dk中存在元素vk和tk，并且vk是不出现在tk中的变量，则转向第(4)步。否则终止，并且W是不可合一的。(4)置(注意：)(5)置k=k+1，转向第(2)步。,4.2.3置换与合一,6、MGU算法,第4章确定性推理,4.1推理的基本概念4.2推理的逻辑基础4.3自然演绎推理4.4归结演绎推理,4.3自然演绎推理,自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括：假言推理P,PQQ拒取式Q,PQP假言三段论PQ,QRPR,4.3自然演绎推理,避免两类错误：肯定后件的错误和否定前件的错误。肯定后件的错误：当PQ为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。原因是指当PQ及Q为真时，前件P既可能为真，也可能为假。否定前件的错误：当PQ为真时，希望通过否定前件P为假来推出后件Q为假，这也是不允许的。原因是指当PQ及P为假时，后件Q既可能为真，也可能为假。,4.3自然演绎推理,自然演绎推理的例子例4.5设已知如下事实：A,B,AC,BCD,DQ求证：Q为真。证明：因为A,ACC假言推理B,CBC引入合取词BC，BCDD假言推理D,DQQ假言推理因此，Q为真,4.3自然演绎推理,例4.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),4.3自然演绎推理,例4.6设已知如下事实：(1)只要是需要编程序的课，王程都喜欢。(2)所有的程序设计语言课都是需要编程序的课。(3)C是一门程序设计语言课。求证：王程喜欢C这门课。,应用推理规则进行推理：Lang(y)Prog(y)全称固化Lang(C)，Lang(y)Prog(y)Prog(C)假言推理C/yProg(C),Prog(x)Like(Wang,x)Like(Wang,C)假言推理C/x因此，王程喜欢C这门课。,4.3自然演绎推理,优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。,第4章确定性推理,4.1推理的基本概念4.2推理的逻辑基础4.3自然演绎推理4.4归结演绎推理,4.4归结演绎推理,归结演绎推理是一种基于鲁宾逊（Robinson）归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明PQ永真。由4.2节可知，要证明PQ永真，就是要证明PQ在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。为此，人们进行了大量的探索，后来发现可以采用反证法的思想，把关于永真性的证明转化为关于不可满足性的证明。即要证明PQ永真，只要能够证明PQ是不可满足的就可以了(原因是(PQ)(PQ)PQ。这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。,4.4归结演绎推理,4.4.1子句集及其化简4.4.2鲁滨逊归结原理4.4.3归结反演推理的归结策略4.4.4用归结反演求取问题的答案,4.4.1子句型,定义4.11原子谓词公式及其否定统称为文字。例如，P(x)、Q(x)、P(x)、Q(x)等都是文字。定义4.12任何文字的析取式称为子句。例如，P(x)Q(x)，P(x，f(x)Q(x，g(x)都是子句。定义4.13不含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句一般被记为或NIL。定义4.14由子句或空子句所构成的集合称为子句集。,1.子句与子句集,在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下：(1)消去连接词“”和“”反复使用如下等价公式：PQPQPQ(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),4.4.1子句型,2.子句集的化简(1/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),2.子句集的化简(2/6),4.4.1子句型,(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),2.子句集的化简(3/6),4.4.1子句型,(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),4.4.1子句型,2.子句集的化简(4/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),4.4.1子句型,2.子句集的化简(5/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),4.4.1子句型,2.子句集的化简(6/6),例4.7将合式公式化为子句形。解：（1）消去蕴涵符号：这可以利用等价式：得到：x(P(x)yP(y)P(f(x,y)yQ(x,y)P(y)（2）减少否定符号的辖域，把“”移到紧靠谓词的位置上：这可以利用下述等价式：,例题分析,得到：x(P(x)yP(y)P(f(x,y)yQ(x,y)P(y)（3）变量标准化：重新命名变元名，使不同量词约束的变元有不同的名字：xP(x)yP(y)P(f(x,y)wQ(x,w)P(w)（4）消去存在量词：xP(x)yP(y)P(f(x,y)Q(x,g(x)P(g(x),（5）化为前束形：xyP(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)（6）把母式化为合取范式：xyP(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)（7）消去全称量词和合取连接词：P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),（8）更改变量名，有时称为变量分离标准化。于是有：必须指出:一个子句内的文字可以含有变量，但这些变量总是被理解为全称量词量化了的变量。,在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此化简后的标准子句集是不唯一的。这样，当原谓词公式为非永假时，它与其标准子句集并不等价。但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。这个结论很重要，是归结原理的主要依据，可用定理的形式来描述。定理4.1设有谓词公式F，其标准子句集为S，则F为不可满足的充要条件是S为不可满足的。,3.子句集的应用,4.4.1子句型,作业：,习题：4.4,4.4.2鲁滨逊归结原理,首先注意以下两个关键问题：第一，子句集中的子句之间是合取关系。因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的；第二，空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。,鲁滨逊归结原理基本思想首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S。然后设法检验子句集S是否含有空子句，若含有空子句，则表明S是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。鲁滨逊归结原理包括命题逻辑归结原理谓词逻辑归结原理,4.4.2鲁滨逊归结原理1.基本思想,(1)归结式的定义及性质定义4.15若P是原子谓词公式，则称P与P为互补文字。定义4.16设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。例4.7设C1=PQR，C2=PS，求C1和C2的归结式C12。解：这里L1=P，L2=P，通过归结可以得到C12=QRS,4.4.2鲁滨逊归结原理2.命题逻辑的归结（1/8）,(1)归结式的定义及性质定理4.3归结式C12其亲本子句C1和C2的逻辑结论。这个定理是归结原理中一个重要定理，由它可得到如下两个推论：推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的的归结式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即：,S1的不可满足性S的不可满足性,4.4.2鲁滨逊归结原理2.命题逻辑的归结（2/8）,(1)归结式的定义及性质定理4.3归结式C12其亲本子句C1和C2的逻辑结论。这个定理是归结原理中一个重要定理，由它可得到如下两个推论：推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的的归结式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即：,S2的不可满足性S的不可满足性,4.4.2鲁滨逊归结原理2.命题逻辑的归结（3/8）,由此得到下列结论：为证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入到子句集S中；或者用归结式代替它的亲本子句，然后对新的子句集证明其不可满足性就可以了。如果经归结得到空子句，根据空子句的不可满足性，即可得到原子句集S是不可满足的结论。在命题逻辑中，对不可满足的子句集S，其归结原理是完备的。这种不可满足性可用如下定理描述：定理4.4子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。,4.4.2鲁滨逊归结原理2.命题逻辑的归结（4/8）,例4.9设设C1=PQ，C2=Q，C3=P，求C1、C2、C3的归结式C123。解：若先对C1、C2归结，可得到C12=P然后再对C12和C3归结，得到C123=NIL如果改变归结顺序，同样可以得到相同的结果，即其归结过程是不唯一的。其归结归结过程可用右图来表示，该树称为归结树。,PQ,Q,P,P,NIL,PQ,P,Q,Q,NIL,4.4.2鲁滨逊归结原理2.命题逻辑的归结（5/8）,(2)命题逻辑的归结反演归结原理：假设F为已知前提，G为欲证明的结论，归结原理把证明G为F的逻辑结论转化为证明FG为不可满足。再根据定理4.3，在不可满足的意义上，公式集FG与其子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足。应用归结原理证明定理的过程称为归结反演。,4.4.2鲁滨逊归结原理2.命题逻辑的归结（6/8）,命题逻辑归结反演的步骤：在命题逻辑中，已知F，证明G为真的归结反演过程如下：否定目标公式G，得G;把G并入到公式集F中，得到F，G；把F，G化为子句集S。应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。,4.4.2鲁滨逊归结原理2.命题逻辑的归结（7/8）,例4.10设已知的公式集为：P,(PQ)R,(ST)Q,T求证结论R。解：假设结论R为假,将R加入公式集，并化为子句集S=P,PQR,SQ,TQ,T,R其归结过程如右图的归结演绎树所示。该树根为空子句。其含义为：先假设子句集S中的所有子句均为真，即原公式集为真,R也为真；然后利用归结原理，对子句集进行归结，并把所得的归结式并入子句集中；重复这一过程，最后归结出了空子句。根据归结原理的完备性，可知子句集S是不可满足的，即开始时假设R为真是错误的，这就证明了R为真。,PQR,R,PQ,P,Q,TQ,T,T,NIL,4.4.2鲁滨逊归结原理2.命题逻辑的归结（8/8）,4.4.2鲁滨逊归结原理3.谓词逻辑的归结（1/20）,在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一（MGU)对变元进行代换，然后才能进行归结。可见，谓词逻辑的归结要比命题逻辑的归结麻烦一些。,谓词逻辑的归结原理：谓词逻辑中的归结式可用如下定义来描述：定义4.17设C1和C2是两个没有公共变元的子句，L1和L2分别是C1和C2中的文字。如果L1和L2存在最一般合一，则称C12=(C1-L1)(C2-L2)为C1和C2的二元归结式，而L1和L2为归结式上的文字。,4.4.2鲁滨逊归结原理3.谓词逻辑的归结（2/20）,谓词逻辑归结举例：例4.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),4.4.2鲁滨逊归结原理3.谓词逻辑的归结（3/20）,谓词逻辑归结举例：例4.12设C1=P(x)Q(a)，C2=P(b)R(x)，求C12解：由于C1和C2有相同的变元x，不符合定义4.17的要求。为了进行归结，需要修改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),4.4.2鲁滨逊归结原理3.谓词