人工智能之确定性推理

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

2、判断推出出另一种种判断的的过程。在AI系统中中，推理理是由程程序来实实现的，称为推理机。不同的控控制策略略推理方式式及分类类：演绎推理理由一般（全称判判断）到到个别（特称判判断）的的推理方方法。核心是三段论，通常由由一个大大前提、一个小小前提和和一个结结论三部部分组成成的。例：阿凡提的的故事-两两头驴的的故事 我肩肩上驮的的是两头头驴的东东西（大前提提） 国王王和大臣臣的衣衫衫是我肩肩上驮的的（小前前提） 国王王和大臣臣的衣衫衫是两头头驴的东东西（结结论）归纳推理理从个别到到一般归纳结论论不具备备逻辑必必然性莫里斯科恩逻辑学著著作包括括两部分分，第一一部分是是演绎，其功能能是解释释谬误；第二部

3、部分是归归纳，其其功能是是生成谬谬误我们获得得关于这这个实在在世界的的一般性性事实的的唯一方方法！演绎推理理所得出出的结论论蕴含在在一般性性知识的的前提中中，演绎绎推理只只不过是是将已有有事实揭揭示出来来，因此此它不能能增殖新新知识。在归纳推推理中，所推出出的结论论是没有有包含在在前提内内容中的的。这种种由个别别事物或或现象推推出一般般性知识识的过程程，是增增殖新知知识的过过程。默认推理理默认推理理是在知知识不完完全的情情况下假设某些些条件已已经具备备所进行的的推理，也称为为缺省推理理。在推理理过程中中，如果果发现原原先的假假设不正正确，就就撤消原原来的假假设以及及由此假假设所推推出的所所有结

4、论论，重新新按新情情况进行行推理。由于默默认推理理允许在在推理过过程中假假设某些些条件是是成立的的，因此此解决了了在一个个不完备备的知识识集中进进行推理理的问题题。封闭世界界假设：如果没没有足够够的证据据证明某某命题不不成立，就假定定该命题题成立推理的控控制策略略推理过程程涉及到到求解方法法和求解策略略。求解方法法包括匹配方法法、不确定性性的传递递方法求解策略略包括推理方向向、求解策略略、限制策略略等。指推理是求求一个解解、所有有解，还还是最优优解。为防止无无穷的推推理过程程，以及及由此带带来的时时间和空空间复杂杂性，限限制策略略是对推推理的深深度、宽宽度、时时间、空空间等进进行限制制。推理方

5、向向推理方向向分为正向推理理、逆向向推理、混合推推理、双双向推理理四种。无论哪一一种推理理，系统统都具有有知识库、数据库和推理机。正向推理理需要解解决的问问题：1、确定匹匹配的方方法2、确定搜搜索策略略3、消解冲冲突正向推理理的缺点点：盲目目，效率率低逆向推理的优优点：1、目标性性强2、有利于于向用户户提供解解释逆向推理理的缺点点：初始目标标的选择择有盲目目性 开始提出假设该假设在数据库中？该假设是证据？在知识库中找出所有能导出该假设的知识，形成适用知识集KS从KS中选出一条知识，并将该知识的每一个运用条件都作为新的假设目标退出有此事实？询问用户NNNYYY逆向推理该假设成立该假设成立，并将此

6、事实存入数据库还有假设？NYY开始把初始已知事实送入DBDB中包含问题的解KB中有可适用的知识把KB中所有的适用知识都选出送入KSKS空？按冲突消解策略从KS中选出一条知识进行推理推出的是新知识？将该新知识加入DB成功，退出失败，退出用户补充新知识？把用户提供的新事实加入DBNNNYYYY正向推理NYN逆向推理理-例有关知识识规则1：IF你丢了自自行车钥钥匙，并并且车胎胎没气THEN自行车不不能骑规则2：IF自行车不不能骑，并且你你只有走走路去THEN你听课会会迟到事实1：你丢了了自行车车钥匙事实2：车胎没没气问题“你听课课会迟到到？”逆向推理理-例1.首先查找找知识库库，知该该假设不不是已有

