第4章-确定性推理

1、第第4章章 确定性推理确定性推理 n智能系统的推理过程实际上就是一种思维过程。按照推理智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性，推理可分为确定性推理和不确定过程所用知识的确定性，推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型，本章重点讨论前一性推理。对于推理的这两种不同类型，本章重点讨论前一种，不确定性推理放到下一章讨论。种，不确定性推理放到下一章讨论。 n4.1 推理的基本概念推理的基本概念n4.2 推理的逻辑基础推理的逻辑基础n4.3 自然演绎推理自然演绎推理n4.4 归结演绎推理归结演绎推理4.1 推理的基本概念推理的基本概念n4.1.1 什么

2、是推理什么是推理n4.1.2 推理方法及其分类推理方法及其分类n4.1.3 推理的控制策略及其分类推理的控制策略及其分类4.1.1 什么是推理什么是推理n推理的概念推理的概念n 是指按照某种策略从已知事实出发去推出结论的过程。是指按照某种策略从已知事实出发去推出结论的过程。n 推理所用的事实：推理所用的事实：n 初始证据：初始证据：推理前用户提供的推理前用户提供的n 中间结论：中间结论：推理过程中所得到的推理过程中所得到的n 推理过程：推理过程：由推理机来完成，所谓推理机就是智能系统由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。中用来实现推理的那些程序。n推理的两个基本问题推

3、理的两个基本问题n 推理的方法：推理的方法：解决前提和结论的逻辑关系，不确定性传解决前提和结论的逻辑关系，不确定性传递递n 推理的控制策略：推理的控制策略：解决推理方向，冲突消解策略解决推理方向，冲突消解策略4.1.2 推理方法及其分类推理方法及其分类n可分为演绎推理、归纳推理、默认推理可分为演绎推理、归纳推理、默认推理 n演绎推理演绎推理n 演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论。方法，其

4、核心是三段论。n 例： 假言三段论n AB，BC ACn 常用的三段论是由一个大前提、一个小前提和一个结论这三部常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，分组成的。其中，大前提大前提是已知的一般性知识或推理过程得到的判是已知的一般性知识或推理过程得到的判断；断；小前提小前提是关于某种具体情况或某个具体实例的判断；是关于某种具体情况或某个具体实例的判断；结论结论是由是由大前提推出的，并且适合于小前提的判断。大前提推出的，并且适合于小前提的判断。n 1. 1. 按推理的逻辑基础分类按推理的逻辑基础分类(1/5)(1/5)例如：例如：有如下三个判断：有如下三个判断： 计算

5、机系的学生都会编程序；（一计算机系的学生都会编程序；（一般性知识）般性知识） 程强是计算机系的一位学生；（具程强是计算机系的一位学生；（具体情况）体情况） 程强会编程序。程强会编程序。 （结论）（结论） 这是一个三段论推理。其中，是大前这是一个三段论推理。其中，是大前提，是小前提；是经演绎推出来的结提，是小前提；是经演绎推出来的结论。论。 可见，其结论是蕴含在大前提中的。可见，其结论是蕴含在大前提中的。n归纳推理归纳推理n是一种由个别到一般的推理方法。归纳推理的类型是一种由个别到一般的推理方法。归纳推理的类型n 按照所选事例的广泛性按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理可分为完

6、全归纳推理和不完全归纳推理n 按照推理所使用的方法按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理可分为枚举、类比、统计和差异归纳推理等等n 完全归纳推理完全归纳推理n 是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。量检验。n 不完全归纳推理不完全归纳推理n 是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，

7、计算机，随机抽查。事物的结论。例如，计算机，随机抽查。n 枚举归纳推理枚举归纳推理n 是指在进行归纳时，如果已知某类事物的有限可数个具体事物都是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。具有某种属性，则可推出该类事物都具有此种属性。4.1.2 推理方法及其分类推理方法及其分类1. 1. 按推理的逻辑基础分类按推理的逻辑基础分类(2/5)(2/5)例如：设有如下事例：例如：设有如下事例： 王强是计算机系学生，他会编程序；王强是计算机系学生，他会编程序； 高华是计算机系学生，她会编程序；高华是计算机系学生，她会编程序； 当这些具体事例足够多

8、时，就可归纳出一个一般性的知识：当这些具体事例足够多时，就可归纳出一个一般性的知识： 凡是计算机系的学生，就一定会编程序。凡是计算机系的学生，就一定会编程序。n类比归纳推理类比归纳推理n 是指在两个或两类事物有许多属性都相同或相似的基础上，推出它是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。们在其他属性上也相同或相似的一种归纳推理。n 设设A、B分别是两类事物的集合：分别是两类事物的集合：n A=a1,a2,n B=b1,b2,n并设并设ai与与bi总是成对出现，且当总是成对出现，且当ai有属性有属性P时，时，bi就有属性就有属性Q与此对应

