第三章 谓词逻辑与归结原理

《第三章 谓词逻辑与归结原理》由会员分享，可在线阅读，更多相关《第三章 谓词逻辑与归结原理（126页珍藏版）》请在文档大全上搜索。

1、2022-5-301第三章第三章 谓词逻辑与归结原理谓词逻辑与归结原理华北电力大学华北电力大学 计算机系计算机系 刘丽刘丽2022-5-30华北电力大学华北电力大学2第三章第三章 谓词逻辑与归结原理谓词逻辑与归结原理 归结原理概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略 Herbrand定理2022-5-30华北电力大学华北电力大学3归结归结推理推理命题命题逻辑逻辑谓词逻谓词逻辑辑Skolem标准型、标准型、子句集子句集基本基本概念概念谓词逻辑谓词逻辑归结原理归结原理合一和置换、合一和置换、控制策略控制策略数理数理逻辑逻辑命题逻辑命题逻辑归结归结Herbrand定理定

2、理内容框架内容框架2022-5-30华北电力大学华北电力大学4第三章第三章 谓词逻辑与归结原理谓词逻辑与归结原理 归结原理概述 命题逻辑的归结法 谓词逻辑归结基础 归结原理 归结过程的控制策略2022-5-30华北电力大学华北电力大学5概述概述-推理技术推理技术 确定知识表达方法将知识表示出来并存储到计算机中利用知识来解决实际问题如专家系统、智能机器人、模式识别、自然语言理解等 按照某种策略从已有事实和知识推出结论的过程。推理是由程序实现的，称为推理机 医疗诊断专家系统 知识库中存储经验及医学常识 数据库中存放病人的症状、化验结果等初始事实 利用知识库中的知识及一定的控制策略，为病人诊治疾病、

3、开出医疗处方就是推理过程2022-5-30华北电力大学华北电力大学6概述概述 推理的分类 演绎推理、归纳推理、默认推理 确定性推理、不精确推理 单调推理、非单调推理 启发式推理、非启发式推理 2022-5-30华北电力大学华北电力大学7概述概述 从推出新判断的途径分演绎、归纳和默认推理 演绎推理 从全称判断推出特称判断或单称判断的过程，即从一般到个别的推理 演绎推理中最常用的形式是三段论法（大前提和小前提，及结论） 例如： 所有的推理系统都是智能系统一般的知识 专家系统是推理系统个体的判断 所以，专家系统是智能系统新判断没有增加新的知识2022-5-30华北电力大学华北电力大学8概述概述-演绎

4、推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 归纳推理 从足够多的事例中归纳出一般性结论的推理过程，是一种 常用的归纳推理有简单枚举法和类比法 枚举法归纳推理是由已观察到的事物都有某属性，而没有观察到相反的事例，从而推出某类事物都有某属性，推理过程为：S1 是 PS2 是 P Sn 是 P (S1,S2, Sn 是S 类中的个别事物，在枚举中兼容) 2022-5-30华北电力大学华北电力大学9概述概述-演绎推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 归纳推理之枚举法 枚举法归纳推理分完全归纳推理与不完全归纳推理 完全归纳推理完全归纳推理在进行归纳时考察了相应事物的全部对象，并

5、根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性完全归纳推理是必然性推理 不完全归纳推理不完全归纳推理只考察了相应事物的部分对象，就得出了结论不完全推理得出的结论不具有必然性，属于非必然性推理2022-5-30华北电力大学华北电力大学10概述概述-演绎推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 归纳推理之类比法 在两个或两类事物在许多属性上都相同的基础上，推出它们在其它属性上也相同，这就是 类比法归纳可形式化地表示为： A 具有属性a,b,c,d,e B 具有属性a,b,c,d, 类比法的可靠程度决定于两个或两类事物的相同属性与推出的那个属性之间的相关程度，相关程度越

