离散数学全册配套完整精品课件

1、离散数学全册配套离散数学全册配套完整精品课件完整精品课件2021-8-92021-8-9计算机应用技术研究所计算机应用技术研究所22离散数学离散数学Discrete Mathematics2021-8-9计算机应用技术研究所计算机应用技术研究所3& 绪绪 论论 离散数学课程性质离散数学课程性质 离散数学课程内容离散数学课程内容 学习此课程的方法学习此课程的方法2021-8-9计算机应用技术研究所计算机应用技术研究所4&课程性质课程性质 p什么是数学什么是数学p数学的价值数学的价值p离散数学与连续数学离散数学与连续数学2021-8-9计算机应用技术研究所计算机应用技术研究所5&课程性质课程性质

2、1818世纪（机械）工业革命的基础是物理世纪（机械）工业革命的基础是物理学、力学，而物理学的基础就是学、力学，而物理学的基础就是高等数学、高等数学、微积分。微积分。 现代的信息社会是以计算机科学技术为现代的信息社会是以计算机科学技术为基础，基础，那么计算机科学技术的基础又是什么那么计算机科学技术的基础又是什么呢？还是微积分？呢？还是微积分？ 2021-8-9计算机应用技术研究所计算机应用技术研究所6&课程性质课程性质 计算机的特点：计算机的特点： 第一、第一、计算机是一个离散结构，只能处理离散计算机是一个离散结构，只能处理离散的或离散化了的数量关系。的或离散化了的数量关系。 第二、所使用的求解

3、方法必须是构造性的，而第二、所使用的求解方法必须是构造性的，而且要在有限的步骤内完成，具备可行性。且要在有限的步骤内完成，具备可行性。 2021-8-9计算机应用技术研究所计算机应用技术研究所7&课程性质课程性质因此，需要一门专门研究和讨论离离散量的结构与关系的数学散量的结构与关系的数学，为计算机学科提供必须的理论基础和应用工具。这就是离散数学离散数学或计算机数学计算机数学。 2021-8-9计算机应用技术研究所计算机应用技术研究所8&课程性质课程性质离散数学离散数学 u 既古老又现代的数学学科既古老又现代的数学学科u 研究对象是离散量之间的结构与关系研究对象是离散量之间的结构与关系u 是集合

4、论、数理逻辑、图论、数论、组合是集合论、数理逻辑、图论、数论、组合计算、代数结构等多个数学分支的集成计算、代数结构等多个数学分支的集成2021-8-9计算机应用技术研究所计算机应用技术研究所9&课程性质课程性质从软件方面的课程体系看：从软件方面的课程体系看： 程序设计语言：机器语言程序设计语言：机器语言汇编语言汇编语言高级面向过程高级面向过程语言语言面向对象语言面向对象语言智能语言智能语言 ； 系统软件：如操作系统，单用户系统软件：如操作系统，单用户 多用户多用户 网络操网络操作系统，作系统，；这些发展都依赖于离散数学离散数学、数据结构、算法设计与分析、编译原理、操作系统、数据库原理、软件工程

5、、计算机网络等课程知识。 其中离散数学离散数学是基础，其它课程都要用到离散数学中的概念、思想和方法 。 2021-8-9计算机应用技术研究所计算机应用技术研究所10&课程性质课程性质从硬件方面的课程体系看：从硬件方面的课程体系看：电路设计、嵌入式系统设计与开发、计算机控电路设计、嵌入式系统设计与开发、计算机控制系统设计与开发制系统设计与开发 都依赖于离散数学离散数学、数字电路、数字逻辑、计算机组成原理、微机原理、计算机控制、计算机系统结构。 其中离散数学离散数学是基础，其它课程都要用到离散数学中的概念、思想和方法 。 2021-8-9计算机应用技术研究所计算机应用技术研究所11&课程性质课程性

6、质结结 论论 1818世纪英国工业革命的基础是物理学，而物理学世纪英国工业革命的基础是物理学，而物理学的基础就是高等数学，就是数学分析、微积分。的基础就是高等数学，就是数学分析、微积分。 现代的信息社会是以计算机科学技术为基础，而现代的信息社会是以计算机科学技术为基础，而计算机科学技术的基础就是离散数学。计算机科学技术的基础就是离散数学。 离散数学在信息社会中的作用就相当于以前工业离散数学在信息社会中的作用就相当于以前工业革命时微积分的作用革命时微积分的作用, ,是计算机及相关学科的专业核是计算机及相关学科的专业核心基础课程。心基础课程。2021-8-9计算机应用技术研究所计算机应用技术研究所

7、12& 绪绪 论论 离散数学课程性质离散数学课程性质 离散数学课程内容离散数学课程内容 学习此课程的方法学习此课程的方法2021-8-9计算机应用技术研究所计算机应用技术研究所13&课程内容课程内容离散数学由多个数学分支组成，每个分支可离散数学由多个数学分支组成，每个分支可以看成是一个相对独立的研究领域。以看成是一个相对独立的研究领域。 各个数学分支从不同的角度出发，研究各种离各个数学分支从不同的角度出发，研究各种离散量之间的结构和关系。散量之间的结构和关系。 同时，这些数学分支之间也存在着密切的联系，同时，这些数学分支之间也存在着密切的联系，构成一个完整的知识体系。构成一个完整的知识体系。2

