确定性推理幻灯片.ppt

《确定性推理幻灯片.ppt》由会员分享，可在线阅读，更多相关《确定性推理幻灯片.ppt（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、确定性推理第1页，共120页，编辑于2022年，星期一3.1 推理的基本概念推理的基本概念3.1.1什么是推理什么是推理3.1.2推理方法及其分类推理方法及其分类3.1.3推理的控制策略及其分类推理的控制策略及其分类3.1.4正向推理正向推理3.1.5逆向推理逆向推理3.1.6混合推理混合推理2第2页，共120页，编辑于2022年，星期一3.1.1什么是推理什么是推理推理的概念推理的概念 是指按照某种策略从已知事实出发去推出结论的过程。是指按照某种策略从已知事实出发去推出结论的过程。推理所用的事实：推理所用的事实：初始证据：初始证据：推理前用户提供的推理前用户提供的 中间结论：中间结论：推理过

2、程中所得到的推理过程中所得到的 推理过程：推理过程：由推理机来完成，所谓推理机就是智能系统中用来实由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。现推理的那些程序。例如，例如，医疗专家系统，专家知识保存在知识库中。推理开始时，先把医疗专家系统，专家知识保存在知识库中。推理开始时，先把病人的症状和检查结果放到综合数据库中，然后再从综合数据库的初始证病人的症状和检查结果放到综合数据库中，然后再从综合数据库的初始证据出发，按照某种策略在知识库中寻找，并使用知识，直到推出最终结论据出发，按照某种策略在知识库中寻找，并使用知识，直到推出最终结论为止。为止。推理的两个基本问题推理的两个基本

3、问题 推理的方法：推理的方法：解决前提和结论的逻辑关系，不确定性传递解决前提和结论的逻辑关系，不确定性传递 推理的控制策略：推理的控制策略：解决推理方向，冲突消解策略解决推理方向，冲突消解策略3第3页，共120页，编辑于2022年，星期一3.1.2推理方法及其分类推理方法及其分类1.按推理的逻辑基础分类按推理的逻辑基础分类(1/4)可分为演绎推理、归纳推理等可分为演绎推理、归纳推理等 演绎推理演绎推理演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三

4、段论，如某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论，如假言假言推理、拒取式和假言三段论推理、拒取式和假言三段论。例：例：假言三段论假言三段论AB，BCAC常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，大前提大前提是已知的一般性知识或推理过程得到的判断；是已知的一般性知识或推理过程得到的判断；小前提小前提是关于某种具体情况或某个具是关于某种具体情况或某个具体实例的判断；体实例的判断；结论结论是由大前提推出的，并且适合于小前提的判断。是由大前提推出的，并且适合于小前提的判断。例如，有

5、如下三个判断：例如，有如下三个判断：计算机系的学生都会编程序；计算机系的学生都会编程序；（一般性知识）（一般性知识）程强是计算机系的一位学生；程强是计算机系的一位学生；（具体情况）（具体情况）程强会编程序。程强会编程序。（结论）（结论）这是一个三段论推理。其中，这是一个三段论推理。其中，是大前提，是大前提，是小前提；是小前提；是经演绎推出来是经演绎推出来的结论。的结论。可见，其结论是蕴含在大前提中的。可见，其结论是蕴含在大前提中的。4第4页，共120页，编辑于2022年，星期一3.1.2推理方法及其分类推理方法及其分类1.按推理的逻辑基础分类按推理的逻辑基础分类(2/4)归纳推理归纳推理是一种

6、由个别到一般的推理方法。归纳推理的类型是一种由个别到一般的推理方法。归纳推理的类型按照所选事例的广泛性按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理可分为完全归纳推理和不完全归纳推理按照推理所使用的方法按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等可分为枚举、类比、统计和差异归纳推理等完全归纳推理完全归纳推理是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。种属性，推出该类事物是否具有此属性。如，计算机质量检验。不完全归纳推理不完

7、全归纳推理是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，计是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，计算机，随机抽查。算机，随机抽查。枚举归纳推理枚举归纳推理是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。该类事物都具有此种属性。例如，设有如下事例：例如，设有如下事例：王强是计算机系学生，他会编程序；王强是计算机系学生，他会编程序；高华是计算机系学生，她会编程序；高华是计算机系学生，她会编程序；当这些

