离散数学及其应用-03 集合的基本概念和运算

3.1集合的基本概念与表示3.2集合的运算3.3集合元素的计数第三章集合的基本概念和运算基本概念集合：一些不同对象的全体，通常用大写的英文字母A，B，C…表示。对象：组成集合的元素，一般可用小写英文字母a，b，c…表示。

3.1.1集合的基本概念元素和集合之间的关系：是隶属关系，即属于或不属于。如果a是A的元素，则记为a∈A，读作“a属于A”或“a在集合A之中”。如果a不是A的元素，则记为a∉A或┐(a∈A)，读作“a不属于A”或“a不在集合A之中”。其中“∈”表示一种关系。

3.1.1集合的基本概念集合的特性：(1)确定性：a∈A或a∉A，二者必居其一并仅居其一。(2)互异性：{1，2，3，2}与{1，2，3}视作一个集合。(3)无序性：{1，2，3}、{2，3，1}与{3，1，2}视为一个集合。3.1.1集合的基本概念集合的基数(势)：集合A

中的不同的元素的数目，可称为集合A的基数或者势，记为|A|。基数有限的集合称为有穷集合，否则称为无穷集合。3.1.1集合的基本概念表示集合的方法:(1)列举法：将集合的元素列举出来并写在一个花括号里，元素之间用逗号分开。例如:设A是由a，b，c，d元素构成的集合，B是由a，{b}，{{c，d}}为元素构成的集合，则A={a，b，c，d}，B={a，{b}，{{c，d}}}。说明：集合B说明集合也可用作元素，因此，尽管集合与其元素是两个截然不同的概念，但一个集合完全可以成为另一个集合的元素。3.1.2集合的表示(2)描述法：规定一个集合A时，将A中元素的特征用一个谓词公式来描述，用谓词P(x)表示x具有性质P，用{x|P(x)}表示具有性质P的集合A，即A={x|P(x)}。3.1.2集合的表示【例3.1.1】

(1)设A(x):x是英文字母,则S={x|A(x)}表示26个英文字母的集合。(2)S={x|x是自然数,并且x2-4=0}。(3)A={1,2,3,4}。(4)B={0,1,4,9,16,…,n2,…}。(5)Q+={x|x是一个正有理数}。(6)C={…,-3,-1,1,3,5,…}={x|x是奇数}。(7)C语言所有关键字。3.1.2集合的表示常见数集符号：N(Natural)表示自然数集合(含0)Z表示整数集合，本书中我们也常用I(Integer)表示整数集合Q(Quotient)表示有理数集合R(Real)表示实数集合C(Complex)表示复数集合P(Proton)表示素数集合

3.1.2集合的表示3.1.3集合的关系定义3.1.1

设A、B为任意两个集合，如果A的每一个元素都是B的元素，则称集合A为集合B的子集合(或子集，subsets)，表示为A⊆B(或B⊇A)，读作“A包含于B”(或“B包含A”)。其符号化形式为A⊆B<=>

∀x(x∈A→x∈B)若A不是B的子集，则记作A

⊈

B，其符号化形式为

A⊈B=>

∃x(x∈A∧x∉B)集合之间的子集关系或包含关系是集合之间最重要的关系之一。集合包含具有性质：(1)自反性：A⊆A;(2)传递性：A⊆B且B⊆C，则A⊆C;(3)A⊆B且A⊈C，则B⊈C。

3.1.3集合的关系【例3.1.2】

(1){a，b}⊆{a，c，b，d}

(2){a，b，c}⊆{a，b，c}

(3){a}⊆{a，b}，但a⊈{a，b}，只有a∈{a，b}。注意：不过存在这样两个集合，其中一个既是另一个的子集，又是它的元素。例如：{a}∈{a，{a}}，且{a}⊆{a，{a}}。

3.1.3集合的关系定义3.1.2

设A、B为任意两个集合，若B包含A

同时A包含B，则称集合A和B相等，记作A=B。即对任意集合A、B，有A=B<=>A⊆B∧B⊆A

<=>∀x(x∈A

x∈B)

3.1.3集合的关系定义3.1.3

设A、B为任意两个集合，若A是B的子集且A≠B，则称A是B的真子集或称B真包含A，记为A⊂B。即A⊂B<=>A⊆B且A≠B若集合A不是集合B的真子集，则记为A⊄B