8、021-8-9计算机应用技术研究所计算机应用技术研究所14&课程内容课程内容知识体系：知识体系：抽象代数结构抽象代数结构组合计算模组合计算模型与结构型与结构图离散结构图离散结构树离散结构树离散结构关系离散结构关系离散结构函数离散结构函数离散结构自然数的自然数的离散结构离散结构集合代数集合代数逻辑代数逻辑代数2021-8-9计算机应用技术研究所计算机应用技术研究所15数理逻辑数理逻辑集集 合合 论论图图 论论代数系统代数系统命题逻辑命题逻辑谓词逻辑谓词逻辑集合集合关系关系图的基本概念图的基本概念几个特殊图几个特殊图代数系统的基本概念代数系统的基本概念特殊代数系统特殊代数系统教学内容教学内容函数函

9、数图的连通性图的连通性代数系统的同态与同构代数系统的同态与同构&课程内容课程内容2021-8-9计算机应用技术研究所计算机应用技术研究所16&课程内容课程内容 能力培养：能力培养： 形式化的数理逻辑思维能力形式化的数理逻辑思维能力 离散结构建模与应用能力离散结构建模与应用能力 计算与算法思维能力计算与算法思维能力 数学抽象思维与概括能力数学抽象思维与概括能力 2021-8-9计算机应用技术研究所计算机应用技术研究所17& 绪绪 论论 离散数学课程性质离散数学课程性质 离散数学课程内容离散数学课程内容 学习此课程的方法学习此课程的方法2021-8-9计算机应用技术研究所计算机应用技术研究所18&

10、学习方法学习方法u 课程特点课程特点 内容广博，概念多，定理多，抽象程内容广博，概念多，定理多，抽象程度高，给学习带来一定难度。度高，给学习带来一定难度。u 学习方法学习方法 强调：逻辑性、抽象性强调：逻辑性、抽象性 注重：概念、方法与应用注重：概念、方法与应用 2021-8-9计算机应用技术研究所计算机应用技术研究所1919u 离散数学及其应用离散数学及其应用（第（第2 2版），版）， 傅彦、顾小丰、傅彦、顾小丰、王庆先、刘启和王庆先、刘启和编著编著，高等教育出版社，高等教育出版社，2013.62013.6 国家精品课程主讲教材，有配套解题指导；国家精品课程主讲教材，有配套解题指导；u 离散

11、数学教程离散数学教程，王元元，沈克勤，李拥新、贺，王元元，沈克勤，李拥新、贺汛汛编著编著，高等教育出版社，高等教育出版社，2010.7 2010.7 国家精品课程主讲教材，有配套解题指导。国家精品课程主讲教材，有配套解题指导。&课程教材课程教材2021-8-9计算机应用技术研究所计算机应用技术研究所2020u Discrete Mathematics and Its Applications， Kenneth H.Rosen著，著，Sixth Edition （有中文版），机（有中文版），机械工业出版社械工业出版社 离散数学领域的经典教材，内容通俗易懂，应用离散数学领域的经典教材，内容通俗易懂

12、，应用例子较多，全世界很多知名的院校都曾使用。例子较多，全世界很多知名的院校都曾使用。u 离散数学教程离散数学教程，耿素云、屈婉玲、王捍贫编著，耿素云、屈婉玲、王捍贫编著，北京大学出版社。北京大学出版社。 国家精品课程主讲教材，有较好的深度和广度，国家精品课程主讲教材，有较好的深度和广度，适合适合160学时以上的多学时课程，有配套解题指导。学时以上的多学时课程，有配套解题指导。&课程教参课程教参2021-8-9计算机应用技术研究所计算机应用技术研究所21本节内容到此结束本节内容到此结束2021-8-9计算机应用技术研究所计算机应用技术研究所2222离散数学离散数学Discrete Mathem

13、atics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2021-8-9计算机应用技术研究所计算机应用技术研究所23第一章第一章 集合论初步集合论初步2021-8-9计算机应用技术研究所计算机应用技术研究所24& 集合论初步集合论初步 数学危机与集合论数学危机与集合论 集合的基本知识集合的基本知识 无限集合及其性质无限集合及其性质 集合代数的应用集合代数的应用2021-8-9计算机应用技术研究所计算机应用技术研究所25&第一次数学危机第一次数学危机毕达哥拉斯：毕达哥拉斯： 万物皆可由整数和分数表示；整数为间隔万物皆可由整数和分数表示；整数为间隔为单位长的点，分数

14、为单位长的点，分数p/qp/q是将单位长是将单位长q q等分，取其等分，取其中的中的p p个等分个等分。 但是，有一天毕达哥拉斯自己痛苦地证明了 不是有理数希帕苏斯悖论希帕苏斯悖论22021-8-9计算机应用技术研究所计算机应用技术研究所26&第二次数学危机第二次数学危机关于微积分里的关于微积分里的“无穷小无穷小”是什么？是什么？牛顿的解释：牛顿的解释： 16691669年说它是一种常量；年说它是一种常量； 16711671年又说它是一个趋于零的变量；年又说它是一个趋于零的变量； 16761676年又说它是年又说它是“两个正在消逝的量的最终比两个正在消逝的量的最终比” 大主教贝克莱讽刺它是：大

15、主教贝克莱讽刺它是： “ “消失了的量的鬼魂消失了的量的鬼魂”（贝克莱悖论）（贝克莱悖论）2021-8-9计算机应用技术研究所计算机应用技术研究所27&第二次数学危机第二次数学危机 直到直到1919世纪世纪2020年代，从波尔查诺、阿贝尔、柯西、年代，从波尔查诺、阿贝尔、柯西、狄里赫利等人的工作开始，到威尔斯特拉斯、狄德金狄里赫利等人的工作开始，到威尔斯特拉斯、狄德金和和康托康托的工作结束，中间经历了半个多世纪，解决了的工作结束，中间经历了半个多世纪，解决了希帕苏斯悖论和贝克莱悖论，为微积分和整个数学奠希帕苏斯悖论和贝克莱悖论，为微积分和整个数学奠定了一个严格的基础。定了一个严格的基础。 20

