人工智能原理ch4.1_经典逻辑推理

1、2022-3-31人工智能原理第四讲第四讲经典逻辑推理经典逻辑推理主讲：王祖喜主讲：王祖喜华中科技大学图像所华中科技大学图像所2022-3-32经典逻辑推理经典逻辑推理 经典逻辑推理是根据经典逻辑的逻辑规则进行经典逻辑推理是根据经典逻辑的逻辑规则进行的 一 种 推 理 ， 又 称 为 机 械的 一 种 推 理 ， 又 称 为 机 械 - 自 动 定 理 证 明自 动 定 理 证 明(mechanical-automatic theorem proving),主要推理主要推理方法有自然演绎推理，归结演绎推理及与或形演方法有自然演绎推理，归结演绎推理及与或形演绎推理等。由于这种推理是基于经典逻辑的

2、，其绎推理等。由于这种推理是基于经典逻辑的，其真值只有真和假两种，因此它是一种精确推理。真值只有真和假两种，因此它是一种精确推理。学习目的：学习目的： 学习学习运用知识进行推理，求解问题运用知识进行推理，求解问题 。 2022-3-33主要讲述内容：主要讲述内容： 1. 简述与推理相关的知识：如推理方式及分类、简述与推理相关的知识：如推理方式及分类、推理控制策略、模式匹配、冲突消解策略、搜索推理控制策略、模式匹配、冲突消解策略、搜索策略等。策略等。 2. 经典逻辑推理：自然演绎推理、归结演绎推理经典逻辑推理：自然演绎推理、归结演绎推理和与和与/或形演绎推理。或形演绎推理。2022-3-34 什

3、么是推理什么是推理 推理推理从已知事实出发，运用已掌握的知识，找出其中蕴从已知事实出发，运用已掌握的知识，找出其中蕴含的事实，或归结出新的事实，这一过程称为推理。含的事实，或归结出新的事实，这一过程称为推理。推理机推理机在人工智能中，推理是由程序实现的，称为推理机。在人工智能中，推理是由程序实现的，称为推理机。推理包括两种判断：一种是已知的判断，它包括已掌握推理包括两种判断：一种是已知的判断，它包括已掌握的与求解问题有关的知识以及关于问题的已知事实；另的与求解问题有关的知识以及关于问题的已知事实；另一种是由已知判断推出的新判断，即推理的结论。一种是由已知判断推出的新判断，即推理的结论。推理的基

4、本任务：是从一种判断推出另一种判断。推理的基本任务：是从一种判断推出另一种判断。1 推理的基本概念2022-3-35一般而言，推理有一下五种划分方式：一般而言，推理有一下五种划分方式：.演绎推理、归结推理、默认推理演绎推理、归结推理、默认推理（从新判断推（从新判断推出的途径来划分）出的途径来划分）演绎推理演绎推理从全称判断推导出特称判断或单称判从全称判断推导出特称判断或单称判断的过程，即由一般性知识推出适合于某一具体情断的过程，即由一般性知识推出适合于某一具体情况的结论。这是一种从一般到个别的推理。演绎推况的结论。这是一种从一般到个别的推理。演绎推理有多种形式，经常用的是三段论式，它包括：理有

5、多种形式，经常用的是三段论式，它包括：1) 大前提，这是已知的一般性知识或假设；大前提，这是已知的一般性知识或假设；2) 小前提，这是关于所研究的具体情况或个别小前提，这是关于所研究的具体情况或个别事实的判断；事实的判断；推理的方式及其分类2022-3-363) 结论，这是由大前提推出的适合于小前提所结论，这是由大前提推出的适合于小前提所示情况的新判断。示情况的新判断。例如：例如： 1) 足球运动员的身体都是强壮的；足球运动员的身体都是强壮的； 2) 高波是一名足球运动员；高波是一名足球运动员； 3) 所以，高波的身体是强壮的。所以，高波的身体是强壮的。这就是一个三段论推理，其中，这就是一个三

6、段论推理，其中，(1) 是大前提，是大前提，(2)是小前提，是小前提，(3) 是经演是经演 绎推出的结论。结论绎推出的结论。结论“高高波的身体是强壮的波的身体是强壮的”事实上是蕴含于事实上是蕴含于“足球运动足球运动员的身体都是强壮的员的身体都是强壮的”这一大前提中的。它没有这一大前提中的。它没有超出超出2022-3-37 大前提所断定的范围。这是演绎推理的一个典大前提所断定的范围。这是演绎推理的一个典型特征，即在任何情况下，由演绎推理导出的型特征，即在任何情况下，由演绎推理导出的结论都是蕴含在大前提的一般性知识中的。因结论都是蕴含在大前提的一般性知识中的。因此，此，只只要大前提和小前提是正确的

7、，则由它们要大前提和小前提是正确的，则由它们推导出来的结论也必然是正确的。推导出来的结论也必然是正确的。 演绎推理是人工智能中的一种重要推理方式，在演绎推理是人工智能中的一种重要推理方式，在直到目前研制成功的各类智能系统中，大多是直到目前研制成功的各类智能系统中，大多是用演绎推理实现的。用演绎推理实现的。2022-3-38归结推理归结推理归结推理是从足够多的事例中归结出归结推理是从足够多的事例中归结出一般性结论的推理过程，是一种从个别到一般的推一般性结论的推理过程，是一种从个别到一般的推理。归结推理又分为完全归结和不完全归结两种。理。归结推理又分为完全归结和不完全归结两种。完全归结：指在进行归

