离散数学第三章集合论.ppt

《离散数学第三章集合论.ppt》由会员分享，可在线阅读，更多相关《离散数学第三章集合论.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第三三章章 集合论集合论离散数学离散数学 陈志奎主编陈志奎主编人民邮电出版社人民邮电出版社集合论的创立与康托尔的遭遇19世纪末期，数学界出现了一件引人注目的事情。一位名叫格奥尔格康托尔（G.Cantor，18451918）的德国数学家提出一种令人费解的古怪理论-集合论。它的内容是如此与常识格格不入，以致于一出世就引起了一场轩然大波。集合论的创立与康托尔的遭遇n自从17世纪牛顿和莱布尼茨创立微积分理论体系之后，在近一二百年时间里，微积分理论一直缺乏一个严格的逻辑基础。n出于这一目的，康托尔用集合的观点重新考察各种数量关系，特别是无穷数量关系。在无穷的世界里，整体的所有元素和部分的所有元素之间可

2、以是一 一对应的。另外，无穷集合并不都是相等的，比如所有实数和所有有理数之间就不是一一对应的。因而，无穷集合是有大小的。集合论用“基数”这个概念来表示无穷集合间的区别。集合论的创立与康托尔的遭遇康托尔的研究成果发表之后，遭到了德国数学家克隆尼克的激烈攻击。“上帝创造了自然数，其余的一切才是人做的工作”集合论的创立与康托尔的遭遇n法国数学家彭加勒说：“我个人，而且还不只我一人，认为重要之点在于，切勿引进一些不能用有限个文字去完全定义好的东西”。他把集合论当作一个有趣的“病理学的情形”来谈，并且预测说：“后一代将把（Cantor）集合论当作一种疾病，而人们已经从中恢复过来了”。n德国数学家魏尔认为

3、，康托尔关于基数的等级观点是雾上之雾。n菲利克斯克莱因也不赞成集合论的思想。n数学家HA施瓦兹原来是康托尔的好友，但他由于反对集合论而同康托尔断交公理化集合论的建立n在1900年第二次国际数学大会上，著名数学家庞加莱就曾兴高采烈地宣布“数学已被算术化了。今天，我们可以说绝对的严格已经达到了。”n然而这种自得的情绪并没能持续多久。不久，集合论有漏洞的消息迅速传遍了数学界。这就是1902年罗素得出的罗素悖论。公理化集合论的建立n罗素构造了一个所有不属于自身（即不包含自身作为元素）的集合R。现在问R是否属于R？如果R属于R，则R满足R的定义，因此R不应属于自身，即R不属于R；另一方面，如果R不属于R

4、，则R不满足R的定义，因此R应属于自身，即R属于R。这样，不论何种情况都存在着矛盾。公理化集合论的建立n 1908年，策梅罗提出公理化集合论，后经改进形成无矛盾的集合论公理系统，简称ZF公理系统。这就是集合论发展的第二个阶段：公理化集合论。n 在1908年以前由康托尔创立的集合论被称为朴素集合论。PART PART 0101PART PART 0202PART PART 0303集合的概念及其表示集合的运算及恒等式有穷集的计数和包含排斥原理主要内容3.1 集合的概念及其表示n 集合是一个不能精确定义的基本概念。一般地说，把具有共同性质的一些事物汇集成一个整体，就叫做集合。而这些事物就是这个集合

5、的元素。例如，全体中国人是一个集合，每个中国人都是这个集合的元素；全体自然数是一个集合，每个自然数都是这个集合的元素；图书馆的藏书是一个集合，每本书都是这个集合的元素；全国的高校也形成一个集合，每所高校都是这个集合的元素。n 集合一般用大写的英文字母表示，集合中的事物，即元素用小写的英文字母表示。若元素 属于集合，记作，读作“属于”；反之，写作，读作“不属于”。n 一个集合的元素个数是有限的，则称作有限集，否则称作无限集。103.1 集合的概念及其表示1枚举法：把集合中的元素写在一个花括号内，元素间用逗号隔开。例如：2构造法：构造法又叫谓词法。如果 是表示元素 x具有某种性质P 的谓词，则所有