16、21-8-9计算机应用技术研究所计算机应用技术研究所28&第二次数学危机第二次数学危机 经过第一、二次数学危机，人们把数学基础理论的经过第一、二次数学危机，人们把数学基础理论的无矛盾性，归结为无矛盾性，归结为集合论集合论的无矛盾性，的无矛盾性，集合论集合论已成为整个已成为整个数学的逻辑基础，数学这座富丽堂皇的大厦就算竣工了。数学的逻辑基础，数学这座富丽堂皇的大厦就算竣工了。 法国著名数学家法国著名数学家庞加莱庞加莱（1854185419121912）于）于19001900年在年在巴黎召开的国际数学家会议上夸耀道：巴黎召开的国际数学家会议上夸耀道：“现在可以说，现在可以说，（数学）绝对的严密性是

17、已经达到了（数学）绝对的严密性是已经达到了”。 2021-8-9计算机应用技术研究所计算机应用技术研究所29&第三次数学危机第三次数学危机 1901 1901年年5 5月，罗素提出月，罗素提出罗素悖论罗素悖论，宣布了一条惊宣布了一条惊人的消息：集合论是自相矛盾的，并不存在什么绝对的严人的消息：集合论是自相矛盾的，并不存在什么绝对的严密性！密性！ 罗素悖论动摇了整个数学的根基罗素悖论动摇了整个数学的根基! ! 弗雷格在收到罗素的信之后，在他刚要出版的弗雷格在收到罗素的信之后，在他刚要出版的算术的算术的基本法则基本法则第第2卷末尾写道：卷末尾写道：一位科学家不会碰到比这更一位科学家不会碰到比这更难

18、堪的事情了，即在工作完成之时，它的基础垮掉了，当难堪的事情了，即在工作完成之时，它的基础垮掉了，当本书等待印出的时候，罗素先生的一封信把我置于这种境本书等待印出的时候，罗素先生的一封信把我置于这种境地地。于是终结了近。于是终结了近12年的刻苦钻研年的刻苦钻研。 2021-8-9计算机应用技术研究所计算机应用技术研究所30&第三次数学危机第三次数学危机 策梅罗策梅罗ZermeloZermelo提出公理化集合提出公理化集合论来对朴素集合论进行限制，解决了论来对朴素集合论进行限制，解决了罗素悖论问题。罗素悖论问题。2021-8-9计算机应用技术研究所计算机应用技术研究所31&第三次数学危机第三次数学

19、危机 u 1930年，哥德尔Godel宣布了不完备定理，这是一个具有哲学意义的普适定理： 无矛盾的系统不完备，完备的系统却是存在矛盾的无矛盾的系统不完备，完备的系统却是存在矛盾的u 结论是： “以有限把握无穷以有限把握无穷”的努力不可能成功，的努力不可能成功，对整个数学形式化的努力是注定要失败的。对整个数学形式化的努力是注定要失败的。2021-8-9计算机应用技术研究所计算机应用技术研究所32&第三次数学危机第三次数学危机两个问题：两个问题： 既然人类思维不可能完全消除错误，那么正确与错既然人类思维不可能完全消除错误，那么正确与错误的边界又在哪里呢？误的边界又在哪里呢？ 可计算理论与图灵机的诞

20、生可计算理论与图灵机的诞生 人类思维似乎不能完全把握这个世界了，那么机器人类思维似乎不能完全把握这个世界了，那么机器思维能做得更好么？思维能做得更好么？ 计算机与人工智能的诞生计算机与人工智能的诞生2021-8-9计算机应用技术研究所计算机应用技术研究所33本节内容到此结束本节内容到此结束2021-8-9计算机应用技术研究所计算机应用技术研究所34& 集合论初步集合论初步2021-8-9计算机应用技术研究所计算机应用技术研究所35& 集合的基本知识集合的基本知识2021-8-9计算机应用技术研究所计算机应用技术研究所36一、集合的基本概念一、集合的基本概念2021-8-9计算机应用技术研究所计

21、算机应用技术研究所37集合论集合论(set theory)(set theory)十九世纪数学最伟大成就十九世纪数学最伟大成就集合论体系集合论体系l朴素集合论朴素集合论l公理集合论公理集合论创始人康托创始人康托(Cantor)(Cantor) Georg Ferdinand Philip Georg Ferdinand Philip Cantor 1845 - 1918Cantor 1845 - 1918，德国数，德国数学家学家2021-8-9计算机应用技术研究所计算机应用技术研究所38&在计算机领域的作用在计算机领域的作用2021-8-9计算机应用技术研究所计算机应用技术研究所39&集合的描

22、述（定义）集合的描述（定义）什么是集合：什么是集合：l 在朴素集合论中不能精确定义；在朴素集合论中不能精确定义；l 在公理集合论中通过公理来定义。在公理集合论中通过公理来定义。（SETSET）由指定范围内满足给定由指定范围内满足给定条件的所有对象聚集在一起构成。条件的所有对象聚集在一起构成。中国中国所有真皮沙发所有真皮沙发的聚集的聚集指定指定范围范围所有所有对象对象指定范围内的每一个对象称为这指定范围内的每一个对象称为这个集合的个集合的或或2021-8-9计算机应用技术研究所计算机应用技术研究所40元素与集合之间的元素与集合之间的“属于关系属于关系”是是“明确明确”的。的。 对某个集合对某个集