8、结时考察了相应事物的全完全归结：指在进行归结时考察了相应事物的全部对象，并根据这些对象是否都有某种属性，从部对象，并根据这些对象是否都有某种属性，从而推出这种事物是否具有这个属性。而推出这种事物是否具有这个属性。 例如例如: 某厂进行产品质量检查，如果对每一件某厂进行产品质量检查，如果对每一件产品都进行了严格检查，并且是合格的，则推产品都进行了严格检查，并且是合格的，则推导出结论该厂的产品是合格的。导出结论该厂的产品是合格的。不完全归结：指只考察了相应事物的部分对象，不完全归结：指只考察了相应事物的部分对象，就得出了结论。就得出了结论。2022-3-39默认推理默认推理又称缺省推理，它是在知识

9、不完全的又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。情况下假设某些条件已经具备所进行的推理。在默认推理过程中，如果到某一时刻发现原先所在默认推理过程中，如果到某一时刻发现原先所作的默认不正确，则就要撤销所作默认，以及由作的默认不正确，则就要撤销所作默认，以及由此默认推出的所有结论重新按新情况进行推理。此默认推出的所有结论重新按新情况进行推理。. 确定性推理，不确定性推理确定性推理，不确定性推理（按推理时所用知识（按推理时所用知识的确定性来划分）的确定性来划分） 确定性推理确定性推理 指推理时所用的知识都是精确的，指推理时所用的知识都是精确的，推出的结论也是确定的，其

10、真值或为推出的结论也是确定的，其真值或为“真真”，或为，或为“假假”，没有第三种情况出现。，没有第三种情况出现。下面将要讨论的经典逻辑推理就属于这一类。下面将要讨论的经典逻辑推理就属于这一类。2022-3-310 不确定性推理不确定性推理指推理时所用的知识不都是精确的，指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于推出的结论也不完全是肯定的，其真值位于“真真”和和“假假”之间，命题的外延模糊不清。之间，命题的外延模糊不清。这里我们要特别强调不确定性推理。自亚里士多德这里我们要特别强调不确定性推理。自亚里士多德建立第一个演绎公理系统以来，经典逻辑与精确数建立第一个演绎公理

11、系统以来，经典逻辑与精确数学的建立与发展为人类科学技术的发展起了巨大的学的建立与发展为人类科学技术的发展起了巨大的作用。然而，现实世界中的事物和现象大都是不严作用。然而，现实世界中的事物和现象大都是不严格、不精确的，许多概念是模糊的，很难用精确的格、不精确的，许多概念是模糊的，很难用精确的数学模型来表示和处理。因此。近几年来，各种非数学模型来表示和处理。因此。近几年来，各种非经典逻辑迅速崛起，人工智能亦把不精确知识的表经典逻辑迅速崛起，人工智能亦把不精确知识的表示与处理作为重要的研究课题。另外，从人类思维示与处理作为重要的研究课题。另外，从人类思维活动的特征来看，人们经常是在知识不完全、不精活

12、动的特征来看，人们经常是在知识不完全、不精确的情况下进行多方位的思考及推理的。因此，要确的情况下进行多方位的思考及推理的。因此，要使计算机模拟人类的思维活动，就必须使其具有不使计算机模拟人类的思维活动，就必须使其具有不确定性推理的能力。确定性推理的能力。2022-3-311. 单调推理、非单调推理单调推理、非单调推理（按推理过程中推出的结（按推理过程中推出的结论是否单调的增加来划分）论是否单调的增加来划分） 单调推理单调推理指在推理过程中随着推理的向前推进指在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目

13、标，在推理过程中不会出现并且越来越接近最终目标，在推理过程中不会出现反复的情况，即不会由于新知识的加入而否定前面反复的情况，即不会由于新知识的加入而否定前面推出的结论，使推理又退回到前面的一步。推出的结论，使推理又退回到前面的一步。非单调推理非单调推理指在推理过程中由于新知识的加入，指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。推理退回到前面的某一步，重新开始。2022-3-312. 启发式推理、非启发式推理启发式推理、非启发式推理（按推理中是否运用（按推理中是否运用与问题有关的启发性知

14、识分）与问题有关的启发性知识分） 启发式推理启发式推理推理中运用与问题有关的启发性知推理中运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门，对解的特性识，即解决问题的策略、技巧、窍门，对解的特性及规律的估计等实践经验和知识以加快推理过程、及规律的估计等实践经验和知识以加快推理过程、提高搜索效率，这种推理称为启发式推理。提高搜索效率，这种推理称为启发式推理。非启发式推理非启发式推理比如穷举式推理等。比如穷举式推理等。2022-3-313. 基于知识的推理、统计推理、直觉推理基于知识的推理、统计推理、直觉推理（从方（从方法论的角度划分）法论的角度划分）基于知识的推理基于知识的推理根据已掌握

15、的事实，通过运根据已掌握的事实，通过运用知识进行的推理。用知识进行的推理。统计推理统计推理根据对某事物的数据统计进行的推根据对某事物的数据统计进行的推理理(相当于归纳推理相当于归纳推理)。直觉推理直觉推理又称常识性推理，是根据常识进行又称常识性推理，是根据常识进行的推理。的推理。2022-3-314推理过程是一个思维过程，即求解问题的过程，推理过程是一个思维过程，即求解问题的过程，求解问题的质量和效率不仅依赖于所采用的求解求解问题的质量和效率不仅依赖于所采用的求解方法，而且还依赖于求解问题的策略，即推理的方法，而且还依赖于求解问题的策略，即推理的控制策略。控制策略。推理的控制策略主要包括：推理

