北大离散数学03.ppt

《北大离散数学03.ppt》由会员分享，可在线阅读，更多相关《北大离散数学03.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/10/24,集合论与图论第3讲,1,第3讲 集合的概念与运算北京大学,1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图、容斥原理,2020/10/24,集合论与图论第3讲,2,集合论(set theory),十九世纪数学最伟大成就之一 集合论体系 朴素(naive)集合论 公理(axiomatic)集合论 创始人康托(Cantor),Georg Ferdinand Philip Cantor 1845 1918 德国数学家, 集合论创始人.,2020/10/24,集合论与图论第3讲,3,什么是集合(set),集合：不能精确定义。一些对象的整体就构成集合，这些对象

2、称为元素(element)或成员(member) 用大写英文字母A,B,C,表示集合 用小写英文字母a,b,c,表示元素 aA：表示a是A的元素，读作“a属于A” aA：表示a不是A的元素，读作“a不属于A”,2020/10/24,集合论与图论第3讲,4,集合的表示,列举法 描述法 特征函数法,2020/10/24,集合论与图论第3讲,5,列举法(roster),列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如 A=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

3、,1,2=2,1,2020/10/24,集合论与图论第3讲,6,多重集(multiple set),多重集: 允许元素多次重复出现的集合 元素的重复度: 元素的出现次数(0). 例如: 设A=a,a,b,b,c是多重集 元素a,b的重复度是2 元素c的重复度是1 元素d的重复度是0,2020/10/24,集合论与图论第3讲,7,描述法(defining predicate),用谓词P(x)表示x具有性质P ，用x|P(x)表示具有性质 P 的集合，例如 P1 (x): x是英文字母 A=x|P1 (x)=x| x是英文字母 =a,b,c,d,x,y,z P2 (x): x是十进制数字 B=x|

4、P2(x)= x|x是十进制数字 =0,1,2,3,4,5,6,7,8,9,2020/10/24,集合论与图论第3讲,8,描述法（续）,两种表示法可以互相转化，例如 E=2,4,6,8, =x|x0且x是偶数 =x|x=2(k+1)，k为非负整数 =2(k+1) | k为非负整数 有些书在描述法中用:代替|, 例如 2(k+1): k为非负整数,2020/10/24,集合论与图论第3讲,9,特征函数法(characteristic function),集合A的特征函数是A (x): 1，若xA A (x) = 0，若xA 对多重集, A (x)=x在A中的重复度,2020/10/24,集合论与

5、图论第3讲,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)集合,2020/10/24,集合论与图论第3讲,11,集合之间的关系,子集、相等、真子集 空集、全集 幂集、n元集、有限集 集族,2020/10/24,集合论与图论第3讲,12,子集(subset),B包含于A, A包含B: BA x(xBxA) B不是A的子集: BA x(xB

6、xA) x(xBxA)x(xBxA) x(xBxA)x(xBxA),2020/10/24,集合论与图论第3讲,13,相等(equal),相等: A=B AB BA x(xAxB) A=B ABBA (=定义) x(xAxB)x(xBxA) (定义) x(xAxB)(xBxA)(量词分配) x(xAxB) (等值式),2020/10/24,集合论与图论第3讲,14,包含()的性质,AA 证明: AAx(xAxA) 1 若AB,且AB,则 BA 证明: AB (A=B) (ABBA) (定义) (AB) (BA) (德摩根律) AB (已知) BA (即BA) (析取三段论) #,2020/10/

7、24,集合论与图论第3讲,15,包含()的性质(续),若AB,且BC, 则AC 证明: AB x(xAxB) x, xA xB (AB) xC (BC) x(xAxC), 即AC. #,2020/10/24,集合论与图论第3讲,16,真子集(proper subset),真子集: B真包含A: AB AB AB AB (AB AB) (定义) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定义),2020/10/24,集合论与图论第3讲,17,真包含()的性质,AA 证明: A A AA AA 10 0. # 若AB,则 BA 证明: (反证) 设BA, 则 AB AB A

8、B AB (化简) BA BA BA BA 所以 AB BA A=B (=定义) 但是 AB AB AB AB (化简) 矛盾! #,2020/10/24,集合论与图论第3讲,18,真包含()的性质(续),若AB,且BC, 则AC 证明: AB AB AB AB (化简), 同理 BC BC, 所以AC. 假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以AC. 所以, AC. #,2020/10/24,集合论与图论第3讲,19,空集(empty set),空集:没有任何元素的集合是空集,记作 例如, xR|x2 +1=0 定理1: 对任意集合A, A 证明: Ax(xxA

