3-3-1 集合的基本概念与运算

复习思考题7
? A、B、C为任意集合，判断下列等式或命 题是否恒真，若不为恒真，请举一反例. ① (A ? B )－ (B ? C ) = A － C ② A ? B ? B = A ? (B － A ) ? 设A、B、C为任意集合，寻找下列等式成 立的充要条件。 ① A?B=A ② A?B=A ③ (A － B ) ? (A － C ) = A

>第3章 集合的基本概念和运算
3.1 集合的基本概念 3.2 集合的基本运算 3.3 集合中元素的计数

3.3 集合中元素的计数
? 集合的基数与有穷集合
? 集合 A 的基数——集合A中的元素数，记作 cardA ? 有穷集 A cardA=|A|=n，n为自然数.

? 集合基本运算的基数
? ? ? ? |A ? B| |A ? B| |A ─ B| |A ? B| ≤ ≤ ≥ = |A| + |B| min(|A| , |B|) |A| ─ |B| |A| + |B|─ 2| A?B|

不属于三个集合的元素的计数
设论域为S，则同时不属于集合A，B和C的

元素为：

| A ? B ? C | =|S|－| A?B ?C |
| A? B ? C |
= |A| +|B| + |C|

─ | A?B| ─ | A?C| ─| B?C|
+| A?B ?C |

包含排斥原理
定理 设 S 为有穷集，P1, P2, …, Pm 是 m 种性质，
Ai 是 S 中具有性质 Pi 的元素构成的子集，i=1, 2, …, m.则 S 中不具有性质 P1, P2, …, Pm 的元素数为

| A1 ? A2 ? ... ? Am | =| S | ?

?| A | ? ?| A ? A
i i i =1 1? i ? j ? m

m

j

|?

1? i ? j ? k ? m

?| A ? A
i

j

? Ak | ?...

? ( ?1) m | A1 ? A2 ? ... ? Am |

| A1 ? A2 ? ... ? Am | =| S | ?

包含排斥原理的证明
i j

?| A | ? ?| A ? A
i i =1 1? i ? j ? m

m

|?

1? i ? j ? k ? m

?| A ? A
i

j

? Ak | ?...

? ( ?1) m | A1 ? A2 ? ... ? Am |

证明要点：任何元素 x，如果不具有任何性质，则对等 式右边计数贡献为１，否则为０。

证：设 x 不具有性质 P1、P2、 … 、 Pm , x?Ai , i = 1, 2, … , m x?Ai?Aj , 1? i < j ? m … x?A1?A2?…?Am , x 对右边计数贡献为 1 ? 0 + 0 ? 0 + … + (?1)m · 0=1

包含排斥原理的证明 = | S | ?? | A | ? ?
m i =1 i

| A1 ? A2 ? ... ? Am |

1?i ? j ? m

| Ai ? A j |

设 x具有 n 条性质，1 ? n ? m x 对 |S| 贡献为 1
x对 x

?

1?i ? j ? k ? m

?

| Ai ? Aj ? Ak | ?...

? 对 ?| A ? A
i =1

m

| Ai | 贡献为 C1 n
i j | 贡献为

? (?1) m | A1 ? A2 ? ... ? Am |

C

…. m x 对 | A1?A2?…?Am| 贡献为 Cn x 对右边计数贡献为 n
i =0

1? i ? j ? m

2 n

1 2 m i 1 ? Cn ? Cn ? ... ? (?1)m Cn = ? (?1)n ?i Cn

= [1 ? (?1)] = 0
n

包含排斥原理的推论
S中至少具有一条性质的元素数为
| A1 ? A2 ? ...? Am | =

?| A | ? ?| A ? A
i i i =1 1? i ? j ? m

m

j

|?

1? i ? j ? k ? m

?| A ? A
i

j

? Ak | ?...

? ( ?1) m ?1 | A1 ? A2 ? ...? Am |

证明:

| A1 ? A2 ? ... ? Am |

= | S | ? | A1 ? A2 ?... ? Am | = | S | ? | A1 ? A2 ?... ? Am | 将定理 1 代入即可

[P65例3.11]例题
? 某班有25名学生，14人会打篮球，12人会打排球， 6人会打篮球和排球，5人会打篮球和网球，还有 2人会打这3种球。而6个会打网球的人都会打另 一种球(指篮球或排球)，求不会打这3种球的人数。 ? 解：设A、B和C分别表示会打排球、网球和篮球 的学生集合， 则 |A|=12，|B|=6，|C|=14， 12 6 |S|=25， |A?B?C|=2 1 网球 排球 |A?B|=3 |A?C|=6，|B?C|=5，
| A ? B ? C | = | S | ?(| A | ? | B | ? | C |) ?(| A ? B | ? | B ? C | ? | C ? A |)? | A ? B ? C |
4 2
篮球

3

=25-(12+6+14)+(6+5+3)-2 = 5

14

25

应用举例2
例：求1到1000之间（包含1和1000在内）既不能 被 5 和6 整除，也不能被 8 整除的数有多少个？

解：S ={ x | x?Z, 1? x ?1000 },
如下定义 S 的 3 个子集 A, B, C： A ={ x | x?S, 5 | x }， B ={ x | x?S, 6 | x }， C ={ x | x?S, 8 | x }
利用下面公式求

| A ? B ? C | = | S | ?(| A | ? | B | ? | C |) ?(| A ? B | ? | B ? C | ? | C ? A |)? | A ? B ? C |