16、方向、搜索策略、推理的控制策略主要包括：推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。冲突消解策略、求解策略及限制策略等。推理的控制策略2022-3-315推理方向用于确定推理的驱动方式，分为正向推推理方向用于确定推理的驱动方式，分为正向推理、逆向推理、混合理、逆向推理、混合 推理和双向推理四种。无论推理和双向推理四种。无论按哪种方向进行推理，一般都要求系统具有一个按哪种方向进行推理，一般都要求系统具有一个存放知识的知识库，一个存放初始已知事实及问存放知识的知识库，一个存放初始已知事实及问题状态的数据库和一个用于推理的与推理机。题状态的数据库和一个用于推理的与推理机。推理方向2022

17、-3-316正向推理正向推理是以已知事实作为出发点的一种推理，正向推理是以已知事实作为出发点的一种推理，又称数据驱动推理、前向链推理及前件推理等。又称数据驱动推理、前向链推理及前件推理等。. 正向推理的基本思想：正向推理的基本思想：从用户提供的初始已知事实出发，在知识库从用户提供的初始已知事实出发，在知识库KB中中找出当前可适用的知识，构成可适用知识集找出当前可适用的知识，构成可适用知识集KS，然后按某种冲突消解策略从然后按某种冲突消解策略从KS中选出一条知识进中选出一条知识进行推理，并将推出的新事实加入到数据库中作为行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，在此之后再在

18、知识库中下一步推理的已知事实，在此之后再在知识库中选取可适用的知识进行推理，如此重复，直到求选取可适用的知识进行推理，如此重复，直到求得了所要求的解，或者知识库中再无可适用的知得了所要求的解，或者知识库中再无可适用的知识为止。识为止。 2022-3-317正向推理过程正向推理过程算法描述：算法描述：开始开始把初始已知事实送入把初始已知事实送入DBDB中包含问题的解？中包含问题的解？KB中有可适用知识？中有可适用知识？KS空？空？把把KB中所有可适用知识都选出来送入中所有可适用知识都选出来送入KS推出的是新事实？推出的是新事实？按冲突消解策略从按冲突消解策略从KS中选出一条知识进行推理中选出一条

19、知识进行推理将该新事实加入到将该新事实加入到DB中中成功，退出成功，退出把用户提供的新事实加入把用户提供的新事实加入DB中中用户用户 可补充新事实？可补充新事实？失败，退出失败，退出YYYYYNNNNN2022-3-318. 与正向推理相关的问题：与正向推理相关的问题：匹配方法匹配方法在以上推理过程中，需要从知识库在以上推理过程中，需要从知识库 KB 中选出可适用的知识，这就要用知识库中的知识与数中选出可适用的知识，这就要用知识库中的知识与数据库中的已知事实进行匹配，为此需确定据库中的已知事实进行匹配，为此需确定匹配方法匹配方法。 搜索策略搜索策略为了进行匹配，就要查找知识，这就牵为了进行匹配

20、，就要查找知识，这就牵涉到按什么路线进行查找的问题，既按什么涉到按什么路线进行查找的问题，既按什么搜索策略搜索策略搜索知识库。搜索知识库。冲突消解策略冲突消解策略如果适用的知识只有一条，这比较如果适用的知识只有一条，这比较简单，系统立即就可用它进行推理，并将推出的新事简单，系统立即就可用它进行推理，并将推出的新事实送入数据库实送入数据库DB中；但是，如果当前适用的知识有多中；但是，如果当前适用的知识有多条，应该先用那一条条，应该先用那一条? 这是推理中的一个重要问题，这是推理中的一个重要问题，称为称为冲突消解策略冲突消解策略。总之，为了实现正向推理，有许多具体问题需要解决。总之，为了实现正向推

21、理，有许多具体问题需要解决。2022-3-319例例: 设在综合数据库中存放有下列已知事实：设在综合数据库中存放有下列已知事实：该动该动物身上有暗斑点，长脖子，长腿，有奶，有蹄物身上有暗斑点，长脖子，长腿，有奶，有蹄且假且假设综合数据库中的已知事实与规则库中的知识是从设综合数据库中的已知事实与规则库中的知识是从第一条开始，逐条第一条开始，逐条 进行匹配的，则推理机构的工作进行匹配的，则推理机构的工作过程如下：过程如下： 从规则库中取出第一条规则从规则库中取出第一条规则r1，检查前提条件，检查前提条件与综合数据库中的已知事实不匹配；取第二条规与综合数据库中的已知事实不匹配；取第二条规则则r2，r

22、2的前提的前提“该动物有奶该动物有奶”与综合数据库中与综合数据库中事实匹配，则事实匹配，则rr被执行，其结论被加入综合数据被执行，其结论被加入综合数据库中，此时综合数据库中的事实为：库中，此时综合数据库中的事实为：该动物身上该动物身上有暗斑点，长脖子，长腿，有奶，有蹄，是哺乳有暗斑点，长脖子，长腿，有奶，有蹄，是哺乳动物动物正向推理求解过程2022-3-320 接着取接着取r3 r4 r5 r6 都不匹配，取到都不匹配，取到r7时，时，匹配成功，则将匹配成功，则将r7的结论加入综合数据库：的结论加入综合数据库：该该动物身上有暗斑点动物身上有暗斑点,长脖子长脖子,长腿长腿,有奶有奶,有蹄有蹄,是

