2005-7-5《集合论与图论》第3讲1
第3讲集合的概念与运算
? 1. 集合的概念
? 2. 集合之间的关系
? 3. 集合的运算
? 4. 文氏图、容斥原理
2005-7-5《集合论与图论》第3讲2
集合论(set theory)
?十九世纪数学最伟大成就之一
?集合论体系
?朴素(naive)集合论
?公理(axiomatic)集合论
?创始人康托(Cantor)
Georg Ferdinand Philip Cantor
1845 ~ 1918
德国数学家, 集合论创始人.
2005-7-5《集合论与图论》第3讲3
什么是集合(set)
?集合：不能精确定义。一些对象的整体
就构成集合，这些对象称为元素
(element)或成员(member)
?用大写英文字母A,B,C,…表示集合
?用小写英文字母a,b,c,…表示元素
?a∈A：表示a是A的元素，读作“a属于A”
a?A：表示a不是A的元素，读作“a不属
于A”
2005-7-5《集合论与图论》第3讲4
集合的表示
?列举法
?描述法
?特征函数法
2005-7-5《集合论与图论》第3讲5
列举法(roster)
?列出集合中的全体元素，元素之间用逗号分开，
然后用花括号括起来，例如
A={a,b,c,d,…,x,y,z}
B={0,1,2,3,4,5,6,7,8,9}
?集合中的元素不规定顺序
C={2,1}={1,2}
?集合中的元素各不相同(多重集除外)
C={2,1,1,2}={2,1}
2005-7-5《集合论与图论》第3讲6
多重集(multiple set)
?多重集: 允许元素多次重复出现的集合
?元素的重复度: 元素的出现次数(≥0).
?例如: 设A={a,a,b,b,c}是多重集
元素a,b的重复度是2
元素c的重复度是1
元素d的重复度是0
2005-7-5《集合论与图论》第3讲7
描述法(defining predicate)
?用谓词P(x)表示x具有性质P，用{x|P(x)}表示
具有性质P的集合，例如
? P
1
(x): x是英文字母
A={x|P
1
(x)}={x| x是英文字母}
={a,b,c,d,…,x,y,z}
? P
2
(x): x是十进制数字
B={x|P
2
(x)}= {x|x是十进制数字}
={0,1,2,3,4,5,6,7,8,9}
2005-7-5《集合论与图论》第3讲8
描述法（续）
?两种表示法可以互相转化，例如
E={2,4,6,8,…}
={x|x>0且x是偶数}
={x|x=2(k+1)，k为非负整数}
={2(k+1) | k为非负整数}
?有些书在描述法中用:代替|, 例如
{2(k+1): k为非负整数}
2005-7-5《集合论与图论》第3讲9
特征函数法(characteristic function)
?集合A的特征函数是χ
A
(x):
1，若x∈A
χ
A
(x) =
0，若x?A
?对多重集, χ
A
(x)=x在A中的重复度
2005-7-5《集合论与图论》第3讲10
常用的数集合
?N：自然数(natural numbers)集合
N={0,1,2,3,…}
?Z：整数(integers)集合
Z={0,±1,±2,…}={…,-2,-1,0,1,2,…}
?Q：有理数(rational numbers)集合
?R：实数(real numbers)集合
?C：复数(complex numbers)集合
2005-7-5《集合论与图论》第3讲11
集合之间的关系
?子集、相等、真子集
?空集、全集
?幂集、n元集、有限集
?集族
2005-7-5《集合论与图论》第3讲12
子集(subset)
?B包含于A, A包含B:
B?A ??x(x∈B→x∈A)
?B不是A的子集:
B?A ??x(x∈B∧x?A)
???x(x∈B→x∈A)??x?(?x∈B∨x∈A)
??x(x∈B∧?x∈A)??x(x∈B∧x?A)
2005-7-5《集合论与图论》第3讲13
相等(equal)
?相等: A=B ? A?B ∧ B?A
??x(x∈A?x∈B)
? A=B ? A?B∧B?A (=定义)
??x(x∈A→x∈B)∧?x(x∈B→x∈A) (?定义)
??x((x∈A→x∈B)∧(x∈B→x∈A))(量词分配)
??x(x∈A?x∈B) (?等值式)
2005-7-5《集合论与图论》第3讲14
包含(?)的性质
? A?A
证明: A?A??x(x∈A→x∈A) ?1
?若A?B,且A≠B,则B?A
证明: A≠B ??(A=B)
??(A?B∧B?A) (定义)
??(A?B) ∨?(B?A) (德?摩根律)
A?B (已知)
∴?B?A (即B?A) (析取三段论) #
2005-7-5《集合论与图论》第3讲15
包含(?)的性质(续)
?若A?B,且B?C, 则A?C
证明: A?B ??x(x∈A→x∈B)
?x, x∈A
? x∈B (A?B)
? x∈C (B?C)
∴?x(x∈A→x∈C), 即A?C. #
2005-7-5《集合论与图论》第3讲16
真子集(proper subset)
?真子集: B真包含A:
A?B ? A?B ∧ A≠B
?A?B ??(A?B ∧ A≠B) (?定义)
??(A?B) ∨ (A=B) (德?摩根律)
??x(x∈A∧x?B) ∨ (A=B) (?定义)
2005-7-5《集合论与图论》第3讲17
真包含(?)的性质
? A?A
证明: A ? A? A?A ∧ A≠A ? 1∧0 ? 0. #
?若A?B,则B?A
证明: (反证) 设B?A, 则
A?B ? A?B ∧ A≠B ? A?B (化简)
B?A ? B?A ∧ B≠A ? B?A
所以A?B ∧ B?A ? A=B (=定义)
但是A?B ? A?B ∧ A≠B ? A≠B (化简) 矛盾!
#
2005-7-5《集合论与图论》第3讲18
真包含(?)的性质(续)
?若A?B,且B?C, 则A?C
证明: A?B ? A?B ∧ A≠B ? A?B (化简),
同理B?C ? B?C, 所以A?C.
假设A=C, 则B?C?B?A,又A?B, 故
A=B, 此与A?B矛盾, 所以A≠C.
所以, A?C. #
2005-7-5《集合论与图论》第3讲19
空集(empty set)
?空集:没有任何元素的集合是空集,记作?
?例如, {x∈R|x
2
+1=0}
?定理1: 对任意集合A, ??A
证明: ??A??x(x∈?→x∈A)
??x(0→x∈A)?1. #
?推论: 空集是唯一的.
证明: 设?
1
与?
2
都是空集, 则
?
1
??
2
∧?
2
??
1
??
1
=?
2 .
#
2005-7-5《集合论与图论》第3讲20
全集
?全集: 如果限定所讨论的集合都是某个集
合的子集,则称这个集合是全集,记作E
?全集是相对的, 视情况而定, 因此不唯一.
例如, 讨论(a,b)区间里的实数性质时, 可
以选E=(a,b), E=[a,b), E=(a,b], E=[a,b],
E=(a,+∞),E=(-∞,+∞)等
2005-7-5《集合论与图论》第3讲21
幂集(power set)
?幂集: A的全体子集组成的集合,称为A的
幂集,记作P(A)
P(A)={x|x?A}
?注意: x∈P(A) ? x?A
?例子: A={a,b}, P(A)={?,{a},{b},{a,b}}. #
2005-7-5《集合论与图论》第3讲22
n元集(n-set)
? n元集: 含有n个元素的集合称为n元集
?0元集: ?
?1元集(或单元集),如{a}, {b}, {?}, {{?}},…
?|A|: 表示集合A中的元素个数,
A是n元集? |A|=n
?有限集(fimite set): |A|是有限数, |A|<∞,
也叫有穷集
2005-7-5《集合论与图论》第3讲23
幂集(续)
?定理: |A|=n ? |P(A)|=2
n
.
证明: 每个子集对应一种染色,一共有2
n
种不同染色. #
A
{a
1
}
?
a
1
a
2
a
3
………
a
n
{a
1
,a
3
}
……
2005-7-5《集合论与图论》第3讲24
集族(set family)
?集族: 由集合构成的集合. 幂集都是集族.
?指标集(index set): 设A是集族, 若
A={A
α
|α∈S}, 则S称为A的指标集. S中的
元素与A中的集合是一一对应的. 也记作
A={A
α
|α∈S}={A
α
}
α∈S
?例1: {A
1
,A
2
}的指标集是{1,2}
2005-7-5《集合论与图论》第3讲25
集族(举例)
?例2: A
n
={x∈N|x=n}, A
0
={0}, A
1
={1},…
{A
n
|n∈N}={{0},{1},{2},…}
{A
n
|n∈N}的指标集是N
?例3: 设R
+
={x∈R|x>0}, A
a
=[0,a),
{A
a
|a∈R
+
}的指标集是R
+
0
a
2005-7-5《集合论与图论》第3讲26
集合之间的运算
?并集、交集
?相对补集、对称差、绝对补
?广义并集、广义交集
2005-7-5《集合论与图论》第3讲27
并集(union)
?并集: A∪B = { x | (x∈A) ∨ (x∈B) }
x∈A∪B ?(x∈A) ∨ (x∈B)
?初级并:
)}1(|{
21 in
AxniixAAA ∈∧≤≤?=ULUU
ni
n
i
AAAA ULUUU
21
1
=
=
LUUU
21
1
AAA
i
i
=
∞
=
2005-7-5《集合论与图论》第3讲28
并集(举例)
?例1: 设A
n
={x∈R|n-1≤x≤n},n=1,2,…,10,
则
?例2: 设A
n
={x∈R|0≤x≤1/n},n=1,2,…,则
]10,0[}100|{
10
1
=≤≤∈=
=
xRxA
i
i
U
]1,0[}10|{
1
=≤≤∈=
∞
=
xRxA
i
i
U
2005-7-5《集合论与图论》第3讲29
交集(intersection)
?交集: A∩B = { x | (x∈A) ∧ (x∈B) }
x∈A∩B ?(x∈A) ∧ (x∈B)
?初级交:
)}1(|{
21 in
AxniixAAA ∈→≤≤?=ILII
ni
n
i
AAAA ILIII
21
1
=
=
LIII
21
1
AAA
i
i
=
∞
=
2005-7-5《集合论与图论》第3讲30
交集(举例)
?例1: 设A
n
={x∈R|n-1≤x≤n},n=1,2,…,10,
则
?例2: 设A
n
={x∈R|0≤x≤1/n},n=1,2,…,则
?=
=
i
i
A
10
1
I
}0{
1
=
∞
=
i
i
AI
2005-7-5《集合论与图论》第3讲31
不相交(disjoint)
?不相交: A∩B=?
?互不相交: 设A
1
,A
2
,…是可数多个集合,
若对于任意的i≠j, 都有A
i
∩A
j
=?, 则说它
们互不相交
?例: 设A
n
={x∈R|n-1<x<n}, n=1,2,…,10,
则A
1
,A
2
,…是不相交的
2005-7-5《集合论与图论》第3讲32
相对补集(set difference)
?相对补集: 属于A而不属于B的全体元素,
称为B对A的相对补集, 记作A-B
A-B = { x | (x∈A) ∧ (x?B) }
A-B
A
B
2005-7-5《集合论与图论》第3讲33
对称差(symmetric difference)
?对称差: 属于A而不属于B, 或属于B而不
属于A的全体元素, 称为A与B的对称差,
记作A⊕B
A⊕B={x|(x∈A∧x?B)∨(x?A∧x∈B)}
?A⊕B=(A-B)∪(B-A)=(A∪B)-(A∩B)
A⊕B
AB
2005-7-5《集合论与图论》第3讲34
绝对补(complement)
?绝对补: ~A=E-A, E是全集, A?E
~A={x|(x∈E∧x?A)}
~A={x∈E|x?A)}
~A
A
2005-7-5《集合论与图论》第3讲35
相对补、对称差、补(举例)
?例: 设A={x∈R|0≤x<2}, B={x∈R|1≤x<3},
则
A-B= {x∈R|0≤x<1}=[0,1)
B-A= {x∈R|2≤x<3}=[2,3)
A⊕B={x∈R|(0≤x<1)∨(2≤x<3)}=[0,1)∪[2,3)
[)
[)
)
[
2005-7-5《集合论与图论》第3讲36
广义并集(big union)
?广义并: 设A是集族, A中所有集合的元素
的全体, 称为A的广义并, 记作∪A.
∪A = { x | ?z(x∈z∧z∈A }
?当A是以S为指标集的集族时
∪A = ∪{A
α
|α∈S}= ∪A
α
α∈S
?例: 设A={{a,b},{c,d},{d,e,f}}, 则
∪A= {a,b,c,d,e,f}
2005-7-5《集合论与图论》第3讲37
广义交集(big intersection)
?广义交: 设A是集族, A中所有集合的公共
元素的全体, 称为A的广义交, 记作∩A.
∩A = { x | ?z(z∈A→x∈z) }
?当A是以S为指标集的集族时
∩A = ∩{A
α
|α∈S}= ∩A
α
α∈S
?例: 设A={{1,2,3},{1,a,b},{1,6,7}}, 则
∩A= {1}
2005-7-5《集合论与图论》第3讲38
广义交、广义并(举例)
?设A
1
={a,b,{c,d}}, A
2
={{a,b}}, A
3
={a},
A
4
={?,{?}}, A
5
=a(a≠?), A
6
=?, 则
∪A
1
= a∪b∪{c,d}, ∩A
1
= a∩b∩{c,d},
∪A
2
={a,b}, ∩A
2
={a,b},
∪A
3
=a, ∩A
3
=a
∪A
4
=?∪{?}={?}, ∩A
4
=?∩{?}=?,
∪A
5
= ∪a, ∩A
5
= ∩a
∪A
6
=?, ∩A
6
=E
2005-7-5《集合论与图论》第3讲39
文氏图(Venn diagram)
?文氏图: 平面上的n个圆(或椭圆),使得任
何可能的相交部分, 都是非空的和连通的
?John Venn, 1834~1923
?例:
2005-7-5《集合论与图论》第3讲40
文氏图(应用)
?文氏图可表示集合运算(结果用阴影表示)
A∩BA∪B A-B
A⊕B ~A
A
A
AA
A
A
BBB
B B
A∩B=?
2005-7-5《集合论与图论》第3讲41
容斥原理(principle of inclusion/exclusion)
?容斥原理(或包含排斥原理)
∑∑
<=
=
?=
ji
ji
n
i
ii
n
i
AAAA ||||||
1
1
IU
∑
<<
?
?+?+
kji
n
n
kji
AAAAAA ||)1(||
21
1
ILIILII
2005-7-5《集合论与图论》第3讲42
容斥原理(证明)
? n=2时的情况:
|A∪B|=|A|+|B|-|A∩B|
?归纳证明: 以n=3为例:
|A∪B ∪C| = |(A∪B)∪C|= |A∪B|+|C|-|(A∪B)∩C|
= |A|+|B|-|A∩B|+|C|-|(A∩C)∪(B∩C)|
= |A|+|B|-|A∩B|+|C|
-(|A∩C|+|B∩C|-|(A∩C)∩(B∩C)|)
= |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|
+|A∩B∩C|
AB
BC
A
2005-7-5《集合论与图论》第3讲43
容斥原理(举例)
?例1: 在1到10000之间既不是某个整数的平方,
也不是某个整数的立方的数有多少?
?解: 设E={x∈N|1≤x≤10000}, |E|=10000
A={x∈E|x=k
2
∧k∈Z}, |A|=100
B={x∈E|x=k
3
∧k∈Z}, |B|=21
则|~(A∪B)|=|E|-|A∪B|
=|E|-(|A|+|B|-|A∩B|)
=10000-100-21+4=9883
注意A∩B= {x∈E|x=k
6
∧k∈Z}, |A∩B|=4. #
2005-7-5《集合论与图论》第3讲44
容斥原理(举例、续)
?例2: 在24名科技人员中,会说英,日,德,法语的人
数分别为13, 5, 10, 和9, 其中同时会说英语,德
语, 或同时会说英语,法语, 或同时会说德语,法
语两种语言的人数均为4.会说日语的人既不会
说法语也不会说德语. 试求只会说一种语言的
人数各为多少?又同时会说英,德,法语的人数有
多少?
?解: 设E={x|x是24名科技人员之一}, |E|=24
A={x∈E|x会说英语}, B={x∈E|x会说日语},
C={x∈E|x会说德语} D={x∈E|x会说法语},
2005-7-5《集合论与图论》第3讲45
容斥原理(举例、续)
?解(续): 设所求人数分别为x
1
,x
2
,x
3
,x
4
,x(如图),
A={x∈E|x会说英语}, |A|=13
B={x∈E|x会说日语}, |B|=5
C={x∈E|x会说德语}, |C|=10
D={x∈E|x会说法语}, |D|=9
首先, x
2
=|B|-|A∩B|=5-2=3,
其次,对A,C,D用容斥原理, 注意|E|=24:
24-3=21=13+10+9-4-4-4+x=20+x, 得x=1,
最后, x
1
=|A|-|A∩B|-3-3-1=13-2-7=4, 同理
x
3
=10-3-3-1=3, x
4
=9-3-3-1=2. #
D
C
B
A
X
X
1
X
2
X
3
X
4
4-X
4-X
4-X
2
2005-7-5《集合论与图论》第3讲46
总结
?集合概念: ∈, ?, E, ?, ?,
?集合运算: ∩, ∪, -, ⊕, ~, P( )
?文氏图
?容斥原理
2005-7-5《集合论与图论》第3讲47
习题(#1)
? p25, 习题一, 3, 7, 10, 16
