确定性推理方法幻灯片.ppt

确定性推理方法确定性推理方法第1页，共74页，编辑于2022年，星期一确定性推理方法确定性推理方法l l知知知知识识识识是是是是人人人人工工工工智智智智能能能能研研研研究究究究的的的的一一一一个个个个核核核核心心心心问问问问题题题题，它它它它包包包包括括括括两两两两个个个个方方方方面面面面：知知知知识识识识表表表表示示示示和和和和知知知知识识识识推推推推理理理理，即即即即如如如如何何何何在在在在人人人人工工工工智智智智能能能能中中中中清清清清晰晰晰晰地地地地表表表表示示示示人人人人类类类类的的的的常常常常识识识识，并并并并运运运运用用用用这这这这些些些些常识去进行符合人类行为的推理。常识去进行符合人类行为的推理。常识去进行符合人类行为的推理。常识去进行符合人类行为的推理。l l 按按按按照照照照推推推推理理理理过过过过程程程程所所所所用用用用知知知知识识识识的的的的确确确确定定定定性性性性，推推推推理理理理可可可可分分分分为为为为确确确确定定定定性性性性推推推推理理理理和和和和不不不不确确确确定定定定性性性性推推推推理理理理。自自自自然然然然演演演演绎绎绎绎推推推推理理理理和和和和归归归归结结结结推推推推理理理理是是是是经经经经典典典典的的的的确确确确定定定定性性性性推推推推理理理理，它它它它们们们们以以以以数数数数理理理理逻逻逻逻辑辑辑辑的的的的有有有有关关关关理理理理论论论论、方方方方法法法法和和和和技技技技术术术术为为为为理理理理论论论论基基基基础础础础，是是是是机机机机械械械械化化化化的的的的、可可可可在在在在计计计计算算算算机机机机上上上上加加加加以以以以实实实实现现现现的的的的推推推推理方法。理方法。理方法。理方法。第2页，共74页，编辑于2022年，星期一第第3章章 主要内容主要内容l l3.1 推理概述推理概述 l l3.2确定性推理的逻辑基础确定性推理的逻辑基础 l l3.3 演绎推理方法演绎推理方法 l l3.4归结推理方法归结推理方法 l l3.5 归结过程中的控制策略归结过程中的控制策略 第3页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.1 推理的概念推理的概念 l l3.1.2 推理的方法推理的方法 l l3.1.3 推理的控制策略推理的控制策略 l l3.1.4 推理中的冲突推理中的冲突 第4页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.1 3.1.1 推理的概念推理的概念推理的概念推理的概念 所所谓谓推推理理是是指指按按照照某某种种策策略略从从已已知知事事实实出出发发去去推推出出结结论论的的过过程程。知知识识推推理理是是指指在在计计算算机机或或智智能能机机器器中中，在在知知识识表表达达的的基基础础上上，利利用用形形式式化化的知识模型，进行机器思维求解问题，实现状态转移的智能操作序列。的知识模型，进行机器思维求解问题，实现状态转移的智能操作序列。推推理理所所用用的的事事实实可可分分为为两两种种情情况况，一一种种是是与与求求解解问问题题有有关关的的初初始始证证据据；另另一一种种是是推理过程中所得到的中间结论，这些中间结论可以作为进一步推理的已知事实或证据。推理过程中所得到的中间结论，这些中间结论可以作为进一步推理的已知事实或证据。例：例：商品是用来交换的，所以，有些用来交换的是商品。商品是用来交换的，所以，有些用来交换的是商品。老虎是要吃人的，东北虎是老虎；所以，东北虎是要吃人的。老虎是要吃人的，东北虎是老虎；所以，东北虎是要吃人的。智智能能系系统统的的推推理理包包括括两两个个方方面面的的基基本本问问题题：一一个个方方面面是是推推理理的的方方法法，另另一一个个方方面面是推理的控制策略。是推理的控制策略。第5页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法 推推理理有有很很多多种种方方法法，根根据据知知识识表表示示方方式式分分类类分分为为“图图搜搜索索”方方法法及及“逻逻辑辑论论证证”方方法法；根根据据逻逻辑辑基基础础分分类类可可分分为为演演绎绎推推理理、归归纳纳推推理理、默默认认（缺缺省省）推推理理；根根据据知知识识的的确确定定性性分分类类分分为为确确定定性性推推理理与与非非确确定定性性推推理理；根根据据推推理理过过程程的的单单调调性性分分类类分分为为单单调调推推理、非单调推理。理、非单调推理。1演绎推理：演绎推理：演演绎绎推推理理是是一一种种由由一一般般到到个个别别的的推推理理方方法法，其其核核心心是是三三段段论论，由由一一个个大大前前提提、一个小前提和一个结论这三部分组成的。其逻辑式为：一个小前提和一个结论这三部分组成的。其逻辑式为：l大前提是已知的一般性知识或推理过程得到的判断；大前提是已知的一般性知识或推理过程得到的判断；l小前提是关于某种具体情况或某个具体实例的判断；小前提是关于某种具体情况或某个具体实例的判断；l结论是由大前提推出的，并且适合于小前提的判断。结论是由大前提推出的，并且适合于小前提的判断。第6页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法 1演绎推理：演绎推理：例：有如下三个判断：例：有如下三个判断：计算机系的学生都会编程序；（一般性知识）计算机系的学生都会编程序；（一般性知识）程强是计算机系的一位学生；（具体情况）程强是计算机系的一位学生；（具体情况）因此程强会编程序。（结论）因此程强会编程序。（结论）这这是是一一个个三三段段论论推推理理。其其中中：“计计算算机机系系的的学学生生都都会会编编程程序序”是是大大前前提提，“程程强强是是计计算算机机系系的的一一位位学学生生”是是小小前前提提，那那么么“程程强强会会编编程程序序”是是经经演演绎推出来的结论。其结论蕴含在大前提中，这就是典型的演绎推理三段论。绎推出来的结论。其结论蕴含在大前提中，这就是典型的演绎推理三段论。第7页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法2归纳归纳推理推理 归归纳纳推推理理的的基基本本思思想想是是：先先从从已已知知事事实实中中猜猜测测出出一一个个结结论论，然然后后对对这这个个结论结论的正确性加以的正确性加以验证验证。例如常用的数学。例如常用的数学归纳归纳法。法。归归纳纳推推理理的的类类型型按按照照所所选选取取的的事事例例的的广广泛泛性性可可分分为为完完全全归归纳纳推推理理、不不完完全全归归纳纳推推理理。归归纳纳推推理理按按照照推推理理所所使使用用的的方方法法可可分分为为枚枚举举归归纳纳推推理理、类类比比归归纳纳推推理、默理、默认认推理等。推理等。（1）枚枚举举归归纳纳推推理理：是是由由已已观观察察到到的的事事物物都都有有某某属属性性，而而没没有有观观察察到到相反的事例，从而推出某相反的事例，从而推出某类类事物都有某属性。事物都有某属性。（2）类类比比归归纳纳推推理理：指指在在两两个个或或两两类类事事物物有有许许多多属属性性都都相相同同或或相相似似的的基基础础上上，推出它推出它们们在其它属性上也相同或相似的一种在其它属性上也相同或相似的一种归纳归纳推理。推理。（3）默默认认推推理理：称称为为缺缺省省推推理理，它它是是在在知知识识不不完完全全的的情情况况下下假假设设某某些些条条件件已已经经具具备备所所进进行的推理。行的推理。第8页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法3演绎推理与归纳推理的区别：演绎推理与归纳推理的区别：演演绎绎推推理理是是在在已已知知领领域域内内的的一一般般性性知知识识的的前前提提下下，通通过过演演绎绎求求解解一一个个具具体体问问题题或或者者证证明明一一个个结结论论的的正正确确性性。它它所所得得出出的的结结论论实实际际上上早早已已蕴蕴含含在在一一般般性性知知识识的的前前提提中中，演演绎绎推推理理只只不不过过是是将将已已有有事事实实揭揭露露出出来来，因此它不能增殖新知识。因此它不能增殖新知识。归归纳纳推推理理所所推推出出的的结结论论是是没没有有包包含含在在前前提提内内容容中中的的。这这种种由由个个别别事事物或现象推出一般性知识的过程，是增殖新知识的过程。物或现象推出一般性知识的过程，是增殖新知识的过程。4推理的其它分类：推理的其它分类：（1）确定性推理与不确定推理）确定性推理与不确定推理（2）单调推理与非单调推理）单调推理与非单调推理（3）启发式推理与非启发式推理）启发式推理与非启发式推理第9页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略 推推理理的的控控制制策策略略是是指指如如何何使使用用领领域域知知识识使使推推理理过过程程尽尽快快达达到到目目标标的的策策略略，主主要要是是指指推推理理方方向向的的选选择择、推推理理时时所所用用的的搜搜索索策策略略及及冲冲突突解解决决策策略略等等。推理的控制策略包括推理策略和搜索策略。推理的控制策略包括推理策略和搜索策略。l推理策略主要解决推理方向、求解策略、冲突消解策略等问题。推理策略主要解决推理方向、求解策略、冲突消解策略等问题。l搜索策略主要解决推理线路、推理效果、推理效率等问题。搜索策略主要解决推理线路、推理效果、推理效率等问题。按按照照对对推推理理方方向向的的控控制制，推推理理可可分分为为正正向向推推理理、反反向向推推理理、混混合合推推理及双向推理四种情况。一般都要求系统具有三个要素：理及双向推理四种情况。一般都要求系统具有三个要素：l一个存放知识的知识库一个存放知识的知识库 l一个存放初始事实和中间结果的数据库一个存放初始事实和中间结果的数据库 l一个用于推理的推理机一个用于推理的推理机第10页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.1 正向推理正向推理正正向向推推理理是是由由已已知知事事实实出出发发，正正向向使使用用推推理理规规则则向向结结论论方方向向的的推推理，算法步骤描述如下：理，算法步骤描述如下：（1）把把用用户户提提供供的的初初始始证证据据放放入入综综合数据库；合数据库；（2）检检查查综综合合数数据据库库中中是是否否包包含含了了问问题题的的解解，若若已已包包含含，则则求求解解结结束束，并并成功推出；否则执行下一步；成功推出；否则执行下一步；第11页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.1 正向推理正向推理（3）检检查查知知识识库库中中是是否否有有可可用用知知识识，若若有有，形形成成当当前前可可用用知知识识集，执行下一步；否则转集，执行下一步；否则转(5)。（4）按按照照某某种种冲冲突突消消解解策策略略，从从当当前前可可用用知知识识集集中中选选出出一一条条规规则则进进行行推推理理，并并将将推推出出的的新新事事实实加入综合数据库种，然后转加入综合数据库种，然后转(2)。第12页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.1 正向推理正向推理（5）询询问问用用户户是是否否可可以以进进一一步步补补充充新新的的事事实实，若若可可补补充充，则则将将补补充充的的新新事事实实加加入入综综合合数数据据库库中中，然然后后转转(3)；否否则则表表示示无无解解，失失败败退退出。出。第13页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略例：请用正向推理完成以下问题的求解：假设知识库中包含有以下例：请用正向推理完成以下问题的求解：假设知识库中包含有以下2 2条规则：条规则：r1 r1：IF B THEN C IF B THEN C r2 r2：IF A THEN B IF A THEN B已知初始证据已知初始证据A A，求证目标，求证目标C C。解：本例的推理过程如下：解：本例的推理过程如下：推推理理开开始始前前，综综合合数数据据库库为为空空。推推理理开开始始后后，先先把把A A放放入入综综合合数数据据库库，然然后后检检查查综综合合数数据据库库中中是是否否含含有有该该问问题题的的解解，回回答答为为“N”“N”。接接着着检检查查知知识识库库中中是是否否有有可可用用知知识识，显显然然r2r2可可用用，形形成成仅仅含含r2r2的的知知识识集集。从从该该知知识识集集中中取取出出r2r2，推推出出新新的的实实事事B B，将将B B加加入入综综合合数数据据库库，检检查查综综合合数数据据库库中中是是否否含含有有目目标标C C，回回答答为为“N”“N”。再再检检查查知知识识库库中中是是否否有有可可用用知知识识，此此时时由由于于B B的的加加入入使使得得r1r1为为可可用用，形形成成仅仅含含r1r1的的知知识识集集。从从该该知知识识集集中中取取出出r1r1，推推出出新新的的实实事事C C，将将C C加加入入综综合合数数据据库库，检检查查综综合合数数据据库库中中是是否否含含有有目目标标C C，回回答答为为“Y”“Y”。它说明综合数据库中已经含有问题的解，推理成功结束，目标它说明综合数据库中已经含有问题的解，推理成功结束，目标C C得证。得证。第14页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.2 反向推理反向推理 反反向向推推理理是是以以某某个个假假设设目目标标作作为为出出发发点点的的一一种种推推理理，又又称称为为目目标标驱驱动推理或逆向推理。动推理或逆向推理。反向推理过程如图：反向推理过程如图：第15页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.2 反向推理反向推理算法描述如下：算法描述如下：（1）将要求证的目标（称为假设）构成一个假设集；）将要求证的目标（称为假设）构成一个假设集；（2）从从假假设设集集中中选选出出一一个个假假设设，检检查查该该假假设设是是否否在在综综合合数数据据库库中中，若若在在，则则该该假假设设成成立立，此此时时，若若假假设集为空，则成功退出，否则仍执行设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步；若该假设不在数据库中，则执行下一步；（3）检检查查该该假假设设是是否否可可由由知知识识库库的的某某个个知知识识导导出出，若若不不能能由由某某个个知知识识导导出出，则则询询问问用用户户该该假假设设是是否否为为可可由由用用户户证证实实的的原原始始事事实实，若若是是，该该假假设设成成立立，并并将将其其放放入入综综合合数数据据库库，再再重重新新寻寻找找新新的的假设，若不是，则转假设，若不是，则转(5)；若能由某个知识导出，则执行下一步；若能由某个知识导出，则执行下一步；（4）将知识库中可以导出该假设的所有知识构成一个可用知识集；）将知识库中可以导出该假设的所有知识构成一个可用知识集；（5）检查可用知识集是否为空，若是，失败退出；否则执行下一步；）检查可用知识集是否为空，若是，失败退出；否则执行下一步；（6）按冲突消解策略从可用知识集中取出一个知识，继续；）按冲突消解策略从可用知识集中取出一个知识，继续；（7）将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转）将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。第16页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略例：请用反向推理完成以下问题的求解：假设知识库中包含有以下例：请用反向推理完成以下问题的求解：假设知识库中包含有以下2 2条规则：条规则：r1 r1：IF B THEN C IF B THEN C r2 r2：IF A THEN B IF A THEN B已知初始证据已知初始证据A A，求证目标，求证目标C C。解解：其其推推理理过过程程如如下下：推推理理开开始始前前，综综合合数数据据库库和和假假设设集集均均为为空空。先先将将初初始始证证据据A和和目目标标C分分别别放放入入综综合合数数据据库库和和假假设设集集，然然后后从从假假设设集集中中取取出出一一个个假假设设C，查查找找C是是否否为为综综合合数数据据库库中中的的已已知知事事实实，回回答答为为“N”。再再检检查查C是是否否能能被被知知识识库库中中的的知知识识所所导导出出，发发现现C可可由由r1导导出出，于于是是r1被被放放入入可可用用知知识识集集。接接着着从从可可用用知知识识集集中中取取出出r1，将将其其前前提提条条件件B作作为为新新的的假假设设放放入入假假设设集集。检检查查B是是否否为为综综合合数数据据库库中中的的实实事事，回回答答为为“N”。再再检检查查B是是否否能能被被知知识识库库中中的的知知识识所所导导出出，发发现现B可可由由r2导导出出，于于是是r2被被放放入入可可用用知知识识集集。从从可可用用知知识识集集中中取取出出r2，将将其其前前提提条条件件A作作为为新新的的假假设设放放入入假假设设集集。然然后后从从假假设设集集中中取取出出A，检检查查A是是否否为为综综合合数数据据库库中的实事，回答为中的实事，回答为“Y”。说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。得证。第17页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.3 正反向混合推理正反向混合推理 正正向向推推理理和和反反向向推推理理相相结结合合的的推推理理方方法法称称为为正正反反向向混混合合推推理理。混混合合推推理理的的方法包括：方法包括：1.先正向后逆向先正向后逆向2.先逆向后正向先逆向后正向3.双向混合双向混合第18页，共74页，编辑于2022年，星期一3.1 推理概述推理概述 l l3.1.4 3.1.4 推理中的冲突推理中的冲突推理中的冲突推理中的冲突 在在推推理理过过程程中中，系系统统要要不不断断地地用用数数据据库库中中的的事事实实与与知知识识库库中中的的规规则则进进行行匹匹配配，当当有有一一个个以以上上规规则则的的条条件件部部分分和和当当前前数数据据库库相相匹匹配配时时，就就需需要要有有一一种种策策略略来来决决定定首首先先使使用用哪哪一一条条规规则则，这这就就是是冲冲突突解解决决策策略略。冲冲突突解解决决策策略实际上就是确定规则的启用顺序。略实际上就是确定规则的启用顺序。常用排序方法有如下几种常用排序方法有如下几种:（1）按专一性排序）按专一性排序 （2）按规则排序）按规则排序（3）按数据排序）按数据排序 （4）按就近原则排序）按就近原则排序（5）上下文限制）上下文限制 （6）按匹配度排序）按匹配度排序（7）按条件个数排序）按条件个数排序第19页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.1 3.2.1 命题公式的解释命题公式的解释命题公式的解释命题公式的解释l l3.2.2 3.2.2 等价式等价式等价式等价式l l3.2.3 3.2.3 永真蕴含式永真蕴含式永真蕴含式永真蕴含式l l3.2.4 3.2.4 前束范式与前束范式与前束范式与前束范式与SkolemSkolem范式范式范式范式l l3.2.5 3.2.5 置换与合一置换与合一置换与合一置换与合一 本本节节中中要要考考虑虑在在人人工工智智能能中中如如何何利利用用谓谓词词逻逻辑辑表表示示来来完完成成由由问问题题到到结结论论的的推理。推理。第20页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.1 3.2.1 命题公式的解释命题公式的解释命题公式的解释命题公式的解释 定定义义3.1 设设D是是谓谓词词公公式式P的的非非空空个个体体域域，若若对对P中中的的个个体体常常量量、函函数数和和谓谓词词按如下按如下规规定定赋值赋值：（1）为为每个个体常量指派每个个体常量指派D中的一个元素；中的一个元素；（2）为为每个每个n元函数指派一个从元函数指派一个从 到到D的一个映射，其中的一个映射，其中（3）为为每个每个n元元谓词谓词指派一个从指派一个从 到到F，T的映射。的映射。则则称称这这些指派些指派为为P在在D上的一个解上的一个解释释I。定定义义3.2 对对于于谓谓词词公公式式P，如如果果至至少少存存在在D上上的的一一个个解解释释，使使公公式式P在在此此解解释释下的真下的真值为值为T，则则称公式称公式P在在D上是可上是可满满足的。足的。第21页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.2 3.2.2 等价式等价式等价式等价式 定定义义3.3 设设P与与Q是是D上上的的两两个个谓谓词词公公式式，若若对对D上上的的任任意意解解释释，P与与Q都都有有相相同同的的真真值值，则则称称P与与Q在在D 上上是是等等价价的的。如如果果D是是任任意意非非空空个个体体域域，则则称称P与与Q是等价的，是等价的，记记作作 。常用谓词公式的等价式包括：常用谓词公式的等价式包括：（1）双重否定律：）双重否定律：（2）交换律：）交换律：（3）结合律：）结合律：（4）分配律：）分配律：（5）摩根定律：）摩根定律：第22页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.2 3.2.2 等价式等价式等价式等价式常用谓词公式的等价式包括：常用谓词公式的等价式包括：（6）吸收律：）吸收律：（7）补余律）补余律:（8）连词化归律）连词化归律:（9）量词转换律）量词转换律:（10）量词分配律）量词分配律:第23页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.3 3.2.3 永真蕴含式永真蕴含式永真蕴含式永真蕴含式 定定义义3.4 对谓词对谓词公式公式P和和Q，如果，如果 永真，永真，则则称称P 永真永真蕴蕴含含Q，且称，且称Q为为P的的逻辑结论逻辑结论，P为为Q的前提，的前提，记记作作 。常用常用永真蕴含式永真蕴含式包括：包括：（1）化简式：）化简式：（2）附加式：）附加式：（3）析取三段论：）析取三段论：（4）假言推理：）假言推理：（5）拒取式：）拒取式：第24页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.3 3.2.3 永真蕴含式永真蕴含式永真蕴含式永真蕴含式 常用永真常用永真蕴蕴含式包括：含式包括：（6）假言三段）假言三段论论：（7）二）二难难推理：推理：（8）全称固化：）全称固化：其中，其中，y是个体域中的任一个体，是个体域中的任一个体，依此可消去依此可消去谓词谓词公式中的全称量公式中的全称量词词。（9）存在固化：）存在固化：其中，其中，y是个体域中某一个可以使是个体域中某一个可以使 P(y)为为真的个体，依此可消去真的个体，依此可消去谓词谓词公式中的存在量公式中的存在量词词。第25页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.4 3.2.4 前束范式与前束范式与前束范式与前束范式与SkolemSkolem范式范式范式范式 范式分为两种：前束范式与范式分为两种：前束范式与Skolem范式。范式。定定义义3.5 设设F为为一一谓谓词词公公式式，如如果果其其中中的的所所有有量量词词均均非非否否定定地地出出现现在在公公式式的的最最前前面面，且且它它们们的的辖辖域域为为整整个个公公式式，则则称称F为为前前束束范范式式。一一般般形形式：式：其中，其中，为前缀，它是一个由全称量词或存在量词组成的量为前缀，它是一个由全称量词或存在量词组成的量词串；词串；为母式，它是一个不含任何量词的谓词公式。为母式，它是一个不含任何量词的谓词公式。例例:定定义义3.6 如果前束范式中所有的存在量如果前束范式中所有的存在量词词都在全称量都在全称量词词之前，之前，则则称称这这种形式的种形式的谓词谓词公式公式为为Skolem范式。范式。例：例：第26页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.5 3.2.5 置换与合一置换与合一置换与合一置换与合一 1置置换换：定定义义3.7置置换换是形如：是形如：的有限集合。其中，的有限集合。其中，是是项项，是互不相是互不相同的同的变变元；元；表示用表示用t1 替替换换x1，并且要求，并且要求t1 与与x1 不能相同，不能相同，x1 不能循不能循环环地出地出现现在另一个在另一个t1 中。中。定定义义3.8 设设 是一个置是一个置换换，F是一个是一个谓词谓词公式，把公式公式，把公式F中中出出现现的所有的所有 换换成成 得到一个新的公式得到一个新的公式G，记记作作G=F，称，称G为为F在置在置换换下的例示。下的例示。第27页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.5 3.2.5 置换与合一置换与合一置换与合一置换与合一 1置置换换：定定义义3.9 设设是两个置是两个置换换。则则与与的合成也是一个置的合成也是一个置换换，记记作作 。它是从集合。它是从集合:中中删删去以下两种元素：去以下两种元素：当当 时时，删删去去 当当 时时，删删去去 最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。第28页，共74页，编辑于2022年，星期一3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.5 3.2.5 置换与合一置换与合一置换与合一置换与合一2合一：合一：定义定义3.10 设有公式集设有公式集 若存在一个置换若存在一个置换，可使，可使:则称则称是是F的一个合一。称的一个合一。称F1,F2,Fn是可合一的。是可合一的。定定义义3.11 设设 是是公公式式集集F的的一一个个合合一一，如如果果对对F的的任任一一个个合合一一 都都存存在在一一个个置置换换 ，使得，使得 ，则称，则称 是一个最一般合一。是一个最一般合一。第29页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1 什么是演绎推理什么是演绎推理l l3.3.2 演绎推理的特点演绎推理的特点 基基于于规规则则的的演演绎绎推推理理是是一一种种直直接接的的推推理理方方法法。它它不不再再把把有有关关的的知知识识转转化化为为子子句句集集，而而是是把把有有关关问问题题的的知知识识和和信信息息划划分分为为规规则则与与事事实实两两种种类类型型。规规则则由由包包含含蕴蕴含含形形式式的的表表达达式式表表示示，事事实实由由无无蕴蕴含含式式的的表表达达式式表表示示，并并画画出出相相应应的的与与/或或图，然后通过规则进行演绎推理。图，然后通过规则进行演绎推理。第30页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1 3.3.1 什么是演绎推理什么是演绎推理什么是演绎推理什么是演绎推理 所所谓谓自自然然演演绎绎推推理理，在在已已知知一一组组为为真真的的事事实实条条件件下下，直直接接运运用用命命题题和和谓谓词词逻逻辑的一系列基本规则或定律来推出结论，该过程称为自然演绎推理。辑的一系列基本规则或定律来推出结论，该过程称为自然演绎推理。基基于于规规则则的的演演绎绎推推理理可可分分为为正正向向演演绎绎推推理理、反反向向演演绎绎推推理理和和正正反反向向混混合合演绎推理。演绎推理。第31页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1 3.3.1 什么是演绎推理什么是演绎推理什么是演绎推理什么是演绎推理3.3.1.1 正向演绎推理正向演绎推理1 事实表达式及其与事实表达式及其与/或图或图正向演绎推理步骤如下：正向演绎推理步骤如下：1)利用等价式利用等价式PQ与与P Q消去蕴含符消去蕴含符“”。2)把否定符号把否定符号“”移到每个谓词符号的前面。移到每个谓词符号的前面。3)变量标准化，即重新命名变量，使不同量词约束的变量有不同的名字。变量标准化，即重新命名变量，使不同量词约束的变量有不同的名字。4)引入引入Skolem函数消去存在量词。函数消去存在量词。5)将公式化为前束形。将公式化为前束形。6)略去全称量词略去全称量词(这时默认事实表达式中尚存的变量是全称量词量化的变量这时默认事实表达式中尚存的变量是全称量词量化的变量)。7)重新命名变量；使同一变量不出现在不同的主要合取式中。重新命名变量；使同一变量不出现在不同的主要合取式中。第32页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理2F规则规则 在与在与/或形正向演或形正向演绎绎系系统统中，通常要求中，通常要求F规则应规则应具有如下形式：具有如下形式：L为单为单文字，文字，W为为与与/或形公式。或形公式。其其变换变换步步骤骤如下：如下：（1）暂时暂时消去消去蕴蕴含符号含符号“”。（2）把把否否定定符符号号“”移移到到紧紧靠靠谓谓词词的的位位置置上上，使使其其作作用用域域仅仅限限于于单单个个谓词谓词。（3）引入）引入Skolem函数，消去存在量函数，消去存在量词词。（4）化成前束式，消去全部全称量）化成前束式，消去全部全称量词词。（5）恢复）恢复蕴蕴含式表示。含式表示。第33页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理3规则正向演绎规则正向演绎 与与/或或树树正正向向演演绎绎系系统统要要求求目目标标公公式式用用子子句句形形表表示示。如如果果目目标标公公式式不不是是子子句句形形，则需要化成子句形。则需要化成子句形。规规则则正正向向演演绎绎推推理理过过程程是是先先用用与与/或或树树把把已已知知事事实实表表示示出出来来，然然后后再再用用F规规则则的的前前件件和和与与或或树树的的叶叶节节点点进进行行匹匹配配，并并通通过过一一个个匹匹配配弧弧把把匹匹配配成成功功的的F规规则则加加入入到到与与/或或树树中中，依依此此使使用用F规规则则，直直到到产产生生一一个个含含有有以以目目标标节节点点为终止节点的解图为止。为终止节点的解图为止。第34页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理3规则正向演绎规则正向演绎(1)命题逻辑规则演绎过程：命题逻辑规则演绎过程：例：设已知事实为：例：设已知事实为：F规则为：规则为：目标公式为：目标公式为：命题逻辑的规则演绎过程第35页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理3规则正向演绎规则正向演绎(2)谓词逻辑规则演绎过程谓词逻辑规则演绎过程例例：设设已已知知事事实实的的与与/或或形形表表示示为：为：F规则为：规则为：目标公式为：目标公式为：命题逻辑的规则演绎过程命题逻辑的规则演绎过程第36页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.1 3.3.1 什么是演绎推理什么是演绎推理什么是演绎推理什么是演绎推理3.3.1.2 逆向演绎推理逆向演绎推理从从目目标标表表达达式式出出发发，反反方方向向使使用用规规则则（B规规则则）对对目目标标表表达达式式的的与与或或图进行变换，最后得到含有事实节点的一致解图。图进行变换，最后得到含有事实节点的一致解图。1目标表达式的与或形表示：目标表达式的与或形表示：在在基基于于规规则则的的逆逆向向系系统统中中，要要用用对对偶偶形形式式对对目目标标表表达达式式进进行行Skolem化化。即即消消去去全全称称量量词词，对对受受全全称称量量词词约约束束的的变变量量用用Skolem函函数数或或者者常常量量代代替替，省省略略存存在在量量词词，所所有有变变量量默默认认为为受受存存在在量量词词约约束束，并并进进行行变变量量换换名，使得目标公式的主析取元之间具有不同的变量名。名，使得目标公式的主析取元之间具有不同的变量名。第37页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理1目标表达式的与或形表示：目标表达式的与或形表示：例：目标公式：例：目标公式：Skolem化后：化后：变量标准化：变量标准化：这这个个目目标标的的与与或或图图表表示示如如图图，其其子子句句集集可可以以从从结结束束在在端端节节点点的的解解图图集集中中读读得：得：第38页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理2规则的应用规则的应用 逆向演绎推理以逆向方式使用规则（称为逆向演绎推理以逆向方式使用规则（称为B规则），要求规则化简为以下形式：规则），要求规则化简为以下形式：其其中中，L为为单单文文字字，W是是与与或或形形；规规则则的的激激活活取取决决于于L和和与与或或图图叶叶节节点点的的匹配。匹配。逆逆向向系系统统演演绎绎过过程程的的结结束束条条件件是是生生成成的的与与或或图图含含有有事事实实表表达达式式，而而事事实实表表达达式式限限制制为为文文字字的的合合取取形形式式。当当事事实实表表达达式式有有一一个个文文字字同同与与或或图图中中某某一一个个端端节节点点所所标标记记的的文文字字（子子目目标标）匹匹配配上上时时，就就可可以以通通过过匹匹配配弧弧把把事事实实文文字字加加到到图图上上。这这样样当当最最后后得得到到的的与与或或图图包包含含一一个个结结束束在在事事实实节节点点上上的的一一致致解解图图时时，系系统统便便结结束束演演绎绎，一一个个一一致致解解图图是是解图中匹配弧置换集具有合一复合置换的那个解图。解图中匹配弧置换集具有合一复合置换的那个解图。第39页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理2规则规则的的应应用用例：下面通例：下面通过过一个一个简简例例说说明逆向系明逆向系统统的演的演绎过绎过程。程。设设有如下事有如下事实实：lFIDO是一只狗是一只狗lFIDO不叫不叫lFIDO摆摆尾巴尾巴lMYRTLE瞄瞄叫瞄瞄叫规则规则如下：如下：l摆摆尾巴的狗是友好的尾巴的狗是友好的l友好且不叫的是不令友好且不叫的是不令对对方害怕的方害怕的第40页，共74页，编辑于2022年，星期一3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理2规则规则的的应应用用例：例：l狗是狗是动动物物l猫是猫是动动物物l喵喵喵喵叫的是猫叫的是猫问题问题是：是否存在一只猫和一只狗，使是：是否存在一只猫和一只狗，使这这只猫不怕只猫不怕这这只狗？只狗？即目即目标标公式：公式：第41页，共74页，