人工智能第四章经典逻辑推理优秀课件.ppt

《人工智能第四章经典逻辑推理优秀课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第四章经典逻辑推理优秀课件.ppt（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能第四章经典逻辑人工智能第四章经典逻辑推理推理第1页，本讲稿共95页第第4章章 经典逻辑推理经典逻辑推理 l智能系统的推理过程实际上就是一种思维过程。智能系统的推理过程实际上就是一种思维过程。即运用即运用知识知识进行推理来进行推理来求解问题求解问题。l经典逻辑推理是根据经典逻辑（命题逻辑及一阶谓经典逻辑推理是根据经典逻辑（命题逻辑及一阶谓词逻辑）的逻辑规则进行的一种推理。词逻辑）的逻辑规则进行的一种推理。l由于这种推理是基于经典逻辑的，其真值只有由于这种推理是基于经典逻辑的，其真值只有“真真”和和“假假”两种，因此它是一种精确推理，或称为两种，因此它是一种精确推理，或称为确定性确定性推理

2、。推理。2第2页，本讲稿共95页4.1 推理的基本概念推理的基本概念l4.1.1 推理方式及其分类推理方式及其分类l4.1.2 推理的控制策略推理的控制策略l4.1.3 模式匹配及其变量代换模式匹配及其变量代换3第3页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类1.按推理的逻辑基础分类按推理的逻辑基础分类l演绎推理演绎推理l归纳推理归纳推理l默认推理默认推理4第4页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类（1）演绎推理）演绎推理 演绎推理是从已知的一般性知识出发，去推出蕴含演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论

3、。是在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论，一种由一般到个别的推理方法，其核心是三段论，如如 假言推理、拒取式和假言三段论。假言推理、拒取式和假言三段论。5第5页，本讲稿共95页（1）演绎推理）演绎推理 例：例：假言三段论假言三段论 AB，BC AC 常用的三段论是由一个大前提、一个小前提和一个结论常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。这三部分组成的。大前提大前提是已知的一般性知识或推理过程得到的判断；是已知的一般性知识或推理过程得到的判断；小前提小前提是关于某种具体情况或某个具体实例的判断；是关于某种具体情况或某个具

4、体实例的判断；结论结论是由大前提推出的，并且适合于小前提的判断。是由大前提推出的，并且适合于小前提的判断。4.1.1 推理方法及其分类推理方法及其分类6第6页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类（1）演绎推理）演绎推理例，有如下三个判断：例，有如下三个判断：计算机系的学生都会编程序；计算机系的学生都会编程序；（一般性知识）（一般性知识）程强是计算机系的一位学生；程强是计算机系的一位学生；（具体情况）（具体情况）程强会编程序。程强会编程序。（结论）（结论）这是一个三段论推理。这是一个三段论推理。其中，其中，是大前提，是大前提，是小前提；是小前提；是经演绎推出来的结论。是经

5、演绎推出来的结论。可见，其结论是蕴含在大前提中的。可见，其结论是蕴含在大前提中的。7第7页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类（2）归纳推理）归纳推理是一种由个别到一般的推理方法。从足够多的事例中归是一种由个别到一般的推理方法。从足够多的事例中归纳出一般性结论的推理过程。纳出一般性结论的推理过程。例如，设有如下事例：例如，设有如下事例：王强是计算机系学生，他会编程序；王强是计算机系学生，他会编程序；高华是计算机系学生，她会编程序；高华是计算机系学生，她会编程序；当这些具体事例足够多时，就可归纳出一个一般性的知识：当这些具体事例足够多时，就可归纳出一个一般性的知识：凡是计

6、算机系的学生，就一定会编程序。凡是计算机系的学生，就一定会编程序。8第8页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类演绎推理与归纳推理的区别演绎推理与归纳推理的区别 演绎推理演绎推理是在已知领域内的一般性知识的前提下，是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它揭露出来，因此它不能增殖新知识不能增殖新知识。归纳推理归纳推

7、理所推出的结论是没有包含在前提内容中的。所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，这种由个别事物或现象推出一般性知识的过程，是是增殖新知识增殖新知识的过程。的过程。9第9页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类（3）默认推理）默认推理l默认推理又称为缺省推理，它是在知识不完全的情默认推理又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。况下假设某些条件已经具备所进行的推理。l在默认推理过程中，如果某一时刻发现原先所作的默认不在默认推理过程中，如果某一时刻发现原先所作的默认不正确，则就要撤消所作的默认以及由此默认

