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