人工智能之确定性推理(-)课件

第三章确定性推理3.1基本概念3.3自然演绎推理3.4归结演绎推理3.5基于规则的演绎推理（与/或形演绎推理）第三章确定性推理3.1基本概念13.1基本概念为使计算机具有智能，仅仅使它拥有知识还不够，更重要地，还必须使它具有思维能力，即能运用知识进行推理、求解问题的能力。知识表示（知识库）→求解过程（推理）经典推理是根据经典逻辑（命题逻辑和一阶谓词逻辑）的逻辑规则进行的一种推理，又称机械-自动定理证明。主要推理方法有：自然演绎推理、归结演绎推理、基于规则的演绎推理（与/或形演绎推理）。3.1基本概念为使计算机具有智能，仅仅使它拥有知识还不够，2基本概念推理推理是按某种策略由已知判断推出另一种判断的过程。在AI系统中，推理是由程序来实现的，称为推理机。不同的控制策略

推理方式及分类：基本概念推理3演绎推理由一般（全称判断）到个别（特称判断）的推理方法。核心是三段论，通常由一个大前提、一个小前提和一个结论三部分组成的。例：阿凡提的故事---两头驴的故事

①我肩上驮的是两头驴的东西（大前提） ②国王和大臣的衣衫是我肩上驮的（小前提）

③国王和大臣的衣衫是两头驴的东西（结论）演绎推理由一般（全称判断）到个别（特称判断）的推理方法。4归纳推理从个别到一般归纳结论不具备逻辑必然性莫里斯·科恩

逻辑学著作包括两部分，第一部分是演绎，其功能是解释谬误；第二部分是归纳，其功能是生成谬误我们获得关于这个实在世界的一般性事实的唯一方法！归纳推理从个别到一般我们获得关于这个实在世界的5演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。在归纳推理中，所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过6默认推理默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，也称为缺省推理。在推理过程中，如果发现原先的假设不正确，就撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。由于默认推理允许在推理过程中假设某些条件是成立的，因此解决了在一个不完备的知识集中进行推理的问题。封闭世界假设：如果没有足够的证据证明某命题不成立，就假定该命题成立默认推理默认推理是在知识不完全的情况下假设某些条件已经具备所7人工智能之确定性推理(-)课件8推理的控制策略推理过程涉及到求解方法和求解策略。求解方法包括匹配方法、不确定性的传递方法求解策略包括推理方向、求解策略、限制策略等。指推理是求一个解、所有解，还是最优解。为防止无穷的推理过程，以及由此带来的时间和空间复杂性，限制策略是对推理的深度、宽度、时间、空间等进行限制。推理的控制策略指推理是求一个解、所有解，还是最优解。为防止无9推理方向推理方向分为正向推理、逆向推理、混合推理、双向推理四种。无论哪一种推理，系统都具有知识库、数据库和推理机。正向推理需要解决的问题：1、确定匹配的方法2、确定搜索策略3、消解冲突正向推理的缺点：盲目，效率低逆向推理的优点：1、目标性强2、有利于向用户提供解释逆向推理的缺点：初始目标的选择有盲目性

开始提出假设该假设在数据库中？该假设是证据？在知识库中找出所有能导出该假设的知识，形成适用知识集KS从KS中选出一条知识，并将该知识的每一个运用条件都作为新的假设目标退出有此事实？询问用户NNNYYY逆向推理该假设成立该假设成立，并将此事实存入数据库还有假设？NYY开始把初始已知事实送入DBDB中包含问题的解KB中有可适用的知识把KB中所有的适用知识都选出送入KSKS空？按冲突消解策略从KS中选出一条知识进行推理推出的是新知识？将该新知识加入DB成功，退出失败，退出用户补充新知识？把用户提供的新事实加入DBNNNYYYY正向推理NYN推理方向正向推理需要解决的问题：逆向推理的优点：开始10逆向推理-例有关知识 规则1：IF你丢了自行车钥匙，并且车胎没气THEN自行车不能骑

规则2：IF自行车不能骑，并且你只有走路去THEN你听课会迟到

事实1：你丢了自行车钥匙

事实2：车胎没气问题

“你听课会迟到？”

逆向推理-例有关知识11逆向推理-例1.首先查找知识库，知该假设不是已有事实，但可由规则2导出，于是将规则2放入可用知识集，并将其两个前提条件“自行车不能骑”和“你只有走路去”都作为新的假设放入假设集。2.从假设集中取出假设“自行车不能骑”，它不是已有事实，但可由规则1导出，于是规则1被放入可用知识集，并将其两个前提条件“你丢了自行车钥匙”和“车胎没气”也作为新的假设放入假设集。3.从假设集中取出假设“你只有走路去”，此假设既不是已有事实，也不能被任何一条规则导出，询问用户“你只有走路去吗？”，若用户回答“是”，则该假设成立，并被放入已有事实集。4.假设集中还有两个假设“你丢了自行车钥匙”和“车胎没气”，它们都是已有事实，均为真。继续推理，假设集为空，推理过程结束，“你听课会迟到”得证。逆向推理-例1.首先查找知识库，知该假设不是已有事实，但可由12混合推理是把正向推理和逆向推理结合起来，吸取两种推理的优点。它通常适用以下3种情况：（1）已知事实不充分（2）由正向推理推出的可信度不高（3）希望得到更多的结论混合推理有两种方式：先正后逆和先逆后正双向推理是指正向推理和逆向推理同时进行，在推理过程的某步碰头。基本思想双向推理的难点是碰头的判定。开始进行正向推理需要逆向推理？以正向推理所得的结果作为假设进行逆向推理还需要正向推理？输出结果开始YYNN先正后逆开始进行逆向推理需要正向推理？进行正向推理还需要逆向推理？输出结果开始YYNN先逆后正混合推理是把正向推理和逆向推理结合起来，吸取两种推理的优点。13模式匹配模式匹配是指对两个知识模式（如两个谓词公式、框架或语义片段等）的比较与藕合，即检查这两个知识模式是否完全一致或近似一致。按匹配的近似程度划分，可分为确定性匹配和不确定性匹配。确定性匹配是指两个知识模式完全一致，或经过变量代换后变得完全一致。例如：

不确定性匹配是指两个知识模式不完全一致，但总体上它们的相似度在一定的限度内。模式匹配模式匹配是指对两个知识模式（如两个谓词公式、框架或语14定义3.1置换（代换）

