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

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

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

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

4、020/9/1,6,1 推理技术概述,推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理 1）演绎推理 从全称判断推出特称判断或单称判断的过程，即从一般到个别的推理 演绎推理中最常用的形式是三段论法（大前提和小前提，及结论） 例如： （1）所有的推理系统都是智能系统一般的知识 （2）专家系统是推理系统个体的判断 （3）所以，专家系统是智能系统新判断 没有增加新的知识,2020/9/1,7,1 推理技术概述,推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理 2）归纳推理 人们对客观事物的认识总是由认识个别事物开始，进而认识事物的普遍规律，其中归纳推理起了

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

6、默认推理 2）归纳推理 枚举法归纳推理分完全归纳推理与不完全归纳推理 完全归纳推理在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性 完全归纳推理是必然性推理 不完全归纳推理只考察了相应事物的部分对象，就得出了结论 不完全推理得出的结论不具有必然性，属于非必然性推理,2020/9/1,10,1 推理技术概述,推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理 2）归纳推理 在两个或两类事物在许多属性上都相同的基础上，推出它们在其它属性上也相同，这就是类比法归纳推理 类比法归纳可形式化地表示为： A 具有属性a,b,c,d

7、,e B 具有属性a,b,c,d, B 也具有属性e,2020/9/1,11,1 推理技术概述,推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理 2）归纳推理 类比法的可靠程度决定于两个或两类事物的相同属性与推出的那个属性之间的相关程度，相关程度越高，则类比法的可靠性就越高 归纳推理是人类思维活动中最基本、最常用的一种推理形式 归纳推理增加了知识（在机器学习部分称为归纳学习）,2020/9/1,12,1 推理技术概述,推理的概念和类型 1从推出新判断的途径分：演绎推理、归纳推理、默认推理 3）归纳推理 默认推理又称为缺省推理，是在知识不完全的情况下假设某些条件已经具备所进

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

9、关系，然后进行逻辑推理，推理的结论或者为真，或者为假，这种推理就称为确定性推理 归结反演、基于规则的演绎系统等都是确定性推理,2020/9/1,14,1 推理技术概述,推理的概念和类型 2按推理时所用的知识的确定性来分： 确定性推理、不精确推理 1）不精确推理 （不确定推理） 在人类知识中，有相当一部分属于人们的主观判断，是不精确的和含糊的。由这些知识归纳出来的推理规则往往是不确定的 基于不确定的推理规则进行推理，形成的结论也是不确定的，这种推理称为不精确推理 专家系统中主要使用的是不精确推理,2020/9/1,15,1 推理技术概述,推理的概念和类型 3按推理过程中推出的结论是否单调增加，或

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

11、反而要否定它，使得推理退回到前面的某一步，重新开始非单调推理 一般非单调推理是在知识不完全的情况下进行的，由于知识不完全，为使推理进行下去，就要先做某些假设，并在此假设的基础上进行推理，当以后由于新知识的加入发现原先的假设不正确时，就需要推翻该假设以及由此假设为基础的一切结论，再用新知识重新进行推理,2020/9/1,17,1 推理技术概述,推理的概念和类型 4按推理中是否运用与问题有关的启发性知识可分： 启发式推理、非启发式推理 1）启发式推理 如果在推理过程中，运用与问题有关的启发性知识，即解决问题的策略、技巧及经验，以加快推理过程，提高搜索效率，这种推理过程称为启发式推理 A*、AO*等

12、算法就属于此类推理,2020/9/1,18,1 推理技术概述,推理的概念和类型 4按推理中是否运用与问题有关的启发性知识可分： 启发式推理、非启发式推理 2）非启发式推理 如果在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理，这种推理称为非启发式推理 这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题 图搜索策略中的宽度优先搜索法，虽然是完备的算法，但是对于复杂问题的求解，将出现“组合爆炸”现象，其搜索效率低,2020/9/1,19,1 推理技术概述,推理的控制策略 推理的控制策略主要是指推理方向的选择、推理时所用的搜索策略及冲突解决策略等 一般推理的控制策