23、合A A和元素和元素a a来说，来说， a a属于集合属于集合A A，记为，记为a a A A 或者或者 a a不属于集合不属于集合A A，记为，记为a a A A 两者必居其一且仅居其一两者必居其一且仅居其一。&集合与元素的关系集合与元素的关系2021-8-9计算机应用技术研究所计算机应用技术研究所41 【例例】（罗素悖论）在一个很僻静的孤岛上，住着罗素悖论）在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些不自己理发的人理发。那么，谁给些并且只给那些不自己理发的人理发。那么，谁给这位理发师理发？这位理发师理发？【

24、解解】 设设C Cx|xx|x是不给自己理发的人是不给自己理发的人 ，b b是这位是这位理发师理发师 如如 b b C C，则，则 b b C C； 如如 b b C C，则，则 b b C C。&集合与元素的关系集合与元素的关系2021-8-9计算机应用技术研究所计算机应用技术研究所42&集合的记法集合的记法 通常用带或者不带标号的大写字母通常用带或者不带标号的大写字母A A、B B、C C、.、A A1 1、 B B1 1 、C C1 1 、.、X X、Y Y、Z Z、.表示表示； 通常用带或者不带标号的小写字母通常用带或者不带标号的小写字母a a、b b、c c、.、a a1 1、 b

25、b1 1 、c c1 1 、.、x x、y y、z z、.表示集合中的表示集合中的。2021-8-9计算机应用技术研究所计算机应用技术研究所43集合的表示方法通常有：集合的表示方法通常有：枚举法（显示法）枚举法（显示法）隐式法（叙述法）隐式法（叙述法） 归纳法归纳法 递归指定法递归指定法 文氏图法文氏图法&集合的表示法集合的表示法2021-8-9计算机应用技术研究所计算机应用技术研究所44&集合的表示法集合的表示法枚举法（显示法）：枚举法（显示法）：列出集合中全部元素或部分元素的方法叫列出集合中全部元素或部分元素的方法叫枚举法枚举法【例例】 指出下列集合的表示方法指出下列集合的表示方法适用场景

26、：适用场景：u一个集合仅含有限个元素一个集合仅含有限个元素u一个集合的元素之间有明显关系一个集合的元素之间有明显关系 2021-8-9计算机应用技术研究所计算机应用技术研究所45&集合的表示法集合的表示法枚举法的优缺点：枚举法的优缺点：u 是一种显式表示法是一种显式表示法u 优点：优点：具有透明性具有透明性u 缺点：缺点：在表示具有某种特性的集合或集合中元在表示具有某种特性的集合或集合中元素过多时受到了一定的局限，而且，从计算机的素过多时受到了一定的局限，而且，从计算机的角度看，显式法是一种角度看，显式法是一种“静态静态”表示法，如果一表示法，如果一下子将这么多的下子将这么多的“数据数据”输入

27、到计算机中去，那输入到计算机中去，那将占据大量的将占据大量的“内存内存”。2021-8-9计算机应用技术研究所计算机应用技术研究所46&集合的表示法集合的表示法叙述法（隐式法）：叙述法（隐式法）：通过刻画集合中通过刻画集合中元素所具备的某种特性元素所具备的某种特性来表示集来表示集合的方法称为合的方法称为描述法描述法。表示方法表示方法：A Ax|x|P(x)P(x) 适用场景：适用场景：含有很多或无穷多个元素；集合的元含有很多或无穷多个元素；集合的元素之间有容易刻画的共同特征。素之间有容易刻画的共同特征。突出优点：突出优点：不要求列出集合中全部元素，只要给不要求列出集合中全部元素，只要给出集合中

28、元素的特性。出集合中元素的特性。X X所具有的所具有的性质性质p p2021-8-9计算机应用技术研究所计算机应用技术研究所47&集合的表示法集合的表示法描述法（隐式法）：描述法（隐式法）：A = x|xA = x|x是是“discrete mathematicsdiscrete mathematics”中的中的所有字母所有字母 ； Z = x|xZ = x|x是一个整数是一个整数 ； S = x|xS = x|x是整数，并且是整数，并且x x2 21 = 01 = 0； Q Q+ + = x|x = x|x是一个正有理数是一个正有理数 。【例例】 指出下列集合的表示方法指出下列集合的表示方法

29、2021-8-9计算机应用技术研究所计算机应用技术研究所48归纳法：归纳法：归纳法归纳法注意：第一部分注意：第一部分和和第二部分第二部分指出一个集合指出一个集合至少包括至少包括的元素的元素，第三部分第三部分指出一个集合指出一个集合至多要包含的元素至多要包含的元素&集合的表示法集合的表示法2021-8-9计算机应用技术研究所计算机应用技术研究所49归纳法：归纳法：【例例】集合集合A A按如下方式定义，试指出其定义方式。按如下方式定义，试指出其定义方式。&集合的表示法集合的表示法2021-8-9计算机应用技术研究所计算机应用技术研究所50递归指定集合法：递归指定集合法：【例例】 设设 a a0 0

30、 1 1， a ai+1 i+1 2a2ai i （i i 0 0） 定义定义S Saa0 0 ，a a1 1 ，a a2 2 ，.aak k | k| k 0 0 ，试写出集合试写出集合S S中的所有元素。中的所有元素。 &集合的表示法集合的表示法2021-8-9计算机应用技术研究所计算机应用技术研究所51文氏图解法文氏图解法AA&集合的表示法集合的表示法2021-8-9计算机应用技术研究所计算机应用技术研究所52、互异性互异性集合中的元素都是不同的，凡是相同的元素，集合中的元素都是不同的，凡是相同的元素，均视为同一个元素。均视为同一个元素。例如：1,1,2=1,22、可分性性集合中的元素能

