离散数学标准讲义sy第2章

1、2020/7/3,离散数学,1,第二章一阶逻辑,2020/7/3,离散数学,2,所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。,2020/7/3,离散数学,3,命题逻辑的局限,符号化：P:所有的人都是要死的。Q:苏格拉底是人，R:所以苏格拉底是要死的。PQR推理正确吗?说明：命题逻辑不能表现出简单命题中各部分的内在联系。,2020/7/3,离散数学,4,本章概要,一阶逻辑，又称一阶谓词逻辑或谓词逻辑。对一阶逻辑的研究能够克服命题逻辑的局限性，对简单命题进行进一步的分解，以表达出个体和总体间的内在联系和数量关系。,2020/7/3,离散数学,5,一阶逻辑知识结构,2.1一阶逻辑基本概念

2、2.2一阶逻辑等值演算2.3一阶逻辑的推理理论,第一、二次课,2020/7/3,离散数学,6,一阶逻辑基本概念知识点,谓词和量词概念一阶逻辑命题的符号化（特性谓词）谓词公式基本概念谓词公式的解释谓词公式的分类,2020/7/3,离散数学,7,谓词和量词,一个简单命题中表示研究对象即主体或客体(对应名词成分)的词称为个体词。表示一个个体词性质的或多个个体词之间关系的词称为谓词。例：小张是学生。小张在跑步。小张比小李高2cm。X是我的同学。,2020/7/3,离散数学,8,谓词和量词,个体词个体常项表示具体的、特指的个体的词用a,b,c表示个体变项表示抽象的、泛指的或在一定范围内变化的个体的词用x

3、,y,z表示个体域个体变项的取值范围全总个体域,2020/7/3,离散数学,9,谓词和量词,谓词谓词常项：表示具体性质或关系的谓词谓词变项：表示抽象的或泛指的性质或关系的谓词用F,G,H表示0元谓词：不包含有个体变项的谓词n元谓词：包含有n个体变项的谓词例：（1）3是整数。（2）x和y具有关系L。（3）小张和小李是同学。,2020/7/3,离散数学,10,全称量词和存在量词,符号化:(1)所有的人都是要死的。(2)有的人活百岁以上。量词：表示个体常项或变项之间数量关系的词全称量词用表示，形成的命题形式为xF(x)，即“对所有的x，F(x)为真”。存在量词用表示，形成的命题形式为xF(x)，即“

4、存在x值，使F(x)为真”。,2020/7/3,离散数学,11,一阶逻辑命题符号化,例：在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡是人都要呼吸.(2)有的人用左手写字.其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域.解答,2020/7/3,离散数学,12,(1)凡是人都要呼吸.解：(a)个体域D1为人类集合(b)个体域D2为全总个体域.为将人从全总个体域中分离出来，令,2020/7/3,离散数学,13,(2)有的人用左手写字.解:(a)个体域D1为人类集合；(b)个体域D2为全总个体域.,2020/7/3,离散数学,14,一阶逻辑命题符号化,例：在个

5、体域限制为(a)和(b)条件时，将下列命题符号化:(1)对于任意的x，均有x2-3x+2=(x-1)(x-2).(2)存在x，使得x+5=3.其中:(a)个体域D1=N(N为自然数集合)(b)个体域D2=R(R为实数集合)解答,2020/7/3,离散数学,15,(1)对于任意的x，均有x2-3x+2=(x-1)(x-2)解：令(a)个体域D1=N(N为自然数集合)命题符号化为：,(b)个体域D2=R(R为实数集合)命题符号化为：,T,T,2020/7/3,离散数学,16,（2）存在x，使得x+5=3.解:令(a)个体域D1=N(N为自然数集合)命题符号化为：,(b)个体域D2=R(R为实数集合

6、)命题符号化为：,F,T,2020/7/3,离散数学,17,一阶逻辑命题符号化,例：将下列命题符号化，并讨论真值.(1)所有的人都长着黑头发.,解：定义特性谓词M(x)：x是人。,定义谓词F(x)：x长着黑头发。,真值：,F,2020/7/3,离散数学,18,(2)有的人登上过月球.,解：定义特性谓词M(x)：x是人。,定义谓词F(x)：x登上过月球。,真值：,T,2020/7/3,离散数学,19,(3)没有人登上过木星.,解：定义特性谓词M(x)：x是人。,定义谓词F(x)：x登上过木星。,真值：,T,2020/7/3,离散数学,20,(4)在美国留学的学生未必都是亚洲人.,解：定义特性谓词