13、略与知识表达方法有关 1推理方向 推理方向用于确定推理的驱动方式 根据推理方向的不同，可将推理分为正向推理、反向推理和正反向混合推理 无论按哪种方式进行推理，一般都要求系统具有一个存放知识的知识库（KB）、一个存放初始事实和中间结果的数据库（DB）和一个用于推理的推理机,2020/9/1,20,1 推理技术概述,推理的控制策略 1推理方向 (1) 正向推理 正向推理（事实驱动推理）是由已知事实出发向结论方向的推理 基本思想是：系统根据用户提供的初始事实，在知识库中搜索能与之匹配的规则即当前可用的规则，构成可适用的规则集RS，然后按某种冲突解决策略从RS中选择一条知识进行推理，并将推出的结论作为

14、中间结果加入到数据库DB中作为下一步推理的事实，在此之后，再在知识库中选择可适用的知识进行推理，如此重复进行这一过程，直到得出最终结论或者知识库中没有可适用的知识为止,2020/9/1,21,1 推理技术概述,推理的控制策略 1推理方向 （1）正向推理,是,2020/9/1,22,1 推理技术概述,推理的控制策略 1推理方向 （1）正向推理 正向推理简单、易实现，但目的性不强，效率低 需要用启发性知识解除冲突并控制中间结果的选取，其中包括必要的回溯 由于不能反推，系统的解释功能受到影响,2020/9/1,23,1 推理技术概述,推理的控制策略 1推理方向 （2）反向推理,2020/9/1,24

15、,1 推理技术概述,推理的控制策略 1推理方向 （2）反向推理 反向推理以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理 反向推理的基本思想是：首先提出一个假设目标，然后由此出发，进一步寻找支持该假设的证据，若所需的证据都能找到，则该假设成立，推理成功；若无法找到支持该假设的所有证据，则说明此假设不成立，需要另作新的假设,2020/9/1,25,1 推理技术概述,推理的控制策略 1推理方向 （2）反向推理 与正向推理相比，反向推理的主要优点是不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释 反向推理的缺点是在选择初始目标时具有很大的盲目性，若假设不正确，就有可能

16、要多次提出假设，影响了系统的效率 反向推理比较适合结论单一或直接提出结论要求证实的系统,2020/9/1,26,1 推理技术概述,推理的控制策略 1推理方向 （3）正反向混合推理,2020/9/1,27,1 推理技术概述,推理的控制策略 1推理方向 （3）正反向混合推理,正向推理 效率低，推出大量无关子目标,反向推理 假设的盲目性降低效率,正反向混合推理,2020/9/1,28,1 推理技术概述,推理的控制策略 1推理方向 （3）正反向混合推理 正反向混合推理的一般过程是：先根据初始事实进行正向推理以帮助提出假设，再用反向推理进一步寻找支持假设的证据，反复这个过程，直到得出结论为止 正反向混合

17、推理集中了正向推理和反向推理的优点，但其控制策略相对复杂,2020/9/1,29,1 推理技术概述,推理的控制策略 2搜索策略 推理时，要反复用到知识库中的规则，而知识库中的规则又很多，这样就存在着如何在知识库中寻找可用规则的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决 为了有效地控制规则的选取，可以采用各种搜索策略 常用搜索策略： 状态空间搜索（宽度优先搜索、深度优先搜索、有界深度优先搜索等） 启发式搜索等（第三章）,2020/9/1,30,1 推理技术概述,推理的控制策略 3冲突解决策略 在推理过程中，系统要不断地用数据库中的事实与知识库中的规则进行匹配，当

18、有一个以上规则的条件部分和当前数据库相匹配时，就需要有一种策略来决定首先使用哪一条规则，这就是冲突解决策略 冲突解决策略实际上就是确定规则的启用顺序,2020/9/1,31,1 推理技术概述,推理的控制策略 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均为真，这时规则1和规则2都与数据库相匹配，但因为规则2的条件部分包括了更多的限制，所以

19、具有较高的优先级 本策略是优先使用针对性较强的产生式规则,2020/9/1,32,1 推理技术概述,推理的控制策略 3冲突解决策略 (2) 规则排序 如果规则编排的顺序就表示了启用的优先级，则称之为规则排序 (3) 数据排序 数据排序就是把规则条件部分的所有条件排序，即按优先级次序编排起来，当发生冲突时，首先使用在条件部分包含较高优先级数据的规则 (4) 就近排序 就近排序就是把最近使用的规则放在最优先的位置。如果某一规则经常使用，则倾向于更多地使用这条规则,2020/9/1,33,1 推理技术概述,推理的控制策略 3冲突解决策略 (5) 上下文限制 上下文限制就是把产生式规则按它们所描述的上

