第1节 集合及其运算

1、集合论集合论与图论与图论1/42集合论与图论集合论与图论集合论集合论与图论与图论2/42引引 言言离散数学主要内容离散数学主要内容:集合论、图论、近世代数、数理逻辑、集合论、图论、近世代数、数理逻辑、组合数学、组合数学、(初等初等)数论等数论等二、集合论与图论与后继课程二、集合论与图论与后继课程 集合论：近世代数、形式语言、集合论：近世代数、形式语言、 数据库系统数据库系统等等图图 论：数据结构、计算机网络等论：数据结构、计算机网络等一、一、集合论与图论是离散数学的重要组成部分集合论与图论是离散数学的重要组成部分集合论集合论与图论与图论3/42三、教学主要内容和教学安排三、教学主要内容和教学安

2、排(32学时学时) 第第1章章 集合集合(4学时学时) 第第2章章 映射映射(2学时学时)第第4章章 无穷集合及其基数无穷集合及其基数(2学时学时)第第3章章 关系关系(8学时学时) 第第6章章 图的基本概念图的基本概念(8学时学时) 第第7章章 树与树与割集割集(2学时学时)第第8章章 连通度连通度和匹配和匹配(2学时学时)第第9章章 平面图和平面图和图的着色图的着色(2学时学时)引引 言言集合论集合论与图论与图论4/42四、主要教材四、主要教材离散数学引论离散数学引论 王义和王义和 哈尔滨工业大学出版社哈尔滨工业大学出版社离散数学离散数学 耿素云等耿素云等 高等教育出版社高等教育出版社离散

3、数学离散数学 左孝凌等左孝凌等 上海科技文献出版社上海科技文献出版社方式：笔试方式：笔试成绩：总成绩成绩：总成绩(100分分)其中：平时成绩其中：平时成绩(作业与出勤作业与出勤)(20分分) 笔试成绩笔试成绩(80分分)五、考试方式与成五、考试方式与成绩绩引引 言言集合论集合论与图论与图论5/42 集合论集合论 集合论成了数学各分支的基础，也是计算机科集合论成了数学各分支的基础，也是计算机科学非常重要的基础知识。学非常重要的基础知识。 它的起源可追溯到它的起源可追溯到16世纪末，主要是对数集进世纪末，主要是对数集进行了卓有成效的研究。但集合论实际发展是由行了卓有成效的研究。但集合论实际发展是由

4、19世世纪纪70年代德国数学家康托年代德国数学家康托(G. Cantor)在无穷序列和在无穷序列和分析的有关课题的理论研究中创立的。康托对具有分析的有关课题的理论研究中创立的。康托对具有任意特性的无穷集合进入了深入的探讨，提出了关任意特性的无穷集合进入了深入的探讨，提出了关于于基数基数、序数、序数、超穷数超穷数和良序集等理论，奠定了集和良序集等理论，奠定了集合论的深厚基础。因此，合论的深厚基础。因此，康托被誉为集合论的创始康托被誉为集合论的创始人人。集合论集合论与图论与图论6/42 但随着集合论的发展，以及它与数学哲学密切但随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在联系所作的讨论

5、，在20世纪初，出现了许多似是而世纪初，出现了许多似是而非、自相矛盾的悖论，如非、自相矛盾的悖论，如康托悖论康托悖论、罗素罗素(Russell)悖悖论论，有力冲击了或者说动摇了集合论的发展。由此，有力冲击了或者说动摇了集合论的发展。由此，激发许多数学家、哲学家为克服这些矛盾建立了各激发许多数学家、哲学家为克服这些矛盾建立了各种种公理化集合论体系公理化集合论体系。 集合论集合论 朴素集合论体系朴素集合论体系 (也称也称康托康托(Cantor)集合论体系集合论体系) 公理集合论体系公理集合论体系集合论集合论集合论集合论与图论与图论7/42 1965年，美国学者年，美国学者L. A. Zadeh提出