9、，即与此对应，即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. 1. 按推理的逻辑基础分类按推理的逻辑基础分类(3/5)(3/5)n默认推理默认推理

10、n 默认推理又被称为缺省推理，它是在知识不完全的情况下假设某些默认推理又被称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。条件已经具备所进行的推理。n 例如：在条件例如：在条件A已成立的情况下，如果没有足够的证据能证明条件已成立的情况下，如果没有足够的证据能证明条件B不成立，则默认不成立，则默认B是成立的，并在此默认的前提下进行推理，推导出某是成立的，并在此默认的前提下进行推理，推导出某个结论。个结论。n 由于这种推理允许某些默认条件是成立的，这就摆脱了需要知道全部由于这种推理允许某些默认条件是成立的，这就摆脱了需要知道全部有关事实才能进行推理的束缚，使得推理在知识不完

11、全的情况下也能进有关事实才能进行推理的束缚，使得推理在知识不完全的情况下也能进行。行。n 在默认推理中，如果到某一时刻发现原先所做的默认不正确，则要撤在默认推理中，如果到某一时刻发现原先所做的默认不正确，则要撤销所做的默认以及由此默认推出的所有结论，重新按新情况进行推理。销所做的默认以及由此默认推出的所有结论，重新按新情况进行推理。4.1.2 推理方法及其分类推理方法及其分类1. 1. 按推理的逻辑基础分类按推理的逻辑基础分类(4/5)(4/5)n演绎推理与归纳推理的区别演绎推理与归纳推理的区别n 演绎推理演绎推理是在已知领域内的一般性知识的前提下，通过演是在已知领域内的一般性知识的前提下，通

12、过演绎求解一个具体问题或者证明一个结论的正确性。它所得出绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不过是将已有事实揭露出来，因此它不能增殖新知识不能增殖新知识。n 归纳推理归纳推理所推出的结论是没有包含在前提内容中的。这种所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，由个别事物或现象推出一般性知识的过程，是增殖新知识是增殖新知识的的过程。过程。n 例如，例如，一位计算机维修员，从书本知识，到通过大量实例一位计算机维修

13、员，从书本知识，到通过大量实例积累经验，是一种积累经验，是一种归纳归纳推理方式。运用这些一般性知识知识推理方式。运用这些一般性知识知识去维修计算机的过程则是去维修计算机的过程则是演绎演绎推理。推理。 4.1.2 推理方法及其分类推理方法及其分类1. 1. 按推理的逻辑基础分类按推理的逻辑基础分类(5/5)(5/5)4.1.2 推理方式及其分类 按推理过程中推出的结论是否单调地增加，或推出的结按推理过程中推出的结论是否单调地增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调推理论是否越来越接近目标，可分为单调推理和非单调推理。 单调推理：单调推理：在推理过程中随着推理的向前及新知识的加

14、在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越接近入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况，即不会由最终目标，在推理过程中不出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理又于新知识的加入否定了前面推出的结论，从而使推理又回到前面的某一步。回到前面的某一步。2 2、单调推理、非单调推理、单调推理、非单调推理(1/2)(1/2)4.1.2 推理方式及其分类 非单调推理：非单调推理：在推理过程中由于新知识的加入，不仅没有在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推

15、理退回到前面加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。的某一步，重新开始。 注意：注意：非单调推理是在知识不完全的情况下发生的。由于非单调推理是在知识不完全的情况下发生的。由于知识不完全，为使推理进行下去，就要先做某些假设，并知识不完全，为使推理进行下去，就要先做某些假设，并在此基础上进行推理，当以后由于新知识的加入发现原先在此基础上进行推理，当以后由于新知识的加入发现原先的假设不正确的时候，就需要推翻该假设以及基于此假设的假设不正确的时候，就需要推翻该假设以及基于此假设而推出的一切结论，再用新的知识重新进行推理。而推出的一切结论，再用新的知识重新进行推理。2 2、

16、单调推理、非单调推理、单调推理、非单调推理(2/2)(2/2)4.1.2 推理方式及其分类 按推理时所用知识的确定性来划分，推理可分为确定性推理、按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理。不确定性推理。 确定性推理（精确推理）：确定性推理（精确推理）：如果在推理中所用的知识都是精确如果在推理中所用的知识都是精确的，即可以把知识表示成必然的因果关系，然后进行逻辑推理的，即可以把知识表示成必然的因果关系，然后进行逻辑推理，推理的结论或者为真，或者为假，这种推理就称为确定性推，推理的结论或者为真，或者为假，这种推理就称为确定性推理。理。 如：在如：在MYCINMYCIN中采