20、下文分组，在某种上下文条件下，只能从与其相对应的那组规则中选择可应用的规则 不仅可以减少冲突，而且由于搜索范围小，也提高了推理的效率,2020/9/1,34,1 推理技术概述,推理的控制策略 3冲突解决策略 (6) 按匹配度排序 在不精确匹配中，为了确定两个知识模式是否可以进行匹配，需要计算这两个模式的相似程度，当其相似度达到某个预先规定的值时，就认为它们是可匹配的 相似度又称为匹配度，它除了可用来确定两个知识模式是否可匹配外，还可用于冲突解除。若有几条规则均可匹配成功，则可根据它们的匹配度来决定哪一个产生式规则可优先被应用,2020/9/1,35,1 推理技术概述,推理的控制策略 3冲突解决

21、策略 (6) 按条件个数排序 如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用，因为要求条件少的规则匹配时花费的时间较少 不同的系统，可使用上述这些策略的不同组合，目的是尽量减少冲突的发生，使推理有较快的速度和较高的效率 如何选择冲突解决策略完全是由启发性知识决定的,2020/9/1,36,2 归结反演系统,归结原理 在谓词演算（第二章）中，利用前面列出的等价式和永真蕴含式可以从已知的一些公式推导出新的公式，这个导出的公式叫做定理，在推导过程中使用的推理规则序列就成了该定理的一个证明 将要介绍的归结原理是定理证明的基础，它应用于称为子句的一种公式类的推理,2020/9/1

22、,37,2 归结反演系统,归结原理,难；繁,2020/9/1,38,2 归结反演系统,归结原理 1子句 谓词逻辑中，把原子公式及原子公式的否定统称为文字 【定义41】任何文字的析取式称为子句。 例如PQ、P（x，f(x)，y）Q(y)R(f(x) 都是子句 【定义42】不包含任何文字的子句称为空子句，表示为NIL 由于空子句不包含有文字，它不能被任何解释满足，所以空子句是永假的，不可满足的 由子句构成的集合称为子句集 谓词逻辑中，任何一个谓词公式都可以化成一个子句集,2020/9/1,39,2 归结反演系统,归结原理 1子句 将谓词公式化为子句集的步骤： (1)利用PQ = PQ；PQ =（P

23、Q）（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) 消去存在量词$ 如果存在量词不在任何一个全称量词的辖域内，则该存在量词不依赖于任何其它的变量，因此可用一个新的个体常量代替 如将($x)P（x）化为P(A) 如果存在量词是在全称量词的辖域内（如在公式(“y)（($x)P（x，y）中，变量x的取值依

24、赖于变量y的取值） 由Skolem函数表示依赖关系 注意，函数名应是原合式公式中没有的符号 （续）,2020/9/1,40,2 归结反演系统,归结原理 1子句 将谓词公式化为子句集的步骤： (5)将公式化为前束形把所有全称量词（已不留下任何存在量词，而且每个全称量词都有自己的变量）移到公式的左边，并使每个量词的辖域包含这个量词后面的整个部分，所得的公式称为前束形 (6)利用P（QR）=（PQ）（PR）；（PQ）（PR）= P（QR）等价关系将母式化为合取范式（子句的合取式） (7)略去全称量词母式中的变量被默认为是全称量词量化的变量 (8)消去合取符号，把母式用子句集表示 如：PQ可表示为成子

25、句集： P Q (9)子句变量标准化重新命名变量，使每个子句中的变量符号不同,2020/9/1,41,2 归结反演系统,归结原理 1子句 【例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)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

26、（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) 子句变量标准化后，最终的子句集为： P（x）S（x，f(x)） Q（y） P（w）B（w）,2020/9/1,42,2 归结反演系统,归结原理 2置换和合一 为了使用推理规则，如假言推理、假言三段论等，一个推理系统必须决定两个表达式是否相同或匹配： 两个表达式匹配当且仅当其语法是等价的 一个表