8、具体事例足够多时，就可归纳出一个一般性的知识：当这些具体事例足够多时，就可归纳出一个一般性的知识：凡是计算机系的学生，就一定会编程序。凡是计算机系的学生，就一定会编程序。5第5页，共120页，编辑于2022年，星期一3.1.2推理方法及其分类推理方法及其分类1.按推理的逻辑基础分类按推理的逻辑基础分类(3/4)类比归纳推理类比归纳推理是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。其他属性上也相同或相似的一种归纳推理。设设A、B分别是两类事物的集合：分别是两类事物的集合：A=a1,

9、a2,B=b1,b2,并设并设ai与与bi总是成对出现，且当总是成对出现，且当ai有属性有属性P时，时，bi就有属性就有属性Q与此对应，即与此对应，即P(ai)Q(bi)i=1,2,.则当则当A与与B中有一新的元素对出现时，若已知中有一新的元素对出现时，若已知a有属性有属性P，b有属性有属性Q，即，即P(a)Q(b)类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。6第6页，共120

10、页，编辑于2022年，星期一3.1.2推理方法及其分类推理方法及其分类 1.按推理的逻辑基础分类按推理的逻辑基础分类(4/4)演绎推理与归纳推理的区别演绎推理与归纳推理的区别演绎推理演绎推理是在已知领域内的一般性知识的前提下，通是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它演绎推理只不过是将已有事实揭露出来，因此它不能增不能增殖新知识殖新知识。归纳推理归纳推理所推出的

11、结论是没有包含在前提内容中的。这种所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，由个别事物或现象推出一般性知识的过程，是增殖新知识是增殖新知识的的过程。过程。例如，例如，一位计算机维修员，从书本知识，到通过大量实例一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种积累经验，是一种归纳归纳推理方式。运用这些一般性知识知推理方式。运用这些一般性知识知识去维修计算机的过程则是识去维修计算机的过程则是演绎演绎推理。推理。7第7页，共120页，编辑于2022年，星期一3.1.3推理的控制策略及其分类推理的控制策略及其分类推理的控制策略推理的控制策略 推理过程不

12、仅依赖于所用的推方法，同时也依赖于推理的控制策略。推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略。推理的控制策略是指推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略如何使用领域知识使推理过程尽快达到目标的策略。控制策略的分类控制策略的分类 由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为为推理策略和搜索策略推理策略和搜索策略。推理策略推理策略 主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略

13、、限制策略、冲突消解策略等策略、冲突消解策略等 推理方向控制策略推理方向控制策略用于确定推理的控制方向，可分为正向推理、逆向推理、混合用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理。推理及双向推理。求解策略求解策略是指仅求一个解，还是求所有解或最优解等。是指仅求一个解，还是求所有解或最优解等。限制策略限制策略是指对推理的深度、宽度、时间、空间等进行的限制。是指对推理的深度、宽度、时间、空间等进行的限制。冲突消解策略冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。

14、最佳知识用于推理的策略。搜索策略搜索策略 主要解决主要解决推理线路、推理效果、推理效率等问题推理线路、推理效果、推理效率等问题。本章主要讨论推理策略，至于搜本章主要讨论推理策略，至于搜索策略将放到第索策略将放到第4章单独讨论。章单独讨论。8第8页，共120页，编辑于2022年，星期一3.1.4正向推理正向推理推理算法推理算法从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。算法描述算法描述(1)把用户提供的初始证据放入综合数据库；把用户提供的初始证据放入综合数据库；(2)检查综合数据库中是否包含了问题的解，若已包

15、含，则求解结束，并成功推检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；出；否则执行下一步；(3)检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。(4)按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转事实加入综合数据库种，然后转(2)。(5)询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合询问用户是否可以进

16、一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转数据库中，然后转(3)；否则表示无解，失败退出。；否则表示无解，失败退出。至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。法和冲突消解策略，以后将会分别讨论。其流程图如下：其流程图如下：9第9页，共120页，编辑于2022年，星期一把初始证据放入把初始证据放入DBDB中有解吗？中