7、有事实，但可由由规则2导出，于于是将规规则2放入可用用知识集集，并将将其两个个前提条条件“自自行车不不能骑”和“你你只有走走路去”都作为为新的假假设放入入假设集集。2.从假设集集中取出出假设“自行车车不能骑骑”，它它不是已已有事实实，但可可由规则则1导出，于于是规则则1被放入可可用知识识集，并并将其两两个前提提条件“你丢了了自行车车钥匙”和“车车胎没气气”也作作为新的的假设放放入假设设集。3.从假设集集中取出出假设“你只有有走路去去”，此此假设既既不是已已有事实实，也不不能被任任何一条条规则导导出，询询问用户户“你只只有走路路去吗？”，若若用户回回答“是是”，则则该假设设成立，并被放放入已有有

8、事实集集。4.假设集中中还有两两个假设设“你丢丢了自行行车钥匙匙”和“车胎没没气”，它们都都是已有有事实，均为真真。继续续推理，假设集为为空，推理过过程结束束，“你你听课会会迟到”得证。混合推理理是把正正向推理理和逆向向推理结结合起来来，吸取取两种推推理的优优点。它它通常适适用以下下3种情况：（1）已知事事实不充充分（2）由正向向推理推推出的可可信度不不高（3）希望得得到更多多的结论论混合推理理有两种种方式：先正后逆逆和先逆后正正双向推理理是指正正向推理理和逆向向推理同同时进行行，在推推理过程程的某步步碰头。基本思想想双向推理理的难点点是碰头的判定。开始进行正向推理需要逆向推理？以正向推理所得

9、的结果作为假设进行逆向推理还需要正向推理？输出结果开始YYNN先正后逆开始进行逆向推理需要正向推理？进行正向推理还需要逆向推理？输出结果开始YYNN先逆后正模式匹配配模式匹配配是指对对两个知知识模式式（如两两个谓词词公式、框架或或语义片片段等）的比较较与藕合合，即检检查这两两个知识识模式是是否完全全一致或或近似一一致。按匹配的的近似程程度划分分，可分分为确定性匹匹配和不确定性性匹配。确定性匹配是指两个知识模式完全一致，或经过变量代换后变得完全一致。例如： 不确定性性匹配是是指两个个知识模模式不完完全一致致，但总总体上它它们的相相似度在在一定的的限度内内。定义3.1置置换（代换） 代换是形如 的

10、有限集合。其中 是项 是互不相同的变元； 表示用 代换 ，不允许 与 相同，也不允许变元 循环地出现在另一个 中。根据定义 是代换不是代换换是代换设有代换换a/x,f(b)/y, u/z则对公式式EP(x,y,z)有 EP(a, f(b), u)对公式E运用代代换s，记作Es。Es称作作公式E在代换换s下的的例（例示），它是是E的逻辑结论论。设是两个代换，则此两个代换的复合也是一个代换，它是从删除以下两种元素后剩下的元素所构成的集合，记作 定义3.2代代换的的复合例如：则解释：就是对一个公式先运用代换，然后再运用代换.大家验证证一下！定义3.3公式集的的合一设有公式式集，若存存在一个个代换使使

11、得则称是是公公式集的的一个合一，且称是是可合一的的。一个公式集的合一一般来说不是唯一的例如公式集有合一定义3.4 最一般合一设 是公式集 的一个合一，如果对任一个合一 都存在一个代换 ，使得则称 是公式集 的一个最一般合一。如前面提到的公式集 是最一般合一，而 则不是最一般合一。 按照最一般合一的定义，有：因此，对于一个公式集来说，如果存在多个合一，则其中代换数最少、限制最少、产生的例最具一般性的代换称为最一般合一。如：一般来说，最一般合一也不是唯一的， 同样是该公式集的一个最一般合一。 求最一般合一一差异集：求最一般合一一算法：（1）令。这这里，是是欲求求最一般般合一的的公式集集，是是空代代

12、换，它它表示不不做代换换。（2）若只只含一个个表达式式，则算算法停止止，就就是是最一般般合一。（3）找出的的差异集。（4）若中中存在在元素和和，其中是是变元，是是项，且且不不在在中中出出现，则则置：然后转向向（2）。（5）算法终止止，的的最最一般合合一不存存在。举例：求的最一般合一。消解冲突突策略在推理过过程中，系统要要不断地地用当前前已知事事实与知知识库中中的知识识进行匹匹配，此此时可能能发生以以下三种种情况：（1）已已知事实实不能与与知识库库中的任任何知识识匹配（2）已已知事实实恰好与与知识库库中的一一条知识识匹配（3）已已知事实实可与知知识库中中的多条条知识匹匹配，或或者多组组已知事事实

