第三章 经典逻辑推理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章 经典逻辑推理,掌握内容,1,掌握谓词公式的概念及可满足性的定义，弄清置换与合一的概念，掌握求取最一般合一置换的方法,2,掌握归结原理及归结推理方法。掌握,Skolem,标准式和子句集的求取方法，理解谓词公式和子句集在不可满足意义下的一致性，弄懂,Herbrand,定理，掌握,H,域、原子集、,H,域上的解释求法，掌握命题逻辑和谓词逻辑中的归结原理,3,掌握利用归结原理进行定理证明的方法,掌握应用归结原理进行问题求解的方法,掌握归结过程中的控制策略,3.1,基本概念,1,3.2,自然演绎推理,2,3.3,归结演绎推理,3,3.4,与,/,或形演绎推理,4,3.1,基本概念,返回,3.1.1,什么是推理,按某种策略由已知判断推出另一判断的思维过程,推理,已知判断,包括已掌握的与求解问题有关的知识及关于问题的已知事实,推理的结论,由已知判断推出新判断,推理机,推理由程序程序实现，称为推理机,从一种判断推出另一种判断,3.1.2,推理方式及其分类,推理的基本任务,按判断推出的途径来划分,演绎推理,归结推理,默认推理,推理的分类,演绎推理,从全称判断推导出特称判断或单称判断的过程,三段论式,演绎推理,结论：由大前提推出的适合于小前提所示情况的新判断,小前提：关于所研究的具体情况或个别事实的判断,大前提：已知的一般性知识或假设,在任何情况下，由演绎推导出的结论都是蕴涵在大前提的一般性知识中,只要大前提和小前提是正确的，则由它们推出的结论必然是正确的,推理过程,归纳推理,从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理,归纳推理,完全归纳推理,不完全归纳推理,归纳推理,在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性,只考察了相应事物的部分对象就得出了结论,枚举归纳推理：,若已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此属性,类比推理：,在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种推理,默认推理,摆脱了需要知道全部事实才能进行推理的需求，使得在知识不完全的情况下也能进行推理,又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理,默认推理,推理,推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，真值位于真与假之间，命题的外延模糊不清,不确定性推理,确定性推理,推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或为假，没有第三种情况出现,按推理时所用知识的确定性来划分,推理,在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始,非单调推理,单调推理,在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况,按推理过程中推出的结论是否单调地增加,一个思维过程，即求解问题的过程,推理过程,推理的,控制策略,推理方向,搜索策略,冲突消解策略,求解策略,限制策略,3.1.3,推理的控制策略,3.1.3,推理的控制策略,正向推理,以已知事实作为出发点的一种推理，又称为数据驱动推理、前向链推理、模式制导推理及前件推理,逆向推理,以某个假设目标为出发点的一种推理，又称为目标驱动推理、逆向链推理、目标制导推理及后件推理,1.,推理方向,3.1.3,推理的控制策略,混合推理,已知的事实不充分。通过正向推理先把其运用条件不能完全匹配的知识都找出来，并把这些知识可导出的结论作为假设，然后分别对这些假设进行逆向推理,由正向推理推出的结论可信度不高,希望得到更多的结论,先正向再逆向,通过正向推理，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高 其可信度,先逆向再正向,先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论,3.1.3,推理的控制策略,双向推理,双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理。,正向推理所得的中间结论恰好是逆向推理此时要求的证据,3.1.3,推理的控制策略,2.,求解策略,推理是只求一个解还是求所有解以及最优解等,3.,限制策略,对推理的深度、宽度、时间、空间等进行限制,3.1.3,推理的控制策略,4.,冲突消解策略,在推理过程中，匹配会出现三种情况,已知事实可与知识库中的多个知识匹配成功；或者有多个（组）已知事实都可与知识库中某一知识匹配成功；或者有多个（组）已知事实可与知识库中的多个知识匹配成功,已知事实恰好只与知识库中的一个知识匹配成功,已知事实不能与知识库中的任何知识匹配成功,3.1.3,推理的控制策略,出现冲突的情况,逆向推理,:,如果有多条产生式的后件都和同一假设匹配成功，或者有多条产生式后件可与多个假设匹配成功,正向推理,:,如果有多条产生式规则的前件都和已知的事实匹配成功；或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功；或者两种情况同时出现,3.1.3,推理的控制策略,1,.,按就近原则排序,该策略把最近被使用过的规则赋予较高的优先级,2.,按已知事实的新鲜性排序,后生成的事实比先生成的事实具有较大的优先性,3.,按匹配度排序,根据匹配程度来决定哪一个产生式规则优先被应用,3.1.3,推理的控制策略,4.,按领域问题特点排序,按照求解问题领域的特点将知识排成固定的次序,5.,按上下文限制排序,根据当前数据库的已知事实与上下文的匹配情况确定,6.,按条件个数排序,将条件少的规则赋予较高的优先级，优先被启用,7.,按规则的次序排序,以知识库中预先存入规则的排列顺序作为知识排序的依据,3.1.4,模式匹配,模式匹配,指对两个知识模式的比较与耦合，即检查这两个知识是否完全一致或近似一致,模式匹配的分类,不确定性匹配,：两个知识模式不完全一致，但从整体上看，它们的相似程度落在规定的范围内,确定性匹配,：两个知识模式完全一致，或者经过变量代换后变得完全一致,3.1.4,模式匹配,定义,1,代换是形如,的有限集合。其中，是项，是变元；表示用 替换 ，不允许 与 相同，也不允许变元 循环出现在另一个 中,3.1.4,模式匹配,定义,2,设,是两个代换，则此两个代换的复合也是一个代换，它是从,中删去如下两种元素：,先删除,:,后删除,:,3.1.4,模式匹配,定义,3,设有公式集 ，若存在一个代换,使得,则称 为公式集,F,的一个合一，且称,是可合一的。,一个公式集的合一一般来说是不唯一的,。,3.1.4,模式匹配,定义,3,设 是公式集,F,的一个合一，如果对任一合一 都存在一个代换 ，使得,则称 是一个最一般的合一,最一般合一是唯一的。,3.1.4,模式匹配,1,2,找出 的差异集,3,4,5,令,若 只含有一个表达式，则算法停止,若 中存在元素 和 ，其中 是变元，是项，且 不在 中出现，则做（,5,），否则不可合一,令,最一般合一算法,3.2,自然演绎推理,返回,3.2.1,自然演绎推理的基本概念,自然演绎推理,从一组已知的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程,4,3,2,1,P,规则,：在推理的任何步骤上都可引入前提,T,规则,：推理时，如果前面步骤中有一个或多个公式永真蕴涵公式,S,，则可把,S,引入推理过程中。,CP,规则,：如果能从,R,和前提集合中推出,S,来，则可从前提集合推 出,来,反证法,：,当且仅当,假言推理,：,推理规则,拒取式推理,：,推理规则,3.2.1,自然演绎推理的基本概念,避免产生两类错误：,肯定后件,(Q),的错误,：,希望通过肯定后件,Q,推出前件,P,为真,否定前件,(P),的错误,：,希望通过否定前件,P,推出后件,Q,为假,3.2.2,利用演绎推理解决问题,例,设已知事实,（,1,）只要不怕困难的人，就会获得胜利。,（,2,）运动员都是不怕困难的人。,（,3,）王力是运动员。,求证：王力会获得胜利。,3.2.2,利用演绎推理解决问题,优点,缺点,定理证明过程自然，容易理解,拥有丰富的推理规则，推理过程灵活，,便于在它的推理规则中嵌入领域启发式知识,容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增,自然演绎推理的,优缺点,3.3,归结演绎推理,返回,3.3.1,子句,文字,原子谓词公式及其否定统称为文字,子句,任何文字的析取式称为子句,空子句,不包含任何文字的子句称为空子句,空子句中不包含任何文字，不能被任何解释满足，所以空子句是永假的，不可满足的,3.3.1,子句,消去存在量词,1,2,3,4,谓词公式化为子句集步骤,重新命名变元,利用等价谓词关系消去谓词公式中的“”和“”,利用等价关系把“”移到紧靠谓词,存在量词不出现在全称量词的辖域内，此时只要用一个新的个体常量替换该存在量词的约束变元可消去存在量词,存在量词位于一个或多个全称量词的辖域内,3.3.1,子句,把全称量词移到公式左边,8,7,6,5,谓词公式化为子句集步骤,消去全称量词,利用等价关系把公式化为,Skolem,标准形,9,对,变元更名,消去合取词,3.3.1,子句,定理：设有谓词公式,F,，其标准形的子句集为,S,，则,F,不可满足的充要条件是,S,不可满足。,Skolem,标准形的一般形式,3.3.2,海明伦理论,令 是,S,中所有个体常量的集合，若,S,中不包含个体常量，则令 ，其中,a,为任意指定的一个个体常量,令,1,2,H域,设,S,为子句集，则按下述方法构造的域称为海明伦域，简称为,H,域,下列集合称为子句集,S,的原子集：,其中，是出现在,S,中的任一谓词符号，而 是,S,在,H,域上的任意元素。,3.3.2,海明伦理论,原子集,3.3.2,海明伦理论,H域上的解释,子句集,S,在,H,域上的解释就是对,S,中出现的常量、函数及谓词取值，一次取值就是一个解释。,子句集,S,在,H,域上的一个解释,I,满足下列条件：,在解释下，常量映射到自身,S,中的任一个,n,元函数是 的映射,S,中的任一个,n,元谓词是 的映射。谓词的真值可以指派为,T,，也可以指派为,F,1,2,3,子句集不可满足的充要条件是在一个有限的不可满足的基子句集,3.3.2,海明伦理论,子句集,S,不可满足的充要条件是,S,对,H,域上的一切解释都为假。,定理,可证明，对给定域,D,上的任何一个解释，总能在,H,域上构造一个解释与它对应，如果,D,域上的解释能满足子句集,S,，则在,H,域上相应解释也能满足,S,。,定理,3.3.3,鲁宾逊归结原理,鲁宾逊归结原理基本思想,检查子句集S中是否包含空子句，若包含，则S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句集，就说明子句集S是不可满足的。,互补文字,若,P,是原子谓词公式，则称 与 为互补文字,3.3.3,鲁宾逊归结原理,1,、命题逻辑中的归结原理,归结,设 与 是子句集中的任意两个子句，如果 中的文字 与 中的文字 互补，那么从 和 中分别消去 和 ，并将二个子句中余下的部分析取，构成一个新子句 ，则称这一过程为归结，称 为 和 的归结式，称 和 为 的亲本子句,3.3.3,鲁宾逊归结原理,归结式 是亲本子句 与 的逻辑结论。,定理,推论,1,推论,2,设 与 是子句集S中的两个子句，是它们的归结式，若把,加入S中，得到新子句集 ，则S与,在,不可满足的意义上是等价的，即,设 与 是子句集,S,中的两个子句，是它们的归结式，若用 代替 和 得到新子句集 ，则由 的不可满足性可推出原子句集,S,的不可满足性，即,设 与 是两个没有相同变元的子句，和 分别是 和 中的文字，若 是 和 的最一般合一，则称,为 和 的二元式，和 称为归结式上的文字,3.3.3,鲁宾逊归结原理,1,、谓词逻辑中的归结,定义,3.3.3,鲁宾逊归结原理,定义,子句 和 的归结式是下列二元归结式之一：,与 的二元归结式,与 的因子 的二元归结式,的因子 与 的二元归结式,的因子 与 的因子 的二元归结式,3.3.4,归结策略,删除策略,通过删除某些无用的子句来缩小归结的范围,归结策略,限制策略,通过对参加归结的子句进行种种限制，尽可能地减小归结的盲目性，使其尽快地归结出空子句。,3.3.4,归结策略,把,纯文字,所在的子句从子句集中删去,从子句集中删除重言式,删除策略,包孕删除法,重言式删除法,纯文字删除法,3.3.4,归结策略,限制策略,支持集策略,线性输入策略,祖先过滤形策略,单文字子句策略,3.3.5,使用归结原理证明问题,1,2,3,否定,G,，,得到,把 并入到公式集,F,中，得到,F,把公式集,F,化为子句集,S,4,反复归结子句集,S,中的子句，若出现了空子句，则停止归结，此时就证明了,G,永真,设,F,为已知前提的公式集，,G,为目标公式（结论），用归结反演证明,Q,为真的步骤是：,3.3.5,使用归结原理证明问题,例,某公司招聘工作人员，,A,、,B,、,C,三人应试，经面试后公司表示如下想法：,(1),三人中至少录取一人,(2),如果录取,A,而不录取,B,，则一定录取,C,(3),如果录取,B,，则一定录取,C,求证：公司一定录取,C,3.3.5,使用归结原理证明问题,例,知以下的事实：,Marcus,是人。,Marcus,是罗马人。,Caser,是一位统治者。所有罗马人或忠于,Caser,或仇恨他。每个人都忠于某个人。人们只想暗杀他们不忠于的统治者。,Marcus,试图暗杀,Caser,。,求证：,Marcus,仇恨,Caser,。,3.3.5,应用归结原理求取问题的答案,例,设,A,、,B,、,C,三人中有人从不说真话，也有人从不说假话，某人向这三个人分别提出同一个问题：谁是说谎者？,A,答：“,B,和,C,都是说谎者”；,B,答“,A,和,C,都是说谎者”；,C,答：“,A,和,B,中至少有一个是说谎者。”求谁是老实人，谁是说谎者？,3.3.6,用归结原理求解问题,用归结原理求解问题,把已知前提用谓词公式表示出来，并且化为相应的子句集,S,把待求解的问题用谓词公式表示，把它否定并与谓词,ANSWER,构成析取式,若得到归结式,ANSWER,，则答案在,ANS,WER,中,对,S,应用归结原理进行归结,1,2,3,4,5,把此析取式化为子句集，并且把该子句集并入到子句集,S,中，得到子句集,S,3.4,与,/,或形演绎推理,返回,与,/,或形演绎推理,正向演绎,双向,演绎,逆向演绎,3.4.1,与,/,或形正向演绎推理,与,/,或形正向演绎推理,从已知事实出发，正向地使用蕴含式,(F,规则,),进行演绎推理，直至得到某个目标公式的一个终止条件为止。,3.4.1,与,/,或形正向演绎推理,事实表达式的与,/,或变换,1,2,3,4,消去公式中的“”；,把“”移到紧靠谓词的位置上,重新命名变元名,引入,Skolem,函数消去存在量词,5,消去全称量词，且使各主要合取式中的变元不同名,3.4.1,与,/,或形正向演绎推理,在与,/,或树中，每个节点表示相应事实表达式的一个子表达式，叶节点为谓词公式中的文字,对于用析取符号“”连接而成的表达式，用一个连接符把它们连接起来。,对于合取符号“”连接而成的表达式，无须用连接符连接,F,规则的表示形式,要求,F,规则具有如下形式：,其中,L,为单文字，,W,为与,/,或形,3.4.1,与,/,或形正向演绎推理,把领域知识的表示形式变成规定形式的步骤,把“”移到紧靠谓词的位置上,引入,Skolem,函数消去存在量词,消去全称量词,A,B,C,D,消去公式中的“”,恢复为蕴含式,E,3.4.1,与,/,或形正向演绎推理,用与,/,或树把已知事实表示出来,用,F,规则的左部和与,/,或树的叶节点进行匹配，并将匹配成功的,F,规则加入到与,/,或树中,重复第,(2),步，直到产生一个含有以目标节点作为终止节点的解图为止,推理过程,3.4.1,与,/,或形正向演绎推理,例,已知事实：,Fido,要么会犬叫和咬人，要么,Fido,就不是狗。,已知规则：所有,Terrier,都是狗；所有会犬叫的东西都是吵人的。,求证：存在某个东西，它要么不是,Terrier,，要么会吵人。,3.4.2,与,/,或形逆向演绎推理,与,/,或形逆向演绎推理,从待证明的问题,(,目标,),出发，通过逆向地使用蕴含式,(B,规则,),进行演绎推理，直到得到包含已知事实的终止条件为止,变换过程与正向演绎推理中的已知事实的变换相似,3.4.2,与,/,或形逆向演绎推理,B,规则的表示形式,B,规则的表示形式为 ，其中，,W,为任一与,/,或形公式；,L,为文字,3.4.2,与,/,或形逆向演绎推理,用与,/,或树把目标公式表示出来,用,B,规则的右部和与,/,或树的叶节点进行匹配，并将匹配成功的,B,规则加入到与,/,或树中,重复进行第,(2),步，直到产生某个终止在事实节点上的一致解图为止,推理过程,3.4.3,与,/,或形双向演绎推理,与,/,或形双向演绎推理,由表示目标及表示已知事实的两个与,/,或树结构组成，这些与,/,或树分别由正向演绎的,F,规则及逆向演绎的,B,规则进行操作，并且仍然限制,F,规则为单文字的左部，,B,规则为单文字的右部。,3.4.4,代换的一致性及剪枝策略,代换的一致性,设代换集合,中第,i,个代换 为,其中，为项，为变元，则代换集 是一致的充要条件是如下两个元组,可合一,3.4.4,代换的一致性及剪枝策略,剪枝策略的基本思想,每当选用一条规则时，就进行一次一致性检查，如果当前的部分解图是一致的，则继续向下扩展，否则就放弃该规则而选用其它候选规则。,Thank You!,开始,把初始已知事实送入,DB,DB,中包含问题的解？,KB,中可适用的知识？,把,KB,中所有适合知识选出来送入,KS,按冲突消解策略从,KS,中选出一条知识进行推理,将该新事实加入,DB,中,成功退出,将该新,事实加入,DB,中,失败退出,用户可补充新事实？,N,Y,Y,N,Y,N,推出的是新事实？,KS,空？,N,N,Y,Y,正向推理示意图,返回,返回,开始,提出假设,该假设在数据库中？,该假设是证据？,在,知识库中找出所有能导出该假设的知识，形成适用知识集,KS,该,假设成立，并将此事实存入数据库,该假设成立,退出,N,Y,Y,N,Y,N,从,KS,中选出一条知识，并将该知识 的一个运用条件作为新的假设目标,询问用户,还有假设？,有此事实？,N,Y,返回,开始,进行正向推理,需要逆向推理？,还需要正向推理？,以,正向推理所得结果作为假设进行逆向推理,该假设成立,退出,N,Y,N,Y,开始,进行逆向推理,需要正向推理？,还需要逆向推理？,进行正向推理,输出结果,退出,N,Y,N,Y,返回,