命题与联结词

1、离 散 数 学（ Discrete Mathematics ）1课程介绍一、简史“离散数学”是一门相对于“连续数学”而命名的数学分支。 产生于数学游戏(如一笔画、过渡、组合、计数等)，分散于各个分支，计算机的产生推动了其形成和发展。二、知识模块数理逻辑集合论和关系图论初步代数系统三、学习要求1.首先要精确严格地掌握好概念和术语、理解基本定理的本质；2. 独立完成每一次作业，每次作业完成之后，能自觉地归纳出其中用到的基本解题方法；3.自学相关参考教材。2 数理逻辑是用数学方法研究思维规律的一门学科. 所谓数学方法是指:用一套数学的符号系统来描述和处理思维的形式与规律. 因此, 数理逻辑又称为符号

2、逻辑.第一部分 数理逻辑3第一章 命题逻辑基本概念第二章 命题逻辑等值演算 第四章 一阶逻辑基本概念第三章 命题逻辑的推理理论第五章 一阶逻辑等值演算与推理4第一章 命题逻辑基本概念第1节 命题与联结词第2节 命题公式及其赋值5一、命题的概念二、复合命题与联结词第1节 命题与联结词6一、命题的概念1 命题：能判断真假的陈述句称为命题。 （1） 真值 : 命题判断真假的结果真值只取两个值：真或假。（2）真命题：真值为真的命题； 假命题：真值为假的命题。（4） 判断命题分两步：是否为陈述句 是否有唯一真值（3）任何命题的真值都是唯一的。 7例1.1 判断下列句子是否为命题(1) 4是素数。(2)

3、是无理数。(3) x大于y。 (4) 月球上有冰。 (5) 2100年元旦是晴天。 (6) 大于 吗？ (7) 请不要吸烟！ (8) 这朵花真美丽啊！ (9) 我正在说假话。8 解: 本题的(9)个句子中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因而这3个句子都不是命题。剩下的6个句子都是陈述句，(3)无确定的真值：根据x,y的不同取值情况它可真可假，即无唯一的真值，因而不是命题。若(9)的真值为真，即“我正在说假话”为真，也就是“我正在说真话”，则又推出(9)的真值应为假；反之，若(9)的真值为假，即“我正在说假话”为假，也就是“我正在说假话”，则又推出(9)的真值应为真。于是(9)

4、既不为真又不为假，因此它不是命题。9像(9)这样由真推出假，又由假推出真的陈述句称为悖论。凡是悖论都不是命题。本例中，只有(1)，(2)，(4)，(5)是命题。(1)为假命题，(2)为真命题。虽然今天我们不知道(4)，(5)的真值，但它们的真值客观存在，而且是唯一的，将来总会知道(4)的真值，到2100年元旦(5)的真值就真相大白了。 注：真值唯一与现在能否确定是不同的!102 命题和真值的符号化 （1）用真值来描述命题是“真” 还是“假”，分别用“1”和“0”表示（或用“F”和“T”表示） （2）命题用小写的英文字母 、 、 、 或者带下标 的小写的字母 、 、 、 来表示.11二、复合命题

5、与联结词各种论述和推理中，出现的命题多数比例1.1中的命题更加复杂。例1.2 下列句子全是命题 是有理数是不对的;2 是偶素数;2或4是素数; 如果2是素数则3也是素数;2 是素数当且仅当3是素数. 这些命题是通过诸如“或”“如果，则”等连词联结而成.121 命题分类 （1） 简单（原子）命题 ：由简单句（不含联结词的陈述句）形成的命题； （2） 复合（分子）命题 ：由一个或几个简单句通过联结词的联接而构成的命题.132 联结词（1） 否定联结词定义1.1 设为命题，复合命题“非（或“的否定”）称为的否定式，记作，符号称作否定联结词.（一元复合命题）规定： 为真当且仅当为假命题取值为真时，命题

6、取值为假；命题取值为假时，命题取值为真14（2） 合取联结词定义1.2 设、 为二命题，复合命题“并且 ”（或“与”）称为与的合取式，记作符号称作合取联结词.规定： 为真当且仅当与同时为真15使用合取联结词是要注意两点： 自然语言的灵活性：自然语言中的“既又”、“不但而且”、“虽然但是”、“一面一面”等联结词基本含义是“和”、“并且” ，都可符号化； 多义性:不要见到“与”或“和”就使用联结词（有时“和”不能符号化为） pq 中p与q在自然语言上未必有某种被认可的联系（只是形式化处理的需要）16例1. 将下列命题符号化(1) 吴颖既用功又聪明.(2) 吴颖不仅用功而且聪明.(3) 吴颖虽然聪明