17、有解吗？KB中有可用知识吗？中有可用知识吗？形成可用知识集形成可用知识集可用知识集空吗？可用知识集空吗？按照冲突消解策略从该知识按照冲突消解策略从该知识集中选出一条知识进行推理集中选出一条知识进行推理 推出的是新事实吗？推出的是新事实吗？将新事实加入到将新事实加入到DB把用户补充的新事把用户补充的新事实加入到实加入到DB中中 用户可补充新事实吗？用户可补充新事实吗？失败退出失败退出 成功退出成功退出YNNYNNNYYY10第10页，共120页，编辑于2022年，星期一3.1.4正向推理正向推理推理例子推理例子例例3.1请用正向推理完成以下问题的求解请用正向推理完成以下问题的求解假设知识库中包含

18、有以下假设知识库中包含有以下2条规则：条规则：r1：IFBTHENCr2：IFATHENB已知初始证据已知初始证据A，求证目标，求证目标C。解：本例的推理过程如下：解：本例的推理过程如下：推理开始前，综合数据库为空。推理开始前，综合数据库为空。推理开始后，先把推理开始后，先把A放入综合数据库，然后检查综合数据库中是否含有该问题的放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为解，回答为“N”。接着检查知识库中是否有可用知识，显然接着检查知识库中是否有可用知识，显然r2可用，形成仅含可用，形成仅含r2的知识集。从该知识集中取出的知识集。从该知识集中取出r2，推出新的实事，推出新的实

19、事B，将，将B加入综合数据库，检查综合数据库中是否含有目标加入综合数据库，检查综合数据库中是否含有目标C，回答为，回答为“N”。再检查知识库中是否有可用知识，此时由于再检查知识库中是否有可用知识，此时由于B的加入使得的加入使得r1为可用，形成仅含为可用，形成仅含r1的的知识集。从该知识集中取出知识集。从该知识集中取出r1，推出新的实事，推出新的实事C，将，将C加入综合数据库，检查综合数据库加入综合数据库，检查综合数据库中是否含有目标中是否含有目标C，回答为，回答为“Y”。它说明综合数据库中已经含有问题的解，推理成功结束，目标它说明综合数据库中已经含有问题的解，推理成功结束，目标C得证。得证。1

20、1第11页，共120页，编辑于2022年，星期一3.1.4正向推理正向推理优缺点优缺点正向推理的主要优点正向推理的主要优点 比较直观，允许用户主动提供有用的事实信息，适合于诊断、比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。设计、预测、监控等领域的问题求解。正向推理的主要缺点正向推理的主要缺点 推理无明确目标，求解问题是可能会执行许多与解无关的操作，推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。导致推理效率较低。12第12页，共120页，编辑于2022年，星期一3.1.5逆向推理逆向推理推理算法推理算法从某个假设目标出发，逆

21、向使用规则，亦称为目标驱动推理或逆向链推理。从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。算法描述：算法描述：(1)将要求证的目标（称为假设）构成一个假设集；将要求证的目标（称为假设）构成一个假设集；(2)从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，；若该假设不在数据库中，则执行下一步；则执行下一步；(3)检查该假设是否可由知识库的某个知识导出，若不能由某个知

22、识导出，则询问用检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一步；若能由某个知识导出，则执行下一步；(4)将知识库中可以导出该假设的所有知识构成一个可用知识集；将知识库中可以导出该假设的所有知识构成一个可用知识集；(5)检查可用知识集是否为空，若是，失败退出；否则执行下一步；检查可用知识集是否为空，若是，失败退出；否

23、则执行下一步；(6)按冲突消解策略从可用知识集中取出一个知识，继续；按冲突消解策略从可用知识集中取出一个知识，继续；(7)将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。其流程图如下：其流程图如下：13第13页，共120页，编辑于2022年，星期一初始化初始化DB和假设集和假设集该假设是该假设是DB中的事实吗？中的事实吗？该假设能被该假设能被KB中中的知识导出吗？的知识导出吗？从假设集中取出一个假设从假设集中取出一个假设可用知识集空吗？可用知识集空吗？按照冲突消解策略从该知识集按照冲突消解策略从该知识集中选出一条知

24、识中选出一条知识将该知识前提中的每个子条件作将该知识前提中的每个子条件作为新的假设加入假设集为新的假设加入假设集该假设成立该假设成立并放入并放入DB还有新的假设吗？还有新的假设吗？失败退出失败退出成功退出成功退出YNYYNNNNY将将KB中所有能导出此假设的知中所有能导出此假设的知识构成一个可用知识集识构成一个可用知识集 询问用户有此询问用户有此事实吗？事实吗？该假设该假设 成立成立Y14第14页，共120页，编辑于2022年，星期一3.1.5逆向推理逆向推理推理例子推理例子对上例，采用逆向推理，其推理过程如下：对上例，采用逆向推理，其推理过程如下：推理开始前，综合数据库和假设集均为空。推理开

