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

1、第四章 推理技术 4.1 一阶谓词逻辑推理4.2 归结演绎推理推理技术概述推理是人类求解问题的主要思维方法，即按照某种策略从已有事实和知识推出结论的过程。按思维方式可分演绎推理、归纳推理、类比推理等。逻辑推理：按逻辑规则进行的推理。分为： 经典逻辑推理 :主要指命题逻辑和一阶谓词逻辑推理，也称精确推理或确定性推理； 非经典逻辑推理：主要指除经典逻辑之外，按多值逻辑、模糊逻辑、概率逻辑等的推理，也称为非精确推理或非确定性推理。逻辑推理举例 经典推理：苏格拉底之死 如何判别谎言？ ABC三人都喜欢说谎话，偶尔也说真话。某天，A指责B说谎话，B指责C说谎话，C说AB两人都在说谎话。问谁在说谎？ 有几

2、条疯狗？ 村里有50户人家，每家都养了一条狗。现发现村子里面出现了n只疯狗，村里规定，谁要是发现了自己的狗是疯狗，就要将自己的狗枪毙。但问题是，村子里面的人只能看出别人家的狗是不是疯狗，而不能看出自己的狗是不是疯的，如果看出别人家的狗是疯狗，也不能告诉别人。于是大家开始观察，第一天晚上，没有枪声，第二天晚上，没有枪声，第三天晚上，枪声响起（具体几枪不清楚），问村子里有几只疯狗？只有晚上才能看出病狗，并且一天晚上只能看一次。 爱因斯坦的世界难题（1）爱因斯坦在20世纪初出一个谜语。他说世界上有98的人答不出来。1、在一条街上，有5座房子，喷了5种颜色；2、每个房里住着不同国籍的人；3、每个人喝不

3、同的饮料，抽不同品牌的香烟，养不同的宠物。 问题是：谁养鱼？ 爱因斯坦的世界难题（2）条件是：1、英国人住红色房子； 2、瑞典人养狗；3、丹麦人喝茶；4、绿色房子在白色房子左面；5、绿色房子主人喝咖啡；6、抽PallMall香烟的人养鸟；7、黄色房子主人抽Dunhill香烟；8、住在中间房子的人喝牛奶；9、挪威人住第一间房；10、抽Blends香烟的人住在养猫的人隔壁11、养马的人住抽Dunhill香烟的人隔壁；12、抽BlueMaster的人喝啤；13、德国人抽Prince香烟；14、挪威人住蓝色房子隔壁；15、抽Blends香烟的人有一个喝水的邻居。逻辑学与计算机科学逻辑学：研究思维规律的

4、科学计算机科学：模拟人脑行为和功能（思维）的科学思维：大脑、逻辑、语言、计算机逻辑是知识表示和推理的重要形式和工具8逻辑的历史Aristotle逻辑学Leibnitz数理逻辑： 逻辑+数学Gottlob Frege (1848-1925)一阶谓词演算系统 逻辑是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创建的。用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑。 20世纪30年代，数理逻辑广泛发展，成为数学和计算机科学基础。逻辑系统一个逻辑系统是定义语言和它的含义的方法。逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：逻辑符号集合：在所有

5、该逻辑的逻辑理论中均出现的符号；非逻辑符号集合：不同的逻辑理论中出现的不同的符号；语句规则：定义什么样的符号串是有意义的；证明：什么样的符号串是一个合理的证明；语义规则：定义符号串的语义。逻辑程序语言逻辑符号保留字或者符号非逻辑符号用户自定义的符号(变量名，函数名等)语句规则构造一个程序的语句规则语义规则定义程序做什么的语句规则推理规则、公理和证明没有逻辑与程序语言的对比1.3 命题逻辑命题：可以确定其真假的陈述句。Bolle提出了布尔代数。语言:原子Q、否定、吸取V、合取、蕴含 、等价公式：AVB， (AB,A)= ? 公司招聘工作人员，有M,N,Q三人应聘，经面试后，公司表示如下想法：（1

6、）三人中至少录取一人;（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)凡是大学生都学过计算机

7、； (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)，即“小王学过计算机”。 这种推理过程完全是一种符号变换过程，很类似于人们用自然语言推理的思维过程，因而称为自然演绎推理 在语法上，如果存在一个从假设到的证明，则记为 ，称由可推导出的，或可证明的。如果在没有任何假设下是

