复习思考题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,如果不具有任何性质,则对等 式右边计数贡献为1,否则为0。
证:设 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
文档资料共享网 nexoncn.com
copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com