31、够明确加以集合中的元素能够明确加以“区分的区分的”对象；对象；3、无序性无序性集合中的元素是没有顺序的。集合中的元素是没有顺序的。例如：2,1=1,21 集合的三大特征集合的三大特征&集合之间的关系集合之间的关系2021-8-9计算机应用技术研究所计算机应用技术研究所53设设E=x|(x-1)(x-2)(x-3)=0, xRE=x|(x-1)(x-2)(x-3)=0, xR F=x|(x Z F=x|(x Z+ +) )且且(x(x2 212)12)。 试指出集合试指出集合E E和和F F中的元素。中的元素。&集合之间的关系集合之间的关系2 2 2021-8-9计算机应用技术研究所计算机应用技

32、术研究所54&集合之间的关系集合之间的关系 自反性：自反性：对任何集合A，有A=A。 传递性：传递性：对任何集合A、B、C，如果有A=B且 B=C ，则A=C。 对称性：对称性：对任何集合A、B，如果有A=B，则B=A。2021-8-9计算机应用技术研究所计算机应用技术研究所55【定义定义 设设A,B是任意两个集合是任意两个集合，如果 B的每个元素都是的每个元素都是A的元素的元素， 则称则称B是是A的的(Subset)，亦称A包含包含B，或称B被被A包含包含。记作A B 或B A。 &集合之间的关系集合之间的关系上述包含定义可用数学语言描述为：上述包含定义可用数学语言描述为： B B A A对

33、任意对任意x x，如，如x x B B，则，则x x A A。2021-8-9计算机应用技术研究所计算机应用技术研究所56&集合之间的关系集合之间的关系2021-8-9计算机应用技术研究所计算机应用技术研究所57&集合之间的关系集合之间的关系 自反性：自反性：对任何集合A，有A A。 传递性：传递性：对任何集合A、B、C，如果有A B且 B C ，则A C。 反对称性：反对称性：对任何集合A、B，如果有A B且B A，则A=B。2021-8-9计算机应用技术研究所计算机应用技术研究所58【定义定义】设设A,B是任意两个集合，如果是任意两个集合，如果B A并且并且AB则称则称B是是A的的(Pro

34、per Subset )，记作，记作B A。真子集的符号描述为：真子集的符号描述为：B B A A 对任意对任意x x，如，如x x B B，则，则x x A A，并且存在并且存在y y A A，但是，但是y y B B&集合之间的关系集合之间的关系BA2021-8-9计算机应用技术研究所计算机应用技术研究所59【例例】 试判断下列集合之间的包含关系。试判断下列集合之间的包含关系。（1 1）a, ba, b和和a, b, c, da, b, c, d；（2 2）a, b, c, da, b, c, d和和a, b, c, da, b, c, d。&集合之间的关系集合之间的关系【例例】 设设A

35、= a是一个集合，是一个集合，B = a, a，试问试问AB和和A B同时成立吗？同时成立吗？2021-8-9计算机应用技术研究所计算机应用技术研究所60&集合之间的关系集合之间的关系2021-8-9计算机应用技术研究所计算机应用技术研究所61二、几种特殊的集合二、几种特殊的集合2021-8-9计算机应用技术研究所计算机应用技术研究所62空集可以符号化为：空集可以符号化为： = x|xx = x|xx空集是客观存在的。空集是客观存在的。【例例】设设A = x|(xR)A = x|(xR)且且(x(x2 20)nrn时，时，P(n, r) = 0P(n, r) = 0。 2021-8-9计算机应

36、用技术研究所计算机应用技术研究所130& 环形排列问题环形排列问题A AE EF FB BD DC C2021-8-9计算机应用技术研究所计算机应用技术研究所131& 环形排列问题环形排列问题【定义定义n n个人围坐圆桌上，有个人围坐圆桌上，有(n-1)(n-1)！种不！种不同的坐法，我们称这种排列为同的坐法，我们称这种排列为，从，从n n个人个人中选出中选出r r个人为圆桌而坐称为个人为圆桌而坐称为。【定理定理含含n n个不同元素的集合的环形个不同元素的集合的环形r-r-排列排列数数Pc(n,r)Pc(n,r)是是c cP(n, r)n!P(n, r)n!P(n, r)=P(n, r)=rr

37、rr(n-r)!(n-r)!2021-8-9计算机应用技术研究所计算机应用技术研究所132& 环形排列问题环形排列问题求满足下列条件的排列数。求满足下列条件的排列数。 ( (1)101)10个男孩和个男孩和5 5个女孩个女孩站成一排站成一排，无两无两个女孩相邻。个女孩相邻。 (2)10(2)10个男孩和个男孩和5 5个女孩个女孩站成一圆圈站成一圆圈，无无两个女孩相邻两个女孩相邻。2021-8-9计算机应用技术研究所计算机应用技术研究所133& 组合问题组合问题【定义定义n!n!C(n, r)=C(n, r)=r!(n -r)!r!(n -r)!2021-8-9计算机应用技术研究所计算机应用技术

38、研究所134& 组合问题组合问题 一副一副5252张的扑克牌含有张的扑克牌含有4 4种花色：梅花、方片、红种花色：梅花、方片、红桃和黑桃；各有桃和黑桃；各有1313种点数，分别为种点数，分别为A, 2-10, J, Q, KA, 2-10, J, Q, K。试求满足下列条件的组合数。试求满足下列条件的组合数。 （1 1）5 5张牌称为一手牌，一手牌共有多少种可能的组合？张牌称为一手牌，一手牌共有多少种可能的组合？ （2 2）一手牌）一手牌5 5张都是同一花色，有多少种可能的组合？张都是同一花色，有多少种可能的组合？ （3 3）一手牌有）一手牌有3 3张牌点数相同，另外两张牌点数相同，共张牌点数

39、相同，另外两张牌点数相同，共有多少种可能的组合？有多少种可能的组合？2021-8-9计算机应用技术研究所计算机应用技术研究所135& 组合问题组合问题 在在1 1到到300300中选三个不同的数，并且这中选三个不同的数，并且这三个数之和能被三个数之和能被3 3整除，问有多少种方式？整除，问有多少种方式？多少个多少个1212位二进制串包含位二进制串包含 a)a)恰好恰好3 3个个1 1？ b)b)至多至多3 3个个1 1？ c) c) 至少至少3 3个个1 1？ d) 0d) 0的个数与的个数与1 1的个数相等？的个数相等？2021-8-9计算机应用技术研究所计算机应用技术研究所136& 有重复

