人工智能第四章经典逻辑推理

1第4章经典逻辑推理4.1推理的基本概念4.2自然演绎推理4.3归结演绎推理4.4与/或形演绎推理2第4章经典逻辑推理智能系统的推理过程实际上就是一种思维过程。即运用知识进行推理来求解问题。经典逻辑推理是根据经典逻辑（命题逻辑及一阶谓词逻辑）的逻辑规则进行的一种推理。由于这种推理是基于经典逻辑的，其真值只有“真”和“假”两种，因此它是一种精确推理，或称为确定性推理。34.1推理的基本概念4.1.1推理方式及其分类4.1.2推理的控制策略4.1.3模式匹配及其变量代换44.1.1推理方法及其分类1.按推理的逻辑基础分类演绎推理归纳推理默认推理54.1.1推理方法及其分类（1）演绎推理演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论，如假言推理、拒取式和假言三段论。6（1）演绎推理例：假言三段论A→B，B→C⇒A→C常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。4.1.1推理方法及其分类74.1.1推理方法及其分类（1）演绎推理例，有如下三个判断：①计算机系的学生都会编程序；（一般性知识）②程强是计算机系的一位学生；（具体情况）③程强会编程序。（结论）这是一个三段论推理。其中，①是大前提，②是小前提；③是经演绎推出来的结论。可见，其结论是蕴含在大前提中的。84.1.1推理方法及其分类（2）归纳推理是一种由个别到一般的推理方法。从足够多的事例中归纳出一般性结论的推理过程。例如，设有如下事例：王强是计算机系学生，他会编程序；高华是计算机系学生，她会编程序；…………当这些具体事例足够多时，就可归纳出一个一般性的知识：凡是计算机系的学生，就一定会编程序。94.1.1推理方法及其分类演绎推理与归纳推理的区别演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。104.1.1推理方法及其分类（3）默认推理默认推理又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。在默认推理过程中，如果某一时刻发现原先所作的默认不正确，则就要撤消所作的默认以及由此默认推出的结论，重新按新情况进行推理。114.1.1推理方法及其分类2.按推理时所用知识的确定性（1）确定性推理确定性推理是指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或者为假，没有第三种情况出现。（2）不确定性推理不确定性推理是指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假之间。（模糊集）124.1.1推理方法及其分类3.按推理过程中结论的单调性（1）单调推理单调推理是指在推理过程中随着推理过程向前推进及新知识的进入，推出的结论呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不会出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理又退回到前面的某一步。（2）非单调推理非单调推理是指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。134.1.1推理方法及其分类4.按推理过程中用到启发性知识（1）启发式推理（2）非启发式推理5.按方法论（1）基于知识的推理（2）直觉推理（常识性推理）6.按推理的简繁程度（1）简单推理（2）复合推理7.按结论是否具有必然性（1）必然性推理（2）或然性推理…………………………144.1.2推理的控制策略推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。推理方向搜索策略求解策略冲突消解限制策略151、推理方向——正向推理从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。算法描述(1)把用户提供的初始证据放入综合数据库；(2)检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；(3)检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。(4)按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转(2)。(5)询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转(3)；否则表示无解，失败退出。至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。其流程图如下：16把初始证据放入DBDB中有解吗？KB中有可用知识吗？形成可用知识集可用知识集空吗？按照冲突消解策略从该知识集中选出一条知识进行推理推出的是新事实吗？将新事实加入到DB把用户补充的新事实加入到DB中用户可补充新事实吗？失败退出成功退出YNNYNNNYYY171、推理方向——正向推理例请用正向推理完成以下问题的求解假设知识库中包含有以下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得证。18正向推理的主要优点比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。正向推理的主要缺点推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。1、推理方向——正向推理191、推理方向——逆向推理从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。算法描述：(1)将要求证的目标（称为假设）构成一个假设集；(2)从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步；(3)检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一步；(4)将知识库中可以导出该假设的所有知识构成一个可用知识集；(5)检查可用知识集是否为空，若是，失败退出；否则执行下一步；(6)按冲突消解策略从可用知识集中取出一个知识，继续；(7)将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。其流程图如下：20初始化DB和假设集该假设是DB中的事实吗？该假设能被KB中的知识导出吗？从假设集中取出一个假设可用知识集空吗？按照冲突消解策略从该知识集中选出一条知识将该知识前提中的每个子条件作为新的假设加入假设集该假设成立并放入DB还有新的假设吗？失败退出成功退出YNYYNNNNY将KB中所有能导出此假设的知识构成一个可用知识集询问用户有此事实吗？该假设成立Y211、推理方向——逆向推理例3.2用逆向推理完成以下问题的求解假设知识库中包含有以下2条规则：r1：IFBTHENCr2：IFATHENB已知初始证据A，求证目标C。推理开始前，综合数据库和假设集均为空。推理开始后，先将初始证据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得证。221、推理方向——逆向推理逆向推理的主要优点不必寻找和使用那些与假设目标无关的信息和知识推理过程的目标明确也有利于向用户提供解释，在诊断性专家系统中较为有效。逆向推理的主要缺点当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。231、推理方向——混合推理混合推理的概念把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。混合推理的应用环境已知事实不充分由正向推理得出的结论可信度不高希望得到更多的结论混合推理的方法1.先正向后逆向这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。2.先逆向后正向这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。3.双向混合是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。241、推理方向——双向推理正向推理与逆向推理同时进行，在推理过程中某一步骤上“碰头”其基本思想是：一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所要求的证据，这时推理就可结束，逆向推理的假设就是推理的最终结论。252.求解策略所谓推理的求解策略是指，推理是只求一个解，还是求所有解以及最优解等。例如前述的正向推理只用于求一个解，只要略加修改就可用来求所有解。263.限制策略为了防止无穷的推理过程，以及由于推理过程太长从而增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。27在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进行匹配，此时可能发生有多个知识匹配成功，称这种情况为发生了冲突。基本任务：解决冲突，选择其中的一条规则来执行。基本思想：对知识进行排序按针对性排序按匹配度进行排序根据领域问题的特点进行排序4.冲突消解策略284.1.3模式匹配及其变量代换模式匹配是指两个知识模式（如两个谓词公式、两个框架片断等）的比较，检查这两个知识模式是否完全一致或近似一致。如果两者完全一致，或者虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。按匹配时两个知识模式的相似程度划分，模式匹配可分为：确定性匹配不确定性匹配294.1.3模式匹配及其变量代换确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。例如，设有如下两个知识模式：P1：Father（李四，李小四）andMan(李小四)P2：Father(x,y)andMan(y)若用“李四”代换变量x，用“李小四”代换变量y，则P1与P2就变得完全