13、可与与知识库库中的某某一条知知识匹配配，或者者多组已已知事实实可与知知识库中中的多条条知识匹匹配。处于第三三种情况况时，就就发生冲突。此时需需要按一一定的消解策略略解决冲突突。冲突：多多个知识识都匹配配成功。冲突消解解的基本本思想都都是对知知识进行行排序。对于产生生式系统统，若出出现以下下情况就就认为发发生冲突突：（1）对对正向推推理而言言，如果果有多条条产生式式规则的的前件都都和已知知事实匹匹配，或或者有多多组已知知事实都都与同一一条产生生式规则则的前件件匹配；或者以以上两种种情况同同时出现现。（2）对对逆向推推理而言言，如果果有多条条产生式式规则的的后件都都和同一一假设匹匹配，或或者有多多

14、条产生生式规则则的后件件可与多多个假设设匹配。常用的消消解冲突突策略：1、按针对对性排序序设有如下下两条产产生式规规则：如果存在在最一般般合一，使得r1中的每个个Ai都可以变变成相应应的Bi，如Ai=P(x,y)，Bi=P(a,z)则称r2比r1有更大的的针对性性，r1比r2有更大的的通用性性。该策略选用用针对性性较强的的产生式式规则。2、按已知知事实的的新鲜性性排序把数据库库中后生生成的事事实称为为新鲜的的事实，该策略略要求具具有最大大新鲜性性的事实实总是排排在前面面。设规则r1可与事实实组A匹配成功功，规则则r2可与事实实组B匹配成功功，则A和B哪一组中中的事实实更新鲜鲜，与它它匹配的的规

15、则就就先被利利用。如何衡量量A和B哪一组中中的事实实更新鲜鲜呢？3、按匹匹配度排排序4、根据据领域问问题的特特点排序序先验知识识、启发发式知识识5、按上上下文限限制排序序把规则按按照下上上文分组组，并只只能选取取组中的的规则。6、按冗冗余限制制排序冗余知识识少的规规则先推推。7、按条条件个数数排序条件少的的规则先先推。尽量量减少冲冲突的发发生，使使推理具具有较高高的效率率3.3自自然演演绎推理理自然演绎绎推理就就是从一一组已知知为真的的事实出出发，直接运用经典逻辑辑的推理理规则推出结论论的过程程。推理规则则包括：1、假言言推理2、拒取取式推理理3、P规规则：在在推理的的任何步步骤都可可引入前提

16、4、T规规则：推推理时，如果前前面步骤骤有一个个或多个个公式永真蕴含含公式S（逻辑结论论），则可可把公式式S引入入推理过过程中。例3.1已已知下述述事实：A，B，AC，BCD，D Q求证：Q为真证明： A，A C C P规则及假言推理 B，C BC 合取 BC，BCD D T规则及假言推理 D，DQ Q T规则及假言推理思考题：所有人都都是必死死的；苏格拉底底是人；求证：苏苏格拉底底是必死死的。自然演绎绎推理的的优点：表达定理理证明过过程自然，容易理理解，而而且拥有有丰富的推推理规则则，推理过过程灵活，便于在在它的推推理规则则中嵌入入领域启发发式知识识。自然演绎绎推理的的缺点：容易产生生组合爆

17、炸炸中间结论论呈指数数级增长长。3.4归归结结演绎推推理要证明PQ永永真，需需要证明明它在任任何个体体域上所所有可能能的解释释都是永永真的，这是难难以实现现的。采采用反证法的思想，只要证证明P Q永假（不不可满足足）即可。这是因为为：PQPQ（PQ）PQ海伯伦（Herbrand）和鲁宾逊（Robinson）在这个方方向上先先后作了了卓越的的研究工工作。首首先，由由海伯伦伦提出的的H域（海伯伯伦域）和海伯伯伦定理理，为自自动定理理证明奠奠定了理理论基础础；然后后，由鲁鲁宾逊提提出的归结原理理（消解解原理）则使机器器定理证证明成为为可能。子句：在谓词公公式中，把原子子谓词公公式及其其否定统统称为文

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