6、了提出了Fuzzy集概集概念念(理论理论)。 20世纪世纪80年代初，波兰学者年代初，波兰学者Z. Pawlak发表了发表了Rough集理论。集理论。 这两种理论区别以往的集合论，是一种新的模这两种理论区别以往的集合论，是一种新的模糊集理论。糊集理论。 集合论集合论 集合论在计算机科学、人工智能领域、逻辑学集合论在计算机科学、人工智能领域、逻辑学及语言学等方面都有着重要的应用。对于从事计算及语言学等方面都有着重要的应用。对于从事计算机科学的工作者来说，集合论是不可缺少的理论知机科学的工作者来说，集合论是不可缺少的理论知识，熟悉和掌握它是十分必要的。识，熟悉和掌握它是十分必要的。集合论集合论与图

7、论与图论8/42毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过。至少与一个姑娘跳过舞，但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。未能与所有的小伙子跳过舞。证明：证明：在所有参加舞会的小伙与姑娘中，必可找到在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每

8、一个也只与这两个小伙中的一个跳过舞。的每一个也只与这两个小伙中的一个跳过舞。 问问 题题问题问题1：毕业舞会问题：毕业舞会问题问题问题2：在至少有两个人的团队里，总有两个人在此团队在至少有两个人的团队里，总有两个人在此团队里有相同个数的朋友？里有相同个数的朋友？集合论集合论与图论与图论9/42 第第1节节 集合及其运算集合及其运算主要内容：主要内容： 集合的概念集合的概念 集合的基本运算集合的基本运算 笛卡儿乘积笛卡儿乘积集合论集合论与图论与图论10/421.1 集合的概念集合的概念 在朴素集合论体系中，在朴素集合论体系中，“集合集合”是集合论中的一个是集合论中的一个原始概念，我们知道在欧氏几

9、何中对点、线不加定义，原始概念，我们知道在欧氏几何中对点、线不加定义，在朴素集合论中在朴素集合论中“集合集合”不能严格定义。不能严格定义。 通常把一些互不相同的东西放在一起所形成的整体通常把一些互不相同的东西放在一起所形成的整体就叫做一个就叫做一个集合集合。构成集合的每一个东西，称为该集合。构成集合的每一个东西，称为该集合的一个的一个元素元素。集合的定义集合的定义集合论集合论与图论与图论11/42康托康托(Cantor) 1874年所给的年所给的“集合集合”定义：定义： 把若干确定的有区别的（不论是具体的或抽象把若干确定的有区别的（不论是具体的或抽象的）事物合并起来，看作一个整体，就称为一个的

10、）事物合并起来，看作一个整体，就称为一个集集合合，其中各事物称为该集合的，其中各事物称为该集合的元素元素。 常用大写英文字母常用大写英文字母A,B,C,.表示集合，用小写英表示集合，用小写英文字母文字母a,b,c,.,表示集合中的元素。表示集合中的元素。如果如果x是集合是集合A的元素，就说的元素，就说x属于属于A，记为，记为x A； 如果如果x不是集合不是集合A的元素，就说的元素，就说x不属于不属于A，记为，记为x A或者或者x A；集合的概念集合的概念集合论集合论与图论与图论12/42 (3)确定性确定性：对于一个集合：对于一个集合A来说，某一对象来说，某一对象x或者是或者是集合集合A的元素

11、，或者不是，两者必居其一。的元素，或者不是，两者必居其一。集合的性质集合的性质 (2)无序性无序性：集合中的元素不规定顺序。：集合中的元素不规定顺序。(1)互异性互异性：集合中的元素是各不相同的。：集合中的元素是各不相同的。 (4)任意性任意性：集合的元素可以是具体的，也可以是抽：集合的元素可以是具体的，也可以是抽象的；集合的元素可以是集合。象的；集合的元素可以是集合。集合论集合论与图论与图论13/42集合的表示方法集合的表示方法 列举法列举法：列出集合中的全体元素，元素之间用：列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来。逗号分开，然后用花括号括起来。 描述法描述法：当集合当

12、集合A是具有某种性质是具有某种性质P的元素全体的元素全体时，我们往往用下面的形式表示时，我们往往用下面的形式表示A。A=x| x具有性质具有性质P注：集合的两种表示法有时是可以互相转化的。注：集合的两种表示法有时是可以互相转化的。集合论集合论与图论与图论14/42集合之间的关系集合之间的关系 定义定义1.1 设设A，B为二集合，若为二集合，若A中的每个元素中的每个元素都是都是B中的元素，则称中的元素，则称A是是B的的子集合子集合，简称，简称子集子集。这时我们说这时我们说A包含包含在在B里里(A包含于包含于B)，或，或B包含着包含着A(B包含包含A)，记作，记作A B。 其符号化形式为：其符号化

