人工智能：第4章 确定性推理.ppt

第第4章章 确定性推理确定性推理 n     智能系统的推理过程实际上就是一种思维过程按照推智能系统的推理过程实际上就是一种思维过程按照推理过程所用知识的确定性，推理可分为确定性推理和不确理过程所用知识的确定性，推理可分为确定性推理和不确定性推理对于推理的这两种不同类型，本章重点讨论前定性推理对于推理的这两种不同类型，本章重点讨论前一种，不确定性推理放到下一章讨论一种，不确定性推理放到下一章讨论 n4.1  推理的基本概念推理的基本概念n4.2  推理的逻辑基础推理的逻辑基础n4.3  自然演绎推理自然演绎推理n4.4  归结演绎推理归结演绎推理4.1 推理的基本概念推理的基本概念n4.1.1  什么是推理什么是推理n4.1.2  推理方法及其分类推理方法及其分类n4.1.3  推理的控制策略及其分类推理的控制策略及其分类n4.1.4  正向推理正向推理n4.1.5  逆向推理逆向推理n4.1.6  混合推理混合推理4.1.1  什么是推理什么是推理n推理的概念推理的概念n 是指按照某种策略从已知事实出发去推出结论的过程是指按照某种策略从已知事实出发去推出结论的过程n 推理所用的事实：推理所用的事实：n 初始证据：初始证据：推理前用户提供的推理前用户提供的n 中间结论：中间结论：推理过程中所得到的推理过程中所得到的n 推理过程：推理过程：由推理机来完成，所谓推理机就是智能系统中由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。

用来实现推理的那些程序n 例如，例如，医疗专家系统，专家知识保存在知识库中推理开医疗专家系统，专家知识保存在知识库中推理开始时，先把病人的症状和检查结果放到综合数据库中，然后再始时，先把病人的症状和检查结果放到综合数据库中，然后再从综合数据库的初始证据出发，按照某种策略在知识库中寻找，从综合数据库的初始证据出发，按照某种策略在知识库中寻找，并使用知识，直到推出最终结论为止并使用知识，直到推出最终结论为止n推理的两个基本问题推理的两个基本问题n 推理的方法：推理的方法：解决前提和结论的逻辑关系，不确定性传递解决前提和结论的逻辑关系，不确定性传递n 推理的控制策略：推理的控制策略：解决推理方向，冲突消解策略解决推理方向，冲突消解策略4.1.2  推理方法及其分类推理方法及其分类1. 按推理的逻辑基础分类按推理的逻辑基础分类(1/4)n可分为演绎推理、归纳推理等可分为演绎推理、归纳推理等 n演绎推理演绎推理n      演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论是一种由一般到个别的推理方法，其核心是适合于某种个别情况的结论。

是一种由一般到个别的推理方法，其核心是三段论，如三段论，如假言推理、拒取式和假言三段论假言推理、拒取式和假言三段论n      例：例： 假言三段论假言三段论n             A→B，，B→C ⇒⇒ A→Cn      常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的其中，其中，大前提大前提是已知的一般性知识或推理过程得到的判断；是已知的一般性知识或推理过程得到的判断；小前提小前提是关于是关于某种具体情况或某个具体实例的判断；某种具体情况或某个具体实例的判断；结论结论是由大前提推出的，并且适合是由大前提推出的，并且适合于小前提的判断于小前提的判断n     例如，有如下三个判断：例如，有如下三个判断：n     ①①  计算机系的学生都会编程序；计算机系的学生都会编程序；   （一般性知识）（一般性知识）n     ②②  程强是计算机系的一位学生；程强是计算机系的一位学生；   （具体情况）（具体情况）n     ③③  程强会编程序程强会编程序                （结论）（结论）n     这是一个三段论推理。

其中，这是一个三段论推理其中，①①是大前提，是大前提，②②是小前提；是小前提；③③是经演绎推是经演绎推出来的结论出来的结论n    可见，其结论是蕴含在大前提中的可见，其结论是蕴含在大前提中的4.1.2  推理方法及其分类推理方法及其分类1. 按推理的逻辑基础分类按推理的逻辑基础分类(2/4)n归纳推理归纳推理n是一种由个别到一般的推理方法归纳推理的类型是一种由个别到一般的推理方法归纳推理的类型n     按照所选事例的广泛性按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理可分为完全归纳推理和不完全归纳推理n     按照推理所使用的方法按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等可分为枚举、类比、统计和差异归纳推理等n     完全归纳推理完全归纳推理n    是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性如，计算机质量检验都具有某种属性，推出该类事物是否具有此属性如，计算机质量检验n    不完全归纳推理不完全归纳推理n    是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。

例如，计算机，随机抽查例如，计算机，随机抽查n    枚举归纳推理枚举归纳推理n     是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性种属性，则可推出该类事物都具有此种属性n例如，设有如下事例：例如，设有如下事例：n    王强是计算机系学生，他会编程序；王强是计算机系学生，他会编程序；n    高华是计算机系学生，她会编程序；高华是计算机系学生，她会编程序；n     ……                ……n    当这些具体事例足够多时，就可归纳出一个一般性的知识：当这些具体事例足够多时，就可归纳出一个一般性的知识：n           凡是计算机系的学生，就一定会编程序凡是计算机系的学生，就一定会编程序4.1.2  推理方法及其分类推理方法及其分类1. 按推理的逻辑基础分类按推理的逻辑基础分类(3/4)n类比归纳推理类比归纳推理n     是指在两个或两类事物有许多属性都相同或相似的基础上，推出是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。

它们在其他属性上也相同或相似的一种归纳推理n     设设A、、B分别是两类事物的集合：分别是两类事物的集合：n              A={a1,a2,……}n              B={b1,b2,……}n并设并设ai与与bi总是成对出现，且当总是成对出现，且当ai有属性有属性P时，时，bi就有属性就有属性Q与此对应，与此对应，即即n                  P(ai)→Q(bi)     i=1,2,…..n     则当则当A与与B中有一新的元素对出现时，若已知中有一新的元素对出现时，若已知a'有属性有属性P，，b'有属有属性性Q，即，即n                  P(a')→Q(b')n     类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度性之间的相关程度4.1.2  推理方法及其分类推理方法及其分类 1. 按推理的逻辑基础分类按推理的逻辑基础分类(4/4)n演绎推理与归纳推理的区别演绎推理与归纳推理的区别n    演绎推理演绎推理是在已知领域内的一般性知识的前提下，是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确通过演绎求解一个具体问题或者证明一个结论的正确性。

它所得出的结论实际上早已蕴含在一般性知识的性它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因前提中，演绎推理只不过是将已有事实揭露出来，因此它此它不能增殖新知识不能增殖新知识n    归纳推理归纳推理所推出的结论是没有包含在前提内容中的所推出的结论是没有包含在前提内容中的这种由个别事物或现象推出一般性知识的过程，这种由个别事物或现象推出一般性知识的过程，是增是增殖新知识殖新知识的过程n    例如，例如，一位计算机维修员，从书本知识，到通过大一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种量实例积累经验，是一种归纳归纳推理方式运用这些一推理方式运用这些一般性知识知识去维修计算机的过程则是般性知识知识去维修计算机的过程则是演绎演绎推理 4.1.3  推理的控制策略及其分类推理的控制策略及其分类n推理的控制策略推理的控制策略n 推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略n 推理的控制策略是指推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略如何使用领域知识使推理过程尽快达到目标的策略。

n控制策略的分类控制策略的分类n 由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为略又可分为推理策略和搜索策略推理策略和搜索策略n 推理策略推理策略n 主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等限制策略、冲突消解策略等n 推理方向控制策略推理方向控制策略用于确定推理的控制方向，可分为正向推理、逆向推理、用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理混合推理及双向推理n 求解策略求解策略是指仅求一个解，还是求所有解或最优解等是指仅求一个解，还是求所有解或最优解等n 限制策略限制策略是指对推理的深度、宽度、时间、空间等进行的限制是指对推理的深度、宽度、时间、空间等进行的限制n 冲突消解策略冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。

中选出一条最佳知识用于推理的策略n 搜索策略搜索策略n 主要解决主要解决推理线路、推理效果、推理效率等问题推理线路、推理效果、推理效率等问题 本章主要讨论推理策略，本章主要讨论推理策略，至于搜索策略将放到第至于搜索策略将放到第4章单独讨论章单独讨论4.1.4  正向推理正向推理推理算法推理算法n      从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理 n算法描述算法描述n     (1) 把用户提供的初始证据放入综合数据库；把用户提供的初始证据放入综合数据库；n     (2) 检查综合数据库中是否包含了问题的解，若已包含，则求解结束，检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；并成功推出；否则执行下一步；n     (3) 检查知识库中是否有可用知识，若有，形成当前可用知识集，执行检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转下一步；否则转(5)n     (4) 按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转理，并将推出的新事实加入综合数据库种，然后转(2)。

