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

离 散 数 学 （ Discrete Mathematics ）,课程介绍,一、简史 “离散数学”是一门相对于“连续数学”而命名的数学分支。 产生于数学游戏(如一笔画、过渡、组合、计数等)，分散于各个分支，计算机的产生推动了其形成和发展。 二、知识模块 数理逻辑 集合论和关系 图论初步 代数系统 三、学习要求 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）由联结词集 中的一个联结词联结一个或两个