人工智能的基本推理技术.ppt

《人工智能的基本推理技术.ppt》由会员分享，可在线阅读，更多相关《人工智能的基本推理技术.ppt（120页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2022-5-251基本的推理技术基本的推理技术 课程的基本内容及要求：课程的基本内容及要求：1.推理的概念和类型，推理的控制策略；2.归结反演系统归结原理、归结反演及其控制策略、应用归结反演求取问题的答案等；3.基于规则的演绎推理（包括正向、反向和双向的演绎推理）。1.熟练掌握与运用归结原理；2.理解各种归结反演的控制策略；3.学会如何从一归结反演系统中提取回答；4.掌握基于规则的演绎推理的工作过程。 2022-5-252课程的安排：课程的安排： 1.1，2（2小节）节（学时） 重点：1节2小节；2节1小节2.2（2，3小节）（学时） 重点：2节2，3小节3.2（4小节），3（学时） 重点：

2、2节（4小节）3节（1，2小节）2022-5-2531 1 推理技术概述推理技术概述 确定知识表达方法将知识表示出来并存储到计算机中去表达知识并存储知识目的为了更好地利用知识来解决实际问题如专家系统、智能机器人、模式识别、自然语言理解等本章介绍的推理归结反演、基于规则的演绎系统等是基于逻辑的推理，属于确定性推理 2022-5-2541 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 人类求解问题主要思维方法，其任务是利用知识 与知识表达方法的关系 按照某种策略从已有事实和知识推出结论的过程。推理是由程序实现的，称为推理机 在人工智能系统中，推理机利用知识库中的知识，按一定的控制策

3、略去求解问题医疗诊断专家系统：知识库中存储经验及医学常识，数据库中存放病人的症状、化验结果等初始事实，为病人诊治疾病实际上就是一次推理过程即从病人的症状及化验结果等初始事实出发，利用知识库中的知识及一定的控制策略，对病情作出诊断，并开出医疗处方从初始事实出发，不断运用知识库中的已知知识，逐步推出结论的过程就是推理2022-5-2551 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 人类的智能活动有多种思维方式，人工智能作为对人类智能的模拟，相应地也有多种推理方式推理的基本任务是从一种判断推出另一种判断分类1演绎推理、归纳推理、默认推理 2.确定性推理、不精确推理 3单调推理、非

4、单调推理 4启发式推理、非启发式推理 2022-5-2561 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理1）演绎推理从全称判断推出特称判断或单称判断的过程，即演绎推理中最常用的形式是三段论法（大前提和小前提，及结论）例如例如：（1）所有的推理系统都是智能系统一般的知识（2）专家系统是推理系统个体的判断（3）所以，专家系统是智能系统新判断没有增加新的知识没有增加新的知识2022-5-2571 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理2）归纳推理人们对客

5、观事物的认识总是由认识个别事物开始，进而认识事物的普遍规律，其中归纳推理起了重要的作用归纳推理是从足够多的事例中归纳出一般性结论的推理过程，是一种常用的归纳推理有简单枚举法和类比法 2022-5-2581 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理2）归纳推理枚举法归纳推理是由已观察到的事物都有某属性，而没有观察到相反的事例，从而推出某类事物都有某属性推理过程可以形式地表示为：S1 是 PS2 是 P Sn 是 P (S1,S2, Sn 是S 类中的个别事物，在枚举中兼容) 2022-5-2591 1 推理技术概述推理技术

6、概述推理的概念和类型推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理2）归纳推理枚举法归纳推理分完全归纳推理与不完全归纳推理在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性 完全归纳推理是必然性推理 只考察了相应事物的部分对象，就得出了结论 不完全推理得出的结论不具有必然性，属于非必然性推理2022-5-25101 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理2）归纳推理在两个或两类事物在许多属性上都相同的基础上，推出它们在其它属性上也相同，这就是

7、类比法归纳可形式化地表示为：A 具有属性a,b,c,d,eB 具有属性a,b,c,d, 2022-5-25111 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理2）归纳推理类比法的可靠程度决定于两个或两类事物的相同属性与推出的那个属性之间的相关程度，相关程度越高，则类比法的可靠性就越高归纳推理是人类思维活动中最基本、最常用的一种推理形式（在机器学习部分称为归纳学习） 2022-5-25121 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理3）归纳推理又称为缺省