25、始前，综合数据库和假设集均为空。推理开始后，先将初始证据推理开始后，先将初始证据A和目标和目标C分别放入综合数据库和假设集，然后从分别放入综合数据库和假设集，然后从假设集中取出一个假设假设集中取出一个假设C，查找，查找C是否为综合数据库中的已知事实，回答为是否为综合数据库中的已知事实，回答为“N”。再检查再检查C是否能被知识库中的知识所导出，发现是否能被知识库中的知识所导出，发现C可由可由r1导出，于是导出，于是r1被放入可被放入可用知识集。由于知识库中只有用知识集。由于知识库中只有r1可用，故可用知识集中仅含可用，故可用知识集中仅含r1。接着从可用知识集中取出接着从可用知识集中取出r1，将其

26、前提条件，将其前提条件B作为新的假设放入假设集。从假作为新的假设放入假设集。从假设集中取出设集中取出B，检查，检查B是否为综合数据库中的实事，回答为是否为综合数据库中的实事，回答为“N”。再检查。再检查B是否能被知是否能被知识库中的知识所导出，发现识库中的知识所导出，发现B可由可由r2导出，于是导出，于是r2被放入可用知识集。由于知识库中被放入可用知识集。由于知识库中只有只有r2可用，故可用知识集中仅含可用，故可用知识集中仅含r2。从可用知识集中取出从可用知识集中取出r2，将其前提条件，将其前提条件A作为新的假设放入假设集。然后从假设集中作为新的假设放入假设集。然后从假设集中取出取出A，检查，

27、检查A是否为综合数据库中的实事，回答为是否为综合数据库中的实事，回答为“Y”。他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。得证。15第15页，共120页，编辑于2022年，星期一3.1.5逆向推理逆向推理优缺点优缺点逆向推理的主要优点逆向推理的主要优点 不必寻找和使用那些与假设目标无关的信息和知识不必寻找和使用那些与假设目标无关的信息和知识 推理过程的目标明确推理过程的目标明确 也也有有利利于于向向用用户户提提供供解解释释，在在诊诊断断性性专专家家系系统统中中较较为为有有效。效。逆向推理的主要缺点逆向推理的

28、主要缺点 当当用用户户对对解解的的情情况况认认识识不不请请时时，由由系系统统自自主主选选择择假假设设目目标标的的盲盲目目性性比比较较大大，若若选选择择不不好好，可可能能需需要要多多次次提提出出假假设设，会会影影响系统效率。响系统效率。16第16页，共120页，编辑于2022年，星期一3.1.6混合推理混合推理混合推理的概念混合推理的概念把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。决较复杂问题的方法。混合推理的方法混合推理的方法1.先正向后逆向先正向后逆向这种方法先进行正向推理，从已知事实出发推出

29、部分结果，然后再用逆向这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。推理对这些结果进行证实或提高它们的可信度。2.先逆向后正向先逆向后正向这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。后再用正向推理对这些中间假设进行证实。3.双向混合双向混合是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。对于这些方法我不再详细讨论。对于这些方法我不再详细讨论。1

30、7第17页，共120页，编辑于2022年，星期一第3章 确定性推理 3.1推理的基本概念推理的基本概念3.2推理的逻辑基础推理的逻辑基础3.3自然演绎推理自然演绎推理3.4归结演绎推理归结演绎推理3.5基于规则的演绎推理基于规则的演绎推理18第18页，共120页，编辑于2022年，星期一3.2推理的逻辑基础推理的逻辑基础3.2.1谓词公式的解释谓词公式的解释3.2.2谓词公式的永真性和可满足性谓词公式的永真性和可满足性3.2.3谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性3.2.4谓词公式的范式谓词公式的范式3.2.5置换与合一置换与合一19第19页，共120页，编辑于2022年，