13、形式为：A B x A, x B 定义定义1.2 设设A，B为二集合，若为二集合，若A B且且 x B使使得得x A，则称，则称A是是B的的真子集真子集，记作记作A B，读作，读作A是是B的真子集。的真子集。 A BA B且且 x B但但x A 定义定义1.3 设设A，B是集合，如果是集合，如果A B且且B A，则，则称称A与与B相等相等，记作，记作A=B。集合论集合论与图论与图论15/42 定义定义1.4 不拥有任何元素的集合称为空集合，简不拥有任何元素的集合称为空集合，简称为称为空集空集，记作，记作。几个特殊的集合：空集几个特殊的集合：空集 定理定理1.1 空集是一切集合的子集。空集是一切

14、集合的子集。推论推论1：空集是唯一的。：空集是唯一的。 由推论可知，空集无论以什么形式出现，它们都由推论可知，空集无论以什么形式出现，它们都是相等的。是相等的。 空集是一切集合的子集，从这个意义上看，可以空集是一切集合的子集，从这个意义上看，可以形象地说：形象地说： 是是“最小最小”的集合，有无最大的集合呢？的集合，有无最大的集合呢？回答是否定的。回答是否定的。 B x , x B集合论集合论与图论与图论16/42定义定义1.5以集合为元素的集合称为以集合为元素的集合称为集族集族。几个特殊的集合：集族几个特殊的集合：集族 若若J为任一集合，对为任一集合，对J中每个元素中每个元素i有唯一的一个有

15、唯一的一个集合与之对应，这个集合记为集合与之对应，这个集合记为Ai，那么所有这些，那么所有这些Ai，形成的集族就用形成的集族就用Aii J表示，其表示，其J称为标号集。称为标号集。 A =A0,A1,.,Ap是以是以J=0,1,2,.p为标号集的集族，为标号集的集族，也可以记为也可以记为 A =Akk 0,1,2,.p =Akk J集合论集合论与图论与图论17/42 定义定义1.6 集合集合S的所有子集的所有子集(包括空集包括空集和和S本身本身)形形成的集族称为成的集族称为S的的幂集幂集，并记为，并记为2S，或记为，或记为P(S)。P(S)=2S=A|A S 为了求出给定集合为了求出给定集合A

16、的幂集，首先求出的幂集，首先求出A的元素个的元素个数由少到多的所有子集，再将它们组成集合即可。数由少到多的所有子集，再将它们组成集合即可。几个特殊的集合：幂集几个特殊的集合：幂集例如例如： 设设S=1,2,3，求，求2S. 定理定理1.2 设集合设集合S的元素个数的元素个数|S|=n(n为自然数为自然数)，则则|P(S)|=| 2S|=2n。集合论集合论与图论与图论18/42注意：注意：2=。 在这里要区分在这里要区分和和: 为空集为空集,而而是一个集族。是一个集族。 和和?集合论集合论与图论与图论19/42就一个问题来说，常称包含所考虑问题的所有集就一个问题来说，常称包含所考虑问题的所有集合

17、的集合合的集合S，称为该问题的，称为该问题的全集全集。几个特殊的集合：全集几个特殊的集合：全集集合论集合论与图论与图论20/421.2 集合的基本运算集合的基本运算 AB=x|x A或者或者x B。AB=x|x A且且x BAB=x|x A且且x B=A-BA B=(AB)(BA) = (AB)(AB)=A BAc=SA（S为全集，为全集，A S ）设设A，B为两个集合，则为两个集合，则A与与B的并：的并：A与与B的交：的交：A与与B的差：的差：A与与B的对称差：的对称差：A对对S的余：的余：集合论集合论与图论与图论21/42在这种图示法中，用矩形中各点表示全集在这种图示法中，用矩形中各点表示

18、全集S的各的各个元素。矩形中的圆里的点表示个元素。矩形中的圆里的点表示S的子集的各元素。的子集的各元素。SABAB文氏图文氏图SABABSABA BSABAB集合论集合论与图论与图论22/42集合集合A对对S的余集的余集Ac可用文氏图表示，如下图：可用文氏图表示，如下图：AAcS文氏图文氏图集合论集合论与图论与图论23/42 性质性质1 设设A,B,C为任意的三个集合为任意的三个集合 (1)交换律成立交换律成立,(3)幂等律成立，即幂等律成立，即AA=A; 即即AB=BA; (4)A=A;(5)AB=BA B。(2)结合律成立，即结合律成立，即(AB)C=A(BC);(AB)C=A(BC)=A