n     (5) 询问用户是否可以进一步补充新的事实，若可补充，则将补充的新询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转事实加入综合数据库中，然后转(3)；否则表示无解，失败退出否则表示无解，失败退出n     至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等这些问题涉及到了知识的中有多条知识可用时应该先使用那一条知识等这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论匹配方法和冲突消解策略，以后将会分别讨论n     其流程图如下：其流程图如下：把初始证据放入把初始证据放入DBDB中有解吗？中有解吗？KB中有可用知识吗？中有可用知识吗？ 形成可用知识集形成可用知识集可用知识集空吗？可用知识集空吗？按照冲突消解策略从该知识按照冲突消解策略从该知识集中选出一条知识进行推理集中选出一条知识进行推理 推出的是新事实吗？推出的是新事实吗？ 将新事实加入到将新事实加入到DB把用户补充的新事把用户补充的新事实实加入到加入到DB中中 用户可补充新事实吗？用户可补充新事实吗？ 失败退出失败退出 成功退出成功退出YNNYNNNYYY4.1.4  正向推理正向推理推理例子推理例子n    例例4.1请用正向推理完成以下问题的求解请用正向推理完成以下问题的求解n    假设知识库中包含有以下假设知识库中包含有以下2条规则：条规则：n            r1：： IF   B   THEN   Cn            r2：： IF   A   THEN   Bn已知初始证据已知初始证据A，求证目标，求证目标C。

n     解：本例的推理过程如下：解：本例的推理过程如下：n     推理开始前，综合数据库为空推理开始前，综合数据库为空n     推理开始后，先把推理开始后，先把A放入综合数据库，然后检查综合数据库中是否含有该放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为问题的解，回答为“N”n     接着检查知识库中是否有可用知识，显然接着检查知识库中是否有可用知识，显然r2可用，形成仅含可用，形成仅含r2的知识集从的知识集从该知识集中取出该知识集中取出r2，推出新的实事，推出新的实事B，将，将B加入综合数据库，检查综合数据库加入综合数据库，检查综合数据库中是否含有目标中是否含有目标C，回答为，回答为“N”n     再检查知识库中是否有可用知识，此时由于再检查知识库中是否有可用知识，此时由于B的加入使得的加入使得r1为可用，形成仅为可用，形成仅含含r1的知识集从该知识集中取出的知识集从该知识集中取出r1，推出新的实事，推出新的实事C，将，将C加入综合数据库，加入综合数据库，检查综合数据库中是否含有目标检查综合数据库中是否含有目标C，回答为，回答为“Y”n    它说明综合数据库中已经含有问题的解，推理成功结束，目标它说明综合数据库中已经含有问题的解，推理成功结束，目标C得证。

得证4.1.4  正向推理正向推理优缺点优缺点n正向推理的主要优点正向推理的主要优点n 比较直观，允许用户主动提供有用的事实信息，适比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解合于诊断、设计、预测、监控等领域的问题求解n正向推理的主要缺点正向推理的主要缺点n 推理无明确目标，求解问题是可能会执行许多与解推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低无关的操作，导致推理效率较低 4.1.5  逆向推理逆向推理推理算法推理算法n     从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理n算法描述：算法描述：n     (1) 将要求证的目标（称为假设）构成一个假设集；将要求证的目标（称为假设）构成一个假设集；n     (2) 从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行则该假设成立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该；若该假设不在数据库中，则执行下一步；假设不在数据库中，则执行下一步；n     (3) 检查该假设是否可由知识库的某个知识导出，若不能由某个知识导检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转(5)；若；若能由某个知识导出，则执行下一步；能由某个知识导出，则执行下一步；n    (4) 将知识库中可以导出该假设的所有知识构成一个可用知识集；将知识库中可以导出该假设的所有知识构成一个可用知识集；n    (5) 检查可用知识集是否为空，若是，失败退出；否则执行下一步；检查可用知识集是否为空，若是，失败退出；否则执行下一步；n    (6) 按冲突消解策略从可用知识集中取出一个知识，继续；按冲突消解策略从可用知识集中取出一个知识，继续；n    (7) 将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。

 n   其流程图如下：其流程图如下：初始化初始化DB和假设集和假设集该假设是该假设是DB中的事实吗？中的事实吗？该假设能被该假设能被KB中中的知识导出吗？的知识导出吗？从假设集中取出一个假设从假设集中取出一个假设可用知识集空吗？可用知识集空吗？按照冲突消解策略从该按照冲突消解策略从该知识知识集中选出一条知识集中选出一条知识将该知识前提中的每个子条将该知识前提中的每个子条件作为新的假设加入假设集件作为新的假设加入假设集该假设成立该假设成立并放入并放入DB还有新的假设吗？还有新的假设吗？失败退出失败退出成功退出成功退出YNYYNNNNY将将KB中所有能导出此假设中所有能导出此假设的的知识构成一个可用知识集知识构成一个可用知识集 询问用户有询问用户有此事实吗？此事实吗？该假设该假设 成立成立Y4.1.5  逆向推理逆向推理推理例子推理例子n对上例，采用逆向推理，其推理过程如下：对上例，采用逆向推理，其推理过程如下： n      推理开始前，综合数据库和假设集均为空推理开始前，综合数据库和假设集均为空n      推理开始后，先将初始证据推理开始后，先将初始证据A和目标和目标C分别放入综合数据库和假设集，然分别放入综合数据库和假设集，然后从假设集中取出一个假设后从假设集中取出一个假设C，查找，查找C是否为综合数据库中的已知事实，回是否为综合数据库中的已知事实，回答为答为“N”。

n      再检查再检查C是否能被知识库中的知识所导出，发现是否能被知识库中的知识所导出，发现C可由可由r1导出，于是导出，于是r1被被放入可用知识集由于知识库中只有放入可用知识集由于知识库中只有r1可用，故可用知识集中仅含可用，故可用知识集中仅含r1n      接着从可用知识集中取出接着从可用知识集中取出r1，将其前提条件，将其前提条件B作为新的假设放入假设集作为新的假设放入假设集从假设集中取出从假设集中取出B，检查，检查B是否为综合数据库中的实事，回答为是否为综合数据库中的实事，回答为“N”再检查查B是否能被知识库中的知识所导出，发现是否能被知识库中的知识所导出，发现B可由可由r2导出，于是导出，于是r2被放入可用被放入可用知识集由于知识库中只有知识集由于知识库中只有r2可用，故可用知识集中仅含可用，故可用知识集中仅含r2n      从可用知识集中取出从可用知识集中取出r2，将其前提条件，将其前提条件A作为新的假设放入假设集然后作为新的假设放入假设集然后从假设集中取出从假设集中取出A，检查，检查A是否为综合数据库中的实事，回答为是否为综合数据库中的实事，回答为“Y”n      他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。

得证 4.1.5  逆向推理逆向推理优缺点优缺点n逆向推理的主要优点逆向推理的主要优点n 不必寻找和使用那些与假设目标无关的信息和知识不必寻找和使用那些与假设目标无关的信息和知识n 推理过程的目标明确推理过程的目标明确n 也也有有利利于于向向用用户户提提供供解解释释，，在在诊诊断断性性专专家家系系统统中中较较为为有效n逆向推理的主要缺点逆向推理的主要缺点n 当当用用户户对对解解的的情情况况认认识识不不请请时时，，由由系系统统自自主主选选择择假假设设目目标标的的盲盲目目性性比比较较大大，，若若选选择择不不好好，，可可能能需需要要多多次次提提出出假假设，会影响系统效率设，会影响系统效率4.1.6  混合推理混合推理n混合推理的概念混合推理的概念n     把正向推理和逆向推理结合起来所进行的推理称为混合推理是把正向推理和逆向推理结合起来所进行的推理称为混合推理是一种解决较复杂问题的方法一种解决较复杂问题的方法n混合推理的方法混合推理的方法n     1. 先正向后逆向先正向后逆向n     这种方法先进行正向推理，从已知事实出发推出部分结果，然后这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。

再用逆向推理对这些结果进行证实或提高它们的可信度 n     2. 先逆向后正向先逆向后正向n     这种方法先进行逆向推理，从假设目标出发推出一些中间假设，这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实然后再用正向推理对这些中间假设进行证实 n     3.  双向混合双向混合n     是指正向推理和逆向推理同时进行，使推理过程在中间的某一步是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来结合起来n     对于这些方法我不再详细讨论对于这些方法我不再详细讨论第4章 确定性推理 n4.1  推理的基本概念推理的基本概念n4.2  推理的逻辑基础推理的逻辑基础n4.3  自然演绎推理自然演绎推理n4.4  归结演绎推理归结演绎推理4.2  推理的逻辑基础推理的逻辑基础n4.2.1  谓词公式的解释谓词公式的解释n4.2.2  谓词公式的永真性和可满足性谓词公式的永真性和可满足性n4.2.3  谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性n4.2.4  谓词公式的范式谓词公式的范式n4.2.5  置换与合一置换与合一4.2.1  谓词公式的解释谓词公式的解释概念概念n命题公式的解释命题公式的解释n    在命题逻辑中，在命题逻辑中，命题公式的一个解释就是对该命题公式中各命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。

个命题变元的一次真值指派n    有了命题公式的解释，就可据此求出该命题公式的真值有了命题公式的解释，就可据此求出该命题公式的真值n谓词公式的解释谓词公式的解释n      由于谓词公式中可能包含由个体由于谓词公式中可能包含由个体常量、变元或函数常量、变元或函数，因此，，因此，必须先考虑这些个体常量和函数在个体域上的取值，然后才能必须先考虑这些个体常量和函数在个体域上的取值，然后才能根据它们的具体取值为谓词分别指派真值根据它们的具体取值为谓词分别指派真值n      定义定义4.1 设设D是谓词公式是谓词公式P的非空个体域，若对的非空个体域，若对P中的个体常中的个体常量、函数和谓词按如下规定赋值：量、函数和谓词按如下规定赋值：n     (1) 为每个个体常量指派为每个个体常量指派D中的一个元素；中的一个元素；n     (2) 为每个为每个n元函数指派一个从元函数指派一个从Dn到到D的一个映射，其中的一个映射，其中n            Dn ={(x1, x2, …, xn)| x1, x2, …, xn∈∈D}n    (3) 为每个为每个n元谓词指派一个从元谓词指派一个从Dn到到{F，，T}的映射。