31、星期一3.2.1谓词公式的解释谓词公式的解释概念概念命题公式的解释命题公式的解释在命题逻辑中，在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。题变元的一次真值指派。有了命题公式的解释，就可据此求出该命题公式的真值。有了命题公式的解释，就可据此求出该命题公式的真值。谓词公式的解释谓词公式的解释由于谓词公式中可能包含由个体由于谓词公式中可能包含由个体常量、变元或函数常量、变元或函数，因此，必须，因此，必须先考虑这些个体常量和函数在个体域上的取值，然后才能根据它们的先考虑这些个体常量和函数在个体域上的取值，然后才能根据它们的具体

32、取值为谓词分别指派真值。具体取值为谓词分别指派真值。定义定义3.1设设D是谓词公式是谓词公式P的非空个体域，若对的非空个体域，若对P中的个体常量、函中的个体常量、函数和谓词按如下规定赋值：数和谓词按如下规定赋值：(1)为每个个体常量指派为每个个体常量指派D中的一个元素；中的一个元素；(2)为每个为每个n元函数指派一个从元函数指派一个从Dn到到D的一个映射，其中的一个映射，其中Dn=(x1,x2,xn)|x1,x2,xnD(3)为每个为每个n元谓词指派一个从元谓词指派一个从Dn到到F，T的映射。的映射。则称这些指派为则称这些指派为P在在D上的一个解释上的一个解释I 20第20页，共120页，编辑

33、于2022年，星期一3.2.1谓词公式的解释谓词公式的解释 例子一例子一(1/2)例例3.2设个体域设个体域D=1,2，求公式，求公式A=(x)(y)P(x,y)在在D上的解释，上的解释，并指出在每一种解释下公式并指出在每一种解释下公式A的真值。的真值。解：解：由于公式由于公式A中没有包含个体常量和函数，故可直接为谓词指派真值，中没有包含个体常量和函数，故可直接为谓词指派真值，设有设有这就是公式这就是公式A在在D上的一个解释。从这个解释可以看出：上的一个解释。从这个解释可以看出：当当x=1、y=1时，有时，有P(x,y)的真值为的真值为T;当当x=2、y=1时，有时，有P(x,y)的真值为的真

34、值为T;即对即对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 F21第21页，共120页，编辑于2022年，星期一3.2.1谓词公式的解释谓词公式的解释 例子一例子一(2/2)说明：说明：一个谓词公式在其个体域上的解释不是唯一的。例如，对公式一个谓词公式在其个体域上的解释不是唯一的。例如，对公式A，若给出另一组真值指派，若给出另一组真值指派这也是公式这也是公式A在在D上的一个解释。从这个解释可以看出：上的一个解释。从这个解释可以

35、看出：当当x=1、y=1时，有时，有P(x,y)的真值为的真值为T;当当x=2、y=1时，有时，有P(x,y)的真值为的真值为F;即对即对x在在D上的任意取值，不存在一个上的任意取值，不存在一个y使得使得P(x,y)的真值为的真值为T。因此，。因此，在此解释下公式在此解释下公式A的真值为的真值为F。实际上，实际上，A在在D上共有上共有16种解释，这里就不在一一列举。种解释，这里就不在一一列举。P(1,1)P(1,2)P(2,1)P(2,2)TT F F22第22页，共120页，编辑于2022年，星期一3.2.1谓词公式的解释谓词公式的解释 例子二例子二例例3.3设个体域设个体域D=1,2，求公

36、式，求公式B=(x)P(f(x),a)在在D上的解释，并指出在该解释下公式上的解释，并指出在该解释下公式B的真值。的真值。解：解：设对个体常量设对个体常量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上的任意取值，都存在上的任意取值，都存

37、在a=1使使P(f(x),a)的真值为的真值为T。因此，在此解释下公式。因此，在此解释下公式B的真值为的真值为T。由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为解释下真值为T，而在另一个解释下为，而在另一个解释下为F。af(1)F(2)112P(1,1)P(1,2)P(2,1)P(2,2)T T23第23页，共120页，编辑于2022年，星期一3.2.2谓词公式的永真性和可满足性谓词公式的永真性和可满足性为了以后推理的需要，下面先定义：为了以后推理的需要，下面先定义：定义定义3

38、.2如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释都取得真值上的任一解释都取得真值T，则称，则称P在在D上是永真上是永真的；如果的；如果P在任何非空个体域上均是永真的，则称在任何非空个体域上均是永真的，则称P永真永真。可见，要判定一谓词公式为永真，必须对每个非空个体域上的每可见，要判定一谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时，尽管工作量大，公个解释逐一进行判断。当解释的个数为有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就很难判定了。很难判定

