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