17、用确定性方法是一种简单有效的方法，仅中采用确定性方法是一种简单有效的方法，仅采用一些简单直观的证据合并规则，其缺点是缺乏良好的理论采用一些简单直观的证据合并规则，其缺点是缺乏良好的理论基础。基础。3 3、确定性推理、不确定性推理、确定性推理、不确定性推理(1/3)(1/3)4.1.2 推理方式及其分类 按推理时所用知识的确定性来划分，推理可分为确定性推理、不按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理。确定性推理。 不确定性推理（不精确推理）：不确定性推理（不精确推理）：在人类知识中，有相当一部分属在人类知识中，有相当一部分属于人们的主观判断，是不精确的和含糊的。由这些知

18、识归纳出来的于人们的主观判断，是不精确的和含糊的。由这些知识归纳出来的推理规则往往是不确定的。基于这种不确定的推理规则进行推理，推理规则往往是不确定的。基于这种不确定的推理规则进行推理，形成的结论也是不确定的，这种推理称为不确定性推理。形成的结论也是不确定的，这种推理称为不确定性推理。 在专家系统中，主要使用的是不确定性推理。在专家系统中，主要使用的是不确定性推理。3 3、确定性推理、不确定性推理、确定性推理、不确定性推理(2/3)(2/3)4.1.2 推理方式及其分类 不确定性研究的重点可能会：不确定性研究的重点可能会： 一是：一是：解决现有处理不确定性的理论中存在的问题；解决现有处理不确定

19、性的理论中存在的问题； 二是：二是：大力研究人类高效、准确的识别能力和判断机智大力研究人类高效、准确的识别能力和判断机智，开拓新的处理不确定性的理论和方法；，开拓新的处理不确定性的理论和方法； 三是：三是：探索可以综合处理多种不确定性的放法和技术。探索可以综合处理多种不确定性的放法和技术。3 3、确定性推理、不确定性推理、确定性推理、不确定性推理(3/3)(3/3)4.1.2 推理方式及其分类 按推理过程中推出的结论是否单调地增加，或推出的结按推理过程中推出的结论是否单调地增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调推理论是否越来越接近目标，可分为单调推理和非单调推理。 单调推

20、理：单调推理：在推理过程中随着推理的向前及新知识的加在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越接近入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况，即不会由最终目标，在推理过程中不出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理又于新知识的加入否定了前面推出的结论，从而使推理又回到前面的某一步。回到前面的某一步。4 4、单调推理、非单调推理、单调推理、非单调推理(1/2)(1/2)4.1.2 推理方式及其分类 按推理过程中推出的结论是否单调地增加，或推出的结论是否按推理过程中推出的结论是否单调地

21、增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调推理。越来越接近目标，可分为单调推理和非单调推理。 非单调推理：非单调推理：在推理过程中由于新知识的加入，不仅没有加强在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。，重新开始。 注意：注意：非单调推理是在知识不完全的情况下发生的。由于知识不完非单调推理是在知识不完全的情况下发生的。由于知识不完全，为使推理进行下去，就要先做某些假设，并在此基础上进行推理全，为使推理进行下去，就要先做某些假设，并在此基础上进行推理，当以后由

22、于新知识的加入发现原先的假设不正确的时候，就需要推，当以后由于新知识的加入发现原先的假设不正确的时候，就需要推翻该假设以及基于此假设而推出的一切结论，再用新的知识重新进行翻该假设以及基于此假设而推出的一切结论，再用新的知识重新进行推理。推理。4 4、单调推理、非单调推理、单调推理、非单调推理(2/2)(2/2)4.1.2 推理方式及其分类 如果按推理程中是否运用于问题有关的启发性知识，推如果按推理程中是否运用于问题有关的启发性知识，推理可分为启发式推理与非启发式推理。理可分为启发式推理与非启发式推理。 启发式推理：启发式推理：如果在推理过程中，运用了与问题有关的如果在推理过程中，运用了与问题有

23、关的启发性知识，即解决问题的策略、技巧及经验，以加快启发性知识，即解决问题的策略、技巧及经验，以加快推理过程，提高搜索效率，这种推理过程就被称为启发推理过程，提高搜索效率，这种推理过程就被称为启发式推理。式推理。 如第三章的如第三章的A A* *、AOAO* *等算法就属于此类推理。等算法就属于此类推理。5 5、启发式推理、非启发式推理、启发式推理、非启发式推理(1/2)(1/2)4.1.2 推理方式及其分类 非启发式推理：非启发式推理：如果在推理过程中，不运用启发性知识，如果在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理，这种推理过程就被称为只按照一般的控制逻辑进行推理，这种推