8、推理，是在知识不完全的情况下假设某些条件已经具备所进行的推理如：在条件A已成立的情况下，如果没有足够的证据能证明条件B不成立，则就默认B是成立的，并在此默认的前提下进行推理，推导出某个结论由于这种推理允许默认某些条件是成立的，这就摆脱了需要知道全部有关事实才能进行推理的要求，能在知识不完全的情况下也能进行推理在默认推理过程中，如果到某一时刻发现原先所作的默认不正确，则就要撤消所作的默认以及由此默认推出的所有结论，重新按新情况进行推理 2022-5-25131 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 2按推理时所用的知识的确定性来分：确定性推理、不精确推理 1）确定性推理（

9、精确推理） 如在推理中所用的知识都是精确的，即可以把知识表示成必然的因果关系，然后进行逻辑推理，推理的结论或者为真，或者为假，这种推理就称为归结反演、基于规则的演绎系统等都是确定性推理 2022-5-25141 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 2按推理时所用的知识的确定性来分：确定性推理、不精确推理 1）不精确推理 （不确定推理） 在人类知识中，有相当一部分属于人们的主观判断，是不精确的和含糊的。由这些知识归纳出来的推理规则往往是不确定的基于不确定的推理规则进行推理，形成的结论也是不确定的，这种推理称为专家系统中主要使用的是不精确推理 2022-5-25151 1

10、 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 3按推理过程中推出的结论是否单调增加，或者说推出的结论是否越来越接近最终目标来划分：单调推理、非单调推理 1）单调推理在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标 一个演绎推理的逻辑系统有一个无矛盾的公理系统，新加入的结论必须与公理系统兼容，因此新的结论与已有的知识不发生矛盾，结论总是越来越多，所以演绎推理是单调推理 2022-5-25161 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 3按推理过程中推出的结论是否单调增加，或者说推出的结论是否越来越接近最终目标来划

11、分：单调推理、非单调推理 2）非单调推理 在推理过程中随着推理的向前推进及新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始一般非单调推理是在知识不完全的情况下进行的，由于知识不完全，为使推理进行下去，就要先做某些假设，并在此假设的基础上进行推理，当以后由于新知识的加入发现原先的假设不正确时，就需要推翻该假设以及由此假设为基础的一切结论，再用新知识重新进行推理2022-5-25171 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 4按推理中是否运用与问题有关的启发性知识可分：启发式推理、非启发式推理 1）启发式推理 如果在推理过程中，运用

12、与问题有关的启发性知识，即解决问题的策略、技巧及经验，以加快推理过程，提高搜索效率，这种推理过程称为A*、AO*等算法就属于此类推理2022-5-25181 1 推理技术概述推理技术概述推理的概念和类型推理的概念和类型 4按推理中是否运用与问题有关的启发性知识可分：启发式推理、非启发式推理 2）非启发式推理 如果在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理，这种推理称为 这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题图搜索策略中的宽度优先搜索法，虽然是完备的算法，但是对于复杂问题的求解，将出现“组合爆炸”现象，其搜索效率低 2022-5-25191

13、1 推理技术概述推理技术概述推理的控制策略推理的控制策略 推理的控制策略主要是指推理方向的选择、推理时所用的搜索策略及冲突解决策略等 一般推理的控制策略与知识表达方法有关推理方向用于确定推理的驱动方式根据推理方向的不同，可将推理分为正向推理、反向推理和正反向混合推理无论按哪种方式进行推理，一般都要求系统具有一个存放知识的知识库（KB）、一个存放初始事实和中间结果的数据库（DB）和一个用于推理的推理机 2022-5-25201 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 (1) 正向推理是由已知事实出发向结论方向的推理基本思想是：系统根据用户提供的初始事实，在知识库中搜索能与之匹配

