第1节集合及其运算精选文档.ppt

《第1节集合及其运算精选文档.ppt》由会员分享，可在线阅读，更多相关《第1节集合及其运算精选文档.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1节集合及其运算1本讲稿第一页，共四十二页一、集合与图论是离散数学的重要组成部分一、集合与图论是离散数学的重要组成部分引引 言言离散数学主要内容离散数学主要内容:集合论、图论、近世代数、数理逻辑、集合论、图论、近世代数、数理逻辑、组合数学等组合数学等二、集合与图论与后继课程二、集合与图论与后继课程 形式语言、形式语言、近世代数、数据库系统原理、数近世代数、数据库系统原理、数据结构、计算机网络等据结构、计算机网络等2本讲稿第二页，共四十二页三、教学主要内容和教学安排三、教学主要内容和教学安排(36学时学时)第第1章章 集合集合(4学时学时)第第2章章 映射映射(2学时学时)第第4章章 无穷集合

2、及其基数无穷集合及其基数(2学时学时)第第3章章 关系关系(10学时学时)第第6章章 图的基本概念图的基本概念(8学时学时)第第7章章 树与割集树与割集(2学时学时)第第8章章 连通度和匹配连通度和匹配(2学时学时)第第9章章 平面图和图的着色平面图和图的着色(4学时学时)第第10章章 有向图有向图(2学时学时)引引 言言3本讲稿第三页，共四十二页四、主要教材四、主要教材离散数学引论离散数学引论 王义和王义和 哈尔滨工业大学出版社哈尔滨工业大学出版社离散数学离散数学 耿素云等耿素云等 高等教育出版社高等教育出版社离散数学离散数学 左孝凌等左孝凌等 上海科技文献出版社上海科技文献出版社方式：笔试

3、方式：笔试成绩：总成绩成绩：总成绩(100分分)其中：平时成绩其中：平时成绩(作业与出勤作业与出勤)(20分分)笔试成绩笔试成绩(80分分)五、考试方式与成绩五、考试方式与成绩引引 言言4本讲稿第四页，共四十二页 集合论集合论 集合论成了数学各分支的基础，也是计算机科学非集合论成了数学各分支的基础，也是计算机科学非常重要的基础知识。常重要的基础知识。它它的的起起源源可可追追溯溯到到16世世纪纪末末，主主要要是是对对数数集集进进行行了了卓卓有有成成效效的的研研究究。但但集集合合论论实实际际发发展展是是由由19世世纪纪70年年代代德德国国数数学学家家康康托托(G.Cantor)在在无无穷穷序序列列

4、和和分分析析的的有有关关课课题题的的理理论论研研究究中中创创立立的的。康康托托对对具具有有任任意意特特性性的的无无穷穷集集合合进进入入了了深深入入的的探探讨讨，提提出出了了关关于于基基数数、序序数数、超超穷穷数数和和良良序序集集等等理理论论，奠奠定定了了集集合合论论的的深深厚厚基基础础。因因此此，康托被誉为集合论的创始人康托被誉为集合论的创始人。5本讲稿第五页，共四十二页 但随着集合论的发展，以及它与数学哲学密切联系但随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在所作的讨论，在20世纪初，出现了许多似是而非、自相矛世纪初，出现了许多似是而非、自相矛盾的悖论，如盾的悖论，如康托悖论康托

5、悖论、罗素罗素(Russell)悖论悖论，有力冲击了，有力冲击了或者说动摇了集合论的发展。由此，激发许多数学家、或者说动摇了集合论的发展。由此，激发许多数学家、哲学家为克服这些矛盾建立了各种哲学家为克服这些矛盾建立了各种公理化集合论体系公理化集合论体系。集合论集合论 朴素集合论体系朴素集合论体系 (也称也称康托康托(Cantor)集合论体系集合论体系)公理集合论体系公理集合论体系集合论集合论6本讲稿第六页，共四十二页 1965年，美国学者年，美国学者L.A.Zadeh提出了提出了Fuzzy集概念集概念(理理论论)。20世纪世纪80年代初，波兰学者年代初，波兰学者Z.Pawlak发表了发表了Ro