例：求1到1000之间（包含1和1000在内）既不能 被 5 和6 整除，也不能被 8 整除的数有多少个？ 对上述子集计数：|S|=1000,
|A?B?C| = ?1000/120? =8, |A?B| = ?1000/30? =33, |A?C| = ?1000/40? =25, |B?C| = ?1000/24? =41, |A| = ?1000/5? =200, |B| = ?1000/6?=166， |C| = ?1000/8? =125,

| A ? B ? C | = | S | ?(| A | ? | B | ? | C |) ?(| A ? B | ? | B ? C | ? | C ? A |)? | A ? B ? C |

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

[P68]例3.16——文氏图法
对24名科技人员掌握外语情况调查结果如下—— 每人至少会1门外语. 英语：13； 日语：5； 德语：10； 法语：9 英日：2; 英德：4； 英法：4； 法德：4 会日语的不会法语、德语 求：只会 1 种语言人数，会 3 种语言人数
英语

解：设同时会3种语言的有x人

法语

y2 只会英、法或德语1种语言 x 分别有y1、y2、y3人 4-x 会英语的人数: x+2(4-x)+y1+2=13 会法语的人数: x+2(4-x)+y2=9 德语 y 3 会德语的人数: x+2(4-x)+y3=10 总人数为: x+3(4-x)+y1+y2+y3+5=24

4-x

y1
2 4-x

3
日语

[P68]例3.16——文氏图法
对24名科技人员掌握外语情况调查结果如下—— 每人至少会1门外语. 英语：13； 日语：5； 德语：10； 法语：9 英日：2; 英德：4； 英法：4； 法德：4 会日语的不会法语、德语 求：只会 1 种语言人数，会 3 种语言人数 x+2(4-x)+y1+2=13 x+2(4-x)+y2=9 x+2(4-x)+y3=10 x+3(4-x)+y1+y2+y3+5=24

x=1, y1=4, y2=2, y3=3
3x+6(4-x)+y1+y2+y3+2=32

[P68]例3.16——包含排斥原理法
对24名科技人员掌握外语情况调查结果如下—— 每人至少会1门外语. 英语：13； 日语：5； 德语：10； 法语：9 英日：2; 英德：4； 英法：4； 法德：4 会日语的不会法语、德语 解：(1) 只会日语的人：5 – 2 = 3 英语 日语 法语 |A ? B ? C| = 24–3 = 21 A 2 3 B (2) 由|A| =13，|B| = 9，|C|=10 1 |A?B| = |A?C| = |B?C|=4 德语 和包含排斥原理的推论得： C |A?B ?C |=|A|+|B|+|C| –(|A?B|+|A?C|+|B?C|)+|A?B?C| 代入得： 21= 13+9+10–( 4+4+4) +|A?B?C| 得会3种语言的人有：|A?B?C|= 1
求：只会 1 种语言人数，会 3 种语言人数

[P68]例3.16——包含排斥原理法
对24名科技人员掌握外语情况调查结果如下—— 每人至少会1门外语. 英语：13； 日语：5； 德语：10； 法语：9 英日：2; 英德：4； 英法：4； 法德：4 会日语的不会法语、德语
求：只会 1 种语言人数，会 3 种语言人数 英语 日语 (3) 只会英语的人： 法语 A 2 3 |A-B?C| –2 B 1 =|A| – (|A?B|+|A?C|)+|A?B?C| –2 =13- 4- 4 +1 – 2 = 4 德语 (5) 只会法语的人： C |B-A?C|=|B|-(|B?A|+|B?C|)+|A?B?C|= 9- 4- 4+1 = 2 (4) 只会德语的人： |C-A?B|=|C|-(|C?A|+|C?B|)+|A?B?C|=10- 4- 4+1= 3

[P66]例3.13——求欧拉函数的值
? 欧拉函数： ?(n)
? 表示{0,1,…,n?1}中与n互素的数的个数.

? 规定：?(1) = 1

? 例：?(12)=4，与12互素的数有1, 5, 7, 11.
? 解： n 的素因子分解式

n = p1 p2 ... pk

?1

?2

?k

Ai ={ x | 0?x<n?1且 pi 整除 x }
?(n) =| A1 ? A2 ? ... ? Ak |

[P66]例3.13——求欧拉函数的值
n 1 1 1 | Ai |= , i = 1, 2,..., k ? (n) = n(1 ? )(1 ? )...(1 ? ) pi p1 p2 pk n | Ai ? Aj |= , 1? i ? j ? n ?k ?1 ?2 p p ... n = p1 p2 ... pk i j

n |A1 ? A2 ? ... ? Ak |= p1 p2 ... pk
?(n) =| A1 ? A2 ?... ? Ak |

n n n n n n = n?( ? ? ... ? ) ? ( ? ? ... ? ) p1 p2 pk p1 p2 p1 p3 pk ?1 pk n ? ... ? (?1) p1 p2 ... pk 1 1 1 = n(1 ? )(1 ? )...(1 ? ) p1 p2 pk
k

欧拉函数实例
? 与 60 互素的正整 数有 16 个：

1,

7, 11, 13, 17, 19, 23, 29,

31, 37, 41, 43, 47, 49, 53, 59.

60 = 2 ? 3 ? 5
2

1 1 1 ? (60) = 60(1 ? )(1 ? )(1 ? ) 2 3 5 1 2 4 = 60 ? ? ? = 16 2 3 5