2009-7-29 离散数学 1
第三章 集合的基本概念和运算
§ 3.1 集合的基本概念
§ 3.2 集合的基本运算
§ 3.3 集合中元素的计数
2009-7-29 离散数学 2
一、集合集 合,一些可确定的可分辨的事物构成的整体。
用大写字母 A,B,C,… 标记。
§ 3.1 集合的基本概念集合的元素,一个集合的每一个特定的事物。用小写字母 a,b,c,… 标记。
如,(1) 26个英文字母的集合；
(2) 坐标平面上所有点的集合。
规定：集合的元素之间彼此相异，无次序关系。
2009-7-29 离散数学 3
二、常用的集合常用的集合记号：
N,自然数集合 (包括 0 )
Z,整数集合
Q,有理数集合
R,实数集合
C,复数集合
,空集 (不含任何元素 )
E,全集
2009-7-29 离散数学 4
三、集合的表示方法列出集合的所有元素，元素之间用逗号隔开。如 A = { a,b,c }
用谓词概括该集合中元素的属性。
即,A = { x | P (x) }
如,A = { x | x?Z? 3 < x? 6 }
1,列举法：
2,描述法：
元素与集合之间的关系 (?属于 ):
若 A={ a,{a},b,{a,b}},则 a?A,{a}?A
2009-7-29 离散数学 5
3,真子集,如果 B? A且 A? B,则 B是 A的真子集。
记作 B? A。
四、集合之间的关系
1,子 集,集合 B中的每个元素都是集合 A中的元素，
则 B是 A的子集，记作 B? A。符号化为
B? A x(x?B? x?A)
2,相等集,如果 A? B且 B? A,则 A与 B相等 。记作
A = B。符号化为 A = B? A? B? B? A
显然,A? A, A
2009-7-29 离散数学 6
解,0元子集,?，
四、集合之间的关系（续）
4,幂 集,集合 A的全体子集构成的集合，记作 P (A)。
符号化为 P (A) = { x | x? A}
例 1,A = {a,b,c}，求 A的幂集 P (A)。
n 元集 A的幂集 P (A)含有 2n个元素。
1元子集,{a},{b},{c}，
2元子集,{a,b},{a,c},{b,c}，
P(A) = {?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
3元子集,{a,b,c}
2009-7-29 离散数学 7
四、集合之间的关系（续）
例 2：计算以下幂集。
(1) P(?)；
(2) P({?,{?}})；
(3) P({1,{2,3}})。
解,(1) P (?) = {?}
(2) P ({?,{?}}) = {?,{?},{{?}},{?,{?}}}
(3) P ({1,{2,3}}) = {?,{1},{{2,3}},{1,{2,3}}}
2009-7-29 离散数学 8
1、并,A∪ B = { x | x?A? x?B }
一、几种常见的运算
§ 3.2 集合的基本运算
2、交,A∩B = { x | x?A? x?B }，
若 A∩B =?,则称 A与 B不交。
3、相对补,A? B = { x | x?A? x?B }（ B对 A的）
4、绝对补,A对全集 E的相对补集，记作,~ A
~ A = E? A = { x | x?E? x?A }
5、对称差,A? B = (A?B)∪ (B?A) = (A∪ B)? (A∩B)
2009-7-29 离散数学 9
二、文氏图
E
A∪ B如：
E
E E E
A∩B
A? B ~ A A? B
2009-7-29 离散数学 10
三、集合算律
(1) 幂等律,A∪ A = A
A∩A = A
(2) 结合律：
(3) 交换 律：
(4) 分配律：
(A∪ B)∪ C = A∪ (B∪ C)
(A∩B)∩C = A∩(B∩C)
A∪ B = B∪ A
A∩B = B∩A
A∪ (B∩C) = (A∪ B)∩(A∪ C)
A∩(B∪ C) = (A∩B)∪ (A∩C)
2009-7-29 离散数学 11
三、集合算律（续）
(5) 同一律,A∪? = A
A∩E = A
(6) 零 律：
(7) 排中 律：
(8) 矛盾律：
A∪ E = E
A∩? =?
A∪ ~ A = E
A∩~ A =?
A∪ (A∩B) = A
A∩(A∪ B) = A
(9) 吸收律：
2009-7-29 离散数学 12
三、集合算律（续）
(10) 德 · 摩根律,A? (B∪ C) = (A? B)∩(A? C)
A? (B∩C) = (A? B)∪ (A? C)
~ (B∪ C) = ~ B∩~ C
~ (B∩C) = ~ B∪ ~ C
~? = E
~ E =?
~ (~ A) = A(11) 双重否定律：
2009-7-29 离散数学 13
四、常用运算性质
(1) A∩B? A A∩B? B
(2) A? A∪ B B? A∪ B
(3) A? B? A
(4) A? B = A∩~ B
(5) A∪ B = B? A? B? A∩B = A? A? B =?
(6) A? B = B? A
(7) (A? B)? C = A? (B? C)
2009-7-29 离散数学 14
四、常用运算性质（续）
(8) A = A
(9) A? A =?
(10) A? B = A? C? B = C
例 3：化简 ((A∪ B∪ C)∩(A∪ B))? ((A∪ (B? C))∩A)
解,∵ A∪ B? A∪ B∪ C 和 A? A∪ (B? C)
∴ (A∪ B∪ C)∩(A∪ B) = A∪ B
原式 = (A∪ B)? A = (A∪ B)∩~ A = B? A
∴ (A∪ (B? C))∩A = A
2009-7-29 离散数学 15
§ 3.3 集合中元素的计数基数,集合中元素的个数，用 |A|表示。
容斥原理,对任意两个有限集 A和 B，有
|A∪ B| = |A| + |B|? |A∩B|
一、理论推广 1,| A∪ B∪ C | = |A| + |B| + |C|? |A∩B|? |A∩C|
|B∩C| + |A∩B∩C|
2009-7-29 离散数学 16
一、理论（续）
推广 2：
kji
n
i
i
n
kji
ji
ji
n
i
i
n
i
i
AAAA
AAAA
1
1
11
)1(.,,
推论：
nn AAAEAAA 2121
2009-7-29 离散数学 17
例 4：某班有 25个学生，其中 14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球，
2人会打这三种球，而 6个会打网球的人都会打另外一种球 (指篮球和排球 )，求不会打这三种球的人数？
二、应用解：分别用 A,B,C表示会打篮球、排球、网球的学生集合。 依题意有,|A| = 14,|B| = 12,|C| = 6，
|A∩B| = 6,|A∩C| = 5,|A∩B∩C| = 2，
且有 C? A∪ B，求 | ∩ ∩ | A B C
2009-7-29 离散数学 18
二、应用（续）
于是 C = C∩(A∪ B) = (C∩A)∪ (C∩B)
| ∩ ∩ | = |E|? |A∪ B∪ C| =25? 20 = 5A B C
从而 |A∪ B∪ C| = |A| + |B| + |C|? |A∩B|? |A∩C|
|B∩C| + |A∩B∩C|
= 14 + 12 + 6? 6? 5? 3 + 2 = 20
得 |B∩C| = 3
6 = 5+ |B∩C|? 2
|C| = |A∩C| + |B∩C|? |A∩B∩C|
2009-7-29 离散数学 19
例 5：一个班有 50个学生，第一次考试有 26人得 5分，
第二次考试有 21人得 5分。如果两次考试都没得 5分的有 17人，那么在两次考试都得 5分的有多少人？
二、应用（续）
解：分别用 A,B表示第一次考试得 5分和第二次考试得 5分的学生集合。
依题意有,|A| = 26,|B| = 21,| ∩ | = 17A B
= |A| + |B|?(|E|? | ∩ |) A B
= 26 + 21? 50 + 17 = 14
则 |A∩B| = |A| + |B|? |A∪ B|
第三章 集合的基本概念和运算
§ 3.1 集合的基本概念
§ 3.2 集合的基本运算
§ 3.3 集合中元素的计数
2009-7-29 离散数学 2
一、集合集 合,一些可确定的可分辨的事物构成的整体。
用大写字母 A,B,C,… 标记。
§ 3.1 集合的基本概念集合的元素,一个集合的每一个特定的事物。用小写字母 a,b,c,… 标记。
如,(1) 26个英文字母的集合；
(2) 坐标平面上所有点的集合。
规定：集合的元素之间彼此相异，无次序关系。
2009-7-29 离散数学 3
二、常用的集合常用的集合记号：
N,自然数集合 (包括 0 )
Z,整数集合
Q,有理数集合
R,实数集合
C,复数集合
,空集 (不含任何元素 )
E,全集
2009-7-29 离散数学 4
三、集合的表示方法列出集合的所有元素，元素之间用逗号隔开。如 A = { a,b,c }
用谓词概括该集合中元素的属性。
即,A = { x | P (x) }
如,A = { x | x?Z? 3 < x? 6 }
1,列举法：
2,描述法：
元素与集合之间的关系 (?属于 ):
若 A={ a,{a},b,{a,b}},则 a?A,{a}?A
2009-7-29 离散数学 5
3,真子集,如果 B? A且 A? B,则 B是 A的真子集。
记作 B? A。
四、集合之间的关系
1,子 集,集合 B中的每个元素都是集合 A中的元素，
则 B是 A的子集，记作 B? A。符号化为
B? A x(x?B? x?A)
2,相等集,如果 A? B且 B? A,则 A与 B相等 。记作
A = B。符号化为 A = B? A? B? B? A
显然,A? A, A
2009-7-29 离散数学 6
解,0元子集,?，
四、集合之间的关系（续）
4,幂 集,集合 A的全体子集构成的集合，记作 P (A)。
符号化为 P (A) = { x | x? A}
例 1,A = {a,b,c}，求 A的幂集 P (A)。
n 元集 A的幂集 P (A)含有 2n个元素。
1元子集,{a},{b},{c}，
2元子集,{a,b},{a,c},{b,c}，
P(A) = {?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
3元子集,{a,b,c}
2009-7-29 离散数学 7
四、集合之间的关系（续）
例 2：计算以下幂集。
(1) P(?)；
(2) P({?,{?}})；
(3) P({1,{2,3}})。
解,(1) P (?) = {?}
(2) P ({?,{?}}) = {?,{?},{{?}},{?,{?}}}
(3) P ({1,{2,3}}) = {?,{1},{{2,3}},{1,{2,3}}}
2009-7-29 离散数学 8
1、并,A∪ B = { x | x?A? x?B }
一、几种常见的运算
§ 3.2 集合的基本运算
2、交,A∩B = { x | x?A? x?B }，
若 A∩B =?,则称 A与 B不交。
3、相对补,A? B = { x | x?A? x?B }（ B对 A的）
4、绝对补,A对全集 E的相对补集，记作,~ A
~ A = E? A = { x | x?E? x?A }
5、对称差,A? B = (A?B)∪ (B?A) = (A∪ B)? (A∩B)
2009-7-29 离散数学 9
二、文氏图
E
A∪ B如：
E
E E E
A∩B
A? B ~ A A? B
2009-7-29 离散数学 10
三、集合算律
(1) 幂等律,A∪ A = A
A∩A = A
(2) 结合律：
(3) 交换 律：
(4) 分配律：
(A∪ B)∪ C = A∪ (B∪ C)
(A∩B)∩C = A∩(B∩C)
A∪ B = B∪ A
A∩B = B∩A
A∪ (B∩C) = (A∪ B)∩(A∪ C)
A∩(B∪ C) = (A∩B)∪ (A∩C)
2009-7-29 离散数学 11
三、集合算律（续）
(5) 同一律,A∪? = A
A∩E = A
(6) 零 律：
(7) 排中 律：
(8) 矛盾律：
A∪ E = E
A∩? =?
A∪ ~ A = E
A∩~ A =?
A∪ (A∩B) = A
A∩(A∪ B) = A
(9) 吸收律：
2009-7-29 离散数学 12
三、集合算律（续）
(10) 德 · 摩根律,A? (B∪ C) = (A? B)∩(A? C)
A? (B∩C) = (A? B)∪ (A? C)
~ (B∪ C) = ~ B∩~ C
~ (B∩C) = ~ B∪ ~ C
~? = E
~ E =?
~ (~ A) = A(11) 双重否定律：
2009-7-29 离散数学 13
四、常用运算性质
(1) A∩B? A A∩B? B
(2) A? A∪ B B? A∪ B
(3) A? B? A
(4) A? B = A∩~ B
(5) A∪ B = B? A? B? A∩B = A? A? B =?
(6) A? B = B? A
(7) (A? B)? C = A? (B? C)
2009-7-29 离散数学 14
四、常用运算性质（续）
(8) A = A
(9) A? A =?
(10) A? B = A? C? B = C
例 3：化简 ((A∪ B∪ C)∩(A∪ B))? ((A∪ (B? C))∩A)
解,∵ A∪ B? A∪ B∪ C 和 A? A∪ (B? C)
∴ (A∪ B∪ C)∩(A∪ B) = A∪ B
原式 = (A∪ B)? A = (A∪ B)∩~ A = B? A
∴ (A∪ (B? C))∩A = A
2009-7-29 离散数学 15
§ 3.3 集合中元素的计数基数,集合中元素的个数，用 |A|表示。
容斥原理,对任意两个有限集 A和 B，有
|A∪ B| = |A| + |B|? |A∩B|
一、理论推广 1,| A∪ B∪ C | = |A| + |B| + |C|? |A∩B|? |A∩C|
|B∩C| + |A∩B∩C|
2009-7-29 离散数学 16
一、理论（续）
推广 2：
kji
n
i
i
n
kji
ji
ji
n
i
i
n
i
i
AAAA
AAAA
1
1
11
)1(.,,
推论：
nn AAAEAAA 2121
2009-7-29 离散数学 17
例 4：某班有 25个学生，其中 14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球，
2人会打这三种球，而 6个会打网球的人都会打另外一种球 (指篮球和排球 )，求不会打这三种球的人数？
二、应用解：分别用 A,B,C表示会打篮球、排球、网球的学生集合。 依题意有,|A| = 14,|B| = 12,|C| = 6，
|A∩B| = 6,|A∩C| = 5,|A∩B∩C| = 2，
且有 C? A∪ B，求 | ∩ ∩ | A B C
2009-7-29 离散数学 18
二、应用（续）
于是 C = C∩(A∪ B) = (C∩A)∪ (C∩B)
| ∩ ∩ | = |E|? |A∪ B∪ C| =25? 20 = 5A B C
从而 |A∪ B∪ C| = |A| + |B| + |C|? |A∩B|? |A∩C|
|B∩C| + |A∩B∩C|
= 14 + 12 + 6? 6? 5? 3 + 2 = 20
得 |B∩C| = 3
6 = 5+ |B∩C|? 2
|C| = |A∩C| + |B∩C|? |A∩B∩C|
2009-7-29 离散数学 19
例 5：一个班有 50个学生，第一次考试有 26人得 5分，
第二次考试有 21人得 5分。如果两次考试都没得 5分的有 17人，那么在两次考试都得 5分的有多少人？
二、应用（续）
解：分别用 A,B表示第一次考试得 5分和第二次考试得 5分的学生集合。
依题意有,|A| = 26,|B| = 21,| ∩ | = 17A B
= |A| + |B|?(|E|? | ∩ |) A B
= 26 + 21? 50 + 17 = 14
则 |A∩B| = |A| + |B|? |A∪ B|