14、的规则即当前可用的规则，构成可适用的规则集RS，然后按某种冲突解决策略从RS中选择一条知识进行推理，并将推出的结论作为中间结果加入到数据库DB中作为下一步推理的事实，在此之后，再在知识库中选择可适用的知识进行推理，如此重复进行这一过程，直到得出最终结论或者知识库中没有可适用的知识为止 2022-5-25211 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 （1）正向推理 是开始DB中是否包含问题的解？将用户提供的新事实加入DB中KB中是否有可适用的知识？把KB中所有适用的规则加入到RS中RS为空？空？按一定的冲突解决策略从RS中选择一条规则进行推理将推理结论加入DB中成功，退出用户

15、可是否补充新事实？失败，退出将初始事实加入数据库DB中是 否否是否是否2022-5-25221 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 （1）正向推理正向推理简单、易实现，但目的性不强，效率低需要用启发性知识解除冲突并控制中间结果的选取，其中包括必要的回溯由于不能反推，系统的解释功能受到影响 2022-5-25231 1 推理技术概述推理技术概述推理的控制策略推理的控制策略（2）反向推理 在KB中找出所有能导出该假设的规则，形成适用规则集RS该假设是否是事实？该假设在数据库DB？从RS中选择一条规则，并将该规则的一个条件作为新的假设目标该假设成立有假设？退出询问用户有事实？该

16、假设成立，并将此假设作为事实存入DB提出假设开始是否是否否是是否2022-5-25241 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 （2）反向推理以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理反向推理的基本思想是：首先提出一个假设目标，然后由此出发，进一步寻找支持该假设的证据，若所需的证据都能找到，则该假设成立，推理成功；若无法找到支持该假设的所有证据，则说明此假设不成立，需要另作新的假设 2022-5-25251 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 （2）反向推理与正向推理相比，反向推理的主要优点是不必使用与目标无关的知识，目的性强，同

17、时它还有利于向用户提供解释 反向推理的缺点是在选择初始目标时具有很大的盲目性，若假设不正确，就有可能要多次提出假设，影响了系统的效率反向推理比较适合结论单一或直接提出结论要求证实的系统 2022-5-25261 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 （3）正反向混合推理是开始进行正向推理需要反向推理？以正向推理所得结果作为假设进行反向推理还需要正向推理吗？输出结果退出否是否2022-5-25271 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 （3）正反向混合推理效率低，推出大量无关子目标假设的盲目性降低效率2022-5-25281 1 推理技术概述推理技术概述

18、推理的控制策略推理的控制策略 （3）正反向混合推理正反向混合推理的是：先根据初始事实进行正向推理以帮助提出假设，再用反向推理进一步寻找支持假设的证据，反复这个过程，直到得出结论为止正反向混合推理集中了正向推理和反向推理的优点，但其控制策略相对复杂 2022-5-25291 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 推理时，要反复用到知识库中的规则，而知识库中的规则又很多，这样就存在着如何在知识库中寻找可用规则的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决为了有效地控制规则的选取，可以采用各种搜索策略常用搜索策略：状态空间搜索（宽度优先搜索、深度优

19、先搜索、有界深度优先搜索等）启发式搜索等（第三章） 2022-5-25301 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 在推理过程中，系统要不断地用数据库中的事实与知识库中的规则进行匹配，当有一个以上规则的条件部分和当前数据库相匹配时，就需要有一种策略来决定首先使用哪一条规则，这就是冲突解决策略实际上就是确定规则的启用顺序 2022-5-25311 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 (1) 专一性排序如果某一规则的条件部分规定的情况比另一规则的条件部分所规定的情况更专门，则这条规则具有较高的优先级例，有如下规则：规则1：IF A AND B AND C

20、THEN E；规则2：IF A AND B AND C AND D THEN F；数据库中A、B、C、D均为真，这时规则1和规则2都与数据库相匹配，但因为规则2的条件部分包括了更多的限制，所以具有较高的优先级 2022-5-25321 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 (2) 规则排序如果规则编排的顺序就表示了启用的优先级，则称之为规则排序 (3) 数据排序数据排序就是把规则条件部分的所有条件排序，即按优先级次序编排起来，当发生冲突时，首先使用在条件部分包含较高优先级数据的规则 (4) 就近排序就近排序就是把最近使用的规则放在最优先的位置。如果某一规则经常使用，则倾向于