代换是形如的有限集合。其中是项是互不相同的变元；表示用代换，不允许与相同，也不允许变元循环地出现在另一个中。根据定义是代换不是代换是代换定义3.1置换（代换）代换是形如15设有代换θ＝{a/x,f(b)/y,u/z}则对公式E＝P(x,y,z)有Eθ＝P(a,f(b),u)对公式E运用代换s，记作Es。Es称作公式E在代换s下的例（例示），它是E的逻辑结论。设有代换θ＝{a/x,f(b)/y,u/z}对公式E运用16设是两个代换，则此两个代换的复合也是一个代换，它是从删除以下两种元素后剩下的元素所构成的集合，记作定义3.2代换的复合例如：则解释：定义3.2代换的复合例如：解释：17就是对一个公式先运用θ代换，然后再运用λ代换.大家验证一下！就是对一个公式先运用θ代换，然后再运用λ代换.大家验证一下！18定义3.3公式集的合一设有公式集，若存在一个代换使得则称是公式集的一个合一，且称是可合一的。一个公式集的合一一般来说不是唯一的例如公式集有合一定义3.3公式集的合一一个公式集的合一一般来说不是唯一的19定义3.4最一般合一设是公式集的一个合一，如果对任一个合一都存在一个代换，使得则称是公式集的一个最一般合一。定义3.4最一般合一20如前面提到的公式集是最一般合一，而则不是最一般合一。按照最一般合一的定义，有：因此，对于一个公式集来说，如果存在多个合一，则其中代换数最少、限制最少、产生的例最具一般性的代换称为最一般合一。如：一般来说，最一般合一也不是唯一的，同样是该公式集的一个最一般合一。如前面提到的公式集因此，对于一个公式集来说，如果存在多个合一21求最一般合一差异集：求最一般合一22求最一般合一算法：（1）令。这里，是欲求最一般合一的公式集，是空代换，它表示不做代换。（2）若只含一个表达式，则算法停止，就是最一般合一。（3）找出的差异集。（4）若中存在元素和，其中是变元，是项，且不在中出现，则置：然后转向（2）。（5）算法终止，的最一般合一不存在。求最一般合一算法：23举例：求的最一般合一。举例：求24消解冲突策略在推理过程中，系统要不断地用当前已知事实与知识库中的知识进行匹配，此时可能发生以下三种情况：（1）已知事实不能与知识库中的任何知识匹配（2）已知事实恰好与知识库中的一条知识匹配（3）已知事实可与知识库中的多条知识匹配，或者多组已知事实可与知识库中的某一条知识匹配，或者多组已知事实可与知识库中的多条知识匹配。处于第三种情况时，就发生冲突。此时需要按一定的消解策略解决冲突。冲突：多个知识都匹配成功。冲突消解的基本思想都是对知识进行排序。消解冲突策略在推理过程中，系统要不断地用当前已知事实与25对于产生式系统，若出现以下情况就认为发生冲突：（1）对正向推理而言，如果有多条产生式规则的前件都和已知事实匹配，或者有多组已知事实都与同一条产生式规则的前件匹配；或者以上两种情况同时出现。（2）对逆向推理而言，如果有多条产生式规则的后件都和同一假设匹配，或者有多条产生式规则的后件可与多个假设匹配。对于产生式系统，若出现以下情况就认为发生冲突：26常用的消解冲突策略：1、按针对性排序设有如下两条产生式规则：如果存在最一般合一，使得r1中的每个Ai都可以变成相应的Bi，如Ai=P(x,y)，Bi=P(a,z)则称r2比r1有更大的针对性，r1比r2有更大的通用性。该策略选用针对性较强的产生式规则。常用的消解冲突策略：如果存在最一般合一，使得r1中的每个Ai272、按已知事实的新鲜性排序把数据库中后生成的事实称为新鲜的事实，该策略要求具有最大新鲜性的事实总是排在前面。设规则r1可与事实组A匹配成功，规则r2可与事实组B匹配成功，则A和B哪一组中的事实更新鲜，与它匹配的规则就先被利用。如何衡量A和B哪一组中的事实更新鲜呢？2、按已知事实的新鲜性排序283、按匹配度排序4、根据领域问题的特点排序

先验知识、启发式知识5、按上下文限制排序

把规则按照下上文分组，并只能选取组中的规则。6、按冗余限制排序

冗余知识少的规则先推。7、按条件个数排序

条件少的规则先推。

——尽量减少冲突的发生，使推理具有较高的效率3、按匹配度排序293.3自然演绎推理自然演绎推理就是从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程。推理规则包括：1、假言推理2、拒取式推理3、P规则：在推理的任何步骤都可引入前提4、T规则：推理时，如果前面步骤有一个或多个公式永真蕴含公式S（逻辑结论），则可把公式S引入推理过程中。3.3自然演绎推理自然演绎推理就是从一组已知为真的事实出发30例3.1已知下述事实：A，B，A→C，B∧C→D，D→Q求证：Q为真证明：∵A，A→CCP规则及假言推理B，CB∧C合取

B∧C，B∧C→DDT规则及假言推理D，D→QQT规则及假言推理思考题： 所有人都是必死的； 苏格拉底是人； 求证：苏格拉底是必死的。例3.1已知下述事实：证明：∵A，A→C31自然演绎推理的优点：表达定理证明过程自然，容易理解，而且拥有丰富的推理规则，推理过程灵活，便于在它的推理规则中嵌入领域启发式知识。自然演绎推理的缺点：容易产生组合爆炸——中间结论呈指数级增长。自然演绎推理的优点：323.4归结演绎推理要证明P→Q永真，需要证明它在任何个体域上所有可能的解释都是永真的，这是难以实现的。采用反证法的思想，只要证明P∧～Q永假（不可满足）即可。这是因为：P→Q

～P∨Q～（～P∨Q）P∧～Q海伯伦（Herbrand）和鲁宾逊（Robinson）在这个方向上先后作了卓越的研究工作。首先，由海伯伦提出的H域（海伯伦域）和海伯伦定理，为自动定理证明奠定了理论基础；然后，由鲁宾逊提出的归结原理（消解原理）则使机器定理证明成为可能。3.4归结演绎推理要证明P→Q永真，需要证明它33子句：

在谓词公式中，把原子谓词公式及其否定统称为文字。例如：P(x,y)和Q(x)都是文字。定义任何文字的析取式称为子句。例如：P(x,y)∨Q(x)是子句；

