《集合论与图论：第3讲 集合的概念与运算》由会员分享，可在线阅读，更多相关《集合论与图论：第3讲 集合的概念与运算（47页珍藏版）》请在金锄头文库上搜索。
1、第3讲 集合的概念与运算 1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图、容斥原理2024/7/311集合论与图论第3讲集合论(set theory)十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 1918德国数学家, 集合论创始人. 2024/7/312集合论与图论第3讲 什么是集合(set)集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,表示集合用小
2、写英文字母a,b,c,表示元素aA：表示a是A的元素，读作“a属于A” aA：表示a不是A的元素，读作“a不属于A”2024/7/313集合论与图论第3讲集合的表示列举法描述法特征函数法2024/7/314集合论与图论第3讲列举法(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,1,2=2,12024/7/315集合论与图论第3讲多重集(multiple set)多重集: 允许元素多次重复出现的集合元素的
3、重复度: 元素的出现次数(0). 例如: 设A=a,a,b,b,c是多重集 元素a,b的重复度是2 元素c的重复度是1 元素d的重复度是02024/7/316集合论与图论第3讲描述法(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|P2(x)= x|x是十进制数字 =0,1,2,3,4,5,6,7,8,92024/7/317集合论与图论第3讲描述法（续）两种表示法可以互相转化，例如E=2,4,
4、6,8,=x|x0且x是偶数 =x|x=2(k+1)，k为非负整数=2(k+1) | k为非负整数 有些书在描述法中用:代替|, 例如2(k+1): k为非负整数2024/7/318集合论与图论第3讲特征函数法(characteristic function)集合A的特征函数是A (x): 1，若xA A (x) = 0，若xA 对多重集, A (x)=x在A中的重复度2024/7/319集合论与图论第3讲常用的数集合N：自然数(natural numbers)集合N=0,1,2,3,Z：整数(integers)集合Z=0,1,2,=,-2,-1,0,1,2,Q：有理数(rational nu
5、mbers)集合R：实数(real numbers)集合C：复数(complex numbers)集合2024/7/3110集合论与图论第3讲集合之间的关系子集、相等、真子集 空集、全集幂集、n元集、有限集集族2024/7/3111集合论与图论第3讲子集(subset) B包含于A, A包含B: BA x(xBxA)B不是A的子集: BA x(xBxA)x(xBxA)x(xBxA) x(xBxA)x(xBxA)2024/7/3112集合论与图论第3讲相等(equal)相等: A=B AB BA x(xAxB) A=B ABBA (=定义)x(xAxB)x(xBxA) (定义)x(xAxB)(x
6、BxA)(量词分配)x(xAxB) (等值式)2024/7/3113集合论与图论第3讲包含()的性质AA 证明: AAx(xAxA) 1若AB,且AB,则 BA 证明: AB (A=B) (ABBA) (定义) (AB) (BA) (德摩根律) AB (已知) BA (即BA) (析取三段论) #2024/7/3114集合论与图论第3讲包含()的性质(续)若AB,且BC, 则AC证明: AB x(xAxB) x, xA xB (AB) xC (BC) x(xAxC), 即AC. #2024/7/3115集合论与图论第3讲真子集(proper subset) 真子集: B真包含A:AB AB A
7、B AB (AB AB) (定义) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定义)2024/7/3116集合论与图论第3讲真包含()的性质AA 证明: A A AA AA 10 0. #若AB,则 BA 证明: (反证) 设BA, 则 AB AB AB AB (化简) BA BA BA BA 所以 AB BA A=B (=定义)但是 AB AB AB AB (化简) 矛盾! #2024/7/3117集合论与图论第3讲真包含()的性质(续)若AB,且BC, 则AC证明: AB AB AB AB (化简), 同理 BC BC, 所以AC. 假设A=C, 则BCBA, 又A
8、B, 故A=B, 此与AB矛盾, 所以AC. 所以, AC. #2024/7/3118集合论与图论第3讲空集(empty set)空集:没有任何元素的集合是空集,记作例如, xR|x2 +1=0定理1: 对任意集合A, A 证明: Ax(xxA) x(0xA)1. #推论: 空集是唯一的. 证明: 设1与2都是空集, 则 12 21 1=2 . #2024/7/3119集合论与图论第3讲全集全集: 如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作E全集是相对的, 视情况而定, 因此不唯一.例如, 讨论(a,b)区间里的实数性质时, 可以选E=(a,b), E=a,b), E=(
9、a,b, E=a,b, E=(a,+),E=(-,+)等2024/7/3120集合论与图论第3讲幂集(power set)幂集: A的全体子集组成的集合,称为A的幂集,记作P(A)P(A)=x|xA注意: xP(A) xA例子: A=a,b, P(A)=,a,b,a,b. #2024/7/3121集合论与图论第3讲n元集(n-set) n元集: 含有n个元素的集合称为n元集0元集: 1元集(或单元集),如a, b, , ,|A|: 表示集合A中的元素个数, A是n元集 |A|=n有限集 (fimite set): |A|是有限数, |A|0, Aa=0,a), Aa|aR+ 的指标集是R+0a
10、2024/7/3125集合论与图论第3讲集合之间的运算并集、交集相对补集、对称差、绝对补广义并集、广义交集2024/7/3126集合论与图论第3讲并集(union)并集: AB = x | (xA) (xB) xAB (xA) (xB)初级并: 2024/7/3127集合论与图论第3讲并集(举例)例1: 设An=xR|n-1xn,n=1,2,10,则例2: 设An=xR|0x1/n,n=1,2,则2024/7/3128集合论与图论第3讲交集(intersection)交集: AB = x | (xA) (xB) xAB (xA) (xB)初级交: 2024/7/3129集合论与图论第3讲交集(
11、举例)例1: 设An=xR|n-1xn,n=1,2,10,则例2: 设An=xR|0x1/n,n=1,2,则2024/7/3130集合论与图论第3讲不相交(disjoint)不相交: AB=互不相交: 设A1,A2,是可数多个集合, 若对于任意的ij, 都有AiAj=, 则说它们互不相交例: 设 An=xR|n-1xn, n=1,2,10, 则 A1,A2,是不相交的2024/7/3131集合论与图论第3讲相对补集(set difference)相对补集: 属于A而不属于B的全体元素,称为B对A的相对补集, 记作A-BA-B = x | (xA) (xB) A-BAB2024/7/3132集合
12、论与图论第3讲对称差(symmetric difference)对称差: 属于A而不属于B, 或属于B而不属于A的全体元素, 称为A与B的对称差, 记作ABAB=x|(xAxB)(xAxB)AB=(A-B)(B-A)=(AB)-(AB)A BAB2024/7/3133集合论与图论第3讲绝对补(complement)绝对补: A=E-A, E是全集, AEA=x|(xExA)A=xE|xA)AA2024/7/3134集合论与图论第3讲相对补、对称差、补(举例)例: 设A=xR|0x2, B=xR|1x3, 则 A-B= xR|0x1=0,1)B-A= xR|2x3=2,3)AB=xR|(0x1)
13、(2x3)=0,1)2,3)2024/7/3135集合论与图论第3讲广义并集(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,f2024/7/3136集合论与图论第3讲广义交集(big intersection)广义交: 设A是集族, A中所有集合的公共元素的全体, 称为A的广义交, 记作 A. A = x | z(zAxz) 当A是以S为指标集的集族时 A = A|S= A S例: 设
14、 A=1,2,3,1,a,b,1,6,7, 则 A= 12024/7/3137集合论与图论第3讲广义交、广义并(举例)设 A1=a,b,c,d, A2=a,b, A3=a, A4=, A5=a(a), A6=, 则 A1= a b c,d, A1= a b c,d, A2=a,b, A2=a,b, A3=a, A3=a A4= =, A4= =, A5= a, A5= a A6=, A6=E2024/7/3138集合论与图论第3讲文氏图(Venn diagram)文氏图: 平面上的n个圆(或椭圆),使得任何可能的相交部分, 都是非空的和连通的John Venn, 18341923例: 2024
15、/7/3139集合论与图论第3讲文氏图(应用)文氏图可表示集合运算(结果用阴影表示)A BA BA-BA BAAAAAAABBBBBA B=2024/7/3140集合论与图论第3讲容斥原理(principle of inclusion/exclusion)容斥原理(或包含排斥原理)2024/7/3141集合论与图论第3讲容斥原理(证明) n=2时的情况:|AB|=|A|+|B|-|AB| 归纳证明: 以n=3为例:|AB C| = |(AB)C|= |AB|+|C|-|(AB)C| = |A|+|B|-|AB|+|C|-|(AC)(BC)| = |A|+|B|-|AB|+|C| -(|AC|+
16、|BC|-|(AC)(BC)|) = |A|+|B|+|C|-|AB|-|AC|-|BC| +|ABC|ABBCA2024/7/3142集合论与图论第3讲容斥原理(举例)例1: 在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少?解: 设 E=xN|1x10000, |E|=10000 A=xE|x=k2kZ, |A|=100 B=xE|x=k3kZ, |B|=21 则 |(AB)|=|E|-|AB| =|E|-(|A|+|B|-|AB|) =10000-100-21+4=9883 注意 AB= xE|x=k6kZ, |AB|=4. #2024/7/3143集合论与图论第
17、3讲容斥原理(举例、续)例2: 在24名科技人员中,会说英,日,德,法语的人数分别为13, 5, 10, 和9, 其中同时会说英语,德语, 或同时会说英语,法语, 或同时会说德语,法语两种语言的人数均为4.会说日语的人既不会说法语也不会说德语. 试求只会说一种语言的人数各为多少?又同时会说英,德,法语的人数有多少?解: 设E=x|x是24名科技人员之一, |E|=24 A=xE|x会说英语, B=xE|x会说日语, C=xE|x会说德语 D=xE|x会说法语,2024/7/3144集合论与图论第3讲容斥原理(举例、续)解(续): 设所求人数分别为x1,x2,x3,x4,x(如图), A=xE|
18、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. #DCBAXX1X2X3X44-X4-X4-X22024/7/3145集合论与图论第3讲总结集合概念: , , E, , , 集合运算: , , -, , , P( )文氏图容斥原理2024/7/3146集合论与图论第3讲习题(#1) p25, 习题一, 3, 7, 10, 16 2024/7/3147集合论与图论第3讲