19、BC。由于结合律成立，由于结合律成立， 所以所以ABC有意义有意义。从而有。从而有问题：消去律成立吗？即问题：消去律成立吗？即 若若AB=AC，则，则B=C？基本运算的性质基本运算的性质集合论集合论与图论与图论24/42性质性质2 设设A,B,C为任意的三个集合，则为任意的三个集合，则:(8)幂等律成立，即幂等律成立，即AA=A;(6)交换律成立，即交换律成立，即AB=BA; (9)A=;(10)AB=AA B。(7)结合律成立，即结合律成立，即(AB)C=A(BC);基本运算的性质基本运算的性质集合论集合论与图论与图论25/42性质性质3 设设A,B,C为任意三个集合，则为任意三个集合，则

20、(11)交运算对并运算满足分配律交运算对并运算满足分配律, 即即A(BC)=(AB)(AC); (12)并运算对交运算满足分配律并运算对交运算满足分配律, 即即A(BC)=(AB)(AC)。 性质性质4 对任何集合对任何集合A,B，吸收律成立。，吸收律成立。 (13)A(AB)=A; (14)A(AB)=A。基本运算的性质基本运算的性质集合论集合论与图论与图论26/42基本运算的性质基本运算的性质性质性质5 设设A,B,C为任意三个集合，则为任意三个集合，则 (15)A(BC)=(AB)(AC)。 性质性质6 设设A,B,C为任意三个集合，则为任意三个集合，则 (16)A B=B A;(18)

21、A A=;(19)A=A; (17)(A B) C=A (B C);(20)交运算关于对称差满足分配律，即交运算关于对称差满足分配律，即 A(B C)=(AB) (AC)。集合论集合论与图论与图论27/42性质性质7 A对对S的余集的余集Ac有如下性质有如下性质:(21)S对对S的余集的余集Sc为空集，即为空集，即Sc=；(22)c=S；(23)AAc=；(24)AAc=S。 基本运算的性质基本运算的性质集合论集合论与图论与图论28/42性质性质8 德摩根德摩根(De Morgan)公式公式: (25)(AB)c=AcBc;(26)(AB)c=AcBc.下面的定理表明余集、差集、对称差之间的联

22、系。下面的定理表明余集、差集、对称差之间的联系。性质性质9 设设A,B都是都是S的子集，则的子集，则(27)AB=ABc;(28)A B=(ABc)(BAc);(29)Ac=S A.基本运算的性质基本运算的性质集合论集合论与图论与图论29/42 A1A2.An定义为至少属于定义为至少属于A1, A2, . , An中中之一的那些元素构成的集合。之一的那些元素构成的集合。 若若A1, A2, . , An, . 是一个集合的无穷序列，则它是一个集合的无穷序列，则它们的并集记为：们的并集记为：A1A2.An. ,niiA1 A1A2.An简记为简记为1iiA 简记为简记为定义定义:A1A2.An.

