Microsoft PowerPoint - ç¬¬ä¸›ç«€ éłƒå’‹è®º-2nd [å–¼å®¹æ¨¡å¼‘]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ç¬¬ä¸›ç«€ éłƒå’‹è®º-2nd [å–¼å®¹æ¨¡å¼‘]"

半都
7 years ago
Views:

1 离散数学大连理工大学软件学院陈志奎博士教授博士生导师办公室 : 综合楼 405,Tel: 实验室 : 综合楼一楼, 教学楼 A502/C109, Mobile: zkchen@dlut.edu.cn zkchen00@hotmail.com QQ: /9/28 1/37

2 回顾集合的定义集合的描述内涵与外延集合的基数集合间的关系相等包含真包含全集补集子集幂集运算 2/49

3 一相交运算 3.2 集合的运算定义 : 由集合 A 和 B 的所有公共元素所组成的集合, 称为集合 A 和 B 的交集记作 A B A B { x x A x B} 例如 : 设 A={a,b,c,d}, B={d,f,a}, C={e,f,g} 则 A B { a, d} B C { f } A C 可以看出 A B A, A B B A A B B 2016/9/28 3/40

4 一相交运算设 A B, 求证 A C B C. 证明 : 若 x A 则 x B, 对任一 x A C, 则 x A 且, 即 x C 且 x B, 故 x C, 因此 x B C A C B C 集合的交运算具有如下性质 : ( a) A A A A ( b) A ( c) A E A ( d) A B B A ( e) ( A B) C A ( B C) A B B 2016/9/28 4/40

5 一相交运算 2016/9/28 试证明 ( A B) C A ( B C). 证明 :( A B) C { x x A B x C} { x x A x B x C} { x x A ( x B x C)} { x x A x B C)} { x x A x B C)} 类推至多个集合的情况, 集合的交运算仍满足结合律假设有 n 个集合 A 1,A 2, A n, 那么这些集合的交集可表示为 : P A A A n i1 1 2 A i n 5/40

6 二联合运算 ( 集合的并 ) 定义 : 由集合 A 和 B 的所有元素组成的集合称为 A 和 B 的并集, 记作 A B A B { x x A x B} 例如设 A={a,b,c}, B={c,d,f}, C={b,e} 那么 A B { a, b, c, d, f } A C { a, b, c, e} B C { b, c, d, e, f } A B 可以看出 A A B, B A B A B 2016/9/28 6/40

7 二集合的并集合的并运算具有如下性质 : ( a) A A A ( b) A E E ( c) A A ( d) A B B A ( e) ( A B) C A ( B C) 注意 : 假设有 n 个集合 A 1,A 2, A n, 那么这些集合的并集可表示为 : W A A A n i1 1 2 A i n 2016/9/28 7/40

8 二集合的并例 1: 假设 A B, C D, 则 A C B D. 证明 : 对任意 x A C, 有 x A x C, 若 x A, 由 A B可得 x B, 故 x B D; 若 x C, 由 C D可得 x D, 故 x B D 因此, A C B D 2016/9/28 8/40

9 二集合的并定理 : 设 A, B, C为三个集合, 那么 ( a) A ( B C) ( A B) ( A C) ( b) 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 A x C) x A B x A C x ( A B) ( A C) 由 x 的任意性可知 (a) 成立同理可以证明 (b) 2016/9/28 9/40

10 二集合的并定理 : 设 A, B为任意两个集合, 那么 ( a) A ( A B) A ( b) A ( A B) A 证明 :( a) A ( A B) ( A E) ( A B) A ( E B) A E A 证明 :( b) A ( A B) ( A A) ( A B) A ( A B) A 2016/9/28 10/40

11 二集合的并定理 3.2 3: A B, 当且仅当 A B B或 A B A 证明 :(1) 若 A B, 对任意 x A, 必有 x B; 对任意 x A B, 则 x A或 x B, 即 x B, 所以 A B B 又 B A B, 故得到 A B B (2) 若 A B B, 因为 A A B, 故 A B. 同理可证明 A B, 当且仅当 A B A. 2016/9/28 11/40

12 关于交集并集的例子老师讲完交集并集的概念之后, 提问学生 : (1) 设 A={x x 是参加百米赛跑的同学 }, B={x x 是参加跳高比赛的同学 }, 求 A B. (2) 设 A={x x 是红星农场的汽车 },B={x x 是红星农场的拖拉机 }, 求 A B. 一学生答道 : (1) 中 A B={x x 是参加百米障碍赛的同学 }. (2) 中 A B={x x 是红星农场的联合收割机 }. 2016/9/28 12/40