8、可推导出的，则记为 ，称为可证明的。 称一个假设是不协调的，如果存在一个语句使得和的否定均可由推导得出。 称一个逻辑系统是一致的，或相容的(consistent)，如果不存在逻辑系统的公式A，使得A与A同时成立。证 明(语法) 语言的解释是在某个论域(domain)中定义非逻辑符号。语句的语义是在解释下定义出语言L的真假值。如果I是L的一个解释，且在I中为真，则记为I ，称作I满足 ，或者I 是的一个模型。 类似地，给定一个语句和一个语句 ，如果对每个解释I ，有I 蕴含I ，换言之，如果I 是的一个模型则I也是的一个模型，则记为 ，我们称为的一个逻辑结果。解 释(语义)可靠性(reliabl

9、e) 语法-语义一个逻辑是可靠的，如果它的证明保持真假值，即在任何解释I下，如果I是 的模型，且可由推导出，则I也是的一个模型。即，一个逻辑是可靠的，如果对任何语句集合和语句 ， 蕴涵 。可靠性和完备性完备性(complete) 语义-语法一个逻辑是完备的，如果任何永真语句是可证的。即，对任何语句集合和语句 ， 蕴涵 。如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。Gdel完备性定理：一阶逻辑是完备的可判定的一个逻辑称为是可判定的(decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定 A是否成立。否则，称为是不可判定的(undecidable) 。如果上述算

10、法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。可判定性一阶逻辑是不可判定的，但它是半可判定的。 现代逻辑学与计算机科学、计算语言学和人工智能的关系表 逻 辑 自然语 程序 人工 逻辑 指令与直 数据库 复杂性 智能体 未 来 展 望 言处理 控制 智能 编程 陈式语言 理论 理论 理论时序逻辑 广泛应用模态逻辑 非常活跃算法证明 非单调推理 意义重大概率和模糊 目前主流直觉主义逻辑 主要替代者高阶逻辑，-演算 更具中心作用经典逻辑片断 前景诱人资源和子结构逻辑 纤维化和组合逻辑 可自我指称谬误理论 在适当

11、语境逻辑动力学 动态逻辑观论辩理论游戏 前景光明对象层次/元层次 总起中心作用机制:溯因 缺省 相干 逻辑的一部分与神经网络的联系 极重要，刚开始时间-行动-修正模型 一类新模型加标演绎系统 逻辑学的统一框架4.2 归结演绎推理 归结演绎推理是基于一种称为归结原理(亦称消解原理 principle of resolution)的推理规则的推理方法。 归结原理是由鲁滨逊(J.A.Robinson)于1965年首先提出。它是谓词逻辑的一个相当有效的机械化推理方法。 归结原理的出现，被认为是自动推理，特别是定理机器证明领域的重大突破。从理论上解决了定理证明问题。 有关归结演绎推理的定义文字子句空子句

12、子句集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乛

13、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), 这

14、里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

15、)(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，则称此过程为归结，又称消解（resolu

16、tion）。称C12为基子句C1和C2的归结式。称C1和C2为C12的亲本子句。例3.9 设C1=乛PQR, C2=乛QS,于是C1,C2的归结式为 乛PRS归结（消解）定义子句集的特点 由谓词公式转化为子句集的过程中可以看出，在子句集中子句之间是合取关系。 其中只要有一个子句不可满足(真值为假），则子句集就不可满足。 若一个子句集中包含空子句，则这个子句集一定是不可满足的。由归结原理可知：如果两个互否的单元子句进行归结，则归结式为空子句即: L L= 同时， L L= F(假）因此 F因此，可以通过推导空子句来做间接证明。一旦推出了空子句，就说明子句集S是不可满足的归结反演证明步骤第一步：化

17、子句集（1）将定理证明的前提谓词公式转换为子句集F (2) 将要求证明的目标表示成谓词公式G(目标公式）（3）将目标公式的否定式乛G转化成子句的形式，并加入到子句集F,得到子句集S。第二步：归结反演 应用归结原理对子句集S中的子句进行归结，并把每次归结的归结式都并入到S中。如此反复进行，若归结得到一个空子句NIL，则停止归结，此时证明了G为真。归结原理证明定理思路 用归结原理证明定理有些类似于“反证法”的思想。反证法：首先假定要证明的结论不成立 然后通过推导出与已知条件存在矛盾 反证出结论成立。 归结法：首先对结论求反， 然后将已知条件和结论的否定合在一起 用子 句集表达。 如果该子句集存在矛

18、盾，则证明了结论的 正确性。2命题逻辑的归结 命题逻辑，简单的说，就是不含有变量的逻辑。 归结式：对任意两个子句C1和C2，若C1中有一个文字L1，而C2中有一个与L1成互补的文字L2，则分别从C1、C2中删去L1和L2，并将其剩余部分组成新的析取式C12，则称这个新子句为归结式或预解式。 命题逻辑的归结过程命题逻辑中，若给定公理集F和命题P，则归结证明过程可归纳如下：把F转化成子句集表示，得子句集S0；把命题P的否定式P也转化成子句集表示，并将其加到S0中，得SS0Sp；对子句集S反复应用归结推理规则，直至导出含有空子句的扩大子句集为止。即出现归结式为空子句的情况时，表明已找到了矛盾，证明过

19、程结束。 例 证明子句集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乛P 乛QR(SU)Q(1)乛(S U) Q(2) (乛S 乛U) Q(3) (乛SQ) (乛UQ)子句集：P,乛P 乛QR

20、, 乛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=

21、乛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)于是根据命题

22、逻辑中的消解原理，得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例

23、 设已知：(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

24、(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第二步：将谓词

25、公式转化为子句集，并将结论的否定化为子句，也加入子句集（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

26、(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是幸运的再将问题用谓词表示如下： “任何通过计算机考试并

27、奖的人都是快乐的” (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) (

28、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/x

29、Liming/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) 用宽度优

30、先策略证明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） 支

31、持集策略是沃斯(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(

32、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)的真

33、值为真还是为假，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. 线形输入策