人工智能第四部分

1、1第四部分 逻辑推理2 对很多复杂的系统和问题，如果采用搜索推理方法，可能很难甚至无法使问题获得解决，需要应用一些更先进的推理技术来求解。 利用知识表示方法，可以把给定的领域问题用某种形式表示出来，并存放到计算机中。但是，一个智能系统仅有知识是不够的，还应该能够很好地利用这些知识，即运用知识进行推理和求解问题。 智能系统的推理过程实际上是一种思维过程的模拟。3 推理的基本概念 推理的逻辑基础 自然演绎推理 归结演绎推理内容提要4一. 什么是推理二. 推理的基本方法及分类三. 推理的控制策略及其分类四. 正向推理五. 逆向推理六. 混合推理七. 推理的冲突消解策略1. 推理的基本概念5 所谓推理

2、是指按照某种策略从已知事实出发去推出结论的过程。 推理所用的事实包括两种情况：一种是与求解问题有关的初始证据，另一种是推理过程中所得到的中间结论。 通常，智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统中用来实现推理的程序。一. 什么是推理6 例如，在医疗诊断专家系统中，所有与诊断有关的医疗常识和专家经验都被保存在知识库中。 当系统开始诊断疾病时，首先需要把病人的症状和检查结果放到事实库中，然后再从事实库中的这些初始证据出发，按照某种策略在知识库中寻找可以匹配的知识，如果得到的是一些中间结论，还需要把它们作为已知事实放入事实库中，并继续寻找可以匹配的知识，如此反复进行，直到推出最

3、终结论为止。 这种由初始事实出发到推出最终结论为止的这一过程就是推理，实现这一推理过程的程序称为推理机。7 推理方法主要解决在推理过程中前提与结论之间的逻辑关系，以及在非精确性推理中不确定性的传递问题。推理可以有多种不同的分类方法，例如，可以按照推理的逻辑基础、所用知识的确定性、推理过程的单调性以及是否使用启发性信息等来划分。1按推理的逻辑基础分类 按照推理的逻辑基础，常用的推理方法可分为演绎推理、归纳推理和默认推理。 二. 推理方法及其分类8（1）演绎推理 演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论。

4、常用的三段论是由一个大前提、一个小前提和一个结论三部分组成的。其中，大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。9例如，有三个判断： 计算机系的学生都会编程序； 程强是计算机系的一位学生； 程强会编程序。 这是一个三段论推理。 其中，是大前提;是小前提；是经演绎推出来的结论。 从这个例子可以看出，“程强会编程序”这一结论是蕴含在“计算机系的学生都会编程序”这个大前提中的。因此，演绎推理就是从已知的大前提中推导出适应于小前提的结论，即从已知的一般性知识中抽取所包含的特殊性知识。由此可见，只要大前提和小前

5、提是正确的，则由它们推出的结论也必然是正确的。10（2）归纳推理 归纳推理是从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。它是一种由个别到一般的推理方法。 归纳推理的基本思想是：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。 对于归纳推理，如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理；如果按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。11 所谓完全归纳推理是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，来推出该类事物是否具有此属性。 例如，某公

6、司购进一批计算机，如果对每台机器都进行了质量检验，并且都合格，则可得出结论：这批计算机的质量是合格的。 所谓不完全归纳推理是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。 例如，某公司购进一批计算机，如果只是随机地抽查了其中的部分机器，便可根据这些被抽查机器的质量来推出整批机器的质量。 12 所谓枚举归纳推理是指在进行归纳时，如果已知某类事物的有限个具体事物都具有某种属性，则可推出该类事物都具有此种属性。 设a1,a2,an是某类事物A中的具体事物，若已知a1，a2，an都具有属性B，并没有发现反例，那么当n足够大时，就可得出“A中的所有事物都具有属性B”这一结论。13

7、例如，设有如下事例： 王强是计算机系学生，他会编程序； 高华是计算机系学生，她会编程序； 李明是计算机系学生，他会编程序； 赵杰是计算机系学生，他会编程序。 当这些具体事例足够多时，就可归纳出一个一般性的知识：凡是计算机系的学生，就一定会编程序。 按照枚举法归纳出来的知识，尽管可能会有个别反例，但一般来说还是合理的。14 所谓类比推理是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。 设A、B分别是两类事物的集合： A=a1，a2， B=b1，b2，并设ai与bi总是成对出现，且当ai有属性P时，bi就有属性Q与之对应，即 P（ai）Q（bi）

8、 il，2，则当A与B中有一新的元素对出现时，若已知a有属性P，则认为b有属性Q，即 P（a) Q（b) 类比推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。15（3）默认推理 默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺省推理。 在推理过程中，如果发现原先的假设不正确，就撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。 默认推理允许在推理过程中假设某些条件是成立的，从而解决了在一个不完备的知识集中进行推理的问题。16（4）演绎推理与归纳推理的区别 演绎推理与归纳推理是

9、两种完全不同的推理。 演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。17 在归纳推理中，所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。 例如，一位计算机维修员，当他刚开始从事这项工作时，只有书本知识，而无实际经验。但当他经过一段时间的工作实践后，就会通过大量实例积累起来一些经验，这些经验就是由一个个实例归纳出来的一般性知识，采用的是归纳推理方式。当它有了这些一般性知识后，就可以运用这些知