7、M(x)：x是在美国留学的学生。,定义谓词F(x)：x是亚洲人。,真值：,T,2020/7/3,离散数学,21,例：将下列命题符号化。(1)兔子比乌龟跑得快.,解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。,定义谓词H(x,y)：x比y跑得快。,2020/7/3,离散数学,22,(2)有的兔子比所有的乌龟跑得快.,解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。,定义谓词H(x,y)：x比y跑得快。,2020/7/3,离散数学,23,(3)并不是所有的兔子都比乌龟跑得快.,解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。,定义谓词H(x,y)：x比y跑得快。,2020

8、/7/3,离散数学,24,(4)不存在跑得同样快的两只兔子.,解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。,定义谓词L(x,y)：x和y跑得一样快。,2020/7/3,离散数学,25,几点说明：一般说来，多个量词出现时，它们的顺序不能随意调换.有些命题的符号化形式可不止一种.,2020/7/3,离散数学,26,谓词公式知识点,谓词公式指导变元、辖域自由出现、约束出现谓词公式的解释谓词公式的分类,2020/7/3,离散数学,27,定义2.1.1一阶语言的字母表定义如下:,(1)个体常项:a,b,c,ai,bi,ci，i1(2)个体变项:x,y,z,xi,yi,zi，i1(3)函数符号

9、:f,g,h,fi,gi,hi，i1(4)谓词符号:F,G,H,Fi,Gi,Hi，i1(5)量词符号:，(6)联结词符号:,(7)括号与逗号:(,),一阶语言,2020/7/3,离散数学,28,定义2.1.2的项的定义如下:,(3)有限次使用(1)，(2)所得到的符号串都是项.,(1)个体常项和个体变项是项.,(2)若(x1,x2,xn)是任意的n元函数,t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.,2020/7/3,离散数学,29,例:1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式,定义2.1.3原子公式设R(x1,x2,xn)是任意的n元谓词,

