人工智能第四章经典逻辑推理ppt课件.ppt

1,第4章 经典逻辑推理,4.1 推理的基本概念4.2 自然演绎推理4.3 归结演绎推理4.4 与/或形演绎推理,2,第4章 经典逻辑推理,智能系统的推理过程实际上就是一种思维过程。即运用知识进行推理来求解问题。经典逻辑推理是根据经典逻辑（命题逻辑及一阶谓词逻辑）的逻辑规则进行的一种推理。由于这种推理是基于经典逻辑的，其真值只有“真”和“假”两种，因此它是一种精确推理，或称为确定性推理。,3,4.1 推理的基本概念,4.1.1 推理方式及其分类4.1.2 推理的控制策略4.1.3 模式匹配及其变量代换,4,4.1.1 推理方法及其分类,1. 按推理的逻辑基础分类演绎推理归纳推理默认推理,5,4.1.1 推理方法及其分类,（1）演绎推理 演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论， 如 假言推理、拒取式和假言三段论。,6,（1）演绎推理 例： 假言三段论 AB，BC AC 常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。 大前提是已知的一般性知识或推理过程得到的判断； 小前提是关于某种具体情况或某个具体实例的判断； 结论是由大前提推出的，并且适合于小前提的判断。,4.1.1 推理方法及其分类,7,4.1.1 推理方法及其分类,（1）演绎推理例，有如下三个判断： 计算机系的学生都会编程序； （一般性知识） 程强是计算机系的一位学生； （具体情况） 程强会编程序。 （结论） 这是一个三段论推理。其中，是大前提，是小前提；是经演绎推出来的结论。可见，其结论是蕴含在大前提中的。,8,4.1.1 推理方法及其分类,（2）归纳推理是一种由个别到一般的推理方法。从足够多的事例中归纳出一般性结论的推理过程。例如，设有如下事例： 王强是计算机系学生，他会编程序； 高华是计算机系学生，她会编程序； 当这些具体事例足够多时，就可归纳出一个一般性的知识： 凡是计算机系的学生，就一定会编程序。,9,4.1.1 推理方法及其分类,演绎推理与归纳推理的区别 演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。 归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。,10,4.1.1 推理方法及其分类,（3）默认推理默认推理又称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。 在默认推理过程中，如果某一时刻发现原先所作的默认不正确，则就要撤消所作的默认以及由此默认推出的结论，重新按新情况进行推理。,11,4.1.1 推理方法及其分类,2. 按推理时所用知识的确定性（1）确定性推理确定性推理是指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或者为假，没有第三种情况出现。（2）不确定性推理不确定性推理是指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假之间。（模糊集）,12,4.1.1 推理方法及其分类,3.按推理过程中结论的单调性（1）单调推理单调推理是指在推理过程中随着推理过程向前推进及新知识的进入，推出的结论呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不会出现反复的情况 ，即不会由于新知识的加入否定了前面推出的结论，从而使推理又退回到前面的某一步。（2）非单调推理非单调推理是指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。,13,4.1.1 推理方法及其分类,4.按推理过程中用到启发性知识（1）启发式推理（2）非启发式推理5.按方法论（1）基于知识的推理（2）直觉推理（常识性推理）6.按推理的简繁程度（1）简单推理（2）复合推理7.按结论是否具有必然性（1）必然性推理（2）或然性推理,14,4.1.2 推理的控制策略,推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。推理方向搜索策略求解策略冲突消解限制策略,15,1、 推理方向正向推理,从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理。 算法描述(1) 把用户提供的初始证据放入综合数据库；(2) 检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；(3) 检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。(4) 按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转(2)。(5) 询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转(3)；否则表示无解，失败退出。至于如何根据综合数据库中的事实到知识库中选取可用知识，当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略，以后将会分别讨论。 其流程图如下：,16,17,1、推理方向正向推理,例 请用正向推理完成以下问题的求解 假设知识库中包含有以下2条规则： r1： IF B THEN C r2： IF A THEN B已知初始证据A，求证目标C。解：本例的推理过程如下：推理开始前，综合数据库为空。推理开始后，先把A放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为“N”。接着检查知识库中是否有可用知识，显然r2可用，形成仅含r2的知识集。从该知识集中取出r2，推出新的实事B，将B加入综合数据库，检查综合数据库中是否含有目标C，回答为“N”。再检查知识库中是否有可用知识，此时由于B的加入使得r1为可用，形成仅含r1的知识集。从该知识集中取出r1，推出新的实事C，将C加入综合数据库，检查综合数据库中是否含有目标C，回答为“Y”。它说明综合数据库中已经含有问题的解，推理成功结束，目标C得证。,18,正向推理的主要优点比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解。正向推理的主要缺点推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低。,1、推理方向正向推理,19,1、推理方向 逆向推理,从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。算法描述：(1) 将要求证的目标（称为假设）构成一个假设集；(2) 从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步；(3) 检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一步；(4) 将知识库中可以导出该假设的所有知识构成一个可用知识集；(5) 检查可用知识集是否为空，若是，失败退出；否则执行下一步；(6) 按冲突消解策略从可用知识集中取出一个知识，继续；(7) 将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。 其流程图如下：,20,初始化DB和假设集,该假设是DB中的事实吗？,该假设能被KB中的知识导出吗？,从假设集中取出一个假设,可用知识集空吗？,按照冲突消解策略从该知识集中选出一条知识,将该知识前提中的每个子条件作为新的假设加入假设集,该假设成立并放入DB,还有新的假设吗？,失败退出,成功退出,Y,N,Y,Y,N,N,N,N,Y,将KB中所有能导出此假设的知识构成一个可用知识集,询问用户有此事实吗？,该假设 成立,Y,21,1、推理方向逆向推理,例3.2 用逆向推理完成以下问题的求解 假设知识库中包含有以下2条规则： r1： IF B THEN C r2： IF A THEN B已知初始证据A，求证目标C。推理开始前，综合数据库和假设集均为空。推理开始后，先将初始证据A和目标C分别放入综合数据库和假设集，然后从假设集中取出一个假设C，查找C是否为综合数据库中的已知事实，回答为“N”。再检查C是否能被知识库中的知识所导出，发现C可由r1导出，于是r1被放入可用知识集。由于知识库中只有r1可用，故可用知识集中仅含r1。接着从可用知识集中取出r1，将其前提条件B作为新的假设放入假设集。从假设集中取出B，检查B是否为综合数据库中的实事，回答为“N”。再检查B是否能被知识库中的知识所导出，发现B可由r2导出，于是r2被放入可用知识集。由于知识库中只有r2可用，故可用知识集中仅含r2。从可用知识集中取出r2，将其前提条件A作为新的假设放入假设集。然后从假设集中取出A，检查A是否为综合数据库中的实事，回答为“Y”。他说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。,22,1、推理方向逆向推理,逆向推理的主要优点不必寻找和使用那些与假设目标无关的信息和知识推理过程的目标明确也有利于向用户提供解释，在诊断性专家系统中较为有效。逆向推理的主要缺点当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。,23,1、推理方向混合推理,混合推理的概念把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。混合推理的应用环境已知事实不充分由正向推理得出的结论可信度不高希望得到更多的结论混合推理的方法1. 先正向后逆向这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度。 2. 先逆向后正向这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实。 3. 双向混合是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来。,24,1、推理方向双向推理,正向推理与逆向推理同时进行，在推理过程中某一步骤上“碰头”其基本思想是：一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面从某假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在中途相遇，即由正向推理所得的中间结论恰好是逆向推理此时所要求的证据，这时推理就可结束，逆向推理的假设就是推理的最终结论。,25,2. 求解策略,所谓推理的求解策略是指，推理是只求一个解，还是求所有解以及最优解等。例如前述的正向推理只用于求一个解，只要略加修改就可用来求所有解。,26,3. 限制策略,为了防止无穷的推理过程，以及由于推理过程太长从而增加时间及空间的复杂性，可在控制策略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。,27,在推理过程中，系统要不断地用当前已知的事实与知识库中的知识进行匹配，此时可能发生有多个知识匹配成功，称这种情况为发生了冲突。基本任务：解决冲突，选择其中的一条规则来执行。基本思想：对知识进行排序按针对性排序按匹配度进行排序根据领域问题的特点进行排序,4. 冲突消解策略,28,4.1.3 模式匹配及其变量代换,模式匹配是指两个知识模式（如两个谓词公式、两个框架片断等）的比较，检查这两个知识模式是否完全一致或近似一致。如果两者完全一致，或者虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。 按匹配时两个知识模式的相似程度划分，模式匹配可分为：确定性匹配不确定性匹配,29,4.1.3 模式匹配及其变量代换,确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。例如，设有如下两个知识模式： P1：Father（李四，李小四）and Man (李小四) P2：Father(x,y) and Man (y)若用“李四”代换变量x，用“李小四”代换变量y，则P1与P2就变得完全一致。不确定性匹配是指两个知识模式不完全一致，但从总体上看，它们的相似程度又落在规定的限度内。,30,4.1.3 模式匹配及其变量代换,代换（置换）可简单的理解为是在一个谓词公式中用置换项去替换变量。定义3.1代换（置换）是形如 t1/x1,t2/x2,tn/xn的有限集合。其中，t1,t2,tn是项；x1,x2,xn是互不相同的变元；ti/xi表示用ti替换xi。并且要求ti与xi不能相同，xi不能循环地出现在另一个ti中。,31,4.1.3 模式匹配及其变量代换,例如， 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。通常，置换是用希腊字母、 、 等来表示的。,32,4.1.3 模式匹配及其变量代换,定义3.2 设 =t1/x1,t2/x2,tn/xn = u1/y1, u2/y2, , um/ym 是两个置换。则与的复合（合成）也是一个置换，记作。它是从集合 t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , um/ym 中删去以下两种元素 当ti=xi时， 删去ti/xi (i=1, 2 , n)； 当yj x1, x2 , xn 时， 删去uj/yj (j=1, 2 , m)最后剩下的元素所构成的集合。,33,4.1.3 模式匹配及其变量代换,例 设= 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,34,4.1.3 模式匹配及其变量代换,合一可理解为是寻找项对变量的置换，使两个谓词公式一致。可定义为：定义3.3 设有公式集F=F1, F2,Fn，若存在一个置换，可使 F1=F2=Fn，则称是F的一个合一。称F1,F2,Fn是可合一的。例如，设有公式集F=P(x,y,f(y), P(a,g(x),z)，则 =a/x, g(a)/y, f(g(a)/z是它的一个合一。一般来说，一个公式集的合一不是唯一的。,35,4.1.3 模式匹配及其变量代换,定义3.4 设是公式集F的一个合一，如果对F的任一个合一都存在一个置换，使得=，则称是一个最一般合一。（Most General Unifier）一个公式集的最一般合一是唯一的。,36,4.1.3 模式匹配及其变量代换,差异集的概念。设有如下两个谓词公式： F1：P（x, y, z） F2：P (x, f (A), h(B) )分别从F1与F2的第一个符号开始，逐个向右比较，此时发现F1与F2构差异集：D1=y, f (A)， D2=z, h(B),37,4.1.3 模式匹配及其变量代换,求最一般合一算法（1）初始化，令k=0, Fk=F,k=。其中，是代换空集。（2）若Fk只含一个表达式，则算法停止，k就是最一般合一；否则转步骤（3）。（3）找出Fk的差异集Dk。 （4）若Dk中存在变元xk和项tk，且xk不在tk中出现，则：k+1= tk/xkFk+1=Fk tk/xkk=k+1转步骤（2）；否则， 算法终止，F的最一般合一不存在。,38,4.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) ,39,4.1.3 模式匹配及其变量代换,Loop 1：F0= P (A, x, f (g (y), P(z, f (z), f (u) 含有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) ,40,4.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)/xF2=F1f (A)/x= P(A, f (A), f (g (y), P(A, f (A), f (u),41,4.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, f (A), f (g(y) = P(A, f (A), f (g (y) ,42,4.1.3 模式匹配及其变量代换,Loop 4：F3中只含有一个表达式，故算法成功终止，3 =A/z, f (A)/x, g (y)/u，即为公式集F的最一般合一。,43,实验二：编程实现公式集的最一般合一求解,可以输入公式集，对不符合规范的公式集要报错，符合规范的公式集进入求最一般合一步骤。如果有最一般合一，要求显示每一步过程的差异集和代换，最后输出解；如果没有最一般合一，最后要作出判断。,44,第4章 经典逻辑推理,4.1 推理的基本概念4.2 自然演绎推理4.3 归结演绎推理4.4 与/或形演绎推理,45,4.2 自然演绎推理,自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括：假言推理 P, PQ Q拒取式 Q, PQ P假言三段论 PQ, QR PR例 设已知如下事实： A, B, AC, BCD, DQ 求证：Q为真。 证明：因为 A, AC C 假言推理 B, C BC 引入合取词 BC，BCD D 假言推理 D, DQ Q 假言推理因此，Q为真,46,4.2 自然演绎推理,例 设已知如下事实：(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这门课。,47,4.2 自然演绎推理,优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。 缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。,48,第4章 经典逻辑推理,4.1 推理的基本概念4.2 自然演绎推理4.3 归结演绎推理4.4 与/或形演绎推理,49,4.3 归结演绎推理,在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明PQ永真。要证明PQ永真，就是要证明PQ在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。为此，人们进行了大量的探索，后来发现可以采用反证法的思想，把关于永真性的证明转化为关于不可满足性的证明。即要证明PQ永真，只要能够证明PQ是不可满足的就可以了(原因是 (PQ) ( PQ) P Q 。这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。归结演绎推理是一种基于鲁宾逊（Robinson）归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。,50,4.3 归结演绎推理,4.3.1 谓词公式化为子句集4.3.2 归结原理4.3.3 归结反演4.3.4 基于归结反演的问题求解4.3.5 归结反演策略,51,4.3.1 谓词公式化为子句集,归结原理是在子句集的基础上讨论问题的。因此，讨论归结演绎推理之前，需要先讨论子句集的有关概念。子句和子句集 定义3.5 原子谓词公式及其否定统称为文字。 例如，P(x)、Q(x)、 P(x)、 Q(x)等都是文字。 定义3.6 任何文字的析取式称为子句。 例如，P(x)Q(x)，P(x，f(x)Q(x，g(x)都是子句。 定义3.7 不含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句可表示为NIL定义3.8 由子句或空子句所构成的集合称为子句集。,52,谓词公式化成子句集的步骤如下： (1) 消去连接词“”和“” 反复使用如下等价公式： PQ PQ PQ (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),4.3.1 谓词公式化为子句集,53,(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),4.3.1 谓词公式化为子句集,54,(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),4.3.1 谓词公式化为子句集,55,(5) 消去存在量词消去存在量词时，需要区分以下两种情况：若存在量词不出现在全称量词的辖域内（即它的左边没有全称量词），只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。若存在量词位于一个或多个全称量词的辖域内例如 (x1)(xn) (y)P(x1，x2 , xn ,y)则需要用Skolem函数f(x1，x2 , xn)替换受该存在量词约束的变元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) ) ),4.3.1 谓词公式化为子句集,56,(6) 化为Skolem标准形Skolem标准形的一般形式为 (x1)(xn) M(x1,x2,xn)其中， M(x1,x2,xn)是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),4.3.1 谓词公式化为子句集,57,(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),4.3.1 谓词公式化为子句集,58,在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此化简后的标准子句集是不唯一的。这样，当原谓词公式为非永假时，它与其标准子句集并不等价。但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。这个结论很重要，是归结原理的主要依据，可用定理的形式来描述。定理3.1 设有谓词公式F，其标准子句集为S，则F为不可满足的充要条件是S为不可满足的。由此定理可知，为要证明一个谓词公式是不可满足的，只要证明相应的子句集是不可满足的就可以了。,4.3.1 谓词公式化为子句集,59,4.3.1 谓词公式化为子句集,例 请将下述谓词公式化为子句集：(x)(y)P(x,y) (y)(Q(x,y)R(x,y)解 (x)(y)P(x,y) (y)(Q(x,y)R(x,y)(x)(y)P(x,y) (y)(Q(x,y)R(x,y) (x)(y)P(x，y)(y)( Q(x，y) R(x，y) (x)(y)P(x，y)(z)( Q(x，z) R(x，z) (x)(y) (z)(P(x，y)( Q(x，z) R(x，z) (x)(P(x,f(x) (Q(x,g(x) R(x,g(x) ) ),60,4.3.1 谓词公式化为子句集,(x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x) (P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x) (P(x,f(x)Q(x,g(x) (P(y,f(y)R(y,g(y)消去合取词后，上式就变为下述子句集：P(x, f (x)Q(x, g (x)P(y, f (y)R(y, g (y),61,4.3.2 归结原理,鲁滨逊归结原理基本思想首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S。然后设法检验子句集S是否含有空子句，若含有空子句，则表明S是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。鲁滨逊（Robinson）归结原理包括命题逻辑归结原理谓词逻辑归结原理,62,一、命题逻辑的归结原理 归结推理的核心是求两个子句的归结式 (1) 归结式的定义及性质定义3.9 若P是原子谓词公式，则称P与P为互补文字。定义3.10 设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。,4.3.2 归结原理,63,例3.5 设C1=PQR，C2=PS，求C1和C2的归结式C12。解：这里L1=P，L2=P，通过归结可以得到 C12= QRS例3.6 设C1=Q，C2=Q，求C1和C2的归结式C12。 解：这里L1=Q，L2=Q，通过归结可以得到 C12= NIL,4.3.2 归结原理,64,例3.7 设C1 =P Q ， C2=Q，C3=P，求C1、C2、C3的 归结式C123。 解：若先对C1、C2归结，可得到 C12=P然后再对C12和C3归结，得到 C123=NIL 如果改变归结顺序，同样可以得到相同的结果，即其归结过程是不唯一的。 其归结过程可用右图来表示，该树称为归结树。,4.3.2 归结原理,65,定理3.2 归结式C12是其亲本子句C1和C2的逻辑结论。 证明：（按定义）设C1=LC1 ，C2=LC2关于解释I为真，则只需证明C12= C1 C2关于解释I也为真。 对于解释I，L和L中必有一个为假。 若L为假，则必有C1为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1为真。 同理，若L为假，则必有C2为真。 因此，必有C12= C1C2关于解释I也为真。即C12是C1和C2的逻辑结论。,4.3.2 归结原理,66,上述定理是归结原理中的一个重要定理，由它可得到以下两个推论：推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即： S1的不可满足性 S的不可满足性推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即： S2的不可满足性S的不可满足性,4.3.2 归结原理,67,上述两个推论说明，为证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入到子句集S中，或者用归结式代替他的亲本子句，然后对新的子句集证明其不可满足性就可以了。如果经归结能得到空子句，根据空子句的不可满足性，即可得到原子句集S是不可满足的结论。在命题逻辑中，对不可满足的子句集S，其归结原理是完备的。这种不可满足性可用如下定理描述：定理3.3 子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。,4.3.2 归结原理,68,二、谓词逻辑的归结原理 在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一对变元进行代换，然后才能进行归结。可见，谓词逻辑的归结要比命题逻辑的归结麻烦一些。谓词逻辑的归结原理 谓词逻辑中的归结式可用如下定义来描述： 定义3.11 设C1和C2是两个没有公共变元的子句，L1和L2分别是C1和C2中的文字。如果L1和L2存在最一般合一，则称 C12=(C1- L1)( C2- L2)为C1和C2的二元归结式，而L1和L2为归结式上的文字。,4.3.2 归结原理,69,例3.8 设C1=P(a)R(x)，C2=P(y)Q(b)，求 C12 解：取L1= P(a), L2=P(y)，则L1和L2的最一般合一是=a/y。根据定义3.20,可得C12=( C1-L1) (C2-L2) =(P(a), R(x)-P(a)(P(a), Q(b)-P(a) =(R(x)(Q(b)= R(x), Q(b) =R(x)Q(b),4.3.2 归结原理,70,例3.9 设C1=P(x)Q(a)，C2=P(b)R(x) ，求 C12 解：由于C1和C2有相同的变元x，不符合定义3.20的要求。为了进行归结，需要修改C2中变元的名字，令C2=P(b)R(y)。此时L1= P(x), L2 =P(b)，L1和L2的最一般合一是=b/x。则有 C12=( C1-L1) (C2-L2) =(P(b), Q(a)-P(b) (P(b), R(y)-P(b) =(Q(a) (R(y)= Q(a), R(y) =Q(a)R(y),4.3.2 归结原理,71,对以上讨论做以下两点说明: (1) 这里之所以使用集合符号和集合的运算，目的是为了说明问题的方便。即先将子句Ci和Li写成集合的形式，在集合表示下做减法和并集运算，然后再写成子句集的形式。 (2) 定义中还要求C1和C2无公共变元，这也是合理的。例如C1=P(x)，C2=P(f(x)，而S= C1, C2是不可满足的。但由于C1和C2的变元相同，就无法合一了。没有归结式，就不能用归结法证明S的不可满足性，这就限制了归结法的使用范围。如果对C1或C2的变元进行换名，便可通过合一，对C1和C2进行归结。如上例，若先对C2进行换名，即C2=P(f(y)，则可对C1和C2进行归结，得到一个空子句，从而证明了S是不可满足的。事实上，在由公式集化为子句集的过程中，最后一步就是做换名处理。因此，定义中假设C1和C2没有相同变元是可以的。,4.3.2 归结原理,72,4.3.3 归结反演,一、 命题逻辑的归结反演 归结原理：假设F为已知前提，G为欲证明的结论，归结原理把证明G为F的逻辑结论转化为证明FG为不可满足。再根据定理3.1，在不可满足的意义上，公式集FG与其子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足。应用归结原理证明定理的过程称为归结反演。 在命题逻辑中，已知F，证明G为真的归结反演过程如下： 否定目标公式G，得G; 把G并入到公式集F中，得到F，G； 把F，G化为子句集S。 应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。,73,例 设已知的公式集为 P, (PQ)R, (ST)Q, T， 求证结论R。 解：假设结论R为假, 将R加入公式集，并化为子句集 S=P,PQR, SQ, TQ, T, R 其归结过程如右图的归结演绎树所示。该树根为空子句。其含义为：先假设子句集S中的所有子句均为真，即原公式集为真,R也为真；然后利用归结原理，对子句集进行归结，并把所得的归结式并入子句集中；重复这一过程，最后归结出了空子句。根据归结原理的完备性，可知子句集S是不可满足的，即开始时假设R为真是错误的，这就证明了R为真。,4.3.3 归结反演,74,4.3.3 归结反演,二、谓词逻辑的归结反演谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比，其步骤基本相同，但每步的处理对象不同。例如，在步骤(3)化简子句集时，谓词逻辑需要把由谓词构成的公式集化为子句集；在步骤(4)按归结原理进行归结时，谓词逻辑的归结原理需要考虑两个亲本子句的最一般合一。,75,4.3.3 归结反演,例 F: (x)(y)(A(x, y)B(y)(y)(C(y)D(x, y)G: (x)C(x)(x)(y)(A(x, y)B(y)证明:G是F的逻辑结论。 先把G否定，并放入F中，得到的F, G为 ( x)( y)(A(x,y)B(y)( y)(C(y)D(x,y), ( x)C(x)( x)( y)(A(x,y) B(y),76,再把F,G化成子句集，得到 (1) A(x,y) B(y) C(f(x) (2) A(u,v) B(v) D(u,f(u) (3) C(z) (4) A(m,n) (5) B(k)其中，(1)、(2)是由F 化出的两个子句， (3)、(4)、(5)是由G化出的3个子句。 最后应用谓词逻辑的归结原理对上述子句集进行归结，其过程为 (6) A(x,y) B(y) 由(1)和(3)归结，取=f(x)/z (7) B(n) 由(4)和(6)归结，取=m/x,n/y (8) NIL 由(5)和(7)归结，取=n/k因此，G是F 的逻辑结论。,4.3.3 归结反演,77,4.3.3 归结反演,上述