第3 章集合的基本概念和运算
3.集合的基本概念
1
集合是不能精确定义的基本的数学概念。一般认为一个集合指的是一些可确定的、可
分辨的事物构成的整体。对于给定的集合和事物,应该可以断定这个特定的事物是否属于
这个集合。如果属于,就称它为这个集合的元素。集合可以由各种类型的事物构成。例如,
26个英文字母的集合;
PASCAL语言中保留字的集合;
坐标平面上所有点的集合;
全体中国人的集合;
……
集合通常用大写的英文字母来标记。例如,
N
代表自然数集合(包括0),
Z
代表整数集
合,
Q
代表有理数集合,
R
代表实数集合,C代表复数集合。
给出一个集合的方法有两种,一种是列出集合的所有元素,元素之间用逗号隔开,并把
它们用花括号括起来。例如,
A={b,d}a,c,
其中,
a
是
A
的元素,记作a∈A。同样有b∈A,但
e
不是
A
的元素,
c∈
A
和d∈A, 可记作
e.A。另一种方法是用谓词概括该集合中元素的属性。集合
B={x|P(x)}
表示
B
由使P(x)为真的全体
x
构成。例如,
则B={4,5,6}。
B={x|x∈Z∧3<x≤6}
一般来说,集合的元素可以是任何类型的事物,一个集合也可以作为另一个集合的元
素。例如,集合
c}∈A,
A={a,{b,d,{{c},d}}}
其中,b,d}}∈A, d}.A。
b
是
A
的元素{c} 不
a∈A,{d∈A,{{但b.A,{b,的元素,
是
A
的元素。可以用一种树形结构把集合和它的元素之间的关系表示
出来。在每个层次上,都把集合作为一个结点,它的元素则作为它的儿
子。这样,
A
集合的结构如图3-1所示。不难看出,
A
有4个儿子,所以
A
只有4个元素,而b、
c
和{d}都是
A
的元素的元素,但不是
A
的元素。
在集合论中,人们还规定元素之间是彼此相异的,并且是没有次序关
系的。例如,集合{3,4,5}、{3,4,4,4,5}和{5,3,4}都是同一个集合。图3-
1
下面考虑两个集合之间的关系。
定义3.1
设A、
B
为集合,如果
B
中的每个元素都是
A
中的元素,则称
B
为
A
的子
第3章集合的基本概念和运算·57·
集合,简称子集。这时也称
B
被
A
包含,或
A
包含B,记作B.A。如果
B
不被
A
包含,则
记作B.A。包含的符号化表示为
B.A..x(x∈B→x∈A)
例如,A={1,B={1},1,则有B.A,但B.C。因为存在0,
0,2},0,C={2}, C.A, 0∈
B
但0.C。类似地有C.B。
根据定义不难得到:对任何集合S,都有S.S。
设A、
B
为集合,如果A.
B
且B.A,则称
A
与
B
相等,记作
A
=B。符
号化表示为
定义3.2
如果
A
和
B
不相等,则记作A≠BA
。
=B.A.B∧B.
A
由以上定义可知,两个集合相等的充分必要条件是它们具有相同的元素。例如,
A={x|
x
是小于或等于3的素数}
则A=B。
B={x|x=2∨x=3}
定义3.3
设A、
B
为集合,如果B.
A
且B≠A,则称
B
是
A
的真子集,记作B.A。
如果
B
不是
A
的真子集,则记作B.A。这时,或者B.A,或者B=A。
定义3.4
例如,{0,是{1,的真子集, 1,和{1,都不是{1,的真子集。
1} 0,2} 但{3} 0,2} 0,2}
不含任何元素的集合称为空集,记作.。空集可以符号化表示
为
.={x|x≠x}
空集是客观存在的,例如,
A={x|x∈R∧x2+1=0}
是方程x2+1=0的实数解集。因为该方程没有实数解,所以A=. 。
空集是一切集合的子集。
证明任给集合A,由子集定义有
..A..x(x∈.→x∈A)
定理3.1
右边的蕴涵式中因前件x∈. 为假,所以整个蕴涵式对一切
x
为真,因此..
A
为真。■
推论空集是唯一的。
证明假设存在空集.1 和.2, 1有.1..2 和.2..1,
由定理3.根据集合相等的定
义得.1=.2。■
确定下列命题是否为真。
例3.1
(1)...;(2).∈.;(3)..{.};(4).∈{.}。
解(1),(3),(4)为真;(2)为假。
由例3.1不难看出.与{.}的区别。.中不含有任何元素,而{.}中有一个元素.,所
以.≠{.}。
含有
n
个元素的集合简称
n
元集,它的含有
m
个(m≤n)元素的子集称作它的
m
元子
集。任给一个
n
元集,怎样求出它的全部子集呢?举例说明如下。
例3.2
A={b,求
A
的全部子集。
a,c}
,
解将
A
的子集从小到大分类
:
·58· 离散数学(第六版)
0元子集,即空集,只有1个:.
。
1元子集,即单元集,3 个:{b},
{
有C1a},{c}
。
2元子集,有C2a,a,b,
3 个:{b},{c},{c}
。
3元子集,有C3a,}
。
3 个:{b,
一般来说,对于
n
元集A,它(c) 的
m
(0≤
m
≤n)元子集有Cm
个,所以不同的子集总
数是
n
C0
n
+…+Cn
n
+C1
n
由二项式定理不难证明这个和是2n
。所以,
n
个子集。
n
元集有2
设
A
为集合,把
A
的全体子集构成的集合称为
A
的幂集,记作P(A)( 或
PA,2A
)。符号化表示为
P(A)={x|x.A}
定义3.5
设A={a,bP,
(A)
由例3.
a},{c},{b},{c},{c},{b,
c}, 2可知
={.,{b},{a,a,b,a,c}}
不难看出
例3.3,若
A
是
n
元集,则P(A)有2n
个元素。
计算以下幂集
:
(1)P(.)
;
(2)P({.})
;
(3)P({.,{.}})
;
(4)P({1,{2,3}})
。
解(1)P(.)={.}
;
(2)P({.})={.,{.}}
;
(3)P({.,{.}})={.,{.},{{.}},{.,{.}}}
;
定义3.6(4)P({1,{2,3}})={.,{1},{{2,3}},{1,{2,3}}}
。
在一个具体问题中,如果所涉及的集合都是某个集合的子集,则称这个集
合为全集,记作
E
(或U)。
全集是个有相对性的概念。由于所研究的问题不同,所取的全集也不同。例如,在研究
平面解析几何的问题时可以把整个坐标平面取作全集;在研究整数的问题时,可以把整数集
Z取作全集。
3.集合的基本运算
2
给定集合
A
和B,可以通过集合的并(∪)、交(∩)、相对补(-)、绝对补(~)和对称差
(..)
定义3.7
等运算产生新的集合。
设A、
B
为集合,
A
与
B
的并集
A
∪B、交集
A
∩B、
B
对
A
的相对补集
A-
B
分别定义如下:
A∪B={x|x∈A∨x∈B}
A∩B={x|x∈A∧x∈B}
A-B={x|x∈A∧x.B}
第3章集合的基本概念和运算·59·
显然,A∪
B
由
A
或
B
中的元素构成,A∩
B
由
A
和
B
中的公共元素构成,A-
B
由属
于
A
但不属于
B
的元素构成。例如,
A={1,2,3},B={1,4},C={3}
则有
A∪B={1,2,3,4}=B∪
A
A∩B={1}=B∩
A
A-B={2,3}
B-A={4}
C-A=.
B∩C=.
当两个集合的交集是空集时,称它们是不交的。上面例子中的
B
和
C
是不交的。
把以上定义加以推广,可以得到
n
个集合的并集和交集,即
A1∪A2∪…∪An
={x|x∈A1∨x∈A2∨…∨x∈An
}
A1∩A2∩…∩An
={x|x∈A1∧x∈A2∧…∧x∈An
}
例如,
{2}∪{{1},{2}}2,{1},{2}} 0,1}∪{1,0,1,={0,1,0,1,
{2}∩{{1},{
0,1}∩{1,0,1,2}}=.
可以把
n
个集合的并和交简记为∪Ai
和∩Ai,即
ni=1
ni=1
∪(n) Ai=A1∪A2∪…∪An
i=1
∩(n) Ai=A1∩A2∩…∩An
i=1
可数无穷多个集合的并和交,可以记为
∪(∞) Ai=A1∪A2∪…
i=1
∩(∞) Ai=A1∩A2∩…
=
定义3.8
设
E
为全集,A.E(i) ,(1) 则称
A
对
E
的相对补集为
A
的绝对补集,记作
~A,即
~A=E-A={x|x∈E∧x.A}
因为
E
为全集,在所研究的问题中,任何集合的元素
x
都是
E
的元素,也就是说,x∈
E
是真命题。所以~
A
可以定义为
例如,
~A={x|x.A}
E={0,1,2,3},A={0,1,2},B={0,1,2,3},C=
.
则
~A={3}, ~B=.,~C=
E
·60· 离散数学(第六版)
设A、
B
为集合,则
A
与
B
的对称差为
定义3.9
例如,
A..B=(A-B)∪(B-A)
A={0,1,2},B={2,3}
则有
A..B={0,1}∪{3}={0,1,3}
A
与
B
的对称差还有一个等价的定义,即
A..B=(A∪B)-(A∩B)
在上面的例子中用这种定义也可以得到同样的结果,即
A..B={0,1,3}2}0,3}
2,-{={1,
集合之间的相互关系和有关的运算可以用文氏图给予形象描述,文氏图的构造方法
如下。
首先画一个大矩形表示全集E,其次在矩形内画一些圆(或任何其他的适当的闭曲线),
用圆的内部表示集合。在一般情况下,如果不特殊说明,这些表示集合的圆应该是彼此相交
的。如果已知某两个集合是不交的,则表示它们的圆彼此相离。通常在图中画有阴影的区
域表示新组成的集合。图3-2是一些文氏图的实例。
图3-
2
任何代数运算都遵从一定的算律,集合运算也不例外。下面列出的是集合运算的主要
算律,其中的A、B、
C
表示任意的集合,
E
为全集。
幂等律A∪A=
A
(1)
3.
A∩A=
A
3.
(2)
结合律((3)
A∪B)∪C=A∪(B∪C)3.
(A∩B)∩C=A∩(B∩C) (4)
3.
交换律A∪B=(3.
B∪
A
5)
A∩B=B∩
A
3.
(6)
分配律A∪(B∩C)=(A∪B)∩(A∪C) (3.
7)
A∩(B∪C)=(A∩B)∪(A∩C) (3.
8)
同一律(9)
A∪.=
A
3.
A∩E=
A
(10)
3.
第3章集合的基本概念和运算·61·
零律A∪E=(11)
E
3.
A∩.=. (12)
3.
排中律A∪~A=
E
(13)
3.
矛盾律A∩~A=. 3.
(14)
吸收律A∪(=
A
3.
A∩B)(15)
A∩(A∪B)(3.
=
A
16)
德摩根律A-(=(B)∩(C)3.
B∪C)A-A-(17)
A-(B∩C)A-A-C) (18)
=(B)∪(3.
~(B∪C)B∩~
C
(19)
=~3.
~(B∩C)B∪~
C
3.
=~(20)
余补律~.=
E
3.
(21)
~E=. (22)
3.
双重否定律~(=
A
3.
~A)(23)
以上恒等式的证明主要用到命题演算的等值式。证明的基本思想:欲证
P
=Q,
即证
P.Q∧Q.
P
也就是要证对任意的
x
有
x∈P.x∈
Q
和x∈Q.x∈
P
成立,把这两个式子合到一起就是
例3.4
证明式(3.即
x∈P.x∈
Q
17),
证明对任意的x,
A-(B∪C)=(A-B)∩(A-C)
x∈A-(B∪C)
.x∈A∧x.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)
除了以上的算律以外,还有一些关于集合运算性质的重要结论。由于篇幅所限,有关的
证明略去,仅把结论列在下面。
A∩B.A,A∩B.
B
(24)
3.
A.A∪B,B.A∪
B
(3.
25)
·62· 离散数学(第六版)
A-B.
A
(26)
3.
A-B=(27)
A∩~
B
3.
A∪B=B.A.B.A∩B=A.A-(28)
B=. 3.
A..B=B..
A
(29)
3.
(A..B)..C=A..((30)
B..C)3.
A...=
A
(31)
3.
A..A=. (3.
32)
A..B=A..C.B=(33)
C
3.
式(3.建立了相对补运算和交运算之间的联系。可以利用它把相对补转变成交。请
看例3.27)
例3.5。
5
证明(A-B)∪B=A∪B。
证明(A-B)∪
B
=(A∩~B)∪
B
=(A∪B)∩(~B∪B)
=(A∪B)∩
E
28)
=A∪
B
这不仅提供了证明两个集合之间包含关系
式(3.给出了A.
B
的3种等价的定义,
的新方法,同时也可以用于集合公式的化简。
例3.6
化简((A∪B∪C)∩(A∪B))-((A∪(B-C))∩A)。
解因为A∪B.A∪B∪
(
C,B-由式(28)
A.A∪(C), 3.有
A∪B∪C)∩(A∪B)=A∪
B
所以,原式等于
(A∪(B-C))∩A=
A
(A∪B)-A=B-
A
例3.7
设A.B,证明~B.~A。
证明已知A.B,由式(3.得B∩A=A。所以28)
再利用式(3.有
~B∪~A=~(B∩A)=~
A
(德摩根律)
28)
~B.~
A
式(3.~式(33)是关于对称差运算的算律,前4条可通过对称差的定义加以证明,
29)3.
最后一条叫作消去律,它的证明在例3.
例3.8
已知A..B=A..C,证明
8
B
中
=
。
C
。
证明A..B=A..
C
(已知
)
则有A..(A..B)=A..(A..C)
(A..A)..B=(A..A)..
C
(结合律)
...B=...
C
(3.
式(32)
)
所以B=(式(29) 3.
C
3.和式(31))
第3章集合的基本概念和运算·63·
3.集合中元素的计数
3
集合A={1,n}, 可以说这个集合的基数是n,记作
2,…,它含有
n
个元素,
cardA=
n
所谓基数,是表示集合中所含元素多少的量。如果
A
的基数是n,也可以记为|A|=n,显然
空集的基数是
定义3.100,即|.|=0。
a,c} 而N、Q、
有穷集的基数很容易确定,而无穷集的基数就比较复杂了,这里不讨论这个问题。本节
所涉及的计数问题是针对有穷集而言。下面先看一个简单的例子。
有100 名程序员,其中47 名熟悉FORTRAN 语言,35 名熟悉PASCAL 语
言,23 名熟悉这两种语言。有多少人对这两种语言都不熟悉?
设
A
为集合,若存在自然数n(0也是自然数), 使得|A|=cardA
=n,则
称
A
为有穷集,否则称
A
为无穷集。
例如,{b,是有穷集, Z、
R
都是无穷集。
例3.9
解设A、
B
分别表示熟悉FORTRAN 语言和PASCAL 语言的程序员的集合,则该问
题可以用图3-3来表示。将熟悉两种语言的对应人数23 填到
A
∩
B
的区域内,不难得到
A-
B
和B-
A
的人数分别为
|A-B|=|A|-|A∩B|=47-23=24
|B-A|=|B|-|A∩B|=35-23=12
从而得到
|A∪B|=24+23+12=59
|~(A∪B)|=100-59=41
所以,两种语言都不熟悉的有41 人。
使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图
画出来。一般来说,每条性质决定一个集合,有多少条性质,就有多少个集合。如果没有特
殊的说明,任何两个集合都是相交的。然后将已知集合的基数填入表示该集合的区域内。
通常是从几个集合的交集填起,接着根据计算的结果将数字逐步填入其他空白区域内,直到
所有区域都填好为止。
例3.10
求1~1000 中不能被5或6,也不能被8整除的数的个数。
解设1~1000 的整数构成全集E,A、B、
C
分别表示其中可被5、6或8整除的数的集
合。文氏图如图3-4所示。
图3-
3
图3-
4
·64· 离散数学(第六版)
在A∩B∩
C
中的数一定可以被5、6和8的最小公倍数[5,6,8]=120 整除,即
|A∩B∩C|=
1000/[5,6,8]=
1000/120
=8
其中,
x
表示小于或等于
x
的最大整数。然后将8填入A∩B∩
C
的区域内
。
同样可
得
|A∩B|=
1000/[5,6]=
1000/30
=33
|A∩C|=
1000/[5,8]=
1000/40
=25
|B∩C|=
1000/[6,8]=
1000/24
=41
然后将33-8=25,25-8=17,41-8=33 分别填入邻近的3块区域。
最后计算
|A|=
1000/5
=200
|B|=
1000/6
=166
|C|=
1000/8
=125
根据这些结果,剩下的区域就不难填出来了,从而得到
|A∪B∪C|=400
所以,1~1000 中不能被5、6和8整除的数有600 个。
除了使用文氏图的方法外,对于集合的计数还有一条重要的定理———包含排斥原理。
下面介绍这个定理。
设
S
是有穷集,P1 和P2 分别表示两种性质,对于
S
中的任何一个元素x,只能处于以
下4种情况之一:只具有性质P1;只具有性质P2;具有P1 和P2 两种性质;两种性质都没
有。令A1 和A2 分别表示
S
中具有性质P1 和P2 的元素的集合。为使表达式简洁,对任
何集合B,用
B
代替~
|..A2|=|S|-(|A1|+|A2|)+|A1∩A2|
..B。由文氏图不难得到以下公式:
A1∩..
这就是包含排斥原理的一种简单形式。
如果涉及3条性质,包含排斥原理的公式则变成:
|..A2∩..
A1∩..A3|=|S|-(|A1|+|A2|+|A3|)+(|A1∩A2|+
|A1∩A3|+|A2∩A3|)-|A1∩A2∩A3|
一般来说,设
S
为有穷集,P1,P2,…,Pm
是
m
条性质。
S
中的任何一个元素
x
对于性
质Pi(i=1,2,…,m)具有或者不具有,两种情况必居其一。令Ai
表示
S
中具有性质Pi
的
元素构成的集合,那么包含排斥原理可以叙述为定理3.
2
。
S
中不具有性质P1,P2,…,Pm
的元素数
是
|..A2∩…∩
..
定理3.2
A1∩..Am|
=|S|-Σ(m) |Ai|+ Σ |Ai∩Aj|
i=1≤i<j≤m
Σ|(1) Ai∩Aj
∩Ak|+…+(-1)m|A1∩A2∩…∩Am|
1≤i<j<k≤m
证明等式左边是
S
中不具有性质P1,P2,…,Pm
的元素数。我们将要证明:对
S
中
的任何元素x,如果它不具有这
m
条性质,则对等式右边的贡献是1;如果
x
至少具有其中
的一条性质,则对等式右边的贡献是0。
设x 不具有性质P1,P2,…,Pm ,那么x.Ai,i=1,2,…,m 。对任何整数i 和j,1≤
i<j≤m,都有x.Ai∩Aj。对任何整数i、j 和k,1≤i<j<k≤m,都有x.Ai∩Aj∩Ak,…,
x.A1∩A2∩…∩Am 。但是x∈S,所以在等式右边的计数中它的贡献是
1-0+0-0+…+(-1)m ·0=1
设x 具有n 条性质,1≤n≤m ,则x 对|S|的贡献是1,即C0n ;对Σm
i=1|Ai|项的贡献是
C1n =n;对1≤iΣ<j≤m|Ai∩Aj|项的贡献是C2n ;……;对|A1∩A2∩…∩Am|项的贡献是Cm
n 。
所以,x 对等式右边计数的总贡献是
C0n -C1n +C2n -…+(-1)mCm
n (n≤m )
=C0n -C1n +C2n -…+(-1)nCnn
根据二项式定理不难得到上面式子的结果是0。■
推论 在S 中至少具有一条性质的元素数是
|A1∪A2∪…∪Am|
= Σm
i=1 |Ai|-1≤iΣ<j≤m|Ai∩Aj|+
1≤i<Σj<k≤m|Ai∩Aj∩Ak|-…+(-1)m +1|A1∩A2∩…∩Am|
证明 |A1∪A2∪…∪Am|
=|S|-|A1∪A2∪…∪Am|
=|S|-|..A1∩..A2∩…∩..Am|
将定理3.2的结果代入即可得证。■
考虑例3.10,由包含排斥原理可得
|..A1∩..A2∩..A3|
=|S|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+
|A2∩A3|)-|A1∩A2∩A3|
=1000-(200+166+125)+(33+25+41)-8
=600
这恰好与用文氏图所求得的结果是一致的。
例3.11 某班有25个学生,其中14人会打篮球,12人会打排球,6人会打篮球和排
球,5人会打篮球和网球,还有2人会打这3种球。而6个会打网球的人都会打另外一种球
(指篮球或排球),求不会打这3种球的人数。
解 设会打排球、网球、篮球的学生集合分别为A 、B 和C,则有
|A|=12, |B|=6, |C|=14, |S|=25,
|A ∩C|=6, |B∩C|=5, |A ∩B∩C|=2
现在求|A ∩B|。因为会打网球的人都会打另外一种球,即篮球或排球。而其中会打篮球
的有5人,那么另一个人肯定会打排球但不会打篮球。再加上会打3种球的2人,共有3人
会打排球和网球,即|A ∩B|=3。根据定理3.2有
|..A ∩..B ∩..C|=25-(12+6+14)+(3+6+5)-2=5
第3章 集合的基本概念和运算·65·
例3.12 一个班有50个学生,在第一次考试中有26人得5分,在第二次考试中有
21人得5分。如果两次考试中都没得5分的有17人,那么两次考试都得5分的有多
少人?解
1 设A 、B 分别表示在第一次和第二次考试中得5分的学生的集合,那么有
|S|=50, |A|=26, |B|=21, |..A ∩..B|=17
由包含排斥原理有
|..A ∩..B|=|S|-(|A|+|B|)+|A ∩B|
即
|A ∩B|=|..A ∩..B|-|S|+|A|+|B|
=17-50+26+21
=14
图 3-5
有14人两次考试都得5分。
解2 画出文氏图,如图3-5所示。因为首先要填入A ∩B 中
的人数正是题目所要求的,所以设它为x,然后填入其他区域中的数
字,并列出方程如下:
(26-x)+x+(21-x)+17=50
解得x=14。
例3.13 求欧拉函数的值。
欧拉函数. 是数论中的一个重要函数,在密码学中有着重要的应用。设n 是正整数,
.(n)表示{0,1,…,n-1}中与n 互素的数的个数。例如,.(12)=4,因为与12互素的数有
1,5,7,11。这里认为.(1)=1。下面利用包含排斥原理给出欧拉函数的计算公式。
给定正整数n,n=pα1 1pα2 2 …pαk
k 为n 的素因子分解式,令
Ai={x|0≤x<n-1且pi 整除x}, i=1,2,…,k
那么
.(n)=|..A1∩..A2∩…∩..Ak|
下面计算等式右边的各项
|Ai|=n
pi, i=1,2,…,k
|Ai∩Aj|= n
pipj , 1≤i<j≤n
.
|A1∩A2∩…∩Ak|= n
p1p2…pk
根据包含排斥原理
.(n)=|..A1∩..A2∩…∩..Ak|
=n- n
p1+n
p2+…+n
pk
.
è .
.
. ÷
+ n
p1p2+ n
p2p3+…+ n
pk-1pk
.
è .
.
. ÷
-…+
·66· 离散数学(第六版)
(-1)k n
p1p2…pk
=n 1-1 p1
.
è .
.
. ÷
1-1 p2
.
è .
.
. ÷
… 1-1 pk
.
è .
.
. ÷
例如,60=22×3×5,根据上述公式得
.(60)=601-12
.
è .
.
. ÷
1-13
.
è .
.
. ÷
1-15
.
è .
.
. ÷
=60×12
×23
×45
=16
小于60且与60互素的正整数有16个,它们是1,7,11,13,17,19,23,29,31,37,41,43,47,
49,53,59。
3.4 题例分析
例3.14~例3.17为选择题。
例3.14 设F 表示一年级大学生的集合,S 表示二年级大学生的集合,R 表示计算机
科学系学生的集合,M 表示数学系学生的集合,T 表示选修离散数学的学生的集合,L 表示
爱好文学的学生的集合,P 表示爱好体育运动的学生的集合,则下列各句子所对应的集合
表达式分别是什么?
(1)所有计算机科学系二年级的学生都选修离散数学。A
(2)数学系的学生或者爱好文学或者爱好体育运动。B
(3)数学系一年级的学生都没有选修离散数学。C
(4)只有一、二年级的学生才爱好体育运动。D
(5)除去数学系和计算机科学系二年级的学生外都不选修离散数学。E
供选择的答案
A、B、C、D、E:①T.(M ∪R)∩S;②R∩S.T;③(M ∩F)∩T=.;④ M .L∪P;
⑤P .F∪S;⑥S-(M ∪R).P 。
答案 A:②;B:④;C:③;D:⑤;E:①。
分析 (1)计算机系二年级学生的集合为R ∩S,选修离散数学的学生的集合为T ,前
者为后者的子集。
(2)数学系学生的集合为M ,爱好文学或爱好体育运动的学生的集合为L∪P ,前者为
后者的子集。
(3)数学系一年级学生的集合为M ∩F,选修离散数学的学生的集合为T ,这两个集合
不交。
(4)只有p 才q,这种句型的逻辑含义是如果q 则p。所以,这句话可解释为:爱好体
育运动的学生一定是一、二年级的学生。爱好体育运动的学生构成集合P ,一、二年级的学
生构成集合F∪S,前者是后者的子集。
(5)除去p 都不q,这种句型的逻辑含义可解释为如果q 则p。原来的句子就变成:选
修离散数学的学生都是数学系和计算机科学系二年级的学生。所以T .(M ∪R)∩S。
第3章 集合的基本概念和运算·67·
·68· 离散数学(第六版)
例3.15
设S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},
S5={3,5}。确定在以下条件下
X
可能与S1,S2,…,S5 中哪个集合相等。
(1)若X∩S5=.,则A。
(2)若X.S4 但
X
∩S2=.,则B。
(3)若X.S1 且
X
.S3,则C。
(4)若X-S3=.,则D。
(5)若X.S3 且
X
.S1,则E。
供选择的答案
A、B、C、D、E:①X=S2 或S5;②
X
=S4 或S5;③X=S1,S2 或S4;④
X
与其中任何
集合都不等;⑤X=S2;⑥X=S5;⑦
X
=S3 或S5;⑧
X
=S2 或S4。
答案A:⑤;B:⑥;C:③;D:⑦;E:④。
分析(1)和S5 不交的集合不含3和5,只能是S2。
(2)只有S4 和S5 是S4 的子集,但S4∩S2≠.,所以S5 满足要求。
(3)X.S3 意味着
X
中必含有偶数,S1、S2 和S4 中含有偶数并且都是S1 的子集。
(4)由X-S3=. 知
X
.S3,那么
X
可能是S3 或S5。
(5)由于S3.S1,所以
X
.S3.S1,与X.S1 矛盾。
X
与这5个集合中的任何一个都
不相等。
例3.16
对24 名科技人员进行掌握外语情况的调查。其统计资料如下:掌握英语、
日语、德语和法语的人数分别为13 、5、10 和9。其中同时掌握英语和日语的有2人。同时
掌握英语和法语,或者同时掌握英语和德语,或者同时掌握德语和法语两种语言的各有4
人。掌握日语的人既不懂法语也不懂德语。由上述资料,知道在这24 名科技人员中只掌握
一种语言的人数:掌握英语的有A人,掌握法语的有B人,掌握德语的有C人和掌握日语
的有D人。同时掌握英语、德语和法语3种语言的有E人。
供选择的答案
A、B、C、D、E:①0;②1;③2;④3;⑤4;⑥5;⑦6;⑧7;⑨8;⑩9 。
答案A:⑤;B:③;C:④;D:④;E:②。
分析解
1
文氏图法。
令A、B、C、
D
分别表示掌握英语、法语、德语、日语的人的集合。根据题意画出文氏图
如图3-6所示。设同时掌握3种语言的有
x
人,只掌握英语、
法语或德语一种语言的分别有y1、y2、y3 人。将x、y1、y2
和y3 填入图中相应的区域中,然后依次填入其他区域的
人数。
请看图3-6。由图列出方程组如下:
y1+2(4-x)+x+2=13 ①
图3-
6
y2+2(4-x)+x=9 ②
第3章集合的基本概念和运算·69·
y3+2(4-x)+x=10 ③
将式①、式②和式③相加得
y1+y2+y3+3(4-x)+x+5=24 ④
⑤-④ 得
y1+y2+y3+6(4-x)+3x+2=32 ⑤
3(4-x)+2x-3=8
解得
x=1
再代入式①、式②和式③,解得
y1=4,y2=2,y3=3
解
2
包含排斥原理法。
由题意,只掌握日语的有5-2=3人。因此掌握英语、法语或德语的有24-3=21 人。
先不考虑掌握日语的人。设A、B、
C
分别表示掌握英语、法语、德语的人的集合,由已知条
件有
|A∪B∪C|=21,|A|=13,|B|=9,|C|=10
|A∩B|=4,|A∩C|=4,|B∩C|=4
令|A∩B∩C|=x。由包含排斥原理有
|A∪B∪C|=(|A|+|B|+|C|)-(|A∩B|+|A∩C|+|B∩C|)+|A∩B∩C|
代入相应的数字解得|A∩B∩C|=1。从而得到
|A-(B∪C)|=|A|-(|A∩B|+|A∩C|)+|A∩B∩C|
=13-(4+4)+1
=6
因为这6人中还有2人掌握日语,所以只掌握英语的人数应该是6-2=4。同理求得
|B-(A∪C)|=9-(4+4)+1=2
|C-(A∪B)|=10-(4+4)+1=3
例3.17
设S、T、
M
是集合,图3-7给出5个文氏图。那么(a)、(b)、(c)、(d)和(e)图
的阴影部分的区域所代表的集合表达式分别是A、B、C、D、E。
图3-
7
·70· 离散数学(第六版)
供选择的答案
A、B、C、D、E:①(S∩
M
)-T;②S∪
M
;③(S∪
M
)-T;④(T..
M
)-S;
⑤S∩(T∪
M
);⑥(T∪
M
)-S;⑦T-(S∪
M
);⑧T-(S-
M
);
⑨(S-T)∩
M
;⑩(S∩
M
)∪(S-T)。
答案A:③;B:⑦;C:⑤;D:⑩;E:④。
分析可使用排除法。①是S∩
M
的子集,不是任何阴影区域的集合表达式。同理可
知②、⑥、⑧和⑨也不符合题意。剩下的5个集合表达式显然分别对应于5个文氏图。根据
每个表达式就不难找到相应的图了。
例3.18
设A、B、
C
为任意集合,判断下述命题是否恒真,如果恒真给出证明,否则举
出反例。
(1)A∪B=A∪C.B=C。
(2)A..B=A.B=. 。
(3)A∩(B-C)=(A∩B)-(A∩C)。
(4)(A∩B)∪(B-A)=B。
答案
(1)不是恒真。反例A={1,2},B={1},C={2}。
(2)恒真。证明如下:
假设B≠.,则存在x∈B。若x∈A,则x.
A
..B,与
A
..B=
A
矛盾。若x.A,则
x∈A..B,也与A..B=
A
矛盾。
(3)恒真。证明如下:
(A∩B)-(A∩C)=(A∩B)∩~(A∩C)=(A∩B)∩(~A∪~C)
=(A∩B∩~A)∪(A∩B∩~C)=.∪(A∩B∩~C)=A∩B∩~
C
=A∩(B∩~C)=A∩(B-C)
(4)恒真。证明如下:
(A∩B)∪(B-A)=(A∩B)∪(B∩~A)=B∩(A∪~A)=B∩E=
B
分析
(1)在集合等式两边进行相同的集合运算,得到的结果仍是等式。例如,由B=
C
可以
得到A∪B=
A
∪C、
A
∩
B
=
A
∩C、
A
-
B
=
A
-
C
等。但是逆过程不成立,即
A
∪
B
=
A∪
C
不能推出B=C。同样地,A∩B=A∩
C
或者A-B=A-
C
也不能推出B=C。这
说明集合的并、交和补运算不满足消去律。
(2)这个命题的逆命题显然为真。因此该命题可以强化成A..B=A.B=.,这说明
.是集合..运算的单位元。关于单位元的概念将在第9章叙述。
(2)、(3)和(4)涉及集合恒等式的证明。证明集合恒等式
P
=
Q
的主要方法有以
下3种。
方法
1
命题演算法,相当于证明两个方向的包含,具体书写规范是
任取x,然后证明
第3章集合的基本概念和运算·71·
x∈P.….x∈
Q
x∈Q.….x∈
P
有时某个方向的包含是显然的结果,那么只需证明其中的一个方向。而当以上两个方
向的推理互为逆过程时,可以将这两个过程合写成一个过程,即
x∈P.….x∈
Q
在这种情况下,必须保证推理的每步都是可逆的,即由左边可推出右边,同时由右边也
可以推出左边。
方法
2
恒等变形法。本题(3)与(4)的证明使用了这种方法。使用恒等变形法必须熟
悉集合恒等式和一些常用的结果,如A-B=A∩~
B
等。
例3.19
方法
3
反证法。(2)的证明使用了这种方法。
(1)A-B=
设
BA
。
、
B
为集合,试确定下列各式成立的充分必要条件。
(2)A-B=B-A。
(3)A∩B=A∪B。
答案(1)A=B=. 。
(2)A=B。
(3)A=B。
分析求解这类问题可能用到集合恒等式、不同集合之间的包含关系,以及文氏图等。
具体求解过程可以说明如下。
(1)由A-B=
B
得
(A∩~B)∩B=B∩
B
化简得B=. 。再将这个结果代入已知等式得A=. 。从而得到必要条件A=B=. 。
下面验证充分性。如果A=B=. 成立,则A-B=.=
B
也成立。
(2)充分性是显然的,下面验证必要性。由A-B=B-
A
得
(A-B)∪A=(B-A)∪
A
从而有A=A∪B,即B.A。同理可证A.B。
(3)充分性是显然的,下面验证必要性。由A∩B=A∪
B
得
A∪(A∩B)=A∪(A∪B)
化简得A=A∪B,从而有B.A。类似可以证明A.B。
习题
题3.~题3.题目要求从供选择的答案中选出应填入叙述中的
17是选择题,
内的正确
答案。
3.设
F
表示一年级大学生的集合,
M
表示数学专业学
1 S
表示二年级大学生的集合,
生的集合,
R
表示计算机专业学生的集合,
T
表示听离散数学课学生的集合,
G
表示星期一
·72· 离散数学(第六版)
晚上听音乐会的学生的集合,
H
表示星期一晚上很晚才睡觉的学生的集合,则下列各句子
所对应的集合表达式分别是什么?
(1)所有计算机专业二年级的学生在听离散数学课。A
(2)这些且只有这些听离散数学课的学生或者星期一晚上听音乐会的学生在星期一晚
上很晚才睡觉。B
(3)听离散数学课的学生都没听星期一晚上的音乐会。C
(4)听音乐会的只是大学一、二年级的学生。D
(5)除去数学专业和计算机专业以外的二年级学生都去听音乐会。E
供选择的答案
A、B、C、D、E:①T.G∪
H
;②G∪
H
.T;③S∩R.T;④
H
=G∪T;
⑤T∩G=.;⑥F∪S.G;⑦G.F∪S;⑧S-(R∪
M
).G;
⑨G.S-(R∩
M
)。
3.2
设
S
表示某人拥有的所有的树的集合,
M
,
N
,T,
P
.S,且
M
是珍贵的树的集
合,
N
是果树的集合,
T
是去年刚栽的树的集合,
P
是在果园中的树的集合。下面是3个前
提条件和两条结论。
前提(1)所有的珍贵的树都是去年栽的。
(2)所有的果树都在果园里。
(3)果园里没有去年栽的树
。
结论(1)所有的果树都是去年栽的
。
(2)没有一棵珍贵的树是果树。
则前提(1)、(2)、(3)和结论(1)的集合表达式分别为A、B、C、D。根据前提条件,两个结
论中正确的是E。
供选择的答案
A、B、C、D、E:①
N
.P;②T.
N
;③
M
.T;④
M
∩P=.;⑤P∩T=.;
⑥
N
.T;⑦
N
∩
M
=. 。
3.设S={.,{1},{2}}, 则
有
(13
)A∈S。
1,
(2)B.S。
(3)P(S)有
D。
C个元素。
(4)|S|
=
(5)E既是
S
的元素,又是
S
的子集
。
供选择的答案
A:①{1,2};②1;
B:③{{1,2}};④{1}
;
C、D:⑤3;⑥6;⑦7;⑧8;
第3章集合的基本概念和运算·73·
E:⑨{1};⑩. 。
3.设S、T、
M
为任意的集合,且S∩
M
=.。下面是一些集合表达式,每个表达式
4
与图3-8的某个文氏图的阴影区域相对应。请指明这种对应关系。
图3-
8
(1)S∩T∩
M
对应于A;
(2)~S∪T∪
M
对应于B;
(3)S∪(T∩
M
) 对应于C;
(4)(~S∩T)-
M
对应于D;
(5)~S∩~T∩
M
对应于E。
供选择的答案
A、B、D、a);②(c);④(e);⑥(h);⑨(
C、E:①(b);③(d);⑤(f);⑦(g);⑧(i)。
3.5
对60 人的调查表明,有25 人阅读《每周新闻》杂志,26 人阅读《时代》杂志,26 人
阅读《幸运》杂志,9人阅读《每周新闻》和《幸运》杂志,11 人阅读《每周新闻》和《时代》杂志,8
人阅读《时代》和《幸运》杂志,还有8人什么杂志也不阅读。那么阅读全部3种杂志的有A
人,只阅读《每周新闻》的有B人,只阅读《时代》杂志的有C人,只阅读《幸运》杂志的有D
人,只阅读一种杂志的有E人。
供选择的答案
A、B、C、D、E:①2;②3;③6;④8;⑤10;⑥12;⑦15;⑧28;⑨30;⑩31 。
3.6
1~300 的整数中,
(1)同时能被3、5和7这3个数整除的数有A个。
(2)不能被3、5,也不能被7整除的数有B个。
(3)可以被3整除,但不能被5和7整除的数有C个。
(4)可以被3或5整除,但不能被7整除的数有D个。
(5)只能被3、5和7中的一个数整除的数有E个。
供选择的答案
A、B、C、D、E:①2;②6;③56;④68;⑤80;⑥102;⑦120;⑧124;⑨138;⑩162 。
·74· 离散数学(第六版)
7
75 个学生去书店买语文、数学、英语课外书,每种书每个学生至多买1本。已知有
20 个学生每人买3本书,55 个学生每人至少买2本书。设每本书的价格都是1元,所有的
学生总共花费140 元。那么恰好买2本书的有A个学生,至少买2本书的学生花费B元,
买1本书的有C个学生,至少买1本书的有D个学生,没买书的有E个学生。
3.
供选择的答案
A、B、C、D、E:①10;②15;③30;④35;⑤40;⑥55;⑦60;⑧65;⑨130;⑩140 。
3.设S、T、判断下列命题的真假。
8 M
为任意集合,
(1).是.的子集。
(2)如果S∪T=S∪
M
,则T=
M
。
(3)如果S-T=.,则S=T。
(4)如果~S∪T=E,则S.T
。
(5)S..S=S
。
3.9
S1=.,S2={.},S3=P({.}),S4=P(.), 判断以下命题的真假
。
(1)S2∈S4
。
(2)S1.S3
。
(3)S4.S2
。
(4)S4∈S3
。
(5)S2=S1
。
3.用列元素法表示以下集合。
10
(1)A={x|x∈N∧x2≤7 }
。
(2)A={x|x∈N∧|3-x|<3 }
。
(3)A={x|x∈R∧(x+1)2≤0 }
。
(4)A={<x,x,x+y≤4 }
。
11
y>|y∈N∧
ab、
、
3.求使得以下集合等式成立时,、cd
应该满足的条件
。
(1){a,c}
。
a,b}={b,
(2){b,={b}
。
a,a}a,
(3){b,={d}}
。
a,{c}}a,
{
(4){{c}}b}}
。
b},{={
{
(5){{b,{={{.}}
。
a,
a,.},c}}
3.设ab、、指
12
、cd
代表不同的元素。说明以下集合
A
和
B
之间成立哪种关系(
A.B,B.A,A=B,A.
B
且B.A)。
(1)A={{c},{B={{b},{}}。
b},{d}}
,
(2)A={{b},{B={
{
a,a,
c
a,b},.},b}}
。
(3)A={x|x∈N∧x2>4},B={x|x∈N∧x>2 }
。
(b∈Z},y∈R}
。
4)A={ax+b|x∈R∧a,B={x+y|x,
(5)A={x|x∈R∧x2+x-2=0},B={y|y∈Q∧y2+y-2=0}
。
第3章集合的基本概念和运算·75·
(6)A={x|x∈R∧x2≤2},B={x|x∈R∧2x3-5x2+4x=1}。
3.计算A∪B、A∩B、A-B、A..B。
13
(1)A={{b},B={
ad
,
}。
a,
a,c},c,
(2)A={{b}},c},{B={{c,
{
a,{c,{b}},b},b}}
。
(3)A={x|x∈N∧x<3},B={x|x∈N∧x≥2 }
。
(4)A={x|x∈R∧x<1},B={x|x∈Z∧x<1 }
。
(5)A={x|x∈Z∧x<0},B={x|x∈Z∧x≥2 }
。
3.14
计算幂集P(A)
。
(1)A={.}
。
(2)A={{1},1}
。
(3)A=P({1,2})
。
(4)A={{1,1},{2,1},{1,2,1}}
。
(5)A={x|x∈R∧x3-2x2-x+2=0}
。
3.请用文氏图表示以下集合。
15
(1)~A∪(B∩C)
。
(2)(A..B)-C
。
(3)(A∩~B)∪(C-B)
。
(4)A∪(C∩~B)
。
反例
3
。
.设A、B、
C
代表任意集合,判断以下等式是否恒真。如果不为恒真请举一
16
(1)(A∪B)-C=(A-C)∪(B-C)
。
(2)A-(B-C)=(A-B)∪(A∩C)
。
(3)A-(B∪C)=(A-B)-C
。
(4)(A∪B∪C)-(A∪B)=C
。
(5)(A∪B)-(B∪C)=A-C
。
(6)A∩(B..C)=(A∩B)..(A∩C)
。
3.17
设A、B、C、
D
代表任意集合,判断以下命题是否恒真。如果不是,请举一
反例
(
。
1)A.B∧C.D.A∩C.B∩D。
(2)A.B∧C.D.A-D.B-C。
(3)A.B.B=A∪(B-A)。
(4)A-B=B-A.A=B。
3.设|A|=3,B)|64,
A
∪B)|=256 。求|B|、|
A
-B|、
18
|P(=|
P
(|
A
∩B|、
|A..
3B.
|。
求11000000(包括1和1000000 在内)中有多少个整数既不是完全平方数,
19
~
也不是完全立方数?
3.20 错位排列的计数问题。设i1i2…in 是1,2,…,n 这n 个数的排列。如果排在第i
位的数都不等于i,其中i=1,2,…,n,则称这个排列为错位排列。如1,2,3,4的错位排列
有2143,2341,2413,3142,3412,3421,4123,4312,4321,一共9个错位排列,记作D4=9。
将n 个数的错位排列个数记作Dn ,证明Dn =n! 1-1
1!+1
2!-…+(-1)n 1 n!
é
. êê
ù
. úú
。
3.21 求不超过120的素数个数。
·76· 离散数学(第六版)