24、理过程就被称为非启发式推理。非启发式推理。 注意：注意：这种推理缺乏对待求解问题的针对性，所以推理效这种推理缺乏对待求解问题的针对性，所以推理效率较低，容易出现组合爆炸问题。如图搜索策略头重的宽率较低，容易出现组合爆炸问题。如图搜索策略头重的宽度优先搜索法，虽然是完备的算法，但是对复杂问题的求度优先搜索法，虽然是完备的算法，但是对复杂问题的求解，将出现组合爆炸现象，其搜索效率较低。解，将出现组合爆炸现象，其搜索效率较低。5 5、启发式推理、非启发式推理、启发式推理、非启发式推理(2/2)(2/2)4.1.3 推理的控制策略n推理的控制策略推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、

25、求解策略及限制策略等。1、推理方向n推理方向用于确定推理的驱动方式，分为四种： 正向推理 逆向推理 混合推理 双向推理4.1.3 推理的控制策略n正向推理正向推理 正向推理是从初始状态出发，使用规则，到达正向推理是从初始状态出发，使用规则，到达目标状态。又称为数据驱动推理、前向链推理、模目标状态。又称为数据驱动推理、前向链推理、模式制导推理及前件推理。式制导推理及前件推理。n逆向推理逆向推理 逆向推理是以某个假设目标为出发点的一种推逆向推理是以某个假设目标为出发点的一种推理，又称为目标驱动推理、逆向链推理、目标制导理，又称为目标驱动推理、逆向链推理、目标制导推理及后件推理。推理及后件推理。4.

26、1.3 推理的控制策略n混合推理混合推理 已知的事实不充分。通过正向推理先把其运用条件不已知的事实不充分。通过正向推理先把其运用条件不能完全匹配的知识都找出来，并把这些知识可导出的结能完全匹配的知识都找出来，并把这些知识可导出的结论作为假设，然后分别对这些假设进行逆向推理。论作为假设，然后分别对这些假设进行逆向推理。n推理的形式：推理的形式：先正向再逆向，通过正向推理，即从已知事实演绎先正向再逆向，通过正向推理，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高出部分结果，然后再用逆向推理证实该目标或提高其可信度。其可信度。先逆向再正向，先假设一个目标进行逆向推理，然先逆向再正向，先

27、假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。推出更多的结论。4.1.3 推理的控制策略n双向推理双向推理双向推理是指正向推理与逆向推理同时进行，且在推双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上理过程中的某一步骤上“碰头碰头”的一种推理。的一种推理。正向推理所得的中间结论恰好是逆向推理此时要求的正向推理所得的中间结论恰好是逆向推理此时要求的证据证据2、求解策略 推理是只求一个解还是求所有解以及最优解等推理是只求一个解还是求所有解以及最优解等3、限制策略 对推理的深度、宽度、时间、空间等

28、进行限制对推理的深度、宽度、时间、空间等进行限制4.1.3 推理的控制策略4、冲突消解策略冲突消解策略 n在推理过程中，匹配会出现三种情况：在推理过程中，匹配会出现三种情况：已知事实不能与知识库中的任何知识匹配成功已知事实不能与知识库中的任何知识匹配成功已知事实恰好只与知识库中的一个知识匹配成功已知事实恰好只与知识库中的一个知识匹配成功已知事实可与知识库中的多个知识匹配成功；或者有多已知事实可与知识库中的多个知识匹配成功；或者有多个（组）已知事实都可与知识库中某一知识匹配成功；个（组）已知事实都可与知识库中某一知识匹配成功；或者有多个（组）已知事实可与知识库中的多个知识匹或者有多个（组）已知事

29、实可与知识库中的多个知识匹配成功配成功4.1.3 推理的控制策略4、冲突消解策略冲突消解策略 出现冲突的情况出现冲突的情况对正向推理而言，如果有多条产生式规则的前件都和已知对正向推理而言，如果有多条产生式规则的前件都和已知的事实匹配成功；或者有多组不同的已知事实都与同一条的事实匹配成功；或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功；或者两种情况同时出现产生式规则的前件匹配成功；或者两种情况同时出现对逆向推理而言，如果有多条产生式的后件都和同一假设对逆向推理而言，如果有多条产生式的后件都和同一假设匹配成功，或者有多条产生式后件可与多个假设匹配成功匹配成功，或者有多条产生式后件可与多

30、个假设匹配成功。4.1.3 推理的控制策略冲突消解策略冲突消解策略n按就近原则排序按就近原则排序l该策略把最近被使用过的规则赋予较高的优先级。该策略把最近被使用过的规则赋予较高的优先级。 n按已知事实的新鲜性排序按已知事实的新鲜性排序 l一般我们认为新鲜事实是对旧知识的更新和改进，比一般我们认为新鲜事实是对旧知识的更新和改进，比老知识更有效，即后生成的事实比先生成的事实具有老知识更有效，即后生成的事实比先生成的事实具有较大的优先性。较大的优先性。 4.1.3 推理的控制策略冲突消解策略冲突消解策略n按匹配度排序按匹配度排序 l在不确定推理时，匹配度不仅可确定两个知识在不确定推理时，匹配度不仅可