，其符号化形式为

A⊄B<=>∃x(x∈A∧x∉

B)∨(A=B)<=>A⊈B∨A=B

3.1.3集合的关系集合的真包含具有性质：(1)反自反性：A⊄A;(2)传递性：若A⊂B且

B⊂C，则A⊂C;(3)反对称性：若A⊂B，则B⊄A。

3.1.3集合的关系定义3.1.4

没有任何元素的集合称为空集合，简称为空集，记为φ。例如：(1)|φ|=0(2)|{φ}|=1注意：a≠{a}，前者为一对象，后者为仅含该对象的单元素集合；φ≠{φ}，前者是没有元素的集合，后者是恰含一个元素——空集的单元素集。3.1.3集合的关系定理3.1.1

空集是任意集合的子集，即对任何集合A，φ⊆A。推论

空集是唯一的。

3.1.3集合的关系定义3.1.5

在一定范围中，如果所有集合均为某一集合的子集，则称某集合为全集，常记为E，即∀x(x∈E)为真，因此

E＝{x|p(x)∨┐P(x)}，P(x)是任意谓词。

3.1.3集合的关系定理3.1.2

设A为一有限集合，|A|=n，那么A的子集个数为2n。

3.1.3集合的关系定义3.1.6

给定集合A，由A的所有子集为元素构成的集合，称为集合A的幂集，记作P(A)，即