23、哺是哺乳动物乳动物,是有蹄动物是有蹄动物 接着取规则，取到接着取规则，取到r11时，匹配成功，发现时，匹配成功，发现其前提条件与综合数据库完全匹配，则确定该其前提条件与综合数据库完全匹配，则确定该动物是：动物是：长颈鹿长颈鹿 至此，问题的求解结束了。至此，问题的求解结束了。2022-3-321逆向推理是以某个假设目标作为出发点的一种推理，逆向推理是以某个假设目标作为出发点的一种推理，又称为目标驱动推理、逆向链推理及后件推理等。又称为目标驱动推理、逆向链推理及后件推理等。. 逆向推理的基本思想：逆向推理的基本思想：首先选定一个假设目标，然后寻找支持该假设的证首先选定一个假设目标，然后寻找支持该假

24、设的证据，若所需的证据都能找到，则说明原假设成立；据，若所需的证据都能找到，则说明原假设成立；若无论如何都找不到所需证据，说明原假设不成立，若无论如何都找不到所需证据，说明原假设不成立，此时需要另作新的假设。此时需要另作新的假设。. 推理过程算法描述（图示）推理过程算法描述（图示）逆向推理2022-3-322 逆向推理过逆向推理过程算法描述：程算法描述：开始开始 提出假设提出假设该假设在数据库该假设在数据库DB中？中？该假设是证据？该假设是证据？在知识库中找出所有能在知识库中找出所有能导出该假设的知识，形导出该假设的知识，形成适用知识集成适用知识集KS从从KS中选出一条知识，并中选出一条知识，

25、并将该知识的一个运用条件将该知识的一个运用条件作为一个新的假设目标。作为一个新的假设目标。该假设成立该假设成立询问用户询问用户有此事实？有此事实？该假设成立，该假设成立，并将此事实并将此事实存入数据库存入数据库还有假设？还有假设？退出退出YYYYNNNN2022-3-323假设某用户希望动物识别系统验证一下某动物是否假设某用户希望动物识别系统验证一下某动物是否是虎，并设当前数据库为空。其逆向推理过程为：是虎，并设当前数据库为空。其逆向推理过程为： 以虎作为假设目标以虎作为假设目标; 检察数据库中有无虎这个事实。因为数据库初检察数据库中有无虎这个事实。因为数据库初始为空，显然不会有虎这个事实始为

26、空，显然不会有虎这个事实; ; 判断该目标是否是证据；判断该目标是否是证据；判断一个目标是否是判断一个目标是否是证据，只要检查它是否为某条知识的结论就可得证据，只要检查它是否为某条知识的结论就可得知。如果它不包含在任何一条知识的结论部分中，知。如果它不包含在任何一条知识的结论部分中，那么它就是证据。那么它就是证据。这里虎显然不是证据，因为它这里虎显然不是证据，因为它是规则是规则r r1010的结论；的结论；逆向推理求解过程2022-3-324 在知识库中找出所有能导出该目标的知识。该在知识库中找出所有能导出该目标的知识。该问题比较简单，只有一条知识可导出结论虎，问题比较简单，只有一条知识可导出

27、结论虎，即即r r1010；r10: If r10: If 该动物是哺乳动物该动物是哺乳动物 and and 是食肉是食肉动物动物 and and 是黄褐色是黄褐色 and and 身上有黑色条纹身上有黑色条纹 thethen n 该动物是虎该动物是虎 将将r r1010的运用条件分别作为新的假设进行验证。的运用条件分别作为新的假设进行验证。 该知识有一个运用条件是该知识有一个运用条件是“是黄褐色是黄褐色”，当把，当把它它 作为新假设进行推理时，作为新假设进行推理时， 首先要检查数据库中有无该事实，这里显然没首先要检查数据库中有无该事实，这里显然没有；有；2022-3-325 接着判断它是否是

28、证据，因在接着判断它是否是证据，因在r r1 1-r-r1515中没有一中没有一条条 知识的结论部分包含它，所以知识的结论部分包含它，所以 它是证据。它是证据。 此时询问用户：你看到的动物是黄褐色吗？若此时询问用户：你看到的动物是黄褐色吗？若用户答是，则该运用条件就得到了验证，并将它用户答是，则该运用条件就得到了验证，并将它存入数据库中；若用户回答不是，则就否定了原存入数据库中；若用户回答不是，则就否定了原先关于虎的假设，需要作另外的假设，从头开始先关于虎的假设，需要作另外的假设，从头开始进行逆向推理。这里，我们假设用户的回答为是，进行逆向推理。这里，我们假设用户的回答为是，以便将推理进行下去

29、。以便将推理进行下去。 对于知识的运用条件对于知识的运用条件“身上有黑条纹身上有黑条纹”与上面处与上面处理类似理类似, 因为它也是一个证据，我们同样假定用户因为它也是一个证据，我们同样假定用户的回答为是，这样数据库中就又增加了一个事实。的回答为是，这样数据库中就又增加了一个事实。2022-3-326 现在数据库中有两个事实：是黄褐色、身上有黑现在数据库中有两个事实：是黄褐色、身上有黑条纹。条纹。 对于知识的运用条件对于知识的运用条件“是哺乳动物是哺乳动物”，因它没有，因它没有在数据库中出现，同时又不是证据（它是在数据库中出现，同时又不是证据（它是r1与与r2的的结论），所以要在知识库中找出能导

30、出它的所有结论），所以要在知识库中找出能导出它的所有知识，即知识，即 r1与与r2： r1: If r1: If 该动物有毛发该动物有毛发 then then 该动物是哺该动物是哺乳动物乳动物 r2: If r2: If 该动物有奶该动物有奶 then then 该动物是哺该动物是哺乳动物乳动物2022-3-327此时，因同时有两条知识可供使用，因而存在先使此时，因同时有两条知识可供使用，因而存在先使用哪一个的问题。这有多种处理方法，将在以后用哪一个的问题。这有多种处理方法，将在以后讨论，这里我们采用最简单的一种，即哪一个排讨论，这里我们采用最简单的一种，即哪一个排在前面就先使用哪一个，所以用

