1、第第3 3章章 确定性确定性推理推理 如果如果人类的大脑简单到我们可以理解，人类的大脑简单到我们可以理解，那么我们就将愚蠢到无法理解大脑那么我们就将愚蠢到无法理解大脑。爱默生 皮尤,19773.13.1推理的基本概念推理的基本概念3.1.13.1.1推理的定义推理的定义 从从初始证据出发，按某种策略不断运用知识库中的已知知识，初始证据出发，按某种策略不断运用知识库中的已知知识，逐步推出结论的过程称为逐步推出结论的过程称为推理推理。3.13.1推理的基本概念推理的基本概念3.1.23.1.2推理方式及其分类推理方式及其分类 若从推出结论的途径来划分，推理可分为若从推出结论的途径来划分，推理可分为
2、演绎推理演绎推理、归纳推理归纳推理。p演绎推理（演绎推理（Deductive ReasoningDeductive Reasoning）是从全称判断推导出单称判）是从全称判断推导出单称判断的过程，即由一般性知识推出适合于某一具体情况的结论。断的过程，即由一般性知识推出适合于某一具体情况的结论。这是一种从一般到个别的推理。这是一种从一般到个别的推理。p归纳推理（归纳推理（Inductive ReasoningInductive Reasoning）是从足够多的事例中归纳出）是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理。一般性结论的推理过程，是一种从个别到一般的推理。3.
3、13.1推理的基本概念推理的基本概念3.1.23.1.2推理方式及其分类推理方式及其分类 若若按推理时所用知识的确定性来划分，推理可分为按推理时所用知识的确定性来划分，推理可分为确定性推确定性推理理与与不确定性推理不确定性推理。p确定性推理是指推理时所用的知识与证据都是确定的，推出的确定性推理是指推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值为真或者为假，没有第三种情况出现。结论也是确定的，其真值为真或者为假，没有第三种情况出现。p不确定性推理是指推理时所用的知识与证据不都是确定的，推不确定性推理是指推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。现实世界中的事物和
4、现象大都是不确出的结论也是不确定的。现实世界中的事物和现象大都是不确定的，或者模糊的，很难用精确的数学模型来表示与处理。定的，或者模糊的，很难用精确的数学模型来表示与处理。3.13.1推理的基本概念推理的基本概念3.1.33.1.3推理的方向推理的方向1.1.正向推理正向推理 正向推理是以已知事实作为出发点的一种推理。正向推理是以已知事实作为出发点的一种推理。正向推理的基本思想：从用户提供的初始已知事实出发，在正向推理的基本思想：从用户提供的初始已知事实出发，在知识库中找出当前可适用的知识，构成可适用知识知识库中找出当前可适用的知识，构成可适用知识集（集（KS KS），），然后按某种冲突消解策
5、略从然后按某种冲突消解策略从KSKS中选出一条知识进行推理，并将推中选出一条知识进行推理，并将推出的新事实加入数据库中作为下一步推理的已知事实，此后再在出的新事实加入数据库中作为下一步推理的已知事实，此后再在知识库中选取可适用知识进行推理，如此重复这一过程，直到求知识库中选取可适用知识进行推理，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用的知识为止。得了问题的解或者知识库中再无可适用的知识为止。3.13.1推理的基本概念推理的基本概念3.1.33.1.3推理的方向推理的方向2.2.逆向推理逆向推理 逆向推理是以某个假设目标作为出发点的一种推理逆向推理是以某个假设目标作为出发点的一
6、种推理。逆向推理逆向推理的基本思想是：首先选定一个假设目标，然后寻找的基本思想是：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需要的证据，则说明原假设是不成立的；若无论如何都找不到所需要的证据，则说明原假设是不成立的，为此需要另作新的假设。立的，为此需要另作新的假设。3.13.1推理的基本概念推理的基本概念3.1.33.1.3推理的方向推理的方向3.3.混合推理混合推理 正向推理具有盲目、效率低等缺点，推理过程中可能会推出正向推理具有盲目、效率低等缺点，推理过程中可能会推
7、出许多与问题无关的子目标。逆向推理中，若提出的假设目标不符许多与问题无关的子目标。逆向推理中，若提出的假设目标不符合实际，会降低系统的效率合实际，会降低系统的效率。为为解决这些问题，可把正向推理与逆向推理结合起来，使其解决这些问题，可把正向推理与逆向推理结合起来，使其各自发挥自己的优势，取长补短。这种既有正向又有逆向的推理各自发挥自己的优势，取长补短。这种既有正向又有逆向的推理称为混合推理称为混合推理。3.13.1推理的基本概念推理的基本概念3.1.43.1.4冲突消解策略冲突消解策略 在在推理过程中，系统要不断地用当前已知的事实与知识库中推理过程中，系统要不断地用当前已知的事实与知识库中的知
8、识进行匹配。此时，可能发生如下三种情况。的知识进行匹配。此时，可能发生如下三种情况。已知事实恰好只与知识库中的一个知识匹配已知事实恰好只与知识库中的一个知识匹配成功；成功；已知事实不能与知识库中的任何知识匹配已知事实不能与知识库中的任何知识匹配成功；成功；已知事实可与知识库中的多个知识匹配已知事实可与知识库中的多个知识匹配成功；成功；3.13.1推理的基本概念推理的基本概念3.1.43.1.4冲突消解策略冲突消解策略 推理推理过程中不仅有知识匹配成功，而且有多个知识匹配成功，过程中不仅有知识匹配成功，而且有多个知识匹配成功，称为发生了称为发生了冲突冲突。按一定的策略从匹配成功的多个知识中挑出一
9、。按一定的策略从匹配成功的多个知识中挑出一个知识用于当前的推理的过程称为个知识用于当前的推理的过程称为冲突消解冲突消解。解决解决冲突时所用的策略称为冲突时所用的策略称为冲突消解策略冲突消解策略。3.13.1推理的基本概念推理的基本概念3.13.1推理的基本概念推理的基本概念3.1.43.1.4冲突消解策略冲突消解策略2.2.按已知事实的新鲜性排序按已知事实的新鲜性排序 在在产生式系统的推理过程中，每应用一条产生式规则就会得到一个或多产生式系统的推理过程中，每应用一条产生式规则就会得到一个或多个结论或者执行某个操作，数据库就会增加新的事实个结论或者执行某个操作，数据库就会增加新的事实。一般一般把
10、数据库中后生成的事实称为新鲜的事实，即后生成的事实比先生把数据库中后生成的事实称为新鲜的事实，即后生成的事实比先生成的事实具有较大的新鲜性成的事实具有较大的新鲜性。若若一条规则被应用后生成了多个结论，则既可以认为这些结论有相同的一条规则被应用后生成了多个结论，则既可以认为这些结论有相同的新鲜性，也可以认为排在前面（或后面）结论有较大的新鲜性，根据情况决新鲜性，也可以认为排在前面（或后面）结论有较大的新鲜性，根据情况决定。定。3.13.1推理的基本概念推理的基本概念3.23.2自然演绎推理自然演绎推理3.23.2自然演绎推理自然演绎推理3.23.2自然演绎推理自然演绎推理3.23.2自然演绎推理
11、自然演绎推理3.23.2自然演绎推理自然演绎推理3.23.2自然演绎推理自然演绎推理#程序程序3.1 3.1 父子和爷孙关系父子和爷孙关系推理推理3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取定理定理3.13.1：谓词公式不可满足的充要条件是其子句集不可满足。：谓词公式不可满足的充要条件是其子句集不可满足。由此定理可知，要证明一个谓词公式是不可满足的，只要
12、证明相应的子由此定理可知，要证明一个谓词公式是不可满足的，只要证明相应的子句集是不可满足的就可以了。句集是不可满足的就可以了。3.33.3子句集的求取子句集的求取3.33.3子句集的求取子句集的求取3.43.4归结原理归结原理 鲁宾逊归结原理鲁宾逊归结原理 子句子句集中子句之间是合取关系，其中只要有一个子句不可满足，则子句集中子句之间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足集就不可满足。由于由于空子句是不可满足的，所以，若一个子句集中包含空子句，则这个空子句是不可满足的，所以，若一个子句集中包含空子句，则这个子句集一定是不可满足的子句集一定是不可满足的。鲁宾逊归结原理：鲁宾逊
13、归结原理：检查子句集检查子句集S S中是否包含空子句，若包含，则中是否包含空子句，若包含，则S S不可满不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结得到足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结得到空子句，就说明子句集空子句，就说明子句集S S是不可满足的。是不可满足的。3.43.4归结原理归结原理3.43.4归结原理归结原理3.43.4归结原理归结原理3.43.4归结原理归结原理3.43.4归结原理归结原理3.43.4归结原理归结原理3.53.5归结反演归结反演3.53.5归结反演归结反演3.63.6归结原理求解问题归结原理求解问题3.63.6归结
14、原理求解问题归结原理求解问题3.63.6归结原理求解问题归结原理求解问题3.63.6归结原理求解问题归结原理求解问题3.73.7非单调推理非单调推理 建立建立在谓词逻辑基础上的传统系统是单调的，这意味着，已知为真的命在谓词逻辑基础上的传统系统是单调的，这意味着，已知为真的命题数目将随时间而严格增加题数目将随时间而严格增加。这种这种系统具有以下优点：系统具有以下优点：（1 1）当加人一个新命题时，不必检查新命题与原有知识之间的不相容性。）当加人一个新命题时，不必检查新命题与原有知识之间的不相容性。（2 2）对每一个已被证明了的命题，不必保留一个命题表）对每一个已被证明了的命题，不必保留一个命题表
15、。它它的证明以该命题表中的命题为根据，因为不存在那些命题会被取消的的证明以该命题表中的命题为根据，因为不存在那些命题会被取消的危险危险。3.73.7非单调推理非单调推理 非单调推理系统的必要性：非单调推理系统的必要性：（1 1）不完全知识的出现要求缺省推理。不完全知识的出现要求缺省推理。（2 2）一个不断变化的世界必须用适应不断变化的数据库来描述。一个不断变化的世界必须用适应不断变化的数据库来描述。（3 3）产生一个问题的完全解可能要求关于部分解的暂时的假设。产生一个问题的完全解可能要求关于部分解的暂时的假设。3.73.7非单调推理非单调推理3.7.13.7.1缺省推理缺省推理 很少很少有能在
16、处理过程中拥有它所需要的一切信息的有能在处理过程中拥有它所需要的一切信息的系统，当系统，当缺乏信息时，缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省缺省推理推理。3.7.23.7.2真值维持系统真值维持系统 真值维持系统真值维持系统（Truth Maintenance SystemTruth Maintenance System，TMSTMS）是一个已经实现了的）是一个已经实现了的非单调推理系统，它用以协助其他推理程序维持系统的正确性，所以它的作非单调推理系统，它用以协助其他推理程序维持系统的正确性，
17、所以它的作用不是生成新的推理，而是在其他程序所产生的命题之间保持相容性用不是生成新的推理，而是在其他程序所产生的命题之间保持相容性。一旦一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容。并通过修改最小的信念集来消除不相容。3.73.7非单调推理非单调推理 在在TMSTMS中，每一个命题或规则均称为节点，且对任一节点，以下两种状态中，每一个命题或规则均称为节点，且对任一节点，以下两种状态必居其一：必居其一：IN IN 相信相信为真。为真。OUT OUT 不相信为真，或无理由相信为真，或当
18、前没有可相信的理由。不相信为真，或无理由相信为真，或当前没有可相信的理由。每个节点附有一张证实表，表中每一项表示一种确定节点有效性的方法。每个节点附有一张证实表，表中每一项表示一种确定节点有效性的方法。节点是指那些至少有一个在当前说来是有效证实的节点节点是指那些至少有一个在当前说来是有效证实的节点。3.83.8小结小结 从从初始证据出发，按某种策略不断运用知识库中的已知知识，逐步推出初始证据出发，按某种策略不断运用知识库中的已知知识，逐步推出结论的过程称为结论的过程称为推理推理。原子谓词公式及其否定，称为原子谓词公式及其否定，称为文字文字。任何文字的析取式称为。任何文字的析取式称为子句子句。把
19、谓。把谓词公式可以化成子句集。谓词公式不可满足的充要条件是其子句集不可满足。词公式可以化成子句集。谓词公式不可满足的充要条件是其子句集不可满足。鲁宾逊归结原理是机器定理证明的基础，是一种证明子句集不可满足性，鲁宾逊归结原理是机器定理证明的基础，是一种证明子句集不可满足性，从而实现定理证明的一种理论及方法。从而实现定理证明的一种理论及方法。3.83.8小结小结 应用应用归结原理求解问题的方法：把已知前提用谓词公式表示出来，并且归结原理求解问题的方法：把已知前提用谓词公式表示出来，并且化为相应的子句集，把待求解的问题也用谓词公式表示出来，然后把它否定化为相应的子句集，把待求解的问题也用谓词公式表示出来，然后把它否定并与谓词并与谓词ANSWERANSWER构成析取式，化为子句集；对子句集进行归结，若得到归结构成析取式，化为子句集；对子句集进行归结，若得到归结式式ANSWERANSWER，则答案就在，则答案就在ANSWERANSWER中中。非单调推理非单调推理包括缺省推理和真值维持系统。包括缺省推理和真值维持系统。