6、ugh集集理论。理论。这两种理论区别以往的集合论，是一种新的模糊集理论。这两种理论区别以往的集合论，是一种新的模糊集理论。集合论集合论 集合论在计算机科学、人工智能领域、逻辑学及语言集合论在计算机科学、人工智能领域、逻辑学及语言学等方面都有着重要的应用。对于从事计算机科学的工作学等方面都有着重要的应用。对于从事计算机科学的工作者来说，集合论是不可缺少的理论知识，熟悉和掌握它是者来说，集合论是不可缺少的理论知识，熟悉和掌握它是十分必要的。十分必要的。7本讲稿第七页，共四十二页 第第1节节 集合及其运算集合及其运算主要内容：主要内容：集合的概念集合的概念集合的基本运算集合的基本运算笛卡儿乘积笛卡儿

7、乘积8本讲稿第八页，共四十二页1.1 集合的概念集合的概念 在朴素集合论体系中，在朴素集合论体系中，“集合集合”是集合论中的一个原始概是集合论中的一个原始概念，我们知道在欧氏几何中对点、线不加定义，在朴素集合论念，我们知道在欧氏几何中对点、线不加定义，在朴素集合论中中“集合集合”不能严格定义。不能严格定义。通常把一些互不相同的东西放在一起所形成的整体就叫通常把一些互不相同的东西放在一起所形成的整体就叫做一个做一个集合集合。构成集合的每一个东西，称为该集合的一个。构成集合的每一个东西，称为该集合的一个元素元素。集合的定义集合的定义9本讲稿第九页，共四十二页康托康托(Cantor)1874年所给的

8、年所给的“集合集合”定义：定义：把若干确定的有区别的（不论是具体的或抽象的）事把若干确定的有区别的（不论是具体的或抽象的）事物合并起来，看作一个整体，就称为一个物合并起来，看作一个整体，就称为一个集合集合，其中各事，其中各事物称为该集合的物称为该集合的元素元素。常用大写英文字母常用大写英文字母A,B,C,.表示集合，用小写英文字表示集合，用小写英文字母母a,b,c,.,表示集合中的元素。表示集合中的元素。如果如果x是集合是集合A的元素，就说的元素，就说x属于属于A，记为，记为x A；如果如果x不是集合不是集合A的元素，就说的元素，就说x不属于不属于A，记为，记为x A或者或者x A；集合的概念

9、集合的概念10本讲稿第十页，共四十二页 (3)确定性确定性：对于一个集合：对于一个集合A来说，某一对象来说，某一对象x或者是集或者是集合合A的元素，或者不是，两者必居其一。的元素，或者不是，两者必居其一。集合的性质集合的性质 (2)无序性无序性：集合中的元素不规定顺序。：集合中的元素不规定顺序。(1)互异性互异性：集合中的元素是各不相同的。：集合中的元素是各不相同的。(4)任意性任意性：集合的元素可以是具体的，也可以是抽象的；：集合的元素可以是具体的，也可以是抽象的；集合的元素可以是集合。集合的元素可以是集合。11本讲稿第十一页，共四十二页集合的表示方法集合的表示方法 列举法列举法：列出集合中

10、的全体元素，元素之间用逗：列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来。号分开，然后用花括号括起来。描述法描述法：当集合当集合A是具有某种性质是具有某种性质P的元素全体时，的元素全体时，我们往往用下面的形式表示我们往往用下面的形式表示A。A=x|x具有性质具有性质P注：集合的两种表示法有时是可以互相转化的。注：集合的两种表示法有时是可以互相转化的。12本讲稿第十二页，共四十二页集合之间的关系集合之间的关系 定义定义1.1 设设A，B为二集合，若为二集合，若A中的每个元素都是中的每个元素都是B中的元素，则称中的元素，则称A是是B的的子集合子集合，简称，简称子集子集。这时我们。这时

11、我们说说A包含包含在在B里里(A包含于包含于B)，或，或B包含着包含着A(B包含包含A)，记作，记作A B。其符号化形式为：其符号化形式为：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。13本讲稿第十三页，共四十二页 定义定义1.4 不拥有任何元素的集合称为空集合，简称为不拥有任何元素的集合称为空