27、达式的项可以是常量、变量或函数，合一就是寻找项对变量的置换而使表达式一致的过程，合一是人工智能中很重要的过程 如，为了使公式( x)P（x）与P（A）匹配，可以用常量A代替变量x，从而使两个公式一致,2020/9/1,43,2 归结反演系统,归结原理 2置换和合一 置换可用有序对的集合s=t1/v1，t2/v2，tn/vn表示，其中ti/vi表示将表达式中所有的变量vi都用项ti代替，ti可以是变量、常量或函数 注意，一个变量不能用含有同一变量的项来代替 一般可用Es表示一个表达式E用一个置换s所得到的表达式的置换 如：P（z，f（w），A）= （P（x，f（y），A）s,2020/9/1,4

28、4,2 归结反演系统,归结原理 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 ,2020/9/1,45,2 归结反演系统,归结原理 2置换和合一 置换是可结合的 用s1 s2表示两个置换s1和 s2的合成，E表示一表达式，则有： （E s1）s2 = E（s1 s2） （s1 s2）s3= s1

29、（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,2020/9/1,46,2 归结反演系统,归结原理 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就可使上述公式集合一 如果s是Ei的任一合一者，又存在某个s，使得公式Eis=Eig s，则称g为公式集Ei的最简单合一者m

30、gu（Most General Unifier） 置换 B/y 为公式集P(x，f( y )，B), P(x , f(B)，B)的最简单合一者,2020/9/1,47,2 归结反演系统,归结原理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中，return FAIL else return E2/E1 (5) if E2是一个变量，return E1/E

31、2 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的合成,2020/9/1,48,2 归结反演系统,归结原理 3归结原理 归结原理又称为消解原理，它是定理证明基础 由谓词公式转化为子句集的过程中

32、可以看出，在子句集中子句之间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。若一个子句集中包含空子句，则这个子句集一定是不可满足的归结原理就是基于这一认识提出来的 【定义43】若P是原子谓词公式，则称P与P为互补文字,2020/9/1,49,2 归结反演系统,归结原理 3归结原理 (1) 基子句的归结 所谓基子句，是指没有变量的子句 【定义44】设C1与C2是子句集中的任意两个基子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并将二个子句余下的部分析取，构成一个新子句C12，则称一过程为归结，称C12为基子句C1和C2的归结式，称C1和C2为

33、C12的父辈子句,2020/9/1,50,2 归结反演系统,归结原理 3归结原理 【例42】设C1=PQR，C2=PST归结为： C12=QRST,2020/9/1,51,2 归结反演系统,归结原理 3归结原理(多子句则逐步归结) 【例43】设子句集S=PQ，QR，P，RT ，则其归结过程如图 归结结果为T,2020/9/1,52,2 归结反演系统,归结原理 3归结原理 (2)含有变量的子句的归结 在谓词逻辑中，子句中含有变量 为将归结原理应用于含有变量的子句，应找出一个置换，作用于给定的两个子句，使它们包括互补的文字，然后才能进行归结 例:子句集S=P(x)Q(x)，P(A)R(y)，子句集

34、中的两个子句不能直接归结，但若对子句集先进行置换s=A/x，则两个子句分别为P(A)Q(A)和P(A)R(y)，这时再进行归结，归结结果为Q(A)R(y),2020/9/1,53,2 归结反演系统,归结原理 3归结原理 【定义45】设C1和C2是两个没有相同变量的子句，并分别表示成两个文字集合Li和Mi，li是Li的一个子集，mi是Mi的一个子集，若s是集合li和mi的并集的最简合一者，则称 C12 = Li-lisMi-mi s 为C1和C2的归结式。 当两个子句作归结时，子集li和mi的选取可能有多种形式，所以得到的归结式不是唯一的,2020/9/1,54,2 归结反演系统,归结原理 3归

35、结原理 例:设有两个子句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),2020/9/1,55,2 归结反演系统,归结原理 3归结原理 例的归结过程：,2020/9/1,56,2 归结反演系统,归结反演,初始公式,目标公式,初始子句集,目标子句,难；繁,初始子句集,空子句,可判定的！,永真：半可判定的,2020/9/1,57,2 归结反演系统,归结反演 归结

36、反演就是利用归结和反演实现定理的证明 具体过程： (1) 将定理证明的前提谓词公式转化为子句集F (2) 将求证的目标表示成合适的谓词公式G（目标公式） (3)将目标公式的否定式G转化成子句的形式，并加入到子句集F中，得到子句集S (4) 应用归结原理对子句集中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若归结得到一个空子句NIL，则停止归结 证明了G为真,2020/9/1,58,2 归结反演系统,归结反演 【例44】 已知前提为F:(x)P(x,y)Q(y)(y)R(y)S(x,y) 求证结论G:(x)R(x)(x)(y)P(x,y)Q(y)成立 证明：先按前面所讲的方