7、，但不用功.(4) 张辉和王丽都是三好学生.(5) 张辉与王丽是同学.17解： 首先将原子命题符号化： p: 吴颖用功. q: 吴颖聪明. r: 张辉是三好学生. s: 王丽是三好学生. t: 张辉与王丽是同学.（1）到(4)都是复合命题，它们使用的联结词表面看来各不相同，但都是合取联结词，都应符号化为，(1)到(4)分别符号化为：pq，pq，qp，rs .（5）是原子命题，符号化为t .18（3） 析取联结词定义1.3 设、 为二命题，复合命题“或” 称为与的析取式，记作，符号称作析取联结词.规定： 为假当且仅当与同时为假；等价于当且仅当和至少一个取值为真时， 取值为真19注意： 自然语言中

8、的“或”有二义性：相容“或”（可兼）；排斥“或”(排异). pq 中p与q的关系可任意.例1.4 将下列命题符号化(1) 张晓静爱唱歌或爱听音乐.(2)张晓静是江西人或安徽人.(3) 张晓静只能挑选202或203房间.20 解： 在解题时，先将原子命题符号化。 (1) p：张晓静爱唱歌. q：张晓静爱听音乐 (1)中“或”为相容或，符号化为pq. (2) r：张晓静是江西人. s：张晓静是安徽人. (2)中“或”应为排斥或，但 r 与 s 不能同时为真，因而也可以符号化为 rs.21 (3) t：张晓静挑选202房间. u：张晓静挑选203房间. 由题意可知，(3)中“或”应为排斥或. t，u

9、的联合取值情况有四种：同真，同假，一真一假(两种情况). 如果也符号化为tu，张晓静就可能同时得到两个房间，这违背题意. 因而不能符号化为 tu. 如何达到只能挑一个房间的要求呢？可以使用多个联结词，符号化为 (tu)(tu). 此复合命题为真当且仅当t，u中一个为真，一个为假，它准确地表达了(3)的要求. 当t为真u为假时，张晓静得到202房间，t为假u为真时，张晓静得到203房间，其它情况下，她得不到任何房间.22（4） 蕴涵联结词定义1.4 设、 为二命题，复合命题“如果则” 称为与的蕴涵式，记作，符号称作蕴涵联结词.规定： 为假当且仅当为真为假；的逻辑关系为是的必要条件、是的充分条件2

10、3注意： 在自然语言里，特别是在数学中，q是p的必要条件有许多不同的叙述方式。例如， “如果p，那么q”， “因为p，所以q”， “p仅当q”， “只有q才p”， “除非q才p”， “除非q，否则非p” ,以上各种叙述方式表面看来有所不同，但都表达的是q是p的必要条件，因而所用联结词均应符号化为 ，上述各种叙述方式都应符号化为 . “只要p，就q”， 24注意： 在自然语言里，“如果p，则q”中的前件p与后件q往往具有某种内在联系. 而在数理逻辑中，前件和后件未必是因果关系，p与q可以无任何内在联系. 在数学或其它自然科学中，“如果p，则q”往往表达的是前件p为真，后件q也为真的推理关系. 但

11、在数理逻辑中，作为一种规定，当p为假时，无论q是真是假， 均为真。也就是说，只有p为真q为假这一种情况使得复合命题 为假 . 25例1.5 将下列命题符号化，并指出各复合命题的真值：(1) 如果 336 ，则雪是白色的.(2) 如果 336 ，则雪是白色的.(3) 如果 336 ，则雪不是白色的.(4) 如果 336 ，则雪不是白色的.26以下命题中出现的 a 是给定的一个正整数:(5)只要a 能被 4 整除，则 a 一定能被 2 整除.(6) a 能被4 整除，仅当 a 一定能被 2 整除.(7) 除非 a 能被 2 整除， a 才能被 4 整除.(8) 除非 a 能被 2 整除，否则 a

12、不能被 4 整除.(9) 只有a 能被 2 整除， a 才能被 4 整除.(10) 只有a能被 4 整除， a 才能被 2 整除.27（5）等价联结词定义1.5 设、 为二命题，复合命题“ 当且仅当” 称为与的等价式，记作 ，符号称作等价联结词.规定： 为真当且仅当与同时为真或同时为假；的逻辑关系为与互为充分必要条件注意：p、q的关系可任意。28例1.6 将下列命题符号化，将下列命题符号化，并讨论它们的真值：(1) 是无理数当且仅当加拿大位于亚洲.(2) 235 的充要条件是 是无理数.(3) 若两圆的面积相等，则它们的半径相等，反之亦然.(4) 当王小红心情愉快时，她就唱歌，反之当她唱歌时，一定心情愉快.293 几点说明 以上定义了五种最基本、最常用、也是最重要的联结词 将它们组成一个集合 , 称为一个联结词集. 其中 为一元联结词，其余的都是二元联结词. （1）由联结词集 中的一个联结词联结一个或两个简单命题组成的的复