8、推出的结论，正确，则就要撤消所作的默认以及由此默认推出的结论，重新按新情况进行推理。重新按新情况进行推理。10第10页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类2.按推理时所用知识的确定性按推理时所用知识的确定性（1）确定性推理）确定性推理确定性推理是指推理时所用的知识都是精确的，推出确定性推理是指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或者为假，没的结论也是确定的，其真值或者为真，或者为假，没有第三种情况出现。有第三种情况出现。（2）不确定性推理）不确定性推理不确定性推理是指推理时所用的知识不都是精确的，不确定性推理是指推理时所用的知识不都是精确的

9、，推出的结论也不完全是肯定的，其真值位于真与假之推出的结论也不完全是肯定的，其真值位于真与假之间。（模糊集）间。（模糊集）11第11页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类3.按推理过程中结论的单调性按推理过程中结论的单调性（1）单调推理）单调推理单调推理是指在推理过程中随着推理过程向前推进及新知识的进入，单调推理是指在推理过程中随着推理过程向前推进及新知识的进入，推出推出的结论呈单调增加的趋势，并且越来越接近最终目标的结论呈单调增加的趋势，并且越来越接近最终目标，在，在推理过程中不会出现反复的情况推理过程中不会出现反复的情况，即不会由于新知识的加入否，即不会由于新知识的

10、加入否定了前面推出的结论，从而使推理又退回到前面的某一步。定了前面推出的结论，从而使推理又退回到前面的某一步。（2）非单调推理）非单调推理非单调推理是指在推理过程中非单调推理是指在推理过程中由于新知识的加入，不仅没有加由于新知识的加入，不仅没有加强已推出的结论，反而要否定它强已推出的结论，反而要否定它，使得推理退回到前面的某一，使得推理退回到前面的某一步，重新开始。步，重新开始。12第12页，本讲稿共95页4.1.1 推理方法及其分类推理方法及其分类4.按推理过程中用到启发性知识按推理过程中用到启发性知识（1）启发式推理）启发式推理（2）非启发式推理）非启发式推理5.按方法论按方法论（1）基于

11、知识的推理）基于知识的推理（2）直觉推理（常识性推理）直觉推理（常识性推理）6.按推理的简繁程度按推理的简繁程度（1）简单推理）简单推理（2）复合推理）复合推理7.按结论是否具有必然性按结论是否具有必然性（1）必然性推理）必然性推理（2）或然性推理）或然性推理13第13页，本讲稿共95页4.1.2 推理的控制策略推理的控制策略l推理的控制策略是指如何使用领域知识使推理过推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。程尽快达到目标的策略。l推理方向推理方向l搜索策略搜索策略l求解策略求解策略l冲突消解冲突消解l限制策略限制策略14第14页，本讲稿共95页1、推理方向推理方向正向

12、推理正向推理l从从已知事实出发、正向使用推理规则已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。，亦称为数据驱动推理或前向链推理。l算法描述算法描述l(1)把用户提供的初始证据放入综合数据库；把用户提供的初始证据放入综合数据库；l(2)检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；执行下一步；l(3)检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。l(4)按照某种

13、冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转数据库种，然后转(2)。l(5)询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转然后转(3)；否则表示无解，失败退出。；否则表示无解，失败退出。l至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该

14、先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。策略，以后将会分别讨论。l 其流程图如下：其流程图如下：15第15页，本讲稿共95页把初始证据放入把初始证据放入DBDB中有解吗？中有解吗？KB中有可用知识吗？中有可用知识吗？形成可用知识集形成可用知识集可用知识集空吗？可用知识集空吗？按照冲突消解策略从该知识按照冲突消解策略从该知识集中选出一条知识进行推理集中选出一条知识进行推理 推出的是新事实吗？推出的是新事实吗？将新事实加入到将新事实加入到DB把用户补充的新事把用户补充的新事实加入到实

15、加入到DB中中 用户可补充新事实吗？用户可补充新事实吗？失败退出失败退出 成功退出成功退出YNNYNNNYYY16第16页，本讲稿共95页1、推理方向、推理方向正向推理正向推理l例例 请用正向推理完成以下问题的求解请用正向推理完成以下问题的求解l 假设知识库中包含有以下假设知识库中包含有以下2条规则：条规则：l r1：IF B THEN Cl r2：IF A THEN Bl已知初始证据已知初始证据A，求证目标，求证目标C。l解：本例的推理过程如下：解：本例的推理过程如下：l推理开始前，综合数据库为空。推理开始前，综合数据库为空。l推理开始后，先把推理开始后，先把A放入综合数据库，然后检查综合数

