离散数学屈婉玲.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,*,*,第一章 命题逻辑的基本概念,主要内容,命题与联结词,命题及其分类,联结词与复合命题,命题公式及其赋值,1,命题与真值,命题：判断结果惟一的陈述句,命题的真值：判断的结果,真值的取值：真与假,真命题与假命题,注意：,感叹句、祈使句、疑问句都不是命题,陈述句中的悖论，判断结果不惟一确定的不是命题,1.1,命题与联结词,2,例,1,下列句子中那些是命题？,(1),是有理数,.,(2)2+5=7.,(3),x,+5 3.,(4),你去教室吗？,(5),这个苹果真大呀！,(6),请不要讲话！,(7)2050,年元旦下大雪,.,假命题,命题概念,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,3,命题分类：简单命题（也称原子命题）与复合命题,简单命题符号化,用小写英文字母,p,q,r,p,i,q,i,r,i,(,i,1),表示简单命题,用“,1”,表示真，用“,0”,表示假,例如，令,p,：是有理数，则,p,的真值为,0,，,q,：,2+5=7,，则,q,的真值为,1,命题分类,4,否定、合取、析取联结词,定义,1.3,设,p,q,为两个命题，复合命题“,p,或,q,”,称作,p,与,q,的析取式，记作,p,q,，称作析取联结词,.,规定,p,q,为假当且仅当,p,与,q,同时为假,.,定义,1.1,设,p,为命题，复合命题“非,p,”(,或“,p,的否定”,),称为,p,的否定式，记作,p,，符号,称作否定联结词,.,规定,p,为真当且仅当,p,为假,.,定义,1.2,设,p,q,为两个命题，复合命题“,p,并且,q,”(,或“,p,与,q,”),称为,p,与,q,的合取式，记作,p,q,，称作合取联结词,.,规定,p,q,为真当且仅当,p,与,q,同时为真,.,5,例,2,将下列命题符号化,.,(1),吴颖既用功又聪明,.,(2),吴颖不仅用功而且聪明,.,(3),吴颖虽然聪明，但不用功,.,(4),张辉与王丽都是三好生,.,(5),张辉与,王丽是同学,.,合取联结词的实例,6,解 令,p,:,吴颖用功,q,:,吴颖聪明,(1),p,q,(2),p,q,(3),p,q,(4),设,p,:,张辉是三好生,q,:,王丽是三好生,p,q,(5),p,:,张辉与,王丽是同学,(1)(3),说明描述合取式的灵活性与多样性,(4)(5),要求分清“与”所联结的成分,合取联结词的实例,7,例,3,将下列命题符号化,(1)2,或,4,是素数,.,(2)2,或,3,是素数,.,(3)4,或,6,是素数,.,(4),小元元只能拿一个苹果或一个梨,.,(5),王小红生于,1975,年或,1976,年,.,析取联结词的实例,8,解,(1),令,p,:2,是素数,q,:4,是素数,p,q,(2),令,p,:2,是素数,q,:3,是素数,p,q,(3),令,p,:4,是素数,q,:6,是素数,p,q,(4),令,p,:,小元元拿一个苹果,q:,小元元拿一个梨,(,p,q,)(,p,q,),(5),p,:,王小红生于,1975,年,q,:,王小红生于,1976,年,(,p,q,)(,p,q,),或,p,q,(1)(3),为相容或,(4)(5),为排斥或,符号化时,(5),可有两种形式，而,(4),则不能,析取联结词的实例,9,定义,1.4,设,p,q,为两个命题，复合命题“如果,p,则,q,”,称作,p,与,q,的蕴涵式，记作,p,q,，并称,p,是蕴涵式的前件，,q,为蕴涵式的后件，,称作蕴涵联结词,.,规定：,p,q,为假当且仅当,p,为真,q,为假,.,蕴涵联结词,(1),p,q,的逻辑关系：,q,为,p,的必要条件,(2)“,如果,p,则,q,”,有很多不同的表述方法：,若,p,，就,q,只要,p,，就,q,p,仅当,q,只有,q,才,p,除非,q,才,p,或 除非,q,，否则非,p,，,(3),当,p,为假时，,p,q,恒为真，称为空证明,(4),常出现的错误：不分充分与必要条件,10,例,4,设,p,：天冷，,q,：小王穿羽绒服，将下列命题符号化,(1),只要天冷，小王就穿羽绒服,.,(2),因为天冷，所以小王穿羽绒服,.,(3),若小王不穿羽绒服，则天不冷,.,(4),只有天冷，小王才穿羽绒服,.,(5),除非天冷，小王才穿羽绒服,.,(6),除非小王穿羽绒服，否则天不冷,.,(7),如果天不冷，则小王不穿羽绒服,.,(8),小王穿羽绒服仅当天冷的时候,.,蕴涵联结词的实例,p,q,注意：,p,q,与,q,p,等值（真值相同）,p,q,p,q,q,p,q,p,p,q,q,p,q,p,11,定义,1.5,设,p,q,为两个命题，复合命题“,p,当且仅当,q,”,称作,p,与,q,的等价式，记作,p,q,，,称作等价联结词,.,规定,p,q,为真当且仅当,p,与,q,同时为真或同时为假,.,p,q,的逻辑关系：,p,与,q,互为充分必要条件,等价联结词,例5 求下列复合命题的真值,(1)2+2 4 当且仅当 3+3 6.,(2)2+2 4 当且仅当 3 是偶数.,(3)2+2 4 当且仅当 太阳从东方升起.,(4)2+2 4 当且仅当 位于非洲.,(5)函数 f(x)在 x0 可导的充要条件是 它在 x0 连续.,1,0,0,1,0,12,本小节中,p,q,r,均表示命题,.,联结词集为,，,p,p,q,p,q,p,q,p,q,为基本复合命题,.,其中要特别注意理解,p,q,的涵义,.,反复使用,中的联结词组成更为复杂的复合命题,.,设,p,:,是无理数，,q,:3,是奇数，,r,:,苹果是方的，,s,:,太阳绕地球转,则复合命题,(,p,q,),(,r,s,),p,),是假命题,.,小结,联结词的运算顺序：,同级按先出现者先运算,.,13,1.2,命题公式及其赋值,命题变项与合式公式,命题变项,合式公式,合式公式的层次,公式的赋值,公式赋值,公式类型,真值表,14,命题变项与合式公式,命题常项,命题变项（命题变元）,常项与变项均用,p,q,r,p,i,q,i,r,i,等表示,.,定义,1.6,合式公式（简称公式）的递归定义：,(1),单个命题变项和命题常项是合式公式,称作原子命题公式,(2),若,A,是合式公式，则,(,A,),也是,(3),若,A,B,是合式公式，则,(,A,B,),(,A,B,),(,A,B,),(,A,B,),也是,(4),只有有限次地应用,(1)(3),形成的符号串才是合式公式,几点说明：,归纳或递归定义,元语言与对象语言,外层括号可以省去,15,合式公式的层次,定义,1.7,(1),若公式,A,是单个命题变项，则称,A,为,0,层公式,.,(2),称,A,是,n,+1(,n,0),层公式是指下面情况之一：,(a),A,=,B,B,是,n,层公式；,(b),A,=,B,C,其中,B,C,分别为,i,层和,j,层公式，,且,n,=max(,i,j,),；,(c),A,=,B,C,其中,B,C,的层次及,n,同,(,b,),；,(d),A,=,B,C,其中,B,C,的层次及,n,同,(,b,),；,(e),A,=,B,C,其中,B,C,的层次及,n,同,(,b,).,(3),若公式,A,的层次为,k,则称,A,为,k,层公式,.,例如 公式,A,=,p,B,=,p,C,=,p,q,D,=,(,p,q,),r,E,=(,p,q,),r,),(,r,s,),分别为,0,层，,1,层，,2,层，,3,层，,4,层公式,.,16,定义,1.8,设,p,1,p,2,p,n,是出现在公式,A,中的全部命题变项,给,p,1,p,2,p,n,各指定一个真值,称为对,A,的一个赋值或解释,.,若使,A,为,1,则称这组值为,A,的成真赋值,;,若使,A,为,0,则称这组,值为,A,的成假赋值,.,几点说明：,A,中仅出现,p,1,p,2,p,n,，给,A,赋值,=,1,2,n,是指,p,1,=,1,p,2,=,2,p,n,=,n,i,=0,或,1,i,之间不加标点符号,A,中仅出现,p,q,r,给,A,赋值,1,2,3,是指,p,=,1,q,=,2,r,=,3,含,n,个命题变项的公式有,2,n,个赋值,.,如,000,010,101,110,是,(,p,q,),r,的成真赋值,001,011,100,111,是成假赋值,.,公式赋值,17,定义,1.9,将命题公式,A,在所有赋值下取值的情况列成表,称作,A,的真值表,.,构造真值表的步骤,:,(1),找出公式中所含的全部命题变项,p,1,p,2,p,n,(,若无下角标,则按字母顺序排列,),列出,2,n,个全部赋值,从,00,0,开始,按,二进制加法,每次加,1,直至,111,为止,.,(2),按从低到高的顺序写出公式的各个层次,.,(3),对每个赋值依次计算各层次的真值,直到最后计算出公式,的真值为止,.,真值表,18,例,6,写出下列公式的真值表,并求它们的成真赋值和成假,赋值,:,(1)(,p,q,),r,(2)(,q,p,),q,p,(3),(,p,q,),q,真值表,19,(1),A,=(,p,q,),r,成真赋值,:000,001,010,100,110;,成假赋值,:011,101,111,p q r,p,q,r,(,p,q,),r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,真值表,1,20,(2)若A是合式公式，则(A)也是,(1)2+2 4 当且仅当 3+3 6.,(b)A=BC,其中B,C 分别为 i 层和 j 层公式，,A中仅出现 p1,p2,pn，给A赋值=12n是指,(a)A=B,B 是 n 层公式；,(1)令p:2是素数,q:4是素数,pq,(3)C(pq)q的真值表,联结词,及复合命题符号化,且 n=max(i,j)；,常项与变项均用 p,q,r,pi,qi,ri,等表示.,(3)对每个赋值依次计算各层次的真值,直到最后计算出公式,(1)(pq)r,只要p，就q,求出公式的全部成真赋值与成假赋值,判断公式的类型,(2)苹果树和梨树都是落叶乔木.,例3 将下列命题符号化,设 p:交通阻塞，q:他迟到,(2)(qr)(pr),E=(pq)r)(rs),(e)A=BC,其中B,C 的层次及 n 同(b).,成真赋值:000,001,010,100,110;成假赋值:011,101,111,(4)令p:小元元拿一个苹果,q:小元元拿一个梨,(2)吴颖不仅用功而且聪明.,(3)王小红或李大明是物理组成员.,(5)由于交通阻塞，他迟到了.,(1)pr(qp),(1)(3)为相容或,(pq)(qp)r,(4)(qp)(pr)(rq),(3)对每个赋值依次计算各层次的真值,直到最后计算出公式,(2),B,(,q,p,),q,p,成真赋,值,:00,01,10,11;,无成假赋值,p,q,q,p,(,q,p,),q,(,q,p,),q,p,0 0,0 1,1 0,1 1,1,0,1,1,0,0,0,1,1,1,1,1,真值表,2,21,(3),C,(,p,q,),q,的真值表,成假赋值,:00,01,10,11;,无成真赋值,p,q,p,p,q,(,p,q,),(,p,q,),q,0 0,0 1,1 0,1 1,1,1,0,0,1,1,0,1,0,0,1,0,0,0,0,0,真值表,3,22,公式的类型,定义,1.10,(1),若,A,在它的任何赋值下均为真,则称,A,为重言式或永真式,;,(2),若,A,在它的任何赋值下均为假,则称,A,为矛盾式或永假式,;,(3),若,A,不是矛盾式,则称,A,是可满足式,.,由例,1,可知,(,p,q,),r,(,q,p,),q,p,(,p,q,),q,分别为非重言式的可满足式,重言式,矛盾式,.,注意：重言式是可满足式，但反之不真,.,真值表的用途,:,求出公式的全部成真赋值与成假赋值,判断公式的类型,23,第一章 习题课,主要内容,命题、真值、简单命题与复合命题、命题符号化,联结词,及复合命题符号化,命题公式及层次,公式的类型,真值表及应用,基本要求,深刻理解各联结词的逻辑关系,熟练地将命题符号化,会求复合命题的真值,深刻理解合式公式及重言式、矛盾式、可满足式等概念,熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型,24,1.,将下列命题符号化,(1),豆沙包是由面粉和红小豆做成的,.,(2),苹果树和梨树都是落叶乔木,.,(3),王小红或李大明是物理组成员,.,(4),王小红或李大明中的一人是物理组成员,.,(5),由于交通阻塞，他迟到了,.,(6),如果交通不阻塞，他就不会迟到,.,(7),他没迟到，所以交通没阻塞,.,(8),除非交通阻塞，否则他不会迟到,.,(9),他迟到当且仅当交通阻塞,.,练习,1,25,提示：,分清复合命题与简单命题,分清相容或与排斥或,分清必要与充分条件及充分必要条件,答案,:,(1),是简单命题,(2),是合取式,(3),是析取式（相容或）,(4),是析取式（排斥或）,设,p,:,交通阻塞，,q,:,他迟到,(5),p,q,(6),p,q,或,q,p,(7),q,p,或,p,q,(8),q,p,或,p,q,(9),p,q,或,p,q,可见,(5),与,(7),，,(6),与,(8),相同（等值）,练习,1,解答,26,pq 的逻辑关系：p与q互为充分必要条件,p=1,q=2,r=3,2 设p,q为两个命题，复合命题“p并且q”(或“p与 q”)称为p与q的合取式，记作pq，称作合取联结词.,(3)是析取式（相容或）(4)是析取式（排斥或）,(2)因为天冷，所以小王穿羽绒服.,若使A为1,则称这组值为A的成真赋值;若使A为0,则称这组,(1)豆沙包是由面粉和红小豆做成的.,(2)(pq)(qp)r,例2 将下列命题符号化.,4 设p,q为两个命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词.,(b)A=BC,其中B,C 分别为 i 层和 j 层公式，,E=(pq)r)(rs),(e)A=BC,其中B,C 的层次及 n 同(b).,p=1,q=2,r=3,(2)2+5=7.,2.设 p:2是素数,q:北京比天津人口多,r:的首都是旧金山,求下面命题的真值,(1)(pq)r,(2)(qr)(pr),(3)(qr)(pr),(4)(qp)(pr)(rq),0,练习,2,1,0,0,27,3.,用真值表判断下面公式的类型,(1),p,r,(,q,p,),(2)(,p,q,),(,q,p,),r,(3)(,p,q,),(,p,r,),练习,3,28,练习,3,解答,(1),p,r,(,q,p,),矛盾式,p q r,q,p,(,q,p,),p,r,(,q,p,),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,0,0,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,29,练习,3,解答,(2)(,p,q,),(,q,p,),r,永真式,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0,1,1,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,),(,q,p,),r,q,p,p,q,p q r,30,练习,3,解答,(3)(,p,q,),(,p,r,),非永真式的可满足式,p q r,p,q,p,r,(,p,q,),(,p,r,),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,0,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,0,1,31,