12、集合，简称为空空集集，记作，记作。几个特殊的集合：空集几个特殊的集合：空集 定理定理1.1 空集是一切集合的子集。空集是一切集合的子集。推论推论1：空集是唯一的。：空集是唯一的。由推论可知，空集无论以什么形式出现，它们都是相等的。由推论可知，空集无论以什么形式出现，它们都是相等的。空集是一切集合的子集，从这个意义上看，可以形空集是一切集合的子集，从这个意义上看，可以形象地说：象地说：是是“最小最小”的集合，有无最大的集合呢？回的集合，有无最大的集合呢？回答是否定的。答是否定的。B x,x B14本讲稿第十四页，共四十二页定义定义1.5以集合为元素的集合称为以集合为元素的集合称为集族集族。几个特

13、殊的集合：集族几个特殊的集合：集族 若若J为任一集合，对为任一集合，对J中每个元素中每个元素i有唯一的一个集合有唯一的一个集合与之对应，这个集合记为与之对应，这个集合记为Ai，那么所有这些，那么所有这些Ai，形成的集族，形成的集族就用就用Aii J表示，其表示，其J称为标号集。称为标号集。A=A0,A1,.,Ap是以是以J=0,1,2,.p为标号集的集族，也为标号集的集族，也可以记为可以记为 A=Akk 0,1,2,.p=Akk J15本讲稿第十五页，共四十二页 定义定义1.6 集合集合S的所有子集的所有子集(包括空集包括空集和和S本身本身)形成的形成的集族称为集族称为S的的幂集幂集，并记为，

14、并记为2S，或记为，或记为P(S)。P(S)=2S=A|A S 为了求出给定集合为了求出给定集合A的幂集，首先求出的幂集，首先求出A的元素个数由的元素个数由少到多的所有子集，再将它们组成集合即可。少到多的所有子集，再将它们组成集合即可。几个特殊的集合：幂集几个特殊的集合：幂集例如例如：设设S=1,2,3，求，求2S.定理定理1.2 设集合设集合S的元素个数的元素个数|S|=n(n为自然数为自然数)，则，则|P(S)|=|2S|=2n。16本讲稿第十六页，共四十二页注意：注意：2=。在这里要区分在这里要区分和和:为空集为空集,而而是一个集族。是一个集族。和和?17本讲稿第十七页，共四十二页就一个

15、问题来说，常称包含所考虑问题的所有集合的集合就一个问题来说，常称包含所考虑问题的所有集合的集合S，称为该问题的，称为该问题的全集全集。几个特殊的集合：全集几个特殊的集合：全集18本讲稿第十八页，共四十二页1.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的余：的余：19本讲稿第十九页，共四十二页在

16、这种图示法中，用矩形中各点表示全集在这种图示法中，用矩形中各点表示全集S的各个元素。的各个元素。矩形中的圆里的点表示矩形中的圆里的点表示S的子集的各元素。的子集的各元素。SABAB文氏图文氏图SABABSABA BSABAB20本讲稿第二十页，共四十二页集合集合A对对S的余集的余集Ac可用文氏图表示，如下图：可用文氏图表示，如下图：AAcS文氏图文氏图21本讲稿第二十一页，共四十二页 性质性质1 设设A,B,C为任意的三个集合为任意的三个集合 (1)交换律成立交换律成立,(3)幂等律成立，即幂等律成立，即AA=A;即即AB=BA;(4)A=A;(5)AB=BA B。(2)结合律成立，即结合律成

17、立，即(AB)C=A(BC);(AB)C=A(BC)=ABC。由于结合律成立，由于结合律成立，所以所以ABC有意义有意义。从而有。从而有问题：消去律成立吗？即问题：消去律成立吗？即 若若AB=AC，则，则B=C？基本运算的性质基本运算的性质22本讲稿第二十二页，共四十二页性质性质2 设设A,B,C为任意的三个集合，则为任意的三个集合，则:(8)幂等律成立，即幂等律成立，即AA=A;(6)交换律成立，即交换律成立，即AB=BA;(9)A=;(10)AB=AA B。(7)结合律成立，即结合律成立，即(AB)C=A(BC);基本运算的性质基本运算的性质23本讲稿第二十三页，共四十二页性质性质3 设设

