离散数学(01)

《离散数学(01)》由会员分享，可在线阅读，更多相关《离散数学(01)（60页珍藏版）》请在金锄头文库上搜索。

1、1,办公电话：8 8 4 5 1 1 2 8 住宅电话：8 2 4 9 5 8 7 4 移动电话：1 3 0 9 6 9 8 1 1 8 2 电子邮件：xaL xaL,2,离 散 数 学 方世昌 编著 售 价：20圆 电 话： 029-88202945 手 机：1 3 3 1 9 2 7 1 9 6 0 联系人 ： 刘 杰 由各个班班长统一定购，可优惠20%,3,“离散数学”是一门相对于“连续数学”而命名的数学分支，也叫“不连续的数学”“离散数学”主要研究一些不连续的数学问题。 概率论与数理统计中的随机变量就有离散型和连续型之区分； 离散数学是现代数学的一个重要分支，上世纪八十年代，计算机科学

2、得到迅猛发展，,4,迫切需要一门适合计算机科学的相关数学课程，离散数学由此建立，它是研究离散量的结构及相互关系的学科。它充分描述了计算机科学离散性的特点，是计算机科学与技术的理论基础，所以又称为计算机数学。是计算机、软件专业本科生必修的专业基础课；到硕士研究生段还将开设“组合数学”；到博士研究生段还将开设“计算数学”；,5,“离散数学”一方面给后继课，如“数据结构”、“编译系统”、“操作系统”、“数据库原理”等，提供必要的科学基础；另一方面，通过学习离散数学，培养和提高了同学们的抽象思维和逻辑推理能力，为大家今后继续学习和工作打下坚实的数学基础。 我们选用的这本教材是方世昌著离散数学（第二版）

3、，西安电子科技大学,6,出版社出版。是高等学校工科电子类规划教材精选系列，本书是一本非常有特点的教材。初版出版十三年后，经过全国众多学校的应用，于1996年改进后出第二版；本书力求把握与计算机科学密切相关的问题，通过精选的大量实例深入浅出地介绍了数理逻辑、集合论、二元关系、函数、代数系统、格与布尔代数* 、图论等（我们省掉其中的“无限集合”一章）,7,与计算机科学技术密切相关的课题，既着重于各部分内容之间的紧密联系，又深入探讨各部分内容的概念、理论、算法和实际应用。因而本书既有深度，又有广度，相信学了本书，即能培养思维能力，又能培养理论联系实际的扎实功底 。各章内容大致如下： 第一章 数理逻辑

4、 将形式逻辑符号化后进行逻辑推理，来,8,证明命题的真值，对命题公式运算。 第二章 集合 研究集合基本概念、集合之间的运算关系以及特殊集合。 第三章 二元关系 是研究“关系”的运算、 复合、划分，以及“关系”上的闭包运算等问题。本章内容占全书很大比例。,9,第四章 函数 本章内容我们已经是第三次学习，重点放在函数的映射问题上。 第六章 代数 是研究“代数系统”中元素与运算构成群、半群、环与域的有关问题。完全不同于中学、大一学习过的代数问题,10,第七章 格与布尔代数*(在时间充足时学习) 是研究“代数系统”中“格”以及“特殊格” 的有关问题。是对“代数系统”的进一步研究。 第八章 图论 是研究

5、平面图形中“结点”与“连线”之间的关系，路径的优化、网络、匹配等问题，,11,离散数学课每周上课两次，4学时，安排15周，共60学时。 考核方式：期末笔试占70%，平时作业占30%， 每人准备两个作业本（或者用合页纸），写清班级、学号、姓名。每星期交一次作业，由班长统一收齐交到四楼“专业教研室”。交新作业时领回批改过的作业，按学校规定每次作业将登记，批改三分之一。,12,第一章 数理逻辑 1.1 命 题,逻辑学分为：“形式逻辑”和“数理逻辑”两个部分，他们的最大区别在于， “形式逻辑”允许有二意性而“数理逻辑”决不允许。“数理逻辑” 就是将 “形式逻辑”数学符号化； 例如：陈述句“你吃饱了”在

