Microsoft PowerPoint - chapter ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - chapter ppt"

糟咎
7 years ago
Views:

1 第 3 讲集合的概念与运算 1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图容斥原理集合论与图论第 3 讲 1

2 集合论 (set theory) 十九世纪数学最伟大成就之一集合论体系朴素 (naive) 集合论公理 (axiomatic) 集合论创始人康托 (Cantor) Georg Ferdinand Philip Cantor 1845 ~ 1918 德国数学家, 集合论创始人集合论与图论第 3 讲 2

3 什么是集合 (set) 集合 : 不能精确定义一些对象的整体就构成集合, 这些对象称为元素 (element) 或成员 (member) 用大写英文字母,B,C, 表示集合用小写英文字母 a,b,c, 表示元素 a : 表示 a 是的元素, 读作 a 属于 a : 表示 a 不是的元素, 读作 a 不属于集合论与图论第 3 讲 3

4 集合的表示列举法描述法特征函数法集合论与图论第 3 讲 4

5 列举法 (roster) 列出集合中的全体元素, 元素之间用逗号分开, 然后用花括号括起来, 例如 ={a,b,c,d,,x,y,z} B={0,1,2,3,4,5,6,7,8,9} 集合中的元素不规定顺序 C={2,1}={1,2} 集合中的元素各不相同 ( 多重集除外 ) C={2,1,1,2}={2,1} 集合论与图论第 3 讲 5

6 多重集 (multiple set) 多重集 : 允许元素多次重复出现的集合元素的重复度 : 元素的出现次数 ( 0). 例如 : 设 ={a,a,b,b,c} 是多重集元素 a,b 的重复度是 2 元素 c 的重复度是 1 元素 d 的重复度是集合论与图论第 3 讲 6

7 描述法 (defining predicate) 用谓词 P(x) 表示 x 具有性质 P, 用 {x P(x)} 表示具有性质 P 的集合, 例如 P 1 (x): x 是英文字母 ={x P 1 (x)}={x x 是英文字母 } ={a,b,c,d,,x,y,z} P 2 (x): x 是十进制数字 B={x P 2 (x)}= {x x 是十进制数字 } ={0,1,2,3,4,5,6,7,8,9} 集合论与图论第 3 讲 7

8 描述法 ( 续 ) 两种表示法可以互相转化, 例如 E={2,4,6,8, } ={x x>0 且 x 是偶数 } ={x x=2(k+1),k 为非负整数 } ={2(k+1) k 为非负整数 } 有些书在描述法中用 : 代替, 例如 {2(k+1): k 为非负整数 } 集合论与图论第 3 讲 8

9 特征函数法 (characteristic function) 集合的特征函数是 χ (x): 1, 若 x χ (x) = 0, 若 x 对多重集, χ (x)=x 在中的重复度集合论与图论第 3 讲 9

10 常用的数集合 N: 自然数 (natural numbers) 集合 N={0,1,2,3, } Z: 整数 (integers) 集合 Z={0,±1,±2, }={,-2,-1,0,1,2, } Q: 有理数 (rational numbers) 集合 R: 实数 (real numbers) 集合 C: 复数 (complex numbers) 集合集合论与图论第 3 讲 10

11 集合之间的关系子集相等真子集空集全集幂集 n 元集有限集集族集合论与图论第 3 讲 11

12 子集 (subset) B 包含于, 包含 B: B x(x B x ) B 不是的子集 : B x(x B x ) x(x B x ) x ( x B x ) x(x B x ) x(x B x ) 集合论与图论第 3 讲 12

13 相等 (equal) 相等 : =B B B x(x x B) =B B B (= 定义 ) x(x x B) x(x B x ) ( 定义 ) x((x x B) (x B x ))( 量词分配 ) x(x x B) ( 等值式 ) 集合论与图论第 3 讲 13

14 包含 ( ) 的性质证明 : x(x x ) 1 若 B, 且 B, 则 B 证明 : B (=B) ( B B ) ( 定义 ) ( B) (B ) ( 德摩根律 ) B ( 已知 ) B ( 即 B ) ( 析取三段论 ) # 集合论与图论第 3 讲 14

15 包含 ( ) 的性质 ( 续 ) 若 B, 且 B C, 则 C 证明 : B x(x x B) x, x x B ( B) x C (B C) x(x x C), 即 C. # 集合论与图论第 3 讲 15

16 真子集 (proper subset) 真子集 : B 真包含 : B B B B ( B B) ( 定义 ) ( B) (=B) ( 德摩根律 ) x(x x B) (=B) ( 定义 ) 集合论与图论第 3 讲 16

17 真包含 ( ) 的性质证明 : # 若 B, 则 B 证明 : ( 反证 ) 设 B, 则 B B B B ( 化简 ) B B B B 所以 B B =B (= 定义 ) 但是 B B B B ( 化简 ) 矛盾! # 集合论与图论第 3 讲 17