31、在前面就先使用哪一个，所以用r1。 由于由于r1的运用条件是有毛发，因此又要把有的运用条件是有毛发，因此又要把有毛发作为新假设进行验证，显然它是一个证据。毛发作为新假设进行验证，显然它是一个证据。经询问用户，假定回答为是，这样，是哺乳动物经询问用户，假定回答为是，这样，是哺乳动物就被肯定。就被肯定。 对于运用条件对于运用条件“是食肉动物是食肉动物”可作类似处理，可作类似处理，只是为证实它，要用到只是为证实它，要用到r5或或r6。 2022-3-328r5: If r5: If 该动物吃肉该动物吃肉 then then 该动物是食肉动物该动物是食肉动物r6: If r6: If 该动物有犬齿该动

32、物有犬齿 and and 有爪有爪 and and 眼盯前方眼盯前方 then then 该动物是食肉动物该动物是食肉动物 使用使用r5时，若用户对询问时，若用户对询问“该动物吃肉吗该动物吃肉吗”给出肯定的回答。给出肯定的回答。 至此至此r r1010的四个运用条件都被证实，从而肯定的四个运用条件都被证实，从而肯定原假设原假设“该动物是虎该动物是虎”的正确性。的正确性。2022-3-329. 逆向推理的主要优点：逆向推理的主要优点：不必使用与目标无关的知不必使用与目标无关的知识，识，目的性强目的性强，同时还有利于向用户提供解释。，同时还有利于向用户提供解释。 逆向推理的逆向推理的主要缺点：主要

33、缺点：初始目标的选择有初始目标的选择有盲目性盲目性，若不符合实际，就要多次提出假设，影响到系统若不符合实际，就要多次提出假设，影响到系统效率。效率。2022-3-330. 正、逆向推理存在的缺陷正、逆向推理存在的缺陷 正向推理正向推理具有盲目、效率低等缺点；具有盲目、效率低等缺点； 逆向推理逆向推理若提出的假设目标不符合事实，若提出的假设目标不符合事实，也会降低系统效率。也会降低系统效率。 为解决这些问题，可把正向推理与逆向推理结为解决这些问题，可把正向推理与逆向推理结合起来，取长补短；合起来，取长补短； 象这样既有正向又有逆向的推理称为象这样既有正向又有逆向的推理称为混合推理。混合推理。 混

34、合推理2022-3-331. 混合推理的两种情况混合推理的两种情况 先正向再逆向先正向再逆向 ： 先进行正向推理，先进行正向推理，帮助选择某个目标，即从帮助选择某个目标，即从已知事实演绎出部分结果，已知事实演绎出部分结果，然后再用逆向推理证实该然后再用逆向推理证实该目标或提高其可信度。目标或提高其可信度。开始开始 进行正向推理进行正向推理 需要逆向推理？需要逆向推理？还需要正向推理？还需要正向推理？以正向推理所得结果以正向推理所得结果作为假设进行逆向推理作为假设进行逆向推理输出结果输出结果退出退出YYNN2022-3-332 先逆向再正向：先逆向再正向：先先假设一个目标进行逆假设一个目标进行逆

35、向推理，然后再利用向推理，然后再利用逆向推理中得到的信逆向推理中得到的信息进行正向推理，以息进行正向推理，以推出更多的结论。推出更多的结论。开始开始 进行逆向推理进行逆向推理需要正向推理？需要正向推理？还需要逆向推理？还需要逆向推理？进行正向推理进行正向推理输出结果输出结果退出退出YYNN2022-3-333 双向推理是双向推理是指正向推理与逆向推理同时进行指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上且在推理过程中的某一步骤上“碰头碰头”的一种推的一种推理方式。理方式。基本思想：基本思想： 一方面根据已知事实进行正向推理，但并不推一方面根据已知事实进行正向推理，但并不推到最终目标；

36、另一方面从某假设目标出发进行逆到最终目标；另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所需要的证据，这时推理就可结束，向推理此时所需要的证据，这时推理就可结束，逆向推理时所做的假设就是推理的最终结论。逆向推理时所做的假设就是推理的最终结论。双向推理2022-3-334 求解策略求解策略 所谓推理的求解策略是指，推理是只求一个解，所谓推理的求解策略是指，推理是只求一个解，还是求所有解以及最优解等。还是求所有解以及最优解等。 限制策略限

37、制策略 为了防止无穷的推理过程，以及由于推理过程为了防止无穷的推理过程，以及由于推理过程太长增加时间及空间的复杂性，可在控制策略中指太长增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度，宽度，时间，定推理的限制条件，以对推理的深度，宽度，时间，空间等进行限制。空间等进行限制。 求解策略和限制策略2022-3-335 A 概念概念 在推理过程中，系统要不断地用当前已知的事实与知在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进识库中的知识进 行匹配，此时可能发生如下三种情况：行匹配，此时可能发生如下三种情况： . 已知事实不能与知识库中的任何知识匹配成功；已知事