40、的组合有重复的组合 从包含苹果、橙子、和梨的框子里选从包含苹果、橙子、和梨的框子里选4个水果。如果不关心选择水果的顺序，且只关个水果。如果不关心选择水果的顺序，且只关心水果的类型，那么当框中每类水果至少有心水果的类型，那么当框中每类水果至少有4个时有多少种选法？个时有多少种选法？ 2021-8-9计算机应用技术研究所计算机应用技术研究所137& 有重复的组合有重复的组合共有共有1515种方式：种方式：4 4个苹果；个苹果；4 4个橙子；个橙子；4 4个梨；个梨；3 3个苹果，个苹果，1 1个橙子；个橙子；3 3个苹果，个苹果，1 1个梨；个梨；3 3个梨，个梨，1 1个苹果；个苹果；3 3个橙

41、子，个橙子，1 1个梨；个梨；3 3个梨，个梨，1 1个苹果；个苹果；3 3 个梨，个梨，1 1个橙子；个橙子；2 2个苹果，个苹果，2 2个橙子；个橙子；2 2个苹果，个苹果，2 2个梨；个梨；2 2个橙子，个橙子，2 2个梨个梨2 2个苹果，个苹果，1 1个橙子，个橙子，1 1个梨；个梨；2 2个橙子，个橙子，1 1个苹果，个苹果，1 1个梨个梨2 2个梨，个梨，1 1个苹果，个苹果，1 1个橙子。个橙子。 这个解是从这个解是从3 3个元素的集合个元素的集合 苹果、梨、橙子苹果、梨、橙子 中允许重复的中允许重复的4 4组合数。组合数。2021-8-9计算机应用技术研究所计算机应用技术研究所

42、138& 有重复的组合有重复的组合 从包含从包含1 1美元、美元、2 2美元、美元、5 5美元、美元、1010美元、美元、2020美元、美元、5050美元及美元及100100美元的钱袋中美元的钱袋中选选5 5张纸币，有多少种方式？假定不管纸币张纸币，有多少种方式？假定不管纸币被选的次序，同种币值的纸币都是不加区被选的次序，同种币值的纸币都是不加区别的，并且至少每张纸币有别的，并且至少每张纸币有5 5张。张。2021-8-9计算机应用技术研究所计算机应用技术研究所139& 有重复的组合有重复的组合 假设一个零钱盒子有假设一个零钱盒子有7 7个隔间，每个保存一种纸个隔间，每个保存一种纸币，如下图所

43、示。这些隔间被币，如下图所示。这些隔间被6 6块隔板分开，每选择块隔板分开，每选择1 1张张纸币就在相应的隔间里放置纸币就在相应的隔间里放置1 1个标记。针对选择个标记。针对选择5 5张纸币张纸币的的3 3种不同方式给出了这种对应，其中的竖线表示种不同方式给出了这种对应，其中的竖线表示6 6个隔个隔板，星表示板，星表示5 5张纸币。张纸币。2021-8-9计算机应用技术研究所计算机应用技术研究所140& 有重复的组合有重复的组合2021-8-9计算机应用技术研究所计算机应用技术研究所141& 有重复的组合有重复的组合 选择选择5 5张纸币的方法数对应了安排张纸币的方法数对应了安排6 6条竖线和

44、条竖线和5 5颗星颗星的方法数。因此，选择的方法数。因此，选择5 5张纸币的方法数就是从张纸币的方法数就是从1111个可个可能的位置选能的位置选5 5颗星位置的方法数。颗星位置的方法数。 这对应了从含这对应了从含1111个物体的集合中无序地选择个物体的集合中无序地选择5 5个物个物体的方法数，可以有体的方法数，可以有C(11,5)C(11,5)种方法种方法. . 因此从因此从7 7类纸币的袋中选择类纸币的袋中选择5 5张纸币的方式数有：张纸币的方式数有：11!(11,5)4625!6!C2021-8-9计算机应用技术研究所计算机应用技术研究所142& 有重复的组合有重复的组合 n n个元素的集

45、合中允许重复的个元素的集合中允许重复的r r组合有组合有 C C ( (n n-1+-1+r r, , r r) ) 【分析分析】用用n-1n-1条竖线标记条竖线标记n n个不同的单元。每当集合的第个不同的单元。每当集合的第i i个元素出现个元素出现在组合中，第在组合中，第i i个单元就包含一颗星。例如，个单元就包含一颗星。例如，4 4种元素集合的一个种元素集合的一个6 6组合组合用用3 3条竖线和条竖线和6 6颗星表示。例如颗星表示。例如* * * * | | * * | | | | * * * * * *表示表示2 2个第一元素、个第一元素、1 1个第二元素、个第二元素、0 0个第三元素和

