【人工智能_人工智能原理与应用】第三章经典逻辑推理.ppt

《【人工智能_人工智能原理与应用】第三章经典逻辑推理.ppt》由会员分享，可在线阅读，更多相关《【人工智能_人工智能原理与应用】第三章经典逻辑推理.ppt（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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.求解策略,推理是只求一个解还是求所有解以及最

5、优解等,3. 限制策略,对推理的深度、宽度、时间、空间等进行限制,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.

8、4 模式匹配,1,2,找出 的差异集,3,4,5,令,若 只含有一个表达式，则算法停止,若 中存在元素 和 ，其中 是变元， 是项，且 不在 中出现，则做（5），否则不可合一,令,最一般合一算法,3.2 自然演绎推理,3.2.1 自然演绎推理的基本概念,自然演绎推理,从一组已知的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程,推理规则,3.2.1 自然演绎推理的基本概念,避免产生两类错误：,肯定后件(Q)的错误： 希望通过肯定后件Q推出前件P为真,否定前件(P)的错误： 希望通过否定前件P推出后件Q为假,3.2.2 利用演绎推理解决问题,例,设已知事实 （1）只要不怕困难的人，

9、就会获得胜利。 （2）运动员都是不怕困难的人。 （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域,下列集合称为

11、子句集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上的任何一

12、个解释，总能在H域上构造一个解释与它对应，如果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

15、,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是一位统治者。所有罗马人或忠于

16、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构成析取式,若得到归结式ANSW

17、ER，则答案在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,消去全称量词，且使各主要合取式中的变元不同名

18、,3.4.1 与/或形正向演绎推理,在与/或树中，每个节点表示相应事实表达式的一个子表达式，叶节点为谓词公式中的文字 对于用析取符号“ ”连接而成的表达式，用一个连接符把它们连接起来。 对于合取符号“ ”连接而成的表达式，无须用连接符连接,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 与/或形逆向演

20、绎推理,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!,正向推理示意图,