13 三差分运算集合的补定义设A,B是两个集合所有属于A而不属于B 的元素组成的集合称为A和B的差集或B对A的相对补集记作A- B A B {x x A x B} 绝对补集 B对E的相对补集叫做绝对补集简称补集记作~ B A B ~A A A-B 13/49

14 三差分运算 ( 集合的补 ) 例 : 设 A 是小于 10 的素数集合,B 是奇数集合, 求 A-B 解 :A={1,2,3,5,7} A-B={2} B={1,3,5,7,9} 例 : 设 U=I (I 是整数集合 ) A { i i I, i 0} 解 : U A { i i I, i 0} A U 14/49

15 三差分运算集合的补集合的差分运算还具有如下性质 (a ) ~ (~ A) A (b) ~ E (c) A ~ A E ~A A (d ) A ~ A 15/49

16 三差分运算 ( 集合的补 ) 定理 3.2-4: 设 A,B 为任意两个集合, 则下列关系式成立 ( a) ~ ( A B) ~ A ~ B ( b) ~ ( A B) ~ A ~ B 证明 :(a) ~ ( A B) { x x ~ ( A B)} { x x A B} { x x A B} { x ( x A x B)} { x x A x B} { x x ~ A x ~ B} { x x ~ A ~ B} ~ A ~ B 16/49

17 三差分运算 ( 集合的补 ) 定理 3.2-5: 设 A,B 为任意两个集合, 则下列关系式成立 ( a) A B A ~ B ( b) A B A ( A B) 证明 : (b) 设 x A B, 即 x A 且 x B, 因为 x B 则必有 x A B, 故有 x A ( A B), 即为 A B A ( A B) 设 x A ( A B), 则 x A 且 x ( A B), 即 x A且 x ~ A 或者 x~ B, 显然只能 x A 与 x~ B成立即 x A B A ( A B) A B 17/49

18 三差分运算 ( 集合的补 ) 定理 3.2-6: 设 A,B,C 为任意三个集合, 则下列关系式成立 A ( B C) ( A B) ( A C) 证 : A ( B C) A ( B ~ C) A B ~ C 又 ( 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) ( A C) 18/49

19 三差分运算 ( 集合的补 ) 定理 3.2 7: 设 A, B是任意两个集合, 若 A B, 则 ( a) ~ B ~ A ( b) ( B A) A B 证 :(a) 若 x A, 则 x B; 因此, 若 x B, 必有 x A 即若 x ~ B, 则 x ~ A 即 ~ B ~ A 证 :( b) ( B A) A ( B ~ A) A ( B A) (~ A A) ( B A) E B A 因为 A B, 所以 B A B ( b) 得证 19/49

20 四对称差分运算定义 : 设 A B 为任意两个集合属于 A 但不属于 B 的所有元素和属于 B 但不属于 A 的所有元素的并集, 称为 A 和 B 的对称差集, 记作 A B A B ( A B) ( B A) ( A ~ B) ( B ~ A) ( A B) ( A B) 例如 :A={1,2,3} B={3,2,4} 则 A B ={1,4} A B E 20/49

21 四对称差分运算集合的对称差分运算满足如下性质 : ( a) A B B A ( b) A A ( c) A A ( d) A B ( A ~ B) ( B ~ A) ( e) ( A B) C A ( B C) E A B 21/49

22 四对称差分运算求证 ( A B) C A ( B C) 证 :( A B) C (( A B) ~ C) (~ ( A B) C) ((( A ~ B) (~ A B)) ~ C) (~ (( A ~ B) (~ A B)) C) A ~ B ~ C ~ A B ~ C (~ A B) ( A ~ B) C 由于 (~ A B) ( A ~ B) C ((~ A B) A) ((~ A B) ~ B) C ((~ A A) ( A B) (~ A ~ B) ( B ~ B)) C ( ( A B) (~ A ~ B) ) C ( A B C) (~ A ~ B C) 22/49

23 四对称差分运算所以,( A B) C ( A ~ B ~ C) (~ A B ~ C) (~ A ~ B C) (~ A ~ B C) 又因为, A ( B C) ( A ~ ( B C)) (~ A ( B C)) ( A ~ (( B ~ C) (~ B C))) (~ A (( B ~ C) (~ B C))) ( A (~ B C) ( B ~ C)) (~ A B ~ C ~ A ~ B C) A ~ B B A ~ B ~ C A B C A C ~ C ~ A B ~ C ~ A ~ B C A ~ B ~ C A B C ~ A B ~ C ~ A ~ B C 得证 ( A B) C A ( B C) 23/49

24 四对称差分运算上述证明结果可以通过以下文氏图清楚看出 B A E C A B B A E C ( A B) C A ( B C ) B C 24/49