10、识去完成计算机的维修工作。而这种为某一台具体的计算机运用一般性知识进行维修的过程则是演绎推理。182按所用知识的确定性分类 按所用知识的确定性，推理可分为确定性推理和不确定性推理。 所谓确定性推理是指推理所使用的知识和推出的结论都是可以精确表示，其真值要么为真，要么为假，不会有第三种情况出现。 所谓不确定性推理是指推理时所用的知识不都是确定的，推出的结论也不完全是确定的，其真值会位于真与假之间。由于现实世界中的大多数事物都具有一定程度的不确定性，并且这些事物是很难用精确的数学模型来进行表示与处理的，因此不确定性推理也就成了人工智能的一个重要研究课题。193按推理过程的单调性 按照推理过程的单调

11、性，或者说按照推理过程所得到的结论是否越来越接近目标，推理可分为单调推理与非单调推理。 所谓单调推理是指在推理过程中，每当使用新的知识后，所得到的结论会越来越接近于目标，而不会出现反复情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理过程又退回到先前的某一步。20 非单调推理是指在推理过程中，当某些新知识加入后，会否定原来推出的结论，使推理过程退回到先前的某一步。 非单调推理往往是在知识不完全的情况下发生的。在这种情况下，为使推理能够进行下去，就需要先作某些假设，并在此假设的基础上进行推理。但是，当后来由于新的知识加入，发现原来的假设不正确时，就需要撤销原来的假设以及由此假设为基础推

12、出的一切结论，再运用新知识重新进行推理。 21 智能系统的推理过程模拟人的思维过程，不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。 推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。 智能系统的推理过程一般表现为一种搜索过程，推理的控制策略又可分为推理策略和搜索策略。 推理策略主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等； 搜索策略主要解决推理线路、推理效果、推理效率等问题。三. 推理的控制策略及其分类22 推理方向用来确定推理的控制方式，即推理过程是从初始证据开始到目标，还是从目标开始到初始证据。 按照对推理方向的控制，推理可

13、分为正向推理、逆向推理、混合推理及双向推理四种情况。 无论哪一种推理方式，系统都需要有一个存放知识的知识库，一个存放初始证据及中间结果的综合数据库和一个用于推理的推理机。 求解策略是指仅求一个解，还是求所有解或最优解等。 限制策略是指对推理的深度、宽度、时间、空间等进行限制。 冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。 23 正向推理是一种从已知事实出发、正向使用推理规则的推理方式，亦称为数据驱动推理或前项链推理。 其基本思想是：用户需要事先提供一组初始证据，并将其放入综合数据库。推理开始后，推理机根据综合数据库中的已有事实，到知识库中寻

14、找当前可用知识，形成一个当前可用知识集，然后按照冲突消解策略，从该知识集中选择一条知识进行推理，并将新推出的事实加入综合数据库，作为后面继续推理时可用的已知事实，如此重复这一过程，直到求出所需要的解或者知识库中再无可用知识为止。四. 正向推理24 正向推理算法： （1）把用户提供的初始证据放入综合数据库。 （2）检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功退出；否则执行下一步。 （3）检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转（5）。 （4）按照某种冲突消解策略，从当前可用知识集中选出一条知识进行推理，并将推出的新事实加入综合数据库中，然后转（

15、2）。 （5）询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转（3）；否则表示无解，失败退出。25成功退出失败退出把初始数据放入综合数据库综合数据库中有解吗？形成可用知识集可用知识 集 空？按照冲突消解策略从该知识集中选出一条知识进行推理推出的是新事实？将该新事实加入到综合数据库中把用户补充的新事实加入到综合数据库中用户可以补充新事实吗？知识库中有可 用知识吗？YYYYYNNNNN 正向推理的流程图26 仅从正向推理的算法来看比较简单，但实际上推理的每一步都有许多工作要做。 例如，如何根据综合数据库中的事实到知识库中选取可用知识；当知识库中有多条知识可用时

16、应该先使用哪一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略。 正向推理的优点是比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。 其主要缺点是推理无明确目标，求解问题时可能会执行许多与解无关的操作，导致推理效率较低。27 逆向推理是一种以某个假设目标作为出发点的推理方法，也称为目标驱动推理或逆向链推理。 其基本思想为： 首先根据问题求解的要求，将要求证的目标（称为假设）构成一个假设集； 然后从假设集中取出一个假设对其进行验证，检查该假设是否在综合数据库中、是否为用户认可的事实，当该假设在数据库中时，该假设成立，此时若假设集为空，则成功退出； 若假

17、设不在综合数据库中，但可被用户证实为原始证据时，将该假设放入综合数据库，此时若假设集为空，则成功退出； 若假设可由知识库中的一个或多个知识导出，则将知识库中所有可以导出该假设的知识构成一个可用知识集，并根据冲突消解策略从可用知识集中取出一个知识，将其前提中的所有子条件都作为新的假设放入假设集。 重复上述过程，直到假设集为空时成功退出，或假设集非空但可用知识集为空时失败退出为止。 五. 逆向推理28逆向推理算法： （1）将要求证的目标（称为假设）构成一个假设集； （2）从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行（2）；若该