31、确定两个知识模式是否可匹配，还可用于冲突消解。根据匹模式是否可匹配，还可用于冲突消解。根据匹配程度来决定哪一个产生式规则优先被应用。配程度来决定哪一个产生式规则优先被应用。n按领域问题特点排序按领域问题特点排序 l该方法按照求解问题领域的特点将知识排成固该方法按照求解问题领域的特点将知识排成固定的次序定的次序4.1.3 推理的控制策略冲突消解策略冲突消解策略n按上下文限制排序按上下文限制排序l该策略将知识按照所描述的上下文分成若干组，在推该策略将知识按照所描述的上下文分成若干组，在推理过程中根据当前数据库中的已知事实与上下文的匹理过程中根据当前数据库中的已知事实与上下文的匹配情况，确定选择某组

32、中的某条知识。配情况，确定选择某组中的某条知识。n按条件个数排序按条件个数排序l多条规则生成的结论相同的情况下，由于条件个数较多条规则生成的结论相同的情况下，由于条件个数较少的规则匹配所花费的时间较少而且容易实现，所以少的规则匹配所花费的时间较少而且容易实现，所以将条件少的规则赋予较高的优先级，优先被启用。将条件少的规则赋予较高的优先级，优先被启用。 4.1.3 推理的控制策略冲突消解策略冲突消解策略n按规则的次序排序按规则的次序排序 l该策略是以知识库中预先存入规则的排列顺序作该策略是以知识库中预先存入规则的排列顺序作为知识排序的依据，排在前面的规则具有较高的为知识排序的依据，排在前面的规则

33、具有较高的优先级。优先级。 第4章 确定性推理 n4.1 推理的基本概念推理的基本概念n4.2 推理的逻辑基础推理的逻辑基础n4.3 自然演绎推理自然演绎推理n4.4 归结演绎推理归结演绎推理4.2 推理的逻辑基础推理的逻辑基础n4.2.1 谓词与个体谓词与个体n4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n4.2.3 置换与合一置换与合一4.2.1 谓词与个体谓词与个体n在谓词逻辑中，可以将原子命题分解为在谓词逻辑中，可以将原子命题分解为谓词谓词与与个体个体两部分。两部分。个体：个体：是指可以独立存在的物体，可以是抽象的或具是指可以独立存在的物体，可以是抽象的或具体的。体

34、的。谓词：谓词：则用于刻画个体的性质、状态或个体间的关系。则用于刻画个体的性质、状态或个体间的关系。例如：例如：“李白是诗人李白是诗人”可表示为可表示为poet(LiBai)，poet称称为谓词，用以刻画为谓词，用以刻画“是诗人是诗人”；LiBai称为个体。称为个体。4.2.1 谓词与个体谓词与个体n一元谓词：一元谓词：一个谓词，可以与一个个体相关联，这种一个谓词，可以与一个个体相关联，这种谓词称作一元谓词，谓词称作一元谓词，它刻画了个体的性质。它刻画了个体的性质。n多元谓词：多元谓词：一个谓词，可以与多个个体相关联，这种一个谓词，可以与多个个体相关联，这种谓词称作多元谓词，谓词称作多元谓词，