的映射n则称这些指派为则称这些指派为P在在D上的一个解释上的一个解释I 4.2.1  谓词公式的解释谓词公式的解释 例子一例子一(1/2)n      例例4.2 设个体域设个体域D={1, 2}，求公式，求公式A=(∀∀x)(   y)P(x, y)在在D上的上的解释，并指出在每一种解释下公式解释，并指出在每一种解释下公式A的真值 n      解：解：由于公式由于公式A中没有包含个体常量和函数，故可直接为谓词中没有包含个体常量和函数，故可直接为谓词指派真值，设有指派真值，设有n这就是公式这就是公式A 在在D 上的一个解释从这个解释可以看出：上的一个解释从这个解释可以看出：n      当当x=1、、y=1时，有时，有P(x,y)的真值为的真值为T;n      当当x=2、、y=1时，有时，有P(x,y)的真值为的真值为T;n      即对即对x在在D上的任意取值，都存在上的任意取值，都存在y=1使使P(x,y)的真值为的真值为T因此，在此解释下公式此，在此解释下公式A的真值为的真值为T       P(1,1) P(1,2) P(2,1) P(2,2) T F T F4.2.1  谓词公式的解释谓词公式的解释 例子一例子一(2/2)n说明：说明：一个谓词公式在其个体域上的解释不是唯一的。

例如，对一个谓词公式在其个体域上的解释不是唯一的例如，对公式公式A，若给出另一组真值指派，若给出另一组真值指派n这也是公式这也是公式A 在在D 上的一个解释从这个解释可以看出：上的一个解释从这个解释可以看出：n      当当x=1、、y=1时，有时，有P(x,y)的真值为的真值为T;n      当当x=2、、y=1时，有时，有P(x,y)的真值为的真值为F;n即对即对x在在D上的任意取值，不存在一个上的任意取值，不存在一个y使得使得P(x,y)的真值为的真值为T因此，在此解释下公式此，在此解释下公式A的真值为的真值为Fn     实际上，实际上，A在在D上共有上共有16种解释，这里就不在一一列举种解释，这里就不在一一列举 P(1,1) P(1,2) P(2,1) P(2,2) TT F F4.2.1  谓词公式的解释谓词公式的解释 例子二例子二n      例例4.3 设个体域设个体域D={1, 2}，求公式，求公式B=(∀∀x)P(f(x), a)在在D上的解释，并指出在上的解释，并指出在该解释下公式该解释下公式B的真值n    解：解：设对个体常量设对个体常量a和函数和函数f(x)的值指派为：的值指派为：n对谓词的真值指派为：对谓词的真值指派为：n    由于已指派由于已指派a=1，因此，因此P(1,2)和和P(2,2)不可能出现，故没给它们指派真值。

不可能出现，故没给它们指派真值n    上述指派是公式上述指派是公式B在在D上的一个解释在此解释下有上的一个解释在此解释下有n         当当x=1时，时，a=1使使P(1,1)=Tn         当当x=2时，时，a=1 使使P(2,1)=Tn即对即对x在在D上的任意取值，都存在上的任意取值，都存在a=1使使P(f(x), a)的真值为的真值为T因此，在此解释因此，在此解释下公式下公式B的真值为的真值为Tn     由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为可能在某一个解释下真值为T，而在另一个解释下为，而在另一个解释下为Faf(1)F(2)112P(1,1))P(1,2)P(2,1)P(2,2)T ×T×4.2.2  谓词公式的永真性和可满足性谓词公式的永真性和可满足性n     为了以后推理的需要，下面先定义：为了以后推理的需要，下面先定义：n     定义定义4.2  如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释都取得上的任一解释都取得真值真值T，则称，则称P在在D 上是永真上是永真的；如果的；如果P在任何非空个体域上均是在任何非空个体域上均是永真的，则称永真的，则称P永真永真。

n    可见，要判定一谓词公式为永真，必须对每个非空个体域上的可见，要判定一谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断当解释的个数为有限时，尽管工作量大，每个解释逐一进行判断当解释的个数为有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就很难判定了性就很难判定了n     定义定义4.3  对于谓词公式对于谓词公式P，如果至少存在，如果至少存在D上的一个解释，使上的一个解释，使公式公式P在此解释下的真值为在此解释下的真值为T，则称公式，则称公式P在在D上是可满足上是可满足的n谓词公式的谓词公式的可满足性也称为相容性可满足性也称为相容性n     定义定义4.4  如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释都取真上的任一解释都取真值值F，则称，则称P在在D上是永假上是永假的；如果的；如果P在任何非空个体域上均是永在任何非空个体域上均是永假的，则称假的，则称P永假永假n    谓词公式的永假性又称谓词公式的永假性又称不可满足性或不相容不可满足性或不相容n    后面我们要给出的归结推理，就是采用一种逻辑上的反证法，后面我们要给出的归结推理，就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。

将永真性转换为不可满足性的证明4.2.3  谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性1. 等价式等价式(1/2)n      谓词公式的谓词公式的等价性等价性和和永真蕴含性永真蕴含性可分别用相应的可分别用相应的等价式等价式和和永真蕴含式永真蕴含式来表示，这些等价式和永真蕴含来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规式都是演绎推理的主要依据，因此也称它们为推理规则n      谓词公式的谓词公式的等价式可定义如下等价式可定义如下：：n      定义定义4.5 设设P与与Q是是D上的两个谓词公式，若对上的两个谓词公式，若对D上上的任意解释，的任意解释，P与与Q都有相同的真值，则称都有相同的真值，则称P与与Q在在D 上是等价的如果上是等价的如果D是任意非空个体域，则称是任意非空个体域，则称P与与Q是等价的，记作是等价的，记作P⇔⇔Q 4.2.3  谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性 1. 等价式等价式(2/2)n(1) 双重否定律双重否定律       ¬ ¬ P ⇔⇔ Pn(2) 交换律交换律               (P∨∨Q) ⇔⇔ (Q∨∨P)，， ( P∧∧Q) ⇔⇔ ( Q∧∧P)n(3) 结合律结合律               (P∨∨Q)∨∨R ⇔⇔ P∨∨(Q∨∨R) n                                 (P∧∧Q)∧∧R ⇔⇔ P∧∧(Q∧∧R)n(4) 分配律分配律               P∨∨(Q∧∧R) ⇔⇔ (P∨∨Q)∧∧(P∨∨R)n                                 P∧∧(Q∨∨R) ⇔⇔ (P∧∧Q)∨∨(P∧∧R)n(5) 摩根定律摩根定律      ¬ (P∨∨Q) ⇔⇔ P∧∧Qn                                 ¬ (P∧∧Q) ⇔⇔ P∨∨Qn(6) 吸收律吸收律               P∨∨(P∧∧Q) ⇔⇔ P    n                                 P∧∧(P∨∨Q) ⇔⇔ Pn(7) 补余律补余律               P∨∨P ⇔⇔ T,   P∧∧P ⇔⇔ F n(8) 连词化归律连词化归律       P→Q ⇔⇔ ¬P∨∨Qn                                 P↔Q ⇔⇔ (P→Q)∧∧(Q→P)n                                 P↔Q ⇔⇔ (P∧∧Q)∨∨(Q∧∧P)n(9) 量词转换律量词转换律      ¬ (∃∃x)P ⇔⇔ (∀∀x)( ¬ P)n                                ¬ (∀∀x)P ⇔⇔ (∃∃x) (¬ P)n(10) 量词分配律量词分配律    (∀∀x) (P∧∧Q) ⇔⇔ (∀∀x)P∧∧(∀∀x)Qn                                (∃∃x) (P∨∨Q) ⇔⇔ (∃∃x)P∨∨(∃∃x)Q4.2.3  谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性2. 永真蕴含式永真蕴含式n      定义定义4.6  对谓词公式对谓词公式P和和Q，如果，如果P→Q永真，则称永真，则称P 永真蕴含永真蕴含Q，且称，且称Q为为P的逻辑结论，的逻辑结论，P为为Q的前提，记作的前提，记作P ⇒⇒ Q。

n     常用的永真蕴含式如下：常用的永真蕴含式如下：n      (1) 化简式化简式     P∧∧Q ⇒⇒ P，，  P∧∧Q ⇒⇒ Qn      (2) 附加式附加式     P ⇒⇒ P∨∨Q，，  Q ⇒⇒ P∨∨Qn      (3) 析取三段论析取三段论    ﹁﹁ P,  P∨∨Q ⇒⇒ Qn      (4) 假言推理假言推理        P,  P→Q ⇒⇒ Qn      (5) 拒取式拒取式            ¬Q,  P→Q ⇒⇒ Pn      (6) 假言三段论假言三段论     P→Q,  Q→R ⇒⇒P→Rn      (7) 二难推理二难推理        P∨∨Q,  P→R,  Q→R ⇒⇒ R n      (8) 全称固化全称固化        (∀∀x)P(x) ⇒⇒ P(y)n     其中，其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词是个体域中的任一个体，依此可消去谓词公式中的全称量词n     (9) 存在固化存在固化         (∃∃x)P(x) ⇒⇒ P(y)n     其中，其中，y是个体域中某一个可以使是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中为真的个体，依此可消去谓词公式中的存在量词。