18、假设不在数据库中，则执行下一步； （3）检查该假设是否可由知识库的某个知识导出。若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转（5）；若能由某个知识导出，则执行下一步； （4）将知识库中可以导出该假设的所有知识构成一个可用知识集； （5）检查可用知识集是否为空，若空，失败退出；否则执行下一步； （6）按冲突消解策略从可用知识集中取出一个知识，继续执行下一步； （7）将该知识的前提中的每个子条件都作为新的假设放入假设集，转（2）。29建立假设集从假设集中取出一个假设该假设是综合数据库中的事实该假设能被库

19、中的知识导出吗？将知识库中所有能导出此假设的知识构成一个可用知识集可用知识集空吗将该知识前提中的每个子条件都作为新的假设放入假设集按冲突消解策略从可用知识库中取出一个知识该假设成立还有新的假设吗假设成立，并放入综合数据库询问有此事实吗？失败退出失败退出成功退出成功退出YYYYYNNNN 逆向推理的流程图逆向推理的流程图 30 以上算法仅是逆向推理的一个框架性描述，具体实现时有许多问题需要考虑。如： 第一，算法开始时，初始假设应该选择准确，否则会影响推理机的效率。现有的方法有两种：一种是由用户提出，这种方法简单，但自动化程度差；另一种是系统自主提出，这种方法自动化程度较高但盲目性较大。 第二，当

20、一个假设所对应的知识的前提为多个子条件的逻辑组合时，这些子条件可能是与的关系，也可能是或的关系。当为与关系时，若这些子条件之间隐含有某种必须遵守的隐含顺序，则首先按隐含顺序求解；若不存在这种隐含顺序，则应优先选择可能为假的子条件进行推理。当子条件之间为或关系时，则应优先选择可能为真的子条件。这样可以减少推理费用。31第三，在验证一个子条件时，需要把它作为新的假设，并查找可以导出此新假设的知识，这就又会产生一组新的子条件，推理过程如此不断地进行下去，就会产生处于不同层次上的多组子条件，它将形成一种树状结构。当推理到达一个叶节点（即综合数据库中存在的事实或由用户认可的事实）时，又会逐层向上返回，并

21、且在返回过程中，又可能需要再次向下。如此多次上下反复，才会证明初始假设是否成立，可见这是一个十分复杂的过程。32例：设推理开始时，知识库中的规则和综合数据库中的事实如下：例：设推理开始时，知识库中的规则和综合数据库中的事实如下： 规则规则1 1：IF IF 你丢了自行车钥匙，并且车胎没气你丢了自行车钥匙，并且车胎没气 THEN THEN 自行车不能骑自行车不能骑 规则规则2 2：IF IF 自行车不能骑，并且你只有走路去自行车不能骑，并且你只有走路去 THEN THEN 你听课会迟到你听课会迟到 事实事实1 1：你丢了自行车钥匙：你丢了自行车钥匙 事实事实2 2：车胎没气：车胎没气 如果利用逆

22、向推理求证如果利用逆向推理求证“你听课会迟到你听课会迟到”这一假设，其推理过程如这一假设，其推理过程如下：下：33例：设推理开始时，知识库中的规则和综合数据库中的事实如下：例：设推理开始时，知识库中的规则和综合数据库中的事实如下： 规则规则1 1：IF IF 你丢了自行车钥匙，并且车胎没气你丢了自行车钥匙，并且车胎没气 THEN THEN 自行车不能骑自行车不能骑 规则规则2 2：IF IF 自行车不能骑，并且你只有走路去自行车不能骑，并且你只有走路去 THEN THEN 你听课会迟到你听课会迟到 事实事实1 1：你丢了自行车钥匙：你丢了自行车钥匙 事实事实2 2：车胎没气：车胎没气 如果利用

23、逆向推理求证如果利用逆向推理求证“你听课会迟到你听课会迟到”这一假设，其推理过程如下：这一假设，其推理过程如下：推理开始时，假设集中只有一个假设推理开始时，假设集中只有一个假设“你听课会迟到你听课会迟到”。首先从假设集中取出。首先从假设集中取出该假设，然后查找综合数据库，知该假设不是综合数据库中的事实。再查找知识库，该假设，然后查找综合数据库，知该假设不是综合数据库中的事实。再查找知识库，发现该假设可由规则发现该假设可由规则2 2导出，于是规则导出，于是规则2 2被放入可用知识集。由于只有这一条规则可被放入可用知识集。由于只有这一条规则可用，故可用知识集中只有规则用，故可用知识集中只有规则2

24、2。 从可用知识集中取出规则从可用知识集中取出规则2 2，将其两个前提条件，将其两个前提条件“自行车不能骑自行车不能骑”和和“你只有走你只有走路去路去”都作为新的假设放入假设集。此后，从假设集中取出一个假设都作为新的假设放入假设集。此后，从假设集中取出一个假设“自行车不能自行车不能骑骑”，它不是综合数据库中的事实，但可由规则，它不是综合数据库中的事实，但可由规则1 1导出，于是规则导出，于是规则1 1被放入可用知识被放入可用知识集，此时可用知识集中仍然是只有一条规则。从可用知识集中提出规则集，此时可用知识集中仍然是只有一条规则。从可用知识集中提出规则1 1，将其两个，将其两个前提条件前提条件“