21、更多地使用这条规则 2022-5-25331 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 (5) 上下文限制上下文限制就是把产生式规则按它们所描述的上下文分组，在某种上下文条件下，只能从与其相对应的那组规则中选择可应用的规则不仅可以减少冲突，而且由于搜索范围小，也提高了推理的效率 2022-5-25341 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 (6) 按匹配度排序在不精确匹配中，为了确定两个知识模式是否可以进行匹配，需要计算这两个模式的相似程度，当其相似度达到某个预先规定的值时，就认为它们是可匹配的又称为匹配度，它除了可用来确定两个知识模式是否可匹配外，还可用

22、于冲突解除。若有几条规则均可匹配成功，则可根据它们的匹配度来决定哪一个产生式规则可优先被应用 2022-5-25351 1 推理技术概述推理技术概述推理的控制策略推理的控制策略 (6) 按条件个数排序如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用，因为要求条件少的规则匹配时花费的时间较少 不同的系统，可使用上述这些策略的不同组合，目的是尽量减少冲突的发生，使推理有较快的速度和较高的效率 如何选择冲突解决策略完全是由启发性知识决定的 2022-5-25362 2 归结反演系统归结反演系统 归结原理归结原理 在谓词演算（第二章）中，利用前面列出的等价式和永真蕴含式可以从已知