39、了。定义定义3.3对于谓词公式对于谓词公式P，如果至少存在，如果至少存在D上的一个解释，使公式上的一个解释，使公式P在此解释下的真值为在此解释下的真值为T，则称公式，则称公式P在在D上是可满足上是可满足的。的。谓词公式的谓词公式的可满足性也称为相容性可满足性也称为相容性。定义定义3.4如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释都取真值上的任一解释都取真值F，则，则称称P在在D上是永假上是永假的；如果的；如果P在任何非空个体域上均是永假的，则称在任何非空个体域上均是永假的，则称P永永假假。谓词公式的永假性又称谓词公式的永假性又称不可满足性或不相容不可满足性或不相容。后面我们

40、要给出的归结推理，就是采用一种逻辑上的反证法，将后面我们要给出的归结推理，就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。永真性转换为不可满足性的证明。24第24页，共120页，编辑于2022年，星期一3.2.3谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性1.等价式等价式(1/2)谓词公式的谓词公式的等价性等价性和和永真蕴含性永真蕴含性可分别用相应的可分别用相应的等价式等价式和和永真蕴含式永真蕴含式来表示，这些等价式和永真蕴含式都是演绎来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规则。推理的主要依据，因此也称它们为推理规则。谓词公式的谓词公式

41、的等价式可定义如下等价式可定义如下：定义定义3.5设设P与与Q是是D上的两个谓词公式，若对上的两个谓词公式，若对D上的任上的任意解释，意解释，P与与Q都有相同的真值，则称都有相同的真值，则称P与与Q在在D上是等价的。上是等价的。如果如果D是任意非空个体域，则称是任意非空个体域，则称P与与Q是等价的，记作是等价的，记作PQ。25第25页，共120页，编辑于2022年，星期一3.2.3谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性 1.等价式等价式(2/2)(1)双重否定律双重否定律PP(2)交换律交换律(PQ)(QP)，(PQ)(QP)(3)结合律结合律(PQ)RP(QR)(PQ)RP

42、(QR)(4)分配律分配律P(QR)(PQ)(PR)P(QR)(PQ)(PR)(5)摩根定律摩根定律(PQ)PQ(PQ)PQ(6)吸收律吸收律P(PQ)PP(PQ)P(7)补余律补余律PPT,PPF(8)连词化归律连词化归律PQPQPQ(PQ)(QP)PQ(PQ)(QP)(9)量词转换律量词转换律(x)P(x)(P)(x)P(x)(P)(10)量词分配律量词分配律(x)(PQ)(x)P(x)Q(x)(PQ)(x)P(x)Q26第26页，共120页，编辑于2022年，星期一3.2.3谓词公式的等价性和永真蕴含性谓词公式的等价性和永真蕴含性2.永真蕴含式永真蕴含式定义定义3.6对谓词公式对谓词公式

43、P和和Q，如果，如果PQ永真，则称永真，则称P永真蕴含永真蕴含Q，且称，且称Q为为P的逻辑的逻辑结论，结论，P为为Q的前提，记作的前提，记作PQ。常用的永真蕴含式如下：常用的永真蕴含式如下：(1)化简式化简式PQP，PQQ(2)附加式附加式PPQ，QPQ(3)析取三段论析取三段论P,PQQ(4)假言推理假言推理P,PQQ(5)拒取式拒取式Q,PQP(6)假言三段论假言三段论PQ,QRPR(7)二难推理二难推理PQ,PR,QRR(8)全称固化全称固化(x)P(x)P(y)其中，其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。是个体域中的任一个体，依此可消去谓词公式中的全称量词。(9

44、)存在固化存在固化(x)P(x)P(y)其中，其中，y是个体域中某一个可以使是个体域中某一个可以使P(y)为真的个体，依此可消去谓词公式中的存在量词。为真的个体，依此可消去谓词公式中的存在量词。27第27页，共120页，编辑于2022年，星期一3.2.4谓词公式的范式谓词公式的范式范式是谓词公式的标准形式。在谓词逻辑中，范式分为两种：范式是谓词公式的标准形式。在谓词逻辑中，范式分为两种：前束范式前束范式定义定义3.7设设F为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称面，且它们的辖域为整个公式