的存在量词4.2.4  谓词公式的范式谓词公式的范式n      范式是谓词公式的标准形式在谓词逻辑中，范式分为两种：范式是谓词公式的标准形式在谓词逻辑中，范式分为两种：n前束范式前束范式n      定义定义4.7  设设F为一谓词公式，如果其中的所有量词均非否定地出现在公式为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称的最前面，且它们的辖域为整个公式，则称F为前束范式一般形式：为前束范式一般形式：n        (Q1x1)……(Qnxn)M(x1,x2,……,xn)n其中，其中，Qi(i=1,2,……,n)为前缀，它是一个由全称量词或存在量词组成的量词为前缀，它是一个由全称量词或存在量词组成的量词串；串； M(x1,x2,……,xn)为母式，它是一个不含任何量词的谓词公式为母式，它是一个不含任何量词的谓词公式n      例如例如，，(∀∀x) (∀∀y) (∃∃z)(P(x)∧∧Q(y,z)∨∨R(x,z))是前束范式是前束范式n      任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集的化简中讨论。

集的化简中讨论nSkolem范式范式n      定义定义4.8 如果前束范式中如果前束范式中所有的存在量词都在全称量词之前所有的存在量词都在全称量词之前，则称这种形，则称这种形式的谓词公式为式的谓词公式为Skolem范式n      例如例如，，(∃∃x) (∃∃z) (∀∀y)(P(x)∨∨Q(y,z)∧∧R(x,z))是是Skolem范式n      任一谓词公式均可化为与其对应的任一谓词公式均可化为与其对应的Skolem范式，其化简方法也将在后面范式，其化简方法也将在后面子句集的化简中讨论子句集的化简中讨论4.2.5  置换与合一置换与合一概念n     在不同谓词公式中，往往会出现谓词名相同但其个体不在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理过程是不能直接进行匹配的，需要先同的情况，此时推理过程是不能直接进行匹配的，需要先进行置换进行置换n      例如，可根据例如，可根据全称固化全称固化推理和推理和假言推理假言推理由谓词公式由谓词公式n        W1(A) 和和 (∀∀x)(W1(x)→W2(x))n推出推出W2(A)对谓词W1(A)可看作是由全程固化推理（即可看作是由全程固化推理（即(∀∀x)(W1(x) ⇒⇒ W1(A))推出的，其中推出的，其中A是任一个体常量。

要使用是任一个体常量要使用假言推理，首先需要找到项假言推理，首先需要找到项A对变元对变元x的的置换置换，使，使W1(A)与与W1(x)一致n     这种寻找项对变元的置换，使谓词一致的过程叫做这种寻找项对变元的置换，使谓词一致的过程叫做合一合一的过程的过程n     下面讨论置换与合一的有关概念与方法下面讨论置换与合一的有关概念与方法4.2.5  置换与合一置换与合一1. 置换置换(1/2)n    置换可简单的理解为是在一个谓词公式中用置换项去替换变量置换可简单的理解为是在一个谓词公式中用置换项去替换变量n    定义定义4.9 置换是形如置换是形如n            {t1/x1,t2/x2,…,tn/xn}n的有限集合其中，的有限集合其中，t1,t2,…,tn是项；是项；x1,x2,…,xn是互不相同的变元；是互不相同的变元；ti/xi表示用表示用ti替换替换xi并且要求并且要求ti与与xi不能相同，不能相同，xi不能循环地出现在另一个不能循环地出现在另一个ti中n    例如，例如， {a/x, c/y, f(b)/z} 是一个置换是一个置换n    但但{g(y)/x, f(x)/y}不是一个置换。

原因是它在不是一个置换原因是它在x与与y之间出现了循环置换现象之间出现了循环置换现象即当用即当用g(y)置换置换x,用用f(g(y))置换置换y时，既没有消去时，既没有消去x，也没有消去，也没有消去yn    若改为若改为{g(a)/x, f(x)/y}即可，原因是用即可，原因是用g(a)置换置换x ，用，用f(g(a))置换置换y ，则消去了，则消去了x和和yn     通常，置换是用希腊字母通常，置换是用希腊字母θ、、σ、、 α、、 λ等来表示的等来表示的n     定义定义4.10  设设θ={t1/x1,t2/x2,…,tn/xn}是一个置换，是一个置换，F是一个谓词公式，把公式是一个谓词公式，把公式F中出现的所有中出现的所有xi换成换成ti(i=1,2,…,n)，得到一个新的公式，得到一个新的公式G，称，称G为为F在置换在置换θ下的下的例示例示，记作，记作G=Fθn      一个谓词公式的任何例示都是该公式的逻辑结论一个谓词公式的任何例示都是该公式的逻辑结论4.2.5  置换与合一置换与合一1. 置换置换(2/2)n定义定义4.11 设设n       θ={t1/x1,t2/x2,…,tn/xn}n       λ={ u1/y1, u2/y2, … , um/ym }n是两个置换。

则是两个置换则θ与与λ的合成也是一个置换，记作的合成也是一个置换，记作θ°λ它是从集合它是从集合n         { t1λ/x1, t2λ/x2, … , tnλ/xn,  u1/y1, u2/y2, … , um/ym }n中删去以下两种元素中删去以下两种元素n      ①① 当当tiλ=xi时，删去时，删去tiλ/xi (i=1, 2 ,…, n)；；n      ②② 当当yj∈∈{ x1, x2 ,…, xn }时，删去时，删去uj/yj (j=1, 2 ,…, m)n最后剩下的元素所构成的集合最后剩下的元素所构成的集合n     例例4.4 设设θ={ f(y)/x, z/y }，，λ={a/x, b/y ,y/z }，求，求θ与与λ的合成n     解解:先求出集合先求出集合n        {f(b/y)/x, (y/z)/y, a/x, b/y , y/z}={f(b)/x, y/y, a/x, b/y , y/z}n其中，其中，f(b)/x中的中的f(b)是置换是置换λ作用于作用于f(y)的结果；的结果；y/y 中的中的y是置换是置换λ作用于作用于z的结的结果在该集合中，果。

在该集合中，y/y满足定义中的条件满足定义中的条件①①，需要删除；，需要删除；a/x和和b/y满足定义中的满足定义中的条件条件②②，也需要删除最后得，也需要删除最后得n        θ°λ={f(b)/x, y/z}4.2.5  置换与合一置换与合一2. 合一合一n     合一合一可理解为可理解为是寻找项对变量的置换，使两个谓词公式一致是寻找项对变量的置换，使两个谓词公式一致可定义为：可定义为：n     定义定义4.12 设有公式集设有公式集F={F1, F2,…,Fn}，若存在一个置换，若存在一个置换θ，可使，可使n                  F1θ=F2θ=…=Fnθ，，n则称则称θ是是F的一个合一称的一个合一称F1,F2,…,Fn是可合一的是可合一的n       例如，例如，设有公式集设有公式集F={P(x,y,f(y)), P(a,g(x),z)}，则，则n              λ={a/x, g(a)/y, f(g(a))/z}n是它的一个合一是它的一个合一n      一般来说，一个公式集的合一不是唯一的一般来说，一个公式集的合一不是唯一的n      定义定义4.13 设设σ是公式集是公式集F的一个合一，如果对的一个合一，如果对F的任一个合一的任一个合一θ都存在一都存在一个置换个置换λ，使得，使得θ=σ°λ，则称，则称σ是一个最一般合一。

是一个最一般合一n      一个公式集的最一般合一是唯一的一个公式集的最一般合一是唯一的n      对如何求取最一般合一的问题，不再讨论对如何求取最一般合一的问题，不再讨论第第4章章 确定性推理确定性推理 n4.1  推理的基本概念推理的基本概念n4.2  推理的逻辑基础推理的逻辑基础n4.3  自然演绎推理自然演绎推理n4.4  归结演绎推理归结演绎推理4.3  自然演绎推理自然演绎推理n     自然演绎推理自然演绎推理n     从一组已知为真的事实出发，直接运用经典逻辑中的推理规从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理则推出结论的过程称为自然演绎推理n    自然演绎推理最基本的推理规则是三段论推理，它包括：自然演绎推理最基本的推理规则是三段论推理，它包括：n        假言推理假言推理         P,  P→Q ⇒⇒ Qn        拒取式拒取式            ﹁﹁ Q,  P→Q ⇒⇒ Pn        假言三段论假言三段论     P→Q,  Q→R ⇒⇒ P→Rn   自然演绎推理的例子自然演绎推理的例子n      例例4.5 设已知如下事实：设已知如下事实：n          A,  B,  A→C,  B∧∧C→D,  D→Qn 求证：求证：Q为真。

