第四章推理技术谓词逻辑ppt课件

第四章第四章 推理技术推理技术 4.1 一阶谓词逻辑推理一阶谓词逻辑推理4.2 归结演绎推理归结演绎推理推理技术概述推理技术概述n推理推理是人类求解问题的主要思维方法，即按照某种策略从已有事是人类求解问题的主要思维方法，即按照某种策略从已有事实和知识推出结论的过程。按思维方式可分实和知识推出结论的过程。按思维方式可分演绎推理演绎推理、归纳推理归纳推理、类比推理类比推理等。等。n逻辑推理逻辑推理：按逻辑规则进行的推理。分为：按逻辑规则进行的推理。分为：经典逻辑推理经典逻辑推理:主要指主要指命题逻辑命题逻辑和和一阶谓词逻辑一阶谓词逻辑推理，也称推理，也称精确推理精确推理或或确确定性推理定性推理；非经典逻辑推理非经典逻辑推理：主要指除经典逻辑之外，按多值逻辑、模糊逻辑、概：主要指除经典逻辑之外，按多值逻辑、模糊逻辑、概率逻辑等的推理，也称为率逻辑等的推理，也称为非精确推理非精确推理或或非确定性推理。非确定性推理。逻辑推理举例逻辑推理举例 经典推理：苏格拉底之死 如何判别谎言？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、合取、蕴含、等价公式：AVB，(AB,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),I3 得结果：得结果：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 Gdeldel完备性定理：完备性定理：一阶逻辑是完备的一阶逻辑是完备的可判定的可判定的一个逻辑称为是可判定的可判定的(decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定 A是否成立。否则，称为是不可判定的不可判定的(undecidable)。如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的半可判定的。可判定性一阶逻辑是不可判定的，但它是半可判定的。一阶逻辑是不可判定的，但它是半可判定的。现代逻辑学与计算机科学、计算语言学和人工智能的关系表现代逻辑学与计算机科学、计算语言学和人工智能的关系表 逻逻 辑辑 自然语自然语 程序程序 人工人工 逻辑逻辑 指令与直指令与直 数据库数据库 复杂性复杂性 智能体智能体 未未 来来 展展 望望 言处理言处理 控制控制 智能智能 编程编程 陈式语言陈式语言 理论理论 理论理论 理论理论时序逻辑时序逻辑 广泛应用广泛应用模态逻辑模态逻辑 非常活跃非常活跃算法证明算法证明 非单调推理非单调推理 意义重大意义重大概率和模糊概率和模糊 目前主流目前主流直觉主义逻辑直觉主义逻辑 主要替代者主要替代者高阶逻辑，高阶逻辑，-演算演算 更具中心作用更具中心作用经典逻辑片断经典逻辑片断 前景诱人前景诱人资源和子结构逻辑资源和子结构逻辑 纤维化和组合逻辑纤维化和组合逻辑 可自我指称可自我指称谬误理论谬误理论 在适当语境在适当语境逻辑动力学逻辑动力学 动态逻辑观动态逻辑观论辩理论游戏论辩理论游戏 前景光明前景光明对象层次对象层次/元层次元层次 总起中心作用总起中心作用机制机制:溯因溯因 缺省缺省 相干相干 逻辑的一部分逻辑的一部分与神经网络的联系与神经网络的联系 极重要，刚开始极重要，刚开始时间时间-行动行动-修正模型修正模型 一类新模型一类新模型加标演绎系统加标演绎系统 逻辑学的统一框架逻辑学的统一框架4.2 归结演绎推理归结演绎推理n 归结演绎推理是基于一种称为归结原理归结演绎推理是基于一种称为归结原理(亦称亦称消解原理消解原理 principle of resolution)的推理规则的推理方法。的推理规则的推理方法。n 归结原理是由鲁滨逊归结原理是由鲁滨逊(J.A.Robinson)于于1965年首先提出。年首先提出。它是谓词逻辑的一个相当有效的机械化推理方法。它是谓词逻辑的一个相当有效的机械化推理方法。n 归结原理的出现，被认为是自动推理，特别是定理机归结原理的出现，被认为是自动推理，特别是定理机器证明领域的重大突破。从理论上解决了定理证明问题。器证明领域的重大突破。从理论上解决了定理证明问题。有关归结演绎推理的定义有关归结演绎推理的定义文字文字子句子句空子句空子句子句集子句集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，并将两个子句余下的部分析取，构成一，并将两个子句余下的部分析取，构成一个新子句个新子句C12，则称此过程为，则称此过程为归结，又称消解归结，又称消解（resolution）。）。称称C12为基子句为基子句C1和和C2的的归结式。归结式。称称C1和和C2为为C12的的亲本子句亲本子句。例例3.9 设设C1=乛乛PQR,C2=乛乛QS,于是于是C1,C2的归结式的归结式为为 乛乛PRS归结（消解）定义归结（消解）定义子句集的特点子句集的特点 n由谓词公式转化为子句集的过程中可以看出，在子句集中子句之间是由谓词公式转化为子句集的过程中可以看出，在子句集中子句之间是合取关系。合取关系。n 其中只要有一个子句不可满足其中只要有一个子句不可满足(真值为假），则子句集就不可满足。真值为假），则子句集就不可满足。n 若一个子句集中包含空子句，则这个子句集一定是不可满足的。若一个子句集中包含空子句，则这个子句集一定是不可满足的。由归结原理可知：由归结原理可知：如果两个互否的单元子句进行归结，则归结式为空子句如果两个互否的单元子句进行归结，则归结式为空子句即即:L L=同时，同时，L L=F(假）假）因此因此 F因此，可以通过推导空子句来做间接证明。因此，可以通过推导空子句来做间接证明。一旦推出了空子句，就说明子句集一旦推出了空子句，就说明子句集S 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转化成子句集表示，得子句集转化成子句集表示，得子句集S0；把命题把命题P的否定式的否定式P也转化成子句集表示，并将其也转化成子句集表示，并将其加到加到S0中，得中，得SS0Sp；对子句集对子句集S反复应用归结推理规则，直至导出含有空反复应用归结推理规则，直至导出含有空子句的扩大子句集为止。即出现归结式为空子句的情子句的扩大子句集为止。即出现归结式为空子句的情况时，表明已找到了矛盾，证明过程结束。况时，表明已找到了矛盾，证明过程结束。例例 证明子句集证明子句集P乛乛Q,乛乛P,Q是不可满足的。是不可满足的。证证(1)P乛乛Q(2)乛乛P(3)Q(4)乛乛Q 由由(1),(2)(5)由由(3),(4)基于命题逻辑的归结举例基于命题逻辑的归结举例P乛乛Q乛乛P乛乛QQ 例例 用归结原理证明用归结原理证明 R 是是 P,(PQ)R,(SU)Q,U 的逻辑结果。的逻辑结果。证明步骤证明步骤第一步将问题转换为子句集。第一步将问题转换为子句集。我们先把诸前提条件化为子句形式，再把结论我们先把诸前提条件化为子句形式，再把结论R的非的非乛乛R也化为子句，由所有子句得到子句集也化为子句，由所有子句得到子句集S将将 P,(PQ)R,(SU)Q,U化为子句集形式：化为子句集形式：(PQ)R乛乛(PQ)R(乛乛P 乛乛Q)R(1)乛乛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乛乛UQU乛乛R乛乛P 乛乛Q (2)和（和（6）乛乛Q (1)和（和（7）乛乛U (4)和和(8)(5)和和(9)子句集图31 例3.12归结演绎树 在一阶谓词逻辑中应用消解原理，不像命题逻辑中那样简单，因在一阶谓词逻辑中应用消解原理，不像命题逻辑中那样简单，因为谓词逻辑中谓词具有常量、变量和函数等变元的存在，这就使为谓词逻辑中谓词具有常量、变量和函数等变元的存在，这就使寻找含互否文字的子句对的操作变得复杂。例如：寻找含互否文字的子句对的操作变得复杂。例如：C1=P(x)Q(x)C2=乛乛P(a)R(y)直接比较，似乎两者中不含互否文字，但如果我们用直接比较，似乎两者中不含互否文字，但如果我们用a替换替换C1中的中的x，则得到，则得到 C1=P(a)Q(a)C2=乛乛P(a)R(y)于是根据命题逻辑中的消解原理，得于是根据命题逻辑中的消解原理，得C1和和C2的消解式：的消解式：C3=Q(a)R(y)谓词逻辑的归结谓词逻辑的归结合一（合一（Unify）在谓词逻辑的归结过程中，寻找项之间合适的变量置在谓词逻辑的归结过程中，寻找项之间合适的变量置换使表达式一致是一个很重要的过程，这个过程称为换使表达式一致是一个很重要的过程，这个过程称为合一合一。定义定义6 一个替换一个替换(Substitution)是形如是形如 mgu=t1/x1,t2/x2,tn/xn的有限集合，的有限集合，其中其中t1,t2,tn是项，称为是项，称为替换的分子替换的分子；x1,x2,xn是互不相同的个体变元，称为是互不相同的个体变元，称为替换的分母替换的分母；替换替换(Substitution)C1=P(x)Q(x)C2=乛乛P(a)R(y)做替换：做替换：mgu=a/x C1=P(a)Q(a)C2=乛乛P(a)R(y)于是根据命题逻辑中的消解原理，得于是根据命题逻辑中的消解原理，得C1和和C2的消解的消解式：式：C3=Q(a)R(y)例例3.21 求证求证G是是A1和和A2的逻辑结果。的逻辑结果。A1:x(P(x)(Q(x)R(x)A2: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是是A1和和A2的逻辑结果。的逻辑结果。(A1)(A2)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(PQR)得子句集：得子句集：PQR由（由（3）有：）有：(ST)Q(ST)Q(ST)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)NILLiming/zLiming/xLiming/y归结演绎推理的归结策略归结演绎推理的归结策略 广度优先广度优先是一种穷尽子句比较的复杂搜索方法。设初始子句集为是一种穷尽子句比较的复杂搜索方法。设初始子句集为S0，广，广度优先策略的归结过程可描述如下：度优先策略的归结过程可描述如下：(1)从从S0出发，对出发，对S0中的全部子句作所有可能的归结，得到第一层归结中的全部子句作所有可能的归结，得到第一层归结式，把这些归结式的集合记为式，把这些归结式的集合记为S1;(2)用用S0中的子句与中的子句与S1中的子句进行所有可能的归结，得到第二层归结中的子句进行所有可能的归结，得到第二层归结式，把这些归结式的集合记为式，把这些归结式的集合记为S2;(3)用用S0和和S1中的子句与中的子句与S2中的子句进行所有可能的归结，得到第三层中的子句进行所有可能的归结，得到第三层归结式，把这些归结式的集合记为归结式，把这些归结式的集合记为S3;如此继续，知道得出空子句或不能再继续归结为止。如此继续，知道得出空子句或不能再继续归结为止。例例 设有如下子句集：设有如下子句集：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)NILSS1S2归结演绎推理的归结策略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)如果两个亲本子句都不是初始子句集中的子句，则一个子句应该是另一个子句如果两个亲本子句都不是初始子句集中的子句，则一个子句应该是另一个子句的先辈子句。所谓一个子句的先辈子句。所谓一个子句(例如例如C1)是另一个子句是另一个子句(例如例如C2)的先辈子句是指的先辈子句是指C2是是由由C1与别的子句归结后得到的归结式。与别的子句归结后得到的归结式。例例 设有如下子句集：设有如下子句集：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）本身不一致（或不可满足）本身不一致（或不可满足)。