18、A,B,C为任意三个集合，则为任意三个集合，则 (11)交运算对并运算满足分配律交运算对并运算满足分配律,即即A(BC)=(AB)(AC);(12)并运算对交运算满足分配律并运算对交运算满足分配律,即即A(BC)=(AB)(AC)。性质性质4 对任何集合对任何集合A,B，吸收律成立。，吸收律成立。(13)A(AB)=A;(14)A(AB)=A。基本运算的性质基本运算的性质24本讲稿第二十四页，共四十二页基本运算的性质基本运算的性质性质性质5 设设A,B,C为任意三个集合，则为任意三个集合，则 (15)A(BC)=(AB)(AC)。25本讲稿第二十五页，共四十二页性质性质6 设设A,B,C为任意

19、三个集合，则为任意三个集合，则 (16)A B=B A;(18)A A=;(19)A=A;(17)(A B)C=A(B C);(20)交运算关于对称差满足分配律，即交运算关于对称差满足分配律，即 A(B C)=(AB)(AC)。基本运算的性质基本运算的性质26本讲稿第二十六页，共四十二页性质性质7 A对对S的余集的余集Ac有如下性质有如下性质:(21)S对对S的余集的余集Sc为空集，即为空集，即Sc=；(22)c=S；(23)AAc=；(24)AAc=S。基本运算的性质基本运算的性质27本讲稿第二十七页，共四十二页性质性质8 德摩根德摩根(De Morgan)公式公式:(25)(AB)c=Ac

20、Bc;(26)(AB)c=AcBc.下面的定理表明余集、差集、对称差之间的联系。下面的定理表明余集、差集、对称差之间的联系。性质性质9 设设A,B都是都是S的子集，则的子集，则(27)AB=ABc;(28)A B=(ABc)(BAc);(29)Ac=S A.基本运算的性质基本运算的性质28本讲稿第二十八页，共四十二页 A1A2.An定义为至少属于定义为至少属于A1,A2,.,An中之一中之一的那些元素构成的集合。的那些元素构成的集合。若若A1,A2,.,An,.是一个集合的无穷序列，则它们的并集是一个集合的无穷序列，则它们的并集记为：记为：A1A2.An.,A1A2.An简记为简记为 简记为简

21、记为定义定义:A1A2.An.=x|n N使得使得x An集合并运算的推广集合并运算的推广29本讲稿第二十九页，共四十二页集合交运算的推广集合交运算的推广30本讲稿第三十页，共四十二页性质性质10 设设A为一集合，为一集合，Bll I为任一集族，则为任一集族，则其中其中I。基本运算的性质基本运算的性质31本讲稿第三十一页，共四十二页设设S为任一集合，为任一集合，I为标号集，为标号集，I有有A S，则有，则有性质性质11 并集的余集等于各余集的交集，即并集的余集等于各余集的交集，即性质性质12 交集的余集等于各余集的并集，即交集的余集等于各余集的并集，即基本运算的性质基本运算的性质32本讲稿第三

22、十二页，共四十二页1.3 笛卡儿乘积笛卡儿乘积两个对象两个对象a和和b(允许允许a=b)按一定的次序排列的整体就叫做按一定的次序排列的整体就叫做一个一个二元组二元组或或有序对有序对。如果如果a排在排在b的前面，则这个有序对就记作的前面，则这个有序对就记作(a,b)，a称为称为有序对有序对(a,b)的第一个元素，的第一个元素，b称为第二个元素。称为第二个元素。有序对是由有次序的两个对象组成的，因此有序对与有序对是由有次序的两个对象组成的，因此有序对与含两个对象的集合是有区别的。集合含两个对象的集合是有区别的。集合a,b中的元素没有次中的元素没有次序，集合序，集合a,b与与b,a是同一个集合。但是

23、同一个集合。但(a,b)与与(b,a)在在ab时时是不同的。是不同的。我们规定我们规定(a,b)=(c,d)当且仅当当且仅当a=c,b=d。有序对有序对有序对的集合定义：有序对的集合定义：(a,b)=a,a,b。33本讲稿第三十三页，共四十二页 定义定义3.1 设设A与与B为任意两个集合，则称集合为任意两个集合，则称集合 (a,b)|a A且且b B 为为A与与B的的笛卡尔乘积笛卡尔乘积，记为，记为A B。A B=(a,b)|a A且且b B 例如：在平面上建立了直角坐标系后，平面上的点就用实例如：在平面上建立了直角坐标系后，平面上的点就用实数的有序对来表示。平面上的所有点之集就可视为数的有序

