第 6章 集合代数离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 集合的基本概念 — 集 合、相等,(真 )包含、子集、空集、
全集、幂集
– 集合运算 — 交、并,(相对和绝对 )补、对称差、广义交、
广义并
– 文氏图 — 有穷集计数问题
– 集合恒等式
本章与后续各章的关系
– 是集合论后面各章的基础
– 是典型的布尔代数系统
6.1 集合的基本概念
集合 (Set)是不能精确定义的基本概念。
– 所谓集合，是指我们无意中或思想中将一些确定的、彼此完全不同的客体的总和而考虑为一个整体。这些客体叫做该集合的元素。 (康托 )
– 直观地说，把一些事物汇集到一起组成一个整体就叫 集合,而这些事物就是这个集合的 元素 或 成员 。
例如：
– 方程 x2－ 1＝ 0的实数解集合：
– 26个英文字母的集合；
– 坐标平面上所有点的集合；
– … …
集合通常用大写的英文字母来标记。
常见的数的集合
N— 自然数集合
Z— 整数集合
Q— 有理数集合
R— 实数集合
C— 复数集合集合的表示方法
表示一个集合的方法主要有两种,列元素法 和 谓词表示法 。
列元素法 (roster)是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。
– A＝ {a,b,c,…,z}
– Z＝ {0,± 1,± 2,… }
– C＝ {桌子,灯泡,老虎,自然数 }
谓词表示法 (defining predicate)是用谓词来概括集合中元素的属性。
– B＝ {x|x∈R∧x 2－ 1＝ 0}
许多集合可以用两种方法来表示，如 B也可以写成 {-1,1}。
但是有些集合不可以用列元素法表示，如实数集合。
集合的元素
集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。
例如,{1,1,2,2,3}＝ {1,2,3}
集合的元素是无序的。
例如,{1,2,3}＝ {3,1,2}
在本书所采用的体系中规定,集合的元素都是集合 。
元素和集合之间的关系
元素和集合之间的关系是隶属关系，即 属于 或 不属于,属于记作 ∈,不属于记作?。
例如,A＝ {a,{b,c},d,{{d}}}
a∈ A,{b,c}∈ A,d∈ A,{{d}}∈ A，
b?A,{d}?A。
b和 {d}是 A的元素的元素。
可以用一种树形图表示集合与元素的隶属关系。
说明
隶属关系可以看作是处在不同层次上的集合之间的关系。
规定：对任何集合 A都有 A?A。
A
a {b,c} d {{d}}
b c {d}
d
子集（ subset）
定义 6.1 设 A,B为集合，如果 B中的每个元素都是 A中的元素，
则称 B是 A的子集合，简称 子集 。这时也称 B被 A包含,或 A包含 B，记作 B?A。
包含的符号化表示为
B?Ax(x∈B→x∈A)
如果 B不被 A包含，则记作 B A。
例如,N? Z? Q? R? C，但 Z N。
显然对任何集合 A都有 A?A。
隶属和包含的说明
隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。
例如 A＝ {a,{a}}和 {a}
既有 {a}∈A,又有 {a}?A。
前者把它们看成是不同层次上的两个集合，
后者把它们看成是同一层次上的两个集合。
集合相等 (equal)
定义 6.2 设 A,B为集合，如果 A?B 且 B?A，则称 A与
B相等,记作 A＝ B。
相等的符号化表示为：
A＝ B? A?B ∧ B?A
如果 A与 B不相等，则记作 A≠B 。
真子集定义 6.3 设 A,B为集合，如果 B?A 且 B≠A,则称 B是
A的 真子集,记作 B?A。
真子集的符号化表示为
B?A? B?A ∧ B≠A
如果 B不是 A的真子集，则记作 B? A。
例如,N? N
空集 (empty set)
定义 6.4 不含任何元素的集合叫做 空集,记作?。
空集的符号化表示为,?＝ {x|x≠x} 。
例如,{x|x∈R∧x 2+1=0}
是方程 x2+1=0的实数解集，因为该方程无实数解，所以是空集。
空集的性质推论 空集是唯一的。
证明,假设存在空集?1和?2，由定理 6.1有
12,?21。
根据集合相等的定义，有?1＝?2。
定理 6.1 空集是一切集合的子集。
证明,任给集合 A，由子集定义有
Ax(x∈? → x∈A)
右边的蕴涵式因前件假而为真命题，
所以 A也为真。
n元集
含有 n个元素的集合简称 n元集,它的含有 m(m≤n) 个元素的子集叫做它的 m元子集 。
例 6.1 A＝ {1,2,3}，将 A的子集分类：
0元子集（空集）?
1元子集（单元集） {1},{2},{3}
2元子集 {1,2},{1,3},{2,3}
3元子集 {1,2,3}
幂集 ( power set )
一般地说，对于 n元集 A，它的 0元子集有 个,1元子集有个,…,m元子集有 个,…,n元子集有 个。子集总数为
nnn2n1n0n 2CCCC
0nC 1nC
mnC nnC
定义 6.5 设 A为集合，把 A的全部子集构成的集合叫做 A的 幂集,
记作 P(A)(或 PA,2A)。
P(A)＝ {x | x?A}
若 A是 n元集，则 P(A)有 2n 个元素。
全集定义 6.6 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为 全集,记作 E。
说明
全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。
例如，在研究平面上直线的相互关系时，可以把整个平面 (平面上所有点的集合 )取作全集，也可以把整个空间 (空间上所有点的集合 )取作全集。
一般地说，全集取得小一些，问题的描述和处理会简单些。
6.2 集合的运算定义 6.7 设 A,B为集合,A与 B的 并集 A∪B,交集 A∩B,B对 A
的 相对补集 A－ B分别定义如下：
A∪B ＝ {x|x∈A∨x∈B } (union set)
A∩B ＝ {x|x∈A∧x∈B } (intersection set)
A－ B＝ {x|x∈A∧x?B } (difference set)
举例 设 A＝ {a,b,c},B＝ {a},C＝ {b,d} 则有
A∪B ＝ {a,b,c},A∩B ＝ {a}，
A－ B＝ {b,c}，
B－ A＝?,B∩C ＝?
说明
如果两个集合的交集为?,则称这两个集合是不相交的。例如 B和 C是不相交的。
n个集合的并和交
两个集合的并和交运算可以推广成 n个集合的并和交：
A1∪A 2∪ … ∪A n＝ {x|x∈A 1∨x∈A 2∨ … ∨x∈A n}
A1∩A 2∩ … ∩A n＝ {x|x∈A 1∧x∈A 2∧ … ∧x∈A n}
上述的并和交可以简记为：
n
1i
iA
＝ A1∩A 2∩ … ∩A n
n
1i
iA
＝ A1∪A 2∪ … ∪A n
两个集合的并和交运算可以推广到无穷多个集合的情况：
1i
iA
＝ A1∩A 2∩ …
1i
iA
＝ A1∪A 2∪ …
对称差集定义 6.8 设 A,B为集合,A与 B的 对称差集 A?B定义为：
A?B＝ (A－ B)∪(B － A)
对称差运算的另一种定义是
A?B＝ (A∪B) － (A∩B)
例如,A＝ {a,b,c},B＝ {b,d}，
则 A?B＝ {a,c,d}
绝对补集定义 6.9 ～ A＝ E－ A＝ {x|x∈E∧x?A}
因为 E是全集,x∈E 是真命题，所以～ A可以定义为：
A＝ {x|x? A }
例如,E＝ {a,b,c,d},A＝ {a,b,c}
～ A＝ {d}
文氏图 (Venn Diagram)
集合之间的关系和运算可以用 文氏图 给予形象的描述。
文氏图的构造方法如下：
– 画一个大矩形表示全集 E(有时为简单起见可将全集省略 )。
– 在矩形内画一些圆 (或任何其它的适当的闭曲线 )，用圆的内部表示集合。
– 不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。
– 图中阴影的区域表示新组成的集合。
– 可以用实心点代表集合中的元素。
文氏图的实例有穷集的计数问题
使用文氏图可以很方便地解决 有穷集的计数问题 。
首先根据已知条件把对应的文氏图画出来。
– 一般地说，每一条性质决定一个集合。
– 有多少条性质，就有多少个集合。
– 如果没有特殊说明，任何两个集合都画成相交的
然后将已知集合的元素数填入表示该集合的区域内。
– 通常从 n个集合的交集填起，
– 根据计算的结果将数字逐步填入所有的空白区域。
– 如果交集的数字是未知的，可以设为 x。
根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。
例 6.2
例 6.2 对 24名会外语的科技人员进行掌握外语情况的调查。
其统计结果如下：会英、日、德和法语的人分别为 13,5
,10和 9人，其中同时会英语和日语的有 2人，会英、德和法语中任两种语言的都是 4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言 (英、德、法、日 )的人数和会三种语言的人数。
解,令 A,B,C,D分别表示会英、法、德、日语的人的集合
。根据题意画出文氏图。设同时会三种语言的有 x人，只会英、法或德语一种语言的分别为 y1,y2和 y3人。将 x和 y1
,y2,y3填入图中相应的区域，然后依次填入其它区域的人数。
例 6.2
4-x
4-x
4-x
x
y2 y1
y3
2 5-2
英 13法 9
德 10
日 5
y1+2(4-x)+x+2＝ 13
y2+2(4-x)+x＝ 9
y3+2(4-x)+x＝ 10
y1+y2+y3+3(4-x)+x＝ 24-5
包含排斥原理定理 6.2 设 S为有穷集,P1,P2,…,Pm是 m个性质。 S中的任何元素 x或者具有性质 Pi，或者不具有性质 Pi(i=1,2,… m),
两种情况必居其一。令 Ai表示 S中具有性质 Pk的元素构成的子集，则 S中不具有性质 P1,P2,…,Pm的元素为
|AAA|1)(|AAA|
|AA||A||S|
|AAA|
m21
m
kj
mkji1
i
j
mji1
i
m
1i
i
m21
推论
S中至少具有一条性质的元素数为
mkji1
m21
1m
kji
mji1
ji
m
1i
i
m21
|AAA|1)(|AAA|
|AA||A|
|AAA|
例 6.3
例 6.3 求 1到 1000之间 (包含 1和 1000在内 )既不能被 5和 6，
也不能被 8整除的数有多少个。
解答
S＝ {x|x∈Z∧1≤x≤1000}
A＝ { x|x∈S∧x 可被 5整除 }
B＝ { x|x∈S∧x 可被 6整除 }
C＝ { x|x∈S∧x 可被 8整除 }
|T|表示有穷集 T中的元素数
x?表示小于等于 x的最大整数
lcm(x1,x2,…,xn)表示 x1,x2,…,xn的最小公倍数例 6.3
|A|＝?1000/5?＝ 200
|B|＝?1000/6?＝ 166
|C|＝?1000/8?＝ 125
|A∩B| ＝?1000/lcm(5,6)?＝ 33
|A∩C| ＝?1000/lcm(5,8)?＝ 25
|B∩C| ＝?1000/lcm(6,8)?＝ 41
|A∩B∩C| ＝?1000/lcm(5,6,8)?＝ 8
将这些数字依次填入文氏图，得到例 6.3
根据包含排斥原理，所求不能被 5,6和 8整除的数应为
由文氏图也可得知，不能被 5,6和 8整除的数有
1000－ (200+100＋ 33＋ 67)＝ 600个。
600
8-41)25(33125)166(200-1000
|CBA|
|)CB||CA||BA(|
|)C||B||A(||S||CBA|
广义并和广义交定义 6.10 设 A为集合,A的 元素的元素 构成的集合称为
A的 广义并,记为 ∪ A。
符号化表示为
∪ A＝ {x |?z(z∈A∧x∈z)}
定义 6.11 设 A为 非空 集合,A的所有 元素的公共元素 构成的集合称为 A的 广义交,记为 ∩ A。
符号化表示为
∩ A＝ {x |?z(z∈A→x∈z)}
例 6.4
例 6.4 设 A＝ {{a,b,c},{a,c,d},{a,e,f}}
B＝ {{a}}
C＝ {a,{c,d}}
则 ∪ A＝ {a,b,c,d,e,f}
∪ B＝ {a}
∪ C＝ a∪{c,d}
∪?＝?
∩ A＝ {a}
∩B ＝ {a}
∩C ＝ a∩{c,d}
广义并与广义交的说明
若 A＝ {A1,A2,…,An}，则 ∪ A＝ A1∪A 2∪ … ∪A n
若 A＝ {A1,A2,…,An}，则 ∩ A＝ A1∩A 2∩ … ∩A n
在后面的叙述中，若只说并或交，则这都是指集合的初级并或初级交；如果在并或交前边冠以,广义,两个字，则指集合的广义并或广义交。
为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：
– 称广义并、广义交、幂集、绝对补运算为一类运算
– 并、交、相对补、对称差运算为二类运算。
– 一类运算优先于二类运算
– 一类运算之间由右向左顺序进行
– 二类运算之间由括号决定先后顺序。
例 6.5
例 6.5 设 A＝ {{a},{a,b}}
计算 ∪∪ A,∩∩ A,∩∪ A∪(∪∪A － ∪∩ A)
解答 ∪ A＝ {a,b}
∩A ＝ {a}
∪∪A ＝ a∪b
∩∩A ＝ a
∩∪A ∪( ∪∪A － ∪∩ A)
＝ (a∩b)∪( a∪b － a)
＝ (a∩b)∪(b -a)
＝ b
6.3 集合恒等式
下面的恒等式给出了集合运算的主要算律，其中 A,B,C
代表任意集合。
幂等律 A∪A ＝ A (6.1)
A∩A ＝ A (6.2)
结合律 (A∪B)∪C ＝ A∪(B∪C) (6.3)
(A∩B)∩C ＝ A∩(B∩C) (6.4)
交换律 A∪B ＝ B∪A (6.5)
A∩B ＝ B∩A (6.6)
分配律 A∪(B∩C) ＝ (A∪B)∩(A∪C) (6.7)
A∩(B∪C) ＝ (A∩B)∪(A∩C) (6.8)
同一律 A∪?＝ A (6.9)
A∩E ＝ A (6.10)
6.3 集合恒等式零律 A∪E ＝ E (6.11)
A∩?＝? (6.12)
排中律 A∪ ～ A＝ E (6.13)
矛盾律 A∩ ～ A＝? (6.14)
A∪(A∩B) ＝ A (6.15)
A∩(A∪B) ＝ A (6.16)
德摩根律 A－ (B∪C) ＝ (A－ B)∩(A － C) (6.17)
A－ (B∩C) ＝ (A－ B)∪(A － C) (6.18)
～ (B∪C) ＝～ B∩ ～ C (6.19)
～ (B∩C) ＝～ B∪ ～ C (6.20)
～?＝ E (6.21)
～ E＝? (6.22)
双重否定律 ～ (～ A)＝ A (6.23)
集合运算性质的一些重要结果
A∩B?A,A∩B?B (6.24)
A?A∪B,B?A∪B (6.25)
A－ B?A (6.26)
A－ B＝ A∩ ～ B (6.27)
A∪B ＝ B? A?B? A∩B ＝ A? A－ B＝? (6.28)
A?B＝ B?A (6.29)
(A?B)?C＝ A?(B?C) (6.30)
A＝ A (6.31)
A?A＝? (6.32)
A?B＝ A?C? B＝ C (6.33)
对偶 (dual)原理
对偶 (dual)式,一个集合表达式，如果只含有
∩,∪,～,?,E、＝,?,?，那么同时把
∩ 与 ∪ 互换，把?与 E互换，把?与?互换,得到式子称为原式的对偶式。
对欧原理,对偶式同真假。或者说，集合恒等式的对偶式还是恒等式。
集合恒等式的证明方法
逻辑演算法利用 逻辑等值式 和 推理规则
集合演算法利用 集合恒等式 和 已知结论逻辑演算法的格式题目,A＝ B
证明,?x，
x∈A
… …
x∈B
所以 A＝ B
或证 P?Q ∧ Q?P
题目,A?B
证明,?x，
x∈A
… …
x∈B
所以 A?B
集合演算法的格式题目,A＝ B
证明,A
＝ … …
＝ B
所以 A＝ B
题目,A?B
证明,A
… …
B
所以 A?B
例 6.6
例 6.6 证明式 6.17，即 A－ (B∪C) ＝ (A－ B)∩( A － C)
证明 对任意的 x，有
x∈A － (B∪C)
x∈A ∧ x?B∪C
x∈A ∧ ┐(x∈B∨x∈C)
x∈A ∧ (┐x∈B∧┐x∈C)
x∈A ∧ (x?B ∧ x?C)
(x∈A∧x?B) ∧ (x∈A∧x?C)
x∈A － B ∧ x∈A － C
x∈(A － B)∩(A － C)
所以 A－ (B∪C) ＝ (A－ B)∩( A － C)
例 6.7
例 6.7 证明式 6.10，即 A∩E ＝ A
证明 对任意的 x，有
x∈A∩E
x∈A ∧ x∈E
x∈A ( 因为 x∈E 是恒真命题 )
所以 A∩E ＝ A
例 6.8
例 6.8 假设已知等式 6.1～ 6.14，试证等式 6.15，
即 A∪(A∩B) ＝ A。
证明 A∪(A∩B)
＝ (A∩E)∪(A∩B) ( 由等式 6.10)
＝ A∩(E∪B) (由等式 6.8)
＝ A∩(B∪E) (由等式 6.5)
＝ A∩E (由等式 6.11)
＝ A (由等式 6.10)
例 6.9
例 6.9 证明等式 6.27，即 A－ B＝ A∩ ～ B
证明 对于任意的 x，有
x∈A － B? x∈A ∧ x?B
x∈A ∧ x∈ ～ B
x∈A∩ ～ B
所以 A－ B＝ A∩ ～ B。
说明
等式 6.27把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。
例 6.10
例 6.10 证明 (A－ B)∪B ＝ A∪B
证明 (A－ B)∪B
＝ (A∩ ～ B)∪B
＝ (A∪B)∩( ～ B∪B)
＝ (A∪B)∩E
＝ A∪B
例 6.11
例 6.11 证明命题 6.28是真命题。
A∪B ＝ B? A?B? A∩B ＝ A? A－ B＝?
说明 式 6.28给出了 A?B的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。
证明思路
A∪B ＝ B? A?B? A∩B ＝ A? A－ B＝ A∪B ＝ B
例 6.11
证明 A∪B ＝ B? A?B
对于任意的 x，有
x∈A
x∈A∨x∈B
x∈A∪B
x∈B (因为 A∪B ＝ B)
所以 A?B。
例 6.11
证明 A?B? A∩B ＝ A
显然有 A∩B? A，
下面证 A? A∩B 。
对于任意的 x，有
x∈A
x∈A∧x∈A
x∈A∧x∈B (因为 A?B)
x∈A∩B
所以 A? A∩B
由集合相等的定义有 A∩B ＝ A。
例 6.11
证明 A∩B ＝ A? A－ B＝?
A－ B
＝ A∩ ～ B
＝ (A∩B)∩ ～ B (因为 A∩B ＝ A)
＝ A∩(B∩ ～ B)
＝ A∩?
＝?
例 6.11
证明 A－ B＝ A∪B ＝ B。
由例 6.10 (A－ B)∪B ＝ A∪B 及 A－ B＝? 有
A∪B
＝ B∪(A － B)
＝ B∪?
＝ B
例 6.12
例 6.12 化简 ((A∪B∪C)∩(A∪B)) － ((A∪(B － C))∩A)
解答 因为 A∪B? A∪B∪C,A?A∪(B － C)，
由式 6.28有：
((A∪B∪ C)∩(A∪B) )－ ((A∪ (B－ C))∩A )
＝ (A∪B) － A
＝ B－ A
例 6.13
例 6.13 已知 A?B＝ A?C，证明 B＝ C。
证明 已知 A?B＝ A?C
A?(A?B)＝ A?(A?C)
(A?A)?B＝ (A?A)?C (由式 6.30)
B＝C (由式 6.32)
B＝ C (由式 6.29)
B＝ C (由式 6.31)
学习要求
熟练掌握集合的子集,相等,空集,全集,幂集等概念及其符号化表示
熟练掌握集合的交,并,（ 相对和绝对 ） 补,对称差,
广义交,广义并的定义及其性质
掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法
牢记基本的集合恒等式 （ 等幂律,交换律,结合律,分配律,德 ·摩根律,收律,零律,同一律,排中律,矛盾律,余补律,双重否定律,补交转换律 ）
准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式作业
习题六
5,6,7,8,17,23,25,28
典型题
判断元素与集合的隶属关系以及集合之间的包含关系
集合的基本运算题
有关集合运算性质的分析题
集合相等或者包含的证明题
有穷集合的计数问题典型例题一判断下列命题是否为真
(1) {x}? {x}
(2) {x} ∈ {x}
(3) {x} ∈{x,{x}}
(4) {x}? {x,{x}}
(5) x ∈ {x} － {{x}}
(6) x? {x}∪x
(7) 若 x∈A,A∈P(B),则 x∈P(B)
(8) 若 x?A,A?P(B)，则 x?P(B)
答案
(1) 真
(2) 假
(3) 真
(4) 真
(5) 真
(6) 真
(7) 假
(8) 真分析典型例题一的分析
判断元素 a与集合 A的隶属关系是否成立的基本方法：
把 a作为一个整体，检查它在 A中是否出现，
注意这里的 a可能是集合表达式。
判断集合包含 A?B一般可以使用以下四种方法：
– 若 A,B是用枚举方式定义的，依次检查 A的每个元素是否在 B中出现。
– 若 A,B是用谓词法定义的，且 A,B中元素性质分别为 P和
Q，那么,如果 P则 Q”意味着 A?B,,P当且仅当 Q”意味着 A＝ B。
– 通过集合运算判断 A?B，即 A∪B ＝ B,A∩B ＝ A,A－ B＝
3个等式中有一个为真，则 A?B。
– 可以通过文氏图判断集合的包含（不是证明）。
典型例题二判断以下命题的真假
(1) A∩(B － C)＝ (A∩) － (A∩C)
(2) (A－ B)∩(B － A)＝?
(3) A－ (B∪C) ＝ (A－ B)∪C
(4) ～ (A－ B)＝ ～ (B－ A)
(5) ～ (A∩B)?A
(6) (A∩B)∪(B － A)? A
(7) A∪B ＝ A? B＝?
答案
(1) 真
(2) 真
(3) 假
(4) 假
(5) 假
(6) 假
(7) 假分析
本章的主要内容
– 集合的基本概念 — 集 合、相等,(真 )包含、子集、空集、
全集、幂集
– 集合运算 — 交、并,(相对和绝对 )补、对称差、广义交、
广义并
– 文氏图 — 有穷集计数问题
– 集合恒等式
本章与后续各章的关系
– 是集合论后面各章的基础
– 是典型的布尔代数系统
6.1 集合的基本概念
集合 (Set)是不能精确定义的基本概念。
– 所谓集合，是指我们无意中或思想中将一些确定的、彼此完全不同的客体的总和而考虑为一个整体。这些客体叫做该集合的元素。 (康托 )
– 直观地说，把一些事物汇集到一起组成一个整体就叫 集合,而这些事物就是这个集合的 元素 或 成员 。
例如：
– 方程 x2－ 1＝ 0的实数解集合：
– 26个英文字母的集合；
– 坐标平面上所有点的集合；
– … …
集合通常用大写的英文字母来标记。
常见的数的集合
N— 自然数集合
Z— 整数集合
Q— 有理数集合
R— 实数集合
C— 复数集合集合的表示方法
表示一个集合的方法主要有两种,列元素法 和 谓词表示法 。
列元素法 (roster)是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。
– A＝ {a,b,c,…,z}
– Z＝ {0,± 1,± 2,… }
– C＝ {桌子,灯泡,老虎,自然数 }
谓词表示法 (defining predicate)是用谓词来概括集合中元素的属性。
– B＝ {x|x∈R∧x 2－ 1＝ 0}
许多集合可以用两种方法来表示，如 B也可以写成 {-1,1}。
但是有些集合不可以用列元素法表示，如实数集合。
集合的元素
集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。
例如,{1,1,2,2,3}＝ {1,2,3}
集合的元素是无序的。
例如,{1,2,3}＝ {3,1,2}
在本书所采用的体系中规定,集合的元素都是集合 。
元素和集合之间的关系
元素和集合之间的关系是隶属关系，即 属于 或 不属于,属于记作 ∈,不属于记作?。
例如,A＝ {a,{b,c},d,{{d}}}
a∈ A,{b,c}∈ A,d∈ A,{{d}}∈ A，
b?A,{d}?A。
b和 {d}是 A的元素的元素。
可以用一种树形图表示集合与元素的隶属关系。
说明
隶属关系可以看作是处在不同层次上的集合之间的关系。
规定：对任何集合 A都有 A?A。
A
a {b,c} d {{d}}
b c {d}
d
子集（ subset）
定义 6.1 设 A,B为集合，如果 B中的每个元素都是 A中的元素，
则称 B是 A的子集合，简称 子集 。这时也称 B被 A包含,或 A包含 B，记作 B?A。
包含的符号化表示为
B?Ax(x∈B→x∈A)
如果 B不被 A包含，则记作 B A。
例如,N? Z? Q? R? C，但 Z N。
显然对任何集合 A都有 A?A。
隶属和包含的说明
隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。
例如 A＝ {a,{a}}和 {a}
既有 {a}∈A,又有 {a}?A。
前者把它们看成是不同层次上的两个集合，
后者把它们看成是同一层次上的两个集合。
集合相等 (equal)
定义 6.2 设 A,B为集合，如果 A?B 且 B?A，则称 A与
B相等,记作 A＝ B。
相等的符号化表示为：
A＝ B? A?B ∧ B?A
如果 A与 B不相等，则记作 A≠B 。
真子集定义 6.3 设 A,B为集合，如果 B?A 且 B≠A,则称 B是
A的 真子集,记作 B?A。
真子集的符号化表示为
B?A? B?A ∧ B≠A
如果 B不是 A的真子集，则记作 B? A。
例如,N? N
空集 (empty set)
定义 6.4 不含任何元素的集合叫做 空集,记作?。
空集的符号化表示为,?＝ {x|x≠x} 。
例如,{x|x∈R∧x 2+1=0}
是方程 x2+1=0的实数解集，因为该方程无实数解，所以是空集。
空集的性质推论 空集是唯一的。
证明,假设存在空集?1和?2，由定理 6.1有
12,?21。
根据集合相等的定义，有?1＝?2。
定理 6.1 空集是一切集合的子集。
证明,任给集合 A，由子集定义有
Ax(x∈? → x∈A)
右边的蕴涵式因前件假而为真命题，
所以 A也为真。
n元集
含有 n个元素的集合简称 n元集,它的含有 m(m≤n) 个元素的子集叫做它的 m元子集 。
例 6.1 A＝ {1,2,3}，将 A的子集分类：
0元子集（空集）?
1元子集（单元集） {1},{2},{3}
2元子集 {1,2},{1,3},{2,3}
3元子集 {1,2,3}
幂集 ( power set )
一般地说，对于 n元集 A，它的 0元子集有 个,1元子集有个,…,m元子集有 个,…,n元子集有 个。子集总数为
nnn2n1n0n 2CCCC
0nC 1nC
mnC nnC
定义 6.5 设 A为集合，把 A的全部子集构成的集合叫做 A的 幂集,
记作 P(A)(或 PA,2A)。
P(A)＝ {x | x?A}
若 A是 n元集，则 P(A)有 2n 个元素。
全集定义 6.6 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为 全集,记作 E。
说明
全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。
例如，在研究平面上直线的相互关系时，可以把整个平面 (平面上所有点的集合 )取作全集，也可以把整个空间 (空间上所有点的集合 )取作全集。
一般地说，全集取得小一些，问题的描述和处理会简单些。
6.2 集合的运算定义 6.7 设 A,B为集合,A与 B的 并集 A∪B,交集 A∩B,B对 A
的 相对补集 A－ B分别定义如下：
A∪B ＝ {x|x∈A∨x∈B } (union set)
A∩B ＝ {x|x∈A∧x∈B } (intersection set)
A－ B＝ {x|x∈A∧x?B } (difference set)
举例 设 A＝ {a,b,c},B＝ {a},C＝ {b,d} 则有
A∪B ＝ {a,b,c},A∩B ＝ {a}，
A－ B＝ {b,c}，
B－ A＝?,B∩C ＝?
说明
如果两个集合的交集为?,则称这两个集合是不相交的。例如 B和 C是不相交的。
n个集合的并和交
两个集合的并和交运算可以推广成 n个集合的并和交：
A1∪A 2∪ … ∪A n＝ {x|x∈A 1∨x∈A 2∨ … ∨x∈A n}
A1∩A 2∩ … ∩A n＝ {x|x∈A 1∧x∈A 2∧ … ∧x∈A n}
上述的并和交可以简记为：
n
1i
iA
＝ A1∩A 2∩ … ∩A n
n
1i
iA
＝ A1∪A 2∪ … ∪A n
两个集合的并和交运算可以推广到无穷多个集合的情况：
1i
iA
＝ A1∩A 2∩ …
1i
iA
＝ A1∪A 2∪ …
对称差集定义 6.8 设 A,B为集合,A与 B的 对称差集 A?B定义为：
A?B＝ (A－ B)∪(B － A)
对称差运算的另一种定义是
A?B＝ (A∪B) － (A∩B)
例如,A＝ {a,b,c},B＝ {b,d}，
则 A?B＝ {a,c,d}
绝对补集定义 6.9 ～ A＝ E－ A＝ {x|x∈E∧x?A}
因为 E是全集,x∈E 是真命题，所以～ A可以定义为：
A＝ {x|x? A }
例如,E＝ {a,b,c,d},A＝ {a,b,c}
～ A＝ {d}
文氏图 (Venn Diagram)
集合之间的关系和运算可以用 文氏图 给予形象的描述。
文氏图的构造方法如下：
– 画一个大矩形表示全集 E(有时为简单起见可将全集省略 )。
– 在矩形内画一些圆 (或任何其它的适当的闭曲线 )，用圆的内部表示集合。
– 不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。
– 图中阴影的区域表示新组成的集合。
– 可以用实心点代表集合中的元素。
文氏图的实例有穷集的计数问题
使用文氏图可以很方便地解决 有穷集的计数问题 。
首先根据已知条件把对应的文氏图画出来。
– 一般地说，每一条性质决定一个集合。
– 有多少条性质，就有多少个集合。
– 如果没有特殊说明，任何两个集合都画成相交的
然后将已知集合的元素数填入表示该集合的区域内。
– 通常从 n个集合的交集填起，
– 根据计算的结果将数字逐步填入所有的空白区域。
– 如果交集的数字是未知的，可以设为 x。
根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。
例 6.2
例 6.2 对 24名会外语的科技人员进行掌握外语情况的调查。
其统计结果如下：会英、日、德和法语的人分别为 13,5
,10和 9人，其中同时会英语和日语的有 2人，会英、德和法语中任两种语言的都是 4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言 (英、德、法、日 )的人数和会三种语言的人数。
解,令 A,B,C,D分别表示会英、法、德、日语的人的集合
。根据题意画出文氏图。设同时会三种语言的有 x人，只会英、法或德语一种语言的分别为 y1,y2和 y3人。将 x和 y1
,y2,y3填入图中相应的区域，然后依次填入其它区域的人数。
例 6.2
4-x
4-x
4-x
x
y2 y1
y3
2 5-2
英 13法 9
德 10
日 5
y1+2(4-x)+x+2＝ 13
y2+2(4-x)+x＝ 9
y3+2(4-x)+x＝ 10
y1+y2+y3+3(4-x)+x＝ 24-5
包含排斥原理定理 6.2 设 S为有穷集,P1,P2,…,Pm是 m个性质。 S中的任何元素 x或者具有性质 Pi，或者不具有性质 Pi(i=1,2,… m),
两种情况必居其一。令 Ai表示 S中具有性质 Pk的元素构成的子集，则 S中不具有性质 P1,P2,…,Pm的元素为
|AAA|1)(|AAA|
|AA||A||S|
|AAA|
m21
m
kj
mkji1
i
j
mji1
i
m
1i
i
m21
推论
S中至少具有一条性质的元素数为
mkji1
m21
1m
kji
mji1
ji
m
1i
i
m21
|AAA|1)(|AAA|
|AA||A|
|AAA|
例 6.3
例 6.3 求 1到 1000之间 (包含 1和 1000在内 )既不能被 5和 6，
也不能被 8整除的数有多少个。
解答
S＝ {x|x∈Z∧1≤x≤1000}
A＝ { x|x∈S∧x 可被 5整除 }
B＝ { x|x∈S∧x 可被 6整除 }
C＝ { x|x∈S∧x 可被 8整除 }
|T|表示有穷集 T中的元素数
x?表示小于等于 x的最大整数
lcm(x1,x2,…,xn)表示 x1,x2,…,xn的最小公倍数例 6.3
|A|＝?1000/5?＝ 200
|B|＝?1000/6?＝ 166
|C|＝?1000/8?＝ 125
|A∩B| ＝?1000/lcm(5,6)?＝ 33
|A∩C| ＝?1000/lcm(5,8)?＝ 25
|B∩C| ＝?1000/lcm(6,8)?＝ 41
|A∩B∩C| ＝?1000/lcm(5,6,8)?＝ 8
将这些数字依次填入文氏图，得到例 6.3
根据包含排斥原理，所求不能被 5,6和 8整除的数应为
由文氏图也可得知，不能被 5,6和 8整除的数有
1000－ (200+100＋ 33＋ 67)＝ 600个。
600
8-41)25(33125)166(200-1000
|CBA|
|)CB||CA||BA(|
|)C||B||A(||S||CBA|
广义并和广义交定义 6.10 设 A为集合,A的 元素的元素 构成的集合称为
A的 广义并,记为 ∪ A。
符号化表示为
∪ A＝ {x |?z(z∈A∧x∈z)}
定义 6.11 设 A为 非空 集合,A的所有 元素的公共元素 构成的集合称为 A的 广义交,记为 ∩ A。
符号化表示为
∩ A＝ {x |?z(z∈A→x∈z)}
例 6.4
例 6.4 设 A＝ {{a,b,c},{a,c,d},{a,e,f}}
B＝ {{a}}
C＝ {a,{c,d}}
则 ∪ A＝ {a,b,c,d,e,f}
∪ B＝ {a}
∪ C＝ a∪{c,d}
∪?＝?
∩ A＝ {a}
∩B ＝ {a}
∩C ＝ a∩{c,d}
广义并与广义交的说明
若 A＝ {A1,A2,…,An}，则 ∪ A＝ A1∪A 2∪ … ∪A n
若 A＝ {A1,A2,…,An}，则 ∩ A＝ A1∩A 2∩ … ∩A n
在后面的叙述中，若只说并或交，则这都是指集合的初级并或初级交；如果在并或交前边冠以,广义,两个字，则指集合的广义并或广义交。
为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：
– 称广义并、广义交、幂集、绝对补运算为一类运算
– 并、交、相对补、对称差运算为二类运算。
– 一类运算优先于二类运算
– 一类运算之间由右向左顺序进行
– 二类运算之间由括号决定先后顺序。
例 6.5
例 6.5 设 A＝ {{a},{a,b}}
计算 ∪∪ A,∩∩ A,∩∪ A∪(∪∪A － ∪∩ A)
解答 ∪ A＝ {a,b}
∩A ＝ {a}
∪∪A ＝ a∪b
∩∩A ＝ a
∩∪A ∪( ∪∪A － ∪∩ A)
＝ (a∩b)∪( a∪b － a)
＝ (a∩b)∪(b -a)
＝ b
6.3 集合恒等式
下面的恒等式给出了集合运算的主要算律，其中 A,B,C
代表任意集合。
幂等律 A∪A ＝ A (6.1)
A∩A ＝ A (6.2)
结合律 (A∪B)∪C ＝ A∪(B∪C) (6.3)
(A∩B)∩C ＝ A∩(B∩C) (6.4)
交换律 A∪B ＝ B∪A (6.5)
A∩B ＝ B∩A (6.6)
分配律 A∪(B∩C) ＝ (A∪B)∩(A∪C) (6.7)
A∩(B∪C) ＝ (A∩B)∪(A∩C) (6.8)
同一律 A∪?＝ A (6.9)
A∩E ＝ A (6.10)
6.3 集合恒等式零律 A∪E ＝ E (6.11)
A∩?＝? (6.12)
排中律 A∪ ～ A＝ E (6.13)
矛盾律 A∩ ～ A＝? (6.14)
A∪(A∩B) ＝ A (6.15)
A∩(A∪B) ＝ A (6.16)
德摩根律 A－ (B∪C) ＝ (A－ B)∩(A － C) (6.17)
A－ (B∩C) ＝ (A－ B)∪(A － C) (6.18)
～ (B∪C) ＝～ B∩ ～ C (6.19)
～ (B∩C) ＝～ B∪ ～ C (6.20)
～?＝ E (6.21)
～ E＝? (6.22)
双重否定律 ～ (～ A)＝ A (6.23)
集合运算性质的一些重要结果
A∩B?A,A∩B?B (6.24)
A?A∪B,B?A∪B (6.25)
A－ B?A (6.26)
A－ B＝ A∩ ～ B (6.27)
A∪B ＝ B? A?B? A∩B ＝ A? A－ B＝? (6.28)
A?B＝ B?A (6.29)
(A?B)?C＝ A?(B?C) (6.30)
A＝ A (6.31)
A?A＝? (6.32)
A?B＝ A?C? B＝ C (6.33)
对偶 (dual)原理
对偶 (dual)式,一个集合表达式，如果只含有
∩,∪,～,?,E、＝,?,?，那么同时把
∩ 与 ∪ 互换，把?与 E互换，把?与?互换,得到式子称为原式的对偶式。
对欧原理,对偶式同真假。或者说，集合恒等式的对偶式还是恒等式。
集合恒等式的证明方法
逻辑演算法利用 逻辑等值式 和 推理规则
集合演算法利用 集合恒等式 和 已知结论逻辑演算法的格式题目,A＝ B
证明,?x，
x∈A
… …
x∈B
所以 A＝ B
或证 P?Q ∧ Q?P
题目,A?B
证明,?x，
x∈A
… …
x∈B
所以 A?B
集合演算法的格式题目,A＝ B
证明,A
＝ … …
＝ B
所以 A＝ B
题目,A?B
证明,A
… …
B
所以 A?B
例 6.6
例 6.6 证明式 6.17，即 A－ (B∪C) ＝ (A－ B)∩( A － C)
证明 对任意的 x，有
x∈A － (B∪C)
x∈A ∧ x?B∪C
x∈A ∧ ┐(x∈B∨x∈C)
x∈A ∧ (┐x∈B∧┐x∈C)
x∈A ∧ (x?B ∧ x?C)
(x∈A∧x?B) ∧ (x∈A∧x?C)
x∈A － B ∧ x∈A － C
x∈(A － B)∩(A － C)
所以 A－ (B∪C) ＝ (A－ B)∩( A － C)
例 6.7
例 6.7 证明式 6.10，即 A∩E ＝ A
证明 对任意的 x，有
x∈A∩E
x∈A ∧ x∈E
x∈A ( 因为 x∈E 是恒真命题 )
所以 A∩E ＝ A
例 6.8
例 6.8 假设已知等式 6.1～ 6.14，试证等式 6.15，
即 A∪(A∩B) ＝ A。
证明 A∪(A∩B)
＝ (A∩E)∪(A∩B) ( 由等式 6.10)
＝ A∩(E∪B) (由等式 6.8)
＝ A∩(B∪E) (由等式 6.5)
＝ A∩E (由等式 6.11)
＝ A (由等式 6.10)
例 6.9
例 6.9 证明等式 6.27，即 A－ B＝ A∩ ～ B
证明 对于任意的 x，有
x∈A － B? x∈A ∧ x?B
x∈A ∧ x∈ ～ B
x∈A∩ ～ B
所以 A－ B＝ A∩ ～ B。
说明
等式 6.27把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。
例 6.10
例 6.10 证明 (A－ B)∪B ＝ A∪B
证明 (A－ B)∪B
＝ (A∩ ～ B)∪B
＝ (A∪B)∩( ～ B∪B)
＝ (A∪B)∩E
＝ A∪B
例 6.11
例 6.11 证明命题 6.28是真命题。
A∪B ＝ B? A?B? A∩B ＝ A? A－ B＝?
说明 式 6.28给出了 A?B的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。
证明思路
A∪B ＝ B? A?B? A∩B ＝ A? A－ B＝ A∪B ＝ B
例 6.11
证明 A∪B ＝ B? A?B
对于任意的 x，有
x∈A
x∈A∨x∈B
x∈A∪B
x∈B (因为 A∪B ＝ B)
所以 A?B。
例 6.11
证明 A?B? A∩B ＝ A
显然有 A∩B? A，
下面证 A? A∩B 。
对于任意的 x，有
x∈A
x∈A∧x∈A
x∈A∧x∈B (因为 A?B)
x∈A∩B
所以 A? A∩B
由集合相等的定义有 A∩B ＝ A。
例 6.11
证明 A∩B ＝ A? A－ B＝?
A－ B
＝ A∩ ～ B
＝ (A∩B)∩ ～ B (因为 A∩B ＝ A)
＝ A∩(B∩ ～ B)
＝ A∩?
＝?
例 6.11
证明 A－ B＝ A∪B ＝ B。
由例 6.10 (A－ B)∪B ＝ A∪B 及 A－ B＝? 有
A∪B
＝ B∪(A － B)
＝ B∪?
＝ B
例 6.12
例 6.12 化简 ((A∪B∪C)∩(A∪B)) － ((A∪(B － C))∩A)
解答 因为 A∪B? A∪B∪C,A?A∪(B － C)，
由式 6.28有：
((A∪B∪ C)∩(A∪B) )－ ((A∪ (B－ C))∩A )
＝ (A∪B) － A
＝ B－ A
例 6.13
例 6.13 已知 A?B＝ A?C，证明 B＝ C。
证明 已知 A?B＝ A?C
A?(A?B)＝ A?(A?C)
(A?A)?B＝ (A?A)?C (由式 6.30)
B＝C (由式 6.32)
B＝ C (由式 6.29)
B＝ C (由式 6.31)
学习要求
熟练掌握集合的子集,相等,空集,全集,幂集等概念及其符号化表示
熟练掌握集合的交,并,（ 相对和绝对 ） 补,对称差,
广义交,广义并的定义及其性质
掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法
牢记基本的集合恒等式 （ 等幂律,交换律,结合律,分配律,德 ·摩根律,收律,零律,同一律,排中律,矛盾律,余补律,双重否定律,补交转换律 ）
准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式作业
习题六
5,6,7,8,17,23,25,28
典型题
判断元素与集合的隶属关系以及集合之间的包含关系
集合的基本运算题
有关集合运算性质的分析题
集合相等或者包含的证明题
有穷集合的计数问题典型例题一判断下列命题是否为真
(1) {x}? {x}
(2) {x} ∈ {x}
(3) {x} ∈{x,{x}}
(4) {x}? {x,{x}}
(5) x ∈ {x} － {{x}}
(6) x? {x}∪x
(7) 若 x∈A,A∈P(B),则 x∈P(B)
(8) 若 x?A,A?P(B)，则 x?P(B)
答案
(1) 真
(2) 假
(3) 真
(4) 真
(5) 真
(6) 真
(7) 假
(8) 真分析典型例题一的分析
判断元素 a与集合 A的隶属关系是否成立的基本方法：
把 a作为一个整体，检查它在 A中是否出现，
注意这里的 a可能是集合表达式。
判断集合包含 A?B一般可以使用以下四种方法：
– 若 A,B是用枚举方式定义的，依次检查 A的每个元素是否在 B中出现。
– 若 A,B是用谓词法定义的，且 A,B中元素性质分别为 P和
Q，那么,如果 P则 Q”意味着 A?B,,P当且仅当 Q”意味着 A＝ B。
– 通过集合运算判断 A?B，即 A∪B ＝ B,A∩B ＝ A,A－ B＝
3个等式中有一个为真，则 A?B。
– 可以通过文氏图判断集合的包含（不是证明）。
典型例题二判断以下命题的真假
(1) A∩(B － C)＝ (A∩) － (A∩C)
(2) (A－ B)∩(B － A)＝?
(3) A－ (B∪C) ＝ (A－ B)∪C
(4) ～ (A－ B)＝ ～ (B－ A)
(5) ～ (A∩B)?A
(6) (A∩B)∪(B － A)? A
(7) A∪B ＝ A? B＝?
答案
(1) 真
(2) 真
(3) 假
(4) 假
(5) 假
(6) 假
(7) 假分析