25 S A B A 1 S A B B 2 S A A B 3 S B A B 4 S A B A 集合定律 S A B A B S7 A B B A S8 A B B A S9 A B B A 交换律 S10 A ( B C) ( A B) C S11 ( A B) C A ( B C) S12 ( A B) C A ( B C) 结合律 25/49

26 集合定律 S13 A ( B C) ( A B) ( A C) 分配律 S14 A ( B C) ( A B) ( A C) S ~~ A A 双重否定律 S16 ~ ( A B) ~ A ~ B 德摩根律 S17 ~ ( A B) ~ A ~ B S18 A A A 等幂律 S19 A A A S20 A ~ A 补余律 S21 A ~ A E S22 A E A S23 A A 同一律 S24 A A S25 A A 26/49

27 集合定律 S26 A 零律 S27 A E E S28 A ( A B) A S29 A ( A B) A S ~ E S ~ E S A A S A ( B A) S A ( B A) A B 吸收律 S A ( B C) ( A B) ( A C) 27/49

28 证明 : (39) 转化为假设 3.3 集合定律 S A ( B C) ( A B) ( A C) S A B A ~ B S A B ( A ~ B) (~ A B) S ( A B ) ( A ) ( B ) S ( A B ) ( A ) ( B ) A B 为假为假, 证明由 ( A ) ( B ) 为假可知, A 和 B 均为假, 即并且为真, 也就是为真, 使得 ( A ) ( B ) A B A B A B 为假 28/49

29 3.4 包含排斥原理集合的运算, 可用于有限个元素的技术问题集合的基数 : 集合所含元素的个数集合 A 的基数用 A 或 #A 表示设 A 1,A 2 是有限集合, 用 A 1, A 2 分别表示它们的基数, 那么可以推出 : A A A A A A min( A, A ) A A A A A A A A 2 A A /49

30 3.4 包含排斥原理定理 3.4-1: 设 A 1,A 2 是有限集合, A 1, A 2 为其基数, 则 A A A A A A 证 :(1) 当 A和 A 不相交, 即 A A 时, A A A A (2) 当 A A 1 2 A A A A , 那么 A A ~ A A A A ~ A A A A 所以 A A A ~ A ~ A A 2 A A 由于 A ~ A ~ A A A A A A 因此 A A A A A A /49

31 3.4 包含排斥原理例 3.4.1: 假设在 10 名青年中有 5 名是工人,7 名是学生, 其中兼具有工人与学生双重身份的青年有三名, 问既不是工人又不是学生的青年有几名? 解 : 设工人的集合为 W, 学生的集合为 S, 则根据题设应有 : W 5, S 7, W S 3, 又因为 ~ W ~ S W S 10, ~ W ~ S 10 W S 10 ( W S W S ) 10 (5 7 3) 1 因此既不是工人又不是学生的青年有 1 人则 31/49

32 3.4 包含排斥原理包含排斥原理在三个有限集和上的推广 : A A A A A A ( A A A A A A ) A A A /49

33 例求 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 整除 } 用 P 表示有穷集 P 中的元素数, x 表示小于等于 x 的最大整数, lcm( x1, x2,, x n ) 表示 x1, x2,, xn的最小公倍数, 则有 33/49

34 A 1000 / B 1000 / C 1000 / 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 根据包含排斥原理, 所求的元素数为 ~ A ~ B ~ C S ( A B C ) ( A B A C B C ) A B C 1000 ( ) ( ) /49

35 3.4 包含排斥原理例 3.4.3: 某工厂装配 30 辆汽车, 可供选择的设备是收音机空气调节器和对讲机已知其中 15 辆汽车有收音机 8 辆有空气调节器,6 辆有对讲机, 而且其中有 3 辆这三种设备都有我们希望知道有几辆汽车没有提供任何设备解 : 设 A 1,A 2 和 A 3 分别表示配有收音机空气调节器和对讲机的汽车集合, 因此由题设知 A 15, A 8, A 6, A A A A A A A A 3 因为得 A A A A A A A A A A A A A A A A A A A /49

36 3.4 包含排斥原理把包含排斥原理推广到 n 个集合定理 3.4-2: 设 A 1,A 2,,A n 为 n 个有限集合, 它们的基数分别为 A 1, A 2,, A n, 可得 : A A A A A A 1 2 n n i i j i1 1i jn n1 Ai Aj Ak... ( 1) A1 A2... An 1i jkn 36/49

