确定性推理方法精品文稿.ppt

确定性推理方法确定性推理方法第1页，本讲稿共74页确定性推理方法确定性推理方法l l知知知知识识识识是是是是人人人人工工工工智智智智能能能能研研研研究究究究的的的的一一一一个个个个核核核核心心心心问问问问题题题题，它它它它包包包包括括括括两两两两个个个个方方方方面面面面：知知知知识识识识表表表表示示示示和和和和知知知知识识识识推推推推理理理理，即即即即如如如如何何何何在在在在人人人人工工工工智智智智能能能能中中中中清清清清晰晰晰晰地地地地表表表表示示示示人人人人类类类类的的的的常常常常识识识识，并运用这些常识去进行符合人类行为的推理。并运用这些常识去进行符合人类行为的推理。并运用这些常识去进行符合人类行为的推理。并运用这些常识去进行符合人类行为的推理。l l 按按按按照照照照推推推推理理理理过过过过程程程程所所所所用用用用知知知知识识识识的的的的确确确确定定定定性性性性，推推推推理理理理可可可可分分分分为为为为确确确确定定定定性性性性推推推推理理理理和和和和不不不不确确确确定定定定性性性性推推推推理理理理。自自自自然然然然演演演演绎绎绎绎推推推推理理理理和和和和归归归归结结结结推推推推理理理理是是是是经经经经典典典典的的的的确确确确定定定定性性性性推推推推理理理理，它它它它们们们们以以以以数数数数理理理理逻逻逻逻辑辑辑辑的的的的有有有有关关关关理理理理论论论论、方方方方法法法法和和和和技技技技术术术术为为为为理理理理论论论论基基基基础础础础，是是是是机机机机械械械械化化化化的的的的、可可可可在在在在计计计计算算算算机机机机上加以实现的推理方法。上加以实现的推理方法。上加以实现的推理方法。上加以实现的推理方法。第2页，本讲稿共74页第第3章章 主要内容主要内容l l3.13.1 推理概述推理概述推理概述推理概述 l l3.2确定性推理的逻辑基础确定性推理的逻辑基础 l l3.3演绎推理方法演绎推理方法 l l3.4归结推理方法归结推理方法 l l3.53.5 归结过程中的控制策略归结过程中的控制策略归结过程中的控制策略归结过程中的控制策略 第3页，本讲稿共74页3.1 推理概述推理概述 l l3.1.1 推理的概念推理的概念 l l3.1.2 推理的方法推理的方法 l l3.1.3 推理的控制策略推理的控制策略 l l3.1.4 推理中的冲突推理中的冲突 第4页，本讲稿共74页3.1 推理概述推理概述 l l3.1.1 3.1.1 推理的概念推理的概念推理的概念推理的概念 所所谓谓推推理理是是指指按按照照某某种种策策略略从从已已知知事事实实出出发发去去推推出出结结论论的的过过程程。知知识识推推理理是是指指在在计计算算机机或或智智能能机机器器中中，在在知知识识表表达达的的基基础础上上，利利用用形形式式化化的的知知识识模模型型，进进行行机器思维求解问题，实现状态转移的智能操作序列。机器思维求解问题，实现状态转移的智能操作序列。推推理理所所用用的的事事实实可可分分为为两两种种情情况况，一一种种是是与与求求解解问问题题有有关关的的初初始始证证据据；另另一一种种是是推推理理过过程程中中所所得得到到的的中中间间结结论论，这这些些中中间间结结论论可可以以作作为为进进一一步步推推理理的已知事实或证据。的已知事实或证据。例：例：商品是用来交换的，所以，有些用来交换的是商品。商品是用来交换的，所以，有些用来交换的是商品。老虎是要吃人的，东北虎是老虎；所以，东北虎是要吃人的。老虎是要吃人的，东北虎是老虎；所以，东北虎是要吃人的。智智能能系系统统的的推推理理包包括括两两个个方方面面的的基基本本问问题题：一一个个方方面面是是推推理理的的方方法法，另一个方面是推理的控制策略。另一个方面是推理的控制策略。第5页，本讲稿共74页3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法 推推理理有有很很多多种种方方法法，根根据据知知识识表表示示方方式式分分类类分分为为“图图搜搜索索”方方法法及及“逻逻辑辑论论证证”方方法法；根根据据逻逻辑辑基基础础分分类类可可分分为为演演绎绎推推理理、归归纳纳推推理理、默默认认（缺缺省省）推推理理；根根据据知知识识的的确确定定性性分分类类分分为为确确定定性性推推理理与与非非确确定定性性推推理理；根根据据推推理理过过程程的单调性分类分为单调推理、非单调推理。的单调性分类分为单调推理、非单调推理。1演绎推理：演绎推理：演演绎绎推推理理是是一一种种由由一一般般到到个个别别的的推推理理方方法法，其其核核心心是是三三段段论论，由由一一个个大大前前提提、一一个小前提和一个结论这三部分组成的。其逻辑式为：个小前提和一个结论这三部分组成的。其逻辑式为：l大前提是已知的一般性知识或推理过程得到的判断；大前提是已知的一般性知识或推理过程得到的判断；l小前提是关于某种具体情况或某个具体实例的判断；小前提是关于某种具体情况或某个具体实例的判断；l结论是由大前提推出的，并且适合于小前提的判断。结论是由大前提推出的，并且适合于小前提的判断。第6页，本讲稿共74页3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法 1演绎推理：演绎推理：例：有如下三个判断：例：有如下三个判断：计算机系的学生都会编程序；（一般性知识）计算机系的学生都会编程序；（一般性知识）程强是计算机系的一位学生；（具体情况）程强是计算机系的一位学生；（具体情况）因此程强会编程序。（结论）因此程强会编程序。（结论）这这是是一一个个三三段段论论推推理理。其其中中：“计计算算机机系系的的学学生生都都会会编编程程序序”是是大大前前提提，“程程强强是是计计算算机机系系的的一一位位学学生生”是是小小前前提提，那那么么“程程强强会会编编程程序序”是是经经演演绎绎推推出出来来的的结结论论。其其结结论论蕴蕴含含在在大大前前提提中中，这这就就是是典典型的演绎推理三段论。型的演绎推理三段论。第7页，本讲稿共74页3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法2归纳推理 归纳推理的基本思想是：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以验证。例如常用的数学归纳法。归纳推理的类型按照所选取的事例的广泛性可分为完全归纳推理、不完全归纳推理。归纳推理按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、默认推理等。（1）枚举归纳推理：是由已观察到的事物都有某属性，而没有观察到相反的事例，从而推出某类事物都有某属性。（2）类比归纳推理：指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其它属性上也相同或相似的一种归纳推理。（3）默认推理：称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。第8页，本讲稿共74页3.1 推理概述推理概述 l l3.1.2 3.1.2 推理的方法推理的方法推理的方法推理的方法3演绎推理与归纳推理的区别：演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。4推理的其它分类：（1）确定性推理与不确定推理（2）单调推理与非单调推理（3）启发式推理与非启发式推理第9页，本讲稿共74页3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略 推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略，主要是指推理方向的选择、推理时所用的搜索策略及冲突解决策略等。推理的控制策略包括推理策略和搜索策略。l推理策略主要解决推理方向、求解策略、冲突消解策略等问题。l搜索策略主要解决推理线路、推理效果、推理效率等问题。按照对推理方向的控制，推理可分为正向推理、反向推理、混合推理及双向推理四种情况。一般都要求系统具有三个要素：l一个存放知识的知识库 l一个存放初始事实和中间结果的数据库 l一个用于推理的推理机第10页，本讲稿共74页3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.1 正向推理正向推理是由已知事实出发，正向使用推理规则向结论方向的推理，算法步骤描述如下：（1）把用户提供的初始证据放入综合数据库；（2）检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；第11页，本讲稿共74页3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.1 正向推理（3）检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。（4）按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转(2)。第12页，本讲稿共74页3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.1 正向推理（5）询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转(3)；否则表示无解，失败退出。第13页，本讲稿共74页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页3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.2 反向推理 反向推理是以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理。反向推理过程如图：第15页，本讲稿共74页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页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页3.1 推理概述推理概述 l l3.1.3 3.1.3 推理的控制策略推理的控制策略推理的控制策略推理的控制策略3.1.3.3 正反向混合推理 正向推理和反向推理相结合的推理方法称为正反向混合推理。混合推理的方法包括：1.先正向后逆向2.先逆向后正向3.双向混合第18页，本讲稿共74页3.1 推理概述推理概述 l l3.1.4 3.1.4 推理中的冲突推理中的冲突推理中的冲突推理中的冲突 在推理过程中，系统要不断地用数据库中的事实与知识库中的规则进行匹配，当有一个以上规则的条件部分和当前数据库相匹配时，就需要有一种策略来决定首先使用哪一条规则，这就是冲突解决策略。冲突解决策略实际上就是确定规则的启用顺序。常用排序方法有如下几种:（1）按专一性排序 （2）按规则排序（3）按数据排序 （4）按就近原则排序（5）上下文限制 （6）按匹配度排序（7）按条件个数排序第19页，本讲稿共74页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页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页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页3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.2 3.2.2 等价式等价式等价式等价式常用谓词公式的等价式包括：（6）吸收律：（7）补余律:（8）连词化归律:（9）量词转换律:（10）量词分配律:第23页，本讲稿共74页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页3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.3 3.2.3 永真蕴含式永真蕴含式永真蕴含式永真蕴含式 常用永真蕴含式包括：（6）假言三段论：（7）二难推理：（8）全称固化：其中，y是个体域中的任一个体，依此可消去谓词公式中的全称量词。（9）存在固化：其中，y是个体域中某一个可以使 P(y)为真的个体，依此可消去谓词公式中的存在量词。第25页，本讲稿共74页3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.4 3.2.4 前束范式与前束范式与前束范式与前束范式与SkolemSkolem范式范式范式范式 范式分为两种：前束范式与Skolem范式。定义3.5 设F为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称F为前束范式。一般形式：其中，为前缀，它是一个由全称量词或存在量词组成的量词串；为母式，它是一个不含任何量词的谓词公式。例:定义3.6 如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为Skolem范式。例：第26页，本讲稿共74页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页3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.5 3.2.5 置换与合一置换与合一置换与合一置换与合一 1置置换换：定定义义3.9 设设是两个置是两个置换换。则则与与的合成也是一个置的合成也是一个置换换，记记作作 。它是从集合。它是从集合:中中删删去以下两种元素：去以下两种元素：当当 时时，删删去去 当当 时时，删删去去 最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。第28页，本讲稿共74页3.2 确定性推理的逻辑基础确定性推理的逻辑基础l l3.2.5 3.2.5 置换与合一置换与合一置换与合一置换与合一2合一：合一：定义定义3.10 设有公式集设有公式集 若存在一个置换若存在一个置换，可使，可使:则称则称是是F的一个合一。称的一个合一。称F1,F2,Fn是可合一的。是可合一的。定定义义3.11 设设 是是公公式式集集F的的一一个个合合一一，如如果果对对F的的任任一一个个合合一一 都都存存在在一一个置换个置换 ，使得，使得 ，则称，则称 是一个最一般合一。是一个最一般合一。第29页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.1 什么是演绎推理什么是演绎推理l l3.3.2 演绎推理的特点演绎推理的特点 基于规则的演绎推理是一种直接的推理方法。它不再把有关的知识转化为子句集，而是把有关问题的知识和信息划分为规则与事实两种类型。规则由包含蕴含形式的表达式表示，事实由无蕴含式的表达式表示，并画出相应的与/或图，然后通过规则进行演绎推理。第30页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.1 3.3.1 什么是演绎推理什么是演绎推理什么是演绎推理什么是演绎推理 所谓自然演绎推理，在已知一组为真的事实条件下，直接运用命题和谓词逻辑的一系列基本规则或定律来推出结论，该过程称为自然演绎推理。基于规则的演绎推理可分为正向演绎推理、反向演绎推理和正反向混合演绎推理。第31页，本讲稿共74页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页3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理2F规则规则 在与在与/或形正向演或形正向演绎绎系系统统中，通常要求中，通常要求F规则应规则应具有如下形式：具有如下形式：L为单为单文字，文字，W为为与与/或形公式。或形公式。其其变换变换步步骤骤如下：如下：（1）暂时暂时消去消去蕴蕴含符号含符号“”。（2）把把否否定定符符号号“”移移到到紧紧靠靠谓谓词词的的位位置置上上，使使其其作作用用域域仅仅限限于于单单个个谓词谓词。（3）引入）引入Skolem函数，消去存在量函数，消去存在量词词。（4）化成前束式，消去全部全称量）化成前束式，消去全部全称量词词。（5）恢复）恢复蕴蕴含式表示。含式表示。第33页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理3规则正向演绎 与/或树正向演绎系统要求目标公式用子句形表示。如果目标公式不是子句形，则需要化成子句形。规则正向演绎推理过程是先用与/或树把已知事实表示出来，然后再用F规则的前件和与或树的叶节点进行匹配，并通过一个匹配弧把匹配成功的F规则加入到与/或树中，依此使用F规则，直到产生一个含有以目标节点为终止节点的解图为止。第34页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理3规则正向演绎(1)命题逻辑规则演绎过程：例：设已知事实为：F规则为：目标公式为：命题逻辑的规则演绎过程第35页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.1.1 3.3.1.1 正向演绎推理正向演绎推理正向演绎推理正向演绎推理3规则正向演绎(2)谓词逻辑规则演绎过程例：设已知事实的与/或形表示为：F规则为：目标公式为：命题逻辑的规则演绎过程第36页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.1 3.3.1 什么是演绎推理什么是演绎推理什么是演绎推理什么是演绎推理3.3.1.2 逆向演绎推理从目标表达式出发，反方向使用规则（B规则）对目标表达式的与或图进行变换，最后得到含有事实节点的一致解图。1目标表达式的与或形表示：在基于规则的逆向系统中，要用对偶形式对目标表达式进行Skolem化。即消去全称量词，对受全称量词约束的变量用Skolem函数或者常量代替，省略存在量词，所有变量默认为受存在量词约束，并进行变量换名，使得目标公式的主析取元之间具有不同的变量名。第37页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理1目标表达式的与或形表示：例：目标公式：Skolem化后：变量标准化：这个目标的与或图表示如图，其子句集可以从结束在端节点的解图集中读得：第38页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理2规则的应用 逆向演绎推理以逆向方式使用规则（称为B规则），要求规则化简为以下形式：其中，L为单文字，W是与或形；规则的激活取决于L和与或图叶节点的匹配。逆向系统演绎过程的结束条件是生成的与或图含有事实表达式，而事实表达式限制为文字的合取形式。当事实表达式有一个文字同与或图中某一个端节点所标记的文字（子目标）匹配上时，就可以通过匹配弧把事实文字加到图上。这样当最后得到的与或图包含一个结束在事实节点上的一致解图时，系统便结束演绎，一个一致解图是解图中匹配弧置换集具有合一复合置换的那个解图。第39页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理2规则的应用例：下面通过一个简例说明逆向系统的演绎过程。设有如下事实：lFIDO是一只狗lFIDO不叫lFIDO摆尾巴lMYRTLE瞄瞄叫规则如下：l摆尾巴的狗是友好的l友好且不叫的是不令对方害怕的第40页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理2规则的应用例：l狗是动物l猫是动物l喵喵叫的是猫问题是：是否存在一只猫和一只狗，使这只猫不怕这只狗？即目标公式：第41页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 逆向演绎推理逆向演绎推理逆向演绎推理逆向演绎推理2规则的应用解：解该问题的过程如图：得到解答语句：（它表示有一只名叫MYRTLE的猫和一只名叫FIDO的狗，这只猫不怕那只狗。）第42页，本讲稿共74页3.3 演绎推理方法演绎推理方法l l3.3.2 3.3.2 演绎推理的特点演绎推理的特点演绎推理的特点演绎推理的特点正向演绎推理逆向演绎推理问题求解的描述事实文字与或形事实文字合取式规则L=W规则W=L目标文字析取形目标文字与或形初始与或图相应于事实表达式事实表达式的与或树相应于目标公式事实表达式的与或树演绎推理F规则事实-目标B规则目标-事实结束条件包含所有目标节点的一致解图以事实节点作为所有终节点的一致解图第43页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.1 3.4.1 子句集及其化简子句集及其化简子句集及其化简子句集及其化简l l3.4.2 Herbrand3.4.2 Herbrand（海伯伦）定理（海伯伦）定理（海伯伦）定理（海伯伦）定理l l3.4.3 Robinson3.4.3 Robinson（鲁宾逊）归结原理（鲁宾逊）归结原理（鲁宾逊）归结原理（鲁宾逊）归结原理l l3.4.4 3.4.4 利用归结推理进行定理证明利用归结推理进行定理证明利用归结推理进行定理证明利用归结推理进行定理证明l l3.4.5 3.4.5 应用归结原理进行问题求解应用归结原理进行问题求解应用归结原理进行问题求解应用归结原理进行问题求解 在谓词演算中，利用前面列出的等价式和永真蕴含式，可以从已知的一些公式推导出新的公式，这个导出的公式叫做定理，在推导过程中使用的推理规则序列就成了该定理的一个证明，而这种推导，就是归结推理方法。第44页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.1 3.4.1 子句集及其化简子句集及其化简子句集及其化简子句集及其化简定义定义3.12 任何文字的析取式称为子句。任何文字的析取式称为子句。定义定义3.13 包含任何文字的子句称为空子句，表示为包含任何文字的子句称为空子句，表示为NIL。定义定义3.14 由子句或空子句所构成的集合称为子句集。由子句或空子句所构成的集合称为子句集。在在谓谓词词逻逻辑辑中中，任任何何一一个个谓谓词词公公式式都都可可以以化化成成一一个个子子句句集集。将将谓谓词词公公式式化化为为子句集的步骤如下：子句集的步骤如下：(1)消去连接词消去连接词“”和和“”：(2)减少否定符号的辖域：减少否定符号的辖域：(3)对对变变元元标标准准化化：在在一一个个量量词词的的辖辖域域内内，把把谓谓词词公公式式中中受受该该量量词词约约束束的的变变元元全全部部用用另另外外一一个个没没有有出出现现过过的的任任意意变变元元代代替替，使使不不同同量量词词约约束束的变元有不同的名字。的变元有不同的名字。(4)化化为为前前束束范范式式：把把所所有有量量词词都都移移到到公公式式的的左左边边，并并且且在在移移动动时时不不能能改改变变其其相对顺序。相对顺序。第45页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.1 3.4.1 子句集及其化简子句集及其化简子句集及其化简子句集及其化简 在谓词逻辑中，任何一个谓词公式都可以化成一个子句集。将谓词公式化为子句集的步骤如下：（5）消去存在量词;（6）化为Skolem标准形;（7）消去全称量词：由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。（8）消去合取词：在母式中消去所有合取词，把母式用子句集的形式表示出来。（9）更换变量名称：对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。第46页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.1 3.4.1 子句集及其化简子句集及其化简子句集及其化简子句集及其化简例：将下列谓词公式化成子句集。解：转换过程遵照上述9个步骤。(1)(2)(3)(4)(5)(6)(7)第47页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.1 3.4.1 子句集及其化简子句集及其化简子句集及其化简子句集及其化简例：将下列谓词公式化成子句集。解：转换过程遵照上述9个步骤。(8)子句集为：(9)子句变量标准化后，最终的子句集为：第48页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.1 3.4.1 子句集及其化简子句集及其化简子句集及其化简子句集及其化简 当原谓词公式为非永假时，它与其标准子句集并不等价。当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。这个结论很重要，是归结原理的主要依据，可用定理的形式来描述。定理3.1 设有谓词公式F，其标准子句集为S，则F为不可满足的充要条件是S为不可满足的。第49页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.2 Herbrand3.4.2 Herbrand（海伯伦）定理（海伯伦）定理（海伯伦）定理（海伯伦）定理1H域及其原子集：域及其原子集：定定义义3.15 H域：域：设设G是是谓词谓词公式，定公式，定义义在在论论域域D上，令上，令H0是是G中所出中所出现现的常的常量的集合。若量的集合。若G中没有常量出中没有常量出现现，就任取常量，就任取常量aD，而，而规规定定H0=a；其中其中f(t1,tn)是出是出现现于于G中的任一函数符号，而中的任一函数符号，而t1tn是是Hi-1的元素，的元素，i=1,2,。规规定定H为为G的的H域。域。(或或说说是相是相应应的子句集的子句集S的的H域域)。第50页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.2 Herbrand3.4.2 Herbrand（海伯伦）定理（海伯伦）定理（海伯伦）定理（海伯伦）定理2对H域的解释问题：定义3.16 如果子句集S的原子集为A，则对A中各元素的真假值的一个具体设定都是S的一个H解释。定理3.2 设I是S的论域D上的解释，存在对应于I的H解释 ，使得若有 必有 。定理3.3 子句集S是不可满足的，当且仅当所有的S的H解释下为假。定理3.4 子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。第51页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.2 Herbrand3.4.2 Herbrand（海伯伦）定理（海伯伦）定理（海伯伦）定理（海伯伦）定理3Herbrand（海伯（海伯伦伦）定理）定理 定定理理3.5 设设有有谓谓词词公公式式F，其其标标准准形形的的子子句句集集为为S，则则F不不可可满满足足的的充充要要条条件件是是S不可不可满满足。足。Herbrand（海伯（海伯伦伦）定理如下：）定理如下：定定理理3.6 子子句句集集S不不可可满满足足的的充充要要条条件件是是：该该子子句句集集S在在H域域中中的的所所有有解解释释都都为为假。假。定理定理3.7 子句集子句集S不可不可满满足的充要条件是存在一个不可足的充要条件是存在一个不可满满足的基子句集足的基子句集S。对对Herbrand（海海伯伯伦伦）定定理理一一般般通通俗俗性性解解释释是是：如如果果一一个个一一阶阶谓谓词词公公式式是是永永真真的的，则则该该公公式式的的机机器器定定理理证证明明求求解解计计算算可可在在有有限限步步内内实实现现证证明明；如如果果该公式不是永真的，则无法在有限步内实现证明。该公式不是永真的，则无法在有限步内实现证明。第52页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.2 Herbrand3.4.2 Herbrand（海伯伦）定理（海伯伦）定理（海伯伦）定理（海伯伦）定理3Herbrand（海伯伦）定理 例：对子句集 画出相应的语义树。解：第53页，本讲稿共74页3.4 归结推理方法归结推理方法l l3.4.2 Herbrand3.4.2 Herbrand（海伯伦）定理（海伯伦）定理（海伯伦）定理（海伯伦）定理3Herbrand（海伯（海伯伦伦）定理）定理 Herbrand定理用于定理用于语义树语义树解解释释有：有：定定理理3.8 子子句句集集S是是不不可可满满足足的的，当当且且仅仅当当对对应应于于S的的完完全全语语义义树树都都是是一一棵有限的封棵有限的封闭语义树闭语义树。定定理理3.9 子子句句集集S是是不不可可满满足足的的，当当且且仅仅当当存存在在不不可可满满足足的的有有限限基基例例集集（即即存在有限个失存在有限