命题逻辑基本概念课件

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,1,第1章 命题逻辑基本概念,离散数学,第1章 命题逻辑基本概念离散数学,第一次课程说明,本书的主要内容,数理逻辑,集合论,代数结构,图论,第一次课程说明本书的主要内容,第一次课程说明,数理逻辑,:,数理逻辑是研究推理逻辑规则的一个数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系。进而讨论推理体系的一致性、可靠性和完备（全）性等。数理逻辑的研究内容是两个演算加四论，具体为命题演算、谓词演算、集合论、模型论、递归论和证明论。数理逻辑是形式逻辑与数学相结合的产物。但数理逻辑研究的是各学科（包括数学）共同遵从的一般性的逻辑规律，而各门学科只研究自身的具体规律。,本章是后续各章的准备或前提,第一次课程说明数理逻辑:,1.1 命题与联结词,数理逻辑研究的,中心问题,是,推理,。,推理的,前提,和,结论,都是,表达判断,的,陈述句,。,表达判断的陈述句构成了推理的,基本单位,。,1.1 命题与联结词数理逻辑研究的中心问题是推理。,1.1 命题与联结词,称非真即假的陈述句为,命题（,proposition,）,。,作为命题的陈述句所表达得的判断结果称为命题的,真值,。,真值只取两个：,真与假,。,真值为真的命题称为,真命题,。,真值为假的命题称为,假命题,。,感叹句、疑问句、祈使句都不能称为命题。,判断结果不唯一确定的陈述句不是命题。,陈述句中的悖论不是命题,。,说明,1.1 命题与联结词称非真即假的陈述句为命题（propos,4是素数。,x,大于,y。,充分大的偶数等于两个素数之和。,今天是星期二。,请不要吸烟！,这朵花真美丽啊！,我正在说假话。,例1.1,判断下列句子是否为命题。,是，假命题,是，真命题,不是，无确定的真值,是，真值客观存在,是，真值根据具体情况而定。,不是，疑问句,不是，祈使句,不是，感叹句,不是，悖论,4是素数。例1.1 判断下列句子是否为命题。是，假命题,命题和真值的符号化,用小写英文字母,p,q,r,p,i,q,i,r,i,表示命题,用“,1,”表示真，用“,0,”表示假,r,：,充分大的偶数等于两个素数之和,。,s,：,今天是星期二,。,p,：4,是素数。,q,：,不能被分解成更简单的陈述句，称这样的命题为,简单命题,或,原子命题,。,由简单陈述句通过联结词而成的陈述句，称这样的命题为,复合命题,。,命题和真值的符号化用小写英文字母p,q,r,pi,qi,例1.2,将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。,是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。,p,：,是有理数,q,：2,是素数；,r,：,2是偶数,s：,3是素数；,t,：,4是素数,0,1,1,1,0,非,p,；,q,并且,(,与,),r,；,q,或,t；,如果,q,，,则,s,；,q,当且仅当,s。,例1.2将下面这段陈述中所出现的原子命题符号化，并指出它们的,例1.2的讨论,半形式化形式,数理逻辑研究方法的主要特征是将论述或推理中的,各种要素都符号化,。即构造各种符号语言来代替自然语言,。为达到这一目的,引入形式化语言,.,形式化语言,：,完全由符号所构成的语言。,将联结词（,connective,）符号化，消除其二义性，对其进行严格定义。,例如：他,是100米或400米赛跑的冠军。,鱼香肉丝或锅包肉，加一碗汤。,例1.2的讨论半形式化形式,定义1.1,否定(,negation,),设,p,为命题，复合命题“非,p,”(,或“,p,的否定”)称为,p,的否定式,记作,p,，,符号称作,否定联结词,，并规定,p,为真当且仅当,p,为假,。,例如,：,p,：,哈尔滨,是一个大城市,。,p,：,哈尔滨是一个不大城市。,p,：,哈尔滨不是一个大城市。,p,p,1,0,0,1,定义1.1否定(negation)设p为命题，复合命题“非,定义1.2,合取(,conjunction,),设,p,q,为二命题，复合命题“,p,并且,q”(,或“,p,与,q”),称为,p,与,q,的,合取式,，记作,pq，,称作,合取联结词,，并规定,pq,为真当且仅当,p,与,q,同时为真,。,使用合取联结词时要注意的两点：,描述合取式的灵活性与多样性。自然语言中的“既又”、“不但而且”、“虽然但是”、“一面一面”等联结词都可以符号化为。,分清简单命题与复合命题。不要见到“与”或“和”就使用联结词。,p,q,p,q,1,1,1,1,0,0,0,1,0,0,0,0,定义1.2合取(conjunction)设p,q为二命题，,例1.3,将下列命题符号化,吴颖既用功又聪明。,吴颖不仅用功而且聪明。,吴颖虽然聪明，但不用功。,张辉与王丽都是三好学生。,张辉与王丽是同学。,p:,吴颖用功。,q:,吴颖聪明。,r:,张辉是三好学生。,s:,王丽是三好学生。,t:,张辉与王丽是同学。,(1)pq,(2)pq,(3)qp,(4)rs,(5)t,解题要点：,正确理解命题含义。,找出原子命题并符号化。,选择恰当的联结词。,例1.3 将下列命题符号化吴颖既用功又聪明。p:吴颖用功。,合取举例,p,：,我们去看电影。,q,：,房间里有十张桌子。,p,q,：,我们去看电影并且房间里有十张桌子。,在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容,。,说明,合取举例p：我们去看电影。q：房间里有十张桌子。pq,定义1.3,析取(,disjunction,),设,p,，,q,为二命题，复合命题“,p,或,q,”,称作,p,与,q,的,析取式,，记作,p,q,，,称作,析取联结词,，并规定,p,q,为假当且仅当,p,与,q,同时为假,。,自然语言中的“或”具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或,和,排斥或(排异或)。,说明,p,q,p,q,1,1,1,1,0,1,0,1,1,0,0,0,定义1.3析取(disjunction)设p，q为二命题，,例1.4 将下列命题符号化,张晓静爱唱歌或爱听音乐。,张晓静只能挑选202或203房间。,张晓静是江西人或安徽人。,他昨天做了二十或三十道习题。,设,p,：,张晓静爱唱歌，,q,：,张晓静爱听音乐。相容或，符号化为,p,q,设,t,：,张晓静挑选202房间，,u,：,张晓静挑选203房间。排斥或，符号化为：(,t,u,)(,t,u,),设,r,：,张晓静是江西人，,s,：,张晓静是安徽人。排斥或，符号化为：,r,s,。(排斥或,联结的两个命题事实上不可能同时为真,),或符号化为：(,rs)(rs),原子命题，因为“或”只表示了习题的近似数目。,例1.4 将下列命题符号化 张晓静爱唱歌或爱听音乐。设 p：,定义1.4,蕴涵,(,implication,),设,p,，,q,为二命题，复合命题“如果,p,，,则,q,”,称作,p,与,q,的,蕴涵式,，记作,p,q,，,并称,p,是蕴涵式的,前件,，,q,为蕴涵式的,后件,，称作,蕴涵联结词,并规定,p,q,为假当且仅当,p,为真,q,为假,。,说明,p,q,的逻辑关系表示,q,是,p,的必要条件。,q,是,p,的必要条件有许多不同的叙述方式,只要,p,，,就,q,因为,p,，,所以,q,p,仅当,q,只有,q,才,p,除非,q,才,p,除非,q,，,否则非,p,p,q,p,q,1,1,1,1,0,0,0,1,1,0,0,1,定义1.4蕴涵(implication)设p，q为二命题，,例1.5 将下列命题符号化，并指出其真值,如果3+36，则雪是白的。,如果3+36，则雪是白的。,如果3+36，则雪不是白的。,如果3+36，则雪不是白的。,解：令,p,：3+36，,p,的真值为1。,q,：,雪是白色的，,q,的真值也为1。,p,q,p,q,p,q,p,q,1,1,0,1,例1.5 将下列命题符号化，并指出其真值 如果3+36，则,例1.5 将下列命题符号化，并指出其真值,以下命题中出现的,a,是一个给定的正整数：,(5)只要,a,能被4整除，则,a,一定能被2整除。,(6),a,能被4整除，仅当,a,能被2整除。,(7)除非,a,能被2整除，,a,才能被4整除。,(8)除非,a,能被2整除，否则,a,不能被4整除。,(9)只有,a,能被2整除，,a,才能被4整除。,(10)只有,a,能被4整除，,a,才能被2整除。,解：,令,r,：,a,能被4整除,s,：,a,能被2整除,(5),至(9)五个命题均叙述的是,a,能被2整除是,a,能被4整除的必要条件,，因而都符号化为,r,s,。,其真值为1,在(10)中，,将,a,能被4整除看成了,a,能被2整除的必要条件,，因而应符号化为,s,r,。,a,值不定时，真值未知。,例1.5 将下列命题符号化，并指出其真值 以下命题中出现的a,关于蕴含的进一步说明,作为一种规定，当,p,为假时，无论,q,是真是假，,p,q,均为真。也就是说，只有,p,为真,q,为假这一种情况使得复合命题,p,q,为假。称为,实质蕴含,。,例：如果,x5，,则,x2。(1),x=6,如果65，则62。(2),x=3,如果35，则32。(3),x=1,如果15，则12。,例：如果我有车，那么我去接你,常出现的错误，没有分清充分条件与必要条件。,关于蕴含的进一步说明作为一种规定，当p为假时，无论q是真是假,定义1.5,等价,(,two-way-implication,),设,p,，,q,为二命题，复合命题“,p,当且仅当,q,”,称作,p,与,q,的,等价式,，记作,p,q，,称作,等价联结词,，并规定,p,q,为真当且仅当,p,与,q,同时为真或同时为假,。,说明,“,当且仅当,”（,if and only if,）,p,q,的逻辑关系为,p,与,q,互为充分必要条件。,(,pq)(qp),与,p,q,的逻辑关系完全一致。,p,q,p,q,1,1,1,1,0,0,0,1,0,0,0,1,定义1.5等价(two-way-implication)设,例1.6 将下列命题符号化，并讨论它们的真值,是无理数当且仅当加拿大位于亚洲。,2+35的充要条件是,是无理数。,若两圆,A，B,的面积相等，则它们的半径相等；反之亦然。,当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快,。,设,p,：,是无理数，,q,：,加拿大位于亚洲。符号化为,p,q,，,真值为0。,设,p,：,2+35，,q,：,是无理数。符号化为,p,q,，,真值为1。,设,p,：,两圆,A，B,的面积相等，,q,：,两圆,A，B,的半径相等。符号化为,p,q,，,真值为1。,设,p,：,王小红心情愉快，,q,：,王小红唱歌。符号化为,p,q,，,真值由具体情况而定。,例1.6 将下列命题符号化，并讨论它们的真值 是无理数当且,关于基本联结词的说明,，称为一个联结词集。,由联结词集,中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为,基本的复合命题,。,基本复合命题的真值见下表：,关于基本联结词的说明,，称为一个联结词集,关于基本联结词的说明,多次使用联结词集中的联结词，可以组成更为复杂的复合命题。,求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。,本书规定的联结词优先顺序为：()，,，对于同一优先级的联结词，先出现者先运算。,关于基本联结词的说明多次使用联结词集中的联结词，可以组成更为,例1.7,令,p：,北京比天津人口多。,q：2+24.,r：,乌鸦是白色的。,求下列复合命题的真值：(1)(,pq)(pq)r(2)(qr)(pr)(3)(pr),(pr),解：,p、q、,r,的真值分别为,1、1、0,(1)1,(2)1(3)0,我们关心的是复合命题中命题之间的真值关系，而不关