18 真包含 ( ) 的性质 ( 续 ) 若 B, 且 B C, 则 C 证明 : B B B B ( 化简 ), 同理 B C B C, 所以 C. 假设 =C, 则 B C B, 又 B, 故 =B, 此与 B 矛盾, 所以 C. 所以, C. # 集合论与图论第 3 讲 18

19 空集 (empty set) 空集 : 没有任何元素的集合是空集, 记作例如, {x R x 2 +1=0} 定理 1: 对任意集合, 证明 : x(x x ) x(0 x ) 1. # 推论 : 空集是唯一的. 证明 : 设 1 与 2 都是空集, 则 = # 集合论与图论第 3 讲 19

20 全集全集 : 如果限定所讨论的集合都是某个集合的子集, 则称这个集合是全集, 记作 E 全集是相对的, 视情况而定, 因此不唯一. 例如, 讨论 (a,b) 区间里的实数性质时, 可以选 E=(a,b), E=[a,b), E=(a,b], E=[a,b], E=(a,+ ),E=(-,+ ) 等集合论与图论第 3 讲 20

21 幂集 (power set) 幂集 : 的全体子集组成的集合, 称为的幂集, 记作 P() P()={x x } 注意 : x P() x 例子 : ={a,b}, P()={,{a},{b},{a,b}}. # 集合论与图论第 3 讲 21

22 n 元集 (n-set) n 元集 : 含有 n 个元素的集合称为 n 元集 0 元集 : 1 元集 ( 或单元集 ), 如 {a}, {b}, { }, {{ }}, : 表示集合中的元素个数, 是 n 元集 =n 有限集 (fimite set): 是有限数, <, 也叫有穷集集合论与图论第 3 讲 22

23 幂集 ( 续 ) 定理 : =n P() =2 n. 证明 : 每个子集对应一种染色, 一共有 2 n 种不同染色. # a 1 a 2 a 3 a n {a 1 } {a 1,a 3 } 集合论与图论第 3 讲 23

24 集族 (set family) 集族 : 由集合构成的集合. 幂集都是集族. 指标集 (index set): 设是集族, 若 ={ α α S}, 则 S 称为的指标集. S 中的元素与中的集合是一一对应的. 也记作 ={ α α S}={ α } α S 例 1: { 1, 2 } 的指标集是 {1,2} 集合论与图论第 3 讲 24

25 集族 ( 举例 ) 例 2: n ={x N x=n}, 0 ={0}, 1 ={1}, { n n N}={{0},{1},{2}, } { n n N} 的指标集是 N 例 3: 设 R + ={x R x>0}, a =[0,a), { a a R + } 的指标集是 R + 0 a 集合论与图论第 3 讲 25

26 集合之间的运算并集交集相对补集对称差绝对补广义并集广义交集集合论与图论第 3 讲 26

27 并集 (union) 并集 : B = { x (x ) (x B) } x B (x ) (x B) 初级并 : U U L U = { x 1 2 n i i(1 n U i = 1 U 2 i= 1 U i = 1 U 2 i= 1 U L i U U L n n x )} 集合论与图论第 3 讲 27

28 并集 ( 举例 ) 例 1: 设 n ={x R n-1 x n},n=1,2,,10, 则 10 U i i= 1 = { x R 0 x 10} = [0,10] 例 2: 设 n ={x R 0 x 1/n},n=1,2,, 则 U i= 1 i = { x R 0 x 1} = [0,1] 集合论与图论第 3 讲 28

29 交集 (intersection) 交集 : B = { x (x ) (x B) } x B (x ) (x B) 初级交 : I I L I = { x i(1 1 2 n i n I i = 1 I 2 i= 1 I i = 1 I 2 i= 1 I L i I I L n n x )} 集合论与图论第 3 讲 29

30 交集 ( 举例 ) 例 1: 设 n ={x R n-1 x n},n=1,2,,10, 则 10 I i= 1 i = 例 2: 设 n ={x R 0 x 1/n},n=1,2,, 则 I i= 1 i = {0} 集合论与图论第 3 讲 30

31 不相交 (disjoint) 不相交 : B= 互不相交 : 设 1, 2, 是可数多个集合, 若对于任意的 i j, 都有 i j =, 则说它们互不相交例 : 设 n ={x R n-1<x<n}, n=1,2,,10, 则 1, 2, 是不相交的集合论与图论第 3 讲 31

32 相对补集 (set difference) 相对补集 : 属于而不属于 B 的全体元素, 称为 B 对的相对补集, 记作 -B -B = { x (x ) (x B) } B -B 集合论与图论第 3 讲 32

33 对称差 (symmetric difference) 对称差 : 属于而不属于 B, 或属于 B 而不属于的全体元素, 称为与 B 的对称差, 记作 B B={x (x x B) (x x B)} B=(-B) (B-)=( B)-( B) B B 集合论与图论第 3 讲 33

34 绝对补 (complement) 绝对补 : ~=E-, E 是全集, E ~={x (x E x )} ~={x E x )} ~ 集合论与图论第 3 讲 34