6、“形式逻辑”中可以理解为：,13,（1）你的确是吃的过饱了 （2）你这个人的行为很无聊，如同吃饱饭撑的。 这就是“形式逻辑”的二意性。一个陈述句可能有两个意识。 命题是逻辑学中的基本单位；陈述语句是逻辑学的形式语言，断言是一个陈述语句。,14,1.1.1 命题 在特定的范围、时间、和空间内具有唯一确定的真假性。这样的陈述语句就是命题； 一个命题是一个或真或假而不能两者都是的断言。如果命题是真, 我们说它的真值为真，如果命题是假, 我们说它的真值是假。,15,例 1 下述都是命题: (a) 今天下雪; (c) 2 是偶数而 3 是奇数; (b) 3+3=6; (d) 陈胜起义那天, 杭州下雨;

7、(e) 2008年人类将登上火星。 以上命题, (a)的真值取决于今天的天气, (b)和(c)是真, (d)已无法查明它的真值, 但它是或真或假, 将它归属于命题。 (e)目前尚未确定其真假, 但它是有真值的, 应归属于命题。,16,例 2 下述都不是命题: (a) x+y4。 (c) 真好啊! (b) x=3。 (d) 你去哪里? (a)和(b)是断言，不是命题, 因为它的真值取决于x和y的值。 (c)和(d)都不是断言, 所以不是命题。自然语句中有陈述句、祈使句、疑问句、和感叹句等，其中能判断对错的只有陈述句。,17,例 3 一个人说:“我正在说谎”。 他是在说谎还是在说真话呢? 如果他讲

8、真话, 那么他所说的是真, 也就是他在说谎。 我们得出结论如果他讲真话, 那么他是在说谎。 另一方面, 如果他是说谎, 那么他说的是假; 因为他承认他是说谎, 所以他实际上是在说真话, 我们得出结论如果他是说谎, 那么他是讲真话。,18,从以上分析, 我们得出他必须既非说谎也不是讲真话。这样, 断言“我正在说谎”事实上不能指定它的真假, 所以不是命题。 这种断言叫悖论。 例：学生甲在教师乙处学习法律，约定一年学成甲支付学费2000圆，同时规定在学生甲和教师乙在同一场官司中，师生分别作为控辩双方，若学生方获胜为学成的标准；,19,学业结束后学生拒绝支付学费，他认为： 教师您可以通过打官司解决，如

9、果教师官司打输了，我自然不支付学费，如果教师官司打嬴了，说明我还没有学成，根据先前的约定，我仍然可以不支付学费。 这也是个悖论的例子，无论教师乙的怎样努力，在签合同时就被学生甲算计进去了。,20,若一个命题已不能分解成更简单的命题, 则这个命题叫原子命题或本原命题。 例 1 中(a) , (b) , (d) , (e)都是本原命题, 但(c)不是, 因为它可写成“2 是偶数”和“3 是奇数”两个命题。 命题和本原命题常用大写字母P , Q , R :表示。 如用P表示“4 是质数”, 则记为 ： P: 4 是质数。,21,第一章 数理逻辑 1.2 命题联结词,1.1.2 命题联结词 命题和原子

10、命题常可通过一些联结词构成新命题, 这种新命题叫复合命题。例如 ： P: 明天下雪, Q: 明天下雨 是两个命题, 利用联结词“不”, “并且”, “或”等可分别构成新命题:,22,“明天不下雪”; “明天下雪并且明天下雨”; “明天下雪或者明天下雨”等。 即 ：“非P”; ; “P并且Q”; “P或Q”等。,23,在代数式x+3 中, “x “, “3” 叫运算对象,代数中的运算对象分有“变量(x)”和“常量(3)”；命题演算同样对原子命题有“变元(P)”和“常元(真、假)”之分； “+”叫运算符, x+3 表示运算结果。在命题演算中, 也用同样术语。联结词就是命题演算中的运算符, 叫逻辑运

11、算符或叫逻辑联结词。 常用的有以下 5 个。,24,1.否定词 设P表示命题, 那么“P不真”是另一命题, 表示为 P, 叫做P的否定, 读做“非P”。 从排中律知: 如果P是假, 则 P是真, 反之亦然。 所以否定词 可以如下表所示定义。归纳为：非真即假，非假即真。,25,这张表叫真值表, 定义运算符的真值表, 指明如何用运算对象的真值, 来决定一个应用运算符的命题的真值。 真值表的左边列出运算对象的真值的所有可能组合, 结果命题的真值列在最右边的一列。为了便于阅读, 我们通常用符号T(true)或 1 代表真, 符号F(false)或 0 代表假。 一般在公式中采用T和F, 在真值表中采用