19、：合取范范式(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)

20、(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：求求谓词公公式G=xyz(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)该谓词公公式已经经是合取范式式了，消去去全称量量词、对对变元更更名、消消去合取取词，得得到谓

21、词词公式G的子句集是P(x,f(x)R(x,f(x),g(x)，Q(y,g(y)R(y,f(y),g(y)例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(

22、y)转化要点点：1、第一步步应先消消去蕴涵涵符号，再内移移否定符符号等其其它工作作；2、先内移移否定符符号，再再消去量量词；3、先消存存在量词词，再消消全称量量词。定理3.1设设有谓谓词公式式F，其其标准形形的子句句集为S，则F不可满足足的充要条件件是S不可满足足。（注意意：F和和S并不不等价！存存在量量词消去去、变元元更名）因此，要要想证明明F不可可满足，只需证证明S不不可满足足即可，鲁滨逊逊提出的的归结原原理就是是用来解解决这一一问题的的。鲁宾逊归结原理理为提高判判定子句句集不可可满足的的有效性性，鲁宾宾逊于1965年提出了了归结(Resolution)原理，也也称为消解原理理。由谓词转转

23、化子句句集的过过程可以以看出，在子句句集中各各子句之之间是合取关系，其其中只要要有一个个子句不不可满足足，则子子句集就就不可满满足。空空子句是是不可满满足的，若一个子子句集含含有一个个空子句句（该子子句集中中有矛盾盾），子子句集一一定是不不可满足足的。鲁宾逊归归结原理理的基本本是：检检查子句句集S是否包含含空子句句，若包包含，则则S不可满足足；若不不包含，就在子子句集中中选择合合适的子子句进行行归结，一旦通通过归结推出空子句，就说明明子句集集S是不可满满足的。定义3.18若P是原原子谓词词公式，则称P和P为互补文字字。命题逻辑辑中归结结原理设C1和C2是子句集集中任意意二个子子句，如如果C1中

24、的文字字L1和C2中的文字字L2互补，那那么从C1和C2中分别消消去L1和L2，并对C1和C2的剩余部部分析取取，构成成一个新新的子句句C12，则称这一一过程为为归结，称C12为C1和C2的归结式，C1和C2是C12的亲本子句句。例：C1=PQ，C2=QR，C3=PC12=PR，C123=RPQQRPRPR 归结树定理3.2归结式C12是是其亲本本子句C1和C2的逻辑结论论，即：C1C2C12如何证明明？推论1：设C1和C2是子句集集S中的两个个子句，C12是它们的的归结式式，若用用C12代替C1和C2后得到新新子句集集S1，则S1的不可满满足性S的不可满满足性推论2：设C1和C2是子句集集S

25、中的两个个子句，C12是它们的的归结式式，若用用C12加入S中后，得得到新子子句集S1，则S1的不可满满足性S的不可满满足性谓词逻辑辑中的归归结原理理在谓词逻逻辑情况况下，由由于子句句中含有有变量，不能像像命题逻逻辑那样样直接发发现和消消去互补补文字，往往需需对潜在的互互补文字字先作变量代换换和合一一处理，才才能用于于归结。例如有如如下两个个子句：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)又该如何何？定义3.20设C1和和C2是是两个没没有相同

26、同变元的的子句，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做了更严严格的限限制，有有可能存存在

27、归结结不出结结果的可可能性。一般来说说：若子子句C中有两个个或两个个以上的的文字具具有最一一般的合合一，则称称C为子句C的因子。如果C是一个单单文字，则称为为单因子子。定义3.21子句C1和C2的归结结式是下下列二元元归结式式之一：（1）C1和和C2的的二元归归结式；（2）C1和和C2的的因子C22的二元归结结式；（3）C1的的因子C11和C2的二元归结结式；（4）C1的的因子C11和C2的的因子C22的二元归结结式。对于谓词词逻辑，定理3.2仍仍然适用用。归结演绎绎的完备备性从不可满足足的意义上上说，基基于归结结的演绎绎方法是是完备的的，即若若子句集集S不可满足足，就必必定存在在一个从从S到

28、空子句句的归结结演绎；反之，若存在在一个从从S到空子句句的归结结演绎，则S必定是不不可满足足的。关关于归结结演绎的的完备性性可用海海伯伦定定理进行行证明，因此从从这个意意义上讲讲，归结结原理是是建立在在海伯伦伦定理之之上的。不过归结原理理并不能能用于解解决子句句集不可可满足性性的不可可判定问问题，即对于于永真和可满足的子句集集，判定定过程将将无休止止地进行行下去，得不到到任何结结果。归结反演演证明Q是是P1，P2Pn的逻辑结结论，即：P1P2PnQ只需证明明(P1P2PnQ)是不可满足足的。因为(P1P2PnQ)(P1P2Pn) Q)(P1P2Pn)Q只需证明明子句集P1，P2，Pn，Q是不可

29、满满足的。对子句集集中的子子句相互互归结，直到归归结出空子句，这个过过程就是是归结反演演。设F为已已知前提提的公式式集，Q为目标标公式，用归结结反演证证明Q为为真的步步骤：（1）否定Q，得到Q；（2）把Q并入到公公式集F中，得到到F，Q；（3）把公式集集F，Q化为子句句集S（P126127）；（4）应用归结结原理对对子句集集S中的子句句进行归归结，并并把每次次得到的的归结式式放入S中。如此此反复，若出现现空子句，就停止止归结，此时就就证明了了Q为真。例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)

30、.从A1变换P(y)R(y).从A1变换换P(a).从A2变换S(a).从A2变换S(z)R(z).结结论的否否定R(a).归结a/yR(a).归结结a/zNIL.归归结得证.例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).求证结结论将已知条件件,求

31、证结论论的反化成子句句集R(x)L(x)D(y)L(y)D(a)I(a)I(z)R(z)L(a).2,3归归结a/yR(a).1,6归归结a/xR(a).4,5归结结a/zNIL.7,8归结得证.例3.17 “快乐学生生”问题题假设：任任何通过过计算机机考试并并获奖的的人都是是快乐的的，任何何肯学习习或幸运运的人都都可以通通过所有有考试，张不肯肯学习但但他是幸幸运的，任何幸幸运的人人都能获获奖。求证：张张是快乐乐的。解：先定定义谓词词：Pass(x, y)x可以通过过y考试Win(x,prize)x能获得奖奖励Study(x)x肯学习Happy(x)x是快乐的的Lucky(x)x是幸运的的再将

32、问题题用谓词词表示如如下：“任何通通过计算算机考试试并奖的的人都是是快乐的的”(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)将上述谓谓词公式式转化为为子句集集如下：(1)Pass(x,computer)Win(x,prize)Happ

33、y(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)(结论的否否定) 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(

34、u, v)Lucky(zhang)Lucky(zhang)NILw/xzhang/wzhang/u, computer/v例3.18 “激动人心心的生活活”问题题假设：所所有不贫贫穷并且且聪明的的人都是是快乐的的，那些些看书的的人是聪聪明的。李明能能看书且且不贫穷穷，快乐乐的人过过着激动动人心的的生活。求证：李李明过着着激动人人心的生生活。解：先定定义谓词词：Poor(x)x是贫穷的的Smart(x)x是聪明的的Happy(x)x是快乐的的Read(x)x能看书Exciting(x)x过着激动动人心的的生活再将问题题用谓词词表示如如下：“所有不不贫穷并并且聪明明的人都都是快乐乐的”(x)(Po

35、or(x)Smart(x)Happy(x)“那些看书书的人是是聪明的的”(y)(Read(y) Smart(y)“李明能看看书且不不贫穷”Read(Liming)Poor(Liming)“快乐的人人过着激激动人心心的生活活”(z)(Happy(z)Exciting(z)目标“李李明过着着激动人人心的生生活”的的否定Exciting(Liming)将上述谓谓词公式式转化为为子句集集如下：(1)Poor(x)Smart(x)Happy(x)(2)Read(y)Smart(y)(3)Read(Liming)(4)Poor(Liming)(5)Happy(z)Exciting(z)(6)Excitin

36、g(Liming)(结论的否否定) 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)NILLiming/zLiming/xLiming/y应用归结结原理求求问题的的答案求问题的的答案与与定理证证明类似似，其步步骤为：（1）用用谓词公公式表示示已知前前提，并并化为子子句集S；（2）用用谓词公公式表示示待

37、求解解，并将将其否定与谓词ANSWER构构成析取式（同一个个子句）；ANSWER是一一个为求求解而设设定的谓谓词，其变元必必须与问问题公式式的变元元一致；（用重言式也可）（3）把把此析取取式化为为子句集集，并把把该子句句集假如如到子句句集S中中，得到到子句集集S；（4）对S应用归结结原理进进行归结结；（5）若若得到归归结式ANSWER，则答案案就在ANSWER中中。例设设A,B,C三三人中有有人从不不说真话话，也有有人从不不说假话话。某人人向这三三人分别别提出同同一个问问题：谁谁是说谎谎者？A答：“B和C都是说说谎者”；B答答：“A和C都都是说谎谎者”；C答：“A和和B中至至少有一一个是说说谎

38、者”。求谁谁是老实实人，谁谁是说谎谎者？解：设用用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)把上述公公式化成成子句集集，得到到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。即多一一个子句句

39、：(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从不说说假话。下面证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也不是是老实

40、人人。归结时，并不要要求把子子句集中中所有的的子句都都用到。在归结过过程中，一个子子句可以以多次被被用来进进行归结结。例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)把上述公公式化为为子句

41、集集：C(zhang,li)C(x,y)At(x,u)At(y,u)At(zhang, 302)把目标的的否定化化成子句句式，并并用重言言式At(li,v)At(li,v)代替之。把此重言言式加入入前提子子句集中中，得到到一个新新的子句句集，对对这个新新的子句句集，应应用归结结原理求求出其证证明树。其求解解过程如如下图所所示。该证明树树的根子子句就是是所求的的答案，即“李李明在302教室”。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(zha

42、ng, 302)At(li, 302)li/y,v/uZhang/x302/v归结策略略1、计算算机进行行归结的的一般过过程设子句集集S=C1，C2，C3，C4，计算算机对此此子句集集进行归归结的一一般过程程是：（1）从从子句C1开始始，逐个个与C2，C3，C4进行比比较，若若能归结结，就求求出归结结式。然然后用C2与C3、C4进行行归结，最后C3和C4进行行归结。经过这这一轮的的比较和和归结后后，就得得到一组组归结式式，称为为第一级归归结式。（2）再再从C1开始，用S中的子子句分别与第第一级归归结式中中的子句句逐个地地比较、归结，这样又又会得到到一组归归结式，称为第二级归归结式。（3）仍仍然

43、从C1开始始，用S中的子子句及第第一级归归结式中中的子句句分别与第第二级归归结式中中的子句句逐个地地比较、归结，得到第第三级归归结式。如此继续续，直到到出现空空子句或或者不能能再继续续归结为为止。例 设有有子句集集：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)归结就可可以得到到NIL2、归结结策略为了尽量量避免造造成时空空浪费，提高归归结的效效率，需需要对归归结过程程进行适适当的控控制。归结策略略分为两两大类：删除策略略：删除某某些无用用子句，

44、缩小归归结的范范围限制策略略：对参加加归结的的子句进进行限制制，减小小归结的的盲盲目目性2、删除除策略删除策略略是指在在归结过过程中把把子句集集的无用用的子句句删除掉掉这样就就会缩小寻找找范围，减少比比较次数数。删除策策略具有有以下几几种删除除方法：（1）纯纯文字删删除法。如果某某文字L在子句句集中不不存在可可与之互互补的文文字L，则称该文文字是纯纯文字。例如：S=PQR,QR,Q,R中是纯纯文字删除纯文文字所在在的子句句PQR（2）重言式删删除法。如果一一个子句句中同时时包含互互补文字字对，则则称该子子句为重重言式。重言式式是永真真式。例如：P(x)P(x) ,P(x)(x)P(x)（）包孕

45、删除除法。设设子句C1和C2，如果存在在一个代代换，使得C1C2，则称C1包孕于C2。删除包孕的子子句C2，不会影影响子句句集的不可满足足性，因为C2是C1的逻辑蕴蕴涵，即即C1C2，如何证证明？例如：P(x)包孕于P(y)Q(z)=y/xP(x)包孕于P(a)=a/xP(x)包孕于P(a)Q(z)=a/xP(a,x)P(y,b)包包孕于P(a,b)=b/x,a/y2、删除除策略（续）如子句集集P(x),P(a),P(b)、支持持集策略略每一次归归结时，亲本子子句中至至少有一一个是由由目标公公式的否否定所得得到的子子句，或或者是他他们的后后裔。可可以证明明，支持持集策略略是完备的。例设设有子句

46、句集：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)4、线性性输入策策略参加归结结的两个个子句中中必须至至少有一一个是初初始子句句集的子子句。线线性输入入策略是是不完备的。例如如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)NI