P(x,y)∨(Q(x)∧R(y))不是子句。定义不包含任何文字的子句称为空子句，简记为NIL。空子句是永假的，是不可满足的。子句的集合称为子句集。在谓词逻辑中，谓词公式可以通过等价关系及推理规则化成相应的子句集。子句：定义任何文字的析取式称为子句。定义不包含任34把谓词公式转化为子句集的步骤：(1)消去蕴涵符号(2)内移否定符号(3)对变元更名：使不同量词约束的变元不同名(4)消去存在量词：个体常量、Skolem函数代换(5)全称量词前束化(6)化为Skolem标准型：合取范式(7)消去全称量词(8)对变元更名：使不同子句中的变元不同名(9)消去合取词：子句集例如：("x)(("y)P(x,y)→("y)(Q(x,y)→R(x,y)))("x)(("y)P(x,y)∨("y)(Q(x,y)∨R(x,y)))(2)("x)((y)P(x,y)∨(y)(Q(x,y)∧R(x,y)))(3)("x)((y)P(x,y)∨(z)(Q(x,z)∧R(x,z)))(4)("x)(P(x,f(x))∨(Q(x,g(x))∧R(x,g(x))))(5)全称量词已经前束化(6)("x)((P(x,f(x))∨Q(x,g(x)))∧(P(x,f(x))∨R(x,g(x))))(7)(P(x,f(x))∨Q(x,g(x)))∧(P(x,f(x))∨

R(x,g(x)))(8)(P(x,f(x))∨(Q(x,g(x)))∧(P(y,f(y))∨

R(y,g(y)))(9){P(x,f(x))∨Q(x,g(x)),P(y,f(y))∨

R(y,g(y))}把谓词公式转化为子句集的步骤：(1)消去蕴涵符号例如：("35例1：求谓词公式G=

x

y

z((P(x,y)∨R(x,y,z))∧(Q(x,z)∨R(x,y,z)))的子句集。解：已经是前束范式，并且不含连接词。由于存在量词y,z都在全称量词x的辖域中，所以将y,z分别用Skolem函数f(x)、g(x)代替。

x((P(x,f(x))∨R(x,f(x),g(x)))∧(Q(x,g(x))∨R(x,f(x),g(x))))该谓词公式已经是合取范式了，消去全称量词、对变元更名、消去合取词，得到谓词公式G的子句集是｛P(x,f(x))∨R(x,f(x),g(x))，Q(y,g(y))∨R(y,f(y),g(y))｝例1：求谓词公式G=

x

y

z((P(x36例2：求谓词公式的子句集:

x(

yP(x,y)→

y(Q(x,y)→R(x,y)))解：

x(

yP(x,y)→y(Q(x,y)→R(x,y)))==>

x(

yP(x,y)→

y(Q(x,y)∧R(x,y)))==>

x(yP(x,y)∨

y(Q(x,y)∧R(x,y)))==>

x(

yP(x,y)∨

z(Q(x,z)∧R(x,z)))==>

x(P(x,f(x))∨(Q(x,g(x))∧R(x,g(x))))==>

x((P(x,f(x))∨Q(x,g(x)))∧(P(x,f(x))∨R(x,g(x))))从而该谓词公式的子句集是｛P(x,f(x))∨(Q(x,g(x)，P(y,f(y))∨R(y,g(y))｝转化要点：1、第一步应先消去蕴涵符号，再内移否定符号等其它工作；2、先内移否定符号，再消去量词；3、先消存在量词，再消全称量词。例2：求谓词公式的子句集:

x(

yP(x,y)→37定理3.1设有谓词公式F，其标准形的子句集为S，则F不可满足的充要条件是S不可满足。（注意：F和S并不等价！——存在量词消去、变元更名）因此，要想证明F不可满足，只需证明S不可满足即可，鲁滨逊提出的归结原理就是用来解决这一问题的。鲁宾逊归结原理为提高判定子句集不可满足的有效性，鲁宾逊于1965年提出了归结(Resolution)原理，也称为消解原理。由谓词转化子句集的过程可以看出，在子句集中各子句之间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。空子句是不可满足的，若一个子句集含有一个空子句（该子句集中有矛盾），子句集一定是不可满足的。鲁宾逊归结原理的基本是：检查子句集S是否包含空子句，若包含，则S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结推出空子句，就说明子句集S是不可满足的。定理3.1设有谓词公式F，其标准形的子句集为S，则F不可38定义3.18若P是原子谓词公式，则称P和P为互补文字。命题逻辑中归结原理设C1和C2是子句集中任意二个子句，如果C1中的文字L1和C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并对C1和C2的剩余部分析取，构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，C1和C2是C12的亲本子句。例：C1=P∨Q，C2=Q∨R，C3=PC12=P∨R，C123=RP∨QQ∨RP∨RPR归结树定义3.18若P是原子谓词公式，则称P和P为互补文字。39定理3.2归结式C12是其亲本子句C1和C2的逻辑结论，即：C1∧C2C12如何证明？推论1：设C1和C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2后得到新子句集S1，则

S1的不可满足性S的不可满足性推论2：设C1和C2是子句集S中的两个子句，C12是它们的归结式，若用C12加入S中后，得到新子句集S1，则

S1的不可满足性S的不可满足性定理3.2归结式C12是其亲本子句C1和C2的逻辑结论，40谓词逻辑中的归结原理在谓词逻辑情况下，由于子句中含有变量，不能像命题逻辑那样直接发现和消去互补文字，往往需对潜在的互补文字先作变量代换和合一处理，才能用于归结。例如有如下两个子句：C1=P(x)∨Q(x)C2=P(a)∨R(y)用最一般合一

={a/x}对两个子句分别进行代换：C1=P(a)∨Q(a)C2=P(a)∨R(y)可得归结式：Q(a)∨R(y)若C2=P(a)∨R(x)又该如何？谓词逻辑中的归结原理41定义3.20设C1和C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若是L1和L2的最一般合一，则称C12=(C1-{L1})∪(C2-{L2})是C1和C2的二元归结式，L1和L2称为归结式上的文字。如果在参加归结的子句内部含有可合一的文字，则在进行归结前应对这些文字先进行合一。例如：C1=P(x)∨P(f(a))∨Q(x)C2=P(y)∨R(b)C1中P(x)和P(f(a))可合一，用其最一般合一={f(a)/x}进行代换，得：C1=P(f(a))∨Q(f(a))C1和C2归结得C12=Q(f(a))∨R(b)注意：这样多做了一次代换，相当于对C1做了更严格的限制，有可能存在归结不出结果的可能性。一般来说：若子句C中有两个或两个以上的文字具有最一般的合一，则称C为子句C的因子。如果C是一个单文字，则称为单因子。定义3.20设C1和C2是两个没有相同变元42定义3.21子句C1和C2的归结式是下列二元归结式之一：（1）C1和C2的二元归结式；（2）C1和C2的因子C22的二元归结式；（3）C1的因子C11和C2的二元归结式；（4）C1的因子C11和C2的因子C22的二元归结式。对于谓词逻辑，定理3.2仍然适用。定义3.21子句C1和C2的归结式是下列二元归结式之一：43归结演绎的完备性

从不可满足的意义上说，基于归结的演绎方法是完备的，即若子句集S不可满足，就必定存在一个从S到空子句的归结演绎；反之，若存在一个从S到空子句的归结演绎，则S必定是不可满足的。关于归结演绎的完备性可用海伯伦定理进行证明，因此从这个意义上讲，归结原理是建立在海伯伦定理之上的。不过归结原理并不能用于解决子句集不可满足性的不可判定问题，即对于永真和可满足的子句集，判定过程将无休止地进行下去，得不到任何结果。归结演绎的完备性

从不可满足的意义上说，基于归结的演绎方44归结反演证明Q是P1，P2Pn的逻辑结论，即：P1∧P2∧∧Pn→Q只需证明(P1∧P2∧∧Pn→Q)是不可满足的。因为(P1∧P2∧∧Pn→Q)((P1∧P2∧∧Pn)∨Q)(P1∧P2∧∧Pn)∧

Q只需证明子句集{P1，P2，，Pn，Q}是不可满足的。对子句集中的子句相互归结，直到归结出空子句，这个过程就是归结反演。归结反演45设F为已知前提的公式集，Q为目标公式，用归结反演证明Q为真的步骤：（1）否定Q，得到Q；（2）把Q并入到公式集F中，得到{F，Q}；（3）把公式集{F，Q}化为子句集S（P126~127）；（4）应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式放入S中。如此反复，若出现空子句，就停止归结，此时就证明了Q为真。设F为已知前提的公式集，Q为目标公式，用归结反演证明Q为真的46例1:求证:G是A1和A2的逻辑结论A1:x(P(x)→(Q(x)∧R(x)))A2:x(P(x)∧S(x))G:x(S(x)∧R(x))证:①～P(x)∨Q(x)...从A1变换②～P(y)∨R(y)...从A1变换③P(a))...从A2变换④S(a))...从A2变换⑤～S(z)∨～R(z)...结论的否定⑥R(a)......②③归结｛a/y｝⑦～R(a)......④⑤归结｛a/z｝⑧NIL......⑥⑦归结得证.例1:求证:G是A1和A2的逻辑结论47

例2:设已知:(1)能阅读者是识字的;(2)海豚不识字;(3)有些海豚是聪明的;求证:有些聪明者并不能阅读.

证:定义如下命题:R(x):x能阅读;L(x):x识字;I(x):x是聪明的;D(x):x是海豚;把已知条件及求证结论翻译成谓词公式为x(R(x)→L(x))...已知x(D(x)→～L(x))...已知x(D(x)∧I(x))...已知x(I(x)∧～R(x))...求证结论将已知条件,求证结论的反化成子句集①～R(x)∨L(x)②～D(y)∨～L(y)③D(a)④I(a)⑤～I(z)∨R(z)⑥～L(a)......2,3归结｛a/y｝⑦～R(a)......1,6归结｛a/x｝⑧R(a)......4,5归结｛a/z｝⑨NIL......7,8归结得证.例2:设已知:48例3.17“快乐学生”问题假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。解：先定义谓词：Pass(x,y)x可以通过y考试Win(x,prize)x能获得奖励Study(x)x肯学习Happy(x)x是快乐的Lucky(x)x是幸运的例3.17“快乐学生”问题49再将问题用谓词表示如下：“任何通过计算机考试并奖的人都是快乐的”(∀x)(Pass(x,computer)∧Win(x,prize)→Happy(x))“任何肯学习或幸运的人都可以通过所有考试”(∀x)(∀y)(Study(x)∨Lucky(x)→Pass(x,y))“张不肯学习但他是幸运的”﹁Study(zhang)∧Lucky(zhang)“任何幸运的人都能获奖”(∀x)(Lucky(x)→Win(x,prize))结论“张是快乐的”的否定﹁Happy(zhang)再将问题用谓词表示如下：50将上述谓词公式转化为子句集如下：(1)﹁Pass(x,computer)∨﹁Win(x,prize)∨Happy(x)(2)﹁Study(y)∨Pass(y,z)(3)﹁Lucky(u)∨Pass(u,v)(4)﹁Study(zhang)(5)Lucky(zhang)(6)﹁Lucky(w)∨Win(w,prize)(7)﹁Happy(zhang)(结论的否定)将上述谓词公式转化为子句集如下：51

﹁Pass(x,computer)∨﹁Win(x,prize)∨Happy(x)﹁Lucky(w)∨Win(w,prize)﹁Pass(w,Computer)∨Happy(w)∨﹁Lucky(w)﹁Happy(zhang)Lucky(zhang)﹁Pass(zhang,Computer)∨﹁Lucky(zhang)﹁Pass(zhang,Computer)﹁Lucky(u)∨Pass(u,v)﹁Lucky(zhang)Lucky(zhang)NIL{w/x}{zhang/w}{zhang/u,computer/v}﹁Pass(x,computer)∨﹁Win(x,pr52

例3.18“激动人心的生活”问题假设：所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李明能看书且不贫穷，快乐的人过着激动人心的生活。求证：李明过着激动人心的生活。解：先定义谓词：Poor(x)x是贫穷的Smart(x)x是聪明的Happy(x)x是快乐的Read(x)x能看书Exciting(x)x过着激动人心的生活例3.18“激动人心的生活”问题53再将问题用谓词表示如下：“所有不贫穷并且聪明的人都是快乐的”(∀x)((﹁Poor(x)∧Smart(x))→Happy(x))“那些看书的人是聪明的”(∀y)(Read(y)→Smart(y))“李明能看书且不贫穷”Read(Liming)∧﹁Poor(Liming)“快乐的人过着激动人心的生活”(∀z)(Happy(z)→Exciting(z))目标“李明过着激动人心的生活”的否定﹁Exciting(Liming)再将问题用谓词表示如下：54将上述谓词公式转化为子句集如下：(1)Poor(x)∨﹁Smart(x)∨Happy(x)(2)﹁Read(y)∨Smart(y)(3)Read(Liming)(4)﹁Poor(Liming)(5)﹁Happy(z)∨Exciting(z)(6)﹁Exciting(Liming)(结论的否定)将上述谓词公式转化为子句集如下：55

﹁Exciting(Liming)﹁Happy(z)∨Exciting(z)﹁Happy(Liming)Happy(x))∨﹁Smart(x)∨Happy(x)Poor(Liming)∨﹁Smart(Liming)﹁Read(y)∨Smart(y)Poor(Liming)∨﹁Read(Liming)﹁Poor(Liming)﹁Read(Liming)Read(Liming)NIL{Liming/z}{Liming/x}{Liming/y}﹁Exciting(Liming)﹁Happy(z)∨Ex56应用归结原理求问题的答案求问题的答案与定理证明类似，其步骤为：（1）用谓词公式表示已知前提，并化为子句集S；（2）用谓词公式表示待求解，并将其否定与谓词ANSWER构成析取式（同一个子句）；ANSWER是一个为求解而设定的谓词，其变元必须与问题公式的变元一致；（用重言式也可）（3）把此析取式化为子句集，并把该子句集假如到子句集S中，得到子句集S’；（4）对S’应用归结原理进行归结；（5）若得到归结式ANSWER，则答案就在ANSWER中。应用归结原理求问题的答案求问题的答案与定理证明类似，其步骤为57例设A,B,C三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者？解：设用T(x)表示x说真话。如果A说的是真话，则T(A)→¬T(B)∧¬T(C)如果A说的是假话，则¬T(A)→T(B)∨T(C)对B和C说的话作相同处理，可得：T(B)→¬T(A)∧¬T(C)¬T(B)→T(A)∨T(C)T(C)→¬T(A)∨¬T(B)¬T(C)→T(A)∧T(B)例设A,B,C三人中有人从不说真话，也有人从不说假话。某58把上述公式化成子句集，得到S：(1)¬T(A)∨¬T(B)(2)¬T(A)∨¬T(C)(3)T(C)∨T(A)∨T(B)(4)¬T(B)∨¬T(C)(5)¬T(C)∨¬T(A)∨¬T(B)(6)T(A)∨T(C)(7)T(B)∨T(C)下面先求谁是老实人。把¬T(x)∨Answer(x)并入S得到S1。即多一个子句：(8)¬T(x)∨Answer(x)应用归结原理对S1进行归结：(9)¬T(A)∨T(C) (1)和(7)归结(10)T(C) (6)和(9)归结(11)Answer(C) (8)和(10)归结所以C是老实人，即C从不说假话。把上述公式化成子句集，得到S：59下面证A和B不是老实人。设A不是老实人，则有¬T(A)，把它否定并入S中，得到子句集S2，即S2比S多如下子句：(8)¬(¬T(A)),即T(A)应用归结原理对S2进行归结：(9)¬T(A)∨T(C) (1)和(7)归结(10)¬T(A) (2)和(9)归结(11)NIL (8)和(10)归结所以A不是老实人。同理，可证明B也不是老实人。归结时，并不要求把子句集中所有的子句都用到。在归结过程中，一个子句可以多次被用来进行归结。下面证A和B不是老实人。60例3.24已知：“张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。”问：“现在李在哪个教室上课？”解：首先定义谓词：C(x,y)x和y是同班同学；At(x,u)x在u教室上课。把已知前提用谓词公式表示如下：C(zhang,li)(∀x)(∀y)(∀u)(C(x,y)∧At(x,u)→At(y,u))At(zhang,302)把目标的否定用谓词公式表示如下：﹁(∃v)At(li,v)例3.24已知：“张和李是同班同学，如果x和y是同班同学，61把上述公式化为子句集：C(zhang,li)﹁C(x,y)∨﹁At(x,u)∨At(y,u)At(zhang,302)把目标的否定化成子句式，并用重言式﹁At(li,v)∨At(li,v)代替之。把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。其求解过程如下图所示。该证明树的根子句就是所求的答案，即“李明在302教室”。把上述公式化为子句集：62﹁At(li,v)∨At(li,v)﹁C(x,y)∨﹁At(x,u)∨At(y,u)At(li,v)∨﹁

C(x,li)∨﹁At(x,v)C(zhang,li)﹁At(zhang,v)∨At(li,v)At(zhang,302)At(li,302){li/y,v/u}{Zhang/x}{302/v}﹁At(li,v)∨At(li,v)﹁C(x,y)∨﹁At63归结策略1、计算机进行归结的一般过程设子句集S={C1，C2，C3，C4}，计算机对此子句集进行归结的一般过程是：（1）从子句C1开始，逐个与C2，C3，C4进行比较，若能归结，就求出归结式。然后用C2与C3、C4进行归结，最后C3和C4进行归结。经过这一轮的比较和归结后，就得到一组归结式，称为第一级归结式。（2）再从C1开始，用S中的子句分别与第一级归结式中的子句逐个地比较、归结，这样又会得到一组归结式，称为第二级归结式。（3）仍然从C1开始，用S中的子句及第一级归结式中的子句分别与第二级归结式中的子句逐个地比较、归结，得到第三级归结式。如此继续，直到出现空子句或者不能再继续归结为止。归结策略1、计算机进行归结的一般过程64例设有子句集：S={P，R，PQ，QR}归结过程：S:(1)P(2)R(3)PQ(4)QRS1:(5)Q(6)Q(7)PRS2:(8)R(9)P(10)P(11)RS3:(12)NIL事实上，(5)(6)归结就可以得到NIL例设有子句集：S:(1)PS2:(8)R652、归结策略为了尽量避免造成时空浪费，提高归结的效率，需要对归结过程进行适当的控制。归结策略分为两大类：

删除策略：删除某些无用子句，缩小归结的范围

限制策略：对参加归结的子句进行限制，减小归结的 盲目性2、归结策略为了尽量避免造成时空浪费，提高归结的效率662、删除策略删除策略是指在归结过程中把子句集的无用的子句删除掉这样就会缩小寻找范围，减少比较次数。删除策略具有以下几种删除方法：（1）纯文字删除法。如果某文字L在子句集中不存在可与之互补的文字L，则称该文字是纯文字。例如：S={PQR,QR,Q,R}中Ｐ是纯文字．删除纯文字所在的子句PQR（2）重言式删除法。如果一个子句中同时包含互补文字对，则称该子句为重言式。重言式是永真式。例如：P(x)P(x),P(x)Ｑ(x)P(x)2、删除策略删除策略是指在归结过程中把子句集的无用的子句删除67（３）包孕删除法。设子句C1和C2，如果存在一个代换，使得C1C2，则称C1包孕于C2。删除包孕的子句C2，不会影响子句集的不可满足性，因为C2是C1的逻辑蕴涵，即C1→C2，如何证明？例如：P(x)包孕于P(y)Q(z)

={y/x}

P(x)包孕于P(a)

={a/x}

P(x)包孕于P(a)Q(z)

={a/x}

P(a,x)P(y,b)包孕于P(a,b)

={b/x,a/y}2、删除策略（续）如子句集{P(x),P(a),P(b)}（３）包孕删除法。设子句C1和C2，如果存在一个代换，使得68３、支持集策略每一次归结时，亲本子句中至少有一个是由目标公式的否定所得到的子句，或者是他们的后裔。可以证明，支持集策略是完备的。例设有子句集：S={I(x)R(x),I(a),R(y)L(y),L(a)}其中I(x)R(x)是目标公式否定后得到的子句。I(x)R(x)I(a)R(y)L(y)L(a)R(a)NILI(x)L(x)L(a)L(a)I(a)３、支持集策略每一次归结时，亲本子句中至少有一个是由目标公式694、线性输入策略参加归结的两个子句中必须至少有一个是初始子句集的子句。线性输入策略是不完备的。例如S={P(x)Q(x),P(x)Q(x),P(u)Q(u),P(t)Q(t)}是不可满足的，但用线性输入策略却归结不出空子句。﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁I(x)∨L(x)﹁R(a)﹁I(a)L(a)L(a)﹁I(a)NIL4、线性输入策略参加归结的两个子句中必须至少有一个是初始子句705、单文字子句策略如果一个子句只包含一个文字，就称它为单文字子句。该策略要求参加归结的子句至少有一个是单文字子句。该策略也是不完备的。﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁R(a)NIL5、单文字子句策略﹁I(x)∨R(x)I(a716、祖先过滤形策略当两个子句C1和C2进行归结时，只要它们满足下述两个条件中的任一个就可以归结。（1）C1和C2中至少有一个是初始子句集的子句（线性输入）；（2）如果两个子句都不是初始子句集的子句，则一个应是另一个的祖先。祖先过滤形策略是完备的。﹁Q(x)∨﹁P(x)Q(y)∨﹁P(y)﹁P(x)﹁Q(w)∨P(w)﹁Q(w)Q(a)∨P(a)P(a)NIL6、祖先过滤形策略当两个子句C1和C2进行归结72

归结演绎推理具有证明简单，在计算机上容易实现等优点，但同时具有以下缺点：（1）必须把逻辑公式化成子句集。（2）不自然，不便于阅读与理解。如：¬P(x)∨Q(x)没有P(x)→Q(x)直观。（3）有可能丢失一些重要的控制信息。针对以上缺点，与/或形演绎推理可以克服。

通常很多应用知识是用蕴含式直接表达的，因此都带有超逻辑的或启发式的控制信息。在归结反演证明系统中，要把这些表达式化成子句形表示，这就可能丢掉隐含在蕴含式中、对推理有用的控制信息，例如下面的几个蕴含式

~A∧~B→C，~A∧~C→B，~B∧~C→A，~A→B∨C，~B→A∨C，~C→A∨B

其中任意一个式子在逻辑上都与子句（A∨B∨C）等价，而每种形式表达的蕴含式都有其内在含有的各不相同的超逻辑的控制信息，子句形表示只给出了谓词间的逻辑关系。因此有时候会希望系统能按近于原始给定的描述形式来使用这些公式，不把它们都化成子句集，这就是基于规则的演绎系统（强调直接使用规则进行演绎，或称为与/或形演绎推理）的基本思想。

归结演绎推理具有证明简单，在计算机上容易实现等733.5与/或形演绎推理1、与/或形正向演绎推理它是从已知事实出发，正向使用蕴涵式（F规则）进行演绎推理，直到得到某个目标公式的一个终止条件。在这种推理中，对已知事实、F规则及目标公式的表示形式都有一定的要求，如果不是所要求的形式，就需要进行变换。事实为支持演绎推理，事实表达式不必化简为子句集，只需规范地表示为不含蕴涵符号的文字与或形，具体步骤如下：（1）利用P→QPQ消去公式中的“→”；（2）把“”移到紧靠谓词的位置上；（3）重新命名变元名，使不同量词约束的变元有不同的名字；（4）引入Skolem函数消去存在量词；（5）消去全称量词，使主合取式中的变元不同名。3.5与/或形演绎推理1、与/或形正向演绎推理74例如：(x)("y){(Q(y,x)∧[(R(y)P(y))∧S(x,y)]}(x)("y){(Q(y,x)∧

[

(R(y)∧

P(y))

S(x,y)]}

("y){(Q(y,a)∧

[(R(y)∧

P(y))

S(a,y)]}

Q(z,a)∧

[(R(y)∧

P(y))

S(a,y)]Q(z,a)∧

[(R(y)∧

P(y))

S(a,y)]Q(z,a)

(R(y)∧

P(y))

S(a,y)R(y)∧

P(y)S(a,y)R(y)P(y)子句集（解图）：Q(z,a)，R(y)S(a,y)，P(y)S(a,y)例如：(x)("y){(Q(y,x)∧[(R(y)75F规则

在与/或形正向演绎推理中，通常要求F规则具有如下形式：L→W其中，L为单文字，W为与/或形。为了得到这种可应用的形式，对原始蕴含式必须作必要的化简。设原始公式为

(x)(((y)(z)P(x,y,z))→(u)Q(x,u))

则化简步骤如下：

（1）(x)(~((y)(z)P(x,y,z))∨(u)Q(x,u))

（2）(x)(((y)(z)~P(x,y,z))∨(u)Q(x,u))

（3）(x)(((y)~P(x,y,f(x,y)))∨(u)Q(x,u))（4）~P(x,y,f(x,y))∨Q(x,u)

（5）P(x,y,f(x,y))→Q(x,u)

对规则作单文字前项的限制将大大简化了应用时的匹配过程，对非单文字前项的情况，若形式为（L1∨L2）→W，则可化成与其等价的两个规则L1→W与L2→W进行处理。F规则76目标公式的表示形式目标公式用子句（析取式）表示。推理过程（1）首先用与/或树表示已知事实（2）用F规则的左部与与/或树的叶节点匹配，并把匹配成功的F规则加入到与/或树中。（3）重复（2），直到产生一个含有以目标节点作为终止节点的一致解图为止。目标公式的表示形式77例设已知事实为：ABF规则为：r1：A→CDr2：B→EG欲证明的目标公式为：CGABABABCDEGCG已知事实F规则目标解图？（=归结式？）归结演绎推理该如何做？例设已知事实为：ABABABCDEGCG已知事实F规则目78例设已知事实为

((P∨Q)∧R)∨(S∧(T∨U))

规则为

S→(X∧Y)∨Z

解图？（=归结式？）例设已知事实为

((P∨Q)∧R)∨(S∧(T∨U))

规79例事实与或形表示为P(A,y)∨(Q(x,A)∧R(B,y))

规则为P(z,B)→(S(z)∨X(B))

施以规则后的与或图如右图所示。解图？（=归结式？）一个解图是否是一致的，需要看该解图所涉及的若干个代换组成的代换集是否存在矛盾。当代换集没有矛盾存在时，称该代换集是一致的，也就是没有矛盾的，否则就是不一致的。只有当解图所涉及的代换集是一致的时，解图才是一致的。例事实与或形表示为解图？（=归结式？）一个802、与/或形逆向演绎推理与/或形逆向演绎推理从目标公式出发，逆向应用蕴含式（B规则）对相应于目标公式的原始与/或树进行变换，直至得到一个所有叶节点都是事实节点（以事实表达式中的文字作为节点内容的节点）的一致解图为止。逆向演绎推理情况下问题求解的描述也分为三部分：目标公式、B规则和事实，它们的标准化表示形式与正向演绎呈现对偶关系。目标公式——用对偶形的Skolem化目标公式的变换与正向演绎推理中的已知事实变换类似，只是将全称量词的约束变量用存在量词的约束变量的Skolem函数取代，消去全称量词和存在量词。例如：2、与/或形逆向演绎推理与/或形逆向演绎推理从目标公式出发，81（x）（y）{P(x)→[Q(x,y)∧(R(x)→S(x,y))]}

先化简为：

（x）（y）{P(x)∨[Q(x,y)∧(R(x)∨S(x,y))]}

P(x)∨[Q(x,f(x))∧(R(x)∨S(x,f(x)))]再通过换名，使顶层析取式的各析取项不含同名变量：

P(z)∨[(Q(x,f(x))∧(R(x)∨S(x,f(x))))解图？只要其中一个解图得证，该目标公式就可得证。（x）（y）{P(x)→[Q(x,y)∧(R(x)82B规则

逆向演绎推理以逆向方式使用规则（称为B规则），要求规则化简为以下形式：

W→L

其中，L为单文字，W是与或形；有时会出现形如

W→L1∧L2

的情况，可以进一步化简为与其等价的两条规则

W→L1,W→L2事实

在逆向演绎推理中，要求已知事实是文字的合取式，即形如：F1∧F2∧…∧FnB规则

逆向演绎推理以逆向方式使用规则（称为B规则），要83推理过程（1）首先用与/或树表示目标公式（2）用B规则的右部与与/或树的叶节点匹配，并把匹配成功的B规则加入到与/或树中。（3）重复（2），直到产生一个含有以事实节点作为终止节点的一致解图为止。推理过程84

正、逆向演绎推理的特点比较正、逆向演绎推理的特点比较853、双向演绎推理可以把正向和逆向演绎推理结合起来加以应用，建立基于规则的双向演绎推理系统。这种系统可以免除因单向推理而引入的限制，并实现优势互补。然而处理结束条件的复杂性以及需分别支持正、逆向推理，增加了系统设计和知识获取的困难。例设已知事实及目标分别是：

Q(x,a)∧[R(x)∨S(a)]P(f(y))∨{Q(f(y),y)∧[R(f(y))∨S(y)]}3、双向演绎推理可以把正向和逆向演绎推理结合起来加以应用，建864、代换的一致性及剪枝策略代换的一致性定义设代换集合

如果一个解图中所涉及的代换是一致的，则该解图称为一致解图。4、代换的一致性及剪枝策略代换的一致性如果一个解图中87

为避免在匹配过程中产生一些不必要的约束，从而将原本一致的代换误认为是不一致的，我们需要将不同规则中的变元进行更名；有时候在演绎过程中会多次调用同一条规则，这时也要注意每次应用时都要使用更名的变量。为避免在匹配过程中产生一些不必要的约束，从而将原88剪枝策略所谓剪枝策略，就是每当以规则扩展局部解图时，就及时检查解图代换的一致性，并随即修剪掉不一致的局部解图，以免对这种局部解图的进一步徒劳搜索。剪枝策略895、与/或形演绎推理的特点优点：不必把公式化为子句集，保留了连接词“→”。这就可直观地表达出因果关系，比较自然。直接证明系统。缺点：对正向演绎推理，目标表达式被限制为文字的析取式；对逆向演绎推理，已知事实表达式被限制为文字的合取式；正、逆双向演绎推理虽然可以克服以上两个问题，但其“接头”的处理却比较困难。5、与/或形演绎推理的特点优点：90本章小结基本概念推理推理的控制策略代换与合一消解冲突策略……自然演绎推理归结演绎推理归结原理定理证明问题求解与/或形演绎推理正向、逆向、双向演绎推理本章小结基本概念91作业（P99~101）3.83.113.123.153.163.19作业（P99~101）3.89239、把生活中的每一天，都当作生命中的最后一天。

40、机不可失，时不再来。

41、就算全世界都否定我，还有我自己相信我。

42、不为模糊不清的未来担忧，只为清清楚楚的现在努力。

43、付出才会杰出。

44、成功不是凭梦想和希望，而是凭努力和实践。

45、成功这件事，自己才是老板！

46、暗自伤心，不如立即行动。

47、勤奋是你生命的密码，能译出你一部壮丽的史诗。

48、随随便便浪费的时间，再也不能赢回来。

49、不要轻易用过去来衡量生活的幸与不幸！每个人的生命都是可以绽放美丽的，只要你珍惜。

50、给自己定目标，一年，两年，五年，也许你出生不如别人好，通过努力，往往可以改变%的命运。破罐子破摔只能和懦弱做朋友。

51、当眼泪流尽的时候，留下的应该是坚强。

52、上天完全是为了坚强你的意志，才在道路上设下重重的障碍。

53、没有播种，何来收获；没有辛苦，何来成功；没有磨难，何来荣耀；没有挫折，何来辉煌。

54、只要路是对的，就不怕路远。

55、生命对某些人来说是美丽的，这些人的一生都为某个目标而奋斗。

56、浪花总是着扬帆者的路开放的。

74、失败是什么？没有什么，只是更走近成功一步；成功是什么？就是走过了所有通向失败的路，只剩下一条路，那就是成功的路。

75、要改变命运，首先改变自己。

76、我们若已接受最坏的，就再没有什么损失。

77、在生活中，我跌倒过。我在嘲笑声中站起来，虽然衣服脏了，但那是暂时的，它可以洗净。

78、没有压力的生活就会空虚；没有压力的青春就会枯萎；没有压力的生命就会黯淡。

79、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有久久不会退去的余香。

80、最困难的时候，就是距离成功不远了。

81、知道自己要干什么，夜深人静，问问自己，将来的打算，并朝着那个方向去实现。而不是无所事事和做一些无谓的事。

82、出路出路，走出去了，总是会有路的。困难苦难，困在家里就是难。

83、人生最大的喜悦是每个人都说你做不到，你却完成它了！

84、勇士搏出惊涛骇流而不沉沦，懦夫在风平浪静也会溺水。

85、生活不是林黛玉，不会因为忧伤而风情万种。

86、唯有行动才能改造命运。

87、即使行动导致错误，却也带来了学习与成长；不行动则是停滞与萎缩。

88、光说不干，事事落空；又说又干，马到成功。

89、对于每一个不利条件，都会存在与之相对应的有利条件。

90、人的潜能是一座无法估量的丰富的矿藏，只等着我们去挖掘。

91、要成功，不要与马赛跑，要骑在马上，马上成功。

2、虚心使人进步，骄傲使人落后。

3、谦虚是学习的朋友，自满是学习的敌人。

4、若要精，人前听。

5、喜欢吹嘘的人犹如一面大鼓，响声大腹中空。

6、强中更有强中手，莫向人前自夸口。

7、请教别人不折本，舌头打个滚。

8、人唯虚，始能知人。满招损，谦受益。满必溢，骄必败。39、把生活中的每一天，都当作生命中的最后一天。93第三章确定性推理3.1基本概念3.3自然演绎推理3.4归结演绎推理3.5基于规则的演绎推理（与/或形演绎推理）第三章确定性推理3.1基本概念943.1基本概念为使计算机具有智能，仅仅使它拥有知识还不够，更重要地，还必须使它具有思维能力，即能运用知识进行推理、求解问题的能力。知识表示（知识库）→求解过程（推理）经典推理是根据经典逻辑（命题逻辑和一阶谓词逻辑）的逻辑规则进行的一种推理，又称机械-自动定理证明。主要推理方法有：自然演绎推理、归结演绎推理、基于规则的演绎推理（与/或形演绎推理）。3.1基本概念为使计算机具有智能，仅仅使它拥有知识还不够，95基本概念推理推理是按某种策略由已知判断推出另一种判断的过程。在AI系统中，推理是由程序来实现的，称为推理机。不同的控制策略

推理方式及分类：基本概念推理96演绎推理由一般（全称判断）到个别（特称判断）的推理方法。核心是三段论，通常由一个大前提、一个小前提和一个结论三部分组成的。例：阿凡提的故事---两头驴的故事

①我肩上驮的是两头驴的东西（大前提） ②国王和大臣的衣衫是我肩上驮的（小前提）

③国王和大臣的衣衫是两头驴的东西（结论）演绎推理由一般（全称判断）到个别（特称判断）的推理方法。97归纳推理从个别到一般归纳结论不具备逻辑必然性莫里斯·科恩

逻辑学著作包括两部分，第一部分是演绎，其功能是解释谬误；第二部分是归纳，其功能是生成谬误我们获得关于这个实在世界的一般性事实的唯一方法！归纳推理从个别到一般我们获得关于这个实在世界的98演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。在归纳推理中，所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过99默认推理默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，也称为缺省推理。在推理过程中，如果发现原先的假设不正确，就撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。由于默认推理允许在推理过程中假设某些条件是成立的，因此解决了在一个不完备的知识集中进行推理的问题。封闭世界假设：如果没有足够的证据证明某命题不成立，就假定该命题成立默认推理默认推理是在知识不完全的情况下假设某些条件已经具备所100人工智能之确定性推理(-)课件101推理的控制策略推理过程涉及到求解方法和求解策略。求解方法包括匹配方法、不确定性的传递方法求解策略包括推理方向、求解策略、限制策略等。指推理是求一个解、所有解，还是最优解。为防止无穷的推理过程，以及由此带来的时间和空间复杂性，限制策略是对推理的深度、宽度、时间、空间等进行限制。推理的控制策略指推理是求一个解、所有解，还是最优解。为防止无102推理方向推理方向分为正向推理、逆向推理、混合推理、双向推理四种。无论哪一种推理，系统都具有知识库、数据库和推理机。正向推理需要解决的问题：1、确定匹配的方法2、确定搜索策略3、消解冲突正向推理的缺点：盲目，效率低逆向推理的优点：1、目标性强2、有利于向用户提供解释逆向推理的缺点：初始目标的选择有盲目性

开始提出假设该假设在数据库中？该假设是证据？在知识库中找出所有能导出该假设的知识，形成适用知识集KS从KS中选出一条知识，并将该知识的每一个运用条件都作为新的假设目标退出有此事实？询问用户NNNYYY逆向推理该假设成立该假设成立，并将此事实存入数据库还有假设？NYY开始把初始已知事实送入DBDB中包含问题的解KB中有可适用的知识把KB中所有的适用知识都选出送入KSKS空？按冲突消解策略从KS中选出一条知识进行推理推出的是新知识？将该新知识加入DB成功，退出失败，退出用户补充新知识？把用户提供的新事实加入DBNNNYYYY正向推理NYN推理方向正向推理需要解决的问题：逆向推理的优点：开始103逆向推理-例有关知识 规则1：IF你丢了自行车钥匙，并且车胎没气THEN自行车不能骑

规则2：IF自行车不能骑，并且你只有走路去THEN你听课会迟到

事实1：你丢了自行车钥匙

事实2：车胎没气问题

“你听课会迟到？”

逆向推理-例有关知识104逆向推理-例1.首先查找知识库，知该假设不是已有事实，但可由规则2导出，于是将规则2放入可用知识集，并将其两个前提条件“自行车不能骑”和“你只有走路去”都作为新的假设放入假设集。2.从假设集中取出假设“自行车不能骑”，它不是已有事实，但可由规则1导出，于是规则1被放入可用知识集，并将其两个前提条件“你丢了自行车钥匙”和“车胎没气”也作为新的假设放入假设集。3.从假设集中取出假设“你只有走路去”，此假设既不是已有事实，也不能被任何一条规则导出，询问用户“你只有走路去吗？”，若用户回答“是”，则该假设成立，并被放入已有事实集。4.假设集中还有两个假设“你丢了自行车钥匙”和“车胎没气”，它们都是已有事实，均为真。继续推理，假设集为空，推理过程结束，“你听课会迟到”得证。逆向推理-例1.首先查找知识库，知该假设不是已有事实，但可由105混合推理是把正向推理和逆向推理结合起来，吸取两种推理的优点。它通常适用以下3种情况：（1）已知事实不充分（2）由正向推理推出的可信度不高（3）希望得到更多的结论混合推理有两种方式：先正后逆和先逆后正双向推理是指正向推理和逆向推理同时进行，在推理过程的某步碰头。基本思想双向推理的难点是碰头的判定。开始进行正向推理需要逆向推理？以正向推理所得的结果作为假设进行逆向推理还需要正向推理？