P(A)＝{x|x⊆A｝。由于φ

⊆

A，A⊆A，故必有φ∈P(A)，A∈P(A)。例如：(1)A=φ，P(A)={φ}(2)A={a}，P(A)={φ

，{a}}(3)A={a，b}，P(A)={φ，{a}，{b}，{a，b}}注意：幂集元素的个数与集合A的元素个数有关，且当集合A的基数为n时，A有2n个子集，因此|P(A)|=2n。3.1.3集合的关系注意：

φ⊆{{φ}，φ}

φ∈{{φ}，φ}

φ⊆{{φ}}

φ∈{{φ}}

{a}∈{{a}}

{a}⊆{{a}}

{a}∈{{a}，a}

{a}⊆{{a}，a}✔✔✔✘✔✘✔✔3.1.3集合的关系【例3.1.3】(1)设A={φ，{φ}}，B={φ，{φ}，{φ，{φ}}}，求P(A)和P(B)。(2)设A={Φ，{b，1}}，B={a，{b，c}}，求P(A)和P(B)。

解：(1)P(A)={φ，{φ}，{{φ}}，{φ，{φ}}}P(B)={φ，{φ}，{{φ}}，{{φ，{φ}}}，{φ，{φ}}，{φ

，{φ

，{φ}}}，{{φ}，{φ

，{φ}}}，{φ

，{φ}，{φ

，{φ}}}}(2)P(A)＝｛Φ，｛Φ｝，{{b,1}}，{Φ,{b,1}}｝P(B)={Φ,{a},{{b,c}},{a,{b,c}}}

3.1.3集合的关系定理3.1.3

设A，B为任意集合，A⊆B当且仅当P(A)⊆P(B)。3.1.3集合的关系子集的编码表示法：二进制数为足码表示任意集合的子集。设集合A={a1，a2，a3，…，an}。用BXXX…X表示A的一个子集，其中B是子集符号，足码XXX…X是n位二进制数，n是集合A的基数，对于A，如果子集含有ai，则在足码的第i位上记入1，否则为0。所以P(A)={Bk|0≤k≤2n-1}也可将Bi的二进制数换算成十进制数。3.1.4集合的计算机表示【例3.1.4】设A={a，b，c}，则各子集的编码表示为φ=B000=B0 {a}=B100=B4{b}=B010=B2 {c}=B001=B1{a，b}=B110=B6 {a，c}=B101=B5{b，c}=B011=B3 {a，b，c}=B111=B73.1.4集合的计算机表示定义3.2.1

设A，B为任意两个集合。由那些或属于A或属于B或同时属于二者的所有元素构成的集合称为A与B的并集(unionset)，记为A∪B。形式化为A∪B＝｛x|x∈A∨x∈B｝“∪”称为并运算3.2.1集合的基本运算定理3.2.1

对任意集合A，B，有A⊆

A∪B，B⊆A∪B

3.2.1集合的基本运算定义3.2.2

设A，B为任意两个集合。由集合A和B

所共有的全部元素构成的集合称为A与B的交集(intersectionset)，记为A∩B。形式化为A∩B=｛x|x∈A∧x∈B｝,“∩”称为交运算。

3.2.1集合的基本运算定理3.2.2

对任意集合A，B，有A∩B⊆

A，A∩B⊆

B。

3.2.1集合的基本运算定义3.2.3设A，B为任意两个集合。由属于A但不属于集合B

的所有元素构成的集合称为A与B的差集(differenceset)，记为A-B，又称为相对补。形式化为

A-B＝｛x|x∈A∧x∉B｝“-”称为差运算。

3.2.1集合的基本运算定理3.2.3

对任意的集合A，B，C，有(1)A-B=A-(A∩B)(2)A∪(B-A)=A∪B(3)A∩(B-C)=(A∩B)-C

(4)A-B⊆

A

3.2.1集合的基本运算定义3.2.4

设A为任意集合，E是全集。对于

E

和

A

所进行的差运算称为A的补集(complementset)，也称为A

对E

的相对补集，称为A的绝对补集，或简称为A

的补集，记为～A。即

～A=E-A=｛x|x∉A｝

“～”称为补运算，它是一元运算，是差运算的特例。

3.2.1集合的基本运算定理3.2.4

对任意的集合A，B，若A⊆B，则～B⊆～A。3.2.1集合的基本运算集合的图形表示法：集合与集合之间的关系以及一些运算结果可用文氏图给予直观的表示。3.2.1集合的基本运算其构造如下：用一个大的矩形表示全集的所有元素(有时为简单起见，可将全集省略)。在矩形内画一些圆(或任何其他形状的闭曲线)，用圆或其他闭曲线的内部代表E的子集，用圆的内部的点表示相应集合的元素。不同的圆代表不同的集合，并将运算结果得到的集合用阴影或斜线的区域表示新组成的集合。3.2.1集合的基本运算文氏图的优点是形象直观，易于理解。缺点是理论基础不够严谨。需要注意的是这里介绍的文氏图只能帮助我们形象地理解复杂的集合关系，一般不作为一种证明方法来证明集合等式及包含关系。因此只能用于说明，不能用于证明。集合的相关运算用文氏图表示如图3.2.1所示。3.2.1集合的基本运算图3.2.1ABEA∩B

ABEABEAEA∪BA-B～A3.2.1集合的基本运算【例3.2.1】设E＝{0，1，2，3，…，9，10}，A={2，4}，B={4，5，6，7}，C={0，8，9}，D＝{1，2，3，10}，则A∪B＝｛2，4，5，6，7｝A∪B∪C∪D＝E

A∩B

＝｛4｝A∩C=φA-B={2}B-A=｛5，6，7｝A-C=｛2，4｝～A=｛0，1，3，5，6，7，8，9，10｝～B＝｛0，1，2，3，8，9｝3.2.1集合的基本运算定理3.2.5

设A，B，C为任意集合，那么下列各式成立。(1)等幂律 A∪A=A

A∩A=A

(2)交换律 A∪B=B∪A

A∩B＝B∩A

(3)结合律 (A∪B)∪C=A∪(B∪C)

(A∩B)∩C=A∩(B∩C)(4)同一律 A∪φ＝AA∩E=A

(5)零律 A∩φ=φA∪E=E(6)分配律 A∪(B∩C)=(A∪B)∩(A∪C)

A∩(B∪C)=(A∩B)∪(A∩C)

3.2.2集合的基本定律(7)吸收律 A∩(A∪B)=A

A∪(A∩B)=A

(8)双重否定律～(～A)＝A

～E＝φ～φ＝E(9)排中律 A∪～A＝E(10)矛盾律A∩～A＝φ

(11)德·摩根律 ～(A∪B)＝～A∩～B

～(A∩B)＝～A∪～B

A-(B∪C)＝(A-B)∩(A-C)

A-(B∩C)＝(A-B)∪(A-C)(12)补交转换律A-B＝A∩～B

3.2.2集合的基本定律定理3.2.6

对任意集合A，B，下面四个命题等价。(1)A⊆B(2)A-B=φ(3)A∪B=B(4)A∩B=A

3.2.2集合的基本定律定理3.2.7

对任意集合A，有A-A＝φ，A-φ＝A，A-E=φ。

3.2.2集合的基本定律定理3.2.8

对任意集合A，B，若它们满足A∪B＝E和A∩B＝φ，那么B＝～A。

3.2.2集合的基本定律定义3.2.5

设A，B为任意两个集合，由或属于A或属于B，但不同时属于A

和

B

的那些元素构成的集合称为集合A，B的环和(cyclesum)或对称差，记为A⊕B。即有

A

⊕

B=(A-B)∪(B-A)

“⊕”称为对称差运算。该运算的文氏图如图3.2.2所示。3.2.3集合的环和图3.2.2ABA⊕B3.2.3集合的环和定理3.2.9

对任意集合A，B，有A

⊕

B=(A∪B)-(A∩B)

3.2.3集合的环和定理3.2.10

对任意集合A，B，C，有(1)交换律A⊕B=B⊕A(2)同一律A⊕φ=A

(3)零律A

⊕

A=φ(4)分配律A∩(B

⊕

C)=(A∩B)⊕(A∩C)(5)结合律(A

⊕

B)⊕

C=A

⊕(B

⊕

C)(6)吸收律A

⊕(A

⊕

B)=B

3.2.3集合的环和定理3.2.11

对任意的集合A，B，C，有(1)(A⊕E)=～A(2)～A⊕～B=A⊕B(3)～A⊕B=A⊕～B=～(A⊕B)

3.2.3集合的环和(1)设A，B，C是任意的集合，则有A

B

(A×C)

(B×C)。

(2)设A，B，C，D是任意四个集合，

则有(A×B)

(C×D)

A

C，B

D。(3)设A，B，C为任意一个集合，则有(A-B)-C=A-(B∪C)。

✔✘✔3.2.3集合的环和定理3.3.1

(基本运算的基数)假设A，B均是有穷集合，其基数分别为|A|，|B|，则(1)|A∪B|≤|A|+|B|(2)|A∩B|≤Min(|A|，|B|)(3)|A-B|≥|A|-|B|(4)|A⊕B|=|A|+|B|-2|A∩B|

3.3.1集合的计数定理3.3.2

(包含排除原理)对有限集合A和B，有|A∪B|=|A|+|B|-|A∩B|证明：

(1)当A与B不相交，即A∩B=φ，则

|A∪B|=|A|+|B|(2)若A∩B≠φ，则

|A|=|A∩～B|+|A∩B|，|B|=|～A∩B|+|A∩B|所以

|A|+|B|=|A∩～B|+|A∩B|+|～A∩B|+|A∩B|

=|A∩～B|+|～A∩B|+2|A∩B|

但

|A∩～B|+|～A∩B|+|A∩B|=|A∪B|

因此|A∪B|=|A|+|B|-|A∩B|得证。证毕3.3.1集合的计数【例3.3.1】在18个大学生中,有10人爱好跳舞,有8人爱好唱歌,有6人既爱好跳舞又爱好唱歌。问既不爱好跳舞又不爱好唱歌的学生有多少人?解设A为爱好跳舞的人的集合,B为爱好唱歌的人的集合,E为全集。根据题设有|A|=10,|B|=8,|E|=18,|A∩B|=6|A∪B|=|A|+|B|-|A∩B|=10+8-6=12|A∩B|=|E|-|A∪B|=18-12=6所以既不爱好跳舞又不爱好唱歌的学生有6人。3.3.2集合的应用定理3.3.3

设A1，A2，…，An是有限集合，其元素的基数分别为|A1|，|A2|，…，|An|，则

|A1∪A2∪…∪An|=

|Ai|-

|Ai∩Aj|+

|Ai∩Aj∩Ak|

+…+(-1)n-1|A1∩A2∩A3∩…∩An|3.3.2集合的应用【例3.3.2】

利民社区为更好地为民服务,对该社区内的260人进行了调研。调研结果,其中有64人会玩军棋,94人会玩象棋,58人会玩围棋,28人同时会玩军棋和围棋,26人同时会玩军棋和象棋,22人同时会玩象棋和围棋,14人同时会玩三种棋类。(1)三种棋类都不会的人有多少?(2)只会玩象棋的人有多少?解3.3.2集合的应用3.3.2集合的应用方法二：

借助文氏图法可以很方便地解决有限集合的计数问题。首先根据已知条件画出相应的文氏图。如果没有特殊说明，两个集合一般都画成相交的，然后将已知的集合的基数填入文氏图中的相应区域，用x等字母来表示未知区域，根据题目中的条件，列出相应的方程或方程组，解出未知数即可得出所需求的集合的基数。3.3.2集合的应用【例3.3.3】在31个公司员工中,有17人爱好音乐,有13人爱好乒乓球,有15人爱好足球,有7人爱好美术,其中同时爱好音乐和美术的有4人,爱好音乐、足球和乒乓球中任意两项的都是6人,已知爱好美术的人既不爱好足球也不爱好乒乓球,问:同时有三种爱好的员工有多少人?只有一种爱好(或音乐或美术或足球或乒乓球)的员工有多少人?解：根据题意设E表示公司所有员工,A、B、C、D分别表示爱好音乐、乒乓球、足球和美术的人构成的集合,y1表示仅爱好音乐的人构成的集合,y2表示仅爱好乒乓球的人构成的集合,y3表示仅爱好足球的人构成的集合,x表示同时爱好音乐、乒乓球、足球的人构成的集合。

3.3.2集合的应用

|E|=31,|A|=17,|B|=15,|C|=13,|D|=7全集E:y1+y2+y3+3(6-x)+x+7=31(1)y1+2(6-x)+x=13(2)y2+2(6-x)+x=15(3)y3+2(6-x)+x=13(4)所以把(1)代入(2)+(3)+(4),得24+3(6-x)+2x=15+13+13即x=1,同时有三种爱好的人为1人。文氏图法如图3-3-1所示。3.3.2集合的应用图3.3.13.3.2集合的应用将x代入(1)得:y1+y2+y3=31-23=8(人),所以只有一种爱好的有:8+3=11(人)。3.3.2集合的应用【例3.3.4】求1到500的整数中（1和500包含在内）可以被4或5整除，但不能被7整除的整数有多少个？。3.3.2集合的应用解：E={x|1≤x≤500，x∈Z}，A={x|x能被4整除}，

B={x|x能被5整除}，C={x|x能被7整除}

|E|=500|A|=125

|B|=100|C|=71

|A∩B|=25|A∩C|=17

|B∩C|=214|A∩B∩C|=3

|（A∪B）-C|=|A∪B|-|A∩C|-|B∩C|+|A∩B∩C|

=|A|+|B|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

=125+100-25-17-14+3=172

所以

1到500的整数中（包括1和500），能被4或5整除但不能被7整除的整数有172个。3.3.2集合的应用【例3.3.5】对某学院会玩棋类的308人进行了调研。调研结果，其中有142人会玩军棋，140人会玩象棋，154人会玩围棋，只有58人三种棋类都会玩，试问：仅同时会两种棋类的有多少人？3.3.2集合的应用解：设A为玩军棋，B为玩象棋，C为玩围棋。其中a为仅会玩军棋,b同时会军棋和象棋,c仅会玩象棋,d同时会玩象棋与围棋,e仅会玩围棋,f仅会玩军棋和围棋,g三种同时会玩的人数，另外，由于会玩棋类的人数总和为308人，没有不会玩的，如文氏图所示。

a+b+c+d+e+f+g=308，即a+b+c+d+e+f＝250

g=58

a+b+f+g=142，即a+b+f=84

b+c+d+g=140，即b+c+d=82

d+e+f+g=154，即d+e+f=96

可得：b+d+f=12

BACabcdefg3.3.2集合的应用【例3.3.6】求1到1000的整数中（1和1000包含在内）既不能被5和6整除，也不能被8整除的整数有多少个？。3.3.2集合的应用3.3集合元素的计数解：E={x|1≤x≤1000，x∈Z}，A={x|x能被5整除}，

B={x|x能被6整除}，C={x|x能被8整除}

|E|=1000|A|=200

|B|=166|C|=125

|A∩B|=33|A∩C|=25

|B∩C|=41|A∩B∩C|=8

|E-（A∪B∪C）|=|E-|-|A∪B∪C|

=|E|-(|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|)

=1000-(200+166+125-33-25-41+8)=600

所以

1到1000的整数中（1和1000包含在内）既不能被5和6整除，也不能被8整除的整数有600个。【例3.3.7】对24名会外语的