搜索
1第4章确定性推理•智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型，本章重点讨论前一种，不确定性推理放到下一章讨论。•4.1推理的基本概念•4.2推理的逻辑基础•4.3自然演绎推理•4.4归结演绎推理•4.5基于规则的演绎推理24.1推理的基本概念•4.1.1什么是推理•4.1.2推理方法及其分类•4.1.3推理的控制策略及其分类•4.1.4正向推理•4.1.5逆向推理•4.1.6混合推理34.1.1什么是推理•推理的概念•是指按照某种策略从已知事实出发去推出结论的过程。•推理所用的事实：•初始证据：推理前用户提供的•中间结论：推理过程中所得到的•推理过程：由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。•例如，医疗专家系统，专家知识保存在知识库中。推理开始时，先把病人的症状和检查结果放到综合数据库中，然后再从综合数据库的初始证据出发，按照某种策略在知识库中寻找，并使用知识，直到推出最终结论为止。•推理的两个基本问题•推理的方法：解决前提和结论的逻辑关系，不确定性传递•推理的控制策略：解决推理方向，冲突消解策略44.1.2推理方法及其分类1.按推理的逻辑基础分类(1/4)•可分为演绎推理、归纳推理等•演绎推理•演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论，如假言推理、拒取式和假言三段论。•例：假言三段论•A→B，B→C⇒A→C•常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。•例如，有如下三个判断：•①计算机系的学生都会编程序；（一般性知识）•②程强是计算机系的一位学生；（具体情况）•③程强会编程序。（结论）•这是一个三段论推理。其中，①是大前提，②是小前提；③是经演绎推出来的结论。•可见，其结论是蕴含在大前提中的。54.1.2推理方法及其分类1.按推理的逻辑基础分类(2/4)•归纳推理•是一种由个别到一般的推理方法。归纳推理的类型•按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理•按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等•完全归纳推理•是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。•不完全归纳推理•是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，计算机，随机抽查。•枚举归纳推理•是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。•例如，设有如下事例：•王强是计算机系学生，他会编程序；•高华是计算机系学生，她会编程序；•…………•当这些具体事例足够多时，就可归纳出一个一般性的知识：•凡是计算机系的学生，就一定会编程序。64.1.2推理方法及其分类1.按推理的逻辑基础分类(3/4)•类比归纳推理•是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。•设A、B分别是两类事物的集合：•A={a1,a2,……}•B={b1,b2,……}•并设ai与bi总是成对出现，且当ai有属性P时，bi就有属性Q与此对应，即•P(ai)→Q(bi)i=1,2,…..•则当A与B中有一新的元素对出现时，若已知a'有属性P，b'有属性Q，即•P(a')→Q(b')•类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。74.1.2推理方法及其分类1.按推理的逻辑基础分类(4/4)•演绎推理与归纳推理的区别•演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。•归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。•例如，一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种归纳推理方式。运用这些一般性知识知识去维修计算机的过程则是演绎推理。84.1.3推理的控制策略及其分类•推理的控制策略•推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略。•推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。•控制策略的分类•由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。•推理策略•主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等•推理方向控制策略用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理。•求解策略是指仅求一个解，还是求所有解或最优解等。•限制策略是指对推理的深度、宽度、时间、空间等进行的限制。•冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。•搜索策略•主要解决推理线路、推理效果、推理效率等问题。本章主要讨论推理策略，94.1.4正向推理推理算法•从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。•算法描述•(1)把用户提供的初始证据放入综合数据库；•(2)检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；•(3)检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。•(4)按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转(2)。•(5)询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转(3)；否则表示无解，失败退出。•至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。•其流程图如下：10把初始证据放入DBDB中有解吗？KB中有可用知识吗？形成可用知识集可用知识集空吗？按照冲突消解策略从该知识集中选出一条知识进行推理推出的是新事实吗？将新事实加入到DB把用户补充的新事实加入到DB中用户可补充新事实吗？失败退出成功退出YNNYNNNYYY114.1.4正向推理推理例子•例4.1请用正向推理完成以下问题的求解•假设知识库中包含有以下2条规则：•r1：IFBTHENC•r2：IFATHENB•已知初始证据A，求证目标C。•解：本例的推理过程如下：•推理开始前，综合数据库为空。•推理开始后，先把A放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为“N”。•接着检查知识库中是否有可用知识，显然r2可用，形成仅含r2的知识集。从该知识集中取出r2，推出新的实事B，将B加入综合数据库，检查综合数据库中是否含有目标C，回答为“N”。•再检查知识库中是否有可用知识，此时由于B的加入使得r1为可用，形成仅含r1的知识集。从该知识集中取出r1，推出新的实事C，将C加入综合数据库，检查综合数据库中是否含有目标C，回答为“Y”。•它说明综合数据库中已经含有问题的解，推理成功结束，目标C得证。124.1.4正向推理优缺点•正向推理的主要优点•比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。•正向推理的主要缺点•推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。134.1.5逆向推理推理算法•从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。•算法描述：•(1)将要求证的目标（称为假设）构成一个假设集；•(2)从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步；•(3)检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一步；•(4)将知识库中可以导出该假设的所有知识构成一个可用知识集；•(5)检查可用知识集是否为空，若是，失败退出；否则执行下一步；•(6)按冲突消解策略从可用知识集中取出一个知识，继续；•(7)将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。•其流程图如下：14初始化DB和假设集该假设是DB中的事实吗？该假设能被KB中的知识导出吗？从假设集中取出一个假设可用知识集空吗？按照冲突消解策略从该知识集中选出一条知识将该知识前提中的每个子条件作为新的假设加入假设集该假设成立并放入DB还有新的假设吗？失败退出成功退出YNYYNNNNY将KB中所有能导出此假设的知识构成一个可用知识集询问用户有此事实吗？该假设成立Y154.1.5逆向推理推理例子•对上例，采用逆向推理，其推理过程如下：•推理开始前，综合数据库和假设集均为空。•推理开始后，先将初始证据A和目标C分别放入综合数据库和假设集，然后从假设集中取出一个假设C，查找C是否为综合数据库中的已知事实，回答为“N”。•再检查C是否能被知识库中的知识所导出，发现C可由r1导出，于是r1被放入可用知识集。由于知识库中只有r1可用，故可用知识集中仅含r1。•接着从可用知识集中取出r1，将其前提条件B作为新的假设放入假设集。从假设集中取出B，检查B是否为综合数据库中的实事，回答为“N”。再检查B是否能被知识库中的知识所导出，发现B可由r2导出，于是r2被放入可用知识集。由于知识库中只有r2可用，故可用知识集中仅含r2。•从可用知识集中取出r2，将其前提条件A作为新的假设放入假设集。然后从假设集中取出A，检查A是否为综合数据库中的实事，回答为“Y”。•他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。164.1.5逆向推理优缺点•逆向推理的主要优点•不必寻找和使用那些与假设目标无关的信息和知识•推理过程的目标明确•也有利于向用户提供解释，在诊断性专家系统中较为有效。•逆向推理的主要缺点•当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。174.1.6混合推理•混合推理的概念•把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。•混合推理的方法•1.先正向后逆向•这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。•2.先逆向后正向•这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。•3.双向混合•是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。•对于这些方法我不再详细讨论。18第4章确定性推理•4.1推理的基本概念•4.2推理的逻辑基础•4.3自然演绎推理•4.4归结演绎推理•4.5基于规则的演绎推理194.2推理的逻辑基础•4.2.1谓词公式的解释•4.2.2谓词公式的永真性和可满足性•4.2.3谓词公式的等价性和永真蕴含性•4.2.4谓词公式的范式•4.2.5置换与合一204.2.1谓词公式的解释概念•命题公式的解释•在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。•有了命题公式的解释，就可据此求出该命题公式的真值。•谓词公式的解释•由于谓词公式中可能包含由个体常量、变元或函数，因此，必须先考虑这些个体常量和函数在个体域上的取值，然后才能根据它们的具体取值为谓词分别指派真值。•