47、L5、单文字字子句策策略如果一个个子句只只包含一一个文字字，就称称它为单单文字子子句。该策略要要求参加加归结的的子句至至少有一一个是单单文字子子句。该策略也也是不完备的。I(x)R(x)I(a)R(y)L(y)L(a)R(a)R(a)NIL6、祖先先过滤形形策略当两个子子句C1和C2进行归归结时，只要它它们满足足下述两两个条件件中的任任一个就就可以归归结。（1）C1和C2中至至少有一一个是初初始子句句集的子子句（线线性输入入）；（2）如如果两个个子句都都不是初初始子句句集的子子句，则则一个应应是另一一个的祖祖先。祖先过滤滤形策略略是完备的。Q(x) P(x)Q(y)P(y) P(x) Q(w)

48、P(w) Q(w)Q(a)P(a)P(a)NIL归结演绎绎推理具具有证明明简单，在计算算机上容容易实现现等优点点，但同同时具有以下下缺点：（1）必须把把逻辑公公式化成成子句集集。（2）不自然然，不便便于阅读读与理解解。如：P(x)Q(x)没有P(x)Q(x)直观。（3）有可能能丢失一一些重要要的控制制信息。针对以上上缺点，与/或形演绎绎推理可可以克服服。通常很多多应用知知识是用用蕴含式式直接表表达的，因此都都带有超逻辑的的或启发发式的控控制信息息。在归结结反演证证明系统统中，要要把这些些表达式式化成子子句形表表示，这这就可能能丢掉隐隐含在蕴蕴含式中中、对推推理有用用的控制制信息，例如下下面的几

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