38、实不能与知识库中的任何知识匹配成功； . 已知事实恰好只与知识库中的一个知识匹配成功；已知事实恰好只与知识库中的一个知识匹配成功； . 已知事实可以与知识库中的多个知识匹配成功；已知事实可以与知识库中的多个知识匹配成功；或者有多个（组）已知事实都可与知识库中的一个知识或者有多个（组）已知事实都可与知识库中的一个知识匹配成功；或者有多个（组）已知事实可与知识库中的匹配成功；或者有多个（组）已知事实可与知识库中的多个知识匹配成功。多个知识匹配成功。 第三种情况为发生了冲突，此时需要按一定的策第三种情况为发生了冲突，此时需要按一定的策略解决冲突，以便从中挑选一个知识用于当前的推理，略解决冲突，以便从

39、中挑选一个知识用于当前的推理，称这一解决冲突的过称为称这一解决冲突的过称为冲突消解冲突消解。解决冲突时所用的。解决冲突时所用的方法称为方法称为冲突消解策略冲突消解策略。冲突消解策略2022-3-336 B 以产生式系统为例进行较详细说明以产生式系统为例进行较详细说明. 产生式系统冲突产生式系统冲突 在产生式系统中，若出现下列情况就认为发生了在产生式系统中，若出现下列情况就认为发生了冲突：冲突： 对正向推理而言，如果有多条产生式规则的前对正向推理而言，如果有多条产生式规则的前件都和已知事实匹配成功；或者有多组不同的已知件都和已知事实匹配成功；或者有多组不同的已知事实都与同一条产生式规则的前件匹配

40、成功；或者事实都与同一条产生式规则的前件匹配成功；或者以上两种情况同时出现。以上两种情况同时出现。 对逆向推理而言，如果有多条产生式规则的后对逆向推理而言，如果有多条产生式规则的后件都和同一个假设匹配成功；或者有多条产生式规件都和同一个假设匹配成功；或者有多条产生式规则的后件可与多个假设匹配成功。则的后件可与多个假设匹配成功。 2022-3-337. 冲突消解冲突消解 冲突消解的任务是解决冲突。冲突消解的任务是解决冲突。 对正向推理来说，它将决定选择哪一组已知对正向推理来说，它将决定选择哪一组已知事实来激活哪一条产生式规则，使它用于当前的事实来激活哪一条产生式规则，使它用于当前的推理，产生其后

41、件指出的结论或执行相应的操作。推理，产生其后件指出的结论或执行相应的操作。 对逆向推理来说，它将决定用哪一个假设与对逆向推理来说，它将决定用哪一个假设与哪一个产生式规则的后件进行匹配，从而推出相哪一个产生式规则的后件进行匹配，从而推出相应的前件，作为新的假设。应的前件，作为新的假设。2022-3-338. 冲突消解策略冲突消解策略 目前已有多种消解冲突的策略，其基本思想都是目前已有多种消解冲突的策略，其基本思想都是对对知识进行排序知识进行排序。常用的有以下几种：。常用的有以下几种： 按针对性排序按针对性排序本策略是优先选用针对性较本策略是优先选用针对性较强的产生式规则。强的产生式规则。 设有如

42、下两条产生式规则：设有如下两条产生式规则： r r1: 1: IF AIF A1 1 AND A AND A2 2 AND AND A AND AND An n THEN H THEN H1 1 r r2 2：IF BIF B1 1 AND B AND B2 2 AND AND B AND AND Bm m THEN HTHEN H2 2 如果存在最一般合一，使得如果存在最一般合一，使得r r1 1中每一个中每一个Ai都可变成都可变成相应的相应的B Bi i, ,即即r r2 2中包含中包含r r1 1的全部条件的全部条件A A1 1,A,A2 2,An,An外，还外，还包含其他条件，则称包含

43、其他条件，则称r r2 2比比r r1 1有更大的针对性，有更大的针对性，r r1 1比比r r2 2有更大的通用性。有更大的通用性。2022-3-339 按已知事实的新鲜性排序按已知事实的新鲜性排序把数据库中后生成把数据库中后生成的事实称为新鲜的事实的事实称为新鲜的事实 。 在产生式的推理过程中，每应用一条产生式规则在产生式的推理过程中，每应用一条产生式规则就会得到一个或多个结论或者执行某个操作，数据库就会得到一个或多个结论或者执行某个操作，数据库就会增加新的事实。另外，在推理时还会向用户询问就会增加新的事实。另外，在推理时还会向用户询问有关的信息，也使数据库的内容发生变化。我们把数有关的信

44、息，也使数据库的内容发生变化。我们把数据库中后生成的事实称为新鲜的事实，据库中后生成的事实称为新鲜的事实，即后生成的事即后生成的事实比先生成的事实具有较大的新鲜性。实比先生成的事实具有较大的新鲜性。 若一条规则被应用后生成了多个结论，则即可以若一条规则被应用后生成了多个结论，则即可以认为这些结论有相同的新鲜性，也可认为排在前面的认为这些结论有相同的新鲜性，也可认为排在前面的结论有较大的新鲜性，根据情况而定。结论有较大的新鲜性，根据情况而定。2022-3-340 按匹配度排序按匹配度排序 匹配度大的知识优先选用。匹配度大的知识优先选用。 在不确定性匹配中，为了确定两个知识模式在不确定性匹配中，为

45、了确定两个知识模式是否匹配，需要计算这两个模式是否匹配，需要计算这两个模式 的相似程度，当的相似程度，当其达到某个预先规定的值时，则认为它们是可匹其达到某个预先规定的值时，则认为它们是可匹配的。相似度又称为匹配度。配的。相似度又称为匹配度。 若产生式规则若产生式规则r1、r2都可匹配成功，则可根据都可匹配成功，则可根据它们的匹配度决定哪个规则被优先选用。它们的匹配度决定哪个规则被优先选用。2022-3-341 根据领域问题的特点排序根据领域问题的特点排序 某些领域问题，预先可知道它的某些特点，此时某些领域问题，预先可知道它的某些特点，此时可根据这些特点把知识排成固定的顺序。可根据这些特点把知识