9、) x(0 xA)1. # 推论: 空集是唯一的. 证明: 设1与2都是空集, 则 12 21 1=2 . #,2020/10/24,集合论与图论第3讲,20,全集,全集: 如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作E 全集是相对的, 视情况而定, 因此不唯一.例如, 讨论(a,b)区间里的实数性质时, 可以选E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+),E=(-,+)等,2020/10/24,集合论与图论第3讲,21,幂集(power set),幂集: A的全体子集组成的集合,称为A的幂集,记作P(A) P(A)=x|xA 注意: xP

10、(A) xA 例子: A=a,b, P(A)=,a,b,a,b. #,2020/10/24,集合论与图论第3讲,22,n元集(n-set),n元集: 含有n个元素的集合称为n元集 0元集: 1元集(或单元集),如a, b, , , |A|: 表示集合A中的元素个数, A是n元集 |A|=n 有限集 (fimite set): |A|是有限数, |A|, 也叫有穷集,2020/10/24,集合论与图论第3讲,23,幂集(续),定理: |A|=n |P(A)|=2n. 证明: 每个子集对应一种染色,一共有2n 种不同染色. #,A,a1,a1,a2,a3,an,a1,a3,2020/10/24,集

11、合论与图论第3讲,24,集族(set family),集族: 由集合构成的集合. 幂集都是集族. 指标集(index set): 设A是集族, 若A=A|S, 则S称为A的指标集. S中的元素与A中的集合是一一对应的. 也记作A=A|S=AS 例1: A1,A2的指标集是1,2,2020/10/24,集合论与图论第3讲,25,集族(举例),例2: An=xN|x=n, A0=0, A1=1, An|nN=0,1,2, An|nN的指标集是N 例3: 设R+=xR|x0, Aa=0,a), Aa|aR+ 的指标集是R+,0,a,2020/10/24,集合论与图论第3讲,26,集合之间的运算,并集

12、、交集 相对补集、对称差、绝对补 广义并集、广义交集,2020/10/24,集合论与图论第3讲,27,并集(union),并集: AB = x | (xA) (xB) xAB (xA) (xB) 初级并:,2020/10/24,集合论与图论第3讲,28,并集(举例),例1: 设An=xR|n-1xn,n=1,2,10,则 例2: 设An=xR|0 x1/n,n=1,2,则,2020/10/24,集合论与图论第3讲,29,交集(intersection),交集: AB = x | (xA) (xB) xAB (xA) (xB) 初级交:,2020/10/24,集合论与图论第3讲,30,交集(举例

13、),例1: 设An=xR|n-1xn,n=1,2,10,则 例2: 设An=xR|0 x1/n,n=1,2,则,2020/10/24,集合论与图论第3讲,31,不相交(disjoint),不相交: AB= 互不相交: 设A1,A2,是可数多个集合, 若对于任意的ij, 都有AiAj=, 则说它们互不相交 例: 设 An=xR|n-1xn, n=1,2,10, 则 A1,A2,是不相交的,2020/10/24,集合论与图论第3讲,32,相对补集(set difference),相对补集: 属于A而不属于B的全体元素,称为B对A的相对补集, 记作A-B A-B = x | (xA) (xB) ,A

14、-B,A,B,2020/10/24,集合论与图论第3讲,33,对称差(symmetric difference),对称差: 属于A而不属于B, 或属于B而不属于A的全体元素, 称为A与B的对称差, 记作AB AB=x|(xAxB)(xAxB) AB=(A-B)(B-A)=(AB)-(AB),AB,A,B,2020/10/24,集合论与图论第3讲,34,绝对补(complement),绝对补: A=E-A, E是全集, AE A=x|(xExA) A=xE|xA),A,A,2020/10/24,集合论与图论第3讲,35,相对补、对称差、补(举例),例: 设A=xR|0 x2, B=xR|1x3,