16、据库中是否含有该问题的解，回答为放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为“N”。l接着检查知识库中是否有可用知识，显然接着检查知识库中是否有可用知识，显然r2可用，形成仅含可用，形成仅含r2的知识集。从该知识集中取出的知识集。从该知识集中取出r2，推，推出新的实事出新的实事B，将，将B加入综合数据库，检查综合数据库中是否含有目标加入综合数据库，检查综合数据库中是否含有目标C，回答为，回答为“N”。l再检查知识库中是否有可用知识，此时由于再检查知识库中是否有可用知识，此时由于B的加入使得的加入使得r1为可用，形成仅含为可用，形成仅含r1的知识集。从的知识集。从该知识集中取出

17、该知识集中取出r1，推出新的实事，推出新的实事C，将，将C加入综合数据库，检查综合数据库中是否含有目标加入综合数据库，检查综合数据库中是否含有目标C，回答为，回答为“Y”。l它说明综合数据库中已经含有问题的解，推理成功结束，目标它说明综合数据库中已经含有问题的解，推理成功结束，目标C得证。得证。17第17页，本讲稿共95页l正向推理的主要优点正向推理的主要优点l比较直观，允许用户主动提供有用的事实信息，适合于诊断、比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。设计、预测、监控等领域的问题求解。l正向推理的主要缺点正向推理的主要缺点l推理无明确目标，求解

18、问题是可能会执行许多与解无关的推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。操作，导致推理效率较低。1、推理方向推理方向正向推理正向推理18第18页，本讲稿共95页1、推理方向、推理方向 逆向推理逆向推理l从某个假设目标出发，逆向使用规则从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。，亦称为目标驱动推理或逆向链推理。l算法描述：算法描述：l(1)将要求证的目标（称为假设）构成一个假设集；将要求证的目标（称为假设）构成一个假设集；l(2)从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假从假设集中选出一个假设，检查

19、该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步；若该假设不在数据库中，则执行下一步；l(3)检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转假设，若不是，则转(5)；若能由某个知识导出，则执

20、行下一步；若能由某个知识导出，则执行下一步；l(4)将知识库中可以导出该假设的所有知识构成一个可用知识集；将知识库中可以导出该假设的所有知识构成一个可用知识集；l(5)检查可用知识集是否为空，若是，失败退出；否则执行下一步；检查可用知识集是否为空，若是，失败退出；否则执行下一步；l(6)按冲突消解策略从可用知识集中取出一个知识，继续；按冲突消解策略从可用知识集中取出一个知识，继续；l(7)将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。l 其流程图如下：其流程图如下：19第19页，本讲稿共95页初始化初始化DB和假

21、设集和假设集该假设是该假设是DB中的事实吗？中的事实吗？该假设能被该假设能被KB中的中的知识导出吗？知识导出吗？从假设集中取出一个假设从假设集中取出一个假设可用知识集空吗？可用知识集空吗？按照冲突消解策略从该知识集按照冲突消解策略从该知识集中选出一条知识中选出一条知识将该知识前提中的每个子条件作为新将该知识前提中的每个子条件作为新的假设加入假设集的假设加入假设集该假设成立该假设成立并放入并放入DB还有新的假设吗？还有新的假设吗？失败退出失败退出成功退出成功退出YNYYNNNNY将将KB中所有能导出此假设的知中所有能导出此假设的知识构成一个可用知识集识构成一个可用知识集 询问用户有询问用户有此事

22、实吗？此事实吗？该假设该假设 成立成立Y20第20页，本讲稿共95页1、推理方向、推理方向逆向推理逆向推理l例例3.2 用逆向推理完成以下问题的求解用逆向推理完成以下问题的求解l 假设知识库中包含有以下假设知识库中包含有以下2条规则：条规则：l r1：IF B THEN Cl r2：IF A THEN Bl已知初始证据已知初始证据A，求证目标，求证目标C。l推理开始前，综合数据库和假设集均为空。推理开始前，综合数据库和假设集均为空。l推理开始后，先将初始证据推理开始后，先将初始证据A和目标和目标C分别放入综合数据库和假设集，然后从假设集中取出分别放入综合数据库和假设集，然后从假设集中取出一个假

