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

《离散数学第三章集合论.ppt》由会员分享，可在线阅读，更多相关《离散数学第三章集合论.ppt（37页珍藏版）》请在三一办公上搜索。

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

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

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

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

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

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

7、定义3.6 给定集合 A，由集合A 的所有子集为元素组成的集合称为集合 A的幂集，记为。例如 定理3.2 若有限集合 A有n 个元素，则它的幂集 有 个元素。,17,集合间的关系,集合的概念及其表示,集合的运算及恒等式,有穷集的计数和包含排斥原理,主要内容,3.2 集合的运算及恒等式,集合之间的关系和初级运算可以用文氏图给予形象的描述。文氏图的构造方法是首先画一个大矩形表示全集（有时为简单起见可将全集省略），其次在矩形内画一些圆（或任何其他适当的闭曲线），用圆的内部表示集合。不同的圆代表不同的集合。如图3.1所示，图中的阴影部分表示新组成的集合。图3.1 文氏图表示集合关系集合的运算，就是以给

8、定集合为对象，按确定的规则得到另外一些集合。集合的基本运算有并、交，相对补，绝对补和对称差。,19,3.2 集合的运算及恒等式,集合的运算，就是以给定集合为对象，按确定的规则得到另外一些集合。集合的基本运算有并、交，相对补，绝对补和对称差。,20,3.2 集合的运算及恒等式,定义3.7 设 A，B 为集合，A 与B 的并集，交集，B对A 的相对补集 分别定义如下。由定义可以看出，是由A或B中的元素构成，由A和B中的公共元素构成，由属于A但不属于B的元素构成，例如则有如果两个集合交集为，则称这两个集合是不交的，例如B和C是不交的。,21,3.2 集合的运算及恒等式,定义3.8 设A，B为集合，A

9、与B的对称差集 定义为例如 则 定理3.3 证明等式,22,3.2 集合的运算及恒等式,定义3.9 设 E 为全集，A 为一集合，则 的绝对补集 定义为因为 E 是全集，是永真命题，所以 可以定义为例如，则,23,3.2 集合的运算及恒等式,以上所定义的集合之间的基本运算的文氏图表示可以参考图3.2。,24,3.2 集合的运算及恒等式,根据以上对集合基本运算的定义，可以得到集合论中的关于集合运算的基本定律。,25,集合运算基本定律,3.2 集合的运算及恒等式,除了以上的定律以外，还有一些关于集合运算性质的重要结果。,26,集合运算重要性质,3.2 集合的运算及恒等式,证明一个集合为另一个集合的

10、子集的基本思想是：设 P,Q 为集合公式，欲证，即证对于任意的 x有 成立。例3.1 证明，即证明：对于任意 x,27,集合运算重要性质,因此，,3.2 集合的运算及恒等式,28,集合运算重要性质,3.2 集合的运算及恒等式,29,集合运算重要性质,3.2 集合的运算及恒等式,例3.4 证明，即 证明：,30,集合运算重要性质,因此,3.2 集合的运算及恒等式,31,集合运算重要性质,集合的概念及其表示,集合的运算及恒等式,有穷集的计数和包含排斥原理,主要内容,3.3 有穷集的计数和包含排斥原理,使用文氏图可以很方便的解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般来说，每一条

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