35、它刻画了个体间的关系。它刻画了个体间的关系。n谓词的一般形式谓词的一般形式可表示为：可表示为： P(x1,x2, ,xn)n其中其中P P是谓词，而是谓词，而x x1 1,x,x2 2, , ,x,xn n是个体。谓词通常用大是个体。谓词通常用大写字母表示，个体通常用小写字母表示。写字母表示，个体通常用小写字母表示。4.2.1 谓词与个体谓词与个体n注意事项：注意事项：n谓词的项：谓词的项：在谓词中，个体可以是常量，也可以是变量，在谓词中，个体可以是常量，也可以是变量，还可以是一个函数。例如：还可以是一个函数。例如：“小刘的哥哥是个个人小刘的哥哥是个个人”，可，可以表示为以表示为worker(

36、brother(Liu)，其中，其中brother(Liu)是一个是一个函数。个体常量、变量和函数统称为项。函数。个体常量、变量和函数统称为项。n谓词的语义：谓词的语义：由使用者根据需要人为地定义。由使用者根据需要人为地定义。n谓词的元数：谓词的元数：谓词中包含的个体变量的数目称为谓词的元谓词中包含的个体变量的数目称为谓词的元数。数。4.2.1 谓词与个体谓词与个体n注意事项：注意事项：n谓词的阶数：谓词的阶数：在谓词在谓词P(x1,x2, ,xn)中，若中，若xi(i=1,2, ,n)都都是个体常量、变量或函数，则称它为一阶谓词。若某个是个体常量、变量或函数，则称它为一阶谓词。若某个xi本身

37、又是一个一阶谓词，则称它为二阶谓词，依次类推。本身又是一个一阶谓词，则称它为二阶谓词，依次类推。n谓词与函数的区别：谓词与函数的区别：谓词具有逻辑值谓词具有逻辑值“真真”或或“假假”，而，而函数则是某个个体到另一个个体（数学上：自变量到因变函数则是某个个体到另一个个体（数学上：自变量到因变量）之间的映射。量）之间的映射。4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n定义定义4.1 设设D是谓词公式是谓词公式P的非空个体域，若对的非空个体域，若对P中的个体中的个体常量、函数和谓词按如下规定赋值：常量、函数和谓词按如下规定赋值：n (1) 为每个个体常量指派为每个个体常量指派D

38、中的一个元素；中的一个元素；n (2) 为每个为每个n元函数指派一个从元函数指派一个从Dn到到D的一个映射，其中的一个映射，其中n Dn =(x1, x2, , xn)| x1, x2, , xnDn (3) 为每个为每个n元谓词指派一个从元谓词指派一个从Dn到到F，T的映射。的映射。n则称这些指派为则称这些指派为P在在D上的一个解释上的一个解释。n1、谓词公式的解释、谓词公式的解释n 例例4.1 设个体域设个体域D=1, 2，求公式，求公式A=(x)( y)P(x, y)在在D上的解释，并上的解释，并指出在每一种解释下公式指出在每一种解释下公式A的真值。的真值。 n 解：解：由于公式由于公式

39、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 F4.2.2 谓词公

40、式的永真性和可满足性谓词公式的永真性和可满足性n1、谓词公式的解释、谓词公式的解释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。因此，。因

41、此，在此解释下公式在此解释下公式A的真值为的真值为F。n 实际上，实际上，A在在D上共有上共有16种解释，这里就不在一一列举。种解释，这里就不在一一列举。 P(1,1) P(1,2) P(2,1) P(2,2) TT F F4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n定义定义4.2 如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释都取上的任一解释都取得真值得真值T，则称，则称P在在D 上是永真的上是永真的；如果；如果P在任何非空个体域在任何非空个体域上均是永真的，则称上均是永真的，则称P永真。永真。n 可见，要判定一谓词公式为永真，必须对每个非空个体域可见

42、，要判定一谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时，尽上的每个解释逐一进行判断。当解释的个数为有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个管工作量大，公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就很难判定了。数为无限时，其永真性就很难判定了。4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n2、谓词公式的永真性、谓词公式的永真性n定义定义4.3 如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释都取假上的任一解释都取假值值F，则称，则称P在在D上是永假的上是永假的；如果；如果P在任何非空个体域

43、上均在任何非空个体域上均是永假的，则称是永假的，则称P永假。永假。n谓词公式的永假性又称谓词公式的永假性又称不可满足性或不相容。不可满足性或不相容。4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n2、谓词公式的永真性、谓词公式的永真性n定义定义4.4 对于谓词公式对于谓词公式P，如果至少存在，如果至少存在D上的一个解释，上的一个解释，使公式使公式P在此解释下的真值为在此解释下的真值为T，则称公式，则称公式P在在D上是可满上是可满足的。足的。n谓词公式的谓词公式的可满足性也称为相容性。可满足性也称为相容性。n按照定义按照定义4.4，对谓词公式，对谓词公式P，如果不存在任何解释，

44、使得，如果不存在任何解释，使得P的取值为的取值为T，则称公式，则称公式P是不可满足的。所以谓词公式是不可满足的。所以谓词公式P的永假与不可满足是等价的。的永假与不可满足是等价的。n后面我们要给出的归结推理，就是采用一种逻辑上的反证后面我们要给出的归结推理，就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。法，将永真性转换为不可满足性的证明。4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n3、谓词公式的可满足性、谓词公式的可满足性n谓词公式的谓词公式的等价式可定义如下：等价式可定义如下：n定义定义4.5 设设P与与Q是是D上的两个谓词公式，上的两个谓词公式，D是它是它

45、们共同的个体域。若对们共同的个体域。若对D上的任意解释，上的任意解释，P与与Q的的取值都相同，则称公式取值都相同，则称公式P与与Q在域在域D上是等价的。上是等价的。如果如果D是任意非空个体域，则称是任意非空个体域，则称P与与Q是等价的。是等价的。记作：记作：PQ。 4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n4、谓词公式的等价性与永真蕴含、谓词公式的等价性与永真蕴含n双重否定律双重否定律(double negation law): (P(x) P(x)n德德摩根定律摩根定律(Mogen law): (P(x)Q(x) P(x) Q(x) (P(x)Q(x) P(x) Q(

46、x)n逆否律逆否律(inverse-negation law):P(x) Q(x) Q(x) P(x)n分配律分配律(assignment law):P(x)(Q(x)R(x)(P(x)Q(x)(P(x)R(x)P(x)(Q(x)R(x)(P(x)Q(x)(P(x)R(x)附附1 1：谓词演算的基本等价式谓词演算的基本等价式4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n结合律结合律(association law): （P(x)Q(x)R(x)P(x)(Q(x)R(x) （P(x)Q(x)R(x)P(x)(Q(x)R(x)n蕴含等价式蕴含等价式(implication la

47、w): P(x)Q(x)P(x)Q(x)n易名规则易名规则(rename law): xP(x) xQ(x) x P(x) yQ(y)n量词转换律量词转换律(quantifier transform law): xP(x) xP(x) xP(x) xP(x)附附1 1：谓词演算的基本等价式谓词演算的基本等价式4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n量词分配律量词分配律(quantifier assignment law): x(P(x)Q(x) xP(x) xQ(x) x(P(x)Q(x) xP(x) xQ(x) x(PQ(x)P xQ(x) x(PQ(x)P xQ(

48、x)n量词交换律量词交换律(quantifier commutative law): x y(P(x, y) y x(P(x, y) x y(P(x, y) ) y x(P(x, y) x y(P(x, y) ) y x(P(x, y) x y(P(x, y) )y x(P(x, y)附附1 1：谓词演算的基本等价式谓词演算的基本等价式4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n量词辖域变换等价式量词辖域变换等价式: xP(x)Q x(P(x)Q) xP(x)Q x(P(x)Q) xP(x)Q x(P(x)Q) xP(x)Q x(P(x)Q)Q中不含变量中不含变量附附1

49、1：谓词演算的基本等价式谓词演算的基本等价式4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性 全称量词消去规则全称量词消去规则: xP(x)P(y) 全称量词引入规则全称量词引入规则: P(y) xP(x) 存在量词消去规则存在量词消去规则: xQ(x)Q(c)(c为常量为常量) 存在量词引人规则存在量词引人规则: Q(c) xQ(x) 有限域量词消去规则有限域量词消去规则:设有限个体域为设有限个体域为D d1,d2,dn xP(x)P(d1)P(d2),P(dn) xQ(x)Q(d1) Q(d2),Q(dn)附附2 2：量词消去及引入规则量词消去及引入规则4.2.2 谓词公式

50、的永真性和可满足性谓词公式的永真性和可满足性n 定义定义4.6 对谓词公式对谓词公式P和和Q，如果，如果PQ永真，则称永真，则称P 永真蕴永真蕴含含Q，且称，且称Q为为P的逻辑结论，的逻辑结论，P为为Q的前提。的前提。记作记作P Q。 4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n4、谓词公式的等价性与永真蕴含、谓词公式的等价性与永真蕴含n推理规则：推理规则：nP规则：规则：在推理的任何步骤上都可引入前提。在推理的任何步骤上都可引入前提。nT规则：规则：推理时，如果前面步骤中有一个或多个永真蕴含公式推理时，如果前面步骤中有一个或多个永真蕴含公式S，则可把，则可把S引入推理过

51、程中。引入推理过程中。nCP规则：规则：如果能从如果能从R和前提集合中推出和前提集合中推出S来，则可从前提集合推出来，则可从前提集合推出RS。n反证法：反证法： P Q，当且仅当，当且仅当P Q F，即，即Q为为P的逻辑结论，当且仅的逻辑结论，当且仅当当P Q 是不可满足的。是不可满足的。由此得到如下定理：由此得到如下定理：定理定理4.1：Q为为P1,P2,Pn的逻辑的逻辑结论，当且仅当（结论，当且仅当（ P1P2 Pn)Q是不可满足的。是不可满足的。 n常用的永真蕴含式如下：常用的永真蕴含式如下：n (1) 化简式化简式 PQ P， PQ Qn (2) 附加式附加式 P PQ， Q PQn

52、(3) 析取三段论析取三段论 P, PQ Qn (4) 假言推理假言推理 P, PQ Qn (5) 拒取式拒取式 Q, PQ Pn (6) 假言三段论假言三段论 PQ, QR PRn (7) 二难推理二难推理 PQ, PR, QR R n (8) 全称固化全称固化 (x)P(x) P(y)n 其中，其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。是个体域中的任一个体，依此可消去谓词公式中的全称量词。n (9) 存在固化存在固化 (x)P(x) P(y)n 其中，其中，y是个体域中某一个可以使是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公为真的个体，依此可消去谓词公式中

53、的存在量词。式中的存在量词。4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n4、谓词公式的等价性与永真蕴含、谓词公式的等价性与永真蕴含4.2 推理的逻辑基础推理的逻辑基础n4.2.1 谓词与个体谓词与个体n4.2.2 谓词公式的永真性和可满足性谓词公式的永真性和可满足性n4.2.3 置换与合一置换与合一n置换可简单的理解为是在一个谓词公式中用置换项去替换变量。置换可简单的理解为是在一个谓词公式中用置换项去替换变量。n定义定义4.74.7 置换是形如置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，的有限集合。其中，t1,t2,tn是项；是项；x1,x2,xn是互不

54、相同的变元；是互不相同的变元；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之间出现了循之间出现了循环置换现象。通常，置换是用希腊字母环置换现象。通常，置换是用希腊字母、 、 等来表示的。等来表示的。n不含任何元素的置换称为空置换，以不含任何元素的置换称为空置换，以 表示。表示。4.2.3 置换与合一置换与合一n1、置换、置换(1)

55、 空置换空置换 是左么元和右么元，即对任意的置换是左么元和右么元，即对任意的置换 , 恒有恒有 (2) 对任意表达式对任意表达式E，恒有，恒有E( )(E ) 。(3) 若对任意表达式若对任意表达式E恒有恒有E E ，则，则 。(4) 对任意置换对任意置换 ， ， , 恒有恒有 即置换的合成满足结合律。即置换的合成满足结合律。(5) 设设A和和B为表达式集合，则为表达式集合，则 注意注意: 置换的合成不满足交换律。置换的合成不满足交换律。()ABAB n2、置换的性质、置换的性质4.2.3 置换与合一置换与合一n3、置换乘法、置换乘法定义定义4.8 设设 =t1/x1,t2/x2,tn/xn

56、= 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)； 当当yj x1, x2 , xn 时，删去时，删去uj/yj (j=1, 2 , m)最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。4.2.3 置换与合一置换与合一n例例4.2 设设= f(y)/x, z/y

57、，=a/x, b/y ,y/z ，求，求与与的合成。的合成。n 解解:先求出集合先求出集合n f(y)/x, (z)/y, a/x, b/y , y/z=f(b)/x, y/y, a/x, b/y , y/zn其中，其中，f(b)/x中的中的f(b)是置换是置换作用于作用于f(y)的结果；的结果；y/y 中的中的y是置是置换换作用于作用于z的结果。在该集合中，的结果。在该集合中，y/y满足定义中的条件，满足定义中的条件，需要删除；需要删除；a/x和和b/y满足定义中的条件，也需要删除。最后满足定义中的条件，也需要删除。最后得得:=f(b)/x, y/zn3、置换乘法、置换乘法4.2.3 置换与

58、合一置换与合一n合一合一可理解为可理解为是寻找项对变量的置换，使两个谓词公式一致是寻找项对变量的置换，使两个谓词公式一致。可定。可定义为：义为：n定义定义4.94.9 设有公式集设有公式集F=F1, F2,Fn，若存在一个置换，若存在一个置换，可使，可使n F1=F2=Fn，n则称则称是是F的一个合一。称的一个合一。称F1,F2,Fn是可合一的。是可合一的。n 例例4.34.3 设有公式集设有公式集F=P(x,y,f(y), P(a,g(x),z)，则，则n =a/x, g(a)/y, f(g(a)/zn是它的一个合一。是它的一个合一。n 一般来说，一个公式集的合一不是唯一的。一般来说，一个公

59、式集的合一不是唯一的。n4、合一、合一4.2.3 置换与合一置换与合一n定义定义4.104.10 设设是公式集是公式集F的一个合一，如果对的一个合一，如果对F的任一个的任一个合一合一都存在一个置换都存在一个置换，使得，使得=，则称，则称是一个最一是一个最一般合一般合一(MGU)。n 一个公式集的最一般合一是唯一的。一个公式集的最一般合一是唯一的。n5、最一般合一、最一般合一(MGU, Most General Unifier)4.2.3 置换与合一置换与合一n6、MGU算法算法4.2.3 置换与合一置换与合一 定义定义4.11 表达式的非空集合表达式的非空集合W的差异集的差异集(differe

60、nce set)是按下述是按下述方法得出的子表达式的集合方法得出的子表达式的集合： （1）在在W的所有表达式中找出对应符号不全相同的第一个符号的所有表达式中找出对应符号不全相同的第一个符号(自左算起自左算起)。 （2）在在W的每个表达式中的每个表达式中，提取出占有该符号位置的子表达式提取出占有该符号位置的子表达式。这些子表达式的集合便是。这些子表达式的集合便是W的的差异集差异集D。例例4.44.4：W=P(x,f(y,z),P(x,a),P(x,g(h(k(x),在在W的的3个表达式中，个表达式中，前前4个符号个符号-“P(x,”是相同的，第是相同的，第5个符号不全相同，所以个符号不全相同，所