25、你丢了自行车钥匙你丢了自行车钥匙”和和“车胎没气车胎没气”也作为新的假设放入假设集。此后，也作为新的假设放入假设集。此后，再从假设集中取出一个假设再从假设集中取出一个假设“你只有走路去你只有走路去”，检查发现此假设既不在综合数据库，检查发现此假设既不在综合数据库中，也不能被任何一条规则所导出，询问用户中，也不能被任何一条规则所导出，询问用户“你只有走路去吗？你只有走路去吗？”，若用户回答，若用户回答“是是”，则该假设成立，并被放入综合数据库。此时，假设集中还有两个假设，则该假设成立，并被放入综合数据库。此时，假设集中还有两个假设“你你丢了自行车钥匙丢了自行车钥匙”和和“车胎没气车胎没气”，继续

26、推理，很显然它们都是综合数据库中的事，继续推理，很显然它们都是综合数据库中的事实，均为真。继续推理，假设库也为空，推理过程结束，实，均为真。继续推理，假设库也为空，推理过程结束，“你听课会迟到你听课会迟到”得证。得证。 在上述例子中，如果询问用户在上述例子中，如果询问用户“你只有走路吗？你只有走路吗？”时，用户回答时，用户回答“否否”，则，则“你只有走路去你只有走路去”这一假设不成立，应再检查可用知识集中是否还有可用知识，但这一假设不成立，应再检查可用知识集中是否还有可用知识，但此时可用知识集中已无可用知识，且假设库非空，故失败退出。此时可用知识集中已无可用知识，且假设库非空，故失败退出。34

27、 逆向推理的主要优点是不必寻找和使用那些与假设目标无关的信息和知识，推理过程的目标明确，同时也有利于向用户提供解释，在诊断性专家系统中较为有效。其主要缺点是当用户对解的情况认识不清时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。35 正向推理和逆向推理都有各自的优缺点。当问题较复杂时，单独使用其中的哪一种，都会影响到推理效率。为了更好地发挥这两种算法各自的长处，避免各自的短处，互相取长补短，可以将它们结合起来使用。这种把正向推理和逆向推理结合起来所进行的推理称为混合推理。1混合推理的方法 混合推理可有多种具体的实现方法。例如，可以采用先正向推理，后逆

28、向推理的方法；也可以采用先逆向推理，后正向推理的方法；还可以采用随机选择正向和逆向推理的方法。下面分别对这三种情况进行讨论。六. 混合推理36（1）先正向后逆向的混合推理 这种方法先进行正向推理，从已知事实出发推出部分结果，然后将这些部分结果作为事实放入综合数据库中，以此为依据进行逆向推理。其推理过程如右图所示。 开始开始进行正向推理进行正向推理需要逆向推理需要逆向推理吗？吗？以正向推理所得结果作以正向推理所得结果作为事实进行逆向推理为事实进行逆向推理还需要正向还需要正向推理吗？推理吗？退出退出先正向后逆向推理的流程图先正向后逆向推理的流程图 NNYY37（2）先逆向后正向的混合推理 这种方法

29、先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。其推理过程如右图所示。开始开始进行逆向推理进行逆向推理需要正需要正向推理向推理吗吗？进行正向推理进行正向推理还需要逆向还需要逆向推理吗？推理吗？退出退出先逆向再正向推理的流程图 NNYY38（3）双向混合推理 所谓双向混合推理是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。 其基本思想是：依据某种选择，先根据问题的已知事实进行正向推理，或从假设目标出发进行逆向推理。在整个推理过程中，两种控制策略依据一定的算法交替执行交替执行。正向推理时不期望从初始证据一直推到最终目标，逆向推理时也不期望从

30、某个假设一直推到原始事实，而是期望推理过程在中间的某处汇合。这种汇合表明了正向推理所得到的中间结果满足了逆向推这种汇合表明了正向推理所得到的中间结果满足了逆向推理的要求，也就表明了双向混合推理的成功理的要求，也就表明了双向混合推理的成功。 如果在推理过程的某一步，正向推理的结论否认了逆向推理中的某个子假设，则说明逆向推理中该子假设的选择错误，从而可终止该子假设，这样可减少由于假设选择盲目性所造成的损失。39开始开始选择推理方向选择推理方向是正向吗是正向吗？进行逆向推理进行逆向推理进行正向推理进行正向推理比较正向推出的结论和比较正向推出的结论和逆向推出的结论逆向推出的结论匹配吗匹配吗？成功，退出

