离散数学第1章-命题逻辑基本概念

,单击此处编辑母版文本样式,*,Discrete Math. , Chen Chen,*,CHAPTER ONE,离散数学,Discrete Mathematics,9/22/2024,1,Discrete Math. , Chen Chen,第一部分,数 理 逻 辑,Part One,Mathematics logic,9/22/2024,2,Discrete Math. , Chen Chen,逻辑学,:,研究人的思维形式和规律的科学由于研究的对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑,数理逻辑是用,数学方法,来研究,推理的形式结构,和,推理规律,的数学学科。这里所指的数学方法就是引进一套,符号体系,的方法。所以数理逻辑又称,符号逻辑,，它是从量的侧面来研究思维规律的。,现代数理逻辑可分为逻辑演算、证明论、公理集合论、递归论和模型论。,本部分仅介绍计算机科学领域中所必需的数理逻辑基础知识： 命题逻辑和谓词逻辑（一阶逻辑）。,9/22/2024,3,Discrete Math. , Chen Chen,第一章,命题逻辑基本概念,Chapter One,Foundations of Proposition Logic,9/22/2024,4,Discrete Math. , Chen Chen,1.1,命题与联结词,1.2,命题公式及其赋值,命题与真值,命题符号化,联结词及其逻辑关系,复合命题,命题常项与变项,命题公式及其赋值,命题公式的类型,公式类型的判断方法,9/22/2024,5,Discrete Math. , Chen Chen,一 、命题,命题：,能判断真假,(,非真即假,),的陈述句。,命题的真值：,命题的判断结果。,1.1,命题与联结词,它只有两种可能：真或假，分别用,1,和,0,来表示。,真值为,1,的命题称为,真命题,；真值为,0,的命题称为,假命题,。,判断一个句子是否为命题：,首先判断它是否为陈述句,;,其次判断它是否有唯一的真值。,定义,一个命题若不能被分解成更简单的陈述句，则称为,简单命题,或,原子命题,；,若一个命题是由几个简单陈述句通过,联结词,联结而成的，则称为,复合命题,。,例,命题“因为,32,所以,3,2.”,的组成。,9/22/2024,6,Discrete Math. , Chen Chen,（,1,）,4,是素数。,例,1.1,判断下列句子是否为命题,注：通常用小写字母,p , q , r,等来表示命题。,（,9,）我正在说假话。,（,8,）这朵花真美丽啊！,（,7,）请不要吸烟！,（,6,）,大于 吗？,（,5,）,2050,年元旦是晴天。,（,4,）火星上有水。,（,3,）,x,大于,y,其中,x,和,y,是任意的两个数。,（,2,） 是无理数 。,9/22/2024,7,Discrete Math. , Chen Chen,定义,1.1,设,p,为命题，复合命题“非,p,” (,即 “,p,的否定”,),称为,p,的否定式,，记为 ,p,。 符号 称为,否定联结词,。,规定：,p,为真当且仅当,p,为假,。,二联结词与复合命题,则,: (1),p,；,(2),q .,例,符号化：（,1,）张伟不是三好学生,;,（,2,）,不是有理数,。,解：记,p,：,张伟是三好学生。,q,：,是有理数。,例,1.2,将下列命题符号化。,(1),是有理数是不对的,.,（,2,）,2,是偶素数,. (3) 2,或,4,是偶素数,.,(4),如果,2,是素数，则,3,也是素数,. (5) 2,是素数当且仅当,3,是素数,.,解：记,p,：,是有理数,.,q,：,2,是素数,.,r,：,2,是偶数,.,s,：,3,是素数,.,t,：,4,是偶数,.,则各语句表述为：,非,p;,(2),q,与,r;,(3),p,或,t;,(4),如果,q,则,s,；,(5),q,当且仅当,s .,9/22/2024,8,Discrete Math. , Chen Chen,定义,1.2,设,p , q,为两个命题。复合命题“,p,与,q,”,即“,p,并且,q,”,称为,p,与,q,的合取式,，记为,p,q,。,符号,称为,合取联结词,。,规定：,p,q,为真,当且仅当,p,与,q,同时为真,。,注：自然语言中 “与”, “,和”, “,且”, “,既,.,又,”, “,不仅,而且,”, “,虽然,但是,”, “,一面,一面,”,等联结词都可以符号化为,；,但并不是所有的“与”、“和”等都能用联结词替代。,9/22/2024,9,Discrete Math. , Chen Chen,(1),吴颖既用功又聪明,.,(2),吴颖,不仅用功而且聪明,.,(3),吴颖,虽然聪明，但不用功,.,(4),张辉和王,丽,都是三好学生,.,(5),张,辉,和王丽是同学,.,例,1.3,将下列命题符号化,p,q,;,p,q,;,q,p,；,r,s,。,(5),是原子命题,符号化为,t,:,张,辉,和王丽是同学。,则符号化分别为：,解,: (1),、,(2),、,(3),、,(4),：,令,p,:,吴颖,用功；,q,:,吴颖,聪明，,r,:,张伟是三好学生；,s,:,王辉是三好学生,.,9/22/2024,10,Discrete Math. , Chen Chen,定义,1.3,设,p , q,为两个命题,复合命题 “,p,或,q ”,称为,p,与,q,的析取式,记为,p,q,。,符号,称为,析取联结词,。,规定：,p,q,为假当且仅当,p,与,q,同时为假。,注,:,自然语言中的 “或” 联结的两个命题可以具有相容性，也可以具有排斥性。,前者称为,相容或,，后者称为,排斥或,。,析取联结词,指的是“相容或”。,9/22/2024,11,Discrete Math. , Chen Chen,（,1,）张晓静爱唱歌或爱听音乐。,（,2,）张晓静只能挑选,202,房或,203,房。,（,3,）张晓静是江西人或安徽人。,解：,(1),令,p:,张晓静爱唱歌；,q:,张晓静爱听音乐，,则：,例,1.4,将下列命题符号化,p,q,;,(2),令,r:,张晓静住,202,房；,s:,张晓静住,203,房，,则,:,(,rs)(rs,);,(3),令,t,:,张晓静是江西人；,u,:,张晓静是安徽人，,则：,(,t,u),(,tu,).,9/22/2024,12,Discrete Math. , Chen Chen,定义,1.4,设,p,q,为两个命题。复合命题 “,如果,p,则,q,”,称为,p,与,q,的蕴,涵,式,，记作,p,q,。符号,称为,蕴涵联结词,，,称,p,是蕴涵式的,前件,，,q,是蕴,涵,式的,后件,，,q,是,p,的必要条件。,规定：,p,q,为假,当且仅当,p,为真,q,为假,。,注：,1.,在自然语言中，“如果,p,则,q,”,这种命题还有其它叙述方式，比如：“只要,p,就,q,”,，“ 因为,p,，所以,q,”,“,p,仅当,q,”,“,只有,q,才,p,”,，,“除非,q,才,p,”, “,除非,q,，否则非,p,”,等等，它们都可符号化为,p,q,。,2.,在数学或其它自然科学中，“如果,p,则,q,”,往往表达的是,前件,p,为真,，,后件,q,也为真的,推理,关系。但在数理逻辑中，作为一种规定，,当,p,为假时，无论,q,是真是假，,p,q,均为真,（因为考虑的整个语句）。,3.,在自然语言中，“如果,p,则,q,”,中的前件,p,和后件,q,往往具有某种内在联系，而在数理逻辑中，,p,与,q,可以无任何内在联系。,9/22/2024,13,Discrete Math. , Chen Chen,(1),如果,3+3 = 6,则雪是白色的。,(2),如果,3+3 6,则雪是白色的。,(3),如果,3+3 = 6,则雪不是白色的。,(4),如果,3+3 6,则雪不是白色的。,(5),只要,a,能被整除，则,a,一定能被整除。,(6),a,能被整除，仅当,a,能被整除。,(7),除非,a,能被整除，,a,才能被整除。,(8),除非,a,能被整除，否则,a,不能被整除。,(9),只有,a,能被整除，,a,才能被整除。,(10),只有,a,能被整除，,a,才能被整除。,(,a,是一个给定的正整数）。,例,1.5,将下列命题符号化，并指出各复合命题的真值。,解：令,p,：,3+3=6,；,q,：,雪是白色的。则,(1),到,(4),的符号化形式分别为：,令,r,：,a,能被整除；,s,:,a,能被整除。,(5),到,(9),都可符号化为,:,p,q,；,p,q,；,p,q,；,p,q,。,它们的真值分别为：,。,(10),可符号化为,r,s,真值为,。,s,r,，,真值视,a,的值而定。,9/22/2024,14,Discrete Math. , Chen Chen,定义,1.5,设,p,q,是两个命题，复合命题 “,p,当且仅当,q,”,称为,p,与,q,的等价式,，记为,pq,。,符号,称为,等价联结词,。,规定：,pq,为,真,当且仅当,p,与,q,同时为真,或,同时为假,。,注：,pq,可理解为“,q,与,p,互为充分必要条件,”；,它与,(,p,q,),(,qp,),的逻辑关系完全一致。,9/22/2024,15,Discrete Math. , Chen Chen,(1),3,是无理数当且仅当加拿大位于亚洲。,(2),2+3=5,的充要条件是,3,是无理数。,(3),若两圆的面积相等,则它们的半径相等,反之亦然。,(4),当王小红心情愉快,时,她就唱歌,反之,当她唱歌时,一定心情愉快。,解：,(1),令,p,:,3,是无理数；,q,:,加拿大位于亚洲，则符号化为,(4),令,x,:,王小红心情愉快,；,y:,王小红唱歌,，则,符号化为,p,q,真值为,0,。,(2),令,r,:2+3=5,；令,p,:,3,是无理数，则,符号化为,r,p,真值为,1,。,(,3,),令,s,:,两圆面积相等；,t,:,两圆半径相等，则符号化为,x y,真值由具体情况而定。,s t,真值为,1,。,例,1.6,将下列命题符号化，并讨论它们的真值。,9/22/2024,16,Discrete Math. , Chen Chen,以上定义的五种最基本的联结词组成一个联结词集,，,。由其中某个联结词联结两个原子命题（联结一个原子命题）所形成的,复合命题,称为,基本复合命题,，它们的真值情况如下表。,p q,p,p,q,p,q,pq,pq,小 结,1,1,0,0,0,0,0,1,0,1,1,1,1,1,0,1,1,0,0,1,0 0,0 1,1 0,1 1,9/22/2024,17,Discrete Math. , Chen Chen,多次使用联结词集中的联结词，可组成更为复杂的复合命题。求复杂的复合命题的真值时，可依据上述真值表逐次求取。但运算过程中应注意联结词的优先顺序,(,包括括号,),：,( ), , , , ,，。,对同一优先级的联结词，按出现的先后次序运算。,例,1.7,令：,p,：,北京比天津人口多；,q,：,2+2=4,；,r,：,乌鸦是白色的。求下列命题的真值：,(1) (,p,q,)(,p,q,),r,; (2) ( qr) (p r);,(3) (pr) (pr).,解：,p , q , r,的真值分别为,1, 1, 0,，, 按照真值表及命题式，,(1), (2), (3),的真值分别为,1, 1, 0,。,9/22/2024,18,Discrete Math. , Chen Chen,定义,1.6,简单命题（原子命题）称为,命题常项,，而称真值可以变化的陈述句为,命题变项,。命题变项一般也用小写字母,p,q,r,来表示。,将命题变项用联结词和括号按一定逻辑关系联结起来的符号串称为合式公式或命题公式。具体地说,合式公式定义,如下,:,(1),单个命题变项是合式公式,称为,原子命题公式,.,(2),若,A,是合式公式,则,(,A),也是,合式公式,.,(3),若,A,B,是合式公式,则,(AB),(AB),(AB),(A,B),也是,合式公式,.,(4),只有有限次地应用,(1),(3),形成的符号串才是,合式公式,.,设,A,是合式公式, B,是中的一部分,若,B,是合式公式,则称,B,为,A,的,子公式,.,例如,: p, (pq)(r), (pq)(qr), (pq)r, p(qr),都是命题公式。,说明：,元语言与对象语言,外层括号可以省去,1.2,命题公式及其赋值,9/22/2024,19,Discrete Math. , Chen Chen,定义,1.7,(1),若命题公式,A,是单个命题变项，则称,A,为,0,层公式,。,(2),称命题,A,是,n,+1(,n,0),层公式,，只要,A,是下列情况之一：,(a) A = B, B,是,n,层公式,;,(b) A= BC, B, C,分别为,i,层和,j,层公式，且,max,(,i,j,),= n,。,(c) A=BC, B, C,分别为,i,层和,j,层公式，且,max,(,i , j,),= n,。,(d) A= BC, B, C,分别为,i,层和,j,层公式，且,max,(,i , j,)=,n,。,(e) A= B,C, B, C,分别为,i,层和,j,层公式，且,max,(,i , j,)=,n,。,例如,: (,pq)r, (,pq,)(,rs,) p),分别为,3,层和,4,层公式。,9/22/2024,20,Discrete Math. , Chen Chen,由于命题公式中含有命题变项，故其真值一般是,不确定,的。当公式中所有命题变项都,解释,成具体的命题后，命题公式就成了真值确定的命题了。,例如,，命题公式,(,pq)r,:,则命题公式,(,pq)r,就被解释成了一个真命题。,若将,p,解释成,:2,是素数, q,解释成,:3,是偶数, r,解释成： 是无理数。,则,(,pq)r,就被解释成了一个假命题。,另外，如果,p, q,的解释不变，而将,r,解释成： 是有理数，,9/22/2024,21,Discrete Math. , Chen Chen,定义,1.8,设在命题公式,A,中出现的所有命题变项为,p,1,p,2,p,n,，,给它们各指定一个,真值,，称为,对公式,A,的一个赋值,(,或解释,),。,若一个赋值使,A,的真值为,1,，则称该赋值为,A,的,成真赋值,，,否则称为,A,的,成假赋值,。,注：,设,A,中的变项为,p,1,p,2,p,n,，给,A,的赋值,a,1,a,2,a,n,是指,p,1,=,a,1,p,2,=a,2,p,n,=a,n,，,其中,a,i,为,0,或,1, (,i =,1,2, n,),。,例如,：公式,(,p,1,p,2,p,3,)(,p,1,p,2,),中，,000 (,即,p,1,=,0,p,2,=,0,p,3,=,0,),和,110,都是,而,001,(,即,p,1,=0 ,p,2,=0,p,3,=1,),和,011,都是,成真赋值；,成假赋值。,赋值,9/22/2024,22,Discrete Math. , Chen Chen,定义,1.9,将命题公式,A,在,所有赋值,下的取值情况列成表，称为,A,的,真值表,。,含,n,个命题变项的公式共有,2,n,个不同的赋值。构造真值表的一般步骤如下：,列出命题公式中的所有命题变项,p,1,p,2,p,n,，,(,无下标时按字典序排列,),。列出这些变项的所有,2,n,个赋值。一般从,000,开始，按二进制加法依次列到,111,为止。,(2),按从低到高的顺序依次列出公式的各个层。,(3),对应于变项的,2,n,个赋值分别计算出各层的真值，直至算出公式的真值。,真值表,9/22/2024,23,Discrete Math. , Chen Chen,例,1.8,写出下列公式的真值表，并求它们的成真、成假赋值。,(1)(pq)r; (2)(pp),(qq); (3) (pq)qr,p q r,p,r,pq,(pq)r,解：,(,p,q,),r,的真值表,1,1,1,1,0,0,0,0,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,0,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,1,0,1,1,1,1,9/22/2024,24,Discrete Math. , Chen Chen,(pp),(qq),的真值表,p q,p,q,pp,qq,(pp),(qq),0 0,0 1,1 0,1 1,(pq)qr,的真值表,p q r,pq,(pq),(pq)q,(pq)qr,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9/22/2024,25,Discrete Math. , Chen Chen,定义,1.10,设,A,是一个命题公式。,若,A,在,各种赋值,下取值总为,1,，则称,A,是,永真式或重言式,。,(2),若,A,在,各种赋值,下取值总为,0,，则称,A,是,永假式或矛盾式,。,(3),若,A,不是矛盾式，则称,A,为,可满足式,。,注：,A,是可满足式当且仅当,A,至少存在一个成真赋值。,1.,重言式必是可满足式，但反之不真。,2.,可用真值表来判断公式的类型：,若真值表最后一列全为,1,，则公式为重言式；,(2),若真值表最后一列全为,0,，则公式为矛盾式；,(3),若真值表最后一列至少有一个,1,，则公式为可满足式。,公式分类,9/22/2024,26,Discrete Math. , Chen Chen,给定,n,个命题变项，使用联结词和括号，可构成无穷多个命题公式。,个命题变项共有,2,n,个可能的赋值，而在每个赋值下公式只能取,值或,1,。因此含个命题变项的公式其真值表只有,2,2,种可能的情况。从而必有无穷多个公式具有相同的真值表。,9/22/2024,27,Discrete Math. , Chen Chen,例,1.9,下列公式中哪些具有相同的真值表？,(1),；,(2),；,(3) (,),；,(4) (,)(,),；,(5) ,p q,(,),(,)(,p),0 0,0 1,1 0,1 1,解：,5,个公式的真值表,从上表可见，命题公式 “” 与 “ ,(,) ”,有相同的真值表,。,1,1,0,1,1,0,0,1,1,1,0,1,1,0,0,1,1,0,1,1,命题 “,” 与 “,(,)(,) ”,有相同的真值表。,9/22/2024,28,Discrete Math. , Chen Chen,设公式、中总共含有命题变项,p,1,p,2,p,n,，,但或并不全含有这些变项。如果某个变项,未在,公式中,出现,，则称该变项为的,哑元,。同样可定义的哑元。,在讨论与是否有相同的真值表时，应将哑元考虑在内，即将、都看成含所有,p,1,p,2,p,n,的命题公式。,9/22/2024,29,Discrete Math. , Chen Chen,例,1.10,下列公式中，哪些具有相同的真值表？,(1) pq,；,(2) qr,；,(3) (pq)(pr)p),；,(4) (qr)(pp),p q r,pq,qr,(pq)(pr)p),(qr)(pp),0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,解：四个命题共含,p,q,r,三个变项，,r,是,(1),的哑元，,p,是,(2),的哑元。,个公式的真值表,从表中可见，,(1),与,(3),具有相同的真值表；,(2),与,(4),具有相同的真值表。,1,1,1,1,0,0,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,0,1,1,1,1,0,1,1,1,0,1,9/22/2024,30,Discrete Math. , Chen Chen,