第3講 集合的概念與運(yùn)算,1. 集合的概念 2. 集合之間的關(guān)系 3. 集合的運(yùn)算 4. 文氏圖、容斥原理,集合論(set theory),十九世紀(jì)數(shù)學(xué)最偉大成就之一 集合論體系 樸素(naive)集合論 公理(axiomatic)集合論 創(chuàng)始人康托(Cantor),Georg Ferdinand Philip Cantor 1845 1918 德國(guó)數(shù)學(xué)家, 集合論創(chuàng)始人.,什么是集合(set),集合：不能精確定義。一些對(duì)象的整體就構(gòu)成集合，這些對(duì)象稱為元素(element)或成員(member) 用大寫英文字母A,B,C,表示集合 用小寫英文字母a,b,c,表示元素 aA：表示a是A的元素，讀作“a屬于A” aA：表示a不是A的元素，讀作“a不屬于A”,集合的表示,列舉法 描述法 特征函數(shù)法,列舉法(roster),列出集合中的全體元素，元素之間用逗號(hào)分開，然后用花括號(hào)括起來，例如 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,1,多重集(multiple set),多重集: 允許元素多次重復(fù)出現(xiàn)的集合 元素的重復(fù)度: 元素的出現(xiàn)次數(shù)(0). 例如: 設(shè)A=a,a,b,b,c是多重集 元素a,b的重復(fù)度是2 元素c的重復(fù)度是2 元素d的重復(fù)度是0,描述法(defining predicate),用謂詞P(x)表示x具有性質(zhì)P ，用x|P(x)表示具有性質(zhì) P 的集合，例如 P1 (x): x是英文字母 A=x|P1 (x)=x| x是英文字母 =a,b,c,d,x,y,z P2 (x): x是十進(jìn)制數(shù)字 B=x|P2(x)= x|x是十進(jìn)制數(shù)字 =0,1,2,3,4,5,6,7,8,9,描述法（續(xù)）,兩種表示法可以互相轉(zhuǎn)化，例如 E=2,4,6,8, =x|x0且x是偶數(shù) =x|x=2(k+1)，k為非負(fù)整數(shù) =2(k+1) | k為非負(fù)整數(shù) 有些書在列舉法中用:代替|, 例如 2(k+1): k為非負(fù)整數(shù),特征函數(shù)法(characteristic function),集合A的特征函數(shù)是A (x): 1，若xA A (x) = 0，若xA 對(duì)多重集, A (x)=x在A中的重復(fù)度,數(shù)的集合,N：自然數(shù)(natural numbers)集合 N=0,1,2,3, Z：整數(shù)(integers)集合 Z=0,1,2,=,-2,-1,0,1,2, Q：有理數(shù)(rational numbers)集合 R：實(shí)數(shù)(real numbers)集合 C：復(fù)數(shù)(complex numbers)集合,集合之間的關(guān)系,子集、相等、真子集 空集、全集 冪集、n元集、有限集 集族,子集(subset),子集: 若B中的元素也都是A中的元素, 則稱B為A的子集, 或說B包含于A, 或說A包含B, 記作BA BA x(xBxA) 若B不是A的子集, 則記作BA BA x(xBxA) x(xBxA)x(xBxA) x(xBxA)x(xBxA),子集(舉例),設(shè)A=a,b,c,B=a,b,c,d,C=a,b,則 AB, CA, CB,A,C,B,a,b,c,d,e,f,g,h,i,j,相等(equal),相等: 互相包含的集合是相等的. A=B AB BA A=B x(xAxB) A=B ABBA (=定義) x(xAxB)x(xBxA) (定義) x(xAxB)(xBxA) (量詞分配) x(xAxB) (等值式),包含()的性質(zhì),AA 證明: AAx(xAxA) 1 若AB,且AB,則 BA 證明: AB (A=B) (ABBA) (定義) (AB) (BA) (德摩根律) AB (已知) BA (即BA) (析取三段論) #,包含()的性質(zhì)(續(xù)),若AB,且BC, 則AC 證明: AB x(xAxB) x, xA xB (AB) xC (BC) x(xAxC), 即AC. #,真子集(proper subset),真子集: B真包含A: AB AB AB AB (AB AB) (定義) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定義),真包含()的性質(zhì),AA 證明: A A AA AA 10 0. # 若AB,則 BA 證明: (反證) 設(shè)BA, 則 AB AB AB AB (化簡(jiǎn)) BA BA BA BA 所以 AB BA A=B (=定義) 但是 AB AB AB AB (化簡(jiǎn)) 矛盾! #,真包含()的性質(zhì)(續(xù)),若AB,且BC, 則AC 證明: AB AB AB AB (化簡(jiǎn)), 同理 BC BC, 所以AC. 假設(shè)A=C, 則BCBA, 又AB, 故A=B, 此與AB矛盾, 所以AC. 所以, AC. #,空集(empty set),空集:沒有任何元素的集合是空集,記作 例如, xR|x2 +1=0 定理1: 對(duì)任意集合A, A 證明: Ax(xxA) x(0 xA)1. # 推論: 空集是唯一的. 證明: 設(shè)1與2都是空集, 則 12 21 1=2 . #,全集,全集: 如果限定所討論的集合都是某個(gè)集合的子集,則稱這個(gè)集合是全集,記作E 全集是相對(duì)的, 視情況而定, 因此不唯一.例如, 討論(a,b)區(qū)間里的實(shí)數(shù)性質(zhì)時(shí), 可以選E=(a,b), E=a,b), E=(a,B, E=a,b, E=(a,+),E=(-,+)等,冪集(power set),冪集: A的全體子集組成的集合,稱為A的冪集,記作P(A) P(A)=x|xA 注意: xP(A) xA 例子: A=a,b, P(A)=,a,b,a,b. #,n元集(n-set),n元集: 含有n個(gè)元素的集合稱為n元集 0元集: 1元集(或單元集),如a, b, , , |A|: 表示集合A中的元素個(gè)數(shù), A是n元集 |A|=n 有限集 (fimite set): |A|是有限數(shù), |A|<, 也叫有窮集,冪集(續(xù)),定理: |A|=n |P(A)|=2n. 證明: 每個(gè)子集對(duì)應(yīng)一種染色,一共有2n 種不同染色. #,A,a1,a1,a2,a3,an,a1,a3,集族(set family),集族: 由集合構(gòu)成的集合. 冪集都是集族. 指標(biāo)集(index set): 設(shè)A是集族, 若A=A|S, 則S稱為A的指標(biāo)集. S中的元素與A中的集合是一一對(duì)應(yīng)的. 也記作A=A|S=AS 例1: A1,A2的指標(biāo)集是1,2,集族(舉例),例2: An=xN|x=n, A0=0, A1=1, An|nN=0,1,2, An|nN的指標(biāo)集是N 例3: 設(shè)R+=xR|x0, Aa=0,a), Aa|aR+ 的指標(biāo)集是R+,0,a,集合之間的運(yùn)算,并集、交集 相對(duì)補(bǔ)集、對(duì)稱差、絕對(duì)補(bǔ) 廣義并集、廣義交集,并集(union),并集: AB = x | (xA) (xB) xAB (xA) (xB) 初級(jí)并:,并集(舉例),例1: 設(shè)An=xR|n-1xn,n=1,2,10,則 例2: 設(shè)An=xR|0 x1/n,n=1,2,則,交集(intersection),交集: AB = x | (xA) (xB) xAB (xA) (xB) 初級(jí)交:,交集(舉例),例1: 設(shè)An=xR|n-1xn,n=1,2,10,則 例2: 設(shè)An=xR|0 x1/n,n=1,2,則,不相交(disjoint),不相交: AB= 互不相交: 設(shè)A1,A2,是可數(shù)多個(gè)集合, 若對(duì)于任意的ij, 都有AiBj=, 則說它們互不相交 例: 設(shè) An=xR|n-1<x<n, n=1,2,10, 則 A1,A2,是不相交的,相對(duì)補(bǔ)集(set difference),相對(duì)補(bǔ)集: 屬于A而不屬于B的全體元素,稱為B對(duì)A的相對(duì)補(bǔ)集, 記作A-B A-B = x | (xA) (xB) ,A-B,A,B,對(duì)稱差(symmetric difference),對(duì)稱差: 屬于A而不屬于B, 或?qū)儆贐而不屬于A的全體元素, 稱為A與B的對(duì)稱差, 記作AB AB=x|(xAxB)(xAxB) AB=(A-B)(B-A)=(AB)-(AB),AB,A,B,絕對(duì)補(bǔ)(complement),絕對(duì)補(bǔ): A=E-A, E是全集, AE A=x|(xExA) A=xE|xA),A,A,相對(duì)補(bǔ)、對(duì)稱差、補(bǔ)(舉例),例: 設(shè)A=xR|0 x<2, A=xR|1x<3, 則 A-B= xR|0 x<1=0,1) B-A= xR|2x<3=2,3) AB=xR|(0 x<1)(2x<3)=0,1)2,3),),),),廣義并集(big union),廣義并: 設(shè)A是集族, A中所有集合的元素的全體, 稱為A的廣義并, 記作A. A = x | z(xzzA 當(dāng)是以S為指標(biāo)集的集族時(shí) A = A|S= A S 例: 設(shè) A=a,b,c,d,d,e,f, 則 A= a,b,c,d,e,f,廣義交集(big intersection),廣義交: 設(shè)A是集族, A中所有集合的公共元素的全體, 稱為A的廣義交, 記作A. A = x | z(zAxz) 當(dāng)是以S為指標(biāo)集的集族時(shí) A = A|S= A S 例: 設(shè) A=1,2,3,1,a,b,1,6,7, 則 A= 1,廣義交、廣義并(舉例),設(shè) 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,文氏圖(Venn diagram),文氏圖: 平面上的n個(gè)圓(或橢圓),使得任何可能的相交部分, 都是非空的和連通的 John Venn, 18341923 例:,文氏圖(應(yīng)用),文氏圖可表示集合運(yùn)算(結(jié)果用陰影表示),AB,AB,A-B,AB,A,A,A,A,A,A,A,B,B,B,B,B,AB=,文氏圖(問題),Venn曾經(jīng)構(gòu)造出4個(gè)橢圓的文氏圖, 并且斷言: 沒有5個(gè)橢圓的文氏圖 Peter Hamburger & Raymond Pippert, 1996, 構(gòu)造出5個(gè)橢圓的文氏圖 Can you try it ?,文氏圖(續(xù)),試試 n=4:,14 < 16,文氏圖(續(xù)),試試 n=5,17 +,5 < 32,容斥原理(principle of inclusion/exclusion),容斥原理(或包含排斥原理),容斥原理(證明),n=2時(shí)的情況: |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|+|BC|-|(AC)(BC)|) = |A|+|B|+|C|-|AB|-|AC|-|BC| +|ABC|,A,B,B,C,A,容斥原理(舉例),例1: 在1到10000之間既不是某個(gè)整數(shù)的平方,也不是某個(gè)整數(shù)的立方的數(shù)有多少? 解: 設(shè) 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. #,容斥原理(舉例、續(xù)),例2: 在24名科技人員中,會(huì)說英,日,德,法語的人數(shù)分別為13, 5, 10, 和9, 其中同時(shí)會(huì)說英語,德語, 或同時(shí)會(huì)說英語,法語, 或同時(shí)會(huì)說德語,法語兩種語言的人數(shù)均為4.會(huì)說日語的人既不會(huì)說法語也不會(huì)說德語. 試求只會(huì)說一種語言的人數(shù)各為多少?又同時(shí)會(huì)說英,德,法語的人數(shù)有多少? 解: 設(shè)E=x|x是24名科技人員之一, |E|=24 A=xE|x會(huì)說英語, B=xE|x會(huì)說日語, C=xE|x會(huì)說德語 D=xE|x會(huì)說法語,容斥原理(舉例、續(xù)),解(續(xù)): 設(shè)所求人數(shù)分別為x1,x2,x3,x4,x(如圖), A=xE|x會(huì)說英語, |A|=13 B=xE|x會(huì)說日語, |B|=5 C=xE|x會(huì)說德語, |C|=10 D=xE|x會(huì)說法語, |D|=9 首先, x2=|B|-|AB|=5-2=3, 其次,對(duì)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,總結(jié),集合概念: , , E, , , 集合運(yùn)算: , , -, , , P( ) 文氏圖 容斥原理,習(xí)題(#1),p25, 習(xí)題一, 3, 7, 10, 16,