31、成功，退出YNN 双向混合推理的流程图双向混合推理的流程图 40 2混合推理的适用场合 混合推理通常用于以下几种情况： （1）已知事实不够充分 如果综合数据库中的已知事实不够充分，当用这些事实与知识库中知识的前提条件进行匹配时，很可能找不到一个可以匹配的知识，这就使得推理无法进行下去。此时，可把那些条件部分不能匹配的知识都找出来，并把这些知识的结论作为假设进行逆向推理。由于在逆向推理中可以向用户询问有关证据，这就有可能使推理再进行下去。像这种需要先通过正向推理形成假设，然后再通过逆向推理去证实假设的情况特别适合采用混合推理。 41 （2）由正向推理推出的结论可信度不高 有些问题，采用正向推理虽

32、然可以推出结论，但其可信度不高，甚至会低于规定的阈值。此时，可选择几个可信度相对较高的结论作为假设，然后进行逆向推理。这样，通过进一步向用户询问证据，有可能会推出可信度较高的结论。 42（3）希望得出更多的结论 在逆向推理中，由于要与用户对话，这样就会获得一些原来未知的证据。这些证据不仅可用来证实需要证明的假设，同时还可能推出其他结论。此时，可通过使用正向推理，充分利用这些新获得的证据去推出另外一些结论。（4）希望从正反两个方向同时进行推理 有时，可能会希望从正反两个方向同时进行推理，即根据问题初始证据进行正向推理，同时由假设的结论进行逆向推理。 43 在推理的某一步，如果知识库中有多条知识可

33、用，则称发生了冲突。此时，需要按照某种策略从这多条知识中选择一条最佳知识用于推理，称这种解决冲突的过程为冲突消解。冲突消解所用的策略则称为冲突消解策略。 七. 推理的冲突消解策略44 冲突消解的基本思想是对可用知识进行排序。常用的冲突消解策略有:1特殊知识优先 这种策略把知识的特殊性作为选择知识的依据，优先选择那种更具有特殊性的知识。在当前可用知识中，特殊性知识一般是要求前提条件更多的知识，特殊性知识比一般性知识具有针对性更强，结论更接近于目标的特点。优先选择特殊性知识，会缩短推理过程。452新鲜知识优先 这种策略把知识的新鲜性作为选择知识的依据，优先选择更新鲜的知识，认为新鲜知识是对老知识的

34、更新和改进，比老知识更有效。 知识的新鲜性是根据该知识前提中所用事实的新鲜性来确定的，而事实的新鲜性则是根据其在综合数据库中生成的先后顺序确定的。一般来说，在综合数据库中后生成的事实比先生成的事实具有更大的新鲜性。 当可用知识的前提均为多个事实的逻辑组合时，比较两条知识新鲜性的方法有以下三种：46 （1）按前提中新鲜事实的个数进行比较。如果一个知识前提中包含的新鲜事实比另一个知识前提中包含的新鲜事实多，则包含新鲜事实多的知识为更新鲜知识。 （2）按前提中最新鲜的事实进行比较。如果一个知识的前提中包含的最新鲜事实比另一个知识前提中包含的最新鲜事实更新鲜，则包含有更新鲜事实的知识为更新鲜知识。 （

35、3）按前提中最不新鲜的事实进行比较。如果一个知识的前提中包含的最不新鲜事实比另一个知识前提中包含的最不新鲜事实更不新鲜，则包含有更不新鲜事实的知识为更不新鲜知识。473差异性大的知识优先 这种策略把知识的差异度作为选择知识的依据，优先选择与上一次使用过的知识差别大的知识。这样，可以避免重复执行那些相近知识，防止系统在某个问题附近进行低效的、重复性的推理。4领域特点优先 这种策略把领域问题的特点作为选择知识的依据，即根据领域问题的特点把知识排成一定顺序，然后按照这种顺序选择知识。5上下文关系优先 这种策略把知识的上下文关系作为选择知识的依据，即把知识库中的知识按照其上下文关系分成若干组，在推理过

36、程的任一步，都只能从与当时状态有关的知识组中选择知识。486前提条件少者优先 这种策略把知识的前提条件个数作为选择知识的依据，在结论相同的多个知识中优先选择前提条件少的知识。原因是前提条件少的知识在匹配时所花的时间也少。 除了上面所讨论的几种策略以外，还有一些策略可以使用。例如，在非确定性推理中可以按知识的匹配度选择知识等。同时，对上述策略也可以组合起来使用，形成综合冲突消解策略。49一. 谓词公式的解释二. 谓词的永真性和可满足性三. 谓词公式的等价性与永真蕴含性四. 谓词公式的范式五. 置换与合一2. 推理的逻辑基础50 前面讨论了知识表示的一阶谓词逻辑表示法，已经具备了谓词逻辑的一些简单

37、概念。本节主要讨论推理所需的逻辑基础。 在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。有了命题公式的解释，就可以求出该命题公式的真值。 但谓词逻辑则不同，由于谓词公式中可能包含有个体常量、个体变元或函数，因此不能像命题公式那样直接通过真值指派给出解释，必须先考虑个体常量和函数在个体域上的取值，然后才能根据常量与函数的具体取值为谓词分别指派真值。下面给出谓词公式的解释的定义。一. 谓词公式的解释51定义：设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值： （1）为每个个体常量指派D中的一个元素； （2）为每个n元函数指派一个从Dn到D的一

