命题逻辑的基本概念

单击此处编辑母版标题样式,*,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,