46、个第三元素和3 3个第四元素的组合。个第四元素的组合。 因此，包含因此，包含n-1n-1条竖线和条竖线和r r颗星的每一个不同的表对应了颗星的每一个不同的表对应了n n元素集合元素集合的一个允许重复的的一个允许重复的r r组合。组合。 这种表的个数就是这种表的个数就是C(n-1+r, r), C(n-1+r, r), 因为每个表对应了从包含因为每个表对应了从包含r r颗星颗星和和n-1n-1条竖线的条竖线的n-1+rn-1+r个位置来放个位置来放r r颗星的一种选择。颗星的一种选择。2021-8-9计算机应用技术研究所计算机应用技术研究所143& 有重复的组合有重复的组合【例例】方程方程x x

47、1 1+x+x2 2+x+x3 3 =11 =11 有多少个解？其中有多少个解？其中x x1 1,x,x2 2,x,x3 3是非负整数。是非负整数。 【分析分析】一个解对应了从一个解对应了从3 3元素集合中选元素集合中选1111个元素的方式，个元素的方式，以使得以使得x1x1选自第一类，选自第一类，x2x2选自第二类，选自第二类，x3x3选自第三类。选自第三类。 因此，解的个数等于因此，解的个数等于3 3元素集合允许重复的元素集合允许重复的1111组合数：组合数：13 12(311,11)(13,11)(13,2)781 2CCC2021-8-9计算机应用技术研究所计算机应用技术研究所144&

48、 计数法初步计数法初步2021-8-9计算机应用技术研究所计算机应用技术研究所145& 容斥原理容斥原理UA BABABA-BA-BB-AB-A【定理定理2.4】设设A A和和B B是任意有是任意有限集合，有：限集合，有：|AB| = |A|B|AB|【推论推论2.1】设设U U为全集，为全集，A A，B B是任是任意有限集合，有：意有限集合，有：ABU(AB)AB2021-8-9计算机应用技术研究所计算机应用技术研究所146& 容斥原理容斥原理【例例】在在2020个大学生中，有个大学生中，有1010人爱好音人爱好音乐，有乐，有8 8人爱好美术，有人爱好美术，有6 6人既爱好音乐人既爱好音乐又

49、爱好美术。问：又爱好美术。问： （1 1）爱好音乐或美术的学生有多少？）爱好音乐或美术的学生有多少？ （2 2）既不爱好音乐又不爱好美术的学）既不爱好音乐又不爱好美术的学生有多少？生有多少？2021-8-9计算机应用技术研究所计算机应用技术研究所147& 容斥原理容斥原理定理定理2.5 设设A,BA,B和和C C是任意有限集合，有：是任意有限集合，有：A AB BC C = =( ( A A + + B B + + C C) )- -( ( A AB B + + A AC C + + B BC C) )+ + A AB BC C推论推论2.2 设设U U为全集，为全集，A A，B B和和C C

50、是任意有限集是任意有限集合，有：合，有：AABBC = U -( A + B + C )C = U -( A + B + C )+( A+( AB + AB + AC + BC + BC )- AC )- ABBC C2021-8-9计算机应用技术研究所计算机应用技术研究所148& 容斥原理容斥原理【例例】260260个大学生中，个大学生中，6464人选修数学，人选修数学，9494人人选修计算机，选修计算机，5858人选修商贸，人选修商贸，2828人同时选修数人同时选修数学和商贸，学和商贸，2626人同时选修数学和计算机，人同时选修数学和计算机，2222人人同时选修计算机和商贸，同时选修计算机

51、和商贸，1414人对三种课程都选人对三种课程都选修。问修。问（1 1）三种课程都不选的学生三种课程都不选的学生有多少？有多少？（2 2）只选修计算机科学课程的学生只选修计算机科学课程的学生有多少？有多少？2021-8-9计算机应用技术研究所计算机应用技术研究所149& 广义容斥原理广义容斥原理【定理定理2.6 】设设A A1 1, A, A2 2, , , A, An n是任意是任意n n个有限集合，则：个有限集合，则：【推论推论2.3 3】设设U U为全集，为全集，A A1 1, A, A2 2, , , A, An n是任意是任意n n个有个有限集合，则限集合，则2021-8-9计算机应用

52、技术研究所计算机应用技术研究所150& 广义容斥原理广义容斥原理【例例】2424名科技人员中，会英、日、德、法语的分名科技人员中，会英、日、德、法语的分别为别为1313、5 5、1010和和9 9人，同时会英语、日语的有人，同时会英语、日语的有2 2人，人，同时会英语和德语、同时会英语和法语、同时会德同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的均为语和法语两种语言的均为4 4人，会日语的人既不会法人，会日语的人既不会法语也不会德语。试求：语也不会德语。试求： (1)(1)同时会英、德、法语的人数为多少？同时会英、德、法语的人数为多少？ (2) (2)只会一种语言的人数各为多少

53、？只会一种语言的人数各为多少？2021-8-9计算机应用技术研究所计算机应用技术研究所151& 鸽笼原理鸽笼原理2021-8-9计算机应用技术研究所计算机应用技术研究所152& 鸽笼原理鸽笼原理2021-8-9计算机应用技术研究所计算机应用技术研究所153& 鸽笼原理鸽笼原理鸽笼原理（鸽笼原理（Pigeonhole PrinciplePigeonhole Principle）又称）又称为抽屉原理、鸽舍原理，是指如下定理：为抽屉原理、鸽舍原理，是指如下定理：【定理定理2.7】( (鸽笼原理鸽笼原理) ) 若有若有n+1n+1只鸽子只鸽子住进住进n n个鸽笼，则个鸽笼，则鸽笼鸽笼2 2只只鸽子。鸽

