矿大人工智能确定性推理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 确定性推理,智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型，本章重点讨论前一种，不确定性推理放到下一章讨论。,4.1,推理的基本概念,4.2,推理的逻辑基础,4.3,自然演绎推理,4.4,归结演绎推理,4.5,基于规则的演绎推理,1,4.1,推理的基本概念,4.1.1,什么是推理,4.1.2,推理方法及其分类,4.1.3,推理的控制策略及其分类,4.1.4,正向推理,4.1.5,逆向推理,4.1.6,混合推理,2,4.1.1,什么是推理,推理的概念,是指按照某种策略从已知事实出发去推出结论的过程。,推理所用的事实：,初始证据：,推理前用户提供的,中间结论：,推理过程中所得到的,推理过程：,由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。,例如，,医疗专家系统，专家知识保存在知识库中。推理开始时，先把病人的症状和检查结果放到综合数据库中，然后再从综合数据库的初始证据出发，按照某种策略在知识库中寻找，并使用知识，直到推出最终结论为止。,推理的两个基本问题,推理的方法：,解决前提和结论的逻辑关系，不确定性传递,推理的控制策略：,解决推理方向，冲突消解策略,3,4.1.2,推理方法及其分类,1.,按推理的逻辑基础分类,(1/4),可分为演绎推理、归纳推理等,演绎推理,演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论，如,假言推理、拒取式和假言三段论,。,例： 假言三段论,AB,，,BC AC,常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中，,大前提,是已知的一般性知识或推理过程得到的判断；,小前提,是关于某种具体情况或某个具体实例的判断；,结论,是由大前提推出的，并且适合于小前提的判断。,例如，有如下三个判断：, 计算机系的学生都会编程序； （一般性知识）, 程强是计算机系的一位学生； （具体情况）, 程强会编程序。 （结论）,这是一个三段论推理。其中，是大前提，是小前提；是经演绎推出来的结论。,可见，其结论是蕴含在大前提中的。,4,4.1.2,推理方法及其分类,1.,按推理的逻辑基础分类,(2/4),归纳推理,是一种由个别到一般的推理方法。归纳推理的类型,按照所选事例的广泛性,可分为完全归纳推理和不完全归纳推理,按照推理所使用的方法,可分为枚举、类比、统计和差异归纳推理等,完全归纳推理,是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。,不完全归纳推理,是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。例如，计算机，随机抽查。,枚举归纳推理,是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。,例如，设有如下事例：,王强是计算机系学生，他会编程序；,高华是计算机系学生，她会编程序；, ,当这些具体事例足够多时，就可归纳出一个一般性的知识：,凡是计算机系的学生，就一定会编程序。,5,4.1.2,推理方法及其分类,1.,按推理的逻辑基础分类,(3/4),类比归纳推理,是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。,设,A,、,B,分别是两类事物的集合：,A=a,1,a,2,B=b,1,b,2,并设,a,i,与,b,i,总是成对出现，且当,ai,有属性,P,时，,bi,就有属性,Q,与此对应，即,P(a,i,)Q(b,i,) i=1,2,.,则当,A,与,B,中有一新的元素对出现时，若已知,a,有属性,P,，,b,有属性,Q,，即,P(a)Q(b),类比归纳推理的基础是相似原理，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。,6,4.1.2,推理方法及其分类,1.,按推理的逻辑基础分类,(4/4),演绎推理与归纳推理的区别,演绎推理,是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它,不能增殖新知识,。,归纳推理,所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，,是增殖新知识,的过程。,例如，,一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种,归纳,推理方式。运用这些一般性知识知识去维修计算机的过程则是,演绎,推理。,7,4.1.3,推理的控制策略及其分类,推理的控制策略,推理过程不仅依赖于所用的推方法，同时也依赖于推理的控制策略。,推理的控制策略是指,如何使用领域知识使推理过程尽快达到目标的策略,。,控制策略的分类,由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为,推理策略和搜索策略,。,推理策略,主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等,推理方向控制策略,用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理。,求解策略,是指仅求一个解，还是求所有解或最优解等。,限制策略,是指对推理的深度、宽度、时间、空间等进行的限制。,冲突消解策略,是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。,搜索策略,主要解决,推理线路、推理效果、推理效率等问题,。 本章主要讨论推理策略，,8,4.1.4,正向推理,推理算法,从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。,算法描述,(1),把用户提供的初始证据放入综合数据库；,(2),检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；,(3),检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转,(5),。,(4),按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转,(2),。,(5),询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转,(3),；否则表示无解，失败退出。,至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。,其流程图如下：,9,把初始证据放入,DB,DB,中有解吗？,KB,中有可用知识吗？,形成可用知识集,可用知识集空吗？,按照冲突消解策略从该知识,集中选出一条知识进行推理,推出的是新事实吗？,将新事实加入到,DB,把用户补充的新事,实,加入到,DB,中,用户可补充新事实吗？,失败退出,成功退出,Y,N,N,Y,N,N,N,Y,Y,Y,10,4.1.4,正向推理,推理例子,例,4.1,请用正向推理完成以下问题的求解,假设知识库中包含有以下,2,条规则：,r,1,：,IF B THEN C,r,2,：,IF A THEN B,已知初始证据,A,，求证目标,C,。,解：本例的推理过程如下：,推理开始前，综合数据库为空。,推理开始后，先把,A,放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为“,N”,。,接着检查知识库中是否有可用知识，显然,r,2,可用，形成仅含,r,2,的知识集。从该知识集中取出,r,2,，推出新的实事,B,，将,B,加入综合数据库，检查综合数据库中是否含有目标,C,，回答为“,N”,。,再检查知识库中是否有可用知识，此时由于,B,的加入使得,r,1,为可用，形成仅含,r,1,的知识集。从该知识集中取出,r,1,，推出新的实事,C,，将,C,加入综合数据库，检查综合数据库中是否含有目标,C,，回答为“,Y”,。,它说明综合数据库中已经含有问题的解，推理成功结束，目标,C,得证。,11,4.1.4,正向推理,优缺点,正向推理的主要优点,比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。,正向推理的主要缺点,推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。,12,4.1.5,逆向推理,推理算法,从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。,算法描述：,(1),将要求证的目标（称为假设）构成一个假设集；,(2),从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行,(2),；若该假设不在数据库中，则执行下一步；,(3),检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转,(5),；若能由某个知识导出，则执行下一步；,(4),将知识库中可以导出该假设的所有知识构成一个可用知识集；,(5),检查可用知识集是否为空，若是，失败退出；否则执行下一步；,(6),按冲突消解策略从可用知识集中取出一个知识，继续；,(7),将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转,(2),。,其流程图如下：,13,初始化,DB,和假设集,该假设是,DB,中的事实吗？,该假设能被,KB,中的知识导出吗？,从假设集中取出一个假设,可用知识集空吗？,按照冲突消解策略从该知识,集中选出一条知识,将该知识前提中的每个子条件作为新的假设加入假设集,该假设成立,并放入,DB,还有新的假设吗？,失败退出,成功退出,Y,N,Y,Y,N,N,N,N,Y,将,KB,中所有能导出此假设,的知识构成一个可用知识集,询问用户有此事实吗？,该假设,成立,Y,14,4.1.5,逆向推理,推理例子,对上例，采用逆向推理，其推理过程如下：,推理开始前，综合数据库和假设集均为空。,推理开始后，先将初始证据,A,和目标,C,分别放入综合数据库和假设集，然后从假设集中取出一个假设,C,，查找,C,是否为综合数据库中的已知事实，回答为“,N”,。,再检查,C,是否能被知识库中的知识所导出，发现,C,可由,r,1,导出，于是,r,1,被放入可用知识集。由于知识库中只有,r,1,可用，故可用知识集中仅含,r,1,。,接着从可用知识集中取出,r,1,，将其前提条件,B,作为新的假设放入假设集。从假设集中取出,B,，检查,B,是否为综合数据库中的实事，回答为“,N”,。再检查,B,是否能被知识库中的知识所导出，发现,B,可由,r,2,导出，于是,r,2,被放入可用知识集。由于知识库中只有,r,2,可用，故可用知识集中仅含,r,2,。,从可用知识集中取出,r,2,，将其前提条件,A,作为新的假设放入假设集。然后从假设集中取出,A,，检查,A,是否为综合数据库中的实事，回答为“,Y”,。,他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标,C,得证。,15,4.1.5,逆向推理,优缺点,逆向推理的主要优点,不必寻找和使用那些与假设目标无关的信息和知识,推理过程的目标明确,也有利于向用户提供解释，在诊断性专家系统中较为有效。,逆向推理的主要缺点,当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。,16,4.1.6,混合推理,混合推理的概念,把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。,混合推理的方法,1.,先正向后逆向,这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。,2.,先逆向后正向,这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。,3.,双向混合,是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。,对于这些方法我不再详细讨论。,17,第,4,章 确定性推理,4.1,推理的基本概念,4.2,推理的逻辑基础,4.3,自然演绎推理,4.4,归结演绎推理,4.5,基于规则的演绎推理,18,4.2,推理的逻辑基础,4.2.1,谓词公式的解释,4.2.2,谓词公式的永真性和可满足性,4.2.3,谓词公式的等价性和永真蕴含性,4.2.4,谓词公式的范式,4.2.5,置换与合一,19,4.2.1,谓词公式的解释,概念,命题公式的解释,在命题逻辑中，,命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。,有了命题公式的解释，就可据此求出该命题公式的真值。,谓词公式的解释,由于谓词公式中可能包含由个体,常量、变元或函数,，因此，必须先考虑这些个体常量和函数在个体域上的取值，然后才能根据它们的具体取值为谓词分别指派真值。,定义,4.1,设,D,是谓词公式,P,的非空个体域，若对,P,中的个体常量、函数和谓词按如下规定赋值：,(1),为每个个体常量指派,D,中的一个元素；,(2),为每个,n,元函数指派一个从,D,n,到,D,的一个映射，其中,D,n,=(x,1, x,2, , x,n,)| x,1, x,2, , x,n,D,(3),为每个,n,元谓词指派一个从,D,n,到,F,，,T,的映射。,则称这些指派为,P,在,D,上的一个解释,I,20,4.2.1,谓词公式的解释,例子一,(1/2),例,4.2,设个体域,D=1, 2,，求公式,A=(x)( y)P(x, y),在,D,上的解释，并指出在每一种解释下公式,A,的真值。,解：,由于公式,A,中没有包含个体常量和函数，故可直接为谓词指派真值，设有,这就是公式,A,在,D,上的一个解释。从这个解释可以看出：,当,x=1,、,y=1,时，有,P(x,y),的真值为,T;,当,x=2,、,y=1,时，有,P(x,y),的真值为,T;,即对,x,在,D,上的任意取值，都存在,y=1,使,P(x,y),的真值为,T,。因此，在此解释下公式,A,的真值为,T,。,P(1,1),P(1,2),P(2,1),P(2,2),T,F,T,F,21,4.2.1,谓词公式的解释,例子一,(2/2),说明：,一个谓词公式在其个体域上的解释不是唯一的。例如，对公式,A,，若给出另一组真值指派,这也是公式,A,在,D,上的一个解释。从这个解释可以看出：,当,x=1,、,y=1,时，有,P(x,y),的真值为,T;,当,x=2,、,y=1,时，有,P(x,y),的真值为,F;,即对,x,在,D,上的任意取值，不存在一个,y,使得,P(x,y),的真值为,T,。因此，在此解释下公式,A,的真值为,F,。,实际上，,A,在,D,上共有,16,种解释，这里就不在一一列举。,P(1,1),P(1,2),P(2,1),P(2,2),T,T,F,F,22,4.2.1,谓词公式的解释,例子二,例,4.3,设个体域,D=1, 2,，求公式,B=(x)P(f(x), a),在,D,上的解释，并指出在该解释下公式,B,的真值。,解：,设对个体常量,a,和函数,f(x),的值指派为：,对谓词的真值指派为：,由于已指派,a=1,，因此,P(1,2),和,P(2,2),不可能出现，故没给它们指派真值。,上述指派是公式,B,在,D,上的一个解释。在此解释下有,当,x=1,时，,a=1,使,P(1,1)=T,当,x=2,时，,a=1,使,P(2,1)=T,即对,x,在,D,上的任意取值，都存在,a=1,使,P(f(x), a),的真值为,T,。因此，在此解释下公式,B,的真值为,T,。,由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为,T,，而在另一个解释下为,F,。,a,f(1),f(2),1,1,2,P(1,1),P(1,2),P(2,1),P(2,2),T,T,23,4.2.2,谓词公式的永真性和可满足性,为了以后推理的需要，下面先定义：,定义,4.2,如果谓词公式,P,对非空个体域,D,上的任一解释都取得真值,T,，则称,P,在,D,上是永真,的；如果,P,在任何非空个体域上均是永真的，则称,P,永真,。,可见，要判定一谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就很难判定了。,定义,4.3,对于谓词公式,P,，如果至少存在,D,上的一个解释，使公式,P,在此解释下的真值为,T,，则称公式,P,在,D,上是可满足,的。,谓词公式的,可满足性也称为相容性,。,定义,4.4,如果谓词公式,P,对非空个体域,D,上的任一解释都取真值,F,，则称,P,在,D,上是永假,的；如果,P,在任何非空个体域上均是永假的，则称,P,永假,。,谓词公式的永假性又称,不可满足性或不相容,。,后面我们要给出的归结推理，就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。,24,4.2.3,谓词公式的等价性和永真蕴含性,1.,等价式,(1/2),谓词公式的,等价性,和,永真蕴含性,可分别用相应的,等价式,和,永真蕴含式,来表示，这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为推理规则。,谓词公式的,等价式可定义如下,：,定义,4.5,设,P,与,Q,是,D,上的两个谓词公式，若对,D,上的任意解释，,P,与,Q,都有相同的真值，则称,P,与,Q,在,D,上是等价的。如果,D,是任意非空个体域，则称,P,与,Q,是等价的，记作,PQ,。,25,4.2.3,谓词公式的等价性和永真蕴含性,1.,等价式,(2/2),(1),双重否定律, P P,(2),交换律,(PQ) (QP),，,( PQ) ( QP),(3),结合律,(PQ)R P(QR),(PQ)R P(QR),(4),分配律,P(QR) (PQ)(PR),P(QR) (PQ)(PR),(5),摩根定律, (PQ) PQ, (PQ) PQ,(6),吸收律,P(PQ) P,P(PQ) P,(7),补余律,PP T, PP F,(8),连词化归律,PQ PQ,P,Q (PQ)(QP),P,Q (PQ)(QP),(9),量词转换律, (,x)P (x)( P), (x)P (,x) ( P),(10),量词分配律,(x) (PQ) (x)P(x)Q,(,x) (PQ) (,x)P(,x)Q,26,4.2.3,谓词公式的等价性和永真蕴含性,2.,永真蕴含式,定义,4.6,对谓词公式,P,和,Q,，如果,PQ,永真，则称,P,永真蕴含,Q,，且称,Q,为,P,的逻辑结论，,P,为,Q,的前提，记作,P Q,。,常用的永真蕴含式如下：,(1),化简式,PQ P,，,PQ Q,(2),附加式,P PQ,，,Q PQ,(3),析取三段论, P, PQ Q,(4),假言推理,P, PQ Q,(5),拒取式,Q, PQ P,(6),假言三段论,PQ, QR PR,(7),二难推理,PQ, PR, QR R,(8),全称固化,(,x)P(x) P(y),其中，,y,是个体域中的任一个体，依此可消去谓词公式中的全称量词。,(9),存在固化,(,x)P(x) P(y),其中，,y,是个体域中某一个可以使,P(y),为真的个体，依此可消去谓词公式中的存在量词。,27,4.2.4,谓词公式的范式,范式是谓词公式的标准形式。在谓词逻辑中，范式分为两种：,前束范式,定义,4.7,设,F,为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称,F,为前束范式。一般形式：,(Q,1,x,1,)(Q,n,x,n,)M(x,1,x,2,x,n,),其中，,Q,i,(i=1,2,n),为前缀，它是一个由全称量词或存在量词组成的量词串；,M(x,1,x,2,x,n,),为母式，它是一个不含任何量词的谓词公式。,例如,，,(,x) (,y) (,z)(P(x)Q(y,z)R(x,z),是前束范式。,任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集的化简中讨论。,Skolem,范式,定义,4.8,如果前束范式中,所有的存在量词都在全称量词之前,，则称这种形式的谓词公式为,Skolem,范式。,例如,，,(,x) (,z) (,y)(P(x)Q(y,z)R(x,z),是,Skolem,范式。,任一谓词公式均可化为与其对应的,Skolem,范式，其化简方法也将在后面子句集的化简中讨论。,28,4.2.5,置换与合一,概念,在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理过程是不能直接进行匹配的，需要先进行置换。,例如，可根据,全称固化,推理和,假言推理,由谓词公式,W,1,(A),和,(,x)(W,1,(x)W,2,(x),推出,W,2,(A),。对谓词,W,1,(A),可看作是由全程固化推理（即,(,x)(W,1,(x) W,1,(A),推出的，其中,A,是任一个体常量。要使用假言推理，首先需要找到项,A,对变元,x,的,置换,，使,W,1,(A),与,W,1,(x),一致。,这种寻找项对变元的置换，使谓词一致的过程叫做,合一的过程,。,下面讨论置换与合一的有关概念与方法。,29,4.2.5,置换与合一,1.,置换,(1/2),置换可简单的理解为是在一个谓词公式中用置换项去替换变量。,定义,4.9,置换是形如,t,1,/x,1,t,2,/x,2,t,n,/x,n,的有限集合。其中，,t,1,t,2,t,n,是项；,x,1,x,2,x,n,是互不相同的变元；,t,i,/x,i,表示用,t,i,替换,x,i,。并且要求,t,i,与,x,i,不能相同，,xi,不能循环地出现在另一个,t,i,中。,例如，,a/x, c/y, f(b)/z,是一个置换。,但,g(y)/x, f(x)/y,不是一个置换。原因是它在,x,与,y,之间出现了循环置换现象。即当用,g(y),置换,x,用,f(g(y),置换,y,时，既没有消去,x,，也没有消去,y,。,若改为,g(a)/x, f(x)/y,即可，原因是用,g(a),置换,x,，用,f(g(a),置换,y,，则消去了,x,和,y,。,通常，置换是用希腊字母,、,、,、,等来表示的。,定义,4.10,设,=t,1,/x,1,t,2,/x,2,t,n,/x,n,是一个置换，,F,是一个谓词公式，把公式,F,中出现的所有,x,i,换成,t,i,(i=1,2,n),，得到一个新的公式,G,，称,G,为,F,在置换,下的,例示,，记作,G=F,。,一个谓词公式的任何例示都是该公式的逻辑结论。,30,4.2.5,置换与合一,1.,置换,(2/2),定义,4.11,设,=t,1,/x,1,t,2,/x,2,t,n,/x,n,= u,1,/y,1, u,2,/y,2, , u,m,/y,m,是两个置换。则,与,的合成也是一个置换，记作,。它是从集合, t,1,/x,1, t,2,/x,2, , t,n,/x,n, u,1,/y,1, u,2,/y,2, , u,m,/y,m,中删去以下两种元素, 当,t,i,=x,i,时，删去,t,i,/x,i,(i=1, 2 , n),；, 当,y,j, x,1, x,2, x,n,时，删去,u,j,/y,j,(j=1, 2 , m),最后剩下的元素所构成的集合。,例,4.4,设,= f(y)/x, z/y ,，,=a/x, b/y ,y/z ,，求,与,的合成。,解,:,先求出集合,f(b/y)/x, (y/z)/y, a/x, b/y , y/z=f(b)/x, y/y, a/x, b/y , y/z,其中，,f(b)/x,中的,f(b),是置换,作用于,f(y),的结果；,y/y,中的,y,是置换,作用于,z,的结果。在该集合中，,y/y,满足定义中的条件，需要删除；,a/x,和,b/y,满足定义中的条件，也需要删除。最后得,=f(b)/x, y/z,31,4.2.5,置换与合一,2.,合一,合一,可理解为,是寻找项对变量的置换，使两个谓词公式一致,。可定义为：,定义,4.12,设有公式集,F=F,1, F,2,F,n,，若存在一个置换,，可使,F,1,=F,2,=F,n,，,则称,是,F,的一个合一。称,F,1,F,2,F,n,是可合一的。,例如，,设有公式集,F=P(x,y,f(y), P(a,g(x),z),，则,=a/x, g(a)/y, f(g(a)/z,是它的一个合一。,一般来说，一个公式集的合一不是唯一的。,定义,4.13,设,是公式集,F,的一个合一，如果对,F,的任一个合一,都存在一个置换,，使得,=,，则称,是一个最一般合一。,一个公式集的最一般合一是唯一的。,对如何求取最一般合一的问题，不再讨论。,32,第,4,章 确定性推理,4.1,推理的基本概念,4.2,推理的逻辑基础,4.3,自然演绎推理,4.4,归结演绎推理,4.5,基于规则的演绎推理,33,4.3,自然演绎推理,自然演绎推理,从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。,自然演绎推理最基本的推理规则是三段论推理，它包括：,假言推理,P, PQ Q,拒取式,Q, PQ P,假言三段论,PQ, QR PR,自然演绎推理的例子,例,4.5,设已知如下事实：,A, B, AC, BCD, DQ,求证：,Q,为真。,证明：,因为,A, AC C,假言推理,B, C BC,引入合取词,BC,，,BCD D,假言推理,D, DQ Q,假言推理,因此，,Q,为真,34,4.3,自然演绎推理,例,4.6,设已知如下事实：,(1),只要是需要编程序的课，王程都喜欢。,(2),所有的程序设计语言课都是需要编程序的课。,(3) C+,是一门程序设计语言课。,求证：王程喜欢,C+,这门课。,证明：,首先定义谓词,Prog(x) x,是需要编程序的课。,Like(x, y) x,喜欢,y,。,Lang(x) x,是一门程序设计语言课,把已知事实及待求解问题用谓词公式表示如下：,Prog(x)Like(Wang , x),(x)( Lang(x)Prog(x),Lang(C+),应用推理规则进行推理：,Lang(y)Prog(y),全称固化,Lang(C+),，,Lang(y)Prog(y) Prog(C+),假言推理,C+/y,Prog(C+), Prog(x)Like(Wang , x) Like(Wang , C+),假言推理,C+/x,因此，王程喜欢,C+,这门课。,35,4.3,自然演绎推理,优点：,定理证明过程自然，易于理解，并且有丰富的推理规则可用。,缺点：,是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。,36,第,4,章 确定性推理,4.1,推理的基本概念,4.2,推理的逻辑基础,4.3,自然演绎推理,4.4,归结演绎推理,4.5,基于规则的演绎推理,37,4.4,归结演绎推理,归结演绎推理是一种基于鲁宾逊（,Robinson,）归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于,1965,年在海伯伦（,Herbrand,）理论的基础上提出的一种基于逻辑的“反证法”。,在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。,定理证明的实质,，就是要对前提,P,和结论,Q,，证明,PQ,永真。,由,4.2,节可知，要证明,PQ,永真，就是要证明,PQ,在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。,为此，人们进行了大量的探索，后来发现可以,采用反证法的思想,，把关于,永真性的证明转化为关于不可满足性的证明,。,即要证明,PQ,永真，只要能够证明,PQ,是不可满足的就可以了,(,原因是, (PQ) ,(,PQ),P,Q,。,这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。,38,4.4,归结演绎推理,4.4.1,子句集及其化简,4.4.2,鲁滨逊归结原理,4.4.3,归结反演推理的归结策略,4.4.4,用归结反演求取问题的答案,39,4.4.1,子句集及其化简,1.,子句和子句集,鲁滨逊归结原理是在子句集的基础上讨论问题的。因此，讨论归结演绎推理之前，需要先讨论子句集的有关概念。,子句和子句集,定义,4.14,原子谓词公式及其否定统称为,文字,。,例如，,P(x),、,Q(x),、, P(x),、, Q(x),等都是文字。,定义,4.15,任何文字的析取式称为,子句,。,例如，,P(x)Q(x),，,P(x,，,f(x)Q(x,，,g(x),都是子句。,定义,4.16,不含任何文字的子句称为,空子句,。,由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。,空子句一般被记为或,NIL,。,定义,4.17,由子句或空子句所构成的集合称为,子句集,。,40,4.4.1,子句集及其化简,2.,子句集的化简（,1/6,）,在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下：,(1),消去连接词“”和“,”,反复使用如下等价公式：,PQ PQ,P,Q (PQ)(PQ),即可消去谓词公式中的连接词“”和“,”。,例如公式,(x)(y)P(x,y) (y)(Q(x,y)R(x,y),经等价变化后为,(x)(y)P(x,y) (y)(Q(x,y)R(x,y),41,4.4.1,子句集及其化简,2.,子句集的化简（,2/6,）,(2),减少否定符号的辖域,反复使用,双重否定率,(P) P,摩根定律,(PQ) PQ,(PQ) PQ,量词转换率, (x)P(x) (x) P(x), (x)P(x) (x),P(x),将每个否定符号“,”,移到仅靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。,例如，,上式经等价变换后为,(x)(y)P(x,，,y)(y)( Q(x,，,y) R(x,，,y),42,4.4.1,子句集及其化简,2.,子句集的化简（,3/6,）,(3),对变元标准化,在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。,例如，上式经变换后为,(,x)(,y)P(x,，,y)(,z)( Q(x,，,z) R(x,，,z),(4),化为前束范式,化为前束范式的方法,:,把所有量词都移到公式的左边，并且在移动时,不能改变其相对顺序,。由于第,(3),步已对变元进行了标准化，每个量词都有自己的变元，这就消除了任何由变元引起冲突的可能，因此这种移动是可行的。,例如，上式化为前束范式后为,(,x)(,y) (,z)(P(x,，,y)( Q(x,，,z) R(x,，,z),43,4.4.1,子句集及其化简,2.,子句集的化简（,4/6,）,(5),消去存在量词,消去存在量词时，需要区分以下两种情况：,若存在量词不出现在全称量词的辖域内,（即它的左边没有全称量词），只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。,若存在量词位于一个或多个全称量词的辖域内,，例如,(x,1,)(x,n,) (y)P(x,1,，,x,2, x,n,y),则需要用,Skolem,函数,f(x,1,，,x,2, x,n,),替换受该存在量词约束的变元,y,，然后再消去该存在量词。,例如，上步所得公式中存在量词,(y),和,(z),都位于,(x),的辖域内，因此都需要用,Skolem,函数来替换。设替换,y,和,z,的,Skolem,函数分别是,f(x),和,g(x),，则替换后的式子为,(x)(P(x,f(x)(Q(x,g(x)R(x,g(x),44,4.4.1,子句集及其化简,2.,子句集的化简（,5/6,）,(6),化为,Skolem,标准形,Skolem,标准形的一般形式为,(x,1,)(x,n,) M(x,1,x,2,x,n,),其中，,M(x,1,x,2,x,n,),是,Skolem,标准形的母式，它由子句的合取所构成。,把谓词公式化为,Skolem,标准形需要使用以下等价关系,P(QR) (PQ)(PR),例如，前面的公式化为,Skolem,标准形后为,(x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x),(7),消去全称量词,由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。但剩下的母式，仍假设其变元是被全称量词量化的。,例如，上式消去全称量词后为,(P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x),45,4.4.1,子句集及其化简,2.,子句集的化简（,6/6,）,(8),消去合取词,在母式中消去所有合取词，把母式用子句集的形式表示出来。其中，子句集中的每一个元素都是一个子句。,例如，,上式的子句集中包含以下两个子句,P(x,f(x)Q(x,g(x),P(x,f(x)R(x,g(x),(9),更换变量名称,对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此任意两个不同子句的变量之间实际上不存在任何关系。这样，更换变量名是不会影响公式的真值的。,例如，,对前面的公式，可把第二个子句集中的变元名,x,更换为,y,，得到如下子句集,P(x,f(x)Q(x,g(x),P(y,f(y)R(y,g(y),46,4.4.1,子句集及其化简,3.,子句集的应用（,1/4,）,在上述化简过程中，由于在消去存在量词时所用的,Skolem,函数可以不同，因此,化简后的标准子句集是不唯一的,。,这样，当原谓词公式为,非永假,时，它与其标准子句集并不等价。但当原谓词公式为,永假,（或不可满足）时，其标准子句集则一定是永假的，即,Skolem,化并不影响原谓词公式的永假性,。,这个结论很重要，是归结原理的主要依据，可用定理的形式来描述。,定理,4.1,设有谓词公式,F,，其标准子句集为,S,，则,F,为不可满足的充要条件是,S,为不可满足的。,为证明此定理，先作如下说明：,为讨论问题方便，设给定的谓词公式,F,已为前束形,(Q,1,x,1,) (Q,r,x,r,) (Q,n,x,n,)M(x,1,x,2,x,n,),其中，,M(x,1,x,2,x,n,),已化为合取范式。,由于将,F,化为这种前束形是一种很容易实现的等价运算，因此这种假设是可以的。,47,4.4.1,子句集及其化简,3.,子句集的应用（,2/4,）,又设,(Q,r,x,r,),是第一个出现的存在量词,(x,r,),，即,F,为,F=(x,1,)(x,r-1,) (x,r,)(Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,x,r,x,r+1,x,n,),为把,F,化为,Skolem,形，需要先消去这个,(x,r,),，并引入,Skolem,函数，得到,F,1,=(x,1,)(x,r-1,) (Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,f(x,1,x,r-1,),x,r+1,x,n,),若能证明,F,不可满足 ,F,1,不可满足,则同理可证,F,1,不可满足 ,F,2,不可满足,重复这一过程，直到证明了,F,m-1,不可满足 ,F,m,不可满足,为止。,此时，,F,m,已为,F,的,Skolem,标准形。而,S,只不过是,F,m,的一种集合表示形式。因此有,F,m,不可满足 ,S,不可满足,下面开始用反证法证明,F,不可满足 ,F,1,不可满足,48,4.4.1,子句集及其化简,3.,子句集的应用（,3/4,）,先证明 ,已知,F,不可满足，,假设,F,1,是可满足的，则存在一个解释,I,，使,F,1,在解释,I,下为真。即对任意,x,1,x,r-1,在,I,的设定下有,(Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,f(x,1,x,r-1,),x,r+1,x,n,),为真。亦即对任意的,x,1,x,r-1,都有一个,f(x,1,x,r-1,),使,(Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,f(x,1,x,r-1,),x,r+1,x,n,),为真。即在,I,下有,(x,1,)(x,r-1,) (x,r,)(Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,x,r,x,r+1,x,n,),为真。即,F,在,I,下为真。,但这与前提,F,是不可满足的相矛盾，即,假设,F,1,为可满足是错误的,。从而可以得出“若,F,不可满足，则必有,F,1,不可满足”。,49,4.4.1,子句集及其化简,3.,子句集的应用（,4/4,）,再证明,已知,F1,不可满足，假设,F,是可满足的。于是便有某个解释,I,使,F,在,I,下为真。即对任意的,x,1,x,r-1,在,I,的设定下都可找到一个,x,r,使,(Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,x,r,x,r+1,x,n,),为真。若扩充,I,，使它包含一个函数,f(x,1,x,r-1,),，且有,x,r,= f(x,1,x,r-1,),这样，就可以把所有的,(f(x,1,x,r-1,),映射到,x,r,，从而得到一个新的解释,I,，并且在此解释下对任意的,x,1,x,r-1,都有,(Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,f(x,1,x,r-1,),x,r+1,x,n,),为真。即在,I,下有,(x,1,)(x,r-1,) (Q,r+1,x,r+1,)(Q,n,x,n,)M(x,1,x,r-1,f(x,1,x,r-1,),x,r+1,x,n,),为真。它说明,F,1,在解释,I,下为真。但这与前提,F,1,是不可满足的相矛盾，即假设,F,为可满足是错误的。从而可以得出“若,F,1,不可满足，则必有,F,不可满足”,于是，定理得证。,由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。,至于如何证明一个子句集的不可满足性，由下面的海伯伦理论和鲁宾逊归结原理来解决。,50,4.4.2,鲁滨逊归结原理,1.,基本思想,注意以下两个关键,第一，,子句集中的子句之间是合取关系。因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的；,第二，,空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。,鲁滨逊归结原理基本思想,首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集,S,。然后设法检验子句集,S,是否含有空子句，若含有空子句，则表明,S,是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。,鲁滨逊归结原理包括,命题逻辑归结原理,谓词逻辑归结原理,51,4.4.2,鲁滨逊归结原理,2.,命题逻辑的归结（,1/8,）,归结推理的核心是求两个子句的归结式,(1),归结式的定义及性质,定义,4.18,若,P,是原子谓词公式，则称,P,与,P,为,互补文字,。,定义,4.19,设,C,1,和,C,2,是子句集中的任意两个子句，如果,C,1,中的文字,L,1,与,C,2,中的文字,L,2,互补，那么可从,C,1,和,C,2,中分别消去,L,1,和,L,2,，并将,C,1,和,C,2,中余下的部分按析取关系构成一个新的子句,C,12,，则称这一过程为,归结,，称,C,12,为,C,1,和,C,2,的,归结式,，称,C,1,和,C,2,为,C,12,的,亲本子句,。,例,4.7,设,C,1,=PQR,，,C,2,=PS,，求,C,1,和,C,2,的归结式,C,12,。,解：,这里,L,1,=P,，,L,2,=P,，通过归结可以得到,C,12,= QRS,例,4.8,设,C,1,=Q,，,C,2,=Q,，求,C,1,和,C,2,的归结式,C,12,。,解：,这里,L,1,=Q,，,L,2,=Q,，通过归结可以得到,C,12,= NIL,52,4.4.2,鲁滨逊归结原理,2.,命题逻辑的归结（,2/8,）,例,4.9,设设,C,1,=,P,Q,，,C,2,=Q,，,C,3,=P,，求,C,1,、,C,2,、,C,3,的归结式,C,123,。,解：,若先对,C,1,、,C,2,归结，可得到,C,12,=P,然后再对,C,12,和,C,3,归结，得到,C,123,=NIL,如果改变归结顺序,，同样可以得到相同的结果，即其归结过程是不唯一的。,其归结归结过程可用右图来表示，该树称为,归结树,。,P,Q,Q,P,P,NIL,P,Q,P,Q,Q,NIL,53,4.4.2,鲁滨逊归结原理,2.,命题逻辑的归结（,3/8,）,定理,4.2,归结式,C,12,是其亲本子句,C,1,和,C,2,的逻辑结论。,证明：（,按定义）设,C,1,=LC,1,，,C,2,=LC,2,关于解释,I,为真，则只需证明,C,12,= C,1, C,2,关于解释,I,也为真。,对于解释,I,，,L,和,L,中必有一个为假。,若,L,为假，,则必有,C,1,为真，不然就会使,C,1,为假，这将与前提假设,C,1,为真矛盾，因此只能有,C,1,为真。,同理，,若,L,为假,，则必有,C,2,为真。,因此，必有,C,12,= C,1,C,2,关于解释,I,也为真。即,C,12,是,C,1,和,C,2,的逻辑结论。,54,4.4.2,鲁滨逊归结原理,2.,命题逻辑的归结（,4/8,）,上述定理是归结原理中的一个重要定理，由它可得到以下两个推论：,推论,1,：,设,C,1,和,C,2,是子句集,S,中的两个子句，,C,12,是,C,1,和,C,2,的归结式，若用,C,12,代替,C,1,和,C,2,后得到新的子句集,S,1,，则由,S,1,的不可满足性可以推出原子句集,S,的不可满足性。即：,S,1,的不可满足性 ,S,的不可满足性,证明：,设,S= C,1,，,C,2,，,C,3,，,，,C,n,，,C,12,是,C,1,和,C,2,的归结式，则用,C,12,代替,C,1,和,C,2,后可得到一个新的子句集,S,1,= C,12,，,C,3,，, C,n,设,S,1,是不可满足的，则对不满足,S,1,的任一解释,I,，都可能有以下两种情况：, 解释,I,使,C,12,为真，则,C,3,，,，,C,n,中必有一个为假，即,S,是不可满足的。, 解释,I,使,C,12,为假，即,C,12,为真，根据定理,3.2,有, (C,1,C,2,),永真，即,C,1,C,2,永真，它说明解释,I,使,C,1,为假，或,C,2,为假。即,S,也是不可满足的。,因此可以得出,S,1,的不可满足性,S,的不可满足性,55,4.4.2,鲁滨逊归结原理,2.,命题逻辑的归结（,5/8,）,推论,2,：,设,C,1,和,C,2,是子句集,S,中的两个子句，,C,12,是,C,1,和,C,2,的归结式，若把,C,12,加入,S,中,得到新的子句集,S,2,，则,S,与,S,2,的不可满足性是等价的。即：,S,2,的不可满足性,S,的不可满足性,先证明,设,S= C,1,，,C,2,，,C,3,，,，,C,n,是不可满足的，则,C,1,，,C,2,，,C,3,，,，,C,n,中必有一子句为假，因而,S,2,= C,12,，,C,1,，,C,2,，,C3,，,，,C,n,必为不可满足。,再证明,设,S,2,是不可满足的,则对不满足,S,2,的任一解释,I,都可能有以下两种情况：,