23、设一个假设C，查找，查找C是否为综合数据库中的已知事实，回答为是否为综合数据库中的已知事实，回答为“N”。l再检查再检查C是否能被知识库中的知识所导出，发现是否能被知识库中的知识所导出，发现C可由可由r1导出导出，于是，于是r1被放入可用知识集。被放入可用知识集。由于知识库中只有由于知识库中只有r1可用，故可用知识集中仅含可用，故可用知识集中仅含r1。l接着从可用知识集中取出接着从可用知识集中取出r1，将其前提条件，将其前提条件B作为新的假设放入假设集。从假设集中取作为新的假设放入假设集。从假设集中取出出B，检查，检查B是否为综合数据库中的实事，回答为是否为综合数据库中的实事，回答为“N”。再

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

25、功结束，于是目标C得证。得证。21第21页，本讲稿共95页1、推理方向、推理方向逆向推理逆向推理l逆向推理的主要优点逆向推理的主要优点l不必寻找和使用那些与假设目标无关的信息和知识不必寻找和使用那些与假设目标无关的信息和知识l推理过程的目标明确推理过程的目标明确l也有利于向用户提供解释，在诊断性专家系统中较为有效。也有利于向用户提供解释，在诊断性专家系统中较为有效。l逆向推理的主要缺点逆向推理的主要缺点l当当用用户户对对解解的的情情况况认认识识不不请请时时，由由系系统统自自主主选选择择假假设设目目标标的的盲盲目目性性比比较较大大，若若选选择择不不好好，可可能能需需要要多多次次提提出出假假设设，

26、会会影影响响系系统效率。统效率。22第22页，本讲稿共95页1、推理方向、推理方向混合推理混合推理l混合推理的概念混合推理的概念l把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。较复杂问题的方法。l混合推理的应用环境混合推理的应用环境l已知事实不充分已知事实不充分l由正向推理得出的结论可信度不高由正向推理得出的结论可信度不高l希望得到更多的结论希望得到更多的结论l混合推理的方法混合推理的方法l1.先正向后逆向先正向后逆向l这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结

27、这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。果进行证实或提高它们的可信度。l2.先逆向后正向先逆向后正向l这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。推理对这些中间假设进行证实。l3.双向混合双向混合l是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。23第23页，本讲稿共95页1、推理方向、推理方向双向推理双向推理 l正向推理与逆向

28、推理同时进行，在推理过程中某一步骤上正向推理与逆向推理同时进行，在推理过程中某一步骤上“碰碰头头”l其基本思想是：其基本思想是：l一方面根据已知事实进行正向推理，但并不推到最终目标；一方面根据已知事实进行正向推理，但并不推到最终目标；l另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所要求的证据，这时推理就可结束，逆向推理的假设就是推理的此时所要求的证据，这时推理就可结束，逆向推理的假设就是推理的最终

29、结论。最终结论。24第24页，本讲稿共95页2.2.求解策略求解策略l所谓推理的求解策略是指，推理是只求一个解，所谓推理的求解策略是指，推理是只求一个解，还是求所有解以及最优解等。还是求所有解以及最优解等。l例如前述的正向推理只用于求一个解，只要略例如前述的正向推理只用于求一个解，只要略加修改就可用来求所有解。加修改就可用来求所有解。25第25页，本讲稿共95页3.3.限制策略限制策略l为了防止无穷的推理过程，以及由于推理过程为了防止无穷的推理过程，以及由于推理过程太长从而增加时间及空间的复杂性，可在控制太长从而增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度、策略中指

30、定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。宽度、时间、空间等进行限制。26第26页，本讲稿共95页l在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进行匹在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进行匹配，此时可能发生有多个知识匹配成功，称这种情况为发生了冲突。配，此时可能发生有多个知识匹配成功，称这种情况为发生了冲突。l基本任务：基本任务：l解决冲突，选择其中的一条规则来执行。解决冲突，选择其中的一条规则来执行。l基本思想：基本思想：对知识进行排序对知识进行排序l按针对性排序按针对性排序l按匹配度进行排序按匹配度进行排序l根据领域问题的特点进行排