为真n      证明：证明：因为因为  A, A→C⇒⇒ C          假言推理假言推理n                 B,  C⇒⇒ B∧∧C                    引入合取词引入合取词 n                 B∧∧C，，B∧∧C→D ⇒⇒ D    假言推理假言推理n                 D,  D→Q ⇒⇒ Q                  假言推理假言推理n因此，因此，Q为真为真4.3  自然演绎推理自然演绎推理n    例例4.6 设已知如下事实：设已知如下事实：n    (1) 只要是需要编程序的课，王程都喜欢只要是需要编程序的课，王程都喜欢n    (2) 所有的程序设计语言课都是需要编程序的课所有的程序设计语言课都是需要编程序的课n    (3) C是一门程序设计语言课是一门程序设计语言课n求证：王程喜欢求证：王程喜欢C这门课n    证明：证明：首先定义谓词首先定义谓词n        Prog(x)       x是需要编程序的课是需要编程序的课n        Like(x, y)    x喜欢喜欢yn        Lang(x)       x是一门程序设计语言课是一门程序设计语言课n把已知事实及待求解问题用谓词公式表示如下：把已知事实及待求解问题用谓词公式表示如下：n        Prog(x)→Like(Wang , x)n        (∀∀x)( Lang(x)→Prog(x))n        Lang(C)n应用推理规则进行推理：应用推理规则进行推理：n    Lang(y)→Prog(y)                           全称固化全称固化n    Lang(C)，，Lang(y)→Prog(y) ⇒⇒ Prog(C)   假言推理假言推理  {C/y}n    Prog(C),  Prog(x)→Like(Wang , x) ⇒⇒ Like(Wang , C)  假言推理假言推理  {C/x}n因此，王程喜欢因此，王程喜欢C这门课。

这门课    4.3  自然演绎推理自然演绎推理n     优点：优点：定理证明过程自然，易于理解，并且有丰定理证明过程自然，易于理解，并且有丰富的推理规则可用富的推理规则可用n     缺点：缺点：是容易产生知识爆炸，推理过程中得到的是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现理不利，甚至难以实现 第第4章章 确定性推理确定性推理 n4.1  推理的基本概念推理的基本概念n4.2  推理的逻辑基础推理的逻辑基础n4.3  自然演绎推理自然演绎推理n4.4  归结演绎推理归结演绎推理4.4  归结演绎推理归结演绎推理n    归结演绎推理是一种基于鲁宾逊（归结演绎推理是一种基于鲁宾逊（Robinson）归结原理的机器推理）归结原理的机器推理技术鲁宾逊归结原理亦称为消解原理，是鲁宾逊于技术鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦年在海伯伦（（Herbrand）理论的基础上提出的一种基于逻辑的）理论的基础上提出的一种基于逻辑的“反证法反证法”n     在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。

