1、离散数学离散数学CH3 CH3 集合的基本概念和运算集合的基本概念和运算集合论简介集合论简介康托(Georg Cantor，1845-1918)是集合论的创始人，为数学引入了集合和无限两个新事物。集合论是数学中许多分支的基础，是整个大厦的基础，是许多计算机科学理论不可或缺的工具。从历史上来看，1900年之前的数学几乎没有集合论的容身之地。当时的学术论文，文摘杂志上，集合论都被作为哲学的一部分。集合不仅可以用来表示数及其运算，更可集合不仅可以用来表示数及其运算，更可以用于非数值信息的表示和处理，如数据以用于非数值信息的表示和处理，如数据的删除、排序、插入、数据间的关系描述。的删除、排序、插入、数
2、据间的关系描述。第第3 3章章 集合的基本概念和运算集合的基本概念和运算集合集合是数学、计算机科学以及其他科学是数学、计算机科学以及其他科学的最基础的知识之一的最基础的知识之一 本章学习：本章学习：集合的基本概念和基本运算集合的基本概念和基本运算 1 1集合的基本概念集合的基本概念 2 2集合的基本运算集合的基本运算 3 3集合中元素的计数集合中元素的计数 3.13.1集合的基本概念集合的基本概念康托关于集合的描述：集合是一些确定的、不同的事物的总体，这些事物人们可以意识到，并且能判断一个给定的事物是否属于这个总体。集合是由某些相互区别的事物汇集在一起组成的整体。例例(1)所有偶数构成一个集合
3、。(2)所有在20世纪80年代出生的人构成一个集合。(3)亚洲的国家的全体构成一个集合。(4)方程x2-1=0的全体实数解集合。(5)26个英文字母的集合。(6)计算机内存的全体单元的集合。3.13.1集合的基本概念集合的基本概念集合集合是不能精确定义的、基本的数学概念是不能精确定义的、基本的数学概念一般认为一个一般认为一个集合集合指的是一些可确定、可分指的是一些可确定、可分辨的事物构成的整体辨的事物构成的整体对于给定的集合和事物，应该可以断定这个特定对于给定的集合和事物，应该可以断定这个特定的事物是否的事物是否属于属于这个集合这个集合 如果属于，就称它为这个如果属于，就称它为这个集合的元素集
4、合的元素集合的符号表示集合的符号表示 集合通常用大写英文字母表示。元素通常用小写字母表示。a是集合A的元素，记作aA，否则记为aA。集合的特点集合的特点一个集合的元素有如下特点：(1)互异性；(2)无序性；(3)确定性在集合论中，规定元素之间是在集合论中，规定元素之间是彼此相异彼此相异的，的，并且是并且是没有次序关系没有次序关系的的例如例如:集合集合3，4，5，3，4，4，4，5 5，4，3 都是同一个集合都是同一个集合集合的表示方法集合的表示方法列举法（穷举法）穷举法）：把一个集合中的所有或者部分元素列举在花括号当中，元素之间用逗号隔开。例如：例如：A=0,1,100 A=a，b，c，d 其
5、中其中a是是A的元素，记作的元素，记作aA 同样有同样有bA，cA，dA 但但e不是不是A的元素，可记作的元素，可记作e A集合的表示方法集合的表示方法描述法（谓词表示法）：用一个谓词公式P(x)表示x具有性质P，用x|P(x)表示所有具有性质P的事物组成的集合 例如：例如：x|x-2|1,x是实数 x|x是自然数,x100 x|x5+x4+x3+x+1=0 B=x|x Z 3x6一般说来，集合的元素可以是任何类型的事物一般说来，集合的元素可以是任何类型的事物一个集合也可以作为另一个集合的元素一个集合也可以作为另一个集合的元素 例如，集合例如，集合 A=a,b,c,d,d aA,b,cA,dA
6、,d A b,c,d本身也是集合本身也是集合 但，但，b A,d A b是是A的元素的元素b,c中的元素，不是中的元素，不是A的元素的元素 集合间的关系集合间的关系定义（包含关系）定义（包含关系）设设A，B为集合，如果为集合，如果B中中的每个元素都是的每个元素都是A中的元素，则称中的元素，则称B为为A的子的子集合，简称集合，简称子集合子集合，或简称，或简称子集子集。这时也称。这时也称B被被A包含包含，或，或A包含包含B。记作：。记作：B A。包含的符号化表示为：包含的符号化表示为：B A x(x Bx A)例：令例：令A=0，1，2，B=0，1,C=1，2 则有则有B A，C A，A A对任何
7、集合对任何集合S都有都有S S定义（相等关系）定义（相等关系）设设A，B为集合，如果为集合，如果B A且且A B，则，则A与与B相等相等，记作，记作A=B，符号化表示为符号化表示为A=BA B B A如果如果A和和B不相等，则记作不相等，则记作AB由以上定义可以知道，两个集合相等的充分由以上定义可以知道，两个集合相等的充分必要条件是它们具有相同的元素必要条件是它们具有相同的元素例如，例如，A=x|x是小于等于是小于等于3的素数的素数 B=x|x|x=2x=3 则则A=B定义（真子集）定义（真子集）设设A，B为集合，如果为集合，如果B A且且BA，则称，则称B是是A的的真子集真子集，记作，记作B
8、 A例如，例如，0，1是是0，1，2的真子集的真子集 但但1，3和和0，1，2都不是都不是0，1，2的真的真子集子集空集空集:不含任何元素的集合叫做不含任何元素的集合叫做空集空集，记作，记作。空集可以符号化表示为空集可以符号化表示为:=x|xx=x|xx =x|P(x)P(x)空集是客观存在的，例如空集是客观存在的，例如:A=x|xRx A=x|xRx2 2+1=0+1=0 是方程是方程x x2 2+1=0+1=0的实数解集。因为该方程没有的实数解集。因为该方程没有实数解，所以实数解，所以A=A=集合的简单性质集合的简单性质:定理定理3.13.1 空集是一切集合的子集。空集是一切集合的子集。证
9、明证明:任给集合任给集合A A，由子集定义有，由子集定义有 A A x(xx(xxA)xA)右边的蕴涵式中，因前件右边的蕴涵式中，因前件xx为假，所为假，所以整个蕴涵式对一切以整个蕴涵式对一切x x为真。为真。推论推论 空集是唯一的。空集是唯一的。证明证明:假设存在空集假设存在空集1 1和和2 2，由定理，由定理3.13.1，有，有1 12 2和和2 21 1，根据集合相等的定义得，根据集合相等的定义得1 1=2 2。例例3.13.1 确定下列命题是否为真。确定下列命题是否为真。（1 1）；（2 2）；（3 3）；（4 4）。解解:（1 1），（），（3 3），（），（4 4）为真，）为真，（
10、2 2）为假。）为假。注意注意和和 的区别的区别：不含任何元素；不含任何元素；含唯一一个元素含唯一一个元素。集合的其他一些概念集合的其他一些概念:含有含有n个元素的集合简称个元素的集合简称n元集元集，它的含有，它的含有m个（个（mn）元素的子集称作它的）元素的子集称作它的m元子集元子集。下面说明求一个下面说明求一个n元集的全部子集的方法元集的全部子集的方法例例3.23.2 A=a,b,c,A=a,b,c,求求A A的全部子集。的全部子集。解解:将将A A的子集从小到大分类：的子集从小到大分类：0 0元子集，即空集，只有元子集，即空集，只有1 1个：个：1 1 元 子 集，即元 子 集，即 单
11、元 集单 元 集 或或 单 集单 集，有，有 C C3 31 1个：个：a,b,ca,b,c2 2元子集，有元子集，有C C3 32 2个：个：a,b,a,c,b,ca,b,a,c,b,c3 3元子集，有元子集，有C C3 33 3个：个：a,b,ca,b,cA A的子集共有的子集共有8 8个个一般来说，对于一般来说，对于n n元集元集A A，它的，它的m(0mn)m(0mn)元子元子集有集有CnCnm m个。所以不同的子集总数为个。所以不同的子集总数为:C Cn n0 0+C+Cn n1 1+C+Cn nn n=2=2n n定义（幂集）定义（幂集）设设A A为集合，把为集合，把A A的全体子
12、集构成的全体子集构成的集合叫做的集合叫做A A的幂集的幂集，记作，记作P(A)P(A)，或，或P PA A，或，或2 2A A。符。符号化表示为号化表示为:P(A)=x|x P(A)=x|xAA若若A A有有n n个元素，则个元素，则P(A)P(A)有有2 2n n个元素个元素例，设例，设A=a,b,cA=a,b,c，则，则P(A)=P(A)=,a,b,c,a,b,c，a,b,a,c,b,c,a,b,a,c,b,c,a,b,c a,b,c 练习练习判断下列表达式是否成立：xx,xx,xx,xx,xx,xx,x,x,是否存在集合A,B满足AB且AB下列集合是否为某集合的幂集？(1);(2)a,;
13、(3),a;(4),a,a定义（全集）定义（全集）在一个具体问题中，如果所涉在一个具体问题中，如果所涉及的集合都是某个集合的子集。则称这个集及的集合都是某个集合的子集。则称这个集合为全集，记作合为全集，记作E（或（或U）全集是个全集是个相对性相对性的概念。由于所研究的问题的概念。由于所研究的问题不同，所取的全集也不同不同，所取的全集也不同例如，研究平面解析几何的问题时把整个坐例如，研究平面解析几何的问题时把整个坐标平面取作全集，研究整数的问题时，把整标平面取作全集，研究整数的问题时，把整数集取作全集数集取作全集3.23.2集合的基本运算集合的基本运算给定集合给定集合A A和和B B，可以通过集
14、合的并，可以通过集合的并，交，交 ，相对补，相对补，绝对补，绝对补，以及对称差，以及对称差等等运算运算产生新的集合产生新的集合定义（并、交、相对补）定义（并、交、相对补）设设A，B为集合，为集合，A与与B的的并集并集AB，交集交集AB，B对对A的的相对补相对补集集A-B分别定义如下：分别定义如下：A B=x|xAxB A B =x|xAxB AB=x|xAx BA B由由A或或B中的元素构成中的元素构成A B由由A和和B中的公共元素构成中的公共元素构成AB 由属于由属于A但不属于但不属于B中的元素构成中的元素构成例例:A=1:A=1，3 3，44，B=2B=2，33，C=4C=4 则有则有 A
15、 B=1A B=1，2 2，3 3，4=B A4=B A A B=3=B A A B=3=B A B C=B C=A A B=1B=1，44 B B A=2A=2 C C A=A=当两个集合的交集是空集时，称它们是当两个集合的交集是空集时，称它们是不相交不相交的的。交运算和并运算的扩展交运算和并运算的扩展 n n个集合个集合A A1 1，A A2 2，A An n的并集和交集定义如下的并集和交集定义如下:A A1 1A A2 2 A An n=x|xA=x|xA1 1xAxA2 2xAxAn n 简记为简记为:i=1i=1n nA Ai iA A1 1A A2 2 A An n=x|xA=x|
16、xA1 1xAxA2 2xAxAn n 简记为简记为:i=1i=1n nA Ai i 例如，例如，0,1 0,1 1,2 1,2 0,1,1,20,1,1,2 =0,1,2,0,1,1,2 =0,1,2,0,1,1,2 0,1 0,1 1,2 1,2 1,3=1 1,3=1 定义定义(绝对补集绝对补集):设设E为全集，为全集，A E，则，则称称A对对E的相对补集为的相对补集为A的的绝对补集绝对补集，记作，记作A，即：，即：A=EA=x|xEx A例例:E=0,1,2,3,A=0,1,2,B=0,1,2,3,C=则则 A=3，B=，C=E定义（对称差定义（对称差）设设A，B为集合，则为集合，则A
17、与与B的的对称差对称差是是:A B=(AB)(BA)例例:A=0,1,2,B=2,3 则则 A B=0,13=0,1,3A与与B的的对称差对称差也可也可等价地等价地定义为定义为 A B=（A B）（）（A B）这时，对于上例，有这时，对于上例，有 A B=0,1,2,32=0,1,3课堂练习课堂练习P72 3.1 集合的算律集合的算律任何代数运算都遵从一定的任何代数运算都遵从一定的算律算律（恒等恒等式式），集合运算也不例外），集合运算也不例外下面列出的是集合运算的主要算律，其中下面列出的是集合运算的主要算律，其中的的A，B，C表示任意的集合，表示任意的集合，E是全集是全集幂等律幂等律 AA=A
18、 AA=A AA=A AA=A结合律结合律 （AB)C=AAB)C=A（BCBC）(AB)C=A(AB)C=A（BCBC）交换律交换律 AB=BA AB=BA AB=BAAB=BA分配律分配律 AA（BCBC）=（ABAB）（ACAC）AA（BCBC）=（ABAB）（ACAC）同一律同一律 AA=A=A AE=A AE=A零律零律 AE=EAE=E A A=排中律排中律 AA=E 矛盾律矛盾律 AA=吸收律吸收律 A（AB）=A A（AB）=A双重否定律双重否定律 （A）=A德德.摩根律摩根律 ABAB）=AA B B （ABAB）=AA B B =E=E E=E=A-A-（BCBC）=（A-
19、BA-B）（A-CA-C）A-A-（BCBC）=（A-BA-B）（A-CA-C）恒等式及集合相等的证明方法恒等式及集合相等的证明方法之一之一证明的证明的基本思想基本思想是：是：欲证欲证P=Q，即证：，即证：P QQ P 也就是要证明对任意的也就是要证明对任意的x有有 xP xQ例例:证明证明 A-A-（BCBC）=（A-BA-B）（A-CA-C）即证即证对对 x,xA-(BC)x,xA-(BC)x(A-B)(A-C)x(A-B)(A-C)证：证：xA-(BC)xA-(BC)xAx xAx BC BC xA xA(x BC)(x BC)xA xA(x Bx C)(x Bx C)xA(xA(x B
20、x Bx C)x C)xA x xA x B x B x C C (xAx (xAx B)(xAx B)(xAx C)C)xA-B xA-C xA-B xA-C x(A-B)(A-C)x(A-B)(A-C)A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)恒等式及集合相等的证明方法恒等式及集合相等的证明方法之二：之二：利用已知算律证明利用已知算律证明例例:证明（证明（AB）B=AB 证证:（AB）B=（AB）B =（AB）（BB）=（AB）E =AB除以上所给的算律以外，还有一些关于集合运除以上所给的算律以外，还有一些关于集合运算性质的重要结果算性质的重要结果ABABA,AB
21、A,ABB B A AAB,BAB,BABABA-BA-BA AAB=B AB=B A AB B AB=A AB=A A-B=A-B=A-B=A A-B=A B BA-B=A-(A A-B=A-(A B)B)文氏图文氏图集合之间的相互关系和有关的运算可以用文集合之间的相互关系和有关的运算可以用文氏图给予形象的描述氏图给予形象的描述文氏图的构造方法如下文氏图的构造方法如下:首先画一个大矩形表示全集首先画一个大矩形表示全集E其次在矩形内画一些圆或任何其它的适合的闭曲其次在矩形内画一些圆或任何其它的适合的闭曲线，用圆的内部表示集合线，用圆的内部表示集合通常在图中画有阴影的区域表示新组成的集合通常在图
22、中画有阴影的区域表示新组成的集合在一般情况下，如果不作特殊的说明，这些表在一般情况下，如果不作特殊的说明，这些表示集合的圆应该是彼此相交的示集合的圆应该是彼此相交的如果已知某两个集合是不交的，则表示它们的如果已知某两个集合是不交的，则表示它们的圆彼此相离圆彼此相离例例:用文氏图表示下面集合用文氏图表示下面集合(1)(1)A(BC)A(BC)(2)(A B)-C(2)(A B)-C集合中元素的计数集合中元素的计数集合集合A=1，2，n，它含有，它含有n个元素，个元素，这个这个集合的集合的基数基数是是n，记作，记作 card A=n 或或|A|=n显然空集的基数是显然空集的基数是0，即，即|=0定
23、义定义 设A为集合，若存在自然数n，使得card A=|A|=n，则称A为有穷集，否则就称A为无穷集。例例 有100名程序员，其中47名熟悉C语言，35名熟悉C+语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉？常用方法：文氏图、容斥原理使用文氏图解决有穷集的计数问题使用文氏图解决有穷集的计数问题 1.1.首先根据已知条件把对应的文氏图画出首先根据已知条件把对应的文氏图画出一般地说，每一条性质决定一个集合，有多少条一般地说，每一条性质决定一个集合，有多少条性质，就有多少个集合性质，就有多少个集合如果没有特殊的说明，任何两个集合都是相交的如果没有特殊的说明，任何两个集合都是相交的2.2
24、.然后将已知集合的基数填入表示该集合的区域然后将已知集合的基数填入表示该集合的区域内内通常是从几个集合的交集填起通常是从几个集合的交集填起接着根据计算的结果将数字逐步填入其它空白区接着根据计算的结果将数字逐步填入其它空白区域内域内直到所有区域部填好为止直到所有区域部填好为止例例:有有100100名程序员，其中名程序员，其中4747名熟悉名熟悉FORTRANFORTRAN语言，语言，3535名熟悉名熟悉PASCALPASCAL语言，语言，2323名熟悉这名熟悉这两种语言。问有多少人对这两种语言不熟两种语言。问有多少人对这两种语言不熟悉？悉？例：用文氏图解决下列问题：例：用文氏图解决下列问题：某学
25、校足球队某学校足球队38人，篮球队人，篮球队15人，棒球人，棒球队队20人，三个队总人数人，三个队总人数58人，其中，人，其中，3人人同时参加了同时参加了3个队，问同时参加两个队者个队，问同时参加两个队者共有几人？共有几人？3xyz求求x+y+z+358=38-x-y-3+15-x-z-3+20-y-z-3+x+y+z+3求得：求得：x+y+z=90所以同时参加两个队的人有12个练习练习:对对2424名科技人员进行掌握外语情况的名科技人员进行掌握外语情况的调查调查,其统计资料如下其统计资料如下:所有人员起码会一所有人员起码会一门外语。会英、日、德和法语的人数分别门外语。会英、日、德和法语的人数
26、分别为为1313、5 5、1010和和9 9人。其中同时会英语和日人。其中同时会英语和日语的有语的有2 2人。同时会英语和法语，或者同时人。同时会英语和法语，或者同时会英语和德语，或者同时会德语和法语两会英语和德语，或者同时会德语和法语两种语言的各有种语言的各有4 4人。会日语的人既不懂法语人。会日语的人既不懂法语也不懂德语。也不懂德语。求：只会英语、法语、德语和日语的分别求：只会英语、法语、德语和日语的分别有几人？有几人？同时会英语、法语、德语的有几人？同时会英语、法语、德语的有几人？000X=1例例:一个班里有一个班里有5050个学生，在第一次考试中个学生，在第一次考试中有有2626人得人
27、得5 5分，在第二次考试中有分，在第二次考试中有2121人得人得5 5分。如果两次考试中都没得分。如果两次考试中都没得5 5分的有分的有1717人，人，那么两次考试都得那么两次考试都得5 5分的有多少人？分的有多少人？X=14包含排斥原理的简单形式包含排斥原理的简单形式设S是有穷集，P1和P2分别表示两种性质，对于S中的任何一个元素x，只能处于以下4种情况之一：(1)只具有性质P1；(2)只具有性质P2；(3)同时具有两种性质；(4)两种性质都没有。设A1和A2分别表示S中具有性质P1和P2的元素的集合，则|A1A2|=|S|-(|A1|+|A2|)+|A1A2|推论：|A1A2|=(|A1|
28、+|A2|)-|A1A2|包含排斥原理包含排斥原理定理3.2 设S为有穷集，P1,P2,Pm是m个性质。S中的任何元素x或者具有性质Pi，或者不具有性质Pi(i=1,2,m),两种情况必居其一。令Ai表示S中具有性质Pi的元素构成的子集，则S中不具有性质P1,P2,Pm的元素为|A AA AA A|1)1)(|A AA AA A|A AA A|A A|S S|A AA AA A|m m2 21 1m mk kj jm mk kj ji i1 1i ij jm mj ji i1 1i im m1 1i ii im m2 21 1推论推论S中至少具有一条性质的元素数为m mk kj ji i1 1
29、m m2 21 11 1m mk kj ji im mj ji i1 1j ji im m1 1i ii im m2 21 1|A AA AA A|1)1)(|A AA AA A|A AA A|A A|A AA AA A|例3.10求1到1000之间(包含1和1000在内)既不能被5和6，也不能被8整除的数有多少个。解：设Sx|xZ1x1000 A x|xSx可被5整除 B x|xSx可被6整除 C x|xSx可被8整除|T|表示有穷集T中的元素数x表示小于等于x的最大整数lcm(x1,x2,xn)表示x1,x2,xn的最小公倍数例3.10|A|1000/5200|B|1000/6166|C|
30、1000/8125|AB|1000/lcm(5,6)33|AC|1000/lcm(5,8)25|BC|1000/lcm(6,8)41|ABC|1000/lcm(5,6,8)8例3.10根据包含排斥原理，所求不能被5，6和8整除的数应为6006008 8-41)41)2525(33(33125)125)166166(200(200-10001000|C CB BA A|)|)C CB B|C CA A|B BA A(|(|)|)C C|B B|A A(|(|S S|C CB BA A|容斥原理实例容斥原理实例2某学院选课情况如下：260人选C语言，208人选编译原理，160人选人工智能，76人选
31、C语言和编译原理，48人选C语言和人工智能，62人选编译原理和人工智能，全部3门课均选的有30人，3门课均没选的有150人(1)该学院共有多少人？(2)有多少学生选C语言和编译原理，但不选人工智能？(3)有多少学生选C语言和人工智能，但不选编译原理？(4)有多少学生选人工智能和编译原理，但不选C语言？(5)有多少学生选C语言，而不选其他两门课？(6)有多少学生选编译原理，而不选其他两门课？(7)有多少学生选人工智能，而不选其他两门课？容斥原理实例容斥原理实例3某班学生150人，数学考试成绩90以上的有80人，语文考试成绩90以上的有75人，两门课程均在90以上的有50人，问(1)只有一门课程在90以上的学生有多少人？(2)两门课程均不在90以上的学生有多少人？作业P75 3.11 4、53.12 5、63.13 2、33.143.15 2、33.183.19Q&A59