46、排成固定的顺序。 例如：例如： (1) 当领域问题有固定的解题次序时，可按该当领域问题有固定的解题次序时，可按该次序排列相应的知识，排在前面的知识优先被应次序排列相应的知识，排在前面的知识优先被应用用; (2) 当已知某些产生式规则被应用后会明显的有当已知某些产生式规则被应用后会明显的有利于问题的求解时，就使这些产生式规则优先被利于问题的求解时，就使这些产生式规则优先被应用。应用。2022-3-342 按上下文限制排序按上下文限制排序 把产生式规则按它们所描述的上下文分成若干组，把产生式规则按它们所描述的上下文分成若干组，在不同的条件下，只能从相应的组中选取有关的产在不同的条件下，只能从相应的

47、组中选取有关的产生式规则。这样，不仅可以减少冲突的发生，而且生式规则。这样，不仅可以减少冲突的发生，而且由于搜索范围小，也提高了推理效率。由于搜索范围小，也提高了推理效率。 按冗余限制排序按冗余限制排序 如果一条产生式规则被应用后将产生冗余知识，如果一条产生式规则被应用后将产生冗余知识，则降低了它被应用的优先级。产生的冗余知识越多，则降低了它被应用的优先级。产生的冗余知识越多，优先级越低。优先级越低。 按条件个数排序按条件个数排序 如果有多条产生式规则生成的结论相同，则要求如果有多条产生式规则生成的结论相同，则要求条件少的产生式规则被优先应用，因为要求条件少条件少的产生式规则被优先应用，因为要

48、求条件少的规则匹配时花费的时间较少。的规则匹配时花费的时间较少。2022-3-343(1) 基本概念基本概念 所谓模式匹配是指对两个知识模式（如两个所谓模式匹配是指对两个知识模式（如两个谓词公式、两个框架片断或两个语义网络片断等）谓词公式、两个框架片断或两个语义网络片断等）的比较与耦合，即的比较与耦合，即 检查这两个知识模式是否完全检查这两个知识模式是否完全一致或近似一致。如果两者完全一致，或虽不完一致或近似一致。如果两者完全一致，或虽不完全一致但其相似程度落在指定的限度内，就称它全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。们是可匹配的，否则为不可匹配。 模式匹配是

49、推理中必须进行的一项重要工作，模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才能从知识库中选出当前因为只有经过模式匹配才能从知识库中选出当前适用的知识，才能进行推理。适用的知识，才能进行推理。 模式匹配2022-3-344(2) 分类分类 若按匹配时两个知识模式的相似程度分，可分若按匹配时两个知识模式的相似程度分，可分 为确定性匹配和不确定性匹配两种。为确定性匹配和不确定性匹配两种。 确定性匹配确定性匹配指两个知识模式完全一致，或指两个知识模式完全一致，或经经 过变量代换后变的完全一致。过变量代换后变的完全一致。 例如，设有两个知识模式：例如，设有两个知识模式： P1：fathe

