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