35 相对补对称差补 ( 举例 ) 例 : 设 ={x R 0 x<2}, B={x R 1 x<3}, 则 -B= {x R 0 x<1}=[0,1) B-= {x R 2 x<3}=[2,3) B={x R (0 x<1) (2 x<3)}=[0,1) [2,3) [ [ ) [ ) ) 集合论与图论第 3 讲 35

36 广义并集 (big union) 广义并 : 设是集族, 中所有集合的元素的全体, 称为的广义并, 记作. = { x z(x z z } 当是以 S 为指标集的集族时 = { α α S}= α α S 例 : 设 ={{a,b},{c,d},{d,e,f}}, 则 = {a,b,c,d,e,f} 集合论与图论第 3 讲 36

37 广义交集 (big intersection) 广义交 : 设是集族, 中所有集合的公共元素的全体, 称为的广义交, 记作. = { x z(z x z) } 当是以 S 为指标集的集族时 = { α α S}= α α S 例 : 设 ={{1,2,3},{1,a,b},{1,6,7}}, 则 = {1} 集合论与图论第 3 讲 37

38 广义交广义并 ( 举例 ) 设 1 ={a,b,{c,d}}, 2 ={{a,b}}, 3 ={a}, 4 ={,{ }}, 5 =a(a ), 6 =, 则 1 = a b {c,d}, 1 = a b {c,d}, 2 ={a,b}, 2 ={a,b}, 3 =a, 3 =a 4 = { }={ }, 4 = { }=, 5 = a, 5 = a 6 =, 6 =E 集合论与图论第 3 讲 38

39 文氏图 (Venn diagram) 文氏图 : 平面上的 n 个圆 ( 或椭圆 ), 使得任何可能的相交部分, 都是非空的和连通的 John Venn, 1834~1923 例 : 集合论与图论第 3 讲 39

40 文氏图 ( 应用 ) 文氏图可表示集合运算 ( 结果用阴影表示 ) B B B B B -B B B B ~ B= 集合论与图论第 3 讲 40

41 集合论与图论第 3 讲 41 容斥原理 (principle of inclusion/exclusion) 容斥原理 ( 或包含排斥原理 ) < = = = j i j i n i i i n i 1 1 I U < < + + k j i n n k j i 1) ( I IL I L I I

42 容斥原理 ( 证明 ) n=2 时的情况 : B = + B - B 归纳证明 : 以 n=3 为例 : B C = ( B) C = B + C - ( B) C = + B - B + C - ( C) (B C) B C = + B - B + C -( C + B C - ( C) (B C) ) = + B + C - B - C - B C + B C B 集合论与图论第 3 讲 42

43 容斥原理 ( 举例 ) 例 1: 在 1 到之间既不是某个整数的平方, 也不是某个整数的立方的数有多少? 解 : 设 E={x N 1 x 10000}, E =10000 ={x E x=k 2 k Z}, =100 B={x E x=k 3 k Z}, B =21 则 ~( B) = E - B = E -( + B - B ) = =9883 注意 B= {x E x=k 6 k Z}, B =4. # 集合论与图论第 3 讲 43

44 容斥原理 ( 举例续 ) 例 2: 在 24 名科技人员中, 会说英, 日, 德, 法语的人数分别为 13, 5, 10, 和 9, 其中同时会说英语, 德语, 或同时会说英语, 法语, 或同时会说德语, 法语两种语言的人数均为 4. 会说日语的人既不会说法语也不会说德语. 试求只会说一种语言的人数各为多少? 又同时会说英, 德, 法语的人数有多少? 解 : 设 E={x x 是 24 名科技人员之一 }, E =24 ={x E x 会说英语 }, B={x E x 会说日语 }, C={x E x 会说德语 } D={x E x 会说法语 }, 集合论与图论第 3 讲 44

45 容斥原理 ( 举例续 ) 解 ( 续 ): 设所求人数分别为 x 1,x 2,x 3,x 4,x( 如图 ), X ={x E x 会说英语 }, = BX 2 4-X 4-X B={x E x 会说日语 }, B =5 X X C 4 C={x E x 会说德语 }, C =10 X 4-X 3 D D={x E x 会说法语 }, D =9 首先, x 2 = B - B =5-2=3, 其次, 对,C,D 用容斥原理, 注意 E =24: 24-3=21= x=20+x, 得 x=1, 最后, x 1 = - B =13-2-7=4, 同理 x 3 = =3, x 4 = =2. # 集合论与图论第 3 讲 45

46 总结集合概念 :,, E,,, 集合运算 :,, -,, ~, P( ) 文氏图容斥原理集合论与图论第 3 讲 46

47 习题 (#1) p25, 习题一, 3, 7, 10, 集合论与图论第 3 讲 47

1.2 集合

1.2 集合 Peking University 1 三次数学危机 Peking University 2 集合是数学中最基本的概念既然是最基本的概念, 就不是很好定义, 一般只是说明要说明什么是集合, 有多种描述方法 : 所要讨论的一类对象的整体 ; 具有同一性质单元的集体等当我们讨论某一类对象的时候, 就把这一类对象的整体称为集合而集合中的对象就成为该集合中的元素 Cantor 是这样描述集合的 :