北大離散數學ppt課件

1、第3講 集合的概念與運算北京大學 1. 集合的概念 2. 集合之間的關系 3. 集合的運算 4. 文氏圖、容斥原理1;集合論(set theory)十九世紀數學最偉大成就之一集合論體系樸素(naive)集合論公理(axiomatic)集合論創(chuàng)始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 1918德國數學家, 集合論創(chuàng)始人. 2; 什么是集合(set)集合：不能精確定義。一些對象的整體就構成集合，這些對象稱為元素(element)或成員(member)用大寫英文字母A,B,C,表示集合用小寫英文字母a,b,c,表示元素aA：表示a是A的元素，讀作“

2、a屬于A” aA：表示a不是A的元素，讀作“a不屬于A”3;集合的表示列舉法描述法特征函數法4;列舉法(roster)列出集合中的全體元素，元素之間用逗號分開，然后用花括號括起來，例如A=a,b,c,d,x,y,z B=0,1,2,3,4,5,6,7,8,9集合中的元素不規(guī)定順序C=2,1=1,2集合中的元素各不相同(多重集除外)C=2,1,1,2=2,15;多重集(multiple set)多重集: 允許元素多次重復出現的集合元素的重復度: 元素的出現次數(0). 例如: 設A=a,a,b,b,c是多重集 元素a,b的重復度是2 元素c的重復度是1 元素d的重復度是06;描述法(defini

3、ng 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,97;描述法（續(xù)）兩種表示法可以互相轉化，例如E=2,4,6,8,=x|x0且x是偶數 =x|x=2(k+1)，k為非負整數=2(k+1) | k為非負整數 有些書在描述法中用:代替|, 例如2(k+1): k為非負整數8;特征函數法(characteristic function)集合

4、A的特征函數是A (x): 1，若xA A (x) = 0，若xA 對多重集, A (x)=x在A中的重復度9;常用的數集合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)集合10;集合之間的關系子集、相等、真子集 空集、全集冪集、n元集、有限集集族11;子集(subset) B包含于A, A包含B: BA x(xBxA)B不是A的子集: BA x(xBxA)x(xBx

5、A)x(xBxA) x(xBxA)x(xBxA)12;相等(equal)相等: A=B AB BA x(xAxB) A=B ABBA (=定義)x(xAxB)x(xBxA) (定義)x(xAxB)(xBxA)(量詞分配)x(xAxB) (等值式)13;包含()的性質AA 證明: AAx(xAxA) 1若AB,且AB,則 BA 證明: AB (A=B) (ABBA) (定義) (AB) (BA) (德摩根律) AB (已知) BA (即BA) (析取三段論) #14;包含()的性質(續(xù))若AB,且BC, 則AC證明: AB x(xAxB) x, xA xB (AB) xC (BC) x(xAxC

6、), 即AC. #15;真子集(proper subset) 真子集: B真包含A:AB AB AB AB (AB AB) (定義) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定義)16;真包含()的性質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 (化簡) 矛盾! #17;真包含()的性質(續(xù))若AB,且BC, 則AC證明: AB AB AB AB (化簡), 同理 BC BC, 所以AC. 假

7、設A=C, 則BCBA, 又AB, 故A=B, 此與AB矛盾, 所以AC. 所以, AC. #18;空集(empty set)空集:沒有任何元素的集合是空集,記作例如, xR|x2 +1=0定理1: 對任意集合A, A 證明: Ax(xxA) x(0 xA)1. #推論: 空集是唯一的. 證明: 設1與2都是空集, 則 12 21 1=2 . #19;全集全集: 如果限定所討論的集合都是某個集合的子集,則稱這個集合是全集,記作E全集是相對的, 視情況而定, 因此不唯一.例如, 討論(a,b)區(qū)間里的實數性質時, 可以選E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+

8、),E=(-,+)等20;冪集(power set)冪集: A的全體子集組成的集合,稱為A的冪集,記作P(A)P(A)=x|xA注意: xP(A) xA例子: A=a,b, P(A)=,a,b,a,b. #21;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+0a25;集合之間的運算并集、交集相對補集、對稱差、絕對補廣義并集、廣義交集26;并集(union)并集:

9、AB = x | (xA) (xB) xAB (xA) (xB)初級并: )1 (|21inAxniixAAAniniAAAA211211AAAii27;并集(舉例)例1: 設An=xR|n-1xn,n=1,2,10,則例2: 設An=xR|0 x1/n,n=1,2,則10, 0100|101xRxAii 1 , 010|1xRxAii28;交集(intersection)交集: AB = x | (xA) (xB) xAB (xA) (xB)初級交: )1 (|21inAxniixAAAniniAAAA211211AAAii29;交集(舉例)例1: 設An=xR|n-1xn,n=1,2,10

10、,則例2: 設An=xR|0 x1/n,n=1,2,則iiA10101iiA30;不相交(disjoint)不相交: AB=互不相交: 設A1,A2,是可數多個集合, 若對于任意的ij, 都有AiAj=, 則說它們互不相交例: 設 An=xR|n-1xn, n=1,2,10, 則 A1,A2,是不相交的31;相對補集(set difference)相對補集: 屬于A而不屬于B的全體元素,稱為B對A的相對補集, 記作A-BA-B = x | (xA) (xB) A-BAB32;對稱差(symmetric difference)對稱差: 屬于A而不屬于B, 或屬于B而不屬于A的全體元素, 稱為A與

11、B的對稱差, 記作ABAB=x|(xAxB)(xAxB)AB=(A-B)(B-A)=(AB)-(AB)A BAB33;絕對補(complement)絕對補: A=E-A, E是全集, AEA=x|(xExA)A=xE|xA)AA34;相對補、對稱差、補(舉例)例: 設A=xR|0 x2, B=xR|1x3, 則 A-B= xR|0 x1=0,1)B-A= xR|2x3=2,3)AB=xR|(0 x1)(2x3)=0,1)2,3)35;廣義并集(big union)廣義并: 設A是集族, A中所有集合的元素的全體, 稱為A的廣義并, 記作A.A = x | z(xzzA 當A是以S為指標集的集族

12、時A = A|S= A S例: 設 A=a,b,c,d,d,e,f, 則 A= a,b,c,d,e,f36;廣義交集(big intersection)廣義交: 設A是集族, A中所有集合的公共元素的全體, 稱為A的廣義交, 記作 A. A = x | z(zAxz) 當A是以S為指標集的集族時 A = A|S= A S例: 設 A=1,2,3,1,a,b,1,6,7, 則 A= 137;廣義交、廣義并(舉例)設 A1=a,b,c,d, A2=a,b, A3=a, A4=, A5=a(a), A6=, 則A1= abc,d, A1= a b c,d,A2=a,b, A2=a,b, A3=a,

13、A3=aA4=, A4= =,A5= a, A5= aA6=, A6=E38;文氏圖(Venn diagram)文氏圖: 平面上的n個圓(或橢圓),使得任何可能的相交部分, 都是非空的和連通的John Venn, 18341923例: 39;文氏圖(應用)文氏圖可表示集合運算(結果用陰影表示)A BA BA-BA BAAAAAAABBBBBA B=40;容斥原理(principle of inclusion/exclusion)容斥原理(或包含排斥原理)jijiniiiniAAAA|11kjinnkjiAAAAAA|) 1(|21141;容斥原理(證明) n=2時的情況:|AB|=|A|+|B

14、|-|AB| 歸納證明: 以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|ABBCA42;容斥原理(舉例)例1: 在1到10000之間既不是某個整數的平方,也不是某個整數的立方的數有多少?解: 設 E=xN|1x10000, |E|=10000 A=xE|x=k2kZ, |A|=100 B=xE|x=k3kZ, |B|=21 則 |(AB)|=|

15、E|-|AB| =|E|-(|A|+|B|-|AB|) =10000-100-21+4=9883 注意 AB= xE|x=k6kZ, |AB|=4. #43;容斥原理(舉例、續(xù))例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會說法語,44;容斥原理(舉例、續(xù))解(續(xù)): 設所求人數分別為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|