6、具有性质 P 的元素构成了一个集合，记作 。显然，。例如：11集合的表示法3.1 集合的概念及其表示n 集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如n集合的元素是无序的，如但n集合中的元素还可以是集合。例如应该说明的是 ，但 ，同理 但 。12集合的表示法3.1 集合的概念及其表示在本书中定义一些通用的集合的符号，自然数集合 N，整数集合Z，有理数集合 Q，实数集合R，复数集合 C。为了体系上的严谨性，我们规定，对于任何集合 A 都有 。133.1 集合的概念及其表示14集合间的关系3.1 集合的概念及其表示15集合间的关系3.1 集合的概念及其表示定理3.1

7、空集是任意集合的子集，即对于任意集合 A，有16集合间的关系3.1 集合的概念及其表示n定义3.6 给定集合 A，由集合A 的所有子集为元素组成的集合称为集合 A的幂集，记为 。例如 n定理3.2 若有限集合 A有n 个元素，则它的幂集 有 个元素。17集合间的关系PART PART 0101PART PART 0202PART PART 0303集合的概念及其表示集合的运算及恒等式有穷集的计数和包含排斥原理主要内容3.2 集合的运算及恒等式集合之间的关系和初级运算可以用文氏图给予形象的描述。文氏图的构造方法是首先画一个大矩形表示全集（有时为简单起见可将全集省略），其次在矩形内画一些圆（或任何

8、其他适当的闭曲线），用圆的内部表示集合。不同的圆代表不同的集合。如图3.1所示，图中的阴影部分表示新组成的集合。图3.1 文氏图表示集合关系集合的运算，就是以给定集合为对象，按确定的规则得到另外一些集合。集合的基本运算有并、交，相对补，绝对补和对称差。193.2 集合的运算及恒等式集合的运算，就是以给定集合为对象，按确定的规则得到另外一些集合。集合的基本运算有并、交，相对补，绝对补和对称差。203.2 集合的运算及恒等式n定义3.7 设 A，B 为集合，A 与B 的并集 ，交集 ，B对A 的相对补集 分别定义如下。由定义可以看出，是由A或B中的元素构成，由A和B中的公共元素构成，由属于A但不属

9、于B的元素构成，例如则有如果两个集合交集为 ，则称这两个集合是不交的，例如B和C是不交的。213.2 集合的运算及恒等式n定义3.8 设A，B为集合，A与B的对称差集 定义为例如 则 n定理3.3 证明等式 223.2 集合的运算及恒等式n定义3.9 设 E 为全集，A 为一集合，则 的绝对补集 定义为因为 E 是全集，是永真命题，所以 可以定义为例如 ，则 233.2 集合的运算及恒等式以上所定义的集合之间的基本运算的文氏图表示可以参考图3.2。243.2 集合的运算及恒等式n根据以上对集合基本运算的定义，可以得到集合论中的关于集合运算的基本定律。25集合运算基本定律3.2 集合的运算及恒等

10、式n除了以上的定律以外，还有一些关于集合运算性质的重要结果。26集合运算重要性质3.2 集合的运算及恒等式n证明一个集合为另一个集合的子集的基本思想是：设 P,Q 为集合公式，欲证 ，即证对于任意的 x有 成立。n例3.1 证明 ，即证明：对于任意 x27集合运算重要性质因此，3.2 集合的运算及恒等式28集合运算重要性质3.2 集合的运算及恒等式29集合运算重要性质3.2 集合的运算及恒等式n例3.4 证明 ，即 证明：30集合运算重要性质因此3.2 集合的运算及恒等式31集合运算重要性质PART PART 0101PART PART 0202PART PART 0303集合的概念及其表示集

11、合的运算及恒等式有穷集的计数和包含排斥原理主要内容3.3 有穷集的计数和包含排斥原理使用文氏图可以很方便的解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般来说，每一条性质决定一个集合，有多少条性质，就有多少个集合。如果没有特殊的说明，任何两个集合都画成相交的，然后将已知的元素个数填入该集合的区域内。通常从 个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为，之后再根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。333.3 有穷集的计数和包含排斥原理n例3.9 对24名会外语的科技人员进行掌握外语情况的调查，统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言（英、德、法、日）的人数和会三种语言的人数。解：令A，B，C，D分别表示会英、德、法、日语的人的集合。根据题意画出文氏图如图3.4所示。设同时会三种语言的有 人，只会英、法或德语一种语言的分别为 ，和 人。将 x 和 ，填入图中相应的区域，然后依次填入其他区域的人数。根据已知条件列出方程组如下：解得 343.3 有穷集的计数和包含排斥原理35包含排斥原理3.3 有穷集的计数和包含排斥原理36包含排斥原理37谢谢！