37、法将前提和结论化为子句集： 前提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),2020/9/1,59,2 归结反演系统,归结反演 【例44】 归结过程 经过归结最后得到NIL， 所以结论G成立,2020/9/1,60,2 归结反演系统,归结反演 【例45】已知: 能阅读的都是有文化的; 海豚是没有文化的; 某些海豚是有智能的; 用归结反演法证明:某些有智能的并不能阅读 证明：设 R(x)：x能阅读 L(x): x有文化 D(x): x是海豚 I(x): x有智能,2020/9/1,61,2

38、 归结反演系统,归结反演 【例45】 将前提形式化地表示为： (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),2020/9/1,62,2 归结反演系统,归结反演 【例45】 归结后得到空子句NIL， 证明完毕,2020/9/1,63,2 归结反演系统,归结反演 归结反演过程主要就是证明一个集合S是不可满足的过程，即从集合S中归结出空子句的过程 算法描述： 过程RESOLUTION (1

39、) CLAUSESS (2) Until NIL是CLAUSES的成员，do: (3) Begin (4) 在CLAUSES中选择两个不同的可归结的子句Ci和Cj (5) 计算Ci和Cj的归结式Cij (6) CLAUSES附加Cij到CLAUSES产生的子句集 （7）end,2020/9/1,64,2 归结反演系统,归结反演的控制策略 对子句集进行归结时，关键的一步是从子句集中找出可进行归结的子句 由于事先不知道哪两个子句可以进行归结，更不知道通过对哪些子句对的归结可以尽快地得到空子句，因而必须对子句集中的所有子句逐对地进行比较，对任何一对可归结的子句对都进行归结，这样的效率是很低的 归结反

40、演的控制策略,2020/9/1,65,2 归结反演系统,归结反演的控制策略 1宽度优先策略 基本思想：首先从基本子句集生成所有的归结式，称为第一级归结式。在这一轮归结中，子句集中的每个子句都要和子句集中的其它子句比较以确定是否进行归结。然后，从基本子句集和第一级归结式生成第二级归结式。以此类推，直到出现了空子句或者不能再归结为止 宽度优先策略是完备的，但会归结出许多无用的子句，而且有一些归结式还是重复的，所以是低效的，即浪费时间又多占空间,2020/9/1,66,2 归结反演系统,归结反演的控制策略 1宽度优先策略,2020/9/1,67,2 归结反演系统,归结反演的控制策略 2支持集策略 支

41、持集策略是一种改进的归结策略 对参加归结的子句提出了如下限制：每一次归结时，其父辈子句中至少有一个是由目标公式的否定所得到的子句或者是它们的后代（即支持集） 可以证明，支持集策略是完备的，即若子句集是不可满足的，则由支持集策略一定可以归结出空子句 支持集策略相当于在宽度优先策略中引入了约束条件，因此效率比宽度优先策略要高,2020/9/1,68,2 归结反演系统,归结反演的控制策略2支持集策略,2020/9/1,69,2 归结反演系统,归结反演的控制策略 3单文字子句优先策略 如果一个子句只包含一个文字，则称它为单文字子句 单文字子句优先策略要求参加归结的子句中必须至少有一个是单文字子句 每次