45、，则称F为前束范式。一般形式：为前束范式。一般形式：(Q1x1)(Qnxn)M(x1,x2,xn)其中，其中，Qi(i=1,2,n)为前缀，它是一个由全称量词或存在量词组成的量词串；为前缀，它是一个由全称量词或存在量词组成的量词串；M(x1,x2,xn)为母式，它是一个不含任何量词的谓词公式。为母式，它是一个不含任何量词的谓词公式。例如例如，(x)(y)(z)(P(x)Q(y,z)R(x,z)是前束范式。是前束范式。任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集的化简中讨任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集的化简中讨论。论。Skolem范式范式定义

46、定义3.8如果前束范式中如果前束范式中所有的存在量词都在全称量词之前所有的存在量词都在全称量词之前，则称这种形式的谓词公，则称这种形式的谓词公式为式为Skolem范式。范式。例如例如，(x)(z)(y)(P(x)Q(y,z)R(x,z)是是Skolem范式。范式。任一谓词公式均可化为与其对应的任一谓词公式均可化为与其对应的Skolem范式，其化简方法也将在后面子句集的化范式，其化简方法也将在后面子句集的化简中讨论。简中讨论。28第28页，共120页，编辑于2022年，星期一3.2.5置换与合一置换与合一概念在不同谓词公式中，往往会出现谓词名相同但其个体不同在不同谓词公式中，往往会出现谓词名相同

47、但其个体不同的情况，此时推理过程是不能直接进行匹配的，需要先进行的情况，此时推理过程是不能直接进行匹配的，需要先进行置换。置换。例如，可根据例如，可根据全称固化全称固化推理和推理和假言推理假言推理由谓词公式由谓词公式W1(A)和和(x)(W1(x)W2(x)推出推出W2(A)。对谓词。对谓词W1(A)可看作是由全程固化推理（即可看作是由全程固化推理（即(x)(W1(x)W1(A)推出的，其中推出的，其中A是任一个体常量。要使用假言推理，是任一个体常量。要使用假言推理，首先需要找到项首先需要找到项A对变元对变元x的的置换置换，使，使W1(A)与与W1(x)一致。一致。这种寻找项对变元的置换，使谓

48、词一致的过程叫做这种寻找项对变元的置换，使谓词一致的过程叫做合一的过合一的过程程。下面讨论置换与合一的有关概念与方法。下面讨论置换与合一的有关概念与方法。29第29页，共120页，编辑于2022年，星期一3.2.5置换与合一置换与合一1.置换置换(1/2)置换可简单的理解为是在一个谓词公式中用置换项去替换变量。置换可简单的理解为是在一个谓词公式中用置换项去替换变量。定义定义3.9置换是形如置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，的有限集合。其中，t1,t2,tn是项；是项；x1,x2,xn是互不相同的变元；是互不相同的变元；ti/xi表示用表示用ti替换替换xi。并。并且

49、要求且要求ti与与xi不能相同，不能相同，xi不能循环地出现在另一个不能循环地出现在另一个ti中。中。例如，例如，a/x,c/y,f(b)/z是一个置换。是一个置换。但但g(y)/x,f(x)/y不是一个置换。原因是它在不是一个置换。原因是它在x与与y之间出现了循环置换现象。即当用之间出现了循环置换现象。即当用g(y)置换置换x,用用f(g(y)置换置换y时，既没有消去时，既没有消去x，也没有消去，也没有消去y。若改为若改为g(a)/x,f(x)/y即可，原因是用即可，原因是用g(a)置换置换x，用，用f(g(a)置换置换y，则消去了，则消去了x和和y。通常，置换是用希腊字母通常，置换是用希腊

50、字母、等来表示的。等来表示的。定义定义3.10设设=t1/x1,t2/x2,tn/xn是一个置换，是一个置换，F是一个谓词公式，把公式是一个谓词公式，把公式F中出现的中出现的所有所有xi换成换成ti(i=1,2,n)，得到一个新的公式，得到一个新的公式G，称，称G为为F在置换在置换下的下的例示例示，记作，记作G=F。一个谓词公式的任何例示都是该公式的逻辑结论。一个谓词公式的任何例示都是该公式的逻辑结论。30第30页，共120页，编辑于2022年，星期一3.2.5置换与合一置换与合一1.置换置换(2/2)定义定义3.11设设=t1/x1,t2/x2,tn/xn=u1/y1,u2/y2,um/ym