50、得得到某个个目标公公式的一一个终止止条件。在这种推推理中，对已知知事实、F规则则及目标标公式的的表示形形式都有有一定的的要求，如果不不是所要要求的形形式，就就需要进进行变换换。事实为支持演演绎推理理，事实实表达式式不必化化简为子子句集，只需规规范地表表示为不不含蕴涵涵符号的的文字与或或形，具体步骤骤如下：（1）利用PQPQ消去公式式中的“”；（2）把“”移到到紧靠谓词词的位置置上；（3）重新命命名变元元名，使使不同量词词约束的的变元有不不同的名名字；（4）引入Skolem函数消去去存在量量词；（5）消去全全称量词词，使主合取式式中的变元不同同名。例如：(x)(y)(Q(y,x) (R(y)P(

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

52、(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)对规则作作单文字字前项的的限制将将大大简简化了应应用时的的匹配过过程，对对非单文文字前项项的情况况，若形形式为（L1L2）W，则可化化成与其其等价的的两个规规则L1W与与L2W进行行处理。目标公式式的表示示形式目标公式式用子句（析析取式）表示。推理过程程（1）首首先用与/或树树表示已知知事实（2）用用F规则则的左部部与与/或树树的叶节节点匹配，并并把匹配配成功的的F规则则加入到到与/或或树中。（3）重重复（2），直直到产生生一个含有有以目标标节点作作为终止止节点的的一致解解图为止。例 设已已知事实实为：ABF规则为为：r1：ACDr2：BEG欲证明的的目标公公式为：CGABABABCDEGCG已知事实F规则目标解图？（=归结式？）归结演绎绎推理该该如何做做？例 设已已知事实实为(PQ)R)(S(TU)规则则为S(XY)Z解图？（=归结式？）例事事实与或或形表示示为P(A, y)(Q(x, A)R(B,y)规规则为P(z,B)(