离散数学屈婉玲版ch.pptx

单击此处编辑母版标题样式,*,*,1,第1页,主要内容,命题逻辑基本概念,命题逻辑等值演算,命题逻辑推理理论,一阶逻辑基本概念,一阶逻辑等值演算与推理,第一部分 数理逻辑,2,第2页,第一章 命题逻辑基本概念,主要内容,命题与联结词,命题及其分类,联结词与复合命题,命题公式及其赋值,3,第3页,命题与真值,命题：判断结果惟一陈说句,命题真值：判断结果,真值取值：真与假,真命题与假命题,注意：,感叹句、祈使句、疑问句都不是命题,陈说句中悖论，判断结果不惟一确定不是命题,1.1,命题与联结词,4,第4页,例1,以下句子中那些是命题？,(1)是有理数.,(2)2+5=7.,(3),x,+5 3.,(4)你去教室吗？,(5)这个苹果真大呀！,(6)请不要讲话！,(7)2050年元旦下大雪.,假命题,命题概念,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,5,第5页,命题分类：简单命题（也称原子命题）与复合命题,简单命题符号化,用小写英文字母,p,q,r,p,i,q,i,r,i,(,i,1)表示简单命题,用“1”表示真，用“0”表示假,比如，令,p,：是有理数，则,p,真值为0，,q,：2+5=7，则,q,真值为1,命题分类,6,第6页,否定、合取、析取联结词,定义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,同时为真.,7,第7页,例,2,将以下命题符号化.,(1)吴颖既用功又聪明.,(2)吴颖不但用功而且聪明.,(3)吴颖即使聪明，但不用功.,(4)张辉与王丽都是三好生.,(5)张辉与,王丽是同学.,合取联结词实例,8,第8页,解 令,p,:吴颖用功,q,:吴颖聪明,(1),p,q,(2),p,q,(3),p,q,(4)设,p,:张辉是三好生,q,:王丽是三好生,p,q,(5),p,:张辉与,王丽是同学,(1)(3)说明描述合取式灵活性与多样性,(4)(5)要求分清“与”所联结成份,合取联结词实例,9,第9页,例3,将以下命题符号化,(1)2 或 4 是素数.,(2)2 或 3 是素数.,(3)4 或 6 是素数.,(4)小元元只能拿一个苹果或一个梨.,(5)王小红生于 1975 年或 1976 年.,析取联结词实例,10,第10页,解,(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)则不能,析取联结词实例,11,第11页,定义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)常出现错误：不分充分与必要条件,12,第12页,例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,13,第13页,定义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,)在,x,0,可导充要条件是 它在,x,0,连续.,1,0,0,1,0,14,第14页,本小节中,p,q,r,均表示命题.,联结词集为,，,p,p,q,p,q,p,q,p,q,为基本复合命题.其中要尤其注意了解,p,q,涵义.重复使用,中联结词组成更为复杂复合命题.,设,p,:是无理数，,q,:3是奇数，,r,:苹果是方，,s,:太阳绕地球转,则复合命题(,p,q,),(,r,s,),p,)是假命题.,小结,联结词运算次序：,同级按先出现者先运算.,15,第15页,1.2,命题公式及其赋值,命题变项与合式公式,命题变项,合式公式,合式公式层次,公式赋值,公式赋值,公式类型,真值表,16,第16页,命题变项与合式公式,命题常项,命题变项（命题变元）,常项与变项均用,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)形成符号串才是合式公式,几点说明：,归纳或递归定义,元语言与对象语言,外层括号能够省去,17,第17页,合式公式层次,定义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层公式.,18,第18页,定义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是成假赋值.,公式赋值,19,第19页,定义1.9,将命题公式,A,在全部赋值下取值情况列成表,称作,A,真值表,.,结构真值表步骤:,(1)找出公式中所含全部命题变项,p,1,p,2,p,n,(若无下角标,则按字母次序排列),列出2,n,个全部赋值,从00,0开始,按,二进制加法,每次加1,直至111为止.,(2)按从低到高次序写出公式各个层次.,(3)对每个赋值依次计算各层次真值,直到最终计算出公式,真值为止.,真值表,20,第20页,例,6,写出以下公式真值表,并求它们成真赋值和成假,赋值:,(1)(,p,q,),r,(2)(,q,p,),q,p,(3),(,p,q,),q,真值表,21,第21页,(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,22,第22页,(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,23,第23页,(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,24,第24页,公式类型,定义1.10,(1)若,A,在它任何赋值下均为真,则称,A,为,重言式,或,永真式,;,(2)若,A,在它任何赋值下均为假,则称,A,为,矛盾式,或,永假式,;,(3)若,A,不是矛盾式,则称,A,是,可满足式,.,由例1可知,(,p,q,),r,(,q,p,),q,p,(,p,q,),q,分别为非重言式可满足式,重言式,矛盾式.,注意：重言式是可满足式，但反之不真.,真值表用途:,求出公式全部成真赋值与成假赋值,判断公式类型,25,第25页,第一章 习题课,主要内容,命题、真值、简单命题与复合命题、命题符号化,联结词,及复合命题符号化,命题公式及层次,公式类型,真值表及应用,基本要求,深刻了解各联结词逻辑关系,熟练地将命题符号化,会求复合命题真值,深刻了解合式公式及重言式、矛盾式、可满足式等概念,熟练地求公式真值表，并用它求公式成真赋值与成假赋值及判断公式类型,26,第26页,1.将以下命题符号化,(1)豆沙包是由面粉和红小豆做成.,(2)苹果树和梨树都是落叶乔木.,(3)王小红或李大明是物理组组员.,(4)王小红或李大明中一人是物理组组员.,(5)因为交通阻塞，他迟到了.,(6)假如交通不阻塞，他就不会迟到.,(7)他没迟到，所以交通没阻塞.,(8)除非交通阻塞，不然他不会迟到.,(9)他迟到当且仅当交通阻塞.,练习,1,27,第27页,提醒：,分清复合命题与简单命题,分清相容或与排斥或,分清必要与充分条件及充分必要条件,答案:,(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解答,28,第28页,2.设,p,:2是素数,q,:北京比天津人口多,r,:美国首都是旧金山,求下面命题真值,(1)(,p,q,),r,(2)(,q,r,),(,p,r,),(3)(,q,r,),(,p,r,),(4)(,q,p,),(,p,r,),(,r,q,),0,练习,2,1,0,0,29,第29页,3.用真值表判断下面公式类型,(1),p,r,(,q,p,),(2)(,p,q,),(,q,p,),r,(3)(,p,q,),(,p,r,),练习,3,30,第30页,练习,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,31,第31页,练习,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,32,第32页,练习,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,33,第33页,