资源描述
单击此处编辑母版标题样式,*,*,1,主要内容,命题逻辑基本概念,命题逻辑等值演算,命题逻辑推理理论,一阶逻辑基本概念,一阶逻辑等值演算与推理,第一部分 数理逻辑,2,第一章 命题逻辑的基本概念,主要内容,命题与联结词,命题及其分类,联结词与复合命题,命题公式及其赋值,3,命题与真值,命题：判断结果惟一的陈述句,命题的真值：判断的结果,真值的取值：真与假,真命题与假命题,注意：,感叹句、祈使句、疑问句都不是命题,陈述句中的悖论，判断结果不惟一确定的不是命题,1.1,命题与联结词,4,例,1,下列句子中那些是命题？,(1),是有理数,.,(2) 2 + 5 = 7.,(3),x,+ 5 3.,(4),你去教室吗？,(5),这个苹果真大呀！,(6),请不要讲话！,(7) 2050,年元旦下大雪,.,假命题,命题概念,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,5,命题分类：简单命题（也称原子命题）与复合命题,简单命题符号化,用小写英文字母,p,q,r, ,p,i,q,i,r,i,(,i,1),表示简单命题,用“,1”,表示真，用“,0”,表示假,例如，令,p,： 是有理数，则,p,的真值为,0,，,q,：,2 + 5 = 7,，则,q,的真值为,1,命题分类,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,例,2,将下列命题符号化,.,(1),吴颖既用功又聪明,.,(2),吴颖不仅用功而且聪明,.,(3),吴颖虽然聪明，但不用功,.,(4),张辉与王丽都是三好生,.,(5),张辉与,王丽是同学,.,合取联结词的实例,8,解 令,p,:,吴颖用功,q,:,吴颖聪明,(1),p,q,(2),p,q,(3),p,q,(4),设,p,:,张辉是三好生,q,:,王丽是三好生,p,q,(5),p,:,张辉与,王丽是同学,(1)(3),说明描述合取式的灵活性与多样性,(4)(5),要求分清 “与” 所联结的成分,合取联结词的实例,9,例,3,将下列命题符号化,(1) 2,或,4,是素数,.,(2) 2,或,3,是素数,.,(3) 4,或,6,是素数,.,(4),小元元只能拿一个苹果或一个梨,.,(5),王小红生于,1975,年或,1976,年,.,析取联结词的实例,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,定义,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,例,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,定义,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,本小节中,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,1.2,命题公式及其赋值,命题变项与合式公式,命题变项,合式公式,合式公式的层次,公式的赋值,公式赋值,公式类型,真值表,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,合式公式的层次,定义,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,定义,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,定义,1.9,将命题公式,A,在所有赋值下取值的情况列成表,称作,A,的,真值表,.,构造真值表的步骤,:,(1),找出公式中所含的全部命题变项,p,1,p,2, ,p,n,(,若无下角标,则按字母顺序排列,),列出,2,n,个全部赋值,从,00,0,开始,按,二进制加法,每次加,1,直至,111,为止,.,(2),按从低到高的顺序写出公式的各个层次,.,(3),对每个赋值依次计算各层次的真值,直到最后计算出公式,的真值为止,.,真值表,20,例,6,写出下列公式的真值表,并求它们的成真赋值和成假,赋值,:,(1) (,p,q,),r,(2) (,q,p,) ,q,p,(3),(,p,q,) ,q,真值表,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,(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,(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,公式的类型,定义,1.10,(1),若,A,在它的任何赋值下均为真,则称,A,为,重言式,或,永真式,;,(2),若,A,在它的任何赋值下均为假,则称,A,为,矛盾式,或,永假式,;,(3),若,A,不是矛盾式,则称,A,是,可满足式,.,由例,1,可知, (,p,q,),r,(,q,p,) ,q,p,(,p,q,) ,q,分别为非重言式的可满足式,重言式,矛盾式,.,注意：重言式是可满足式，但反之不真,.,真值表的用途,:,求出公式的全部成真赋值与成假赋值,判断公式的类型,25,第一章 习题课,主要内容,命题、真值、简单命题与复合命题、命题符号化,联结词,及复合命题符号化,命题公式及层次,公式的类型,真值表及应用,基本要求,深刻理解各联结词的逻辑关系,熟练地将命题符号化,会求复合命题的真值,深刻理解合式公式及重言式、矛盾式、可满足式等概念,熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型,26,1.,将下列命题符号化,(1),豆沙包是由面粉和红小豆做成的,.,(2),苹果树和梨树都是落叶乔木,.,(3),王小红或李大明是物理组成员,.,(4),王小红或李大明中的一人是物理组成员,.,(5),由于交通阻塞，他迟到了,.,(6),如果交通不阻塞，他就不会迟到,.,(7),他没迟到，所以交通没阻塞,.,(8),除非交通阻塞，否则他不会迟到,.,(9),他迟到当且仅当交通阻塞,.,练习,1,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,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,3.,用真值表判断下面公式的类型,(1),p,r,(,q,p,),(2) (,p,q,),(,q,p,),r,(3) (,p,q,),(,p,r,),练习,3,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,练习,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,练习,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,
展开阅读全文