23、的一些公式推导出新的公式，这个导出的公式叫做定理，在推导过程中使用的推理规则序列就成了该定理的一个证明将要介绍的归结原理是定理证明的基础，它应用于称为子句的一种公式类的推理 2022-5-25372 2 归结反演系统归结反演系统 归结原理归结原理难；繁初始公式目标公式初始子句集目标子句易；简规格化规格化2022-5-25382 2 归结反演系统归结反演系统 归结原理归结原理 谓词逻辑中，把原子公式及原子公式的否定统称为文字【定义41】任何文字的析取式称为子句。例如PQ、P（x，f(x)，y）Q(y)R(f(x) 都是子句【定义42】不包含任何文字的子句称为空子句，表示为NIL由于空子句不包含有

24、文字，它不能被任何解释满足，所以空子句是永假的，不可满足的由子句构成的集合称为子句集2022-5-25392 2 归结反演系统归结反演系统 归结原理归结原理 将谓词公式化为子句集的步骤：(1) 利用PQ = PQ；PQ =（PQ）（PQ）等价关系消去蕴含符“”和双条件符“” (2) 利用P = P；（PQ）= P Q；（PQ）= P Q；($x)P = (x)(P)；(x)P = ($x)(P)等价关系把否定符号“”移到紧靠谓词位置上(3) 利用(x)P（x）= (y)P（y）；($x)P（x）= ($y)P（y）等价关系将变量标准化，即使每个量词采用不同的变量 (4) 如果存在量词不在任何一

25、个全称量词的辖域内，则该存在量词不依赖于任何其它的变量，因此可用一个新的个体常量代替 如将($x)P（x）化为P(A) 如果存在量词是在全称量词的辖域内（如在公式(“y)（($x)P（x，y）中，变量x的取值依赖于变量y的取值） 由表示依赖关系 注意，函数名应是原合式公式中没有的符号（续）2022-5-25402 2 归结反演系统归结反演系统 归结原理归结原理 将谓词公式化为子句集的步骤： (5)将公式化为前束形把所有全称量词（已不留下任何存在量词，而且每个全称量词都有自己的变量）移到公式的左边，并使每个量词的辖域包含这个量词后面的整个部分，所得的公式称为前束形 (6)利用P（QR）=（PQ）

26、（PR）；（PQ）（PR）= P（QR）等价关系将母式化为合取范式（） (7)略去全称量词母式中的变量被默认为是全称量词量化的变量 (8)消去合取符号，把母式用表示 如：PQ可表示为成子句集： P Q (9)子句变量标准化重新命名变量，使每个子句中的变量符号不同2022-5-25412 2 归结反演系统归结反演系统 归结原理归结原理 【例41】将(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)

27、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） (8) 子句集为： P（x）S(x，f(x)）；Q(x)；P（w）B（w） (9) 子句变量标准化后，最终的子句集为： 2022-5-25422 2 归结反演系统归结反演系统 归结原

28、理归结原理 为了使用推理规则，如假言推理、假言三段论等，一个推理系统必须决定两个表达式是否相同或匹配：一个表达式的项可以是常量、变量或函数，就是寻找项对变量的而使表达式一致的过程，合一是人工智能中很重要的过程如，为了使公式( x)P（x）与P（A）匹配，可以用常量A代替变量x，从而使两个公式一致 2022-5-25432 2 归结反演系统归结反演系统 归结原理归结原理 置换可用有序对的集合s=t1/v1，t2/v2，tn/vn表示，其中ti/vi表示将表达式中所有的变量vi都用项ti代替，ti可以是变量、常量或函数注意，一个变量不能用含有同一变量的项来代替 一般可用Es表示一个表达式E用一个置

29、换s所得到的表达式的置换如：P（z，f（w），A）= （P（x，f（y），A）s 2022-5-25442 2 归结反演系统归结反演系统 归结原理归结原理 例如有表达式P（x，f（y），A），通过不同的置换，可分别得到：P（z，f（w），A） 相应的置换为 s1 = z/x ，w/y 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 2022-5-25452 2 归结反演系统归结反演系统 归结原理归结原理 置换是可结合的用s1 s2表示两个置

30、换s1和 s2的合成，E表示一表达式，则有：（E s1）s2 = E（s1 s2） （s1 s2）s3= s1（s2 s3）把置换s作用于集合Ei中每一个公式得到的例的集合用Eis表示如果存在一个置换s，使(E1)s=(E2)s=(E3)s=，则称公式集Ei是可合一的，置换s称为Ei的合一者 如：公式集P(x,f(y),B),P(x,f(B),B)的合一者为s = A/x,B/y 2022-5-25462 2 归结反演系统归结反演系统 归结原理归结原理 在P(x,f(y),B)s=P(x,f(B),B)s=P(A,f(B),B)s,s=A/x,B/y中，s并不是最简单的，因置换B/y就可使上述

31、公式集合一如果s是Ei的任一合一者，又存在某个s，使得公式Eis=Eig s，则称g为公式集Ei的最简单合一者（Most General Unifier）置换 B/y 为公式集P(x，f( y )，B), P(x , f(B)，B)的最简单合一者 2022-5-25472 2 归结反演系统归结反演系统 归结原理归结原理最简单的合一者的递归算法UNIFY（E1，E2）(1) if E1或E2是一个原子，如果有必要则交换E1和E2的位置，使E1是一个原子，do： (2) if E1和E2是相同的，return NIL (3) else if E1是个变量，do： (4) if E1出现在E2中，r

32、eturn FAIL else return E2/E1 (5) if E2是一个变量，return E1/E2 else return FAIL (6) else F1E1的第一个元素，T1E1的其余元素 (7) F2E2的第一个元素，T2E2的其余元素 (8) Z1UNIFY（F1，F2） (9) if Z1 = FAIL, return FAIL (10) G1Z1作用到T1的结果 (11) G2Z1作用到T2的结果 (12) Z2UNIFY（G1，G2） (13) if Z2 = FAIL, return FAIL else Return Z1 和Z2的合成 2022-5-25482

33、2 归结反演系统归结反演系统 归结原理归结原理归结原理又称为消解原理，它是定理证明基础由谓词公式转化为子句集的过程中可以看出，在子句集中子句之间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。若一个子句集中包含空子句，则这个子句集一定是不可满足的归结原理就是基于这一认识提出来的【定义43】若P是原子谓词公式，则称P与P为互补文字 2022-5-25492 2 归结反演系统归结反演系统 归结原理归结原理(1) 基子句的归结所谓基子句，是指没有变量的子句【定义44】设C1与C2是子句集中的任意两个基子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，

34、并将二个子句余下的部分析取，构成一个新子句C12，则称一过程为归结，称C12为基子句C1和C2的归结式，称C1和C2为C12的父辈子句2022-5-25502 2 归结反演系统归结反演系统 归结原理归结原理【例42】设C1=PQR，C2=PST归结为：C12=QRST P QRPSTQRST2022-5-25512 2 归结反演系统归结反演系统 归结原理归结原理(多子句则逐步归结)【例43】设子句集S=PQ，QR，P，RT ，则其归结过程如图 归结结果为T P Q QRP RP R RTT2022-5-25522 2 归结反演系统归结反演系统 归结原理归结原理(2)含有变量的子句的归结在谓词逻

35、辑中，子句中含有变量为将归结原理应用于含有变量的子句，应找出一个置换，作用于给定的两个子句，使它们包括互补的文字，然后才能进行归结 例:子句集S=P(x)Q(x)，P(A)R(y)，子句集中的两个子句不能直接归结，但若对子句集先进行置换s=A/x，则两个子句分别为P(A)Q(A)和P(A)R(y)，这时再进行归结，归结结果为Q(A)R(y) 2022-5-25532 2 归结反演系统归结反演系统 归结原理归结原理【定义45】设C1和C2是两个没有相同变量的子句，并分别表示成两个文字集合Li和Mi，li是Li的一个子集，mi是Mi的一个子集，若s是集合li和mi的并集的最简合一者，则称C12 =

36、 Li-lisMi-mi s为C1和C2的归结式。当两个子句作归结时，子集li和mi的选取可能有多种形式，所以得到的归结式不是唯一的 2022-5-25542 2 归结反演系统归结反演系统 归结原理归结原理例:设有两个子句P(A)Q(x)R(x)和P(y)Q(B)，则由如下两种归结方法： 取li=P(A)，mi=P(y)，li和mi的最简合一者为s=A/y，此时归结结果为Q(x)R(x)Q(B) 取li=Q(x)，mi=Q(B)，li和mi的最简合一者为s=B/x，此时归结结果为P(A)R(B)P(y) 2022-5-25552 2 归结反演系统归结反演系统 归结原理归结原理例的归结过程： P

37、(A) Q(x)R(x) P(y) Q(B)P(A) Q(x)R(x) P(y) Q(B) Q(x)R(x) Q(B)P(A) R(B) P(y)s=A/ y s=B/ x 2022-5-25562 2 归结反演系统归结反演系统 归结反演归结反演初始公式目标公式初始子句集目标子句难；繁初始子句集可判定的！永真：半可判定的永真：半可判定的2022-5-25572 2 归结反演系统归结反演系统 归结反演归结反演 归结反演就是利用归结和反演实现定理的证明具体过程： (1) 将定理证明的前提谓词公式转化为子句集F (2) 将求证的目标表示成合适的谓词公式G（目标公式） (3) 将目标公式的否定式G转化

38、成子句的形式，并加入到子句集F中，得到子句集S (4) 应用归结原理对子句集中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若归结得到一个空子句NIL，则停止归结 证明了G为真2022-5-25582 2 归结反演系统归结反演系统 归结反演归结反演 已知前提为已知前提为F:(F:( x x)P(x,y)Q(y)P(x,y)Q(y)( ($ $y y)R(y)S(x,y)R(y)S(x,y)求证结论求证结论G:G: ( ( x x)R(x)R(x)( ( x x)()( y y)P(x,y)P(x,y) Q(y)Q(y)成立成立证明：先按前面所讲的方法将前提和结论化为子句集：

39、证明：先按前面所讲的方法将前提和结论化为子句集：前提前提F F所对应的子句集为：所对应的子句集为： P(x,y)P(x,y) Q(y)R(f(x)Q(y)R(f(x) P(x,y) P(x,y) Q(y)S(x, f(x)Q(y)S(x, f(x)结论结论G G否定对应子句集为：否定对应子句集为： R(z)R(z) P(A,B) P(A,B) Q(B) Q(B) 2022-5-25592 2 归结反演系统归结反演系统 归结反演归结反演 归结过程归结过程经过归结最后得到经过归结最后得到，所以结论所以结论G G成立成立 P(x,y) Q(y) R(f(x) R(z) P(x,y) Q(y)f(x)

40、/ zP(A,B) Q(B)A/x,B/y Q(B) 2022-5-25602 2 归结反演系统归结反演系统 归结反演归结反演 已知已知: : 能阅读的都是有文化的能阅读的都是有文化的; ; 海豚是没有文化的海豚是没有文化的; ; 某些海豚是有智能的某些海豚是有智能的; ; 用归结反演法证明用归结反演法证明: :某些有智能的并不能阅读某些有智能的并不能阅读证明：证明：设设 R(x)R(x)：x x能阅读能阅读L(x): xL(x): x有文化有文化 D(x): xD(x): x是海豚是海豚 I(x): xI(x): x有智能有智能 2022-5-25612 2 归结反演系统归结反演系统 归结反

41、演归结反演 将前提形式化地表示为：将前提形式化地表示为：( ( x)x)（R(x)R(x)L(x)L(x)）( ( y)y)（D(y)D(y) L(y) L(y)）( ($ $z z) )（D(z)I(z)D(z)I(z)将结论形式化地表示为：将结论形式化地表示为： ( ($ $w w)(I(w)(I(w) R(w)R(w)首先将前提化成子句集：首先将前提化成子句集： R(x)L(x)R(x)L(x) D(y) D(y) L(y) L(y) D(A)D(A)I(A)I(A)将结论的否定式为化成子句：将结论的否定式为化成子句： I(w)R(w)I(w)R(w)2022-5-25622 2 归结反

42、演系统归结反演系统 归结反演归结反演 I(w) R(w)I(A)R(A) R(x) L(x)L(A) D(y) L(y) D(A) D(A)2022-5-25632 2 归结反演系统归结反演系统 归结反演归结反演 归结反演过程主要就是证明一个集合归结反演过程主要就是证明一个集合S S是是不可满足不可满足的过程，即从集合的过程，即从集合S S中中归结出空子句归结出空子句的过程的过程算法描述：算法描述：过程过程RESOLUTIONRESOLUTION (1) (1) CLAUSESSCLAUSESS (2) (2) Until NILUntil NIL是是CLAUSESCLAUSES的成员，的成员

43、，do:do: (3) (3) BeginBegin (4)(4) 在在CLAUSESCLAUSES中选择两个不同的可归结的子句中选择两个不同的可归结的子句CiCi和和CjCj (5)(5) 计算计算CiCi和和CjCj的归结式的归结式CijCij (6)(6) CLAUSESCLAUSES附加附加CijCij到到CLAUSESCLAUSES产生的子句集产生的子句集 （7 7）endend2022-5-25642 2 归结反演系统归结反演系统 归结反演的控制策略归结反演的控制策略对子句集进行归结时，关键的一步是从子句集中找出可对子句集进行归结时，关键的一步是从子句集中找出可进行归结的子句进行归

44、结的子句由于事先不知道哪两个子句可以进行归结，更不知道通由于事先不知道哪两个子句可以进行归结，更不知道通过对哪些子句对的归结可以尽快地得到空子句，因而必须对过对哪些子句对的归结可以尽快地得到空子句，因而必须对子句集中的所有子句逐对地进行比较，对任何一对可归结的子句集中的所有子句逐对地进行比较，对任何一对可归结的子句对都进行归结，这样的效率是很低的子句对都进行归结，这样的效率是很低的归结反演的归结反演的控制策略控制策略 2022-5-25652 2 归结反演系统归结反演系统 归结反演的控制策略归结反演的控制策略1 1宽度优先策略宽度优先策略基本思想基本思想：首先从基本子句集生成：首先从基本子句集

45、生成所有的所有的归结式，称为归结式，称为第一级归结式。在这一轮归结中，子句集中的每个子句都要第一级归结式。在这一轮归结中，子句集中的每个子句都要和子句集中的其它子句比较以确定是否进行归结。然后，从和子句集中的其它子句比较以确定是否进行归结。然后，从基本子句集和第一级归结式生成第二级归结式。以此类推，基本子句集和第一级归结式生成第二级归结式。以此类推，直到出现了空子句或者不能再归结为止直到出现了空子句或者不能再归结为止宽度优先策略是宽度优先策略是完备的完备的，但会归结出许多无用的子句，而且，但会归结出许多无用的子句，而且有一些归结式还是重复的，所以是有一些归结式还是重复的，所以是低效的低效的，即

46、浪费时间又多，即浪费时间又多占空间占空间 2022-5-25662 2 归结反演系统归结反演系统 归结反演的控制策略归结反演的控制策略1 1宽度优先策略宽度优先策略 I(w) R(w)I(A)L(A) R(x) L(x) D(y) L(y) D(A) I(w) L(w) R(y) D(y) L(A)R(A)D(A)L(A) I(w) D(w)R(A) I(A)2022-5-25672 2 归结反演系统归结反演系统 归结反演的控制策略归结反演的控制策略2 2支持集策略支持集策略 支持集支持集策略是一种改进的归结策略策略是一种改进的归结策略对参加归结的子句提出了如下限制：对参加归结的子句提出了如下

47、限制：每一次归结时，其每一次归结时，其父辈子句中至少有一个是由目标公式的否定所得到的子句或父辈子句中至少有一个是由目标公式的否定所得到的子句或者是它们的后代（即支持集）者是它们的后代（即支持集）可以证明，支持集策略是可以证明，支持集策略是完备的完备的，即若子句集是不可满，即若子句集是不可满足的，则由支持集策略一定可以归结出空子句足的，则由支持集策略一定可以归结出空子句支持集策略相当于在宽度优先策略中引入了约束条件，支持集策略相当于在宽度优先策略中引入了约束条件，因此因此效率效率比宽度优先策略要高比宽度优先策略要高 2022-5-25682 2 归结反演系统归结反演系统 归结反演的控制策略归结反

48、演的控制策略2 2支持集策略支持集策略 I(w) R(w)I(A)L(A) R(x) L(x) D(y) L(y) D(A) I(w) L(w)R(A)L(A) I(y) D(y)D(A)I(A)D(A)D(A)2022-5-25692 2 归结反演系统归结反演系统 归结反演的控制策略归结反演的控制策略 3 3单文字子句优先策略单文字子句优先策略 如果一个子句只包含一个文字，则称它为单文字子句如果一个子句只包含一个文字，则称它为单文字子句 单文字子句优先策略要求参加单文字子句优先策略要求参加归结的子句中必须至少有一个归结的子句中必须至少有一个是单文字子句是单文字子句每次归结时优先选择单文字子句

49、进行归结，所以得到的归结每次归结时优先选择单文字子句进行归结，所以得到的归结式的文字数目必然比其另外一个父辈子句少。这有利于归结式的文字数目必然比其另外一个父辈子句少。这有利于归结式向空子句的方向生成，提高了式向空子句的方向生成，提高了效率效率 2022-5-25702 2 归结反演系统归结反演系统 归结反演的控制策略归结反演的控制策略 3 3单文字子句优先策略单文字子句优先策略 I(w) R(w)I(A)R(A) R(x) L(x)L(A) D(y) L(y) D(A) D(A)2022-5-25712 2 归结反演系统归结反演系统 归结反演的控制策略归结反演的控制策略 4 4线性输入形策略

50、线性输入形策略归结策略对参加归结的子句提出了如下限制：参加归结策略对参加归结的子句提出了如下限制：参加归结的两归结的两个子句中必须至少有一个是基本子句集中的子句个子句中必须至少有一个是基本子句集中的子句线性输入形策略可提高线性输入形策略可提高效率效率，但，但不完备不完备( (祖先过滤策略祖先过滤策略能使能使之完备）之完备）例见下页其它的归结策略如其它的归结策略如祖先过滤策略祖先过滤策略、模型策略模型策略、有序策略有序策略等。等。在具体应用中可根据实际情况选择适当的归结策略，有时可在具体应用中可根据实际情况选择适当的归结策略，有时可把几种策略组合在一起使用把几种策略组合在一起使用 2022-5-