54、子。2021-8-9计算机应用技术研究所计算机应用技术研究所154& 鸽笼原理鸽笼原理【注意注意】 （1 1）鸽笼原理仅提供了）鸽笼原理仅提供了存在性证明存在性证明； （2 2）使用鸽笼原理，必须能够）使用鸽笼原理，必须能够正确识别鸽正确识别鸽子子( (对象对象) )和和鸽巢鸽巢( (某类要求的特征某类要求的特征) )，并且能，并且能够计算出鸽子数和鸽巢数。够计算出鸽子数和鸽巢数。2021-8-9计算机应用技术研究所计算机应用技术研究所155& 鸽笼原理鸽笼原理【例例】抽屉里有抽屉里有3 3双不一样的手套，从中双不一样的手套，从中至少取多少只，才能保证配成一双？至少取多少只，才能保证配成一双？

55、【例例】证明从证明从1 1到到1010中任意选出六个数，中任意选出六个数，其中必有有两个数的和是其中必有有两个数的和是1111。2021-8-9计算机应用技术研究所计算机应用技术研究所156& 广义鸽笼原理广义鸽笼原理【定理定理2.8】若有若有n n只鸽子住进只鸽子住进m(mn)m(mn)个个鸽笼，则鸽笼，则存在一个存在一个鸽笼鸽笼至少住至少住进进 只鸽子。这里，只鸽子。这里， 表示小于等于表示小于等于x x的最的最大整数。大整数。n -1n -1+1+1m mx x 2021-8-9计算机应用技术研究所计算机应用技术研究所157& 广义鸽笼原理广义鸽笼原理【例例】如果一个图书馆里如果一个图书

56、馆里3030本离散数学本离散数学书共有书共有1200312003页，那么必然有一本离散数页，那么必然有一本离散数学书至少有学书至少有401401页。页。【例例】如果离散数学课有如果离散数学课有5 5个可能的成绩个可能的成绩ABCDEABCDE，那么一个班最少有多少名学生才，那么一个班最少有多少名学生才能保证至少能保证至少6 6名学生得到相同的分数。名学生得到相同的分数。2021-8-9计算机应用技术研究所计算机应用技术研究所158& 广义鸽笼原理广义鸽笼原理【例例】( (拉姆齐理论拉姆齐理论) )假定一组有假定一组有6 6个人，个人，任两个人或者是朋友或者是敌人。证明任两个人或者是朋友或者是敌

57、人。证明在这组人中要么存在在这组人中要么存在3 3个人彼此都是朋友，个人彼此都是朋友，要么存在要么存在3 3个人彼此都是敌人。个人彼此都是敌人。2021-8-9计算机应用技术研究所计算机应用技术研究所159& 广义鸽笼原理广义鸽笼原理【分析分析】 令令A A是这是这6 6人中任意一个，则由广义鸽巢原人中任意一个，则由广义鸽巢原理知：组里其他理知：组里其他5 5人中至少有人中至少有3 3人是人是A A的朋友，或至少的朋友，或至少有有3 3个人是个人是A A的敌人。的敌人。 若是前一种情况，假定若是前一种情况，假定B B、C C、D D是是A A的朋友。如果这的朋友。如果这3 3人中有人中有2 2

58、人也是朋友，那么这人也是朋友，那么这2 2人和人和A A构成彼此是朋友构成彼此是朋友的的3 3人组。人组。 否则，否则，B B、C C、D D构成彼此为敌人的构成彼此为敌人的3 3人组。人组。 对于后一种情况，即当对于后一种情况，即当A A存在存在3 3个或更多的敌人时，个或更多的敌人时，可以用类似方法处理。可以用类似方法处理。2021-8-9计算机应用技术研究所计算机应用技术研究所160本节内容到此结束本节内容到此结束161合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院2014.32014.31632021-8-9排列与组合排列与组合164 从从3名男生、名男生、4名女生中，选派

59、名女生中，选派1名男生、名男生、2名女生参加辩名女生参加辩 论赛，则不同的选派方法共有论赛，则不同的选派方法共有_种种答案：答案： 181682021-8-9现要排一份现要排一份5 5天的值班表，每天有一个人值班共有天的值班表，每天有一个人值班共有5 5个人，个人，每个人都可以值多天班或不值班，但相邻两天不准由同一每个人都可以值多天班或不值班，但相邻两天不准由同一个人值班，问此值班表共有多少种不同的排法？个人值班，问此值班表共有多少种不同的排法？解先排第一天，可排5人中的任一人，有5种排法；再排第二天，此时不能排第一天已排的人，有4种排法；再排第三天，此时不能排第二天已排的人，仍有4种排法；同

60、理，第四、五两天均各有4种排法由分步计数原理可得值班表共有不同排法数为：544441280种169、1752021-8-9有多少有多少20位十进制数字包含有位十进制数字包含有2个个0、4个个1、3个个2、1个个3、2个个4、3个个5、2个个7和和3个个9？解：解：这是一个有重复的排列问题，符合题目的十进这是一个有重复的排列问题，符合题目的十进制串个数为制串个数为20!/(2!4!3!1!2!3!2!3!)解：解：为计数解的个数，注意到一个解对应了从为计数解的个数，注意到一个解对应了从3 3元素集合元素集合 中选中选1111个元素的方式，以使得个元素的方式，以使得x x1 1选自第一类，选自第一