38、个映射，其中 Dn (x1,x2,xn)|x1,x2,xn D （3）为每个n元谓词指派一个从Dn到T,F的映射 则称这些指派为P在D上的一个解释。52例：设个体域例：设个体域D=1,2，求公式求公式A=( x)(彐彐y)P(x,y) 在在D上的解释，并指出在每一上的解释，并指出在每一种解释下公式种解释下公式A的真值。的真值。解解: 由于公式由于公式A中没有包含个体常量和函数，因此可以直接为谓词指派真值，设有中没有包含个体常量和函数，因此可以直接为谓词指派真值，设有: 这就是公式这就是公式A在在D上的一个解释。从这个解释可以看出：上的一个解释。从这个解释可以看出： 当当x=1、y=1 时，有时

39、，有P(x,y)的真值为的真值为T； 当当x=2，y=1 时，有时，有P(x,y)的真值为的真值为T；即对即对x 在在D上的任意取值，都存在上的任意取值，都存在y=1使使P(x,y)的真值为的真值为T。因此，在此解释下公式因此，在此解释下公式A的真值为的真值为T。 需要注意，一个谓词公式在其个体域上的解释不是唯一的。例如，对公式需要注意，一个谓词公式在其个体域上的解释不是唯一的。例如，对公式A，若给出另一组真值若给出另一组真值指派指派 这也是公式这也是公式A在在D上的一个解释。从这个解释可以看出：上的一个解释。从这个解释可以看出： 当当x=1、y=1 时，有时，有P(x,y) 的真值为的真值为

40、T； 当当x=2、y=1 时，有时，有p(x,y)的真值为的真值为F；同样同样 当当x=1、y=2 时，有时，有P(x,y) 的真值为的真值为T； 当当x=2、y=2 时，有时，有P(x,y)的真值为的真值为F；即对即对x在在D上的任意取值，不存在一个上的任意取值，不存在一个y 使得使得P(x,y)的真值为的真值为T。因此，在此解释下公式因此，在此解释下公式A的真值为的真值为F。 实际上，实际上，A在在 D上共有上共有 16种解释，这里就不再种解释，这里就不再一列举。一列举。53例：设个体域D=1，2，求公式B=（ x）P（f（x），a）在D上的解释，并指出在该解释下公式A的真值。 解：设对个

41、体常量a和函数f（x）的真值指派为： 对谓词的真值指派为： 这里，由于已知指派a=1，所以P（1，2）和P（2，2）不可能出现，故没有给它们指派真值。 上述指派是公式B在D上的一个解释。在此解释下有 当x=1时，a=1使P（1，1）=T 当x=2时，a=1使P（2，1）=T即对x在D上的任意取值，都有P（f(x)，a）的真值为T。因此，在此解释下公式B的真值为T。 由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为能在某一个解释下真值为 T T，而在另一个解释下为而在另一个解释下为 F F。

42、54 为了以后推理的需要，下面先定义谓词公式的永真性、永假性、可满足性与不可满足性。 定义1：如果谓词公式P对非空个体域D上的任一解释都取得真值T，则称P在D上是永真的；如果P在任何非空个体域上均是永真的，则称P永真。 由此定义可以看出，要判定一个谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数无限时，其永真性就很难判定了。二. 谓词公式的永真性与可满足性55 定义2：对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的。谓词公式的可满足性又称为相容性. 定义

43、3：如果谓词公式P对非空个体域D上的任一解释都取真值F，则称P在D上是永假的；如果P在任何非空个体域上均是永假的，则称P永假。 谓词公式的永假性又称不可满足性或不相容性。56三. 谓词公式的等价性与永真蕴含性 谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真蕴含式来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规则推理规则。1等价式 谓词公式的等价式可定义如下： 定义：设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D上是等价的。如果D是任意非空个体域，则称P与Q是等价的，记作PQ。57常用的等价式： （1）双重否定率 P P