12、 1 和 0。,26,例 4(a) P: 4 是质数。 P: 4 不是质数。 或 4 是质数, 不是这样。 (b) Q: 这些都是男同学。 Q: 这些不都是男同学。 (翻译成“这些都不是男同学”是错的。 ) 原命题为p，非命题p 一般的理解为： 并非p；即在命题前加“并非”二字。,27,例如： p：上海是一个处处都清洁的城市； p：并非上海是一个处处都清洁的城市； 而不能写成：上海是一个处处都不清洁的城市； 2.合取词 如果P和Q是命题, 那么“P并且Q”也是一命题, 记为PQ, 称为P和Q的合取, 读做“P与Q”或“P并且Q”。 运算符定义如下表所示: 从真值表可知PQ是真当且仅当P和Q俱真

13、。,28,归纳为： p，q同真时pq为真，其余为假。 类似集合运算中的： “交 ，”,例5 P: 王华的成绩很好, Q: 王华的品德很好。 PQ: 王华的成绩很好并且品德很好。,29,3. 析取词 如果P和Q是命题, 则“P或Q”也是一命题, 记作PQ, 称为P和Q的析取, 读做“P或Q”。运算符定义如右表所示。从真值表可知PQ为真, 当且仅当P或Q至少有一为真。 归纳为： p，q同假时 p q 为假，其余为真。 看的出：合取与析取有对偶的关系。,30,析取类似集合运算中的： “并 ，”,例 6 (a) P: 今晚我写字, Q: 今晚我看书。 PQ: 今晚我写字或看书,31,(b) P: 今年

14、是闰年; Q: 今年她生孩子。 PQ: 今年是闰年或者今年她生孩子。 逻辑运算符可以将两个无关的命题连接成一新命题。 “或”字常见的含义有两种: 一种是“可兼或”, 如上例中的或, 它不排除今晚既看书又写字这种情况。,32,一种是“排斥或”, 例如“人固有一死, 或重于泰山, 或轻于鸿毛”中的“或”, 它表示非此即彼, 不可兼得。 运算符表示可兼或, 排斥或以后用另一符号表达。 联结词是自然语言中的“或”、“或者”的逻辑抽象，而在自然语言中，“或”是多义的，可列表如下：,33,“可兼或”与“排斥或” 的联系与区别,34,4. 蕴涵词(涵常简写作含) 如果P和Q是命题, 那么“P蕴含Q”也是命题

15、, 记为PQ, 称为蕴含式, 读做“P蕴含Q”或“如果P, 那么Q”，是典型的“因果关系”。 运算对象P叫做前提 , 假设或前件, 而Q叫做结论或后件。逻辑推理经常用到这种“因果关系”；运算符定义如下表所示。命题PQ是假, 当且仅当P是真而Q是假。,35,归纳为：条件为真，结论为假时pq 为假，其余为真。 我们经常把“”（条件命题）简称为： 单条件命题。以区别后面的双条件命题。,36,例 7 (a) P: 天不下雨, Q: 草木枯黄。 PQ: 如果天不下雨, 那么草木枯黄。 (b) R: G是正方形, S: G的四边相等。 RS: 如果G是正方形, 那么G的四边相等。 (c) W: 桔子是紫色

16、的, V: 大地是不平的WV: 如果桔子是紫色的, 那么大地是不平的。,37,在日常生活中用蕴含式来断言前提和结论之间的因果或实质关系, 如上例(a)和(b), 这样的蕴含式叫形式蕴含, 然而, 在命题演算中, 一个蕴含式的前提和结论并不需要有因果和实质联系, 这样的蕴含式叫实质蕴含, 如上例(c)中, 桔子的颜色和大地的外形之间没有因果和实质关系存在, 但蕴含式WV是真,38,因为前提是假而结论是真,这就是我们常说的”善意推断”。即：条件为假时，条件命题永真。 例如：如果太阳从西边出来，那么每个星期我们就休息5天。 这个命题的条件是假的，无论后面的结论是什么，整个条件命题是真的。,39,蕴含式PQ可以用多种方式陈述: “若P, 则Q” “P是Q的充分条件” “Q是P的必要条件”