10、t1,t2,tn是的任意的n个项，则称R(t1,t2,tn)是的原子公式.,2020/7/3,离散数学,30,定义2.1.4的合式公式定义如下:,(1)原子公式是合式公式.,(2)若A是合式公式，则(A)也是合式公式.,(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式.,(5)只有有限次的应用(1)(4)构成的符号串才是合式公式.,(4)若A是合式公式，则也是合式公式.,合式公式也称为谓词公式，简称公式.,2020/7/3,离散数学,31,定义2.1.5在公式和中，称x为指导变元，A为相应量词的辖域。在和的辖域中,x的所有出现都称为约束出现.A中不是约束出现的其他

11、变项均称为是自由出现的.,自由与约束,2020/7/3,离散数学,32,例指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项:,2020/7/3,离散数学,33,解：(1)x是指导变元.量词的辖域A=(F(x,y)G(x,z)，在A中，x是约束出现的.而且约束出现两次，y和z均为自由出现的，而且各自由出现一次.,2020/7/3,离散数学,34,解：(2)公式中含有两个量词，前件上的量词的指导变元为x，的辖域A=(F(x)G(y)，其中x是约束出现的，y是自由出现的.,后件中的量词的指导变元为y，的辖域为(H(x)L(x,y,z)，其中y是约束出现的，x,z均为自由出现的

12、.,在整个公式中，x约束出现一次，自由出现2次，y自由出现一次，约束出现一次，z只自由出现一次.,2020/7/3,离散数学,35,则x1A(x1,x2,xn)是含有x2,x3,xn自由出现的公式，可记为A1(x2,xn)。,类似的,x2x1A(x1,x2,xn)可记为A2(x3,x4,xn)，xn-1xn-2x1A(x1,x2,xn)中只含有xn是自由出现的个体变项，可以记为An-1(xn)。,而xnx1A(x1,x2,xn)已经没有自由出现的个体变项了。,为方便起见，用A(x1,x2,xn)表示含x1,x2,xn自由出现的公式，并用表示任意的量词(或)。,2020/7/3,离散数学,36,

13、定义2.1.6：设A是任意的公式,若A中不含有自由出现的个体变项，则称A为封闭的公式，简称闭式.,闭公式,要想使含有r(r1)个自由出现个体变项的公式变成闭式，至少要加上r个量词.,闭式,不是闭式,2020/7/3,离散数学,37,换名规则,将量词辖域中的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中没有出现的个体变项符号，公式中的其它部分不变。例：,2020/7/3,离散数学,38,代替规则,对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。例：,2020/7/3,离散数学,39,一阶公式的解释,2020/7/3,离散数学,40,例:将下列两个公式

14、中的变项指定成常项使其成为命题:,(1)x(F(x)G(x)(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y),2020/7/3,离散数学,41,解：(1)指定个体变项的变化范围，并且指定谓词F,G的含义，下面给出两种指定法:,(a)令个体域D1为全总个体域，F(x)为x是人，G(x)为x是黄种人，则表达的命题为“所有人都是黄种人”，这是假命题.,(b)令个体域D2为实数集合R，F(x)为x是自然数，G(x)为x是整数，则表达的命题为“自然数都是整数”,这是真命题.,(1)x(F(x)G(x),2020/7/3,离散数学,42,(2)式中含有函数变项，1元谓词变项，2元谓词

15、变项。指定个体域为全总个体域,F(x)为x是实数,G(x,y)为xy，H(x,y)为xy，f(x,y)=x2+y2,g(x,y)=2xy，,则上式表达的命题为“对于任意的x，y，若x与y都是实数，且xy，则x2+y22xy”.这是真命题.若H(x,y)改为xy，则所得命题就为假命题了.,(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y),2020/7/3,离散数学,43,在例中所谈的对各种变项的指定也可以称为对它们的解释.,解释包括指定：个体域个体域中一些特定的元素函数谓词,2020/7/3,离散数学,44,定义2.1.7的解释I由下面4部分组成:,(a)非空个体域D(b)

16、D中一些特定元素的集合(c)D上特定函数集合(d)D上特定谓词的集合,2020/7/3,离散数学,45,例：给定解释I如下:(a)个体域D=N(N为自然数集合)(b)(c)(d),在I下，下列哪些公式为真?哪些为假?(1)F(f(x,y),g(x,y),解：在I下，(1)中公式被解释成“x+y=xy”，这不是命题.,2020/7/3,离散数学,46,(2)F(f(x,a),y)F(g(x,y),z),解：公式被解释成“(x+0=y)(xy=z)”，这也不是命题.,(3)F(g(x,y),g(y,z),解：公式被解释成“xyyz”.不是命题.,(4)xF(g(x,y),z）,解：公式被解释成“x

17、(xy=z)”.不是命题.,2020/7/3,离散数学,47,解：公式被解释成“x(x0=x)(x=y)”.由于蕴涵式的前件为假，所以被解释的公式为真.,(5)xF(g(x,a),x)F(x,y),解：公式被解释成“x(x0=x)”.假命题.,(7)xy(F(f(x,a),y)F(f(y,a),x),解：公式被解释成“xy(x+0=y)(y+0=x)”.真命题.,2020/7/3,离散数学,48,(8)xyzF(f(x,y),z),解：公式被解释为：xyz(x+y=z)，真命题。,从本例可以看出，闭式在给定的解释中都变成了命题。,定理封闭的公式在任何解释下都变成命题.,2020/7/3,离散数

18、学,49,定义2.1.8设A为一个公式，若A在任何解释下均为真，则称A为永真式(或称逻辑有效式).,若A在任何解释下均为假，则称A为矛盾式(或永假式)。,若至少存在一个解释使A为真，则称A为可满足式.,从定义可知，永真式一定是可满足式，但可满足式不一定是永真式。,一阶公式的分类,2020/7/3,离散数学,50,定义2.1.9设A0是含有命题变项p1,p2,pn的命题公式,A1,A2,An是n个谓词公式,用Ai(1in)处处代替A0中的pi，所得公式A称为A0的代换实例。,例如，F(x)G(x)，xF(x)yG(y)等都是pq的代换实例，而x(F(x)G(x)不是pq的代换实例.,定理：重言式

19、的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,2020/7/3,离散数学,51,例判断下列公式中，哪些是永真式，哪些是矛盾式?,(1)x(F(x)G(x)(2)xF(x)(xyG(x，y)xF(x)(3)(xF(x)yG(y)yG(y),2020/7/3,离散数学,52,解：为方便起见，用A，B，C分别记(1)，(2)，(3)中的公式。,(1)取解释I1:个体域为实数集合R，F(x):x是整数，G(x):x是有理数.在I1下A为真，因而A不是矛盾式.,取解释I2:个体域仍然为R,F(x):x是无理数,G(x):x能表示成分数.,在I2下A为假，所以A不是永真式.故A是非永真式的可满足式.

20、,(1)x(F(x)G(x),2020/7/3,离散数学,53,(2)xF(x)(xyG(x，y)xF(x)易知B是命题公式p(qp)的代换实例，而该命题公式是重言式，所以B是永真式.,(3)(xF(x)yG(y)yG(y)C是命题公式(pq)q的代换实例，而该命题公式是矛盾式，所以C是矛盾式。,2020/7/3,离散数学,54,(1)xF(x)xF(x)(2)xyF(x，y)xyF(x,y)(3)x(F(x)G(x)yG(y),例判断下列公式的类型.,2020/7/3,离散数学,55,解：记(1),(2),(3)中的公式分别为A,B,C.,(1)设I为任意一个解释，个体域为D.若存在x0D，

21、使得F(x0)为假，则xF(x)为假，所以A的前件为假，故A为真.若对于任意xD，F(x)均为真，则xF(x)，xF(x)都为真，从而A为真.所以在I下A为真.由I的任意性可知，A是永真式.,(1)xF(x)xF(x),2020/7/3,离散数学,56,解：取解释I:个体域为自然数集合N,F(x,y)为xy.,在I下B的前件与后件均为真，所以B为真。这说明B不是矛盾式.,再取I：个体域仍然为N，F(x,y)为x=y。在I下，B的前件真而后件假，所以B为假，这又说明B不是永真式。故B是非永真式的可满足式。,(3)x(F(x)G(x)yG(y)C也是非永真式的可满足式.,（2）xyF(x，y)xy

22、F(x,y),2020/7/3,离散数学,57,一阶逻辑知识结构,2.1一阶逻辑基本概念2.2一阶逻辑等值演算2.3一阶逻辑的推理理论,第一、二次课,2020/7/3,离散数学,58,一阶逻辑等值演算知识点,两组一阶逻辑等值式命题逻辑中重言式的代换实例量词消去等值式、量词否定等值式、量词辖域收缩与扩张等值式、量词分配等值式三条规则置换规则换名规则代替规则,2020/7/3,离散数学,59,一阶逻辑等值式,定义2.2.1：设A、B是一阶逻辑中任意的两个公式，若AB为逻辑有效式，则称A与B是等值的，记作：AB，称AB为等值式。,2020/7/3,离散数学,60,举例说明：等价：AB读作：A等价于B

23、含义：A与B在各种赋值下取值均相等AB当且仅当AB是永真式例如：xF(x)xF(x),2020/7/3,离散数学,61,命题公式的推广,命题演算中的等价公式和蕴含公式都可以推广到谓词演算中使用。例1：AA,令A=xF(x),得到xF(x)xF(x)例2：ABAB,令A=F(x),B=G(y),得到F(x)G(y)F(x)G(y),2020/7/3,离散数学,62,定理2.2.1：量词否定等值式,（1）xA(x)xA(x)（2）xA(x)xA(x)直观理解例：设P(x)：x今天上班。个体域为某公司全体员工。有限个体域内的证明,2020/7/3,离散数学,63,定理2.2.2量词辖域收缩与扩张等值

24、式(1),（1）xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)说明:B中不含x的出现,2020/7/3,离散数学,64,例1:(x)(F(x)G(y)(x)F(x)G(y)例2:(x)(y)(F(x)G(y)(x)(F(x)(y)G(y)(x)F(x)(y)G(y)例3:(x)(F(x)G(y)(x)F(x)G(y)例4:(x)(y)(F(x)G(y)(x)(F(x)(y)G(y)(x)F(x)(y)G(y),2020/7/3,离散数学,65,定理2.2.2量词辖域收缩与扩张等值式(2),(x)A(x)B)(x)(A(x)B)(

25、x)A(x)B)(x)(A(x)B)(B(x)A(x)(x)(BA(x)(B(x)A(x)(x)(BA(x)说明:B中不含x的出现,2020/7/3,离散数学,66,例1：(x)(A(x)B)(x)A(x)B证明:(x)(A(x)B)(x)(A(x)B)(x)A(x)B(x)A(x)B(x)A(x)B例2：(x)(BA(x)B(x)A(x)证明:(x)(BA(x)(x)(BA(x)B(x)A(x)B(x)A(x),2020/7/3,离散数学,67,例3：(x)(A(x)B)(x)A(x)B证明:(x)(A(x)B)(x)(A(x)B)(x)A(x)B(x)A(x)B(x)A(x)B例4：(x)

26、(BA(x)B(x)A(x)证明:(x)(BA(x)(x)(BA(x)B(x)A(x)B(x)A(x),2020/7/3,离散数学,68,定理2.2.3量词分配等值式,(1)x(A(x)B(x)xA(x)xB(x)(2)x(A(x)B(x)xA(x)xB(x)称(1)为“对满足分配律”，(2)为“对满足分配律”。例1:联欢会上所有人既唱歌又跳舞;联欢会上所有人唱歌且所有人跳舞。例2:联欢会上有的人唱歌，有的人跳舞。注意：“对”以及“对”不存在分配等价式。,2020/7/3,离散数学,69,量词分配蕴含式,定理2.2.4：量词分配蕴含式(1)(x)A(x)(x)B(x)(x)(A(x)B(x)(

27、2)(x)(A(x)B(x)(x)A(x)(x)B(x)例:个体域为全体自然数;A(x):x是偶数;B(x):x是奇数,成立,不成立,2020/7/3,离散数学,70,1.(x)(A(x)B(x)(x)A(x)(x)B(x)2.(x)A(x)(x)B(x)(x)(A(x)B(x)例:个体域为全体自然数;A(x):x是偶数B(x):x是奇数;,成立,不成立,2020/7/3,离散数学,71,量词的消去,2020/7/3,离散数学,72,前束范式知识点,定义前束范式存在定理前束范式的求取方法,2020/7/3,离散数学,73,一阶逻辑公式的标准形前束范式,定义2.2.2设A为一个一阶逻辑公式，若A

28、具有如下形式,则称A为前束范式，其中为或，B为不含量词的公式。,2020/7/3,离散数学,74,等公式都是前束范式，而,等都不是前束范式.,可证明每个一阶逻辑公式都能找到与之等价的前束范式.,2020/7/3,离散数学,75,定理2.2.5(前束范式存在定理)一阶逻辑中的任何公式都存在与之等值的前束范式.,下面用一阶逻辑的等值演算求前束范式.,例求下面公式的前束范式：,(1),(2),2020/7/3,离散数学,76,解(1),(换名规则),(2.1第二式),(2.2第二式),(2.2第二式),或者,(2.1第二式),(2.3第一式),由此可知，(1)中公式的前束范式是不唯一的.,2020/

29、7/3,离散数学,77,(2),(2.2第一式),(2.1第二式),(换名规则),(2.2第一式),2020/7/3,离散数学,78,求一个谓词公式的前束范式的过程,（1）通过利用公式消去谓词公式中的蕴含和等价联结词；,（2）消去；（3）否定深入，即利用量词转化公式，把否定联结词深入到命题变元和谓词填式的前面；（4）运用换名规则和代入规则，将公式中所有变元均用不同的符号；（5）量词前移，即利用量词辖域的扩张把量词移到前面。,2020/7/3,离散数学,79,一阶逻辑知识结构,2.1一阶逻辑基本概念2.2一阶逻辑等值演算2.3一阶逻辑的推理理论,第一、二次课,2020/7/3,离散数学,80,一

30、阶逻辑推理理论知识点,推理理论的形式结构推理规则全称量词消去规则全称量词引入规则存在量词消去规则存在量词引入规则,2020/7/3,离散数学,81,推理理论的形式结构,从前提A1,A2Ak出发推出结论B的推理形式结构为：,若此式为永真式，则推理正确；否则，称推理不正确。,2020/7/3,离散数学,82,xA(x)xB(x)x(A(x)B(x),量词分配的推理定律,x(A(x)B(x)xA(x)xB(x)；,x(A(x)B(x)xA(x)xB(x)；,x(A(x)B(x)xA(x)xB(x)；,2020/7/3,离散数学,83,全称量词引入规则(简记为UG规则或UG),（2）取代自由出现的y的

31、x也不能在中约束出现.,该式成立的条件是：,（1）无论中自由出现的个体变项y取何值，应该均为真.,A(y)xA(x)。,2020/7/3,离散数学,84,全称量词消去规则(简记为UI规则或UI),两式成立的条件是：,（2）在第二式中，c为任意个体变项。,（3）用y或c去取代中自由出现的x时，一定要在x自由出现的一切地方进行取代.,（1）在第一式中，取代x的y应为任意的不在中约束出现的个体变项.,1,xA(x)A(y),xA(x)A(c),2020/7/3,离散数学,85,存在量词引入规则(简称EG规则或EG),（2）取代c的x不能在中出现过.,（1）c是特定的个体常项.,该式成立的条件是：,A(a)xA(x),2020/7/3,离散数学,86,存在量词消去规则(简记为EI规则