44、（2）交换率 PQ QP， PQ QP （3）结合率 （PQ）R P（QR）,（PQ）RP （QR） （4）分配率 P（QR）（PQ）（PR） P（QR）（PQ）（PR） （5）狄摩根定律 （PQ） P Q （PQ） P Q （6）吸收率 P（PQ）P， P（P Q）P （7）补余率 P P T , P P F （8）连词化归率 PQ P V Q , P Q (PQ) (QP) （9）量词转换率 (彐x）P（ x）（ P）， （ x）P（彐x）( P） （1O）量词分配率 （ x）（PQ）（ x）P（ x）Q （彐x ）（PQ）（彐x ）P（彐x ）Q582. 永真蕴含式谓词公式的永真蕴含式可

45、定义如下： 定义：对谓词公式P和Q，如果PQ永真，则称P永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提，记作P=Q。 等价式和永真蕴含式是进行演绎推理的重要依据，因此这些公式也被称为推理规则。常用的永真蕴含式如下： 59 （1）化简式 PQ = P， PQ=Q （2）附加式 P=PQ， Q=PQ （3）析取三段论 P，P V Q = Q （4）假言推理 P，PQ = Q （5）拒取式 Q，P Q = P （6）假言三段论 P Q，Q R = P R （7）二难推理 P Q，P R，Q R = R （8）全称固化 （ x）P（x） = P（y） 其中，y是个体域中的任一个体，利用此永真蕴含式可消

46、去谓词公式中的全程量词。 （9）存在固化 （彐x）P（x） = P（y） 其中，y是个体域中某一个可以使P（y）为真的个体，利用此永真蕴含式可消去谓词公式中的存在量词。 60 四谓词公式的范式 范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。在谓词逻辑中，根据量词在公式中出现的情况可将谓词公式的范式分为两种。611前束范式 定义：设F为谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，而它们的辖域为整个公式，则称F为前束范式。一般地，前束范式可写成: （Q1x1）（Qnxn）M(x1,x2,xn)其中，Qi（i=1，2，n）为前缀，它是一个由全称量词或

47、存在量词组成的量词串； M(x1,x2,xn)为母式，它是一个不含任何量词的谓词公式。 例如，（ x）( y）(彐z）(P(x) Q(y,z)R(x,z)）是前束范式。 任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集的化简中讨论。622Skolem范式 定义：如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为Skolem范式。 例如，（彐x）（彐z）（ y）（P(x) Q(y，z) R(x，z)是Skolem范式。 任一谓词公式均可化为与其对应的Skolem范式，其化简方法也将在后面子句集的化简中讨论。63五置换与合一 在不同谓词公式中，往往会出现谓词名相

48、同但其个体不同的情况，此时推理过程是不能直接进行匹配的，需要先进行置换。例如，可根据全称固化推理和假言推理由谓词公式 W1(A)和（ x）(W1(x) W2(x) 推出W2(A) 。可以看出，要使用假言推理，首先需要找到项A对变元x的置换，使W1(A) 与W1(x) 一致。这种寻找项对变元的置换，使谓词一致的过程叫做合一的过程。下面讨论置换与合一的有关概念与方法。641置换（Substitution） 置换可以简单的理解为是在一个谓词公式中用置换项去替换变量。其形式定义如下定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，t1,t2,tn是项；x1,x2,xn是互不相同的变元

49、；ti/xi表示用ti置换xi。并且要求ti与xi不能相同，xi不能循环地出现在另一个ti中。65例如: ax，cy，f(b)z是一个置换。 但是g(y)/x,f(x)/y不是一个置换，原因是它在x与y之间出现了循环置换现象。置换的目的是要将某些变元用另外的变元、常量或函数取代，使其不在公式中出现。但在g(y)/x,f(x)/y中，它用g(y)置换x，用f(g(y)置换y，并没有消去y。若改为g(a)/x,f(x)/y就可以了。它将把公式中的x用g(a)来置换，y用f(g(a) 来置换，从而消去了x和y. 通常，置换是用希腊字母、等来表示的。66定义：设=t1/x1,t2/x2,tn/xn 是

50、一个置换，F是一个谓词公式，把公式F中出现的所有xi换成ti(i=1，2，n），得到一个新的公式G，称G为F在置换下的例示，记作G=F 。 一个谓词公式的任何例示都是该公式的逻辑结论。定义：设 =t1/x1,t2/x2,tn/xn , =u1/y1,u2/y2,um/ym 是两个置换。则 与 的合成也是一个置换，记作 它是从集合 t1 /x1,t2 /x2,tn /xn,u1/y1,u2/y2,um/ym中删去以下两种元素 当ti= xi 时，删去ti / xi （i=1，2，n）； 当 yix1,x2,xn时，删去 uiyi（i=1,2,m）。最后剩下的元素所构成的集合。67例：设=f(y)

51、/x,z/y, =a/x,b/y,y/z求与的合成。 解：先求出集合 f(b/y)/x,(y/z)/y,a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,y/z 其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。在该集合中，y/y满足定义中的条件，需要删除；a/x和b/y满足定义中的条件，也需要删除。 最后得 =f(b)/x,y/z682合一（Unifier） 合一可以简单地理解为是寻找项对变量的置换，使两个谓词公式一致。其形式定义如下:定义：设有公式集F=F1,F2,.,Fn ,若存在一个置换，可使F1= F2= F3= Fn 。则称

52、是F的一个合一。称F1,F2,.,Fn是可合一的。 一般来说一个公式集的合一不是唯一的。69定义：设是公式集 F的一个合一, 如果对F的任一个合一都存在一个置换，可使= , 则称是一个最一般合一(Most General Unifier.简记MGU)。 一个公式集的最一般合一是唯一的。如果用最一般合一去置换可合一的谓词公式,可使它们变成完全一致的谓词公式、现在的问题是如何求取最一般合一，为此，下面讨论求取最一 般合一的合一算法。 703合一算法 在讨论合一算法之前，先引入分歧集的概念。 定义：设 F=F1,F2,.,Fn是一个非空有限的公式集,从F中每个公式的第一个符号同时向右比较,直到发现第

53、一个不相同的符号为止, 从F的每个公式中取出以第一个不相同符号开始的最大子表达式,并组成一个集合D, 则D称为F的分歧集（Disagreement Set)。71例：求 F=P（x,y,z）， P（x,f(a), h(b)）的分歧集 解: 这里F1=P（x，y，z），F2=P（x,f(a), h（b ） ），分别从FI和F2的第一个符号开始，逐 个向后比较会发现F1中的y与F2中的f（a）不同，它们构成了一个分歧集： D1=y,f(a) 再继续向后比较，又会发现F1中的z与F2中的h(b)不同，它们又构成了一个分歧集： D2=z,h(b)72 (1) 令k=0,Fk=F, k=(空置换) ；

54、(2) 若Fk只含有一个表达式，则算法停止, k 就是最一般合一; (3) 找出Fk的分歧集DK； (4) 若DK中存在元素xk和tk,xk是变元,tk是项,同时xk不在tk中出现,则置 k+1= k tk/xk, Fk+1=Fktk/xk, k=k+1然后转（2）； （5）算法停止，F的最一般合一不存在。 有了分歧集的概念，就可以讨论合一算法了。设F为非空有限集合，求F的最一般合一的合一算法如下：73例：例： 求公式集求公式集F= P(a,x,f(g(y) F= P(a,x,f(g(y) ，P(z,h(a,u),f(u) P(z,h(a,u),f(u) 的最一般合一的最一般合一. .解解:

55、根据合一算法根据合一算法,首先置首先置 k=0 ; F0=F ; 0= F0不是单一表达式不是单一表达式,有有D0=a,z. 其中其中z为变元为变元,并且并且z不在不在a中出现中出现,从而从而 1= 0 a/z F1 = F0(a/z)= P(a,x,f(g(y) P(a,x,f(g(y) ，P(a,h(a,u),f(u) P(a,h(a,u),f(u) k=1: F1不是单一表达式不是单一表达式, D1=x,h(a,u). 其中其中x为变元为变元,从而从而 2= 1 h(a,u)/x =a/z, h(a,u)/x F2 = F1(h(a,u)/x)= P(a,h(a,u),f(g(y) P(

56、a,h(a,u),f(g(y) ，P(a,h(a,u),f(u) P(a,h(a,u),f(u) k=2: F2不是单一表达式不是单一表达式, D2=g(y),u. 其中其中u为变元为变元,从而从而 3= 2 g(y)/u =a/z, h(a,g(y)/x, g(y)/u F3 = F2(g(y)/u)= P(a,h(a,g(y),f(g(y) P(a,h(a,g(y),f(g(y) ，P(a,h(a,g(y),f(g(y) P(a,h(a,g(y),f(g(y) = P(a,h(a,g(y),f(g(y) = P(a,h(a,g(y),f(g(y) k=3: F3已是单一表达式已是单一表达式

57、, 从而从而 3= a/z, h(a,g(y)/x, g(y)/u是是F的最一般合一的最一般合一.743. 自然演绎推理75 从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 在这种推理中，最基本的推理规则是三段论推理，它包括假言推理、拒取式推理、假言三段论等。76 在自然演绎推理中，需要避免两类错误：肯定后件的错误和否定前件的错误。 所谓肯定后件的错误是指当PQ为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。原因是当PQ及Q为真时，前件P既可能为真，也可能为假。 所谓否定前件的错误是指当PQ为真时，希望通过否定前件P来推出后件Q为假，这也是

58、不允许的。原因是当PQ及P为假时，后件Q既可能为真，也可能为假。77天下雨天下雨 地湿地湿肯定后件肯定后件: 地湿地湿 下雨下雨? ?否定前件否定前件:天不下雨天不下雨 地不湿地不湿? ?78 例：设已知如下事实： A，B，AC，BC D，DQ 求证：Q为真。 证明：因为A，AC=C 假言推理 B，C=BC 引入合取词 B C， B CD=D 假言推理 D，DQ=Q 假言推理 所以Q为真。79 例：设已知如下事实： （1）只要是需要编程序的课，王程都喜欢。 （2）所有的程序设计语言课都是需要编程序的课。 （3） C是一门程序设计语言课。 求证：王程喜欢C这门课。 证明：首先定义谓词 Prog(

59、x) x是需要编程序的课。 Like(x,y) x喜欢y。 Lang(x) x是一门程序设计语言课。 把上述已知事实及待求解问题用谓词公式表示如下： Prog（x）Like（Wang， x） （ x）（Lang（x）Prog(x) ) Lang（C） 应用推理规则进行推理： Lang（y）Prog（y） 全称固化 Lang（C），Lang（y）Prog（y）=Prog（C） 假言推理 Prog（C），Prog（x）Like（Wang，x）=Like（Wang，C）假言推理. 因此，王程喜欢C这门课。80 一般来说，自然演绎推理由已知事实推出的结论可能有多个，只要其中包含了需要证明的结论，就认为

60、问题得到了解。 自然演绎推理的优点是定理证明过程自然，易于理解，并且有丰富的推理规则可用。 主要缺点是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。81一. 子句集及其化简二. 海伯伦理论三. 鲁宾逊归结原理四. 归结演绎推理的归结策略五. 用归结反演求取问题的答案4.归结演绎推理82 归结演绎推理是一种基于鲁宾逊（Robinson）归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。 在人工智能中，很多问题可以转化为定理证明问题。而定理证明的实质