《人工智能第四章经典逻辑推理ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第四章经典逻辑推理ppt课件.ppt（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第第4章章 经典逻辑推理经典逻辑推理l4.1 推理的基本概念推理的基本概念l4.2 自然演绎推理自然演绎推理l4.3 归结演绎推理归结演绎推理l4.4 与与/或形演绎推理或形演绎推理2第第4章章 经典逻辑推理经典逻辑推理 l智能系统的推理过程实际上就是一种思维过程。智能系统的推理过程实际上就是一种思维过程。即运用即运用知识知识进行推理来进行推理来求解问题求解问题。l经典逻辑推理是根据经典逻辑（命题逻辑及一经典逻辑推理是根据经典逻辑（命题逻辑及一阶谓词逻辑）的逻辑规则进行的一种推理。阶谓词逻辑）的逻辑规则进行的一种推理。l由于这种推理是基于经典逻辑的，其真值只有由于这种推理是基于经典逻辑的，其
2、真值只有“真真”和和“假假”两种，因此它是一种精确推理，两种，因此它是一种精确推理，或称为或称为确定性确定性推理。推理。34.1 推理的基本概念推理的基本概念l4.1.1 推理方式及其分类推理方式及其分类l4.1.2 推理的控制策略推理的控制策略l4.1.3 模式匹配及其变量代换模式匹配及其变量代换44.1.1 推理方法及其分类推理方法及其分类1. 按推理的逻辑基础分类按推理的逻辑基础分类l演绎推理演绎推理l归纳推理归纳推理l默认推理默认推理54.1.1 推理方法及其分类推理方法及其分类（1）演绎推理）演绎推理 演绎推理是从已知的一般性知识出发，去推出演绎推理是从已知的一般性知识出发，去推出蕴
3、含在这些已知知识中的适合于某种个别情况的蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心结论。是一种由一般到个别的推理方法，其核心是三段论，是三段论， 如如 假言推理、拒取式和假言三段论。假言推理、拒取式和假言三段论。 6（1）演绎推理）演绎推理 例：例： 假言三段论假言三段论 AB，BC AC 常用的三段论是由一个大前提、一个小前提和一常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。个结论这三部分组成的。 大前提大前提是已知的一般性知识或推理过程得到的判断；是已知的一般性知识或推理过程得到的判断； 小前提小前提是关于某种具体情况或某个具体实
4、例的判断；是关于某种具体情况或某个具体实例的判断； 结论结论是由大前提推出的，并且适合于小前提的判断。是由大前提推出的，并且适合于小前提的判断。4.1.1 推理方法及其分类推理方法及其分类74.1.1 推理方法及其分类推理方法及其分类（1）演绎推理）演绎推理例，有如下三个判断：例，有如下三个判断： 计算机系的学生都会编程序；计算机系的学生都会编程序； （一般性知识）（一般性知识） 程强是计算机系的一位学生；程强是计算机系的一位学生； （具体情况）（具体情况） 程强会编程序。程强会编程序。 （结论）（结论） 这是一个三段论推理。这是一个三段论推理。其中，其中，是大前提，是大前提，是小前提；是小前
5、提；是经演绎推出来的结论。是经演绎推出来的结论。可见，其结论是蕴含在大前提中的。可见，其结论是蕴含在大前提中的。84.1.1 推理方法及其分类推理方法及其分类（2）归纳推理）归纳推理是一种由个别到一般的推理方法。从足够多的事是一种由个别到一般的推理方法。从足够多的事例中归纳出一般性结论的推理过程。例中归纳出一般性结论的推理过程。例如，设有如下事例：例如，设有如下事例： 王强是计算机系学生，他会编程序；王强是计算机系学生，他会编程序； 高华是计算机系学生，她会编程序；高华是计算机系学生，她会编程序； 当这些具体事例足够多时，就可归纳出一个一般性的知识：当这些具体事例足够多时，就可归纳出一个一般性
6、的知识： 凡是计算机系的学生，就一定会编程序。凡是计算机系的学生，就一定会编程序。94.1.1 推理方法及其分类推理方法及其分类演绎推理与归纳推理的区别演绎推理与归纳推理的区别 演绎推理演绎推理是在已知领域内的一般性知识的前提是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不过是将已有事实揭露出来，因此它不能增不能增殖新知识殖新知识。 归纳推理归纳推理所
7、推出的结论是没有包含在前提内所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性容中的。这种由个别事物或现象推出一般性知识的过程，知识的过程，是增殖新知识是增殖新知识的过程。的过程。104.1.1 推理方法及其分类推理方法及其分类（3）默认推理）默认推理l默认推理又称为缺省推理，它是在知识不完全的默认推理又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。情况下假设某些条件已经具备所进行的推理。 l在默认推理过程中，如果某一时刻发现原先所作在默认推理过程中，如果某一时刻发现原先所作的默认不正确，则就要撤消所作的默认以及由此的默认不正确，则就要撤消所作的默认
8、以及由此默认推出的结论，重新按新情况进行推理。默认推出的结论，重新按新情况进行推理。114.1.1 推理方法及其分类推理方法及其分类2. 按推理时所用知识的确定性按推理时所用知识的确定性（1）确定性推理）确定性推理确定性推理是指推理时所用的知识都是精确确定性推理是指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为的，推出的结论也是确定的，其真值或者为真，或者为假，没有第三种情况出现。真，或者为假，没有第三种情况出现。（2）不确定性推理）不确定性推理不确定性推理是指推理时所用的知识不都是不确定性推理是指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其精确的，推出的结论也
9、不完全是肯定的，其真值位于真与假之间。（模糊集）真值位于真与假之间。（模糊集）124.1.1 推理方法及其分类推理方法及其分类3.按推理过程中结论的单调性按推理过程中结论的单调性（1）单调推理）单调推理单调推理是指在推理过程中随着推理过程向前推进及新知识单调推理是指在推理过程中随着推理过程向前推进及新知识的进入，的进入，推出的结论呈单调增加的趋势，并且越来推出的结论呈单调增加的趋势，并且越来越接近最终目标越接近最终目标，在推理过程中不会出现反复的情况，在推理过程中不会出现反复的情况 ，即不会由于新知识的加入否定了前面推出的结论，从而使推即不会由于新知识的加入否定了前面推出的结论，从而使推理又退
10、回到前面的某一步。理又退回到前面的某一步。（2）非单调推理）非单调推理非单调推理是指在推理过程中非单调推理是指在推理过程中由于新知识的加入，不仅由于新知识的加入，不仅没有加强已推出的结论，反而要否定它没有加强已推出的结论，反而要否定它，使得推理退，使得推理退回到前面的某一步，重新开始。回到前面的某一步，重新开始。134.1.1 推理方法及其分类推理方法及其分类4.按推理过程中用到启发性知识按推理过程中用到启发性知识（1）启发式推理）启发式推理（2）非启发式推理）非启发式推理5.按方法论按方法论（1）基于知识的推理）基于知识的推理（2）直觉推理（常识性推理）直觉推理（常识性推理）6.按推理的简繁
11、程度按推理的简繁程度（1）简单推理）简单推理（2）复合推理）复合推理7.按结论是否具有必然性按结论是否具有必然性（1）必然性推理）必然性推理（2）或然性推理）或然性推理144.1.2 推理的控制策略推理的控制策略l推理的控制策略是指如何使用领域知识使推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。推理过程尽快达到目标的策略。l推理方向推理方向l搜索策略搜索策略l求解策略求解策略l冲突消解冲突消解l限制策略限制策略151、 推理方向推理方向正向推理正向推理l从从已知事实出发、正向使用推理规则已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。，亦称为数据驱动推理或前向
12、链推理。 l算法描述算法描述l(1) 把用户提供的初始证据放入综合数据库；把用户提供的初始证据放入综合数据库；l(2) 检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；否则执行下一步；l(3) 检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转转(5)。l(4) 按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将
13、推出的新事实加入综合数据库种，然后转的新事实加入综合数据库种，然后转(2)。l(5) 询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转数据库中，然后转(3)；否则表示无解，失败退出。；否则表示无解，失败退出。l至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策
14、略，以后将会分别讨论。冲突消解策略，以后将会分别讨论。l 其流程图如下：其流程图如下：16把初始证据放入把初始证据放入DBDB中有解吗？中有解吗？KB中有可用知识吗？中有可用知识吗？ 形成可用知识集形成可用知识集可用知识集空吗？可用知识集空吗？按照冲突消解策略从该知识按照冲突消解策略从该知识集中选出一条知识进行推理集中选出一条知识进行推理 推出的是新事实吗？推出的是新事实吗？ 将新事实加入到将新事实加入到DB把用户补充的新事把用户补充的新事实加入到实加入到DB中中 用户可补充新事实吗？用户可补充新事实吗？ 失败退出失败退出 成功退出成功退出YNNYNNNYYY171、推理方向、推理方向正向推理
15、正向推理l例例 请用正向推理完成以下问题的求解请用正向推理完成以下问题的求解l 假设知识库中包含有以下假设知识库中包含有以下2条规则：条规则：l r1： IF B THEN Cl r2： IF A THEN Bl已知初始证据已知初始证据A，求证目标，求证目标C。l解：本例的推理过程如下：解：本例的推理过程如下：l推理开始前，综合数据库为空。推理开始前，综合数据库为空。l推理开始后，先把推理开始后，先把A放入综合数据库，然后检查综合数据库中是否含有该问题的放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为解，回答为“N”。l接着检查知识库中是否有可用知识，显然接着检查知识库中是否有可
16、用知识，显然r2可用，形成仅含可用，形成仅含r2的知识集。从该知识的知识集。从该知识集中取出集中取出r2，推出新的实事，推出新的实事B，将，将B加入综合数据库，检查综合数据库中是否含有加入综合数据库，检查综合数据库中是否含有目标目标C，回答为，回答为“N”。l再检查知识库中是否有可用知识，此时由于再检查知识库中是否有可用知识，此时由于B的加入使得的加入使得r1为可用，形成仅含为可用，形成仅含r1的的知识集。从该知识集中取出知识集。从该知识集中取出r1，推出新的实事，推出新的实事C，将，将C加入综合数据库，检查综合加入综合数据库，检查综合数据库中是否含有目标数据库中是否含有目标C，回答为，回答为
17、“Y”。l它说明综合数据库中已经含有问题的解，推理成功结束，目标它说明综合数据库中已经含有问题的解，推理成功结束，目标C得证。得证。18l正向推理的主要优点正向推理的主要优点l比较直观，允许用户主动提供有用的事实信息，适合于比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。诊断、设计、预测、监控等领域的问题求解。l正向推理的主要缺点正向推理的主要缺点l推理无明确目标，求解问题是可能会执行许多与解无关推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。的操作，导致推理效率较低。 1、推理方向推理方向正向推理正向推理191、推理方向、推理
18、方向 逆向推理逆向推理l从某个假设目标出发，逆向使用规则从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。，亦称为目标驱动推理或逆向链推理。l算法描述：算法描述：l(1) 将要求证的目标（称为假设）构成一个假设集；将要求证的目标（称为假设）构成一个假设集；l(2) 从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，；若该假设不在数据库中，则执行下一步；则执行下一步；l(
19、3) 检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转据库，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一；若能由某个知识导出，则执行下一步；步；l(4) 将知识库中可以导出该假设的所有知识构成一个可用知识集；将知识库中可以导出该假设的所有知识构成一个可用知识集；l(5) 检查可用知识集是否为空，若是
20、，失败退出；否则执行下一步；检查可用知识集是否为空，若是，失败退出；否则执行下一步；l(6) 按冲突消解策略从可用知识集中取出一个知识，继续；按冲突消解策略从可用知识集中取出一个知识，继续；l(7) 将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。 l 其流程图如下：其流程图如下：20初始化初始化DB和假设集和假设集该假设是该假设是DB中的事实吗？中的事实吗？该假设能被该假设能被KB中中的知识导出吗？的知识导出吗？从假设集中取出一个假设从假设集中取出一个假设可用知识集空吗？可用知识集空吗？按照冲突消解策略从该按照冲
21、突消解策略从该知识集中选出一条知识知识集中选出一条知识将该知识前提中的每个子条将该知识前提中的每个子条件作为新的假设加入假设集件作为新的假设加入假设集该假设成立该假设成立并放入并放入DB还有新的假设吗？还有新的假设吗？失败退出失败退出成功退出成功退出YNYYNNNNY将将KB中所有能导出此假设的中所有能导出此假设的知识构成一个可用知识集知识构成一个可用知识集 询问用户有询问用户有此事实吗？此事实吗？该假设该假设 成立成立Y211、推理方向、推理方向逆向推理逆向推理l例例3.2 用逆向推理完成以下问题的求解用逆向推理完成以下问题的求解l 假设知识库中包含有以下假设知识库中包含有以下2条规则：条规
22、则：l r1： IF B THEN Cl r2： IF A THEN Bl已知初始证据已知初始证据A，求证目标，求证目标C。l推理开始前，综合数据库和假设集均为空。推理开始前，综合数据库和假设集均为空。l推理开始后，先将初始证据推理开始后，先将初始证据A和目标和目标C分别放入综合数据库和假设集，然后从假分别放入综合数据库和假设集，然后从假设集中取出一个假设设集中取出一个假设C，查找，查找C是否为综合数据库中的已知事实，回答为是否为综合数据库中的已知事实，回答为“N”。l再检查再检查C是否能被知识库中的知识所导出，发现是否能被知识库中的知识所导出，发现C可由可由r1导出导出，于是，于是r1被放入
23、被放入可用知识集。由于知识库中只有可用知识集。由于知识库中只有r1可用，故可用知识集中仅含可用，故可用知识集中仅含r1。l接着从可用知识集中取出接着从可用知识集中取出r1，将其前提条件，将其前提条件B作为新的假设放入假设集。从假设作为新的假设放入假设集。从假设集中取出集中取出B，检查，检查B是否为综合数据库中的实事，回答为是否为综合数据库中的实事，回答为“N”。再检查。再检查B是否能是否能被知识库中的知识所导出，发现被知识库中的知识所导出，发现B可由可由r2导出导出，于是，于是r2被放入可用知识集。由被放入可用知识集。由于知识库中只有于知识库中只有r2可用，故可用知识集中仅含可用，故可用知识集
24、中仅含r2。l从可用知识集中取出从可用知识集中取出r2，将其前提条件，将其前提条件A作为新的假设放入假设集。然后从假设作为新的假设放入假设集。然后从假设集中取出集中取出A，检查，检查A是否为综合数据库中的实事是否为综合数据库中的实事，回答为，回答为“Y”。l他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。得证。221、推理方向、推理方向逆向推理逆向推理l逆向推理的主要优点逆向推理的主要优点l不必寻找和使用那些与假设目标无关的信息和知识不必寻找和使用那些与假设目标无关的信息和知识l推理过程的目标明确推理过程的目标
25、明确l也有利于向用户提供解释，在诊断性专家系统中较为有效。也有利于向用户提供解释，在诊断性专家系统中较为有效。l逆向推理的主要缺点逆向推理的主要缺点l当用户对解的情况认识不请时，由系统自主选择假设目标的当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。响系统效率。231、推理方向、推理方向混合推理混合推理l混合推理的概念混合推理的概念l把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。解
26、决较复杂问题的方法。l混合推理的应用环境混合推理的应用环境l已知事实不充分已知事实不充分l由正向推理得出的结论可信度不高由正向推理得出的结论可信度不高l希望得到更多的结论希望得到更多的结论l混合推理的方法混合推理的方法l1. 先正向后逆向先正向后逆向l这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。逆向推理对这些结果进行证实或提高它们的可信度。 l2. 先逆向后正向先逆向后正向l这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后这种方法先进行逆向推理，从假设目标出发推
27、出一些中间假设，然后再用正向推理对这些中间假设进行证实。再用正向推理对这些中间假设进行证实。 l3. 双向混合双向混合l是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。起来。241、推理方向、推理方向双向推理双向推理 l正向推理与逆向推理同时进行，在推理过程中某一步骤正向推理与逆向推理同时进行，在推理过程中某一步骤上上“碰头碰头”l其基本思想是：其基本思想是：l一方面根据已知事实进行正向推理，但并不推到最终目标；一方面根据已知事实进行正向推理，但并不推到最终目标；l另一方面从某假设目标出发进行逆向推理，但并不推至原始
28、事另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所要求的证据，这时推理就可结束，逆向推好是逆向推理此时所要求的证据，这时推理就可结束，逆向推理的假设就是推理的最终结论。理的假设就是推理的最终结论。252. 2. 求解策略求解策略l所谓推理的求解策略是指，推理是只求一个解，所谓推理的求解策略是指，推理是只求一个解，还是求所有解以及最优解等。还是求所有解以及最优解等。l例如前述的正向推理只用于求一个解，只要略例如前述的正向推理只用于求一个解，只要略加修改就可用来求所有
29、解。加修改就可用来求所有解。 263. 3. 限制策略限制策略l为了防止无穷的推理过程，以及由于推理过程为了防止无穷的推理过程，以及由于推理过程太长从而增加时间及空间的复杂性，可在控制太长从而增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度、策略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。宽度、时间、空间等进行限制。 27l在推理过程中，系统要不断地用当前已知的事实与知识库中在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进行匹配，此时可能发生有多个知识匹配成功，称这的知识进行匹配，此时可能发生有多个知识匹配成功，称这种情况为发生了冲突。
30、种情况为发生了冲突。l基本任务：基本任务：l解决冲突，选择其中的一条规则来执行。解决冲突，选择其中的一条规则来执行。l基本思想：基本思想：对知识进行排序对知识进行排序l按针对性排序按针对性排序l按匹配度进行排序按匹配度进行排序l根据领域问题的特点进行排序根据领域问题的特点进行排序4. 冲突消解策略冲突消解策略284.1.3 模式匹配及其变量代换模式匹配及其变量代换l模式匹配是指两个知识模式（如两个谓词公式、两个框架模式匹配是指两个知识模式（如两个谓词公式、两个框架片断等）的比较，检查这两个知识模式是否完全一致或近片断等）的比较，检查这两个知识模式是否完全一致或近似一致。如果两者完全一致，或者虽
31、不完全一致但其相似似一致。如果两者完全一致，或者虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。可匹配。 l按匹配时两个知识模式的相似程度划分，模式匹配可分为：按匹配时两个知识模式的相似程度划分，模式匹配可分为：l确定性匹配确定性匹配l不确定性匹配不确定性匹配294.1.3 模式匹配及其变量代换模式匹配及其变量代换l确定性匹配确定性匹配是指两个知识模式完全一致，或者经是指两个知识模式完全一致，或者经过变量代换后变得完全一致。过变量代换后变得完全一致。l例如，设有如下两个知识模式：例如，设有如下两个知识模式： P1：
32、Father（李四，李小四）（李四，李小四）and Man (李小四李小四) P2：Father(x,y) and Man (y)l若用若用“李四李四”代换变量代换变量x，用，用“李小四李小四”代换变量代换变量y，则，则P1与与P2就变得完全一致。就变得完全一致。l不确定性匹配不确定性匹配是指两个知识模式不完全一致，但是指两个知识模式不完全一致，但从总体上看，它们的相似程度又落在规定的限度从总体上看，它们的相似程度又落在规定的限度内。内。304.1.3 模式匹配及其变量代换模式匹配及其变量代换l代换（置换）代换（置换）可简单的理解为是在一个谓词公式中可简单的理解为是在一个谓词公式中用置换项去替
33、换变量。用置换项去替换变量。l定义定义3.1代换（置换）是形如代换（置换）是形如l t1/x1,t2/x2,tn/xnl的有限集合。其中，的有限集合。其中，t1,t2,tn是项；是项；x1,x2,xn是互是互不相同的变元；不相同的变元；ti/xi表示用表示用ti替换替换xi。并且要求。并且要求ti与与xi不能相同，不能相同，xi不能循环地出现在另一个不能循环地出现在另一个ti中。中。314.1.3 模式匹配及其变量代换模式匹配及其变量代换l例如例如， a/x, c/y, f(b)/z 是一个置换。是一个置换。l但但g(y)/x, f(x)/y不是一个置换。不是一个置换。l原因是它在原因是它在x
34、与与y之间出现了循环置换现象。即当用之间出现了循环置换现象。即当用g(y)置置换换x,用用f(g(y)置换置换y时，既没有消去时，既没有消去x，也没有消去，也没有消去y。l若改为若改为g(a)/x, f(x)/y即可，即可，l原因是用原因是用g(a)置换置换x ，用，用f(g(a)置换置换y ，则消去了，则消去了x和和y。l通常，置换是用希腊字母通常，置换是用希腊字母、 、 等来表示的。等来表示的。324.1.3 模式匹配及其变量代换模式匹配及其变量代换l定义定义3.2 设设l =t1/x1,t2/x2,tn/xnl = u1/y1, u2/y2, , um/ym l是两个置换。则是两个置换。
35、则与与的复合（合成）也是一个置换的复合（合成）也是一个置换，记作，记作。它是从集合。它是从集合l t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , um/ym l中删去以下两种元素中删去以下两种元素l 当当ti=xi时，时， 删去删去ti/xi (i=1, 2 , n)；l 当当yj x1, x2 , xn 时，时， 删去删去uj/yj (j=1, 2 , m)l最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。334.1.3 模式匹配及其变量代换模式匹配及其变量代换l例例 设设= f(y)/x, z/y ，=a/x, b/y ,y/z ，求，求与与的的合成。
36、合成。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)的结果；的结果；y/y 中的中的y是置换是置换作用于作用于z的结果。的结果。l在该集合中，在该集合中，y/y满足定义中的条件满足定义中的条件，需要删除；，需要删除；a/x和和b/y满足定义中的条件满足定义中的条件，也需要删除。最后得，也需要删除。最后得l=f(b)/x, y/z344.1.3 模式匹配及其变量代换模式匹配及其变量代换l合一合一可理解为是寻找项对变量的
37、置换，使两个谓词公式一致。可理解为是寻找项对变量的置换，使两个谓词公式一致。可定义为：可定义为：l定义定义3.3 设有公式集设有公式集F=F1, F2,Fn，若存在一个置换，若存在一个置换，可使，可使l F1=F2=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一般来说，一个公式集的合一不是唯一的。一般来说，一个公式集的合一不是唯一的。354.1.3 模式匹配及其变量代换模式匹
38、配及其变量代换l定义定义3.4 设设是公式集是公式集F的一个合一，如的一个合一，如果对果对F的任一个合一的任一个合一都存在一个置换都存在一个置换，使得使得=，则称，则称是一个最一般合一。是一个最一般合一。（Most General Unifier）l一个公式集的最一般合一是唯一的。一个公式集的最一般合一是唯一的。364.1.3 模式匹配及其变量代换模式匹配及其变量代换l差异集的概念。差异集的概念。l设有如下两个谓词公式：设有如下两个谓词公式： F1：P（x, y, z） F2：P (x, f (A), h(B) )分别从分别从F1与与F2的第一个符号开始，逐个向右的第一个符号开始，逐个向右比较
39、，此时发现比较，此时发现F1与与F2构差异集：构差异集：D1=y, f (A)， D2=z, h(B)374.1.3 模式匹配及其变量代换模式匹配及其变量代换l求最一般合一算法求最一般合一算法（1）初始化，令）初始化，令k=0, Fk=F,k=。其中，。其中，是代换空集。是代换空集。（2）若）若Fk只含一个表达式，则算法停止，只含一个表达式，则算法停止，k就是最一般合一；就是最一般合一；否则转步骤（否则转步骤（3）。）。（3）找出）找出Fk的差异集的差异集Dk。 （4）若）若Dk中存在变元中存在变元xk和项和项tk，且，且xk不在不在tk中出现，则：中出现，则：k+1= tk/xkFk+1=F
40、k tk/xkk=k+1转步骤（转步骤（2）；否则，）；否则， 算法终止，算法终止，F的最一般合一不存在。的最一般合一不存在。384.1.3 模式匹配及其变量代换模式匹配及其变量代换例例 设有公式集设有公式集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) 394.1.3 模式匹配及其变量代换模式匹配及其变量代换Loop 1：F0= P (A, x, f (g (y), P(z, f (z), f (u) 含
41、有含有2个表达式，故个表达式，故0不是最一般合一。不是最一般合一。F0的差异集的差异集D0=A，z，可有代换，可有代换A/z，1=0 A/z=A/zF1=F0A/z= P(A, x, f (g (y), P(A, f (A), f (u) 404.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
42、)/xF2=F1f (A)/x= P(A, f (A), f (g (y), P(A, f (A), f (u) 414.1.3 模式匹配及其变量代换模式匹配及其变量代换Loop 3： F2= P(A, f (A), f (g (y),P(A, f (A), 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,
43、 f (A), f (g(y) = P(A, f (A), f (g (y) 424.1.3 模式匹配及其变量代换模式匹配及其变量代换Loop 4：F3中只含有一个表达式，故算法成功中只含有一个表达式，故算法成功终止，终止，3 =A/z, f (A)/x, g (y)/u，即为公式集，即为公式集F的最一般合一。的最一般合一。43l可以输入公式集，对不符合规范的公式集要报可以输入公式集，对不符合规范的公式集要报错，符合规范的公式集进入求最一般合一步骤。错，符合规范的公式集进入求最一般合一步骤。l如果有最一般合一，要求显示每一步过程的差如果有最一般合一，要求显示每一步过程的差异集和代换，最后输出解
44、；如果没有最一般合异集和代换，最后输出解；如果没有最一般合一，最后要作出判断。一，最后要作出判断。44第第4章章 经典逻辑推理经典逻辑推理l4.1 推理的基本概念推理的基本概念l4.2 自然演绎推理自然演绎推理l4.3 归结演绎推理归结演绎推理l4.4 与与/或形演绎推理或形演绎推理454.2 自然演绎推理自然演绎推理l自然演绎推理自然演绎推理l从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。结论的过程称为自然演绎推理。l自然演绎推理最基本的推理规则是三段论推理，它包括：自然演绎推理最基本的推理规则
45、是三段论推理，它包括：l假言推理假言推理 P, PQ Ql拒取式拒取式 Q, PQ Pl假言三段论假言三段论 PQ, QR PRl例例 设已知如下事实：设已知如下事实：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为真为真464.2 自然演绎推理自然演绎推理l例例 设已知如下事实：设已知如下事实：l(1) 只要是需要编程序的课，王程都喜欢。只要是需要编程序的课，王程都喜欢。l(2) 所
46、有的程序设计语言课都是需要编程序的课。所有的程序设计语言课都是需要编程序的课。l(3) C是一门程序设计语言课。是一门程序设计语言课。l求证：王程喜欢求证：王程喜欢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应用推理规则进行推理：应用
47、推理规则进行推理：l Lang(y)Prog(y) 全称固化全称固化l Lang(C)，Lang(y)Prog(y) Prog(C) 假言推理假言推理 C/yl Prog(C), Prog(x)Like(Wang , x) Like(Wang , C) 假言推理假言推理 C/xl因此，王程喜欢因此，王程喜欢C这门课。这门课。474.2 自然演绎推理自然演绎推理l 优点：优点：定理证明过程自然，易于理解，并且有丰富定理证明过程自然，易于理解，并且有丰富的推理规则可用。的推理规则可用。l 缺点：缺点：是容易产生知识爆炸，推理过程中得到的中是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递
48、增，对于复杂问题的推理不利，间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。甚至难以实现。 48第第4章章 经典逻辑推理经典逻辑推理l4.1 推理的基本概念推理的基本概念l4.2 自然演绎推理自然演绎推理l4.3 归结演绎推理归结演绎推理l4.4 与与/或形演绎推理或形演绎推理494.3 归结演绎推理归结演绎推理l在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质定理证明的实质，就是要对前提，就是要对前提P和结论和结论Q，证明，证明PQ永真。永真。l要证明要证明PQ永真，就是要证明永真，就是要证明P
49、Q在任何一个非空的个体域上都在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。是永真的。这将是非常困难的，甚至是不可实现的。l为此，人们进行了大量的探索，后来发现可以为此，人们进行了大量的探索，后来发现可以采用反证法的思想采用反证法的思想，把关于永真性的证明转化为关于不可满足性的证明。把关于永真性的证明转化为关于不可满足性的证明。l即要证明即要证明PQ永真，只要能够证明永真，只要能够证明PQ是不可满足的就可以了是不可满足的就可以了(原因是原因是 (PQ) ( PQ) P Q 。l这方面最有成效的工作就是这方面最有成效的工作就是鲁宾逊归结原理鲁宾逊归结原理。它使定理证明的机
50、械。它使定理证明的机械化成为现实。归结演绎推理是一种基于鲁宾逊（化成为现实。归结演绎推理是一种基于鲁宾逊（Robinson）归结）归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于于1965年在海伯伦（年在海伯伦（Herbrand）理论的基础上提出的一种基于逻）理论的基础上提出的一种基于逻辑的辑的“反证法反证法”。504.3 归结演绎推理归结演绎推理l4.3.1 谓词公式化为子句集谓词公式化为子句集l4.3.2 归结原理归结原理l4.3.3 归结反演归结反演l4.3.4 基于归结反演的问题求解基于归结反演的问题求解l4.3