您好、欢迎来到现金彩票网!
当前位置:如意彩票 > 非单调推理 >

人工智能第四章-基推理技术pdf

发布时间:2019-06-06 10:35 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  人 工 智 能(4) 2012/11/16 1 第四章 基本的推理技术 课程的基本内容及要求: 基本内容 基本内容 1. 推理的概念和类型,推理的控制策略; 2. 归结反演系统—— 归结原理、归结反演及其控制策略、应用 归结反演求取问题的答案等; 3. 基于规则的演绎推理(包括正向、反向和双向的演绎推 理)。 要求 要求 1. 熟练掌握与运用归结原理; 2. 理解各种归结反演的控制策略; 3. 学会如何从一归结反演系统中提取回答; 4. 掌握基于规则的演绎推理的工作过程。 2012/11/16 2 第四章 基本的推理技术 4.1 推理技术概述 确定知识表达方法将知识表示出来并存储到计算机 中去 表达知识并存储知识 目的—— 为了更好地利用知识来 解决实际问题 利用知识进行推理是知识利用的基础;是问题求解的 利用知识进行推理是知识利用的基础;是问题求解的 主要手段 主要手段 如专家系统、智能机器人、模式识别、自然语言理解等 本章介绍的推理—— 归结反演、基于规则的演绎系统 等是基于逻辑的推理,属于确定性推理 2012/11/16 3 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 推理—— 人类求解问题主要思维方法,其任务是利用知识 推理 与知识表达方法的关系 推理—— 按照某种策略从已有事实和知识推出结论的过 推理 程。 推理是由程序实现的,称为推理机 在人工智能系统中,推理机利用知识库中的知识,按一定 的控制策略去求解问题 医疗诊断专家系统:知识库中存储经验及医学常识,数据库中存放 病人的症状、化验结果等初始事实,为病人诊治疾病实际上就是一 次推理过程—— 即从病人的症状及化验结果等初始事实出发,利用 知识库中的知识及一定的控制策略,对病情作出诊断,并开出医疗 处方 从初始事实出发,不断运用知识库中的已知知识,逐步推出结论的 过程就是推理 2012/11/16 4 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 人类的智能活动有多种思维方式,人工智能作为对人类智能 的模拟,相应地也有多种推理方式——推理的基本任务 是从一种判断推出另一种判断——分类 1.演绎推理、归纳推理、默认推理 2. 确定性推理、不精确推理 3.单调推理、非单调推理 4.启发式推理、非启发式推理 2012/11/16 5 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 1.从推出新判断的途径分:演绎推理、归纳推理、默认推理 1)演绎推理 从全称判断推出特称判断或单称判断的过程,即从一般 从一般 到个别的推理 到个别的推理 演绎推理中最常用的形式是三段论法 (大前提和小前提,及结 论) 例如: (1)所有的推理系统都是智能系统——一般的知识 (2)专家系统是推理系统——个体的判断 (3)所以,专家系统是智能系统——新判断 没有增加新的知识 2012/11/16 6 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 1.从推出新判断的途径分:演绎推理、归纳推理、默认推理 2)归纳推理 人们对客观事物的认识总是由认识个别事物开 始,进而认识事物的普遍规律,其中归纳推理起了 重要的作用 归纳推理是从足够多的事例中归纳出一般性结 论的推理过程,是一种从个别到一般的推理过程 从个别到一般的推理过程 常用的归纳推理有简单枚举法和类比法 2012/11/16 7 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 1.从推出新判断的途径分:演绎推理、归纳推理、默认推理 2)归纳推理 枚举法归纳推理是由已观察到的事物都有某属性,而没 有观察到相反的事例,从而推出某类事物都有某属性 推理过程可以形式地表示为: S1 是 P S2 是 P … S 是 P n (S ,S , …S 是S 类中的个别事物,在枚举中兼容) 1 2 n S 都是 P S 都是 P 2012/11/16 8 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 1.从推出新判断的途径分:演绎推理、归纳推理、默认推理 2)归纳推理 枚举法归纳推理分完全归纳推理与不完全归纳推理 完全归纳推理—— 在进行归纳时考察了相应事物的全部 完全归纳推理 对象,并根据这些对象是否都具有某种属性,从而推出 这个事物是否具有这个属性 完全归纳推理是必然性推理 不完全归纳推理—— 只考察了相应事物的部分对象,就 不完全归纳推理 得出了结论 不完全推理得出的结论不具有必然性,属于非必然性推理 2012/11/16 9 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 1.从推出新判断的途径分:演绎推理、归纳推理、默认推理 2)归纳推理 在两个或两类事物在许多属性上都相同的基础上,推出 它们在其它属性上也相同,这就是类比法归纳推理 类比法归纳推理 类比法归纳可形式化地表示为: A 具有属性a,b,c,d,e B 具有属性a,b,c,d, B 也具有属性e B 也具有属性e 2012/11/16 10 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 1.从推出新判断的途径分:演绎推理、归纳推理、默认推理 2)归纳推理 类比法的可靠程度决定于两个或两类事物的相同属性与 推出的那个属性之间的相关程度,相关程度越高,则类比法 的可靠性就越高 归纳推理是人类思维活动中最基本、最常用的一种推理 形式 归纳推理增加了知识 (在机器学习部分称为归纳学习) 归纳推理增加了知识 2012/11/16 11 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 1.从推出新判断的途径分:演绎推理、归纳推理、默认推理 3)默认推理 默认推理又称为缺省推理,是在知识不完全的情况下假 默认推理 设某些条件已经具备所进行的推理 如:在条件A已成立的情况下,如果没有足够的证据能证明条件B不成立, 则就默认B是成立的,并在此默认的前提下进行推理,推导出某个结论 由于这种推理允许默认某些条件是成立的,这就摆脱了 需要知道全部有关事实才能进行推理的要求,能在知识不完 全的情况下也能进行推理 在默认推理过程中,如果到某一时刻发现原先所作的默 认不正确,则就要撤消所作的默认以及由此默认推出的所有 结论,重新按新情况进行推理 2012/11/16 12 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 2.按推理时所用的知识的确定性来分: 确定性推理、不精确推理 1)确定性推理 (精确推理) 如在推理中所用的知识都是精确的,即可以把 知识表示成必然的因果关系,然后进行逻辑推理, 推理的结论或者为真,或者为假,这种推理就称为 确定性推理 确定性推理 归结反演、基于规则的演绎系统等都是确定性推理 2012/11/16 13 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 2.按推理时所用的知识的确定性来分: 确定性推理、不精确推理 2)不精确推理 (不确定推理) 在人类知识中,有相当一部分属于人们的主观 判断,是不精确的和含糊的。由这些知识归纳出来 的推理规则往往是不确定的 基于不确定的推理规则进行推理,形成的结论 也是不确定的,这种推理称为不精确推理 不精确推理 专家系统中主要使用的是不精确推理 2012/11/16 14 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 3.按推理过程中推出的结论是否单调增加,或者说推出的结 论是否越来越接近最终目标来划分: 单调推理、非单调推理 1)单调推理 在推理过程中随着推理的向前推进及新知识的加入,推 出的结论呈单调增加的趋势,并且越来越接近最终目标—— 单调推理 单调推理 一个演绎推理的逻辑系统有一个无矛盾的公理系统,新加入的结论 必须与公理系统兼容,因此新的结论与已有的知识不发生矛盾,结论总 是越来越多,所以演绎推理是单调推理 2012/11/16 15 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 3.按推理过程中推出的结论是否单调增加,或者说推出的结 论是否越来越接近最终目标来划分: 单调推理、非单调推理 2)非单调推理 在推理过程中随着推理的向前推进及新知识的加入,不 仅没有加强已推出的结论,反而要否定它,使得推理退回到 前面的某一步,重新开始——非单调推理 非单调推理 一般非单调推理是在知识不完全的情况下进行的,由于 知识不完全,为使推理进行下去,就要先做某些假设,并在 此假设的基础上进行推理,当以后由于新知识的加入发现原 先的假设不正确时,就需要推翻该假设以及由此假设为基础 的一切结论,再用新知识重新进行推理 2012/11/16 16 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 4.按推理中是否运用与问题有关的启发性知识可分: 启发式推理、非启发式推理 1)启发式推理 如果在推理过程中,运用与问题有关的启发性 知识,即解决问题的策略、技巧及经验,以加快推 理过程,提高搜索效率,这种推理过程称为启发式 启发式 推理 推理 * * A 、AO 等算法就属于此类推理 2012/11/16 17 第四章 基本的推理技术 4.1 推理技术概述 推理的概念和类型 4.按推理中是否运用与问题有关的启发性知识可分: 启发式推理、非启发式推理 2)非启发式推理 如果在推理过程中,不运用启发性知识,只按照一般的 控制逻辑进行推理,这种推理称为非启发式推理 非启发式推理 这种方法缺乏对求解问题的针对性,所以推理效率较 低,容易出现“组合爆炸” 问题 图搜索策略中的宽度优先搜索法,虽然是完备的算法,但是对于复 杂问题的求解,将出现 “组合爆炸 ”现象,其搜索效率低 2012/11/16 18 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 推理的控制策略主要是指推理方向的选择、推理时所 用的搜索策略及冲突解决策略等 一般推理的控制策略与知识表达方法有关 1.推理方向 1.推理方向 推理方向用于确定推理的驱动方式 根据推理方向的不同,可将推理分为正向推理、反向推 理和正反向混合推理 无论按哪种方式进行推理,一般都要求系统具有一个存 放知识的知识库(KB)、一个存放初始事实和中间结果的数 据库(DB)和一个用于推理的推理机 2012/11/16 19 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 1.推理方向 1.推理方向 (1) 正向推理 正向推理(事实驱动推理)是由已知事实出发向结论方 正向推理(事实驱动推理) 向的推理 基本思想是:系统根据用户提供的初始事实,在知识库 中搜索能与之匹配的规则即当前可用的规则,构成可适用的 规则集RS,然后按某种冲突解决策略从RS中选择一条知识进 行推理,并将推出的结论作为中间结果加入到数据库DB中作 为下一步推理的事实,在此之后,再在知识库中选择可适用 的知识进行推理,如此重复进行这一过程,直到得出最终结 论或者知识库中没有可适用的知识为止。 2012/11/16 20 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 开始 1.推理方向 1.推理方向 (1)正向推理 将初始事实加入数据库DB 中 是 DB 中是否 成功,退出 包含问题的解? 否 将用户提供的新事实加入DB 中 KB 中是否有可适用的知 否 识? 是 用户可是否补充新 是 把KB 中所有适用的规则加入到RS 中 事实? 是 否 RS为空?空? 失败,退出 否 按一定的冲突解决策略从RS 中 选择一条规则进行推理 将推理结论加入DB 中 2012/11/16 21 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 1.推理方向 1.推理方向 (1)正向推理 正向推理简单、易实现,但目的性不强,效率低 需要用启发性知识解除冲突并控制中间结果的选取,其 中包括必要的回溯 由于不能反推,系统的解释功能受到影响 2012/11/16 22 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 1.推理方向 1.推理方向 (2)反向推理 反向推理—— 以某个假设目标作为出发点的一种推理, 反向推理 又称为 目标驱动推理或逆向推理。 反向推理的基本思想是:首先提出一个假设目标,然后 由此出发,进一步寻找支持该假设的证据,若所需的证据都 能找到,则该假设成立,推理成功;若无法找到支持该假设 的所有证据,则说明此假设不成立,需要另作新的假设。 2012/11/16 23 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 开始 1.推理方向 提出假设 1.推理方向 (2)反向推理 是 是 该假设在数据库 该假设成立 有假设? DB ? 否 否 退出 该假设是否 是 询问用户 是事实? 否 否 在KB 中找出所有能导出该假设的规 有事实? 则,形成适用规则集RS 是 从RS 中选择一条规则,并将该规则的一个 该假设成立,并将此假设 条件作为新的假设目标 作为事实存入DB 2012/11/16 24 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 1.推理方向 1.推理方向 (2)反向推理 与正向推理相比,反向推理的主要优点是不必使用与目 标无关的知识,目的性强,同时它还有利于向用户提供解释 反向推理的缺点是在选择初始目标时具有很大的盲目 性,若假设不正确,就有可能要多次提出假设,影响了系统 的效率 反向推理比较适合结论单一或直接提出结论要求证实的 系统 2012/11/16 25 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 1.推理方向 1.推理方向 (3)正反向混合推理 正向推理 反向推理 正向推理 反向推理 效率低,推出大量无关子目标 假设的盲目性降低效率 正反向混合推理 正反向混合推理 2012/11/16 26 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 1.推理方向 1.推理方向 (3)正反向混合推理 正反向混合推理的一般过程是:先根据初始事实进行正 一般过程 向推理以帮助提出假设,再用反向推理进一步寻找支持假设 的证据,反复这个过程,直到得出结论为止。 正反向混合推理集中了正向推理和反向推理的优点,但 其控制策略相对复杂。 2012/11/16 27 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 开始 1.推理方向 1.推理方向 (3)正反向混合推理 进行正向推理 否 需要反向推理? 输出结果 是 以正向推理所得结果作为假设进行 退出 反向推理 是 否 还需要正向推理吗? 2012/11/16 28 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 2.搜索策略 2.搜索策略 推理时,要反复用到知识库中的规则,而知识库中的规 则又很多,这样就存在着如何在知识库中寻找可用规则的问 题,即如何确定推理路线,使其付出的代价尽可能的少,而 问题又能得到较好的解决 为了有效地控制规则的选取,可以采用各种搜索策略 常用搜索策略: 状态空间搜索(宽度优先搜索、深度优先搜索、有界深度优先搜索等) 启发式搜索等(第三章) 2012/11/16 29 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 3.冲突解决策略 3.冲突解决策略 在推理过程中,系统要不断地用数据库中的事实与知识 库中的规则进行匹配,当有一个以上规则的条件部分和当前 数据库相匹配时,就需要有一种策略来决定首先使用哪一条 规则,这就是冲突解决策略 冲突解决策略 冲突解决策略实际上就是确定规则的启用顺序 2012/11/16 30 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 3.冲突解决策略 3.冲突解决策略 (1) 专一性排序 如果某一规则的条件部分规定的情况比另一规则的条件部分所规定 的情况更专门,则这条规则具有较高的优先级 例,有如下规则: 规则1:IF A AND B AND C THEN E; 规则2:IF A AND B AND C AND D THEN F; 数据库中A、B、C、D均为线都与数据库相匹 配,但因为规则2的条件部分包括了更多的限制,所以具有较高的优先 级。 本策略是优先使用针对性较强的产生式规则 本策略是优先使用针对性较强的产生式规则 2012/11/16 31 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 3.冲突解决策略 3.冲突解决策略 (2) 规则排序 如果规则编排的顺序就表示了启用的优先级,则称之为 规则排序 (3) 数据排序 数据排序就是把规则条件部分的所有条件排序,即按优 先级次序编排起来,当发生冲突时,首先使用在条件部分包 含较高优先级数据的规则 2012/11/16 32 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 3.冲突解决策略 3.冲突解决策略 (4) 就近排序 就近排序就是把最近使用的规则放在最优先的位置。如 果某一规则经常使用,则倾向于更多地使用这条规则 (5) 上下文限制 上下文限制就是把产生式规则按它们所描述的上下文分 组,在某种上下文条件下,只能从与其相对应的那组规则中 选择可应用的规则 不仅可以减少冲突,而且由于搜索范围小,也提高了推 理的效率 2012/11/16 33 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 3.冲突解决策略 3.冲突解决策略 (6)按匹配度排序 在不精确匹配中,为了确定两个知识模式是否可以进行 匹配,需要计算这两个模式的相似程度,当其相似度达到某 个预先规定的值时,就认为它们是可匹配的 相似度又称为匹配度,它除了可用来确定两个知识模式 相似度 是否可匹配外,还可用于冲突解除。若有几条规则均可匹配 成功,则可根据它们的匹配度来决定哪一个产生式规则可优 先被应用 2012/11/16 34 第四章 基本的推理技术 4.1 推理技术概述 推理的控制策略 3.冲突解决策略 3.冲突解决策略 (7) 按条件个数排序 如果有多条产生式规则生成的结论相同,则要求条件少 的产生式规则被优先应用,因为要求条件少的规则匹配时花 费的时间较少 不同的系统,可使用上述这些策略的不同组合,目的是尽 量减少冲突的发生,使推理有较快的速度和较高的效率 如何选择冲突解决策略完全是由启发性知识决定的 2012/11/16 35 第四章 基本的推理技术 4.2 归结反演系统 归结原理 在谓词演算(第二章)中,利用前面列出的等价式和永 真蕴含式可以从已知的一些公式推导出新的公式,这个导出 的公式叫做定理,在推导过程中使用的推理规则序列就成了 该定理的一个证明 将要介绍的归结原理是定理证明的基础,它应用于称为 子句的一种公式类的推理 2012/11/16 36 第四章 基本的推理技术 4.2 归结反演系统 归结原理 难;繁 初始公式 目标公式 规格化 规格化 易;简 初始子句集 目标子句 2012/11/16 37 第四章 基本的推理技术 4.2 归结反演系统 归结原理 1.子句 1.子句 谓词逻辑中,把原子公式及原子公式的否定统称为文字 【定义4.1】任何文字的析取式称为子句。 例如P∨Q、¬P(x,f(x),y)∨Q(y)∨R(f(x)) 都是子句 【定义4.2】不包含任何文字的子句称为空子句,表示为NIL 由于空子句不包含有文字,它不能被任何解释满足,所 以空子句是永假的,不可满足的 由子句构成的集合称为子句集 谓词逻辑中,任何一个谓词公式都可以化成一个子句集 谓词逻辑中,任何一个谓词公式都可以化成一个子句集 2012/11/16 38 第四章 基本的推理技术 4.2 归结反演系统 归结原理 1.子句 1.子句 将谓词公式化为子句集的步骤: (1) 利用P→Q = ¬P∨Q;P↔Q =(P∧Q)∨(¬P∧¬Q)等价 关 系消去蕴含符“→” 和双条件符“↔” (2) 利用¬¬P = P;¬ (P∨Q)= ¬P∧¬ Q;¬ (P∧Q)= ¬P∨¬ Q;¬ (∃x)P = (∀x)(¬P);¬ (∀x)P = (∃x)(¬P)等 价关系把否定符号“¬”移到紧靠谓词位置上 (3) 利用(∀x)P(x)= (∀y)P(y);(∃x)P(x)= (∃y)P (y)等价关系将变量标准化,即使每个量词采用不同的变 量 (续) 2012/11/16 39 第四章 基本的推理技术 4 .2 归结反演系统 归结原理 1.子句 将谓词公式化为子句集的步骤: (4) 消去存在量词∃ 消去存在量词∃ 如果存在量词不在任何一个全称量词的辖域内,则该存 在量词不依赖于任何其它的变量,因此可用一个新的个体 常量代替 如将(∃x)P(x)化为P(A) 如果存在量词是在全称量词的辖域内(如在公式(∀y) ((∃x)P(x,y))中,变量x的取值依赖于变量y的取 值)。令这种依赖关系由函数g(y)来表示,它把每个y值 映射到存在的那个 x。 由Skolem 函数代替存在的x, 就可以消去存在量词 : Skolem 函数代替存在的x, 就可以消去存在量词 : (∀y)P(g(y),y) 。注意,函数名应是原合式公式中没 。 有的符号 2012/11/16 40 第四章 基本的推理技术 4.2 归结反演系统 归结原理 1.子句 1.子句 将谓词公式化为子句集的步骤: (5)将公式化为前束形—— 把所有全称量词(已不留下任何存 在量词,而且每个全称量词都有自己的变量)移到公式的左 边,并使每个量词的辖域包含这个量词后面的整个部分,所 得的公式称为前束形 (6)利用P∨(Q∧R)=(P∨Q)∧(P∨R);(P∧Q)∨ (P∧R)= P∧(Q∨R)等价关系将母式化为合取范式(子 子 句的合取式) 句的合取式 (7)略去全称量词—— 母式中的变量被默认为是全称量词量化 的变量 2012/11/16 41 第四章 基本的推理技术 4.2 归结反演系统 归结原理 1.子句 1.子句 将谓词公式化为子句集的步骤: (8)消去合取符号∧,把母式用子句集表示 子句集 如:P∧Q可表示为成子句集: P Q (9)子句变量标准化——重新命名变量,使每个子句中的变量 符号不同 2012/11/162012/11/16 4242 第四章 基本的推理技术 4.2 归结反演系统 归结原理 1.子句 1.子句 【例4.1】将(∀x){[¬P(x)∨¬Q(x)]→(∃ y)[S(x,y)∧Q(x)]} ∧(∀x) [P(x)∨B(x)]化成子句集 转换过程遵照上述9个步骤: (1) (∀x){¬ [¬P(x)∨¬Q(x)]∨(∃ y)[S(x,y)∧Q(x)]}∧(∀x)[P(x)∨B(x)] (2) (∀x){[P(x)∧Q(x)]∨(∃ y)[S(x,y)∧Q(x)]}∧(∀x)[P(x)∨B(x)] (3) (∀x){[P(x)∧Q(x)]∨ (∃ y)[S(x,y)∧Q(x)]}∧(∀w)[P(w)∨B(w)] (4) (∀x){[P(x)∧Q(x )]∨[S(x,f (x) ) ∧Q(x ) ]}∧ (∀ w) [ P(w)∨B(w)] (5) (∀x)(∀w){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧[P(w)∨B(w)] (6) (∀x)(∀w) {[P(x)∨S(x,f(x))]∧Q(x)∧[P(w)∨B(w)]} (7) [P(x)∨S(x,f(x))]∧Q(x)∧[P(w)∨B(w)] 2012/11/16 43 第四章 基本的推理技术 4.2 归结反演系统 归结原理 1.子句 1.子句 【例4.1】将(∀x){[¬P(x)∨¬Q(x)]→(∃ y)[S(x,y)∧Q(x)]}∧(∀x) [P(x)∨B(x)]化成子句集 转换过程遵照上述9个步骤: (8) 子句集为: P(x)∨S(x,f(x)); Q(x); P(w)∨B(w) (9) 子句变量标准化后,最终的子句集为: P (x)∨S (x,f(x)) P (x)∨S (x,f(x)) Q (y) Q (y) P (w)∨B (w) P (w)∨B (w) 2012/11/162012/11/16 4444 第四章 基本的推理技术 4.2 归结反演系统 归结原理 2.置换和合一 2.置换和合一 为了使用推理规则,如假言推理、假言三段论等,一个 推理系统必须决定两个表达式是否相同或匹配: 两个表达式匹配当且仅当其语法是等价的 两个表达式匹配当且仅当其语法是等价的 一个表达式的项可以是常量、变量或函数,合一就是寻 合一 找项对变量的置换而使表达式一致的过程,合一是人工智能 置换 中很重要的过程 如,为了使公式(∀ x)P(x)与P(A)匹配,可以用常 量A代替变量x,从而使两个公式一致 2012/11/16 45 第四章 基本的推理技术 4.2 归结反演系统 归结原理 2.置换和合一 2.置换和合一 置换可用有序对的集合s={t /v ,t /v ,…,t /v }表 1 1 2 2 n n 示,其中t /v 表示将表达式中所有的变量v 都用项t 代替, i i i i ti可以是变量、常量或函数 注意,一个变量不能用含有同一变量的项来代替 一般可用E 表示一个表达式E用一个置换s所得到的表达 s 式的置换 如:P(z,f(w),A)= (P(x,f(y),A)) s 2012/11/16 46 第四章 基本的推理技术 4.2 归结反演系统 归结原理 2.置换和合一 2.置换和合一 例如有表达式P(x,f(y),A),通过不同的置换,可分 别得到: P(z,f(w),A) 相应的置换为 s = { z/x ,w/y } 1 P(x,f(B),A) 相应的置换为 s2 = { B/ y } P(g(z),f(B),A) 相应的置换为 s3 = { g(z)/x ,B /y } P(C,f(B),A) 相应的置换为 s4 = { C/x ,B/y } 2012/11/16 47 第四章 基本的推理技术 4.2 归结反演系统 归结原理 2.置换和合一 2.置换和合一 置换是可结合的 用s s 表示两个置换s 和 s 的合成,E表示一表达式,则有: 1 2 1 2 (E s)s = E(s s ) 1 2 1 2 (s s )s = s (ss ) 1 2 3 1 2 3 把置换s作用于集合{E }中每一个公式得到的集合用{E } 表示 i i s 如果存在一个置换s,使(E ) =(E ) =(E ) …,则称公式集{E }是可合一 1 s 2 s 3 s i 的,置换s称为{Ei}的合一者 如:公式集{P(x,f(y),B),P(x,f(B),B)}的合一者为s = {A/x,B/y} 2012/11/16 48 第四章 基本的推理技术 4.2 归结反演系统 归结原理 2.置换和合一 2.置换和合一 在 P(x,f(y),B) =P(x,f(B),B) =P(A,f(B),B) ,s={A/x,B/y} s s s 中,s并不是最简单的,因置换{B/y}就可使上述公式集合一 如果s是{E }的任一合一者,又存在某个sˊ,使得公式 i {E }s={E }g sˊ,则称g为公式集{E }的最简单合一者 i i i mgu (Most General Unifier) mgu 置换 { B/y }为公式集{P(x,f( y ),B), P(x , f(B),B)} 的最简单合一者 2012/11/16 49 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理 3.归结原理 归结原理又称为消解原理,它是定理证明基础 由谓词公式转化为子句集的过程中可以看出, 在子句集中子句之间是合取关系,其中只要有一个 子句不可满足,则子句集就不可满足。若一个子句 集中包含空子句,则这个子句集一定是不可满足的 归结原理就是基于这一认识提出来的 【定义4.3】若P是原子谓词公式,则称P与¬P为互补文字 2012/11/16 50 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理 3.归结原理 (1) 基子句的归结 所谓基子句,是指没有变量的子句 【定义4.4】设C 与C 是子句集中的任意两个基子句,如果C 1 2 1 中的文字L 与C 中的文字L 互补,那么从C 和C 中分别消去L 1 2 2 1 2 1 和L ,并将二个子句余下的部分析取,构成一个新子句C , 2 12 则称一过程为归结,称C 为基子句C 和C 的归结式,称C 和 12 1 2 1 C 为C 的父辈子句 2 12 2012/11/16 51 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理 3.归结原理 【例4.2】设C ¬P∨Q∨R,C =P∨S∨T归结为: 1 2 C12=Q∨R∨S∨T ¬P ∨Q ∨R P ∨S∨T Q ∨R ∨S∨T 2012/11/16 52 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理(多子句则逐步归结) 3.归结原理 【例4.3】设子句集S={¬P∨Q,¬Q∨R,P,¬R∨T },则其 归结过程如图 归结结果为T ¬P ∨Q ¬ Q ∨R ¬P ∨R P R ¬ R ∨T T 2012/11/16 53 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理 3.归结原理 (2)含有变量的子句的归结 在谓词逻辑中,子句中含有变量 为将归结原理应用于含有变量的子句,应找出一个置 换,作用于给定的两个子句,使它们包括互补的文字,然后 才能进行归结 例:子句集S={P(x)∨Q(x),¬P(A)∨R(y)},子句集中的两个 子句不能直接归结,但若对子句集先进行置换s={A/x},则 两个子句分别为P(A)∨Q(A)和¬P(A)∨R(y),这时再进行归 结,归结结果为Q(A)∨R(y) 2012/11/16 54 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理 3.归结原理 【定义4.5】设C 和C 是两个没有相同变量的子句,并分别 1 2 表示成两个文字集合{L }和{M },{l }是{L }的一个子集, i i i i {m }是{M }的一个子集,若s是集合{l }和{¬m }的并集的最 i i i i 简合一者,则称 C = {{L }-{l }} ∨{{M }-{m }} 12 i i s i i s 为C 和C 的归结式。 1 2 当两个子句作归结时,子集{l }和{m }的选取可能有多 i i 种形式,所以得到的归结式不是唯一的 2012/11/16 55 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理 3.归结原理 例:设有两个子句P(A)∨¬Q(x)∨R(x)和¬P(y)∨Q(B),则有 如下两种归结方法: ① 取{l }={P(A)},{m }={¬P(y)},{l }和{¬m }的最简合一者 i i i i 为s={A/y},此时归结结果为¬Q(x)∨R(x)∨Q(B) ② 取{l }={¬Q(x)},{m }={Q(B)},{l }和{¬m }的最简合一 i i i i 者为s={B/x},此时归结结果为P(A)∨R(B)∨¬P(y) 2012/11/16 56 第四章 基本的推理技术 4.2 归结反演系统 归结原理 3.归结原理 3.归结原理 例的归结过程: P(A) ∨¬ Q(x) ∨R(x) ¬ P(y) ∨Q(B) P(A) ∨¬ Q(x) ∨R(x) ¬ P(y) ∨Q(B) s={A/ y } s={B/ x } ¬ Q(x) ∨R(x) ∨Q(B) P(A) ∨R(B) ∨¬ P(y) 2012/11/16 57 第四章 基本的推理技术 4.2 归结反演系统 归结反演 归结反演就是利用归结和反演实现定理的证明 具体过程: (1) 将定理证明的前提谓词公式转化为子句集F (2) 将求证的目标表示成合适的谓词公式G(目标公式) (3) 将目标公式的否定式¬G转化成子句的形式,并加入到 子句集F中,得到子句集S (4) 应用归结原理对子句集中的子句进行归结,并把每次 归结得到的归结式都并入S中。如此反复进行,若归结得到 一个空子句NIL,则停止归结 证明了G为线 第四章 基本的推理技术 4.2 归结反演系统 归结反演 【例4.4】 【例4.4】 已知前提为F:(∀x){[P(x,y)∧Q(y)]→(∃y)[R(y)∧S(x,y)]} 求证结论G:¬ (∀x)R(x)→(∀x)(∀y)[P(x,y)→¬Q(y)]成立 证明:先按前面所讲的方法将前提和结论化为子句集: 前提F所对应的子句集为:¬P(x,y)∨¬Q(y)∨R(f(x)) P(x,y)∨¬Q(y)∨S(x, f(x)) 结论G否定对应子句集为:¬R(z) P(A,B) Q(B) 2012/11/16 59 第四章 基本的推理技术 4.2 归结反演系统 归结反演 【例4.4】 ¬ P(x,y) ∨¬ Q(y) ∨R(f(x)) ¬ R(z) 【例4.4】 归结过程 {f(x)/ z} ¬ P(x,y) ∨¬ Q(y) P(A,B) 经过归结最后得到NIL, NIL 所以结论G成立 {A/x,B/y} ¬ Q(B) Q(B) NIL NIL 2012/11/16 60 第四章 基本的推理技术 4.2 归结反演系统 归结反演 【例4.5】已知: 能阅读的都是有文化的; 【例4.5】 海豚是没有文化的; 某些海豚是有智能的; 用归结反演法证明:某些有智能的并不能阅读 证明: 设 R(x):x能阅读 L(x): x有文化 D(x): x是海豚 I(x): x有智能 2012/11/16 61 第四章 基本的推理技术 4.2 归结反演系统 归结反演 【例4.5】 【例4.5】 将前提形式化地表示为: (∀x)(R(x)→L(x)) (∀y)(D(y)→¬ L(y)) (∃z)(D(z)∧I(z)) 将结论形式化地表示为: (∃w)(I(w) ∧ ¬R(w)) 首先将前提化成子句集: ¬ R(x)∨L(x) ¬ D(y)∨¬ L(y) D(A) I(A) 将结论的否定式化成子句:¬I(w)∨R(w) 2012/11/16 62 第四章 基本的推理技术 4.2 归结反演系统 归结反演 ¬ I(w)∨R(w) I(A) 【例4.5】 【例4.5】 R(A) ¬ R(x) ∨L(x) L(A) ¬ D(y) ∨¬ L(y) 归结后得到空子句NIL, ¬ D(A) D(A) 归结后得到空子句

http://mj-sports.net/feidandiaotuili/286.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有