人工智能3经典逻辑推理人工智能课程中国海洋大学33366.pptx

第三章第三章经典逻辑推理经典逻辑推理经典逻辑推理经典逻辑推理经典逻辑推理是根据经典逻辑的逻辑规则进行的一种推理，又称为机械经典逻辑推理是根据经典逻辑的逻辑规则进行的一种推理，又称为机械-自自动定理证明动定理证明(mechanical-automatictheoremproving),主要推理方法有自然主要推理方法有自然演绎推理，归结演绎推理及与或形演绎推理等。由于这种推理是基于经典逻辑演绎推理，归结演绎推理及与或形演绎推理等。由于这种推理是基于经典逻辑的，其真值只有真和假两种，因此它是一种精确推理。的，其真值只有真和假两种，因此它是一种精确推理。本章学习目的：本章学习目的：学习学习运用知识进行推理，求解问题运用知识进行推理，求解问题。本章主要讲述内容：本章主要讲述内容：1.简述与推理相关的知识：如推理方式及分类、推理控制策略、模简述与推理相关的知识：如推理方式及分类、推理控制策略、模式匹配、冲突消解策略、搜索策略等。式匹配、冲突消解策略、搜索策略等。2.经典逻辑推理：自然演绎推理、归结演绎推理和与经典逻辑推理：自然演绎推理、归结演绎推理和与/或形演绎推理。或形演绎推理。3.1推理的基本概念推理的基本概念1.1.推理方式及分类推理方式及分类 (1)(1)什么是推理什么是推理 推理推理从已知事实出发，通过运用已掌握的知识，找出其中蕴含的事实，从已知事实出发，通过运用已掌握的知识，找出其中蕴含的事实，或归结出新的事实，这一过程称为推理。或归结出新的事实，这一过程称为推理。推理机推理机在人工智能中，推理是由程序实现的，称为推理机。在人工智能中，推理是由程序实现的，称为推理机。推理包括两种判断：推理包括两种判断：一种是已知的判断，它包括已掌握的与求解问题有关的知识以及关于一种是已知的判断，它包括已掌握的与求解问题有关的知识以及关于 问题的已知事实；问题的已知事实；另一种是由已知判断推出的新判断，即推理的结论。另一种是由已知判断推出的新判断，即推理的结论。推理的基本任务：是从一种判断推出另一种判断。推理的基本任务：是从一种判断推出另一种判断。(2)推理方式及其分类推理方式及其分类.演绎推理、归结推理、默认推理演绎推理、归结推理、默认推理（从新判断推出的途径来划分从新判断推出的途径来划分）演绎推理演绎推理从全称判断推导出特称判断或单称判断的过程，即由一般性从全称判断推导出特称判断或单称判断的过程，即由一般性知识推出适合于某一具体情况的结论。这是一种从一般到知识推出适合于某一具体情况的结论。这是一种从一般到个别的推理。个别的推理。演绎推理有多种形式，经常用的是三段论式，它包括：演绎推理有多种形式，经常用的是三段论式，它包括：1)大前提，这是已知的一般性知识或假设；大前提，这是已知的一般性知识或假设；2)小前提，这是关于所研究的具体情况或个别事实的判断；小前提，这是关于所研究的具体情况或个别事实的判断；3)结论，这是由大前提推出的适合于小前提所示情况的新判断。结论，这是由大前提推出的适合于小前提所示情况的新判断。例如：例如：1)足球运动员的身体都是强壮的；足球运动员的身体都是强壮的；2)高波是一名足球运动员；高波是一名足球运动员；3)所以，高波的身体是强壮的。所以，高波的身体是强壮的。这就是一个三段论推理，其中，这就是一个三段论推理，其中，(1)是大前提，是大前提，(2)是小前提，是小前提，(3)是经演是经演绎推出的结论。结论绎推出的结论。结论“高波的身体是强壮的高波的身体是强壮的”事实上是蕴含于事实上是蕴含于“足球运动员的足球运动员的身体都是强壮的身体都是强壮的”这一大前提中的。它没有超出大前提所断定的范围。这一大前提中的。它没有超出大前提所断定的范围。这是演绎推理的一个典型特征，即在任何情况下，由演绎推理导出的结论这是演绎推理的一个典型特征，即在任何情况下，由演绎推理导出的结论都是蕴含在大前提的一般性知识中的。因此，只要大前提和小前提是正确的，都是蕴含在大前提的一般性知识中的。因此，只要大前提和小前提是正确的，则由它们推导出来的结论也必然是正确的。则由它们推导出来的结论也必然是正确的。演绎推理是人工智能中的一种重要推理方式，在直到目前研制成功的各类演绎推理是人工智能中的一种重要推理方式，在直到目前研制成功的各类智能系统中，大多是用演绎推理实现的。智能系统中，大多是用演绎推理实现的。归结推理归结推理归结推理是从足够多的事例中归结出一般性结论的推理过程，归结推理是从足够多的事例中归结出一般性结论的推理过程，是一种从个别到一般的推理。是一种从个别到一般的推理。归结推理又分为完全归结和不完全归结两种。归结推理又分为完全归结和不完全归结两种。完全归结：完全归结：指在进行归结时考察了相应事物的全部对象，并根据这些对指在进行归结时考察了相应事物的全部对象，并根据这些对 象是否都有某种属性，从而推出这种事物是否具有这个属性。象是否都有某种属性，从而推出这种事物是否具有这个属性。例如例如:某厂进行产品质量检查，如果对每一件产品都进行了严格检查，某厂进行产品质量检查，如果对每一件产品都进行了严格检查，并且是合格的，则推导出结论该厂的产品是合格的。并且是合格的，则推导出结论该厂的产品是合格的。不完全归结：指只考察了相应事物的部分对象，就得出了结论。不完全归结：指只考察了相应事物的部分对象，就得出了结论。默认推理默认推理又称缺省推理，它是在知识不完全的情况下假设某些条件已经又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。具备所进行的推理。在默认推理过程中，如果到某一时刻发现原先所作的默认不在默认推理过程中，如果到某一时刻发现原先所作的默认不正确，则就要撤销所作默认，以及由此默认推出的所有结论，正确，则就要撤销所作默认，以及由此默认推出的所有结论，重新按新情况进行推理。重新按新情况进行推理。.确定性推理，不确定性推理确定性推理，不确定性推理（按推理时所用知识的确定性来划分按推理时所用知识的确定性来划分）确定性推理确定性推理指推理时所用的知识都是精确的，推出的结论也是指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或为确定的，其真值或为“真真”，或为，或为“假假”，没有第三种，没有第三种情况出现。情况出现。下面将要讨论的经典逻辑推理就属于这一类。下面将要讨论的经典逻辑推理就属于这一类。不确定性推理不确定性推理指推理时所用的知识不都是精确的，推出的结论也不完指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于全是肯定的，其真值位于“真真”和和“假假”之间，命题的外之间，命题的外延延模糊不清。模糊不清。这里我们要特别强调不确定性推理。自亚里士多德建立第一个演绎公这里我们要特别强调不确定性推理。自亚里士多德建立第一个演绎公理系统以来，经典逻辑与精确数学的建立与发展为人类科学技术的发展起了理系统以来，经典逻辑与精确数学的建立与发展为人类科学技术的发展起了巨大的作用。然而，现实世界中的事物和现象大都是不严格、不精确的，许巨大的作用。然而，现实世界中的事物和现象大都是不严格、不精确的，许多概念是模糊的，很难用精确的数学模型来表示和处理。因此。近几年来，多概念是模糊的，很难用精确的数学模型来表示和处理。因此。近几年来，各种非经典逻辑迅速崛起，人工智能亦把不精确知识的表示与处理作为重要各种非经典逻辑迅速崛起，人工智能亦把不精确知识的表示与处理作为重要的研究课题。另外，从人类思维活动的特征来看，人们经常是在知识不完全、的研究课题。另外，从人类思维活动的特征来看，人们经常是在知识不完全、不精确的情况下进行多方位的思考及推理的。因此，要使计算机模拟人类的不精确的情况下进行多方位的思考及推理的。因此，要使计算机模拟人类的思维活动，就必须使其具有不确定性推理的能力。思维活动，就必须使其具有不确定性推理的能力。.单调推理、非单调推理单调推理、非单调推理（按（按推理过程中推出的结论是否单调的增加来划分）推理过程中推出的结论是否单调的增加来划分）单调推理单调推理指在推理过程中随着推理的向前推进及新知识的加入，推出的指在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标，在推理过结论呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不会出现反复的情况，即不会由于新知识的加入而否定了程中不会出现反复的情况，即不会由于新知识的加入而否定了前面推出的结论，使推理又退回到前面的一步。前面推出的结论，使推理又退回到前面的一步。非单调推理非单调推理指在推理过程中由于新知识的加入，不仅没有加强已推出的指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新结论，反而要否定它，使得推理退回到前面的某一步，重新开始。开始。.启发式推理、非启发式推理启发式推理、非启发式推理（按推理中是否运用与问题有关的启发性知识分）按推理中是否运用与问题有关的启发性知识分）启发式推理启发式推理推理中运用与问题有关的启发性知识，即解决问题的策略、推理中运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门，对解的特性及规律的估计等实践经验和知识，技巧、窍门，对解的特性及规律的估计等实践经验和知识，以加快推理过程、提高搜索效率，这种推理称为启发式推理。以加快推理过程、提高搜索效率，这种推理称为启发式推理。非启发式推理非启发式推理.基于知识的推理、统计推理、直觉推理基于知识的推理、统计推理、直觉推理（从方法论的角度划分）从方法论的角度划分）基于知识的推理基于知识的推理根据已掌握的事实，通过运用知识进行的推理。根据已掌握的事实，通过运用知识进行的推理。统计推理统计推理根据对某事物的数据统计进行的推理。根据对某事物的数据统计进行的推理。直觉推理直觉推理又称常识性推理，是根据常识进行的推理。又称常识性推理，是根据常识进行的推理。2.推理的控制策略推理的控制策略推理过程是一个思维过程，即求解问题的过程，求解问题的质量推理过程是一个思维过程，即求解问题的过程，求解问题的质量和效率不仅依赖于所采用的求解方法，而且还依赖于求解问题的策略，和效率不仅依赖于所采用的求解方法，而且还依赖于求解问题的策略，即推理的控制策略。即推理的控制策略。推理的控制策略主要包括：推理的控制策略主要包括：推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。(1)推理方向：推理方向：推理方向用于确定推理的驱动方式，分为正向推理、逆向推理、混合推理方向用于确定推理的驱动方式，分为正向推理、逆向推理、混合推理和双向推理四种。推理和双向推理四种。无论按哪种方向进行推理，一般都要求系统具有一个存放知识的知识库，无论按哪种方向进行推理，一般都要求系统具有一个存放知识的知识库，一个存放初始已知事实及问题状态的数据库和一个用于推理的与推理机。一个存放初始已知事实及问题状态的数据库和一个用于推理的与推理机。正向推理正向推理正向推理正向推理 正向推理是以已知事实作为出发点的一种推理，又称数据驱动推理、前正向推理是以已知事实作为出发点的一种推理，又称数据驱动推理、前向链推理及前件推理等。向链推理及前件推理等。.正向推理的基本思想：正向推理的基本思想：从用户提供的初始已知事实出发，在知识库从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的中找出当前可适用的知识，构成可适用知识集知识，构成可适用知识集KS，然后按某种冲突消解策略从然后按某种冲突消解策略从KS中选出一中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，在此之后再在知识库中选取可适用的知识进行推理，如此重已知事实，在此之后再在知识库中选取可适用的知识进行推理，如此重复，直到求得了所要求的解，或者知识库中再无可适用的知识为止。复，直到求得了所要求的解，或者知识库中再无可适用的知识为止。正向推理过程正向推理过程算法描述：算法描述：开始开始把初始已知事实送入把初始已知事实送入DBDB中包含问题的解？中包含问题的解？KB中有可适用知识？中有可适用知识？KS空？空？把把KB中所有可适用知识都选出来送入中所有可适用知识都选出来送入KS推出的是新事实？推出的是新事实？按冲突消解策略从按冲突消解策略从KS中选出一条知识进行推理中选出一条知识进行推理将该新事实加入到将该新事实加入到DB中中成功，退出成功，退出把用户提供的新事实加入把用户提供的新事实加入DB中中用户用户可补充新事实？可补充新事实？失败，退出失败，退出YYYYYNNNNN.与正向推理相关的问题：与正向推理相关的问题：匹配方法匹配方法在以上推理过程中，需要从知识库在以上推理过程中，需要从知识库KB中选出可适用的知识，中选出可适用的知识，这就要用知识库中的知识与数据库中的已知事实进行匹配，这就要用知识库中的知识与数据库中的已知事实进行匹配，为此需确定为此需确定匹配方法匹配方法。搜索策略搜索策略为了进行匹配，就要查找知识，这就牵涉到按什么路线进行为了进行匹配，就要查找知识，这就牵涉到按什么路线进行查找的问题，既按什么查找的问题，既按什么搜索策略搜索策略搜索知识库。搜索知识库。冲突消解策略冲突消解策略如果适用的知识只有一条，这比较简单，系统立即就可用如果适用的知识只有一条，这比较简单，系统立即就可用它进行推理，并将推出的新事实送入数据库它进行推理，并将推出的新事实送入数据库DB中；但是，中；但是，如果当前适用的知识有多条，应该先用那一条如果当前适用的知识有多条，应该先用那一条?这是推理这是推理中的一个重要问题，称为中的一个重要问题，称为冲突消解策略冲突消解策略。总之，为了实现正向推理，有许多具体问题需要解决。总之，为了实现正向推理，有许多具体问题需要解决。举例说明正向推理的求解过程：举例说明正向推理的求解过程：举例说明正向推理的求解过程：举例说明正向推理的求解过程：例例:设在综合数据库中存放有下列已知事实：设在综合数据库中存放有下列已知事实：该动物身上有暗斑点，长脖子，长腿，有奶，有蹄该动物身上有暗斑点，长脖子，长腿，有奶，有蹄 且假设综合数据库中的已知事实与规则库中的知识是从第一条开始，逐条且假设综合数据库中的已知事实与规则库中的知识是从第一条开始，逐条 进行匹配的，进行匹配的，则推理机构的工作过程如下：则推理机构的工作过程如下：从规则库中取出第一条规则从规则库中取出第一条规则r r1 1，检查前提条件与综合数据库中的已知事实不匹配；检查前提条件与综合数据库中的已知事实不匹配；取第二条规则取第二条规则r r2 2，r r2 2的前提的前提“该动物有奶该动物有奶”与综合数据库中事实匹配，则与综合数据库中事实匹配，则r rr r被执行，其结被执行，其结 论被加入综合数据库中，此时综合数据库中的事实为：论被加入综合数据库中，此时综合数据库中的事实为：该动物身上有暗斑点，长脖子，长腿，有奶，有蹄，是哺乳动物该动物身上有暗斑点，长脖子，长腿，有奶，有蹄，是哺乳动物 接着取接着取r3r4r5r6都不匹配，取到都不匹配，取到r7时，匹配成功，则将时，匹配成功，则将r7的结论加入综合数据库：的结论加入综合数据库：该动物身上有暗斑点该动物身上有暗斑点,长脖子长脖子,长腿长腿,有奶有奶,有蹄有蹄,是哺乳动物是哺乳动物,是有蹄动物是有蹄动物 接着取规则，取到接着取规则，取到r11时，匹配成功，发现其前提条件与综合数据库完全匹配，则确定时，匹配成功，发现其前提条件与综合数据库完全匹配，则确定该动物是：该动物是：长颈鹿长颈鹿至此，问题的求解结束了。至此，问题的求解结束了。逆向推理逆向推理逆向推理逆向推理 逆向推理是以某个假设目标作为出发点的一种推理，又称为目标驱动推理、逆向推理是以某个假设目标作为出发点的一种推理，又称为目标驱动推理、逆向链推理及后件推理等。逆向链推理及后件推理等。.逆向推理的基本思想：逆向推理的基本思想：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设成立；若无论如何都找不到所需证据，说明原假设能找到，则说明原假设成立；若无论如何都找不到所需证据，说明原假设不成立，此时需要另作新的假设。不成立，此时需要另作新的假设。.推理过程算法描述（图示）推理过程算法描述（图示）逆向逆向推理过程推理过程算法描述算法描述开始开始提出假设提出假设该假设在数据库该假设在数据库DB中？中？该假设是证据？该假设是证据？在知识库中找出所有能在知识库中找出所有能导出该假设的知识，形导出该假设的知识，形成适用知识集成适用知识集KS从从KS中选出一条知识，并中选出一条知识，并将该知识的一个运用条件将该知识的一个运用条件作为一个新的假设目标。作为一个新的假设目标。该假设成立该假设成立询问用户询问用户有此事实？有此事实？该假设成立，该假设成立，并将此事实并将此事实存入数据库存入数据库还有假设？还有假设？退出退出YYYYNNNN举例说明正向推理的求解过程：举例说明正向推理的求解过程：举例说明正向推理的求解过程：举例说明正向推理的求解过程：假设某用户希望动物识别系统验证一下某动物是否是虎，并设当前数据库为空。假设某用户希望动物识别系统验证一下某动物是否是虎，并设当前数据库为空。其逆向推理过程为：其逆向推理过程为：以虎作为假设目标以虎作为假设目标;检察数据库中有无虎这个事实。因为数据库初始为空，显然不会有虎这个事实检察数据库中有无虎这个事实。因为数据库初始为空，显然不会有虎这个事实;判断该目标是否是证据；判断该目标是否是证据；判断一个目标是否是证据，只要检查它是否为某条知识的结论就可得知。如判断一个目标是否是证据，只要检查它是否为某条知识的结论就可得知。如果它不包含在任何一条知识的结论部分中，那么他就是证据。果它不包含在任何一条知识的结论部分中，那么他就是证据。这里虎显然不是证据，因为它是规则这里虎显然不是证据，因为它是规则r r1010的结论；的结论；在知识库中找出所有能导出该目标的知识。该问题比较简单，只有一条知识可在知识库中找出所有能导出该目标的知识。该问题比较简单，只有一条知识可导出结论虎，即导出结论虎，即r r1010；r10:If r10:If 该动物是哺乳动物该动物是哺乳动物 and and 是食肉动物是食肉动物 and and 是黄褐色是黄褐色 and and 身上有黑色条纹身上有黑色条纹 then then 该动物是虎该动物是虎将将r r1010的运用条件分别作为新的假设进行验证。的运用条件分别作为新的假设进行验证。该知识有一个运用条件是该知识有一个运用条件是“是黄褐色是黄褐色”，当把它作为新假设进行推理时，当把它作为新假设进行推理时，首先要检查数据库中有无该事实，这里显然没有；首先要检查数据库中有无该事实，这里显然没有；接着判断它是否是证据，因在接着判断它是否是证据，因在r r1 1-r-r1515中没有一条知识的结论部分包含它，所以中没有一条知识的结论部分包含它，所以它是证据。它是证据。此时询问用户：你看到的动物是黄褐色吗？若用户答是，则该运用条件就得此时询问用户：你看到的动物是黄褐色吗？若用户答是，则该运用条件就得到了验证，并将它存入数据库中；若用户回答不是，则就否定了原先关于虎到了验证，并将它存入数据库中；若用户回答不是，则就否定了原先关于虎的假设，需要作另外的假设，从头开始进行逆向推理。这里，我们假设用户的假设，需要作另外的假设，从头开始进行逆向推理。这里，我们假设用户的回答为是，以便将推理进行下去。的回答为是，以便将推理进行下去。对于知识的运用条件对于知识的运用条件“身上有黑条纹身上有黑条纹”与上面处理类似与上面处理类似,因为它也是一个证据，因为它也是一个证据，我们同样假定用户的回答为是，这样数据库中就又增加了一个事实。我们同样假定用户的回答为是，这样数据库中就又增加了一个事实。现在数据库中有两个事实：是黄褐色、身上有黑条纹现在数据库中有两个事实：是黄褐色、身上有黑条纹对于知识的运用条件对于知识的运用条件“是哺乳动物是哺乳动物”，因它没有在数据库中出现，同时又不是，因它没有在数据库中出现，同时又不是证据（它是证据（它是r1与与r2的结论），所以要在知识库中找出能导出它的所有知识，即的结论），所以要在知识库中找出能导出它的所有知识，即r1与与r2：r1:If r1:If 该动物有毛发该动物有毛发 then then 该动物是哺乳动物该动物是哺乳动物 r2:If r2:If 该动物有奶该动物有奶 then then 该动物是哺乳动物该动物是哺乳动物此时，因同时有两条知识可供使用，因而存在先使用哪一个的问题。这有此时，因同时有两条知识可供使用，因而存在先使用哪一个的问题。这有多种处理方法，将在以后讨论，这里我们采用最简单的一种，即哪一个排在前多种处理方法，将在以后讨论，这里我们采用最简单的一种，即哪一个排在前面就先使用哪一个，所以用面就先使用哪一个，所以用r1。由于由于r1的运用条件是有毛发，因此又要把有毛发作为新假设进行验证，显的运用条件是有毛发，因此又要把有毛发作为新假设进行验证，显然它是一个证据。经询问用户，假定回答为是，这样，是哺乳动物就被肯定。然它是一个证据。经询问用户，假定回答为是，这样，是哺乳动物就被肯定。对于运用条件对于运用条件“是食肉动物是食肉动物”可作类似处理，只是为证实它，要用到可作类似处理，只是为证实它，要用到r5或或r6。r5:If r5:If 该动物吃肉该动物吃肉 then then 该动物是食肉动物该动物是食肉动物 r6:If r6:If 该动物有犬齿该动物有犬齿 and and 有爪有爪 and and 眼盯前方眼盯前方 then then 该动物是食肉动物该动物是食肉动物 使用使用r5时，若用户对询问时，若用户对询问“该动物吃肉吗该动物吃肉吗”给出肯定的回答。给出肯定的回答。至此至此r r1010的四个运用条件都被证实，从而肯定原假设的四个运用条件都被证实，从而肯定原假设“该动物是虎该动物是虎”的正确性。的正确性。.逆向推理的主要优点：逆向推理的主要优点：不必使用与目标无关的知识，目的性强，同时还有不必使用与目标无关的知识，目的性强，同时还有利于向用户提供解释。利于向用户提供解释。主要缺点：主要缺点：初始目标的选择有盲目性，若不符合实际，就要多初始目标的选择有盲目性，若不符合实际，就要多次提出假设，影响到系统效率。次提出假设，影响到系统效率。混合推理混合推理混合推理混合推理.正、逆向推理存在的缺陷正、逆向推理存在的缺陷正向推理正向推理具有盲目、效率低等缺点；具有盲目、效率低等缺点；逆向推理逆向推理若提出的假设目标不符合事实，也会降低系统效率。若提出的假设目标不符合事实，也会降低系统效率。为解决这些问题，可把正向推理与逆向推理结合起来，取长补短；为解决这些问题，可把正向推理与逆向推理结合起来，取长补短；象这样既有正向又有逆向的推理称为混合推理。象这样既有正向又有逆向的推理称为混合推理。.混合推理的两种情况混合推理的两种情况先正向再逆向先正向再逆向：先进行正向推理，帮助先进行正向推理，帮助选择某个目标，即从已知事实选择某个目标，即从已知事实演绎出部分结果，然后再用逆演绎出部分结果，然后再用逆向推理证实该目标或提高其可向推理证实该目标或提高其可信度。信度。开始开始进行正向推理进行正向推理需要逆向推理？需要逆向推理？还需要正向推理？还需要正向推理？以正向推理所得结果以正向推理所得结果作为假设进行逆向推理作为假设进行逆向推理输出结果输出结果退出退出YYNN先逆向再正向：先逆向再正向：先假设一个目标进行逆向推理，然后再利用逆向推理中先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。得到的信息进行正向推理，以推出更多的结论。开始开始进行逆向推理进行逆向推理需要正向推理？需要正向推理？还需要逆向推理？还需要逆向推理？进行正向推理进行正向推理输出结果输出结果退出退出YYNN 双向推理双向推理双向推理双向推理 双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上骤上“碰头碰头”的一种推理方式。的一种推理方式。基本思想：基本思想：一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所需要的证据，途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所需要的证据，这时推理就可结束，逆向推理时所做的假设就是推理的最终结论。这时推理就可结束，逆向推理时所做的假设就是推理的最终结论。(2)求解策略求解策略所谓推理的求解策略是指，推理是只求一个解，还是求所有解以及最优解等。所谓推理的求解策略是指，推理是只求一个解，还是求所有解以及最优解等。(3)限制策略限制策略 为了防止无穷的推理过程，以及由于推理过程太长增加时间及空间的复杂性，为了防止无穷的推理过程，以及由于推理过程太长增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度，宽度，时间，空间等可在控制策略中指定推理的限制条件，以对推理的深度，宽度，时间，空间等进行限制。进行限制。3.模式匹配模式匹配(1)基本概念基本概念所谓模式匹配是指对两个知识模式（如两个谓词公式、两个框架片断所谓模式匹配是指对两个知识模式（如两个谓词公式、两个框架片断或两个语义网络片断等）的比较与耦合，即或两个语义网络片断等）的比较与耦合，即检查这两个知识模式是否完全一检查这两个知识模式是否完全一致或近似一致。如果两者完全一致，或虽不完全一致但其相似程度落在指定致或近似一致。如果两者完全一致，或虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。的限度内，就称它们是可匹配的，否则为不可匹配。模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才模式匹配是推理中必须进行的一项重要工作，因为只有经过模式匹配才能从知识库中选出当前适用的知识，才能进行推理。能从知识库中选出当前适用的知识，才能进行推理。(2)分类分类若按匹配时两个知识模式的相似程度分，可分为确定性匹配与不确定性若按匹配时两个知识模式的相似程度分，可分为确定性匹配与不确定性匹配两种。匹配两种。确定性匹配确定性匹配指两个知识模式完全一致，或经过变量代换后变的完全一致。指两个知识模式完全一致，或经过变量代换后变的完全一致。例如，设有两个知识模式：例如，设有两个知识模式：P1：father(李四，李小四）李四，李小四）andman(李小四李小四)P2：father(x,y)andman(y)若用若用“李四李四”代换变量代换变量x，用用“李小四李小四”代换代换y，则则P1，P2就变得完全一致，若用这两个知识模式进行匹配，则称它们就变得完全一致，若用这两个知识模式进行匹配，则称它们是确定性匹配。是确定性匹配。确定性匹配又称完全匹配或精确匹配。确定性匹配又称完全匹配或精确匹配。不确定性匹配不确定性匹配指两个知识模式不完全一致，但从总体上看，其相似程度指两个知识模式不完全一致，但从总体上看，其相似程度又落在指定的限度内。又落在指定的限度内。(3)变量代换变量代换无论是确定性匹配或不确定性匹配，在进行匹配时一般都需要进行变量的代换。无论是确定性匹配或不确定性匹配，在进行匹配时一般都需要进行变量的代换。定义定义11 代换是形如代换是形如 t t1 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相同，也不允许变元相同，也不允许变元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 不是一个代换，不是一个代换，因为代换的目的是使某些变元被另外的变元、常量或函数取代，使之不再在公式因为代换的目的是使某些变元被另外的变元、常量或函数取代，使之不再在公式中出现，而中出现，而 g(y)/x,f(x)/yg(y)/x,f(x)/y在在x x与与y y之间出现了循环代换的情况，它既没有消去之间出现了循环代换的情况，它既没有消去x,x,也也没有消去没有消去y.y.如果将它改为如果将它改为 g(a)/x,f(x)/y g(a)/x,f(x)/y 则是一个代换则是一个代换它将把公式中的它将把公式中的x x用用g(a)g(a)代换，代换，y y用用f(g(a)f(g(a)代换，从而消去了变元代换，从而消去了变元x x和和y y。定义定义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 是两个代换，则此两个代换的复合也是一个代换，它是从是两个代换，则此两个代换的复合也是一个代换，它是从 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 中删去如下两种元素：中删去如下两种元素：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/yf(y)/x,z/y =a/x,b/y,y/z=a/x,b/y,y/z则则 o o =f(b)/x,f(b)/x,y/yy/y,a/xa/x,b/yb/y,y/z,y/z =f(b)/xf(b)/x，y/zy/z删去删去 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 定义定义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)/za/x,g(a)/y,f(g(a)/z 一个公式集的合一一般来说是不唯一的。一个公式集的合一一般来说是不唯一的。定义定义44 设设 是公式集是公式集F F的一个合一，如果对任一个合一的一个合一，如果对任一个合一 都存在一个代换都存在一个代换，使得，使得 =o o 则称则称 是一个最一般的合一。是一个最一般的合一。最一般的合一是唯一的。最一般的合一是唯一的。若用最一般合一去代换那些可合一的谓词公式若用最一般合一去代换那些可合一的谓词公式,可使它们变成完全一致的谓词公式。可使它们变成完全一致的谓词公式。由此可知，为了使两个知识模式匹配，可用其最一般的合一对他们进行代换。由此可知，为了使两个知识模式匹配，可用其最一般的合一对他们进行代换。（差异集的概念：（差异集的概念：设有如下两个谓词公式：设有如下两个谓词公式：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)当继续向右比较时，又发现当继续向右比较时，又发现F F1 1中的中的z z与与F F2 2中的中的h(b)h(b)不同，则又得到一个差异集：不同，则又得到一个差异集：D D2 2=z=z，h(b)h(b)下面给出求取最一般合一的算法下面给出求取最一般合一的算法(1)(1)令令k=0,Fk=0,Fk k=F,=F,k k=。这里，这里，F F是欲求其最一般合一的公式集，是欲求其最一般合一的公式集，是空代换，是空代换，它代它代 表不作代换。表不作代换。(2)(2)若若F Fk k只含一个表达式，则算法停止，只含一个表达式，则算法停止，k k就是最一般合一。就是最一般合一。(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 o ttk k/x/xk k F Fk+1k+1=F=Fk kttk k/x/xk k k=k+1 k=k+1 然后转（然后转（2 2）。）。(5)(5)算法终止，算法终止，F F的最一般合一不存在。的最一般合一不存在。例如，设例如，设 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 o oa/z=a/z,a/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 1=x,f(a)=x,f(a)(5)2 2=1 1 o of(a)/x=a/z,f(a)/xf(a)/x=a/z,f(a)/x F F2 2=F=F1 1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u)f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u)(6)D D2 2=g(y),u=g(y),u(7)3 3=2 2 o og(y)/u=a/z,f(a)/x,g(y)/ug(y)/u=a/z,f(a)/x,g(y)/u(8)F F3 3=F=F2 2g(y)/u=P(a,f(a),f(g(y)g(y)/u=P(a,f(a),f(g(y)因为因为F F3 3只含一个表达式，所以只含一个表达式，所以 3 3就是最一般合一，即就是最一般合一，即 a/z,f(a)/x,g(y)/ua/z,f(a)/x,g(y)/u4.冲突消解策略冲突消解策略(1)概念概念在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进行匹配，此时可能发生如下三种情况：行匹配，此时可能发生如下三种情况：.已知事实不能与知识库中的任何知识匹配成功；已知事实不能与知识库中的任何知识匹配成功；.已知事实恰好只与知识库中的一个知识匹配成功；已知事实恰好只与知识库中的一个知识匹配成功；.已知事实可以与知识库中的多个知识匹配成功；或者有多个（组）已已知事实可以与知识库中的多个知识匹配成功；或者