37 证明 : 设 S 为全集, 由德摩根定律可得 ~ A ~ A ~ A ~ ( A A A ) 1 2 n 1 2 因此, ~ A~ A ~ A ~( A A A ) 1 2 n 1 2 S A A A 1 2 由此, 原定理可变为 n n n A A A 1 2 n A A A i i j i1 1 i j n A A A ( 1) A A A 1 i j k n n n1 i j k 1 2 n 37/49

38 应用数学归纳法对上式进行证明, 当 n=2 时, 证明若, 有, 则若 A A, 有于是 A1 A2 A1 A1 A2, 则 A A A A A A A2 A1 A2 A1 A2 A A A A A A A A ( A A ) ( A ~ A ) A A A ~ A 成立 38/49

39 A A 1 2 ( A A ) ( A ~ A ) A (( A A ) A ) ( A ~ A ) A ( A ~ A ) A A ~ A A A A A 因此当 n=2 时, 假设 A A A A A A 成立 39/49

40 A A A 1 2 n A A A i i j i1 1 i j n A A A ( 1) A A A 1 i j k n n m1 i j k 1 2 n 成立, 则, A A A 1 2 n1 ( A A A ) A 1 2 n n1 A A A A ( A A A ) A 1 2 n n1 1 2 n n1 40/49

41 A A A A ( A A ) ( A A ) ( A A ) n 1 2 n n1 1 n1 2 n1 n n1 A A A i i j i1 1 i j n A A A ( 1) A A A 1 i j k n n1 i j k 1 2 n A ( A A A A A n1 i n1 i j n1 i1 1 i j n A A A A ( 1) A A A A ) 1 i j k n n1 A i i1 1 i j n1 n 1 i j k n1 n1 i j k n1 1 2 n n1 A i A j A A A ( 1) A A A n i j k 1 2 n1 41/49

42 因此定理得证 42/49

43 3.4 包含排斥原理例 3.4.4: 求 1 到 250 之间能被 2,3,5 和 7 中任何一个整除的整数个数解 : 设 A 1 表示 1 到 250 之间能被 2 整除的整数集合, A 2 表示能被 3 整除的整数集合,A 3 表示能被 5 整除的整数集合,A 4 表示能被 7 整除的整数集合 x 表示小于或等于 x 的最大整数 A1 125 A A A4 35 A1 A A1 A3 25 A1 A /49

44 250 A A 包含排斥原理 A A A3 A4 7 A1 A2 A A1 A3 A4 3 A2 A3 A A1 A2 A3 A 于是有 A A A A A1 A2 A /49

45 例 3.4.5: 某系有 100 个学生至少要学法德英三种语言中的一种现在这 100 个学生中有 42 人学法语,45 人学德语,65 人学英语,15 人学法语和德语,20 人学法语和英语,25 人学德语和英语问同时学三种语言的有多少? 仅学英语的有多少? 45/49

46 解 : 令 A,B,C 分别表示学法语德语英语学生的集合则 A =42, B =45, C =65, A B =15, A C =20, B C =2 5, A B C =100 由容斥原理得 : A B C =( A + B + C )-( A B + A C + B C )+ A B C 所以 A B C = A B C -( A + B + C )+( A B + A C + B C )=8 仅学英语的人数为 : C - A C - B C + A B C =28 46/49

47 例求欧拉函数的值欧拉函数 ( n) 表示 {0,1,, n 1} 中与 n 互素的数的个数例如 (12) 4, 因为与 12 互素的数有 1,5,7,11 下面利用包含排斥原理给出欧拉函数的计算公式解 : 给定正整数 n, 因子分解式, 令 a1 a2 a n p k 1 p2 p k 为 n 的素 A { x 0 x n 1 p 整除 x} i i 那么 ( n) ~ A1 ~ A2 ~ A k 47/49

48 下面计算等式右边的各项, n Ai, i 1, 2,, k p i n Ai A j,1 i j k p p 根据包含排斥原理 ( n) ~ A ~ A ~ A i 1 2 j n n n n n n k n n ( 1) p p p p p p p p p p p p 1 2 k k1 k 1 2 k n1 1 1 p p p 1 2 k 例如, k (1 2 ) /49

49 P,63: 作业 10,11,14(2),15, 16(1,3),17(2,4),18(1,3,5,7,9),19,20(2,4,6, 8,10), /49

Microsoft PowerPoint - chapter ppt

Microsoft PowerPoint - chapter ppt 第 3 讲集合的概念与运算 1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图容斥原理 2005-7-5 集合论与图论第 3 讲 1 集合论 (set theory) 十九世纪数学最伟大成就之一集合论体系朴素 (naive) 集合论公理 (axiomatic) 集合论创始人康托 (Cantor) Georg Ferdinand Philip Cantor 1845 ~