23、= =x| n N使得使得x An集合并运算的推集合并运算的推广广1iiA集合论集合论与图论与图论30/42集合交运算的推广集合交运算的推广),.,2 , 1.121iniinAxnixAAAA,.121nnnnAxNnxAAAA类似定义集合论集合论与图论与图论31/42性质性质10 设设A为一集合，为一集合，Bll I为任一集族，则为任一集族，则)()(IllIllBABAIllIllBABA)()(其中其中I。基本运算的性质基本运算的性质集合论集合论与图论与图论32/42设设S为任一集合，为任一集合，I为标号集，为标号集，I有有A S，则有，则有性质性质11 并集的余集等于各余集的交集，即

24、并集的余集等于各余集的交集，即IccIAA)(性质性质12 交集的余集等于各余集的并集，即交集的余集等于各余集的并集，即IccIAA)(基本运算的性质基本运算的性质集合论集合论与图论与图论33/421.3 笛卡儿乘积笛卡儿乘积两个对象两个对象a和和b(允许允许a=b)按一定的次序排列的整体按一定的次序排列的整体就叫做一个就叫做一个二元组二元组或或有序对有序对。如果如果a排在排在b的前面，则这个有序对就记作的前面，则这个有序对就记作(a,b)，a称为有序对称为有序对(a,b)的第一个元素，的第一个元素，b称为第二个元素。称为第二个元素。 有序对是由有次序的两个对象组成的，因此有序有序对是由有次序

25、的两个对象组成的，因此有序对与含两个对象的集合是有区别的。集合对与含两个对象的集合是有区别的。集合a,b中的元中的元素没有次序，集合素没有次序，集合a,b与与b,a是同一个集合。但是同一个集合。但(a,b)与与(b,a)在在ab时是不同的。时是不同的。我们规定我们规定(a,b)=(c,d)当且仅当当且仅当a=c,b=d。有序对有序对有序对的集合定义：有序对的集合定义：(a,b)=a,a,b。集合论集合论与图论与图论34/42 定义定义3.1 设设A与与B为任意两个集合，则称集合为任意两个集合，则称集合 (a,b)|a A且且b B 为为A与与B的的笛卡尔乘积笛卡尔乘积，记为，记为A B。 A

26、B=(a,b)|a A且且b B 例如：在平面上建立了直角坐标系后，平面上的例如：在平面上建立了直角坐标系后，平面上的点就用实数的有序对来表示。平面上的所有点之集就点就用实数的有序对来表示。平面上的所有点之集就可视为可视为R R，其中，其中R为实数集。为实数集。笛卡儿乘积笛卡儿乘积集合论集合论与图论与图论35/42例如例如 设设A=a,b,B=1,2,3A A=(a,a),(a,b),(b,a),(b,b) A B=(a,1),(a,2),(a,3),(b,1),(b,2),(b,3) B A=(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)B B=(1,1),(1,2)

27、,(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) 对任意有穷集合，对任意有穷集合，B，如果用，如果用|A|，|B|分别表分别表示和示和B中元素的个数，那么中元素的个数，那么|A B|A| |B|。两个集合的笛卡尔乘积的元素个数：两个集合的笛卡尔乘积的元素个数：笛卡儿乘积笛卡儿乘积集合论集合论与图论与图论36/42由定义可知，对任一集合由定义可知，对任一集合A，有，有A=A。一般情况下一般情况下A B B A。含空集的两个集合的笛卡尔积：含空集的两个集合的笛卡尔积：是否满足交换律是否满足交换律?1 2=(1,2)2 1=(2,1)是否满足结合律是否满足结合律?

28、当当A,B,C时时, (A B) C中的元素形中的元素形如如(x,y),z) A (B C)中的元素形如中的元素形如(x,(y,z)笛卡儿乘积笛卡儿乘积集合论集合论与图论与图论37/42性质性质 设设A,B,C为任意三个集合，则笛卡儿乘积为任意三个集合，则笛卡儿乘积运算对并、交、差运算分别满足分配律，即运算对并、交、差运算分别满足分配律，即 (30)A (BC)=(A B)(A C); (31)A (BC)=(A B)(A C); (32)A (BC)=(A B)(A C)。笛卡儿乘积笛卡儿乘积集合论集合论与图论与图论38/42有序对也叫二元组，我们可将二元组推广到三元有序对也叫二元组，我们可

29、将二元组推广到三元组，四元组，一直到组，四元组，一直到n元组。元组。三元组就是三个元素按一定次序组成的整体，设三元组就是三个元素按一定次序组成的整体，设第一个元素为第一个元素为x，第二个元素为，第二个元素为y，第三个元素为，第三个元素为z，则，则这个三元组就记为这个三元组就记为(x,y,z)。一般地，一个一般地，一个n元组就是元组就是n个元素按一定次序组个元素按一定次序组成的整体，设第一个元素为成的整体，设第一个元素为x1,第二个元素为第二个元素为x2,.,第第n个元素为个元素为xn,则这个则这个n元组就记为元组就记为(x1,x2,.,xn)。称两个称两个n元组元组(x1,x2,.,xn)与与(y1,y2,.,yn)相等当且仅相等当且仅当当x1y1,x2y2,.,xn=yn。笛卡儿乘积笛卡儿乘积集合论集合论与图论与图论39/42例如：例如： 一个一个n次整系数多项式次整系数多项式, a0 xn+a1xn-1+.+an-1x+an 在计算机中，存