推理技术-谓词逻辑

,第二级,第三级,第四级,第五级,*,第,4,章 推理技术,第四章 推理技术,4.1,一阶谓词逻辑推理,4.2,归结演绎推理,推理技术概述,推理,是人类求解问题的主要思维方法，即按照某种策略从已有事实和知识推出结论的过程。按思维方式可分,演绎推理,、,归纳推理,、,类比推理,等。,逻辑推理,：按逻辑规则进行的推理。分为：,经典逻辑推理,:,主要指,命题逻辑,和,一阶谓词逻辑,推理，也称,精确推理,或,确定性推理,；,非经典逻辑推理,：主要指除经典逻辑之外，按多值逻辑、模糊逻辑、概率逻辑等的推理，也称为,非精确推理,或,非确定性推理。,逻辑推理举例,经典推理：苏格拉底之死,如何判别谎言？,ABC,三人都喜欢说谎话，偶尔也说真话。某天，,A,指责,B,说谎话，,B,指责,C,说谎话，,C,说,AB,两人都在说谎话。问谁在说谎？,有几条疯狗？,村里有,50,户人家，每家都养了一条狗。现发现村子里面出现了,n,只疯狗，村里规定，谁要是发现了自己的狗是疯狗，就要将自己的狗枪毙。但问题是，村子里面的人只能看出别人家的狗是不是疯狗，而不能看出自己的狗是不是疯的，如果看出别人家的狗是疯狗，也不能告诉别人。于是大家开始观察，第一天晚上，没有枪声，第二天晚上，没有枪声，第三天晚上，枪声响起（具体几枪不清楚），问村子里有几只疯狗？只有晚上才能看出病狗，并且一天晚上只能看一次。,爱因斯坦的世界难题（,1,）,爱因斯坦在,20,世纪初出一个谜语。他说世界上有,98,的人答不出来。,1,、在一条街上，有,5,座房子，喷了,5,种颜色；,2,、每个房里住着不同国籍的人；,3,、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物。,问题是：谁养鱼？,爱因斯坦的世界难题（,2,）,条件是：,1,、英国人住红色房子；,2,、瑞典人养狗；,3,、丹麦人喝茶；,4,、绿色房子在白色房子左面；,5,、绿色房子主人喝咖啡；,6,、抽,PallMall,香烟的人养鸟；,7,、黄色房子主人抽,Dunhill,香烟；,8,、住在中间房子的人喝牛奶；,9,、挪威人住第一间房；,10,、抽,Blends,香烟的人住在养猫的人隔壁,11,、养马的人住抽,Dunhill,香烟的人隔壁；,12,、抽,BlueMaster,的人喝啤；,13,、德国人抽,Prince,香烟；,14,、挪威人住蓝色房子隔壁；,15,、抽,Blends,香烟的人有一个喝水的邻居。,逻辑学与计算机科学,逻辑学：研究思维规律的科学,计算机科学：模拟人脑行为和功能（思维）的科学,思维：大脑、逻辑、语言、计算机,逻辑是知识表示和推理的重要形式和工具,8,逻辑的历史,Aristotle,逻辑学,Leibnitz,数理逻辑： 逻辑,+,数学,Gottlob Frege (1848-1925),一阶谓词演算系统,逻辑是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创建的。用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑。,20,世纪,30,年代，数理逻辑广泛发展，成为数学和计算机科学基础。,逻辑系统,一个逻辑系统是定义语言和它的含义的方法。,逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：,逻辑符号集合,：,在所有该逻辑的逻辑理论中均出现的符号；,非逻辑符号集合,：,不同的逻辑理论中出现的不同的符号；,语句规则,：,定义什么样的符号串是有意义的；,证明,：,什么样的符号串是一个合理的证明；,语义规则,：,定义符号串的语义。,逻辑,程序语言,逻辑符号,保留字或者符号,非逻辑符号,用户自定义的符号,(,变量名，函数名等,),语句规则,构造一个程序的语句规则,语义规则,定义程序做什么的语句规则,推理规则、公理和证明,没有,逻辑与程序语言的对比,1.3,命题逻辑,命题：可以确定其真假的陈述句。,Bolle,提出了布尔代数。,语言,:,原子,Q,、,否定,、,吸取,V,、合取、蕴含,、等价,公式：,AV,B,，,(A,B,A)= ?,公司招聘工作人员，有,M,N,Q,三人应聘，经面试后，公司表示如下想法：（,1,）三人中至少录取一人,;,（,2,）如果录取,M,则一定录取,N,；（,3,）如果录取,N,则一定录取,Q,。,结果如何？,1.4,谓词逻辑,(,一阶逻辑,),谓词逻辑是一种形式语言，具有严密的理论体系，也是一种常用的知识表示方法。,语言,:,，,，,(,，,),；常元，变元，函词，谓词；公式,City,（北京）,City,（上海）,Age,（张三，,23,）,(x)( y)( z) (F(x, y)F(y, z)GF(x, z),）,谓词逻辑中的形式演绎推理,将自然语言中的陈述语句,利用谓词公式表示,利用逻辑等价式,将谓词公式进行变换,利用逻辑蕴含式,推出结论,符号化过程,公式变形,推理过程,表,4.1,常用逻辑等价式,表,4.2,常用逻辑蕴含式,设有前提：,(1),凡是大学生都学过计算机；,(2),小王是大学生。,试问：小王学过计算机吗？,解,令,S(x),：,x,是大学生,;,M(x),：,x,学过计算机,;,a,：小王。,则上面的两个命题可用谓词公式表示为,(1) x(S(x)M(x),(2) S(a),例,下面我们进行形式推理：,(1) x(S(x)M(x),前提,(2)S(a)M(a),(1),US,(3)S(a),前提,(4)M(a),(2),(3),I,3,得结果：,M(a),，即“小王学过计算机”。,这种推理过程完全是一种符号变换过程，很类似于人们用自然语言推理的思维过程，因而称为,自然演绎推理,在语法上，如果存在一个从假设,到,的证明，,则记为,，称,由,可推导出的，或,可证明的,。,如果在没有任何假设下,是可推导出的，则记为,，称,为可证明的。,称一个假设,是,不协调的,，如果存在一个语句,使得,和,的否定均可由,推导得出。,称一个逻辑系统是,一致的,，或,相容的,(,consistent),，,如果不存在逻辑系统的公式,A,，使得,A,与,A,同时成,立。,证 明,(,语法,),语言的,解释,是在某个论域,(domain),中定义非逻辑,符号。语句的语义是在解释下定义出语言,L,的真假值。,如果,I,是,L,的一个解释，且,在,I,中为真，则记为,I,，称作,I,满足,，或者,I,是,的一个,模型,。,类似地，给定一个语句,和一个语句,，如果对,每个解释,I,，有,I,蕴含,I,，换言之，如果,I,是,的一个模型则,I,也是,的一个模型，则记为,，我,们称,为,的一个,逻辑结果,。,解 释,(,语义,),可靠性,(reliable),语法,-,语义,一个逻辑是可靠的，如果它的证明保持真假值，,即在任何解释,I,下，如果,I,是,的模型，且,可由,推导,出，则,I,也是,的一个模型。即，一个逻辑是可靠的，,如果对任何语句集合,和语句,，,蕴涵,。,可靠性和完备性,完备性,(complete),语义,-,语法,一个逻辑是完备的，如果任何永真语句是可证的。,即，对任何语句集合,和语句,，,蕴涵,。,如果一个逻辑是完备的，则该逻辑的证明系统已强到,可以推出任何永真式。,G,del,完备性定理：,一阶逻辑是完备的,可判定的,一个逻辑称为是,可判定的,(decidable),，如果存在,一个算法对逻辑中的任一公式,A,，可确定,A,是否成,立。否则，称为是,不可判定的,(undecidable),。,如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是,半可判定的,。,可判定性,一阶逻辑是不可判定的，但它是半可判定的。,现代逻辑学与计算机科学、计算语言学和人工智能的关系表,逻 辑 自然语 程序 人工 逻辑 指令与直 数据库 复杂性 智能体 未 来 展 望,言处理 控制 智能 编程 陈式语言 理论 理论 理论,时序逻辑 广泛应用,模态逻辑 非常活跃,算法证明 ,非单调推理 意义重大,概率和模糊 目前主流,直觉主义逻辑 主要替代者,高阶逻辑，,-,演算 更具中心作用,经典逻辑片断 前景诱人,资源和子结构逻辑 ,纤维化和组合逻辑 可自我指称,谬误理论 在适当语境,逻辑动力学 动态逻辑观,论辩理论游戏 前景光明,对象层次,/,元层次 总起中心作用,机制,:,溯因 缺省 相干 逻辑的一部分,与神经网络的联系 极重要，刚开始,时间,-,行动,-,修正模型 一类新模型,加标演绎系统 逻辑学的统一框架,4.2,归结演绎推理,归结演绎推理是基于一种称为归结原理,(,亦称,消解原理,principle of resolution,),的推理规则的推理方法。,归结原理是由鲁滨逊,(J.A.Robinson),于,1965,年首先提出。它是谓词逻辑的一个相当有效的机械化推理方法。,归结原理的出现，被认为是自动推理，特别是定理机器证明领域的重大突破。从理论上解决了定理证明问题。,有关归结演绎推理的定义,文字,子句,空子句,子句集,Skolem,函数,Skolem,常量,互补文字,归结,，又称,消解,(resolution),定义,1,原子谓词公式及其否定称为,文字,，,若干个文字的一个析取式称为一个,子句,不含任何文字的子句称为,空子句（真值为假）,，记为,NIL,。,例如下面的析取式都是子句,PQ,乛,R,P(x,y),乛,Q(x),定义,2,对一个谓词公式,G,，通过以下步骤所得的子句集合,S,，称为,G,的,子句集,。,(1),消去蕴含词和等值词。可使用逻辑等价式,:,AB,乛,AB,A B (,乛,AB)(,乛,BA),(2),缩小否定词的作用范围，直到其仅作用于原子公式。可使用逻辑等价式,:,乛,(,乛,A) A,乛,(AB),乛,A,乛,B,将一个谓词公式转换为子句集,乛,(AB),乛,A,乛,B,乛,xP(x) x,乛,P(x),乛,xP(x) x,乛,P(x),(3),适当改名，使量词间不含同名自由变元和约束变元。,(4),消去存在量词。,消去存在量词时，同时还要进行变元替换。变元替换分两种情况：,若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为,Skolem,函数；,若该存在量词不在任何全称量词的辖域内，则用一个常量符号代替该存在量词辖域中的相应约束变元，这样的常量符号称为,Skolem,常量,。,x y P(x,y),根据步骤,4,转换为,x P(x,g(x),这里,y=g(x),为,Skolem,函数,。,xP(x),根据步骤,4,转换为,P(a),这里,a,为,Skolem,常量,Skolem,函数举例,(5),消去所有全称量词。,(6),化公式为合取范式。,可使用逻辑等价式,:,A(BC) (AB)(AC),(AB)C (AC)(BC),(7),适当改名，使子句间无同名变元。,(8),消去合取词，以子句为元素组成一个集合,S,。,(A,B),(C,D),1.,消去,(A,B),(C,D),转换子句集举例,(A,B),(C,D),1.,消去,(A,B),(C,D),2.,缩减,作用范围,(,A,B),(C,D),转换子句集举例,(A,B),(C,D),1.,消去,(A,B),(C,D),2.,缩减,作用范围,(,A,B),(C,D),3.,化公式为合取范式,(,A,(C,D),(B,(C,D),(,A,C),(,A,D),(B,C),(B,D),转换子句集举例,(A,B),(C,D),1.,消去,(A,B),(C,D),2.,缩减,作用范围,(,A,B),(C,D),3.,化公式为合取范式,(,A,(C,D),(B,(C,D),(,A,C),(,A,D),(B,C),(B,D),子句集,:,A,C,A,D , B,C , B,D,谓词公式转换子句集举例,定义,3,：若,P,是原子谓词公式，则,P,与乛,P,为,互补文字,定义,4,：设,C1,与,C2,是子句集中的任意两个基子句，如果,C1,中的文字,L1,与,C2,中的文字,L2,互补，那么,C1,和,C2,中分别消去,L1,和,L2,，并将两个子句余下的部分析取，构成一个新子句,C,12,，则称此过程为,归结，又称消解（,resolution,）。,称,C,12,为基子句,C1,和,C2,的,归结式。,称,C1,和,C2,为,C,12,的,亲本子句,。,例,3.9,设,C,1,=,乛,PQR, C,2,=,乛,QS,于是,C,1,C,2,的归结式为,乛,PRS,归结（消解）定义,子句集的特点,由谓词公式转化为子句集的过程中可以看出，在子句集中子句之间是合取关系。,其中只要有一个子句不可满足,(,真值为假），则子句集就不可满足。,若一个子句集中包含空子句，则这个子句集一定是不可满足的。,由归结原理可知：,如果两个互否的单元子句进行归结，则归结式为空子句,即,:,L,L= ,同时，,L,L= F(,假）,因此 ,F,因此，可以通过推导空子句来做间接证明。,一旦推出了空子句，就说明子句集,S,是不可满足的,归结反演证明步骤,第一步：化子句集,（,1,）将定理证明的前提谓词公式转换为子句集,F,(2),将要求证明的目标表示成谓词公式,G(,目标公式）,（,3,）将目标公式的,否定式,乛,G,转化成子句的形式，并加入到子句集,F,得到子句集,S,。,第二步：归结反演,应用归结原理对子句集,S,中的子句进行归结，并把每次归结的归结式都并入到,S,中。如此反复进行，若归结得到一个空子句,NIL,，则停止归结，此时证明了,G,为真。,归结原理证明定理思路,用归结原理证明定理有些类似于“反证法”的思想。,反证法：,首先假定要证明的结论不成立,然后通过推导出与已知条件存在矛盾,反证出结论成立。,归结法：,首先对结论求反，,然后将已知条件和结论的否定合在一起,用子 句集表达。,如果该子句集存在矛盾，则证明了结论的,正确性。,2,命题逻辑的归结,命题逻辑,，简单的说，就是不含有变量的逻辑。,归结式,：对任意两个子句,C1,和,C2,，若,C1,中有一个文字,L1,，而,C2,中有一个与,L1,成互补的文字,L2,，则分别从,C1,、,C2,中删去,L1,和,L2,，并将其剩余部分组成新的析取式,C12,，则称这个新子句为归结式或预解式。,命题逻辑的归结过程,命题逻辑中，若给定公理集,F,和命题,P,，则归结证明过程可归纳如下：把,F,转化成子句集表示，得子句集,S,0,；把命题,P,的否定式,P,也转化成子句集表示，并将其加到,S,0,中，得,S,S,0,Sp,；对子句集,S,反复应用归结推理规则，直至导出含有空子句的扩大子句集为止。即出现归结式为空子句的情况时，表明已找到了矛盾，证明过程结束。,例 证明子句集,P,乛,Q,乛,P,Q,是不可满足的。,证,(1)P,乛,Q,(2),乛,P,(3)Q,(4),乛,Q,由,(1),(2),(5),由,(3),(4),基于命题逻辑的归结举例,P,乛,Q,乛,P,乛,Q,Q,例 用归结原理证明,R,是,P, (PQ)R, (SU)Q, U,的逻辑结果。,证明步骤,第一步将问题转换为子句集。,我们先把诸前提条件化为子句形式，再把结论,R,的非乛,R,也化为子句，由所有子句得到子句集,S,将,P, (PQ)R, (SU)Q, U,化为子句集形式：,(PQ)R,乛,(PQ) R,(,乛,P ,乛,Q) R,乛,P ,乛,QR,(SU)Q,(1),乛,(S U) Q,(2) (,乛,S ,乛,U) Q,(3) (,乛,SQ) (,乛,UQ),子句集：,P,乛,P ,乛,QR,乛,SQ ,乛,UQ, U,乛,R,第二步：然后对该子句集,S,进行归结。,如果从子句集,S,最后归结出空子句，则子句集,S,不可满足，从而间接证明,R,是真。,P,乛,P,乛,QR,乛,SQ,乛,UQ,U,乛,R,乛,P ,乛,Q (2),和（,6,）,乛,Q (1),和（,7,）,乛,U (4),和,(8), (5),和,(9),子句集,图,31,例,3.12,归结演绎树,在一阶谓词逻辑中应用消解原理，不像命题逻辑中那样简单，因为谓词逻辑中谓词具有常量、变量和函数等变元的存在，这就使寻找含互否文字的子句对的操作变得复杂。例如：,C,1,=P(x)Q(x),C,2,=,乛,P(a)R(y),直接比较，似乎两者中不含互否文字，但如果我们用,a,替换,C1,中的,x,，则得到,C,1,=P(a)Q(a),C,2,=,乛,P(a)R(y),于是根据命题逻辑中的消解原理，得,C,1,和,C,2,的消解式：,C,3,=Q(a)R(y) ,谓词逻辑的归结,合一（,Unify,）,在谓词逻辑的归结过程中，寻找项之间合适的变量置换使表达式一致是一个很重要的过程，这个过程称为,合一,。,定义,6,一个替换,(Substitution),是形如,mgu=,t,1,/x,1,t,2,/x,2,t,n,/x,n,的有限集合，,其中,t,1,t,2,t,n,是项，称为,替换的分子,；,x,1,x,2,x,n,是互不相同的个体变元，称为,替换的分母,；,替换,(Substitution),C,1,=P(x)Q(x),C,2,=,乛,P(a)R(y),做替换：,mgu=a/x,C,1,=P(a)Q(a),C,2,=,乛,P(a)R(y),于是根据命题逻辑中的消解原理，得,C,1,和,C,2,的消解式：,C,3,=Q(a)R(y),例,3.21,求证,G,是,A,1,和,A,2,的逻辑结果。,A,1,: x(P(x)(Q(x)R(x),A,2,: x(P(x)S(x),G: x(S(x)R(x),证 我们用反证法，即证明,A1A2,乛,G,不可满足。首先求得子句集,S,：,(1),乛,P(x)Q(x),(2),乛,P(y)R(y),(3)P(a),(4)S(a),(5),乛,S(z),乛,R(z) (,乛,G) ,然后应用消解原理，得,(6)R(a),(2),(3),mgu=,a/y,(7),乛,R(a),(4),(5),mgu=,a/z,(8),(6),(7),所以,S,是不可满足的，从而,G,是,A,1,和,A,2,的逻辑结果。,(A,1,),(A,2,),S,例 设已知：,(1),能阅读者是识字的；,(2),海豚不识字；,(3),有些海豚是很聪明的。,试证明：有些聪明并不能阅读。,证 首先，定义如下谓词：,R(x),：,x,能阅读。,L(x),：,x,识字。,I(x),：,x,是聪明的。,D(x),：,x,是海豚。,然后把上述各语句翻译为谓词公式：,(1) x(R(x)L(x),(2) x(D(x),乛,L(x),已知条件,(3) x(D(x)I(x),(4) x(I(x),乛,R(x),需证结论,求题设与结论否定的子句集，得,(1),乛,R(x)L(x),(2),乛,D(y),乛,L(y),(3)D(a),(4)I(a),(5),乛,I(z)R(z),归结得,(6) R(a) (5),，,(4),，,a/z,(7) L (a) (6),，,(1),，,a/x,(8),乛,D(a) (7), (2), a/y,(9) (8), (3),这个归结过程的演绎树如图,32,所示。,图,3-2,例,3.22,归结演绎树,练习,1,证明子句集,P,乛,Q,乛,P, Q,是不可满足的。,练习,2,某公司招聘工作人员，有,A,B,C,三人应聘，经面试后，公司表示如下想法：,（,1,）三人中至少录取一人,（,2,）如果录取,A,而不录取,B,则一定录取,C,（,3,）如果录取,B,则一定录取,C,试用归结原理求证：公司一定录取,C,第一步：将问题用谓词公式表示,前提：,（,1,）三人中至少录取一人,：,A, B C,（,2,）如果录取,A,而不录取,B,则一定录取,C,：,(A,乛,B)C,（,3,）如果录取,B,则一定录取,C,：,BC,结论：公司一定录取,C C,第二步：将谓词公式转化为子句集，并将结论的否定化为子句，也加入子句集,（,1,）,A, B C,（,2,）,(A,乛,B)C,乛,(A,乛,B) C,乛,A BC,(3) BC,乛,B C,(4),乛,C,子句集：,A, B C,，乛,A BC,，乛,B C,，乛,C,第三步 证明子句集是不可满足的,（,1,）,A, B C,（,2,）乛,A BC,(3),乛,B C,(4),乛,C,(5) B C,由（,1,）（,2,）,(6) C,由,(5) (3),(7) ,由（,4,）（,6,）,课堂练习,问题,1,：设已知公理集为,P,（,1,）（,PQ,）,R,（,2,）（,ST,）,Q,（,3,）,T,（,4,）求证,R,。,由（,1,）有子句集,P,；由（,2,）有： （,PQ,）,R,(PQ)R, (,P,QR),得子句集：,P,QR,由（,3,）有：,(ST)Q,(ST)Q, (,S,T)Q, (,SQ)(,TQ),得子句集：,SQ,TQ,由（,4,）有子句集：,(T),。由结论的否定得子句集：,R,将以上子句集并在一起有总的子句集：,P,，,PQR,，,SQ,，,TQ,，,T,，,R,命题逻辑的归结演绎树,一个经典的归结问题,例,“快乐学生”问题,假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。,求证：张是快乐的。,解：,先定义谓词：,Pass(x, y) x,可以通过,y,考试,Win(x, prize) x,能获得奖励,Study(x) x,肯学习,Happy(x) x,是快乐的,Lucky(x) x,是幸运的,再将问题用谓词表示如下：,“任何通过计算机考试并奖的人都是快乐的”,(,x)(Pass(x, computer)Win(x, prize),Happy(x),“,任何肯学习或幸运的人都可以通过所有考试”,(,x) (,y) (Study(x)Lucky(x)Pass(x, y),“,张不肯学习但他是幸运的”,Study(zhang)Lucky(zhang),“,任何幸运的人都能获奖”,(,x) (Lucky(x)Win(x, prize),结论“张是快乐的”的否定,Happy(zhang),将上述谓词公式转化为子句集如下：,(1) Pass(x, computer)Win(x, prize),Happy(x),(2) Study(y)Pass(y, z),(3) Lucky(u)Pass(u, v),(4) Study(zhang),(5) Lucky(zhang),(6) Lucky(w)Win(w, prize),(7) Happy(zhang) (,结论的否定,),Exciting(Liming),Happy(z),Exciting(z),Happy(Liming),Happy(x)Smart(x),Happy(x),Poor(Liming),Smart(Liming),Read(y),Smart(y ),Poor(Liming),Read(Liming),Poor(Liming),Read(Liming),Read(Liming),NIL,Liming/z,Liming/x,Liming/y,归结演绎推理的归结策略,广度优先,是一种穷尽子句比较的复杂搜索方法。设初始子句集为,S,0,，广度优先策略的归结过程可描述如下：,(1),从,S,0,出发，对,S,0,中的全部子句作所有可能的归结，得到第一层归结式，把这些归结式的集合记为,S,1,;,(2),用,S,0,中的子句与,S,1,中的子句进行所有可能的归结，得到第二层归结式，把这些归结式的集合记为,S,2,;,(3),用,S,0,和,S,1,中的子句与,S,2,中的子句进行所有可能的归结，得到第三层归结式，把这些归结式的集合记为,S,3,;,如此继续，知道得出空子句或不能再继续归结为止。,例,设有如下子句集：,S=I(x)R(x), I(a), R(y)L(y), L(a) ,用宽度优先策略证明,S,为不可满足。,宽度优先策略的归结树如下：,归结演绎推理的归结策略,1.,广度优先策略（,2/3,）,I(x)R(x),I(a),R(y)L(y),L(a),R(a),I(x) L(x),R(a),L(a),L(a),I(a),I(a),NIL,S,S1,S2,归结演绎推理的归结策略,1.,广度优先策略（,3/3,）,从这个例子可以看出，宽度优先策略归结出了许多无用的子句，既浪费事间，又浪费空间。但是，这种策略由一个有趣的特性，就是当问题有解时保证,能找到最短归结路径,。,因此，它,是一种完备,的归结策略。宽度优先对大问题的归结容易产生组合爆炸，但对小问题却仍是一种比较好的归结策略。,归结演绎推理的归结策略,2.,支持集策略（,1/3,）,支持集策略是沃斯,(Wos),等人在,1965,年提出的一种归结策略。,它要求每一次参加归结的两个亲本子句中，至少应该有一个是由目标公式的否定所得到的子句或它们的后裔。,可以证明支持集策略是,完备的,，即当子句集为不可满足时，则由支持集策略一定能够归结出一个空子句。也可以把支持集策略看成是在宽度优先策略中引入了某种限制条件，这种限制条件代表一种启发信息，因而有较高的效率,例,设有如下子句集：,S=I(x)R(x), I(a), R(y)L(y), L(a) ,其中，,I(x)R(x),为目标公式的否定。用支持集策略证明,S,为不可满足。,归结演绎推理的归结策略,2.,支持集策略（,2/3,）,I(x)R(x),I(a), R(y)L(y),L(a),R(a),I(x)L(x),L(a),L(a),I(a),NIL,归结演绎推理的归结策略,2.,支持集策略（,3/3,）,从上述归结过程可以看出，各级归结式数目要比宽度优先策略生成的少，但在第二级还没有空子句。就是说这种策略限制了子句集元素的剧增，但,会增加空子句所在的深度,。此外，支持集策略,具有逆向推理的含义,，由于进行归结的亲本子句中至少有一个与目标子句有关，因此推理过程可以看作是沿目标、子目标的方向前进的,。,归结演绎推理的归结策略,3.,删除策略（,2/2,）,重言式删除法,如果一个子句中,包含有互补的文字对,，则称该子句为,重言式,。例如,P(x)P(x), P(x)Q(x)P(x),都是重言式，不管,P(x),的真值为真还是为假，,P(x)P(x),和,P(x)Q(x)P(x),都均为真。,重言式是真值为真的子句。对一个子句集来说，不管是增加还是删除一个真值为真的子句，都不会影响该子句集的不可满足性。因此，可从子句集中删去重言式。,归结演绎推理的归结策略,4.,单文字子句策略（,1/2,）,如果一个子句,只包含一个文字,，则称此子句为单文字子句。单文字子句策略是对支持集策略的进一步改进，它要求每次参加归结的两个亲本子句中至少有一个子句是单文字子句。,例,设有如下子句集：,S=I(x)R(x), I(a), R(y)L(y), L(a) ,用单文字子句策略证明,S,为不可满足。,采用单文字子句策略，归结式包含的文字数将少于其亲本子句中的文字数，这将有利于向空子句的方向发展，因此会,有较高的归结效率。但这种策略是不完备的,，即当子句集为不可满足时，用这种策略不一定能归结出空子句。,归结演绎推理的归结策略,4.,单文字子句策略（,2/2,）,I(x)R(x),I(a),R(y)L(y),L(a),R(a),R(a),NIL,归结演绎推理的归结策略,5.,线形输入策略（,1/2,）,这种策略要求每次参加归结的两个亲本子句中，,至少应该有一个是初始子句集中的子句,。所谓初始子句集是指开始归结时所使用的子句集。,例,设有如下子句集：,S=I(x)R(x), I(a), R(y)L(y), L(a) ,用线性输入策略证明,S,为不可满足。,线性输入策略可限制生成归结式的数目，,具有简单和高效的优点。但是，这种策略,也是一种不完备的策略,。例如，子句集,S=Q(u)P(a), Q(w)P(w), Q(x) P(x), Q(y) P(y),从,S,出发很容易找到一棵归结反演树，但却不存在线性输入策略的归结反演树。,归结演绎推理的归结策略,5.,线形输入策略（,2/2,）,I(x)R(x),I(a),R(y)L(y),L(a),R(a),I(x)L(x), R(a),I(a),L(a),L(a),I(a),NIL,归结演绎推理的归结策略,6.,祖先过滤策略（,1/2,）,这种策略与线性输入策略有点相似，但是，放宽了对子句的限制。每次参加归结的两个亲本子句，只要,满足以下两个条件中的任意一个,就可进行归结：,(1),两个亲本子句中至少有一个是初始子句集中的子句。,(2),如果两个亲本子句都不是初始子句集中的子句，则一个子句应该是另一个子句的先辈子句。所谓一个子句,(,例如,C,1,),是另一个子句,(,例如,C,2,),的先辈子句是指,C,2,是由,C,1,与别的子句归结后得到的归结式。,例,设有如下子句集：,S=,Q(x),P(x), Q(y),P(y),，,Q(w)P(w) , Q(a)P(a) ,用祖先过滤策略证明,S,为不可满足。,可以证明祖先过滤策略也,是完备的,。,上面分别讨论了几种基本的归结策略，但在实际应用中，还可以把几种策略结合起来使用。总之，在选择归结反演策略时，主要应考虑其完备性和效率问题。,归结演绎推理的归结策略,6.,祖先过滤策略（,2/2,）,Q(x) P(x),Q(y)P(y), P(x), Q(w)P(w), Q(w),Q(a)P(a),P(a),NIL,作 业,1,判断以下子句是否为不可满足,P(x)Q(x )R(x), P(y)R(y), Q(a), R(b),2,证明,G,是,F,的逻辑结论,F: (,x)(,y)(P,(f(x)(Q(f(y),G: P(f(a),P(y)Q(y),3,公司招聘工作人员，有,M,N,Q,三人应聘，经面试后，公司表示如下想法：（,1,）三人中至少录取一人,;,（,2,）如果录取,M,则一定录取,N,；（,3,）如果录取,N,则一定录取,Q,。试用归结反演方法求证：公司一定录取,Q,。,4,设谓词,S(p,q),表示“,p,为,q,刮胡子”。假设论域为人。,（,1),请用谓词语句描述“有一个人,P,只为每个不给自己刮胡子的人刮胡子”。,（,2,）将（,1,）中语句转换为子句形式。,（,3,）用归结法证明（,2,）本身不一致（或不可满足,),。,