《人工智能基础04--推理技术优秀PPT.ppt》由会员分享，可在线阅读，更多相关《人工智能基础04--推理技术优秀PPT.ppt（101页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室1/101书目o第一章绪论第一章绪论o其次章学问表示其次章学问表示o第三章搜寻技术第三章搜寻技术o第四章推理技术第四章推理技术o第五章机器学习第五章机器学习o第六章专家系统第六章专家系统o第七章自动规划系统第七章自动规划系统o第八章第八章自然语言理解自然语言理解o第九章第九章智能限制智能限制o第十章第十章人工智能程序设计人工智能程序设计合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室2/1014.0 推理的基本概念4.0.1推理的定义推理的定义从初始证据动身，按某种策略不断应用学从初始证据动身，
2、按某种策略不断应用学问库中的已知学问，逐步推出结论的过程称为问库中的已知学问，逐步推出结论的过程称为推理。推理。在人工智能系统中，推理是由程序实现的，在人工智能系统中，推理是由程序实现的，称为推理机。称为推理机。已知事实和学问是构成推理的两个基本要已知事实和学问是构成推理的两个基本要素。素。事实又称为证据，用以指出推理的动身点事实又称为证据，用以指出推理的动身点及推理时应当运用的学问。及推理时应当运用的学问。学问是使推理得以向前推动，并逐步达到学问是使推理得以向前推动，并逐步达到最终目标的依据。最终目标的依据。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室3/101
3、4.0 推理的基本概念4.0.2推理方式及其分类推理方式及其分类（1）按推出结论的途径来划分，推理可分为：按推出结论的途径来划分，推理可分为：演绎推理（演绎推理（deductiveresoning）：是从全称）：是从全称推断推导出单称推断的过程，即由一般性学问推断推导出单称推断的过程，即由一般性学问推出适合某一具体状况的结论。一般到个别。推出适合某一具体状况的结论。一般到个别。归纳推理（归纳推理（inductiveresoning）：是从足够）：是从足够多的事例中归纳出一般性结论的推理过程。个多的事例中归纳出一般性结论的推理过程。个别到一般。别到一般。默认推理（默认推理（defaultreso
4、ning）：是在学问不）：是在学问不完全的状况下假设某些条件已经具备所进行的完全的状况下假设某些条件已经具备所进行的推理。推理。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室4/1014.0 推理的基本概念4.0.2推理方式及其分类推理方式及其分类（2）按推理时所用的学问的确定性来划分，推按推理时所用的学问的确定性来划分，推理可分为：理可分为：确定性推理：是指推理时所用的学问与证据确定性推理：是指推理时所用的学问与证据都是确定的，退出的结论也是确定的，其真值或都是确定的，退出的结论也是确定的，其真值或者为真或者为假，没有第三种状况出现。者为真或者为假，没有第三种状况
5、出现。不确定性推理：是指推理时所用的学问与证不确定性推理：是指推理时所用的学问与证据不都是确定的，推出的结论也是不确定的。据不都是确定的，推出的结论也是不确定的。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室5/1014.0 推理的基本概念4.0.2推理方式及其分类推理方式及其分类（3）按推理过程中推出的结论是否越来越接近按推理过程中推出的结论是否越来越接近最终目标来划分，推理可分为：最终目标来划分，推理可分为：单调推理：是指在推理过程中随着推理向前单调推理：是指在推理过程中随着推理向前推动及新学问的加入，推出的结论越来越接近最推动及新学问的加入，推出的结论越来越接
6、近最终目标。终目标。非单调推理：是指在推理过程中由于新学问非单调推理：是指在推理过程中由于新学问的加入，不仅没有加强已推出的结论，反而要否的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，然后重新起定它，使推理退回到前面的某一步，然后重新起先。先。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室6/1014.0 推理的基本概念4.0.2推理方式及其分类推理方式及其分类（4）按推理中是否运用与推理有关的启发性学按推理中是否运用与推理有关的启发性学问来划分，推理可分为：问来划分，推理可分为：启发性推理：是指在推理过程中运用与推理启发性推理：是指在推
7、理过程中运用与推理有关的启发性学问。有关的启发性学问。非启发性推理：是指在推理过程中未运用与非启发性推理：是指在推理过程中未运用与推理有关的启发性学问。推理有关的启发性学问。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室7/1014.0 推理的基本概念4.0.3推理的方向推理的方向（1）正向推理）正向推理是以事实作为动身点的一种推理。是以事实作为动身点的一种推理。基本思想：从用户供应的初始已知事实动身，基本思想：从用户供应的初始已知事实动身，在学问库在学问库KB中找出当前可适用的学问，构成可适中找出当前可适用的学问，构成可适用学问集用学问集KS，然后按某种冲突消解策
8、略从，然后按某种冲突消解策略从KS中中选出一条学问进行推理，并将推出的新事实加入选出一条学问进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，此后再到数据库中作为下一步推理的已知事实，此后再在在KB中选取可适用的学问进行推理，如此重复这中选取可适用的学问进行推理，如此重复这一过程，直到求得了问题的解或者学问库中再无一过程，直到求得了问题的解或者学问库中再无可适用的学问为止。可适用的学问为止。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室8/1014.0 推理的基本概念4.0.3推理的方向推理的方向（2）逆向推理）逆向推理是以某个假设目标为动身点的一种
9、推理。是以某个假设目标为动身点的一种推理。基本思想：首先选择一个假设目标，然后找基本思想：首先选择一个假设目标，然后找寻支持该假设的证据，若需的证据都能找到，则寻支持该假设的证据，若需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需说明原假设是成立的；若无论如何都找不到所需的证据，则说明原假设不成立，为此须要另作新的证据，则说明原假设不成立，为此须要另作新的假设。的假设。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室9/1014.0 推理的基本概念4.0.3推理的方向推理的方向（3）混合推理）混合推理正向推理具有盲目、效率低等缺点，推理过正向推理具有盲目
10、、效率低等缺点，推理过程中可能会推出很多与问题无关的子目标。逆向程中可能会推出很多与问题无关的子目标。逆向推理中，若提出的假设目标不符合实际，也会降推理中，若提出的假设目标不符合实际，也会降低系统效率。可以把正向推理与逆向推理结合起低系统效率。可以把正向推理与逆向推理结合起来，使其各自发挥自己的优势，取长补短。这种来，使其各自发挥自己的优势，取长补短。这种既有正向推理又有逆向推理称为混合推理。既有正向推理又有逆向推理称为混合推理。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室10/1014.0 推理的基本概念4.0.3推理的方向推理的方向（4）双向推理）双向推理双向
11、推理：是指正向推理与逆向推理同时进双向推理：是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上行，且在推理过程中的某一步骤上“碰头碰头”的一种的一种推理。推理。基本思想：一方面依据已知事实进行正向基本思想：一方面依据已知事实进行正向推理，但并不推倒最终目标；另一方面从某假设推理，但并不推倒最终目标；另一方面从某假设目标动身进行逆向推理，但不推至原始事实，而目标动身进行逆向推理，但不推至原始事实，而是让它们在中途相遇，即由正向推理所得到的中是让它们在中途相遇，即由正向推理所得到的中间结论恰好是逆向推理此时所需求的证据，这时间结论恰好是逆向推理此时所需求的证据，这时推理就可以结束，逆向推理
12、时所做的假设就是推推理就可以结束，逆向推理时所做的假设就是推理的最终结论。理的最终结论。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室11/1014.0 推理的基本概念4.0.4冲突消解策略冲突消解策略系统将当前已知事实与系统将当前已知事实与KB中学问匹配的三种中学问匹配的三种状况：状况：（1）已知事实恰好只与）已知事实恰好只与KB中的一个学问匹配中的一个学问匹配成功。成功。（2）已知事实不能与）已知事实不能与KB中的任何学问匹配成中的任何学问匹配成功。功。（3）已知事实可与）已知事实可与KB中的多个学问匹配成功；中的多个学问匹配成功；或者多个（组）事实都可与或者多
13、个（组）事实都可与KB中的某一个学问匹中的某一个学问匹配成功；或者多个（组）事实都可与配成功；或者多个（组）事实都可与KB中的多个中的多个学问匹配成功；学问匹配成功；第第3种状况称为发生了冲突。种状况称为发生了冲突。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室12/1014.0 推理的基本概念4.0.4冲突消解策略冲突消解策略消解冲突的基本思想：对学问进行排序：消解冲突的基本思想：对学问进行排序：（1）按针对性排序：优先选择针对性强的学问）按针对性排序：优先选择针对性强的学问（规则），即要求条件多的规则。（规则），即要求条件多的规则。（2）按已知事实的簇新性排序：
14、后生成的事实）按已知事实的簇新性排序：后生成的事实具有较大的簇新性。具有较大的簇新性。（3）按匹配度排序：在不确定推理中，须要计）按匹配度排序：在不确定推理中，须要计算已知事实与学问的匹配度。算已知事实与学问的匹配度。（4）按条件个数排序：优先应用条件少的产生）按条件个数排序：优先应用条件少的产生式规则。式规则。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室13/1014.1 消解原理4.1.1子句集的求取子句集的求取消解原理是针对谓词逻辑学问表示的问题求解消解原理是针对谓词逻辑学问表示的问题求解方法。方法。消解原理的基础学问：消解原理的基础学问：（1）谓词公式、某
15、些推理规则以及置换合一等）谓词公式、某些推理规则以及置换合一等概念。概念。（2）子句：由文字的析取组成的公式）子句：由文字的析取组成的公式(一个原一个原子公式和原子公式的否定都叫做文字子公式和原子公式的否定都叫做文字)。（3）消解：当消解可运用时，消解过程被应）消解：当消解可运用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，用于母体子句对，以便产生一个导出子句。例如，假如存在某个公理假如存在某个公理E1E2和另一公理和另一公理E2E3，那么，那么E1E3在逻辑上成立。这就是消解，而称在逻辑上成立。这就是消解，而称E1E3为为E1E2和和E2E3的消解式。的消解式。合肥工业大学合肥
16、工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室14/1014.1 消解原理4.1.1子句集的求取子句集的求取步骤步骤(1)消去蕴涵符号消去蕴涵符号只应用只应用和符号，以和符号，以AB替换替换AB。(AB)BC=(AB)BC=(AB)BC=(AB)BC=（AB）（BB）C=（AB）C合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室15/1014.1 消解原理4.1.1子句集的求取子句集的求取(2)削减否定符号的辖域削减否定符号的辖域每个否定符号最多只用到一个谓词符号上，每个否定符号最多只用到一个谓词符号上，并反复应用狄并反复应用狄摩根定律。例如：摩根定律。例
17、如：以以AB代替代替(AB)以以AB代替代替(AB)以以A代替代替(A)以以(彐彐x)A代替代替(x)A以以(x)A代替代替(彐彐x)A合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室16/1014.1 消解原理4.1.1子句集的求取子句集的求取(3)对变量标准化对变量标准化在任一量词辖域内，受该量词约束的变量为在任一量词辖域内，受该量词约束的变量为一哑元一哑元(虚构变量虚构变量)，它可以在该辖域内到处统一，它可以在该辖域内到处统一地被另一个没有出现过的随意变量所代替，而不地被另一个没有出现过的随意变量所代替，而不变更公式的真值。合适公式中变量的标准化意味变更公式的真
18、值。合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑着对哑元改名以保证每个量词有其自己唯一的哑元。元。如，对如，对(x)P(x)(彐彐x)Q(x)标准化可得：标准化可得：(x)P(x)(彐彐y)Q(y)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室17/1014.1 消解原理4.1.1子句集的求取子句集的求取(4)消去存在量词消去存在量词Skolem函数：函数：(y)(彐彐x)P(x,y)中，存在量中，存在量词是在全称量词的辖域内，允许所存在的词是在全称量词的辖域内，允许所存在的x可能可能依靠于依靠于y值。令这种依靠关系明显地有函数值。令这种依靠
19、关系明显地有函数g(y)所所定义，它把每个定义，它把每个y值映射到存在的那个值映射到存在的那个x。这种函。这种函数叫做数叫做Skolem函数。函数。假如用假如用Skolem函数代替存在的函数代替存在的x，就可以消，就可以消去全部存在量词，并写成：去全部存在量词，并写成：(y)P(g(y),y)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室18/1014.1 消解原理4.1.1子句集的求取子句集的求取从一个公式消去一个存在量词的一般规则是从一个公式消去一个存在量词的一般规则是以一个以一个Skolem函数代替每个出现的存在量词的量函数代替每个出现的存在量词的量化变量，而
20、这个化变量，而这个Skolem函数的变量就是由那些全函数的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内。词的辖域包括要被消去的存在量词的辖域在内。Skolem函数所运用的函数符号必需是新的，即不函数所运用的函数符号必需是新的，即不允许是公式中已经出现过的函数符号。允许是公式中已经出现过的函数符号。假如要消去的存在量词不在任何一个全称量假如要消去的存在量词不在任何一个全称量词的辖域内，则用不含变量的词的辖域内，则用不含变量的Skolem函数即常量。函数即常量。例如，例如，(彐彐x)P(x)化为化为P(
21、A)，其中常量符号，其中常量符号A用来用来表示人们知道的存在实体。表示人们知道的存在实体。A必需是个新的常量符必需是个新的常量符号，它未曾在公式中其它地方运用过。号，它未曾在公式中其它地方运用过。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室19/1014.1 消解原理4.1.1子句集的求取子句集的求取(5)化为前束形化为前束形把全部全称量词移到公式的左边，并使每个把全部全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。所得公式称为前束形。前束形前束形=（前（前缀）缀）（母（母式）
22、式）全称量词串全称量词串无量词公式无量词公式(6)把母式化为合取范式把母式化为合取范式任何母式都可写成由一些谓词公式和任何母式都可写成由一些谓词公式和(或或)谓词谓词公式的否定的析取的有限集组成的合取。这种母公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。式叫做合取范式。如：如：ABC化为化为ABBC合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室20/1014.1 消解原理4.1.1子句集的求取子句集的求取(7)消去全称量词消去全称量词消去明显出现的全称量词。消去明显出现的全称量词。(8)消去连词符号消去连词符号用用A，B代替代替(AB)，以消去明显的符号
23、，以消去明显的符号。反复代替的结果，最终得到一个有限集，其中。反复代替的结果，最终得到一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。成的合适公式叫做一个子句。(9)更换变量名称更换变量名称可以更换变量符号的名称，使一个变量符号不可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。出现在一个以上的子句中。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室21/1014.1 消解原理4.1.1子句集的求取子句集的求取例：将下列谓词演算公式化为一个子句集例：将下列谓词演算公式化为一
24、个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)（1）消去蕴涵符号）消去蕴涵符号(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)（2）削减否定符号辖域）削减否定符号辖域(x)P(x)(y)P(y)P(f(x,y)(彐彐y)Q(x,y)P(y)(x)P(x)(y)P(y)P(f(x,y)(彐彐y)Q(x,y)P(y)（3）对变量标准化）对变量标准化(x)P(x)(y)P(y)P(f(x,y)(彐彐w)Q(x,w)P(w)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室22/1014.1 消解原理4.1.1子句集的求取子
25、句集的求取（4）消去存在量词）消去存在量词(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)P(g(x)w=g(x)为一个为一个skolem函数。函数。（5）化为前束形）化为前束形(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)（6）把母式化为合取范式）把母式化为合取范式(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室23/1014.1 消解原理4.1.1子句集的求取子句集的求取（7）消去全称量词）消去全称量词P(x)P(y)P(f(x,y)P(x
26、)Q(x,g(x)P(x)P(g(x)（8）消去连词符号）消去连词符号P(x)P(y)P(f(x,y)，P(x)Q(x,g(x)，P(x)P(g(x)（9）更换变量名称）更换变量名称P(x1)P(y)P(f(x1,y)，P(x2)Q(x2,g(x2)，P(x3)P(g(x3)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室24/1014.1 消解原理4.1.2消解推理规则消解推理规则令令L1为任一原子公式，为任一原子公式，L2为另一原子公式；为另一原子公式；L1和和L2具有相同的谓词符号，但一般具有不同的变量。具有相同的谓词符号，但一般具有不同的变量。已知两子句已知两
27、子句L1和和L2,假如假如L1和和L2具有最一具有最一般合一者般合一者，那么通过消解可以从这两个父辈子句，那么通过消解可以从这两个父辈子句推导出一个新子句推导出一个新子句()。这个新子句叫做消解式。这个新子句叫做消解式。它是由取这两个子句的析取，然后消去互补对而得它是由取这两个子句的析取，然后消去互补对而得到的。到的。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室25/1014.1 消解原理4.1.2消解推理规则消解推理规则常用消解规则常用消解规则(1)假言推理假言推理父辈子句父辈子句PPQ(即即PQ)消解式消解式Q合肥工业大学合肥工业大学 人工智能与数据挖掘研究室
28、人工智能与数据挖掘研究室26/1014.1 消解原理4.1.2消解推理规则消解推理规则常用消解规则常用消解规则(2)合并合并父辈子句父辈子句PQPQ消解式消解式QQ=Q合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室27/1014.1 消解原理4.1.2消解推理规则消解推理规则常用消解规则常用消解规则(3)重言式重言式PQPQPQPQ消解式消解式QQPP合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室28/1014.1 消解原理4.1.2消解推理规则消解推理规则常用消解规则常用消解规则(4)空子句空子句(冲突冲突)PP消解式消解式NIL合肥工
29、业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室29/1014.1 消解原理4.1.2消解推理规则消解推理规则常用消解规则常用消解规则(5)链式链式(三段论三段论)PQQR消解式消解式PR合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室30/1014.1 消解原理4.1.3含有变量的消解式含有变量的消解式为了对含有变量的子句运用消解规则，必需为了对含有变量的子句运用消解规则，必需找到一个置换，作用于父辈子句使其含有互补文找到一个置换，作用于父辈子句使其含有互补文字。字。例：设有两个字句例：设有两个字句P(x)Q(x)Q（f(y)）置换置换=f(y)
30、/x消解可得：消解可得：P（f(y)）合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室31/1014.1 消解原理4.1.3含有变量的消解式含有变量的消解式令父辈子句由令父辈子句由Li和和Mi给出，假设这两个子句中的变给出，假设这两个子句中的变量已经分别标准化。设量已经分别标准化。设li是是 Li的一个子集，的一个子集，mi是是Mi的的一个子集，若一个子集，若是是 li和和mi的最一般的合一，消解两个子的最一般的合一，消解两个子句句Li和和Mi，得到新子句，得到新子句Li-liMi-mi就是这两个子句的消解式。就是这两个子句的消解式。消解两个子句时，可能有一个以上的消
31、解式，因为有多消解两个子句时，可能有一个以上的消解式，因为有多种选择种选择li和和mi的方法。的方法。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室32/1014.1 消解原理4.1.3含有变量的消解式含有变量的消解式例例：考虑两个子句：考虑两个子句：Px,f(A)Px,f(y)Q(y)pz,f(A)Q(z)取取li=Px,f(A)，mi=pz,f(A)可得消解式可得消解式Pz,f(y)Q(y)Q(z)=z/x合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室33/1014.1 消解原理4.1.3含有变量的消解式含有变量的消解式假如取假如取l
32、i=Q(y)，mi=Q(z)则可得消解式则可得消解式Px,f(A)Px,f(y)py,f(A)进一步消解的消解式进一步消解的消解式Py,f(y)=y/z合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室34/1014.1 消解原理4.1.3含有变量的消解式含有变量的消解式几个含有变量的子句运用消解的例子：几个含有变量的子句运用消解的例子：B(x)B(x)C(x)C(x)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室35/1014.1 消解原理4.1.3含有变量的消解式含有变量的消解式几个含有变量的子句运用消解的例子：几个含有变量的子句运用消解
33、的例子：P(x)Q(x)Qf(y)Pf(y)=f(y)/x合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室36/1014.1 消解原理4.1.3含有变量的消解式含有变量的消解式几个含有变量的子句运用消解的例子：几个含有变量的子句运用消解的例子：P(x,f(y)Q(x)Rf(a),yPf(f(a),zR(z,w)Q(f(f(a)Rf(a),yR(f(y),w)=f(f(a)/x,f(y)/z合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室37/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程1.基本思想基本思想把要解决的问题作为
34、一个要证明的命题，其把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于联合集，并公式集中去，把消解反演系统应用于联合集，并推导出一个空子句推导出一个空子句(NIL)，产生一个冲突，这说，产生一个冲突，这说明目标公式的否定式不成立，即有目标公式成立，明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决，与数学中反证法的思定理得证，问题得到解决，与数学中反证法的思想特殊相像。想特殊相像。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室38/1014.1 消
35、解原理4.1.4消解反演求解过程消解反演求解过程2、消解反演、消解反演反演求解的步骤反演求解的步骤给出一个公式集给出一个公式集S和目标公式和目标公式L，通过反证，通过反证或反演来求证目标公式或反演来求证目标公式L，其证明步骤如下：，其证明步骤如下：(1)否定否定L，得，得L；(2)把把L添加到添加到S中去；中去；(3)把新产生的集合把新产生的集合L，S化成子句集；化成子句集；(4)应用消解原理，力图推导出一个表示冲应用消解原理，力图推导出一个表示冲突的空子句突的空子句NIL。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室39/1014.1 消解原理4.1.4消解反演
36、求解过程消解反演求解过程反演求解的正确性反演求解的正确性设公式设公式L在逻辑上遵循公式集在逻辑上遵循公式集S，那么依据，那么依据定义满足定义满足S的每个说明也满足的每个说明也满足L。决不会有满足。决不会有满足S的说明能够满足的说明能够满足L的，所以不存在能够满足并的，所以不存在能够满足并集集SL的说明。假如一个公式集不能被的说明。假如一个公式集不能被任一说明所满足，那么这个公式是不行满足的。任一说明所满足，那么这个公式是不行满足的。因此，假如因此，假如L在逻辑上遵循在逻辑上遵循S，那么，那么SL是不行满足的。可以证明，假如消解反演反复应是不行满足的。可以证明，假如消解反演反复应用到不行满足的子
37、句集，那么最终将要产生空子用到不行满足的子句集，那么最终将要产生空子句句NIL。因此，假如。因此，假如L在逻辑上遵循在逻辑上遵循S，那么由并，那么由并集集SL消解得到的子句，最终将产生空消解得到的子句，最终将产生空子句；反之，可以证明，假如从子句；反之，可以证明，假如从SL的的子句消解得到空子句，那么子句消解得到空子句，那么L在逻辑上遵循在逻辑上遵循S。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室40/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程反演求解举例反演求解举例例：储蓄问题例：储蓄问题前提：每个储蓄钱的人都获得利息。前提：每个储蓄钱的人
38、都获得利息。结论：假如没有利息，那么就没有人去储蓄结论：假如没有利息，那么就没有人去储蓄钱钱证明：令证明：令S(x,y)表示表示“x储蓄储蓄y”M(x)表示表示“x是钱是钱”I(x)表示表示“x是利息是利息”E(x,y)表示表示“x获得获得y”于是上述命题写成：于是上述命题写成：合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室41/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程(x)(x)(彐彐y)(S(x,y)M(y)=(彐彐y)(I(y)E(x,y)结论：结论：(彐彐x)I(x)=(x)(x)(y)(M(y)=(S(x,y)化为子句集：化为子句集
39、：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x)其中，其中，y=f(x)为为Skolem函数。函数。而而L=(彐彐x)I(x)=(x)(x)(y)(s(x,y)=M(y)=I(z),S(a,b),M(b)P=Q等价等价Q=P合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室42/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程按按4个步骤进行反演求解个步骤进行反演求解（1）否定）否定L，即有，即有L=I(z),S(a,b),M(b)（2）将）将L添加到添加到S中去中去,即即S=L,S=S(x,y)M(y)I(f(x),S(x,
40、y)M(y)E(x,f(x),I(z),S(a,b),M(b)（3）把新产生的集合化成子句集，即）把新产生的集合化成子句集，即S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),M(b)（4）应用消解原理，推导出一个表示冲突的空）应用消解原理，推导出一个表示冲突的空子句子句NIL。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室43/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程S(x,y)M(y)I(f(x)I(z)S(x,y)M(y)=f(x)/zM(b)S(a,b)=a/x,b/yNILM(b)合
41、肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室44/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程反演求解过程反演求解过程步骤：步骤：(1)把由目标公式的否定产生的每个子句添把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。加到目标公式否定之否定的子句中去。(2)依据反演树，执行和以前相同的消解，依据反演树，执行和以前相同的消解，直至在根部得到某个子句止。直至在根部得到某个子句止。(3)用根部的子句作为一个回答语句。用根部的子句作为一个回答语句。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室45/1014
42、.1 消解原理4.1.4消解反演求解过程消解反演求解过程分析：分析：答案求取涉及到把一棵根部有答案求取涉及到把一棵根部有NIL的反演树的反演树变换为在根部带有可用作答案的某个语句的一颗变换为在根部带有可用作答案的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否证明树。由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言式，所以被变定产生的每个子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部的换的证明树就是一棵消解的证明树，其在根部的语句在逻辑上遵循公理加上重言式，因而也单独语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证
43、明白地遵循公理。因此被变换的证明树本身就证明白求取方法是正确的。求取方法是正确的。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室46/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程例例4.3假如无论约翰假如无论约翰(John)到哪里去，菲多到哪里去，菲多(Fido)也就去那里，那么假如约翰在学校里，菲多在哪也就去那里，那么假如约翰在学校里，菲多在哪里呢里呢?事实公式集：事实公式集：S=(x)AT(JOHN,x)=AT(FIDO,x),AT(JOHN,SCHOOL)目标公式目标公式L：(彐彐x)AT(FIDO,x)首先证明首先证明L在逻辑上遵循公式集
44、在逻辑上遵循公式集SL=(彐彐x)AT(FIDO,x)=(x)AT(FIDO,x)其子句为其子句为AT(FIDO,x)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室47/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程例例4.3的反演树的反演树AT(FIDO,x)AT(JOHN,y)AT(FIDO,y),AT(JOHN,x)=x/yNILAT(JOHN,SCHOOL)=SCHOOL/x合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室48/1014.1 消解原理4.1.4消解反演求解过程消解反演求解过程例例4.3从消解求取答案
45、的反演树从消解求取答案的反演树AT(FIDO,x)AT(FIDO,y)AT(JOHN,y)AT(FIDO,y),AT(JOHN,x)AT(FIDO,x)=x/yAT(FIDO,SCHOOL)AT(JOHN,SCHOOL)=SCHOOL/x目标公式的重言式目标公式的重言式合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室49/1014.2 规则演绎系统规则演绎系统的定义：规则演绎系统的定义：基于规则的问题求解系统运用下述规则来建立：基于规则的问题求解系统运用下述规则来建立：IfThen其中，其中，If部分可能由几个部分可能由几个if组成，而组成，而Then部分可能由一个或
46、一部分可能由一个或一个以上的个以上的then组成。组成。在全部基于规则系统中，每个在全部基于规则系统中，每个if可能与某断言可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。集中的一个或多个断言匹配。有时把该断言集称为工作内存。在很多基于规则系统中，在很多基于规则系统中，then部分用于规定放入工作内存的新部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统断言。这种基于规则的系统叫做规则演绎系统(rulebaseddeductionsystem)。在这种系统中，通常称每个。在这种系统中，通常称每个if部分为前项部分为前项(antecede
47、nt)，称每个，称每个then部分为后项部分为后项(consequent)。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室50/1014.2 规则演绎系统4.2.1正向规则演绎系统正向规则演绎系统正向规则演绎系统是从事实到目标进行操作正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从的，即从状况条件到动作进行推理的，也就是从if到到then的方向进行推理的。的方向进行推理的。1.事实表达式的与或形变换事实表达式的与或形变换把事实表示为非蕴涵形式的与或形，作为系把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句
48、形统的总数据库。具体变换步骤与前述化为子句形类似。类似。留意：我们不想把这些事实化为子句形，而是留意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。为叫做与或形的非蕴涵形式。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室51/1014.2 规则演绎系统4.2.1正向规则演绎系统正向规则演绎系统例：有事实表达式例：有事实表达式(彐彐u)(v)Q(v,u)(R(v)P(v)S(u,v)把它化为把它化为Q(v,A)R(v)P(v)S(A,v)对变量更名标准化，使得同一变量不出
49、现在事实表达式的对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中，得：不同主要合取式中，得：Q(w,A)R(v)P(v)S(A,v)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室52/1014.2 规则演绎系统4.2.1正向规则演绎系统正向规则演绎系统2.事实表达式的与或图表示事实表达式的与或图表示将上例与或形的事实表达式用与或图来表示将上例与或形的事实表达式用与或图来表示 Q(w,A)R(v)P(v)S(A,v)Q(w,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人
50、工智能与数据挖掘研究室53/1014.2 规则演绎系统4.2.1正向规则演绎系统正向规则演绎系统3.与或图的与或图的F规则变换规则变换这些规则是建立在某个问题辖域中一般陈述性这些规则是建立在某个问题辖域中一般陈述性学问的蕴涵公式基础上的。把允许用作规则的公式学问的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式类型限制为下列形式LW式中：式中：L是单文字；是单文字；W为与或形的唯一公式。为与或形的唯一公式。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室54/1014.2 规则演绎系统4.2.1正向规则演绎系统正向规则演绎系统3.与或图的与或图的F规则变换规则