《命题与联结词》PPT课件.ppt

离散数学（DiscreteMathematics）,课程介绍,一、简史“离散数学”是一门相对于“连续数学”而命名的数学分支。产生于数学游戏(如一笔画、过渡、组合、计数等)，分散于各个分支，计算机的产生推动了其形成和发展。二、知识模块数理逻辑集合论和关系图论初步代数系统三、学习要求1.首先要精确严格地掌握好概念和术语、理解基本定理的本质；2.独立完成每一次作业，每次作业完成之后，能自觉地归纳出其中用到的基本解题方法；3.自学相关参考教材。,数理逻辑是用数学方法研究思维规律的一门学科.所谓数学方法是指:用一套数学的符号系统来描述和处理思维的形式与规律.因此,数理逻辑又称为符号逻辑.,第一部分数理逻辑,第一章命题逻辑基本概念,第二章命题逻辑等值演算,第四章一阶逻辑基本概念,第三章命题逻辑的推理理论,第五章一阶逻辑等值演算与推理,第一章命题逻辑基本概念,第1节命题与联结词,第2节命题公式及其赋值,一、命题的概念,二、复合命题与联结词,第1节命题与联结词,一、命题的概念,1命题：能判断真假的陈述句称为命题。,（1）真值:命题判断真假的结果真值只取两个值：真或假。,（2）真命题：真值为真的命题；假命题：真值为假的命题。,（4）判断命题分两步：是否为陈述句是否有唯一真值,（3）任何命题的真值都是唯一的。,例1.1判断下列句子是否为命题,(1)4是素数。(2)是无理数。(3)x大于y。(4)月球上有冰。(5)2100年元旦是晴天。,(6)大于吗？(7)请不要吸烟！(8)这朵花真美丽啊！(9)我正在说假话。,解:本题的(9)个句子中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因而这3个句子都不是命题。剩下的6个句子都是陈述句，(3)无确定的真值：根据x,y的不同取值情况它可真可假，即无唯一的真值，因而不是命题。若(9)的真值为真，即“我正在说假话”为真，也就是“我正在说真话”，则又推出(9)的真值应为假；反之，若(9)的真值为假，即“我正在说假话”为假，也就是“我正在说假话”，则又推出(9)的真值应为真。于是(9)既不为真又不为假，因此它不是命题。,像(9)这样由真推出假，又由假推出真的陈述句称为悖论。凡是悖论都不是命题。本例中，只有(1)，(2)，(4)，(5)是命题。(1)为假命题，(2)为真命题。虽然今天我们不知道(4)，(5)的真值，但它们的真值客观存在，而且是唯一的，将来总会知道(4)的真值，到2100年元旦(5)的真值就真相大白了。注：真值唯一与现在能否确定是不同的!,2命题和真值的符号化,（1）用真值来描述命题是“真”还是“假”，分别用“1”和“0”表示（或用“F”和“T”表示）,（2）命题用小写的英文字母、或者带下标的小写的字母、来表示.,二、复合命题与联结词,各种论述和推理中，出现的命题多数比例1.1中的命题更加复杂。,例1.2下列句子全是命题,是有理数是不对的;2是偶素数;2或4是素数;,如果2是素数则3也是素数;2是素数当且仅当3是素数.,这些命题是通过诸如“或”“如果，则”等连词联结而成.,1命题分类,（1）简单（原子）命题：由简单句（不含联结词的陈述句）形成的命题；,（2）复合（分子）命题：由一个或几个简单句通过联结词的联接而构成的命题.,2联结词,（1）否定联结词,定义1.1设为命题，复合命题“非（或“的否定”）称为的否定式，记作，符号称作否定联结词.（一元复合命题）,规定：为真当且仅当为假,命题取值为真时，命题取值为假；,命题取值为假时，命题取值为真,（2）合取联结词,定义1.2设、为二命题，复合命题“并且”（或“与”）称为与的合取式，记作符号称作合取联结词.,规定：为真当且仅当与同时为真,使用合取联结词是要注意两点：,自然语言的灵活性：自然语言中的“既又”、“不但而且”、“虽然但是”、“一面一面”等联结词基本含义是“和”、“并且”，都可符号化；,多义性:不要见到“与”或“和”就使用联结词（有时“和”不能符号化为）,pq中p与q在自然语言上未必有某种被认可的联系（只是形式化处理的需要）,例1.将下列命题符号化,(1)吴颖既用功又聪明.(2)吴颖不仅用功而且聪明.(3)吴颖虽然聪明，但不用功.(4)张辉和王丽都是三好学生.(5)张辉与王丽是同学.,解：首先将原子命题符号化：p:吴颖用功.q:吴颖聪明.r:张辉是三好学生.s:王丽是三好学生.t:张辉与王丽是同学.,（1）到(4)都是复合命题，它们使用的联结词表面看来各不相同，但都是合取联结词，都应符号化为，(1)到(4)分别符号化为：pq，pq，qp，rs.（5）是原子命题，符号化为t.,（3）析取联结词,定义1.3设、为二命题，复合命题“或”称为与的析取式，记作，符号称作析取联结词.,规定：为假当且仅当与同时为假；,等价于当且仅当和至少一个取值为真时，取值为真,注意：自然语言中的“或”有二义性：相容“或”（可兼）；排斥“或”(排异).pq中p与q的关系可任意.,例1.4将下列命题符号化,(1)张晓静爱唱歌或爱听音乐.(2)张晓静是江西人或安徽人.(3)张晓静只能挑选202或203房间.,解：在解题时，先将原子命题符号化。(1)p：张晓静爱唱歌.q：张晓静爱听音乐(1)中“或”为相容或，符号化为pq.(2)r：张晓静是江西人.s：张晓静是安徽人.(2)中“或”应为排斥或，但r与s不能同时为真，因而也可以符号化为rs.,(3)t：张晓静挑选202房间.u：张晓静挑选203房间.由题意可知，(3)中“或”应为排斥或.t，u的联合取值情况有四种：同真，同假，一真一假(两种情况).如果也符号化为tu，张晓静就可能同时得到两个房间，这违背题意.因而不能符号化为tu.如何达到只能挑一个房间的要求呢？可以使用多个联结词，符号化为(tu)(tu).此复合命题为真当且仅当t，u中一个为真，一个为假，它准确地表达了(3)的要求.当t为真u为假时，张晓静得到202房间，t为假u为真时，张晓静得到203房间，其它情况下，她得不到任何房间.,（4）蕴涵联结词,定义1.4设、为二命题，复合命题“如果则”称为与的蕴涵式，记作，符号称作蕴涵联结词.,规定：为假当且仅当为真为假；,的逻辑关系为是的必要条件、,是的充分条件,注意：,在自然语言里，特别是在数学中，q是p的必要条件有许多不同的叙述方式。例如，,“如果p，那么q”，,“因为p，所以q”，,“p仅当q”，,“只有q才p”，,“除非q才p”，,“除非q，否则非p”,以上各种叙述方式表面看来有所不同，但都表达的是q是p的必要条件，因而所用联结词均应符号化为，上述各种叙述方式都应符号化为.,“只要p，就q”，,注意：,在自然语言里，“如果p，则q”中的前件p与后件q往往具有某种内在联系.而在数理逻辑中，前件和后件未必是因果关系，p与q可以无任何内在联系.,在数学或其它自然科学中，“如果p，则q”往往表达的是前件p为真，后件q也为真的推理关系.但在数理逻辑中，作为一种规定，当p为假时，无论q是真是假，均为真。也就是说，只有p为真q为假这一种情况使得复合命题为假.,例1.5将下列命题符号化，并指出各复合命题的真值：,(1)如果336，则雪是白色的.(2)如果336，则雪是白色的.(3)如果336，则雪不是白色的.(4)如果336，则雪不是白色的.,以下命题中出现的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整除.,（5）等价联结词,定义1.5设、为二命题，复合命题“当且仅当”称为与的等价式，记作，符号称作等价联结词.,规定：为真当且仅当与同时为真或同时为假；,的逻辑关系为与互为充分必要条件,注意：p、q的关系可任意。,例1.6将下列命题符号化，将下列命题符号化，并讨论它们的真值：,(1)是无理数当且仅当加拿大位于亚洲.(2)235的充要条件是是无理数.(3)若两圆的面积相等，则它们的半径相等，反之亦然.(4)当王小红心情愉快时，她就唱歌，反之当她唱歌时，一定心情愉快.,3几点说明,以上定义了五种最基本、最常用、也是最重要的联结词将它们组成一个集合,称为一个联结词集.其中为一元联结词，其余的都是二元联结词.,（1）由联结词集中的一个联结词联结一个或两个简单命题组成的的