15、 则 A-B= xR|0 x1=0,1) B-A= xR|2x3=2,3) AB=xR|(0 x1)(2x3)=0,1)2,3),),),),2020/10/24,集合论与图论第3讲,36,广义并集(big union),广义并: 设A是集族, A中所有集合的元素的全体, 称为A的广义并, 记作A. A = x | z(xzzA 当A是以S为指标集的集族时 A = A|S= A S 例: 设 A=a,b,c,d,d,e,f, 则 A= a,b,c,d,e,f,2020/10/24,集合论与图论第3讲,37,广义交集(big intersection),广义交: 设A是集族, A中所有集合的公共

16、元素的全体, 称为A的广义交, 记作A. A = x | z(zAxz) 当A是以S为指标集的集族时 A = A|S= A S 例: 设 A=1,2,3,1,a,b,1,6,7, 则 A= 1,2020/10/24,集合论与图论第3讲,38,广义交、广义并(举例),设 A1=a,b,c,d, A2=a,b, A3=a, A4=, A5=a(a), A6=, 则 A1= abc,d, A1= abc,d, A2=a,b, A2=a,b, A3=a, A3=a A4=, A4=, A5= a, A5= a A6=, A6=E,2020/10/24,集合论与图论第3讲,39,文氏图(Venn dia

17、gram),文氏图: 平面上的n个圆(或椭圆),使得任何可能的相交部分, 都是非空的和连通的 John Venn, 18341923 例:,2020/10/24,集合论与图论第3讲,40,文氏图(应用),文氏图可表示集合运算(结果用阴影表示),AB,AB,A-B,AB,A,A,A,A,A,A,A,B,B,B,B,B,AB=,2020/10/24,集合论与图论第3讲,41,容斥原理(principle of inclusion/exclusion),容斥原理(或包含排斥原理),2020/10/24,集合论与图论第3讲,42,容斥原理(证明),n=2时的情况: |AB|=|A|+|B|-|AB|

18、归纳证明: 以n=3为例: |AB C| = |(AB)C|= |AB|+|C|-|(AB)C| = |A|+|B|-|AB|+|C|-|(AC)(BC)| = |A|+|B|-|AB|+|C| -(|AC|+|BC|-|(AC)(BC)|) = |A|+|B|+|C|-|AB|-|AC|-|BC| +|ABC|,A,B,B,C,A,2020/10/24,集合论与图论第3讲,43,容斥原理(举例),例1: 在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少? 解: 设 E=xN|1x10000, |E|=10000 A=xE|x=k2kZ, |A|=100 B=xE|x=

19、k3kZ, |B|=21 则 |(AB)|=|E|-|AB| =|E|-(|A|+|B|-|AB|) =10000-100-21+4=9883 注意 AB= xE|x=k6kZ, |AB|=4. #,2020/10/24,集合论与图论第3讲,44,容斥原理(举例、续),例2: 在24名科技人员中,会说英,日,德,法语的人数分别为13, 5, 10, 和9, 其中同时会说英语,德语, 或同时会说英语,法语, 或同时会说德语,法语两种语言的人数均为4.会说日语的人既不会说法语也不会说德语. 试求只会说一种语言的人数各为多少?又同时会说英,德,法语的人数有多少? 解: 设E=x|x是24名科技人员之

20、一, |E|=24 A=xE|x会说英语, B=xE|x会说日语, C=xE|x会说德语 D=xE|x会说法语,2020/10/24,集合论与图论第3讲,45,容斥原理(举例、续),解(续): 设所求人数分别为x1,x2,x3,x4,x(如图), A=xE|x会说英语, |A|=13 B=xE|x会说日语, |B|=5 C=xE|x会说德语, |C|=10 D=xE|x会说法语, |D|=9 首先, x2=|B|-|AB|=5-2=3, 其次,对A,C,D用容斥原理, 注意|E|=24: 24-3=21=13+10+9-4-4-4+x=20+x, 得x=1, 最后, x1=|A|-|AB|-3-3-1=13-2-7=4, 同理 x3=10-3-3-1=3, x4=9-3-3-1=2. #,D,C,B,A,X,X1,X2,X3,X4,4-X,4-X,4-X,2,2020/10/24,集合论与图论第3讲,46,总结,集合概念: , , E, , , 集合运算: , , -, , , P( ) 文氏图 容斥原理,2020/10/24,集合论与图论第3讲,47,习题(#1),p25, 习题一, 3, 7, 10, 16,