31、序根据领域问题的特点进行排序4.冲突消解策略冲突消解策略27第27页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l模式匹配是指两个知识模式（如两个谓词公式、两个框架片模式匹配是指两个知识模式（如两个谓词公式、两个框架片断等）的比较，检查这两个知识模式是否完全一致或近似一断等）的比较，检查这两个知识模式是否完全一致或近似一致。如果两者完全一致，或者虽不完全一致但其相似程度落致。如果两者完全一致，或者虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。在指定的限度内，就称它们是可匹配的，否则为不可匹配。l按匹配时两个知识模式的相似程度划分，模式匹配

32、可分为：按匹配时两个知识模式的相似程度划分，模式匹配可分为：l确定性匹配确定性匹配l不确定性匹配不确定性匹配28第28页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l确定性匹配确定性匹配是指两个知识模式完全一致，或者经过是指两个知识模式完全一致，或者经过变量代换后变得完全一致。变量代换后变得完全一致。l例如，设有如下两个知识模式：例如，设有如下两个知识模式：P1：Father（李四，李小四）（李四，李小四）and Man(李小四李小四)P2：Father(x,y)and Man(y)l若用若用“李四李四”代换变量代换变量x，用，用“李小四李小四”代换变量代换变量y，则则

33、P1与与P2就变得完全一致。就变得完全一致。l不确定性匹配不确定性匹配是指两个知识模式不完全一致，但从总体是指两个知识模式不完全一致，但从总体上看，它们的相似程度又落在规定的限度内。上看，它们的相似程度又落在规定的限度内。29第29页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l代换（置换）代换（置换）可简单的理解为是在一个谓词公式中可简单的理解为是在一个谓词公式中用置换项去替换变量。用置换项去替换变量。l定义定义3.1代换（置换）是形如代换（置换）是形如l t1/x1,t2/x2,tn/xnl的有限集合。其中，的有限集合。其中，t1,t2,tn是项；是项；x1,x2,