在人工智能中，几乎所有的问题都可以转化为一个定理证明问题定理证明的实质定理证明的实质，就是要对前提，就是要对前提P和结论和结论Q，证明，证明P→Q永真n    由由4.2节可知，要证明节可知，要证明P→Q永真，就是要证明永真，就是要证明P→Q在任何一个非空在任何一个非空的个体域上都是永真的这将是非常困难的，甚至是不可实现的的个体域上都是永真的这将是非常困难的，甚至是不可实现的n    为此，人们进行了大量的探索，后来发现可以为此，人们进行了大量的探索，后来发现可以采用反证法的思想采用反证法的思想，，把关于把关于永真性的证明转化为关于不可满足性的证明永真性的证明转化为关于不可满足性的证明n    即要证明即要证明P→Q永真，只要能够证明永真，只要能够证明P∧∧﹁﹁Q是不可满足的就可以了是不可满足的就可以了(原因是原因是﹁﹁ (P→Q) ⇔⇔ ﹁﹁(﹁﹁ P∨∨Q) ⇔⇔ P∧∧﹁﹁ Q n    这方面最有成效的工作就是鲁宾逊归结原理它使定理证明的机械这方面最有成效的工作就是鲁宾逊归结原理它使定理证明的机械化成为现实化成为现实4.4  归结演绎推理归结演绎推理n4.4.1 子句集及其化简子句集及其化简n4.4.2 鲁滨逊归结原理鲁滨逊归结原理n4.4.3 归结反演推理的归结策略归结反演推理的归结策略n4.4.4 用归结反演求取问题的答案用归结反演求取问题的答案4.4.1  子句集及其化简子句集及其化简1. 子句和子句集子句和子句集n概念。

概念n子句和子句集子句和子句集n     定义定义4.14 原子谓词公式及其否定统称为原子谓词公式及其否定统称为文字文字     例如，例如，P(x)、、Q(x)、、﹁﹁ P(x)、、 ﹁﹁ Q(x)等都是文字等都是文字n     定义定义4.15 任何文字的析取式称为任何文字的析取式称为子句子句     例如，例如，P(x)∨∨Q(x)，，P(x，，f(x))∨∨Q(x，，g(x))都是子句都是子句n     定义定义4.16 不含任何文字的子句称为不含任何文字的子句称为空子句空子句        空子句是永假的，不可满足的记为空子句是永假的，不可满足的记为□或或NILn     定义定义4.17 由子句或空子句所构成的集合称为由子句或空子句所构成的集合称为子句集子句集4.4.1  子句集及其化简子句集及其化简2. 子句集的化简（子句集的化简（1/6））n化简步骤如下：化简步骤如下：n     (1) 消去连接词消去连接词“→”和和“↔”n等价公式：等价公式：             P→Q ⇔⇔﹁﹁ P∨∨Q              P↔Q ⇔⇔ (P∧∧Q)∨∨(﹁﹁P∧∧﹁﹁Q)n     例如公式例如公式         (∀∀x)((∀∀y)P(x,y)→﹁﹁ (∀∀y)(Q(x,y)→R(x,y)))经等价变化后为经等价变化后为        (∀∀x)(﹁﹁(∀∀y)P(x,y)∨∨﹁﹁ (∀∀y)(﹁﹁Q(x,y)∨∨R(x,y)))4.4.1  子句集及其化简子句集及其化简2. 子句集的化简（子句集的化简（2/6））n(2) 减少否定符号的辖域减少否定符号的辖域n双重否定率双重否定率    ﹁﹁(﹁﹁P) ⇔⇔ Pn摩根定律摩根定律       ﹁﹁(P∧∧Q) ⇔⇔﹁﹁P∨∨﹁﹁Q       ﹁﹁(P∨∨Q) ⇔⇔﹁﹁P∧∧﹁﹁Qn量词转换率量词转换率       ﹁﹁ (∀∀x)P(x) ⇔⇔ (∃∃x) ﹁﹁P(x)       ﹁﹁ (∃∃x)P(x) ⇔⇔ (∀∀x)￢￢P(x)n将每个否定符号将每个否定符号“﹁﹁”移到仅靠谓词的位置，使得每个否定移到仅靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。

符号最多只作用于一个谓词上n   例如，例如，上式经等价变换后为上式经等价变换后为        (∀∀x)((∃∃y)﹁﹁P(x，，y)∨∨(∃∃y)( Q(x，，y) ∧∧﹁﹁R(x，，y)))4.4.1  子句集及其化简子句集及其化简2. 子句集的化简（子句集的化简（3/6））n    (3) 对变元标准化对变元标准化n     在一个量词的辖域内，把谓词公式中受该量词约束的变元在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字束的变元有不同的名字n     例如，上式经变换后为例如，上式经变换后为       (∀∀x)((∃∃y)﹁﹁P(x，，y)∨∨(∃∃z)( Q(x，，z) ∧∧﹁﹁R(x，，z)))n     (4) 化为前束范式化为前束范式n把所有量词都移到公式的左边，并且在移动时把所有量词都移到公式的左边，并且在移动时不能改变其相不能改变其相对顺序对顺序n      例如，上式化为前束范式后为例如，上式化为前束范式后为        (∀∀x)(∃∃y) (∃∃z)(﹁﹁P(x，，y)∨∨( Q(x，，z) ∧∧﹁﹁R(x，，z)))4.4.1  子句集及其化简子句集及其化简2. 子句集的化简（子句集的化简（4/6））n    (5) 消去存在量词消去存在量词n     1.存在量词不出现在全称量词的辖域内存在量词不出现在全称量词的辖域内n     2. 存在量词位于一个或多个全称量词的辖域内存在量词位于一个或多个全称量词的辖域内，例如，例如                   (∀∀x1)…(∀∀xn) (∃∃y)P(x1，，x2 ,…, xn ,y)           需要用需要用Skolem函数函数f(x1，，x2 ,…, xn)替换受该存在量词约替换受该存在量词约束的变元束的变元y，然后再消去该存在量词。

然后再消去该存在量词n上公式替换后的式子为上公式替换后的式子为               (∀∀x)(﹁﹁P(x,f(x))∨∨(Q(x,g(x))∧∧﹁﹁R(x,g(x))))4.4.1  子句集及其化简子句集及其化简2. 子句集的化简（子句集的化简（5/6））n     (6) 化为化为Skolem标准形标准形n     Skolem标准形的一般形式为标准形的一般形式为     (∀∀x1)…(∀∀xn) M(x1,x2,……,xn)其中，其中， M(x1,x2,……,xn)是是Skolem标准形的母式，它由子句的标准形的母式，它由子句的合取所构成合取所构成n    把谓词公式化为把谓词公式化为Skolem标准形需要使用以下等价关系标准形需要使用以下等价关系        P∨∨(Q∧∧R) ⇔⇔ (P∨∨Q)∧∧(P∨∨R)n例如，前面的公式化为例如，前面的公式化为Skolem标准形后为标准形后为     (∀∀x)((﹁﹁P(x,f(x))∨∨Q(x,g(x))∧∧(﹁﹁P(x,f(x))∨∨﹁﹁R(x,g(x))))4.4.1  子句集及其化简子句集及其化简2. 子句集的化简（子句集的化简（5/6））n     (7) 消去全称量词消去全称量词n例如，上式消去全称量词后为例如，上式消去全称量词后为          (﹁﹁P(x,f(x))∨∨Q(x,g(x)) ∧∧(﹁﹁P(x,f(x))∨∨﹁﹁R(x,g(x)))n (8) 消去合取词消去合取词n    在母式中消去所有合取词，把母式用子句集的形式在母式中消去所有合取词，把母式用子句集的形式表示出来。

其中，子句集中的每一个元素都是一个子表示出来其中，子句集中的每一个元素都是一个子句n    例如，例如，上式的子句集中包含以下两个子句上式的子句集中包含以下两个子句        ﹁﹁P(x,f(x))∨∨Q(x,g(x))        ﹁﹁P(x,f(x))∨∨﹁﹁R(x,g(x))4.4.1  子句集及其化简子句集及其化简2. 子句集的化简（子句集的化简（6/6））n    (9) 更换变量名称更换变量名称n    对子句集中的某些变量重新命名，使任意两个子句中对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名不出现相同的变量名n    例如，例如，        ﹁﹁P(x,f(x))∨∨Q(x,g(x))        ﹁﹁P(y,f(y))∨∨﹁﹁R(y,g(y))4.4.1  子句集及其化简子句集及其化简3. 子句集的应用（子句集的应用（1/4））n定理定理4.1 Q为为P1,P2,……Pn的逻辑结论，当且仅当的逻辑结论，当且仅当     (P1 ∧∧P2 ∧∧……Pn) ∧∧ ﹁﹁ Q是不可满足的是不可满足的n由于在消去存在量词时所用的由于在消去存在量词时所用的Skolem函数可以不同，函数可以不同，因此因此化简后的标准子句集是不唯一的化简后的标准子句集是不唯一的。

n定理定理4.2 设有谓词公式设有谓词公式F，其标准子句集为，其标准子句集为S，则，则F为为不可满足的充要条件是不可满足的充要条件是S为不可满足的为不可满足的4.4.2 鲁滨逊归结原理鲁滨逊归结原理1. 基本思想基本思想n两个关键两个关键n 第一，第一，子句集中的子句之间是合取关系因此，子句子句集中的子句之间是合取关系因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可集中只要有一个子句为不可满足，则整个子句集就是不可满足的；满足的；n 第二，第二，空子句是不可满足的因此，一个子句集中如空子句是不可满足的因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的果包含有空子句，则此子句集就一定是不可满足的4.4.2 鲁滨逊归结原理鲁滨逊归结原理n鲁滨逊归结原理基本思想鲁滨逊归结原理基本思想n 1.把欲证明问题的结论否定，并加入子句集，得把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集到一个扩充的子句集S'n 2.设法检验子句集设法检验子句集S'是否含有空子句，若含有空子是否含有空子句，若含有空子句，则表明句，则表明S'是不可满足的；若不含有空子句，则是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。

归结，直至导出空子句或不能继续归结为止 n 鲁滨逊归结原理包括鲁滨逊归结原理包括n 命题逻辑归结原理命题逻辑归结原理n 谓词逻辑归结原理谓词逻辑归结原理4.4.2 鲁滨逊归结原理鲁滨逊归结原理2. 命题逻辑的归结（命题逻辑的归结（1/8））n 归结推理的核心是求两个子句的归结式归结推理的核心是求两个子句的归结式n     (1) 归结式的定义及性质归结式的定义及性质n    定义定义4.15 若若P是原子谓词公式，则称是原子谓词公式，则称P与与﹁﹁P为为互补文字互补文字n     定义定义4.16 设设C1和和C2是子句集中的任意两个子句，如果是子句集中的任意两个子句，如果C1中的文字中的文字L1与与C2中的文字中的文字L2互补，那么可从互补，那么可从C1和和C2中中分别消去分别消去L1和和L2，并将，并将C1和和C2中余下的部分按析取关系中余下的部分按析取关系构成一个新的子句构成一个新的子句C12，则称这一过程为，则称这一过程为归结归结，称，称C12为为C1和和C2的的归结式归结式，称，称C1和和C2为为C12的的亲本子句亲本子句4.4.2 鲁滨逊归结原理鲁滨逊归结原理2. 命题逻辑的归结命题逻辑的归结n例例   设设C1=P∨∨Q∨∨R，，C2=﹁﹁P∨∨S，求，求C1和和C2的归结式的归结式C12。

     解：解：这里这里L1=P，，L2=﹁﹁P，通过归结可以得到，通过归结可以得到             C12= Q∨∨R∨∨Sn     例例4.4 设设C1=﹁﹁Q，，C2=Q，求，求C1和和C2的归结式的归结式C12     解：解：这里这里L1=﹁﹁Q，，L2=Q，通过归结可以得到，通过归结可以得到             C12= NIL4.4.2 鲁滨逊归结原理鲁滨逊归结原理2. 命题逻辑的归结命题逻辑的归结n    例例 设设C1 =﹁P ∨∨ Q ，，C2=﹁﹁Q，，C3=P，求，求C1、、C2、、C3的归结式的归结式C123n如果改变归结顺序如果改变归结顺序，同样可，同样可以得到相同的结果，即其归以得到相同的结果，即其归结过程是不唯一的结过程是不唯一的n归结树归结树﹁P ∨ ∨ Q﹁Q﹁P P NIL﹁P ∨ ∨ Q P Q﹁Q NILn 合一合一可理解为可理解为是寻找项对变量的置换，使两个是寻找项对变量的置换，使两个谓词公式一致谓词公式一致可定义为：可定义为：n定义定义4.10 设有公式集设有公式集F={F1, F2,…,Fn}，若存在，若存在一个置换一个置换θ，可使，可使    F1θ=F2θ=…=Fnθ，，则称则称θ是是F的一个合一。

称的一个合一称F1,F2,…,Fn是可合一的是可合一的n 例如，例如，设有公式集设有公式集F={P(x,y,f(y)), P(a,g(x),z)}则则  λ={a/x, g(a)/y, f(g(a))/z}是它的一个合一是它的一个合一定理定理4.3 归结式归结式C12是其亲本子句是其亲本子句C1和和C2的逻辑结论的逻辑结论4.4.2 鲁滨逊归结原理鲁滨逊归结原理2. 命题逻辑的归结命题逻辑的归结n推论推论1：：设设C1和和C2是子句集是子句集S中的两个子句，中的两个子句，C12是是C1和和C2的归结式，若用的归结式，若用C12代替代替C1和和C2后得到新的子句集后得到新的子句集S1，则由，则由S1的不可满足性可以推出原子句集的不可满足性可以推出原子句集S的不可满足性的不可满足性n 推论推论2：：设设C1和和C2是子句集是子句集S中的两个子句，中的两个子句，C12是是C1和和C2的归结式，若把的归结式，若把C12加入加入S中中得到新的子句集得到新的子句集S2，则，则S与与S2的的不可满足性是等价的不可满足性是等价的定理定理4.44.4 子句集子句集S S是不可满足的，当且仅当存在一个从是不可满足的，当且仅当存在一个从S S到空到空子句的归结过程。

子句的归结过程 4.4.2 鲁滨逊归结原理鲁滨逊归结原理2. 命题逻辑的归结命题逻辑的归结n (2) (2) 命题逻辑的归结反演命题逻辑的归结反演 n归结原理：假设归结原理：假设F F为已知前提，为已知前提，G G为欲证明的结论，归结原为欲证明的结论，归结原理把证明理把证明G G为为F F的逻辑结论转化为证明的逻辑结论转化为证明F∧F∧﹁﹁G G为不可满足为不可满足n根据定理根据定理4.14.1，在不可满足的意义上，公式集，在不可满足的意义上，公式集F∧F∧﹁﹁G G与其与其子句集是等价的，即把公式集上的不可满足转化为子句集子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足上的不可满足4.4.2 鲁滨逊归结原理鲁滨逊归结原理2. 命题逻辑的归结命题逻辑的归结n在命题逻辑中，已知在命题逻辑中，已知F F，证明，证明G G为真的归结反演过程如下为真的归结反演过程如下：：n ① ①否定目标公式否定目标公式G G，得，得﹁﹁G;G;n ② ②把把﹁﹁G G并入到公式集并入到公式集F F中，得到中，得到{F{F，，﹁﹁G}G}；；n ③ ③把把{F{F，，﹁﹁G}G}化为子句集化为子句集S S。

n ④ ④ 应用归结原理对子句集应用归结原理对子句集S S中的子句进行归结，并把中的子句进行归结，并把每次得到的归结式并入每次得到的归结式并入S S中如此反复进行，若出现空子中如此反复进行，若出现空子句，则停止归结，此时就证明了句，则停止归结，此时就证明了G G为真n应用归结原理证明定理的过程称为归结反演应用归结原理证明定理的过程称为归结反演4.4.2 鲁鲁滨滨逊归结原理逊归结原理2. 命题逻辑的归结命题逻辑的归结n      例例4.54.5设已知的公式集为设已知的公式集为{P, (P∧∧Q)→R, (S∨∨T)→Q, T}，求证结论，求证结论Rn 解：解：假设结论假设结论R为假为假, 将将﹁﹁R加入公式加入公式集，并化为子句集集，并化为子句集n      S={P,﹁﹁P∨∨﹁﹁Q∨∨R, ﹁﹁S∨∨Q, ﹁﹁T∨∨Q, T, ﹁﹁R}﹁P ∨ ∨﹁﹁Q∨ ∨R﹁ R﹁P ∨ ∨﹁﹁QP﹁﹁Q﹁﹁T ∨ ∨Q﹁﹁TTNIL根据归结原理的完备性，可知子句集根据归结原理的完备性，可知子句集S是是不可满足的，即开始时假设不可满足的，即开始时假设﹁﹁R为真是错为真是错误的，这就证明了误的，这就证明了R为真。

为真 4.4.2 鲁鲁滨滨逊归结原理逊归结原理3. 谓词逻辑的归结谓词逻辑的归结n谓词逻辑的归结原理谓词逻辑的归结原理n      谓词逻辑中的归结式可用如下定义来描述：谓词逻辑中的归结式可用如下定义来描述：n       定义定义4.17 设设C1和和C2是两个是两个没有公共变元没有公共变元的子句，的子句，L1和和L2分别是分别是C1和和C2中的文字如果中的文字如果L1和和L2存在最一般合存在最一般合一一σ，则称，则称          C12=({C1σ}-{ L1σ})∪∪({ C2σ}-{ L2σ})    为为C1和和C2的二元归结式，而的二元归结式，而L1和和L2为归结式上的文字为归结式上的文字4.4.2 鲁滨逊归结原理鲁滨逊归结原理3. 谓词逻辑的归结谓词逻辑的归结n例例4.6 设C1=P(x)∨∨Q(a)，，C2=﹁P(b)∨∨R(x) ，，求 C12n     解：：C1和C2有相同的变元x，，不符合定义3.20先修改C2中变元x的名字为，，令C2=﹁P(b)∨∨R(y)此时L1= P(x), L2 =﹁P(b)，，L1和L2的最一般合一是σ={b/x}则有n      C12=( {C1σ}-{L1σ})∪∪ ({C2σ}-{L2σ})            =({P(b), Q(a)}-{P(b)}) ∪∪ ({﹁P(b), R(y)}-{﹁P(b)})            =({Q(a)}) ∪∪ ({R(y)})= {Q(a), R(y)}            =Q(a)∨∨R(y)4.4.2 鲁滨逊归结原理鲁滨逊归结原理3. 谓词逻辑的归结谓词逻辑的归结n例例4.7 设设C1=P(x)∨∨P(f(a))∨∨Q(x) ，，C2=﹁﹁P(y)∨∨R(b)，求，求C12n     解：对参加归结的某个子句，若其内部有可合一的文解：对参加归结的某个子句，若其内部有可合一的文字，则在进行归结之前应先对这些文字进行合一。

字，则在进行归结之前应先对这些文字进行合一n本例的本例的C1中有可合一的文字中有可合一的文字P(x)与与P(f(a))，若用它们的最，若用它们的最一般合一一般合一σ={f(a)/x}进行代换，可得到进行代换，可得到            C1σ=P(f(a))∨∨Q(f(a))n选选L1= P(f(a)), L2 =﹁﹁P(y)，，L1和和L2的最一般合一是的最一般合一是σ={f(a)/y}，则可得到，则可得到C1和和C2的二元归结式为的二元归结式为n            C12=R(b)∨∨Q(f(a))nC1σ称为称为C1的因子一般来说，若子句的因子一般来说，若子句C中有两个或中有两个或两个以上的文字具有最一般合一两个以上的文字具有最一般合一σ，则称，则称Cσ为子句为子句C的因子如果的因子如果Cσ是一个单文字，则称它为是一个单文字，则称它为C的的单元因单元因子n 定义定义4.18若若C1和和C2是无公共变元的子句，则是无公共变元的子句，则n     ①①  C1和和C2的二元归结式的二元归结式;n     ②②  C1和和C2的因子的因子C2σ2的二元归结式；的二元归结式；n     ③③  C1的因子的因子C1σ1和和C2的二元归结式；的二元归结式；n     ④④  C1的因子的因子C1σ1和和C2的因子的因子C2σ2的二元归结式。

的二元归结式n这四种二元归结式都是子句这四种二元归结式都是子句C1和和C2的二元归结式，的二元归结式，记为记为C124.4.2 鲁滨逊归结原理鲁滨逊归结原理3. 谓词逻辑的归结谓词逻辑的归结n    谓词逻辑的归结反演谓词逻辑的归结反演n    n     例例4.8 已知已知          F:  (∀∀x)((∃∃y)(A(x, y)∧∧B(y))→(∃∃y)(C(y)∧∧D(x, y)))          G: ﹁﹁(∃∃x)C(x)→(∀∀x)(∀∀y)(A(x, y)→﹁﹁B(y))                 求证求证G是是F的逻辑结论的逻辑结论n    证明：先把证明：先把G否定，并放入否定，并放入F中，得到的中，得到的{F, ﹁﹁G}为为    {(∀∀ x)((∃∃ y)(A(x,y)∧∧B(y))→(∃∃ y)(C(y)∧∧D(x,y))),     ﹁﹁(﹁﹁(∃∃ x)C(x)→(∀∀ x)(∀∀ y)(A(x,y)→﹁﹁ B(y)))}4.4.2 鲁滨逊归结原理鲁滨逊归结原理3. 谓词逻辑的归结谓词逻辑的归结n     再把再把{F,﹁﹁G}化成子句集，得到化成子句集，得到n     (1) ﹁﹁A(x,y)∨∨﹁﹁ B(y) ∨∨C(f(x))n     (2) ﹁﹁ A(u,v)∨∨﹁﹁ B(v) ∨∨D(u,f(u))n     (3) ﹁﹁ C(z)n     (4)  A(m,n)n     (5)  B(k)其中，其中，(1)、、(2)是由是由F 化出的两个子句，化出的两个子句，(3)、、(4)、、(5)是由是由﹁﹁G化化出的出的3个子句个子句n     (6) ﹁﹁ A(x,y)∨∨ ﹁﹁ B(y)     由由(1)和和(3)归结，取归结，取σ={f(x)/z}n     (7) ﹁﹁ B(n)                   由由(4)和和(6)归结，取归结，取σ={m/x,n/y}n     (8)  NIL                   由由(5)和和(7)归结，取归结，取σ={n/k}n因此，因此，G是是F 的逻辑结论。

的逻辑结论4.4.2 鲁滨逊归结原理鲁滨逊归结原理3. 谓词逻辑的归结谓词逻辑的归结﹁A(x,y)∨﹁ B(y)∨C(f(x))﹁ C(z)﹁A(x,y)∨﹁ B(y)A(m,n)﹁ B(n)B(k)NIL{f(x)/z}{m/x,n/y}{n/k}归结树归结树4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略n 归结演绎推理实际上就是从子句集中不断寻找可进归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对，并通过对这些子句对的归结，最终行归结的子句对，并通过对这些子句对的归结，最终得出一个空子句的过程这种得出一个空子句的过程这种盲目的全面进行归结盲目的全面进行归结的的方法，不仅会产生许多无用的归结式，更严重的是会方法，不仅会产生许多无用的归结式，更严重的是会产生组核爆炸问题产生组核爆炸问题n归结策略：归结策略：n删除策略删除策略是通过删除某些无用的子句来缩小归结范围；是通过删除某些无用的子句来缩小归结范围；n限制策略限制策略是通过对参加归结的子句进行某些限制，来是通过对参加归结的子句进行某些限制，来减少归结的盲目性，以尽快得到空子句减少归结的盲目性，以尽快得到空子句。

4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略1. 广度优先策略（广度优先策略（1/3））n      n      (1) 从从S0出发，对出发，对S0中的全部子句作所有可能的归结，中的全部子句作所有可能的归结，得到第一层归结式，记为得到第一层归结式，记为S1;n      (2) 用用S0中的子句与中的子句与S1中的子句进行所有可能的归结，中的子句进行所有可能的归结，得到第二层归结式，记为得到第二层归结式，记为S2;n      (3) 用用S0和和S1中的子句与中的子句与S2中的子句进行所有可能的归中的子句进行所有可能的归结，得到第三层归结式，记为结，得到第三层归结式，记为S3;      如此继续，知道得出空子句或不能再继续归结为止如此继续，知道得出空子句或不能再继续归结为止    n  例例4.9 设有如下子句集：设有如下子句集：          S={﹁﹁I(x)∨∨R(x),  I(a), ﹁﹁R(y)∨∨L(y), ﹁﹁L(a) }用宽度优先策略证明用宽度优先策略证明S为不可满足为不可满足4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略1. 广度优先策略（广度优先策略（2/3））﹁﹁I(x)∨ ∨R(x)I(a)﹁﹁R(y)∨ ∨L(y)﹁﹁L(a)R(a)﹁﹁I(x) ∨ ∨L(x)﹁﹁R(a)L(a)L(a)﹁﹁I(a)﹁﹁I(a)NILSS1S24.4.3 归结演绎推理的归结策略归结演绎推理的归结策略2. 支持集策略（支持集策略（1/3））n它要求每一次参加归结的两个亲本子句中，至少应它要求每一次参加归结的两个亲本子句中，至少应该有一个是由目标公式的否定所得到的子句或它们该有一个是由目标公式的否定所得到的子句或它们的后裔。

的后裔n     例例4.10 设有如下子句集：设有如下子句集：          S={﹁﹁I(x)∨∨R(x),  I(a),﹁﹁ R(y)∨∨L(y), ﹁﹁L(a) }其中，其中，﹁﹁I(x)∨∨R(x)为目标公式的否定用支持集策略为目标公式的否定用支持集策略证明证明S为不可满足为不可满足4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略2. 支持集策略（支持集策略（2/3））﹁﹁I(x)∨ ∨R(x)I(a)﹁﹁ R(y)∨ ∨L(y)﹁﹁L(a)R(a)﹁﹁I(x)∨ ∨L(x)L(a)L(a)﹁﹁I(a)NIL4.4.5 归结演绎推理的归结策略归结演绎推理的归结策略3. 删除策略（删除策略（1/3））n在归结时能把子句集中无用的子句删除掉，缩小搜索范围在归结时能把子句集中无用的子句删除掉，缩小搜索范围n常用的删除方法：常用的删除方法：n纯文字删除法纯文字删除法       如果某文字如果某文字L在子句集中不存在可与其互补的文字在子句集中不存在可与其互补的文字﹁﹁L，，则称该文字为则称该文字为纯文字纯文字       在归结过程中，纯文字不可能被消除，对包含纯文字的子在归结过程中，纯文字不可能被消除，对包含纯文字的子句进行归结是没有意义的，应该把它从子句集中删除。

句进行归结是没有意义的，应该把它从子句集中删除n删除包含纯文字的子句，不影响其不可满足性删除包含纯文字的子句，不影响其不可满足性n例如，对子句集例如，对子句集          S={P∨∨Q∨∨R, ﹁﹁Q∨∨R,  Q, ﹁﹁R}其中其中P是纯文字是纯文字，因此可以将子句，因此可以将子句P∨∨Q∨∨R从子句集从子句集S中删除 4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略3. 删除策略（删除策略（2/3））n重言式删除法重言式删除法n 如果一个子句中如果一个子句中包含有互补的文字对包含有互补的文字对，则称该子句，则称该子句为为重言式重言式例如         P(x)∨∨﹁﹁P(x),  P(x)∨∨Q(x)∨∨﹁﹁P(x)  都是重言式，不管都是重言式，不管P(x)的真值为真还是为假，的真值为真还是为假，P(x)∨∨﹁﹁P(x)和和P(x)∨∨Q(x)∨∨﹁﹁P(x)都均为真都均为真n 重言式是真值为真的子句对一个子句集来说，不重言式是真值为真的子句对一个子句集来说，不管是增加还是删除一个真值为真的子句，都不会影管是增加还是删除一个真值为真的子句，都不会影响该子句集的不可满足性。

因此，可从子句集中删响该子句集的不可满足性因此，可从子句集中删去重言式去重言式4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略3. 删除策略（删除策略（3/3））n包孕删除法包孕删除法n    设有子句设有子句C1和和C2，如果存在一个置换，如果存在一个置换σ，使得，使得C1σ⊆⊆C2，则，则称称C1包孕于包孕于C2例如    P(x)             包孕于包孕于   P(y)∨∨Q(z)             σ={x/y}    P(x)             包孕于包孕于   P(a)                        σ={a/x}    P(x)             包孕于包孕于   P(a)∨∨Q(z)             σ={a/x}    P(x) ∨∨Q(a) 包孕于包孕于 P(f(a))∨∨Q(a)∨∨R(y) σ={f(a)/x}    P(x) ∨∨Q(y) 包孕于包孕于 P(a)∨∨Q(u)∨∨R(w)    σ={a/x, u/y}n对子句集来说，把其中包孕的子句删去后，不会影响该子句对子句集来说，把其中包孕的子句删去后，不会影响该子句集的不可满足性。

集的不可满足性4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略4. 单文字子句策略（单文字子句策略（1/2））n例例4.11 设有如下子句集：设有如下子句集：    S={﹁﹁I(x)∨∨R(x),  I(a), ﹁﹁R(y)∨∨L(y), ﹁﹁L(a) }用单文字子句策略证明用单文字子句策略证明S为不可满足为不可满足n但这种策略是但这种策略是不完备的不完备的，即当子句集为不可满足时，用，即当子句集为不可满足时，用这种策略不一定能归结出空子句这种策略不一定能归结出空子句﹁﹁I(x)∨ ∨R(x)I(a)﹁﹁R(y)∨ ∨L(y)﹁﹁L(a)R(a)﹁﹁R(a)NIL4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略5. 线性输入策略（线性输入策略（1/2））n要求每次参加归结的两个亲本子句中，要求每次参加归结的两个亲本子句中，至少应该有一至少应该有一个是初始子句集中的子句个是初始子句集中的子句n      例例4.12 设有如下子句集：设有如下子句集：           S={﹁﹁I(x)∨∨R(x),  I(a), ﹁﹁R(y)∨∨L(y), ﹁﹁L(a) }用线性输入策略证明用线性输入策略证明S为不可满足。

为不可满足n这种策略这种策略也是一种不完备的策略也是一种不完备的策略n例如，子句集例如，子句集 S={Q(u)∨∨P(a), ﹁﹁Q(w)∨∨P(w), ﹁﹁Q(x)∨∨﹁﹁ P(x), Q(y)∨∨﹁﹁ P(y)}     从从S出发很容易找到一棵归结反演树，但却不存性出发很容易找到一棵归结反演树，但却不存性输入策略的归结反演树输入策略的归结反演树 4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略5. 线性输入策略（线性输入策略（2/2））﹁﹁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)NIL4.4.3 归结演绎推理的归结策略归结演绎推理的归结策略6. 祖先过滤策略（祖先过滤策略（1/2））n与线性输入策略有点相似，但是，放宽了对子句的限制与线性输入策略有点相似，但是，放宽了对子句的限制每次参加归结的两个亲本子句，只要每次参加归结的两个亲本子句，只要满足以下两个条件中满足以下两个条件中的任意一个的任意一个就可进行归结：就可进行归结：n (1) 两个亲本子句中至少有一个是初始子句集中的子句。

两个亲本子句中至少有一个是初始子句集中的子句n (2) 如果两个亲本子句都不是初始子句集中的子句，则一如果两个亲本子句都不是初始子句集中的子句，则一个子句应该是另一个子句的先辈子句个子句应该是另一个子句的先辈子句n 例例4.13 设有如下子句集：设有如下子句集： S={﹁﹁Q(x)∨ ∨﹁﹁P(x), Q(y)∨ ∨﹁﹁P(y)，，﹁﹁Q(w)∨ ∨P(w) , Q(a)∨ ∨P(a) } 用祖先过滤策略证明用祖先过滤策略证明S为不可满足为不可满足n祖先过滤策略也祖先过滤策略也是完备的是完备的 4.4.3 归结演绎推理的归结策略6. 祖先过滤策略（祖先过滤策略（2/2））﹁﹁Q(x)∨ ∨ ﹁﹁P(x)Q(y)∨ ∨﹁﹁P(y)﹁﹁ P(x)﹁﹁ Q(w)∨ ∨P(w)﹁﹁ Q(w)Q(a)∨ ∨P(a)P(a)NIL4.4.4 用归结反演求取问题的答案用归结反演求取问题的答案n 归结原理除了用于定理证明外，还可用来求取问题答案归结原理除了用于定理证明外，还可用来求取问题答案.n步骤为：步骤为： (1) 把已知条件用谓词公式表示出来，并化为相应的子句集；把已知条件用谓词公式表示出来，并化为相应的子句集；(2) 把问题的目标的否定用谓词公式表示出来，并化为子句集；把问题的目标的否定用谓词公式表示出来，并化为子句集；(3) 对目标否定子句集中的每个子句，构造该子句的重言式，用对目标否定子句集中的每个子句，构造该子句的重言式，用这些重言式代替相应的目标否定子句式，并把这些重言式加这些重言式代替相应的目标否定子句式，并把这些重言式加入到前提子句集中，得到一个新的子句集；入到前提子句集中，得到一个新的子句集； (4) 对这个新的子句集，应用归结原理求出其证明树，这时证对这个新的子句集，应用归结原理求出其证明树，这时证明树的根子句不为空，称这个证明树为明树的根子句不为空，称这个证明树为修改的证明树修改的证明树；；(5) 用修改证明树的根子句作为回答语句，则答案就在此根子句用修改证明树的根子句作为回答语句，则答案就在此根子句中。

中4.4.4 用归结反演求取问题的答案用归结反演求取问题的答案（（2/4））n例例4.14 已知：已知：“张和李是同班同学，如果张和李是同班同学，如果x和和y是同班同学，是同班同学，则则x的教室也是的教室也是y的教室，现在张在的教室，现在张在302教室上课教室上课      问：问：“现在李在哪个教室上课？现在李在哪个教室上课？”n解：解：首先定义谓词：首先定义谓词：          C(x, y)     x和和y是同班同学；是同班同学；          At(x, u)    x在在u教室上课教室上课n把已知前提用谓词公式表示如下：把已知前提用谓词公式表示如下：          C(zhang, li)          (∀∀x) (∀∀y) (∀∀u) (C(x, y)∧∧At(x, u)→At(y,u))          At(zhang, 302)   n    把目标的否定用谓词公式表示如下：把目标的否定用谓词公式表示如下：          ﹁﹁(∃∃v)At(li, v)    4.4.4 用归结反演求取问题的答案用归结反演求取问题的答案（（3/4））n把上述公式化为子句集：把上述公式化为子句集：      C(zhang, li)      ﹁﹁C(x, y)∨∨﹁﹁At(x, u)∨∨At(y, u)      At(zhang, 302)n把目标的否定化成子句式，并用重言式把目标的否定化成子句式，并用重言式    ﹁﹁At(li,v) ∨∨At(li,v)         代替之。

代替之n把此重言式加入前提子句集中，得到一个新的子句集，对把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树这个新的子句集，应用归结原理求出其证明树n该证明树的根子句就是所求的答案，即该证明树的根子句就是所求的答案，即“李明在李明在302教室教室”4.4.4 用归结反演求取问题的答案用归结反演求取问题的答案（（4/4））﹁﹁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}。