6、高，则类比法的可靠性就越高（在机器学习部分称为归纳学习）2022-5-30华北电力大学华北电力大学11概述概述-演绎推理、归纳推理和默认推理演绎推理、归纳推理和默认推理 默认推理 又称为缺省推理，是在知识不完全的情况下假设某些条件已经具备所进行的推理 如：在条件A已成立的情况下，如果没有足够的证据能证明条件B不成立，则就默认B是成立的，并在此默认的前提下进行推理，推导出某个结论 知识不完全的情况下也能进行推理 如果到某一时刻发现原先所作的默认不正确，则要撤消所作的默认以及由此默认推出的所有结论，重新按新情况进行推理 2022-5-30华北电力大学华北电力大学12概述概述 按推理时所用的知识的确

7、定性分 确定性推理 推理中所用的知识都是精确的 归结反演、基于规则的演绎系统等都是确定性推理 不精确推理 基于不确定的推理规则进行，形成的结论也是不确定的 专家系统中主要使用的是不精确推理2022-5-30华北电力大学华北电力大学13概述概述 按推出的结论是否单调增加，或推出的结论是否越来越接近最终目标分： 单调推理 在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标 非单调推理 在推理过程中随着推理的向前推进及新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始 一般非单调推理是在知识不完全的情况下进行的20

8、22-5-30华北电力大学华北电力大学14概述概述 按推理中是否运用与问题有关的启发性知识分 启发式推理 推理过程中，运用与问题有关的启发性知识，以加快推理过程，提高搜索效率 A*、AO*等算法就属于此类推理 非启发式推理 推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理 这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题，如宽度优先搜索法2022-5-30华北电力大学华北电力大学15概述概述 推理的控制策略 主要是指推理方向的选择、推理时所用的搜索策略及冲突解决策略等 一般推理的控制策略与知识表达方法有关 推理方向 推理方向用于确定推理的驱动方式 根据推理方

9、向的不同，可将推理分为正向推理、反向推理和正反向混合推理 无论按哪种方式进行推理，一般都要求系统具有一个存放知识的知识库（KB）、一个存放初始事实和中间结果的数据库（DB）和一个用于推理的推理机2022-5-30华北电力大学华北电力大学16概述概述-推理的控制策略推理的控制策略 推理方向 正向推理（事实驱动推理）是由已知事实出发向结论方向的推理开始DB中是否包含问题的解？将用户提供的新事实加入DB中KB中是否有可适用的知识？把KB中所有适用的规则加入到RS中RS为空？按一定的冲突解决策略从RS中选择一条规则进行推理将推理结论加入DB中成功，退出用户可是否补充新事实？失败，退出将初始事实加入数据

10、库DB中是 否否是否是否2022-5-30华北电力大学华北电力大学17概述概述-推理的控制策略推理的控制策略 推理方向 反向推理以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理在KB中找出所有能导出该假设的规则，形成适用规则集RS该假设是否是事实？该假设在数据库DB？从RS中选择一条规则，并将该规则的一个条件作为新的假设目标该假设成立有假设？退出询问用户有事实？该假设成立，并将此假设作为事实存入DB提出假设开始是否是否否是是否2022-5-30华北电力大学华北电力大学18概述概述-推理的控制策略推理的控制策略 推理方向 正反混合推理是开始进行正向推理需要反向推理？以正向推理所得

11、结果作为假设进行反向推理还需要正向推理吗？输出结果退出否是否2022-5-30华北电力大学华北电力大学19概述概述-推理的控制策略推理的控制策略 推理时，要反复用到知识库中的规则，而知识库中的规则又很多，这样就存在着如何在知识库中寻找可用规则的问题 为有效控制规则的选取，可以采用各种搜索策略 常用搜索策略：状态空间搜索（宽度优先搜索、深度优先搜索、有界深度优先搜索等）启发式搜索等（第三章）2022-5-30华北电力大学华北电力大学20概述概述-推理的控制策略推理的控制策略 冲突解决策略冲突解决策略 推理过程中，系统要不断地用数据库中的事实与知识库中的规则进行匹配，当有一个以上规则的条件部分和当