离散数学集合论省公共课一等奖全国赛课获奖课件.pptx

第第三三章章 集合论集合论离散数学离散数学 陈志奎主编陈志奎主编人民邮电出版社人民邮电出版社第1页集合论创建与康托尔遭遇19世纪末期，数学界出现了一件引人注目标事情。一位名叫格奥尔格康托尔（G.Cantor，18451918）德国数学家提出一个令人费解古怪理论-集合论。它内容是如此与常识格格不入，以致于一出世就引发了一场轩然大波。第2页集合论创建与康托尔遭遇n自从17世纪牛顿和莱布尼茨创建微积分理论体系之后，在近一二百年时间里，微积分理论一直缺乏一个严格逻辑基础。n出于这一目标，康托尔用集合观点重新考查各种数量关系，尤其是无穷数量关系。在无穷世界里，整体全部元素和部分全部元素之间能够是一 一对应。另外，无穷集合并不都是相等，比如全部实数和全部有理数之间就不是一一对应。因而，无穷集合是有大小。集合论用“基数”这个概念来表示无穷集合间区分。第3页集合论创建与康托尔遭遇康托尔研究结果发表之后，遭到了德国数学家克隆尼克激烈攻击。“上帝创造了自然数，其余一切才是人做工作”第4页集合论创建与康托尔遭遇n法国数学家彭加勒说：“我个人，而且还不只我一人，认为主要之点在于，切勿引进一些不能用有限个文字去完全定义好东西”。他把集合论看成一个有趣“病理学情形”来谈，而且预测说：“后一代将把（Cantor）集合论看成一个疾病，而人们已经从中恢复过来了”。n德国数学家魏尔认为，康托尔关于基数等级观点是雾上之雾。n菲利克斯克莱因也不赞成集合论思想。n数学家HA施瓦兹原来是康托尔挚友，但他因为反对集合论而同康托尔断交第5页公理化集合论建立在19第二次国际数学大会上，著名数学家庞加莱就曾兴高采烈地宣告“数学已被算术化了。今天，我们能够说绝正确严格已经到达了。”然而这种自得情绪并没能连续多久。很快，集合论有漏洞消息快速传遍了数学界。这就是19罗素得出罗素悖论。第6页公理化集合论建立n罗素结构了一个全部不属于本身（即不包含本身作为元素）集合R。现在问R是否属于R？如果R属于R，则R满足R定义，所以R不应属于自身，即R不属于R；其次，如果R不属于R，则R不满足R定义，所以R应属于自身，即R属于R。这样，不论何种情况都存在着矛盾。第7页公理化集合论建立 19，策梅罗提出公理化集合论，后经改进形成无矛盾集合论公理系统，简称ZF公理系统。这就是集合论发展第二个阶段：公理化集合论。在19以前由康托尔创建集合论被称为朴素集合论。第8页PART PART 0101PART PART 0202PART PART 0303集合概念及其表示集合运算及恒等式有穷集计数和包含排斥原理主要内容第9页3.1 集合概念及其表示n 集合是一个不能准确定义基本概念。普通地说，把含有共同性质一些事物聚集成一个整体，就叫做集合。而这些事物就是这个集合元素。比如，全体中国人是一个集合，每个中国人都是这个集合元素；全体自然数是一个集合，每个自然数都是这个集合元素；图书馆藏书是一个集合，每本书都是这个集合元素；全国高校也形成一个集合，每所高校都是这个集合元素。n 集合普通用大写英文字母表示，集合中事物，即元素用小写英文字母表示。若元素 属于集合，记作，读作“属于”；反之，写作，读作“不属于”。n 一个集合元素个数是有限，则称作有限集，不然称作无限集。10第10页3.1 集合概念及其表示1枚举法：把集合中元素写在一个花括号内，元素间用逗号隔开。比如：2结构法：结构法又叫谓词法。假如 是表示元素 x含有某种性质P 谓词，则全部含有性质 P 元素组成了一个集合，记作 。显然，。比如：11集合表示法第11页3.1 集合概念及其表示n 集合元素是彼此不一样，假如同一个元素在集合中屡次出现应该认为是一个元素，如n集合元素是无序，如但n集合中元素还能够是集合。比如应该说明是 ，但 ，同理 但 。12集合表示法第12页3.1 集合概念及其表示在本书中定义一些通用集合符号，自然数集合 N，整数集合Z，有理数集合 Q，实数集合R，复数集合 C。为了体系上严谨性，我们要求，对于任何集合 A 都有 。13第13页3.1 集合概念及其表示14集合间关系第14页3.1 集合概念及其表示15集合间关系第15页3.1 集合概念及其表示定理3.1 空集是任意集合子集，即对于任意集合 A，有16集合间关系第16页3.1 集合概念及其表示n定义3.6 给定集合 A，由集合A 全部子集为元素组成集合称为集合 A幂集，记为 。比如 n定理3.2 若有限集合 A有n 个元素，则它幂集 有 个元素。17集合间关系第17页PART PART 0101PART PART 0202PART PART 0303集合概念及其表示集合运算及恒等式有穷集计数和包含排斥原理主要内容第18页3.2 集合运算及恒等式集合之间关系和初级运算能够用文氏图给予形象描述。文氏图结构方法是首先画一个大矩形表示全集（有时为简单起见可将全集省略），其次在矩形内画一些圆（或任何其它适当闭曲线），用圆内部表示集合。不一样圆代表不一样集合。如图3.1所表示，图中阴影部分表示新组成集合。图3.1 文氏图表示集合关系集合运算，就是以给定集合为对象，按确定规则得到另外一些集合。集合基本运算有并、交，相对补，绝对补和对称差。19第19页3.2 集合运算及恒等式集合运算，就是以给定集合为对象，按确定规则得到另外一些集合。集合基本运算有并、交，相对补，绝对补和对称差。20第20页3.2 集合运算及恒等式n定义3.7 设 A，B 为集合，A 与B 并集 ，交集 ，B对A 相对补集 分别定义以下。由定义能够看出，是由A或B中元素组成，由A和B中公共元素组成，由属于A但不属于B元素组成，比如则有假如两个集合交集为 ，则称这两个集合是不交，比如B和C是不交。21第21页3.2 集合运算及恒等式n定义3.8 设A，B为集合，A与B对称差集 定义为比如 则 n定理3.3 证实等式 22第22页3.2 集合运算及恒等式n定义3.9 设 E 为全集，A 为一集合，则 绝对补集 定义为因为 E 是全集，是永真命题，所以 能够定义为比如 ，则 23第23页3.2 集合运算及恒等式以上所定义集合之间基本运算文氏图表示能够参考图3.2。24第24页3.2 集合运算及恒等式n依据以上对集合基本运算定义，能够得到集合论中关于集合运算基本定律。25集合运算基本定律第25页3.2 集合运算及恒等式n除了以上定律以外，还有一些关于集合运算性质主要结果。26集合运算主要性质第26页3.2 集合运算及恒等式n证实一个集合为另一个集合子集基本思想是：设 P,Q 为集合公式，欲证 ，即证对于任意 x有 成立。n例3.1 证实 ，即证实：对于任意 x27集合运算主要性质所以，第27页3.2 集合运算及恒等式28集合运算主要性质第28页3.2 集合运算及恒等式29集合运算主要性质第29页3.2 集合运算及恒等式n例3.4 证实 ，即 证实：30集合运算主要性质所以第30页3.2 集合运算及恒等式31集合运算主要性质第31页PART PART 0101PART PART 0202PART PART 0303集合概念及其表示集合运算及恒等式有穷集计数和包含排斥原理主要内容第32页3.3 有穷集计数和包含排斥原理使用文氏图能够很方便处理有穷集计数问题。首先依据已知条件把对应文氏图画出来。普通来说，每一条性质决定一个集合，有多少条性质，就有多少个集合。假如没有特殊说明，任何两个集合都画成相交，然后将已知元素个数填入该集合区域内。通常从 个集合交集填起，依据计算结果将数字逐步填入全部空白区域。假如交集数字是未知，能够设为，之后再依据题目中条件，列出一次方程或方程组，就能够求得所需要结果。33第33页3.3 有穷集计数和包含排斥原理n例3.9 对24名会外语科技人员进行掌握外语情况调查，统计结果以下：会英、日、德和法语人分别为13，5，10和9人，其中同时会英语和日语有2人，会英、德和法语中任两种语言都是4人。已知会日语人既不懂法语也不懂德语，分别求只会一个语言（英、德、法、日）人数和会三种语言人数。解：令A，B，C，D分别表示会英、德、法、日语人集合。依据题意画出文氏图如图3.4所表示。设同时会三种语言有 人，只会英、法或德语一个语言分别为 ，和 人。将 x 和 ，填入图中对应区域，然后依次填入其它区域人数。依据已知条件列出方程组以下：解得 34第34页3.3 有穷集计数和包含排斥原理35包含排斥原理第35页3.3 有穷集计数和包含排斥原理36包含排斥原理第36页37第37页