24、对来表示。平面上的所有点之集就可视为R R，其，其中中R为实数集。为实数集。笛卡儿乘积笛卡儿乘积34本讲稿第三十四页，共四十二页例如例如 设设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),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)对任意有穷集合，对任意有穷集合，B，如果用，如果用|A|，|B|分别表示分别表示和和B中元素的个数，那么中元

25、素的个数，那么|A B|A|B|。两个集合的笛卡尔乘积的元素个数：两个集合的笛卡尔乘积的元素个数：笛卡儿乘积笛卡儿乘积35本讲稿第三十五页，共四十二页由定义可知，对任一集合由定义可知，对任一集合A，有，有A=A。一般情况下一般情况下A B B A。含空集的两个集合的笛卡尔积：含空集的两个集合的笛卡尔积：是否满足交换律是否满足交换律?1 2=(1,2)2 1=(2,1)是否满足结合律是否满足结合律?当当A,B,C时时,(A B)C中的元素形中的元素形如如(x,y),z)A(B C)中的元素形如中的元素形如(x,(y,z)笛卡儿乘积笛卡儿乘积36本讲稿第三十六页，共四十二页性质性质 设设A,B,C

26、为任意三个集合，则笛卡儿乘积为任意三个集合，则笛卡儿乘积运算对并、交、差运算分别满足分配律，即运算对并、交、差运算分别满足分配律，即 (30)A(BC)=(A B)(A C);(31)A(BC)=(A B)(A C);(32)A(BC)=(A B)(A C)。笛卡儿乘积笛卡儿乘积37本讲稿第三十七页，共四十二页有序对也叫二元组，我们可将二元组推广到三元有序对也叫二元组，我们可将二元组推广到三元组，四元组，一直到组，四元组，一直到n元组。元组。三元组就是三个元素按一定次序组成的整体，设三元组就是三个元素按一定次序组成的整体，设第一个元素为第一个元素为x，第二个元素为，第二个元素为y，第三个元素为

27、，第三个元素为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。笛卡儿乘积笛卡儿乘积38本讲稿第三十八页，共四十二页例如：例如：一个一个n次整系数多项式次整系数多项式,a0 xn+a1xn-1+.+an

28、-1x+an 在计算机中，存入一个在计算机中，存入一个n次多项式，实质上就是次多项式，实质上就是把系数构成的把系数构成的n+1元组存入计算机。元组存入计算机。若约定按降幂排列时若约定按降幂排列时,依次写出其系数就得到一依次写出其系数就得到一个个n+1元组元组(a0,a1,.,an-1,an)。于是，一个于是，一个n次多项式就可用一个次多项式就可用一个n+1元组表示。元组表示。而一个而一个n+1元组也可视为一个元组也可视为一个n次多项式。次多项式。笛卡儿乘积笛卡儿乘积39本讲稿第三十九页，共四十二页定义定义3.2 设设A1,A2,.,An(n2)为为n个集合，集合个集合，集合 (a1,a2,.,

29、an)|ai Ai,i=1,2,.,n 称为称为A1,A2,.,An的的笛卡尔乘积笛卡尔乘积，并记为并记为:A1 A2.An。当当A1=A2=.=An=A时，时，A1 A2.An就简记为就简记为An。笛卡儿乘积笛卡儿乘积40本讲稿第四十页，共四十二页毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过。同样地，每个一个姑娘跳过舞，但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。跳过舞。证明：证明：在所有参加舞会的小伙与

30、姑娘中，必可找到两个小伙在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。中的一个跳过舞。毕业舞会问题毕业舞会问题41本讲稿第四十一页，共四十二页毕业舞会问题毕业舞会问题不失一般性，不妨设有不失一般性，不妨设有m个小伙，个小伙，n个姑娘，分别用集个姑娘，分别用集合合B、G表示表示:由于由于每个小伙子至少与一个姑娘跳过舞，但未能与所有姑每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过，所以娘跳过，所以 42本讲稿第四十二页，共四十二页