50、r(李四，李小四）李四，李小四）and man(李小四李小四) P2：father(x, y) and man(y) 若用若用“李四李四”代换变量代换变量 x，用，用“李小四李小四”代换代换 y，则则P1，P2就变得完全一致，若用这两个知识模式进就变得完全一致，若用这两个知识模式进行匹配，则称它们是确定性匹配。行匹配，则称它们是确定性匹配。 确定性匹配又称完全匹配或精确匹配。确定性匹配又称完全匹配或精确匹配。2022-3-345 不确定性匹配不确定性匹配指两个知识模式不完全一致，指两个知识模式不完全一致，但从总体上看，其相似程度又落在指定的限度内。但从总体上看，其相似程度又落在指定的限度内。2

51、022-3-346(3) 变量代换变量代换 无论是确定性匹配或不确定性匹配，在进行匹无论是确定性匹配或不确定性匹配，在进行匹配时一般都需要进行变量的代换。配时一般都需要进行变量的代换。 定义定义11 代换是形如代换是形如tt1 1/x/x1 1,t,t2 2/x/x2 2,t,tn n/x/xn n 的的有限集合。其中，有限集合。其中，t t1 1,t,t2 2,t,tn n是项；是项；x x1 1,x,x2 2,x,xn n是是互不相同的变元；互不相同的变元； t ti i/x/xi i表示用表示用t ti i代代x xi i换，不允许换，不允许t ti i与与x xi i相同，也不允许变元

52、相同，也不允许变元x xi i循环地出现在另一个循环地出现在另一个t tj j中。中。 例如：例如： a/x,f(b)/y,w/z a/x,f(b)/y,w/z 是一个代换，是一个代换， g(y)/x,f(x)/y g(y)/x,f(x)/y 不是一个代换。不是一个代换。2022-3-347 因为代换的目的是使某些变元被另外的变元、因为代换的目的是使某些变元被另外的变元、常量或函数取代，使之不再在公式中出现，而常量或函数取代，使之不再在公式中出现，而gg(y)/x,f(x)/y(y)/x,f(x)/y在在x x与与y y之间出现了循环代换的情况，之间出现了循环代换的情况，它既没有消去它既没有消

53、去x,x,也没有消去也没有消去y.y. 如果将它改为如果将它改为g(a)/x,f(x)/yg(a)/x,f(x)/y则是一个代换则是一个代换 它将把公式中的它将把公式中的x x用用g(a)g(a)代换，代换，y y用用f(g(a)f(g(a)代代换，从而消去了变元换，从而消去了变元x x和和y y。2022-3-348 定义定义22 设设 =t=t1 1/x/x1 1,t,t2 2/x/x2 2,t,tn n/x/xn n =u =u1 1/y/y1 1,u,u2 2/y/y2 2,u,um m/y/ym m 是两个代换，则此两个代换的复合也是一个代换，是两个代换，则此两个代换的复合也是一个代

54、换，是从是从tt1 1 /x/x1 1,t,t2 2 /x/x2 2,t,tn n /x/xn n,u,u1 1/y/y1 1,u,u2 2/y/y2 2,u,um m/y/ym m 中删去如下两种元素：中删去如下两种元素： t ti i /x/xi i 当当 t ti i =x=xi i u ui i/y/yi i 当当 y yi i xx1 1,x,x2 2,x,xn n 后剩下的元素所构成的集合，记为后剩下的元素所构成的集合，记为 o o 。 例如，设有代换：例如，设有代换： =f(y)/x,z/y=f(y)/x,z/y =a/x,b/y,y/z=a/x,b/y,y/z 则则 o o =

55、f(b)/x=f(b)/x，y/zy/z2022-3-349 定义定义33 设有公式集设有公式集F=FF=F1,1,F F2,2,FFn n,若存在一个代若存在一个代换换 使得使得F F1 1 = F= F2 2 = F= Fn n 则称则称 为公式集为公式集F F的一的一个合一，且称个合一，且称F F1,1,F F2,2,FFn n是可合一的。是可合一的。 例如：例如： 假设有公式集假设有公式集 F=P(x,y,f(y),P(a,g(x),z)F=P(x,y,f(y),P(a,g(x),z) 则下式是它的一个合一：则下式是它的一个合一： = a/x,g(a)/y,f(g(a)/z = a/x

56、,g(a)/y,f(g(a)/z 一个公式集的合一一般来说是不唯一的。一个公式集的合一一般来说是不唯一的。2022-3-350 定义定义44 设设 是公式集是公式集F F的一个合一，如果对任一个合的一个合一，如果对任一个合一一 都存在一个代换都存在一个代换 ，使得，使得 = = o o ，则称则称 是一是一个最一般的合一。个最一般的合一。 最一般的合一是唯一的。最一般的合一是唯一的。 若用最一般合一去代换那些可合一的谓词公式若用最一般合一去代换那些可合一的谓词公式, ,可使它们变成完全一致的谓词公式。可使它们变成完全一致的谓词公式。 由此可知，为了使两个知识模式匹配，可用其最由此可知，为了使两

57、个知识模式匹配，可用其最一般的合一对他们进行代换。一般的合一对他们进行代换。 2022-3-351差异集的概念：差异集的概念： 设有如下两个谓词公式：设有如下两个谓词公式： F F1 1: P(x: P(x，y y，z)z) F F2 2: P(x: P(x，f(a)f(a)，h(b)h(b) 分别从分别从F F1 1与与F F2 2的第一个符号开始，逐个向右比的第一个符号开始，逐个向右比较，此时发现较，此时发现F F1 1中的中的y y与与F F2 2中的中的f(a)f(a)不同，它们构不同，它们构成了一个差异集：成了一个差异集： D D1 1=y=y，f(a)f(a) 当继续向右比较时，又

58、发现当继续向右比较时，又发现F F1 1中的中的z z与与F F2 2中的中的h h(b)(b)不同，则又得到一个差异集：不同，则又得到一个差异集： D D2 2=z=z，h(b)h(b)2022-3-352下面给出求取最一般合一算法的具体步骤：下面给出求取最一般合一算法的具体步骤： (1) (1) 令令k=0,Fk=0,Fk k=F,=F, k k= = 。这里，。这里，F F是欲求其最一般是欲求其最一般合一的公式集，合一的公式集， 是空代换，它代表不作代换。是空代换，它代表不作代换。 (2) (2) 若若F Fk k只含一个表达式，则算法停止，只含一个表达式，则算法停止， k k就是就是最

59、一般合一。最一般合一。 (3) (3) 找出找出F Fk k的差异集的差异集D Dk k。 (4) (4) 若若D Dk k中存在元素中存在元素x xk k和和t tk k，其中，其中x xk k是变元，是变元，t tk k是项，且是项，且x xk k不在不在t tk k中出现，则置：中出现，则置： k+1k+1= = k k o to tk k/x/xk k ，求取最一般合一的算法2022-3-353 F Fk+1k+1=F=Fk kttk k/x/xk k k=k+1 k=k+1 然后转（然后转（2 2）。）。 (5) (5) 算法中止，算法中止，F F的最一般合一不存在的最一般合一不存在

60、2022-3-354例如：例如： 设设F=P(a,x,f(g(y),P(z,f(z),f(u)F=P(a,x,f(g(y),P(z,f(z),f(u)求求其最一般合一。其最一般合一。 (1) 令令 0 0= = ，F F0 0=F,=F,因因F F0 0中含有两个表达式，所以中含有两个表达式，所以 0 0不是最一般合一；不是最一般合一； (2) 差异集差异集D D0 0=a,z=a,z； (3) 1 1= = 0 0 oa/z=a/z,oa/z=a/z, F F1 1=P(a,x,f(g(y),P(a,f(a),f(u)=P(a,x,f(g(y),P(a,f(a),f(u)； (4) D D1