34、xn是互是互不相同的变元；不相同的变元；ti/xi表示用表示用ti替换替换xi。并且要求。并且要求ti与与xi不能相同，不能相同，xi不能循环地出现在另一个不能循环地出现在另一个ti中。中。30第30页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l例如例如，a/x,c/y,f(b)/z 是一个置换。是一个置换。l但但g(y)/x,f(x)/y不是一个置换。不是一个置换。l原因是它在原因是它在x与与y之间出现了循环置换现象。即当用之间出现了循环置换现象。即当用g(y)置置换换x,用用f(g(y)置换置换y时，既没有消去时，既没有消去x，也没有消去，也没有消去y。l若改为若

35、改为g(a)/x,f(x)/y即可，即可，l原因是用原因是用g(a)置换置换x，用，用f(g(a)置换置换y，则消去了，则消去了x和和y。l通常，置换是用希腊字母通常，置换是用希腊字母、等来表示的。等来表示的。31第31页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l定义定义3.2 设设l =t1/x1,t2/x2,tn/xnl =u1/y1,u2/y2,um/ym l是两个置换。则是两个置换。则与与的复合（合成）也是一个置换的复合（合成）也是一个置换，记作，记作。它是从集合它是从集合l t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym l中删去以

36、下两种元素中删去以下两种元素l 当当ti=xi时，时，删去删去ti/xi(i=1,2,n)；l 当当yj x1,x2,xn 时，时，删去删去uj/yj(j=1,2,m)l最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。32第32页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l例例 设设=f(y)/x,z/y，=a/x,b/y,y/z，求，求与与的的合成。合成。l解解:先求出集合先求出集合lf(b/y)/x,(y/z)/y,a/x,b/y,y/z=f(b)/x,y/y,a/x,b/y,y/zl其中，其中，f(b)/x中的中的f(b)是置换是置换作用于作用于f(y)

37、的结果；的结果；y/y 中的中的y是置换是置换作用于作用于z的结果。的结果。l在该集合中，在该集合中，y/y满足定义中的条件满足定义中的条件，需要删除；，需要删除；a/x和和b/y满足定义中的条件满足定义中的条件，也需要删除。最后得，也需要删除。最后得l=f(b)/x,y/z33第33页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l合一合一可理解为是寻找项对变量的置换，使两个谓词公式一致。可定可理解为是寻找项对变量的置换，使两个谓词公式一致。可定义为：义为：l定义定义3.3 设有公式集设有公式集F=F1,F2,Fn，若存在一个置换，若存在一个置换，可使，可使l F1=F

38、2=Fn，l则称则称是是F的一个合一。称的一个合一。称F1,F2,Fn是可合一的。是可合一的。l例如，例如，设有公式集设有公式集F=P(x,y,f(y),P(a,g(x),z)，则，则l =a/x,g(a)/y,f(g(a)/zl是它的一个合一。是它的一个合一。l一般来说，一个公式集的合一不是唯一的。一般来说，一个公式集的合一不是唯一的。34第34页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l定义定义3.4 设设是公式集是公式集F的一个合一，如果对的一个合一，如果对F的任一个合一的任一个合一都存在一个置换都存在一个置换，使得，使得=，则称，则称是一个最一般合一。（是一

39、个最一般合一。（Most General Unifier）l一个公式集的最一般合一是唯一的。一个公式集的最一般合一是唯一的。35第35页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l差异集的概念。差异集的概念。l设有如下两个谓词公式：设有如下两个谓词公式：F1：P（x,y,z）F2：P(x,f(A),h(B)分别从分别从F1与与F2的第一个符号开始，逐个向右比较，的第一个符号开始，逐个向右比较，此时发现此时发现F1与与F2构差异集：构差异集：D1=y,f(A)，D2=z,h(B)36第36页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换l求最一般合

40、一算法求最一般合一算法（1）初始化，令）初始化，令k=0,Fk=F,k=。其中，。其中，是代换空集。是代换空集。（2）若）若Fk只含一个表达式，则算法停止，只含一个表达式，则算法停止，k就是最一般合一；否就是最一般合一；否则转步骤（则转步骤（3）。）。（3）找出）找出Fk的差异集的差异集Dk。（4）若）若Dk中存在变元中存在变元xk和项和项tk，且，且xk不在不在tk中出现，则：中出现，则：k+1=tk/xkFk+1=Fk tk/xkk=k+1转步骤（转步骤（2）；否则，）；否则，算法终止，算法终止，F的最一般合一不存在。的最一般合一不存在。37第37页，本讲稿共95页4.1.3 模式匹配及其

41、变量代换模式匹配及其变量代换例例 设有公式集设有公式集F=P(A,x,f (g(y),P(z,f(z),f(u)求其最一般合一。求其最一般合一。解：解：初始化，令初始化，令k=0，0=，F0=F=P(A,x,f(g(y),P(z,f(z),f(u)38第38页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换Loop 1：F0=P(A,x,f(g(y),P(z,f(z),f(u)含有含有2个表达式，故个表达式，故0不是最一般合一。不是最一般合一。F0的差异集的差异集D0=A，z，可有代换，可有代换A/z，1=0 A/z=A/zF1=F0A/z=P(A,x,f(g(y),P(A

42、,f(A),f(u)39第39页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换Loop 2：F1=P(A,x,f(g(y),P(A,f(A),f(u)含有含有2个表个表达式，故达式，故1不是最一般合一不是最一般合一F1的差异集的差异集D1=x，f(A)，可有代换，可有代换f(A)/x，2=1 f(A)/x=A/z f(A)/x=A/z,f(A)/xF2=F1f(A)/x=P(A,f(A),f(g(y),P(A,f(A),f(u)40第40页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换Loop 3：F2=P(A,f(A),f(g(y),P(A,f(A

43、),f(u)含有含有2个表达式，故个表达式，故2不是最一般合一不是最一般合一F2的差异集的差异集D2=g(y)，u，可有代换，可有代换g(y)/u，3=2 g(y)/u=A/z,f(A)/x g(y)/u=A/z,f(A)/x,g(y)/uF3=F2g(y)/u=P(A,f(A),f(g(y),P(A,f(A),f(g(y)=P(A,f(A),f(g(y)41第41页，本讲稿共95页4.1.3 模式匹配及其变量代换模式匹配及其变量代换Loop 4：F3中只含有一个表达式，故算法成功中只含有一个表达式，故算法成功终止，终止，3=A/z,f(A)/x,g(y)/u，即为公式集，即为公式集F的最一般

44、合一。的最一般合一。42第42页，本讲稿共95页实验二：实验二：编程实现公式集的最一般合一求解编程实现公式集的最一般合一求解l可以输入公式集，对不符合规范的公式集要报可以输入公式集，对不符合规范的公式集要报错，符合规范的公式集进入求最一般合一步骤。错，符合规范的公式集进入求最一般合一步骤。l如果有最一般合一，要求显示每一步过程的差如果有最一般合一，要求显示每一步过程的差异集和代换，最后输出解；如果没有最一般合异集和代换，最后输出解；如果没有最一般合一，最后要作出判断。一，最后要作出判断。43第43页，本讲稿共95页第第4章章 经典逻辑推理经典逻辑推理l4.1 推理的基本概念推理的基本概念l4.

45、2 自然演绎推理自然演绎推理l4.3 归结演绎推理归结演绎推理l4.4 与与/或形演绎推理或形演绎推理44第44页，本讲稿共95页4.2 自然演绎推理自然演绎推理l自然演绎推理自然演绎推理l从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。的过程称为自然演绎推理。l自然演绎推理最基本的推理规则是三段论推理，它包括：自然演绎推理最基本的推理规则是三段论推理，它包括：l假言推理假言推理 P,PQ Ql拒取式拒取式 Q,PQ Pl假言三段论假言三段论 PQ,QR PRl例例 设已知如下事实：设已知如下事

46、实：l A,B,AC,BCD,DQl 求证：求证：Q为真。为真。l 证明：证明：因为因为 A,AC C 假言推理假言推理l B,C BC 引入合取词引入合取词 l BC，BCD D 假言推理假言推理l D,DQ Q 假言推理假言推理l因此，因此，Q为真为真45第45页，本讲稿共95页4.2 自然演绎推理自然演绎推理l例例 设已知如下事实：设已知如下事实：l(1)只要是需要编程序的课，王程都喜欢。只要是需要编程序的课，王程都喜欢。l(2)所有的程序设计语言课都是需要编程序的课。所有的程序设计语言课都是需要编程序的课。l(3)C是一门程序设计语言课。是一门程序设计语言课。l求证：王程喜欢求证：王程

47、喜欢C这门课。这门课。l证明：证明：首先定义谓词首先定义谓词l Prog(x)x是需要编程序的课。是需要编程序的课。l Like(x,y)x喜欢喜欢y。l Lang(x)x是一门程序设计语言课是一门程序设计语言课l把已知事实及待求解问题用谓词公式表示如下：把已知事实及待求解问题用谓词公式表示如下：l Prog(x)Like(Wang,x)l (x)(Lang(x)Prog(x)l Lang(C)l应用推理规则进行推理：应用推理规则进行推理：l Lang(y)Prog(y)全称固化全称固化l Lang(C)，Lang(y)Prog(y)Prog(C)假言推理假言推理 C/yl Prog(C),P

48、rog(x)Like(Wang,x)Like(Wang,C)假言推理假言推理 C/xl因此，王程喜欢因此，王程喜欢C这门课。这门课。46第46页，本讲稿共95页4.2 自然演绎推理自然演绎推理l 优点：优点：定理证明过程自然，易于理解，并且有丰富定理证明过程自然，易于理解，并且有丰富的推理规则可用。的推理规则可用。l 缺点：缺点：是容易产生知识爆炸，推理过程中得到的中是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。甚至难以实现。47第47页，本讲稿共95页第第4章章 经典逻辑推理经典逻辑推理

49、l4.1 推理的基本概念推理的基本概念l4.2 自然演绎推理自然演绎推理l4.3 归结演绎推理归结演绎推理l4.4 与与/或形演绎推理或形演绎推理48第48页，本讲稿共95页4.3 归结演绎推理归结演绎推理l在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定定理证明的实质理证明的实质，就是要对前提，就是要对前提P和结论和结论Q，证明，证明PQ永真。永真。l要证明要证明PQ永真，就是要证明永真，就是要证明PQ在任何一个非空的个体域上都是永真在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。的。这将是非常困难

50、的，甚至是不可实现的。l为此，人们进行了大量的探索，后来发现可以为此，人们进行了大量的探索，后来发现可以采用反证法的思想采用反证法的思想，把关于永真，把关于永真性的证明转化为关于不可满足性的证明。性的证明转化为关于不可满足性的证明。l即要证明即要证明PQ永真，只要能够证明永真，只要能够证明PQ是不可满足的就可以了是不可满足的就可以了(原因是原因是(PQ)(PQ)P Q。l这方面最有成效的工作就是这方面最有成效的工作就是鲁宾逊归结原理鲁宾逊归结原理。它使定理证明的机械化成为现实。它使定理证明的机械化成为现实。归结演绎推理是一种基于鲁宾逊（归结演绎推理是一种基于鲁宾逊（Robinson）归结原理的