42、归结时优先选择单文字子句进行归结，所以得到的归结式的文字数目必然比其另外一个父辈子句少。这有利于归结式向空子句的方向生成，提高了效率,2020/9/1,70,2 归结反演系统,归结反演的控制策略 3单文字子句优先策略,2020/9/1,71,2 归结反演系统,归结反演的控制策略 4线性输入形策略 归结策略对参加归结的子句提出了如下限制：参加归结的两个子句中必须至少有一个是基本子句集中的子句 线性输入形策略可提高效率，但不完备(祖先过滤策略能使之完备） 例见下页 其它的归结策略如祖先过滤策略、模型策略、有序策略等。在具体应用中可根据实际情况选择适当的归结策略，有时可把几种策略组合在一起使用,20

43、20/9/1,72,2 归结反演系统,归结反演的控制策略 4线性输入形策略,2020/9/1,73,2 归结反演系统,应用归结反演求取问题的答案 归结反演除了可用于定理证明外，还可用来求取问题的答案，其思想与定理证明类似 用归结反演求取问题答案的一般步骤是： (1) 把已知前提用谓词公式表示出来，并且化为子句集，设该子句集为S (2) 把目标也用谓词公式表示出来 (3)在目标公式的否定的子句形式中，附加上该子句的否定（即目标公式否定之否定）。然后一起加入到子句集S中，得到子句集S (4) 对S进行归结，形成归结反演树修改的证明树 (5) 用根部的子句作为解答子句,2020/9/1,74,2 归

44、结反演系统,应用归结反演求取问题的答案 【例46】已知：F1：王(Wang)先生是小李(Li)的老师， F2：小李与小张(Zhang)是同班同学。 F3：如果x和y是同班同学，则x的老师就是y的老师 求：小张的老师是谁？ 解：先定义谓词：T（x，y）：x是y的老师 C（x，y）：x与y是同班同学 把已知前提及目标表示成谓词公式： 前提 F1：T（Wang，Li） F2：C（ Li，Zhang） F3：C（x，y）T（z，x）T（z，y） 目标 G：(x)T(x，Zhang) G的否定：(x)T(x，Zhang),2020/9/1,75,2 归结反演系统,应用归结反演求取问题的答案 【例46】将

45、以上前提和目标的否定化成子句集： F1:T(Wang,Li) F2:C(Li,Zhang) F3:C(x,y)T(z,x)T(z,y) 目标重言式：T(u,Zhang)T(u,Zhang) 根部子句：T(Wang,Zhang)， 这就是答案， 表示小张（Zhang）的老师是王（Wang）,2020/9/1,76,2 归结反演系统,应用归结反演求取问题的答案 【例47】已知事实如下： (1) 对所有的x和y，如果x是y的父辈而y是z的父辈，则x是z的祖辈。 (2) 每个人都有父辈。 问：是否存在具体的x和y，使得x是y的祖辈？ 解：先定义谓词： P（x，y）：x是y的父辈 G（x，y）：x是y的

46、祖辈 把已知前提及目标表示成谓词公式： 前提1：P（x，y）P（y，z）G(x，z) 前提2：（y）（x）P（x，y） 目标G：（x）（y）G（x，y） G的否定：（x）（y）G（x，y）,2020/9/1,77,2 归结反演系统,应用归结反演求取问题的答案 【例47】将前提和目标的否定化成子句集： 前提1：P（x，y） P（y，z）G(x，z) 前提2：P（f(w)，w） G的否定： G（u，v） 把它添加到目标公式否定之否定的子句中去，得到重言式： G（u，v）G（u，v）。 通过归结，在根部得到子句：G(f(f(v)，v)，这就是答案，表示v的父辈的父辈就为v的祖辈,2020/9/1,7

47、8,2 归结反演系统,应用归结反演求取问题的答案 【例47】,2020/9/1,79,2 归结反演系统,应用归结反演求取问题的答案 目标公式中含有全称量词稍复杂些 基于归结原理的归结反演推理比较简单且又便于在计算机上实现，所以对自动定理证明领域影响较大。但是归结反演要求把前提、结论等所有逻辑表达式转化为子句集，因此丧失了许多有用的信息 如逻辑式PQ与子句PQ在逻辑上是等价的，但它们所表达的信息是不同的，相比之下，PQ的含义更易于理解 提出多种非子句定理证明方法 如自然演绎和基于规则的演绎法等,2020/9/1,80,3 基于规则的演绎推理,知识一般是由蕴含式直接表示的，但在归结反演中，必须首先

48、将它们转化为子句的形式，所以这种推理是比较低效的 基于规则的演绎推理则是一种直接的推理方法。它不再把有关的知识转化为子句集，而是把有关问题的知识和信息划分为规则与事实两种类型 规则：包含蕴含形式的表达式表示 事实：无蕴含式的表达式表示 画出相应的与/或图，然后通过规则进行演绎推理,2020/9/1,81,3 基于规则的演绎推理,基于规则的演绎推理可分为正向演绎推理、反向演绎推理和正反向混合演绎推理 在正向演绎推理中，作为F规则用的蕴含式对事实的总数据库进行操作运算，直至得到该目标公式的一个终止条件为止 在反向演绎推理中，作为B规则用的蕴含式对目标的总数据库进行操作运算，直至得到包含这些事实的终

49、止条件为止 在双向演绎推理中，分别从两个方向应用不同的规则（F规则和B规则）进行操作运算,2020/9/1,82,3 基于规则的演绎推理,正向演绎推理 正向演绎推理对应于41中介绍的正向推理，它是从已知事实出发，反复尝试所有可利用的规则（F规则）进行演绎推理，直至得到某个目标公式的一个终止条件为止,2020/9/1,83,3 基于规则的演绎推理,正向演绎推理 （1）事实表达式及其与或图表示 正向演绎要求事实用不包含蕴含符号“”的与/或形表示 一个表达式转化为标准的与/或形的步骤如下： 利用等价式PQ与PQ消去蕴含符“” 把否定符号“”移到每个谓词符号的前面 变量标准化，即重新命名变量，使不同量

50、词约束变量有不同的名字 引入Skolem函数消去存在量词 将公式化为前束形 略去全称量词(默认事实表达式中尚存的变量是全称量词量化的变量) 重新命名变量，使同一变量不出现在不同的主要合取式中,2020/9/1,84,3 基于规则的演绎推理,正向演绎推理 （1）事实表达式及其与或图表示 如表达式:（x）(y)Q(y,x)(R(y)P(y)S(x，y) 转化为标准的与/或形: Q(z,A) R(y) P(y) S(A，y) 事实表达式的标准与/或形树:,2020/9/1,85,3 基于规则的演绎推理,正向演绎推理 （1）事实表达式及其与或图表示 在与/或图中，结点表示事实表达式及其子表达式 根结点

51、表示整个表达式，叶结点表示表达式中的单个文字 对于一个表示析取表达式（E1E2En）的结点，用一个n连接符（图中的半圆弧）连接它的n个子表达式结点； 对于一个表示合取表达式（E1E2En）的结点，则直接用单线连接符与它的n个子表达式结点相连 事实表达式:用n连接符（一个合取记号）来分解析取式,2020/9/1,86,3 基于规则的演绎推理,正向演绎推理 （1）事实表达式及其与或图表示 一重要性质：由变换表达式得到的一组子句则可从与或图中读出，每子句相当于与/或图的一个解图，每个子句是由叶结点组成的公式 从上上页可以读出上例表达式的三个子句： Q(z,A) S(A，y) R(y) S(A，y)

52、P(y) 这三个子句正是原表达式化成的子句集与/或图可看成是一组子句的一个简洁的表达形式,2020/9/1,87,3 基于规则的演绎推理,正向演绎推理 （2）F规则的表示形式 基于规则的正向演绎推理中，通常要求F规则具有以下形式： L W 具体要求如下： L是单文字，W是任意的与或形表达式 L和W中的所有变量都是全称量词量化的，默认的全称量词作用于整个蕴含式 各条规则的变量各不相同，而且规则中的变量与事实表达式中的变量也不相同,2020/9/1,88,3 基于规则的演绎推理,正向演绎推理 （2）F规则的表示形式 将F规则的左部限制为单文字，是因为在进行演绎推理时，要用F规则作用于表示事实的与/

53、或图，而该与/或图的叶结点都是单文字，这样就可用F规则的左部与叶结点进行匹配，大大简化了规则的应用过程,2020/9/1,89,3 基于规则的演绎推理,正向演绎推理 （2）F规则的表示形式 变换成标准形式的步骤： 暂时消去蕴含符号“” 把否定号“”移到每个谓词的前面 引入Skolem函数消去存在量词 将公式化为前束形，并略去全称量词 恢复为蕴含式,2020/9/1,90,3 基于规则的演绎推理,正向演绎推理 （2）F规则的表示形式 变换成标准形式的例： 原公式(x)(y)(z)P(x,y,z)(u)Q(x,u) 消蕴含符(x)(y)(z)P(x,y,z)(u)Q(x,u) 否定号移入(x)(y

54、)(z)P(x,y,z)(u)Q(x,u) Skolem函数(x)(y)P(x,y,f(x,y)(u)Q(x,u) 前束形/略全称量词P(x,y,f(x,y)Q(x,u) 恢复蕴含式P(x,y,f(x,y)Q(x,u),2020/9/1,91,3 基于规则的演绎推理,正向演绎推理 （3）目标公式的表示形式 在基于规则的正向演绎推理中，要求目标公式用子句表示，否则就要化成子句形式,2020/9/1,92,3 基于规则的演绎推理,正向演绎推理 （4）推理过程 基于规则的正向演绎推理应用F规则作用于表示事实的与/或图，改变与/或图的结构，从而产生新的事实，直至推出了目标公式，则推理就成功结束 正向演

55、绎中的目标公式规定为文字的析取式，当一个目标文字和与/或图中的一个文字匹配时，可以将表示该目标文字的结点通过匹配弧连接到与/或图中相应的文字的结点上 表示目标文字的结点为目标结点，当演绎产生的与/或图包括一个在目标结点上结束的解图时，推理便成功结束,2020/9/1,93,3 基于规则的演绎推理,正向演绎推理 （4）推理过程 推理过程为： 首先用与/或图把已知事实表示出来 用F规则的左部和与/或图的叶结点进行匹配，并将匹配成功的F规则加入到与/或图中，即利用F规则转换与/或图 重复第步，直到产生一个含有以目标结点作为终止结点的解图为止,2020/9/1,94,3 基于规则的演绎推理,正向演绎推

56、理 （4）推理过程 【例48】设已知事实为：AB F规则为：ACD ，BEG 目标公式为：CGF 证明：1.将事实表达式用与/或图表示,2020/9/1,95,3 基于规则的演绎推理,正向演绎推理 （4）推理过程 【例48】证明 2.用F规则的左部与上页中的叶结点匹配，并转换与或图新与/或图 图中包括一个在目标结点上结束的解图，该解图对应的子句为CG（注意此子句与目标公式CGF不同，但比目标公式更一般，所以目标公式成立）,2020/9/1,96,3 基于规则的演绎推理,正向演绎推理 （4）推理过程 【例48】证明,2020/9/1,97,3 基于规则的演绎推理,正向演绎推理 （4）推理过程 【

57、例48】验证其推理的正确性，再用归结反演来证明 由已知事实、F规则及目标的 否定所构成的子句集为： AB AC，AD BE，BG C，G，F 子句的归结过程：（归结得空子句NIL）,2020/9/1,98,3 基于规则的演绎推理,正向演绎推理 （5）含有变量的表达式 如果事实表达式、规则和目标表达式中有变量，则在推理中需要用最一般的合一进行变量的代换,2020/9/1,99,3 基于规则的演绎推理,正向演绎推理 （5）含有变量的表达式 【例49】设已知 事实为： P(A)Q(A)R(A) F规则为：R1：P(x)S(x) R2：Q(y)N(y) 证明目标公式：S(z)N(z) 证明： 解图对应

58、的子句为： S(z) N(z),2020/9/1,100,3 基于规则的演绎推理,正向演绎推理 （5）含有变量的表达式 【例49】验证（归结反演） 已知事实、F规则及目标的否定 所构成的子句集为： P(A)Q(A)，P(A)R(A) P(x)S(x) Q(y)N(y) S(z)，N(z) 归结反演图： 归结出空子句，证明目标公式成立,2020/9/1,101,3 基于规则的演绎推理,正向演绎推理 （5）含有变量的表达式 当事实表达式、F规则和目标表达式中包含变量时，只有当解图中所用的置换是一致时，该解图对应的子句才成立 在【例49】解图中使用的置换A/x，A/z和A/y，A/z是一致的，所以该

59、子句成立 将两个置换的合一复合A/x，A/y，A/z作用于子句S(z)N(z)得到：S(A)N(A)，这才是真正的结论,2020/9/1,102,3 基于规则的演绎推理,正向演绎推理 （5）含有变量的表达式 【定义46】设有一个置换集U=u1,u2,un ,每个ui是一个置换对的集合， ui=ti1/vi1 , ti2 /vi2, , tim (i)/vim(i) 其中t为项，v为变量， 令： U1=( v11, ,v1m(1),v21, ,v2m(2) ,vnm(n) U2=( t11, , t1m(1), t21, , t2m(2) ,tnm(n) 则置换U是一致的充要条件是U1和U2可合一。而U的合一复合u=mgu(U1,U2),2020/9/1,103,3 基于规则的演绎推理,正向演绎推理 （5）含有变量的表达式 置换的一致性和置换的合一复合例： 1)u1=A/x,A/z, u2=A/y, A/z, 则U=u1，u2是一致的，其合一复合为 A/x，A/y, A/z 2)u