北大離散數(shù)學(xué)08實用教案

1、2021-12-16集合論與圖論(t ln)第8講1等價等價(dngji)(equivalence)關(guān)系關(guān)系 定義 同余關(guān)系 等價類 商集 劃分(hu fn) 劃分(hu fn)的加細(xì) Stirling子集數(shù)第1頁/共63頁第一頁，共64頁。2021-12-16集合論與圖論(t ln)第8講2等價等價(equivalence)關(guān)系關(guān)系(gun x)定義定義 等價關(guān)系: 設(shè) RAA 且 A, 若R是自反(z fn)的, 對稱的, 傳遞的,則稱R為等價關(guān)系 例9: 判斷是否等價關(guān)系(A是某班學(xué)生): R1=|x,yAx與y同年生 R2=|x,yAx與y同姓 R3=|x,yAx的年齡不比y小 R4=

2、|x,yAx與y選修同門課程 R5=|x,yAx的體重比y重第2頁/共63頁第二頁，共64頁。2021-12-16集合論與圖論(t ln)第8講3例例9(續(xù)續(xù))定義自反對稱 傳遞 等價關(guān)系R1x與y同年生R2x與y同姓R3x的年齡不比y小R4x與y選修同門課程R5x的體重比y重第3頁/共63頁第三頁，共64頁。2021-12-16集合論與圖論(t ln)第8講4例例10 例10: 設(shè) RAA 且 A, 對R依次求三種閉包共有6種不同順序, 其中哪些(nxi)順序一定導(dǎo)致等價關(guān)系? rst( R ), rts( R ), str( R ), srt( R ), trs( R ), tsr( R

3、)=t(s(r( R ) 解: st( R )ts( R ), sr( R )=rs( R ), tsr( R )=trs( R )=rts( R ) str( R )=srt( R )=rst( R )第4頁/共63頁第四頁，共64頁。2021-12-16集合論與圖論(t ln)第8講5例例10(續(xù)續(xù))tsr(R)=trs(R) =rts( R )str(R)=srt(R)=rst( R )自反對稱傳遞等價關(guān)系(等價閉包)第5頁/共63頁第五頁，共64頁。2021-12-16集合論與圖論(t ln)第8講6等價等價(dngji)類類(equivalence class) 等價類: 設(shè)R是A上

4、等價關(guān)系,xA,令 xR= y | yA xRy , 稱xR為x關(guān)于(guny)R的等價類, 簡稱x的等價類, 簡記為x. 等價類性質(zhì): xR ; xRy xR=yR ;xRy xRyR= ; U xR | xA =A.第6頁/共63頁第六頁，共64頁。2021-12-16集合論與圖論(t ln)第8講7定理定理(dngl)27 定理(dngl)27:設(shè)R是A上等價關(guān)系,x,yA, (1) xR (2) xRy xR=yR ; (3) xRy xRyR= ; (4) U xR | xA =A. 證明: (1) R自反xRxxxRxR.x第7頁/共63頁第七頁，共64頁。2021-12-16集合

5、論與圖論(t ln)第8講8定理定理(dngl)27(證明證明(2) (2) xRy xR=yR ; 證明(zhngmng): (2) 只需證明(zhngmng)xRyR和xRyR. () z, zxRxRy zRxxRy zRy zyR . xRyR. () 同理可證.xyz第8頁/共63頁第八頁，共64頁。2021-12-16集合論與圖論(t ln)第8講9定理定理(dngl)27(證明證明(3) (3) xRy xRyR= ; 證明(zhngmng): (3) (反證) 假設(shè)z, zxRyR, 則 zxRyR zRxzRy xRzzRy xRy, 這與xRy矛盾! xRyR=.xyz第9

6、頁/共63頁第九頁，共64頁。2021-12-16集合論與圖論(t ln)第8講10定理定理(dngl)27(證明證明(4) (4) U xR | xA = A. 證明(zhngmng): (4) A=U x | xA U xR | xA U A | xA =A. U xR | xA = A. #xy第10頁/共63頁第十頁，共64頁。2021-12-16集合論與圖論(t ln)第8講11 同余關(guān)系(gun x): 設(shè)n2,3,4, x,yZ,則 x與y模n同余(be congruent modulo n) xy(mod n) n|(x-y) x-y=kn (kZ) 同余關(guān)系(gun x)是等

7、價關(guān)系(gun x) 0 = kn|kZ, 1 = 1+kn|kZ, 2 = 2+kn|kZ, n-1=(n-1)+kn|kZ.同余同余(congruence)關(guān)系關(guān)系(gun x) 63987542110110第11頁/共63頁第十一頁，共64頁。2021-12-16集合論與圖論(t ln)第8講12例例11 例11: 設(shè) A=1,2,3,4,5,8, 求 R3 = | x,yA xy(mod 3) 的等價(dngji)類, 畫出R3的關(guān)系圖. 解: 1=4=1,4, 2=5=8=2,5,8, 3=3. #142583第12頁/共63頁第十二頁，共64頁。2021-12-16集合論與圖論(t

8、 ln)第8講13商集商集(quotient set) 商集: 設(shè)R是A上等價關(guān)系, A/R = xR | xA 稱為(chn wi)A關(guān)于R的商集, 簡稱A的商集. 顯然 U A/R = A. 例11(續(xù)): A/R3 = 1,4, 2,5,8, 3 .第13頁/共63頁第十三頁，共64頁。2021-12-16集合論與圖論(t ln)第8講14例例12(1) 例12(1): 設(shè)A=a1,a2,an, IA, EA, Rij=IA, 都是A上等價關(guān)系, 求對應(yīng)(duyng)的商集, 其中ai,ajA, ij. 是A上等價關(guān)系嗎? 解: A/IA= a1, a2, an A/EA= a1,a2,

9、an A/Rij= A/IAai,aj - ai,aj. 不是A上等價關(guān)系(非自反). #第14頁/共63頁第十四頁，共64頁。2021-12-16集合論與圖論(t ln)第8講15劃分劃分(hu fn)(partition) 劃分: 設(shè)A, AP(A),若A滿足(mnz) (1) A ; (2) x,y( x,yA xy xy= ) (3) UA = A 則稱A為A的一個劃分, A中元素稱為劃分塊(block).第15頁/共63頁第十五頁，共64頁。2021-12-16集合論與圖論(t ln)第8講16劃分劃分(hu fn)(舉例舉例) 設(shè) A1,A2,AnE, 則以下(yxi)都是劃分:

10、Ai = Ai,Ai, ( i=1,2,n ) Aij = AiAj,AiAj, AiAj, AiAj- ( i,j =1,2,n ij ) A12n = A1A2 An, A1A2 An-1An, A1A2 An-. #第16頁/共63頁第十六頁，共64頁。2021-12-16集合論與圖論(t ln)第8講17劃分劃分(hu fn)(舉例舉例,續(xù)續(xù))AiAi第17頁/共63頁第十七頁，共64頁。2021-12-16集合論與圖論(t ln)第8講18等價關(guān)系與劃分等價關(guān)系與劃分(hu fn)是一一對應(yīng)的是一一對應(yīng)的 定理28: 設(shè)A, 則 (1) R是A上等價關(guān)系 A/R是A的劃分 (2) A

11、是A的劃分 RA是A上等價關(guān)系,其中 xRAy z(zA xz yz) RA稱為由劃分A 所定義(dngy)的等價關(guān)系(同塊關(guān)系). #第18頁/共63頁第十八頁，共64頁。2021-12-16集合論與圖論(t ln)第8講19例例12(2) 例12(2): A=a,b,c, 求A上全體等價關(guān)系. 解: A上不同劃分(hu fn)共有5種:abcabcabcabcabcR1= EA, R2=IA, R3=IA, R4=IA, R5=IA. #第19頁/共63頁第十九頁，共64頁。2021-12-16集合論與圖論(t ln)第8講20Bell數(shù)數(shù)(Bell number) 問題: 給n個對象(d

12、uxing)分類, 共有多少種分法? 答案: Bell數(shù) Bn= (Eric Temple Bell, 18831960) Stirling子集數(shù)(Stirling subset number) : 把n個對象(duxing)分成k個非空子集的分法個數(shù). 遞推公式: .211nnnnknnkkn. 1,1, 122, 11, 0021nnCnnnnnnn.111knknkkn第20頁/共63頁第二十頁，共64頁。2021-12-16集合論與圖論(t ln)第8講21Stirling子集子集(z j)數(shù)數(shù) 遞推公式(gngsh): .111knknkkn剔除一個其余分k類加入一類其余分k-1類自

13、成一類第21頁/共63頁第二十一頁，共64頁。2021-12-16集合論與圖論(t ln)第8講22第一第一(dy)、二類、二類Stirling數(shù)數(shù) 第一類Stirling數(shù)(Stirling number of the first kind): s(n,k) 第二類Stirling數(shù)(Stirling number of the second kind): S(n,k)=kn.) 1()2)(1(),(0kknkxkxxxxxkns.),() 1() 2)(1(),(00knknknxknSkxxxxknSx第22頁/共63頁第二十二頁，共64頁。2021-12-16集合論與圖論(t ln)

14、第8講23Bell數(shù)表數(shù)表(sh bio) nBn nBn1184,14022921,1473510115,97541511678,570552124,213,59762031327,644,437787714190,899,322第23頁/共63頁第二十三頁，共64頁。2021-12-16集合論與圖論(t ln)第8講24第二類第二類Stirling數(shù)表數(shù)表(sh bio)nk01 23456789011012011301314017615011525101601319065151701633013501402118011279661,1701,050266281901255 3,0357,

15、7706,9512,64646236110015119,33034,50142,52522,8275,88075045第24頁/共63頁第二十四頁，共64頁。2021-12-16集合論與圖論(t ln)第8講25例例13 例13: 問A=a,b,c,d上有多少(dusho)種等價關(guān)系? 解: #.1516711) 12 (1443424142434CB第25頁/共63頁第二十五頁，共64頁。2021-12-16集合論與圖論(t ln)第8講26劃分劃分(hu fn)的加細(xì)的加細(xì)(refinement) 劃分的加細(xì): 設(shè)A和B都是集合( jh)A的劃分, 若A的每個劃分塊都包含于B的某個劃分塊中

16、, 則稱A為B的加細(xì). A為B的加細(xì) RARB 第26頁/共63頁第二十六頁，共64頁。2021-12-16集合論與圖論(t ln)第8講27例例14 例14: 考慮(kol)A=a,b,c上的劃分之間的加細(xì). 解: abcabcabcabcabc加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)#第27頁/共63頁第二十七頁，共64頁。2021-12-16集合論與圖論(t ln)第8講28序關(guān)系序關(guān)系(gun x) 偏序,線序,擬序,良序 哈斯圖 特殊(tsh)元素: 最?元, 極?元, ?界, ?確界 (反)鏈 第28頁/共63頁第二十八頁，共64頁。2021-12-16集合論與圖論(t ln)第8講29偏序偏序(

17、partial order)關(guān)系關(guān)系(gun x) 偏序關(guān)系(gun x): 設(shè) RAA 且 A, 若R是自反的, 反對稱的, 傳遞的, 則稱R為偏序關(guān)系(gun x) 通常用 表示偏序關(guān)系(gun x),讀作“小于等于” R xRy x y “嚴(yán)格小于”: x y x y xy 偏序集(poset): , 是A上偏序關(guān)系(gun x) 例子: , , , 第29頁/共63頁第二十九頁，共64頁。2021-12-16集合論與圖論(t ln)第8講30偏序集偏序集, , AR = | x,yA xy , = | x,yA xy , AZ+= x | xZ x0 | = | x,yA x|y 第3

18、0頁/共63頁第三十頁，共64頁。2021-12-16集合論與圖論(t ln)第8講31偏序集偏序集 AP(A), = | x,yA xy 設(shè)A=a,b, A1=,a,b, A2=a,a,b, A3=P(A)=,a,b,a,b,則1 = IA1 , 2 = IA2 3 = IA3 , , 第31頁/共63頁第三十一頁，共64頁。2021-12-16集合論與圖論(t ln)第8講32偏序集偏序集 A, 是由A的一些劃分(hu fn)組成的集合 加細(xì) = | x,y x是y的加細(xì) 設(shè)A=a,b,c, A1=a,b,c,A2=a,b,c, A3=b,a,c,A4=c,a,b,A5=a,b,c 取1=

19、A1,A2,2=A2,A3,3=A1,A2,A3,A4,A5 1 = I1 , 2 = I2, 3 = I3 , , ,. #第32頁/共63頁第三十二頁，共64頁。2021-12-16集合論與圖論(t ln)第8講33哈斯圖哈斯圖(Hasse diagram) 設(shè)是偏序集, x,yA 可比(comparable): x與y可比 x y y x 覆蓋(cover): y覆蓋x x y z( zA x z y ) 哈斯圖: 當(dāng)且僅當(dāng)y覆蓋x時,在x與y之間畫無向邊, 并且(bngqi)x畫在y下方第33頁/共63頁第三十三頁，共64頁。2021-12-16集合論與圖論(t ln)第8講34例例1

20、6(1)(2) 例16: 畫出下列(xili)偏序關(guān)系的哈斯圖. (1) , A=1,2,3,4,5,6,9,10,15 (2) , A=a,b,c, AP(A), A=,a,b,c,a,b,b,c,a,c 解: 12436915510abca,ba,cb,c第34頁/共63頁第三十四頁，共64頁。2021-12-16集合論與圖論(t ln)第8講35例例16(3) 例16: 畫出下列(xili)偏序關(guān)系的哈斯圖. (3) , =A1,A2,A3,A4,A5,A6, A=a,b,c,d A1 = a, b, c, d , A2 = a,b, c,d , A3 = a,c, b,d , A4 =

21、 a, b,c,d , A5 = a, b, c,d , A6 = a,b,c,d 解: A1A2A5A3A4A6#第35頁/共63頁第三十五頁，共64頁。2021-12-16集合論與圖論(t ln)第8講36偏序關(guān)系中的特殊偏序關(guān)系中的特殊(tsh)元素元素 最大元, 最小元 極大元, 極小( j xio)元 上界, 下界 最小上界(上確界), 最大下界(下確界)第36頁/共63頁第三十六頁，共64頁。2021-12-16集合論與圖論(t ln)第8講37最大元最大元, 最小元最小元 設(shè)為偏序集, BA, yB 最大元(maximum/greatest element): y是B的最大元 x

22、( xB x y ) 最小元(minimum/least element): y是B的最小元 x( xB y x )第37頁/共63頁第三十七頁，共64頁。2021-12-16集合論與圖論(t ln)第8講38最大元最大元, 最小元舉例最小元舉例(j l)(例例16(1) 例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的最大元是, B1的最小元是1 B2的最大元是15, B2的最小元是 B3的最大元是, B3的最小元是11243691551012436915510第38頁/共63頁第三十八頁，共64頁。2021-12-

23、16集合論與圖論(t ln)第8講39極大元極大元,極小極小(j xio)元元 設(shè)為偏序集, BA, yB 極大元(maximal element): y是B的極大元 x( xB y x x=y ) 極小( j xio)元(minimal element): y是B的極小( j xio)元 x( xB x y x=y )第39頁/共63頁第三十九頁，共64頁。2021-12-16集合論與圖論(t ln)第8講40極大元極大元,極小極小(j xio)元舉例元舉例(例例16(1) 例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A.

24、B1的極大元是2,3, B1的極小(j xio)元是1 B2的極大元是15, B2的極小(j xio)元是3,5 B3的極大元是4,6,9,15,10, B3的極小(j xio)元是11243691551012436915510第40頁/共63頁第四十頁，共64頁。2021-12-16集合論與圖論(t ln)第8講41上界上界, 下界下界(xi ji) 設(shè)為偏序集, BA, yA 上界(shngji)(upper bound): y是B的上界(shngji) x( xB x y ) 下界(lower bound): y是B的下界 x( xB y x )第41頁/共63頁第四十一頁，共64頁。2

25、021-12-16集合論與圖論(t ln)第8講42上界上界, 下界下界(xi ji)舉例舉例(例例16(1) 例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的上界(shngji)是6, B1的下界是1 B2的上界(shngji)是15, B2的下界是1 B3的上界(shngji)是, B3的下界是11243691551012436915510第42頁/共63頁第四十二頁，共64頁。2021-12-16集合論與圖論(t ln)第8講43最小上界最小上界, 最大下界最大下界(xi ji) 設(shè)為偏序集, BA 最小上界(l

26、east upper bound): 設(shè) C = y | y是B的上界 , C的最小元稱為(chn wi)B的最小上界, 或上確界. 最大下界(greatest lower bound): 設(shè) C = y | y是B的下界 , C的最大元稱為(chn wi)B的最大下界, 或下確界. 第43頁/共63頁第四十三頁，共64頁。2021-12-16集合論與圖論(t ln)第8講44最小上界最小上界,最大下界最大下界(xi ji)舉例舉例(例例16(1) 例16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的最小上界(shngji

27、)是6, B1的最大下界是1 B2的最小上界(shngji)是15, B2的最大下界是1 B3的最小上界(shngji)是, B3的最大下界是11243691551012436915510第44頁/共63頁第四十四頁，共64頁。2021-12-16集合論與圖論(t ln)第8講45特殊特殊(tsh)元素比較元素比較存在(B非空有窮) 存在(B無窮) 唯一 B最大元 (表示不一定)最小元 極大元 (表示一定),B=Z 極小元 上界下界上確界 下確界 第45頁/共63頁第四十五頁，共64頁。2021-12-16集合論與圖論(t ln)第8講46鏈鏈(chain), 反鏈反鏈(antichain)

28、設(shè)為偏序集, BA, 鏈(chain): B是A中的鏈 xy( xByB x與y可比 ) |B|稱為(chn wi)鏈的長度 反鏈(antichain): B是A中的反鏈 xy( xByBxy x與y不可比 ) |B|稱為(chn wi)反鏈的長度第46頁/共63頁第四十六頁，共64頁。2021-12-16集合論與圖論(t ln)第8講47鏈鏈, 反鏈反鏈(舉例舉例(j l) 設(shè)偏序集如圖所示, A=a,b,k.abcdefghijkB1=a,c,d,e是長為4的鏈 上界e,f,g,h, 上確界e 下界(xi ji)a, 下確界aB2=a,e,h是長為3的鏈B3=b,g是長為2的鏈B4=g,h

29、,k是長為3的反鏈 上界,下界(xi ji),上確界,下確界: 無B5=a是長為1的鏈和反鏈B6=a,b,g,h既非鏈,亦非反鏈第47頁/共63頁第四十七頁，共64頁。2021-12-16集合論與圖論(t ln)第8講48定理定理(dngl)31 定理31: 設(shè)為偏序集, A中最長鏈的長度為n, 則 (1) A中存在極大元 (2) A存在n個劃分塊的劃分, 每個劃分塊都是反鏈(即A劃分成n個互不相交的反鏈) 推論(tuln): 設(shè)為偏序集, 若|A|=mn+1,則A中要么存在長度為m+1的反鏈, 要么存在長度為n+1的鏈.第48頁/共63頁第四十八頁，共64頁。2021-12-16集合論與圖論

30、(t ln)第8講49定理定理(dngl)31(舉例舉例)abcdefghijk最長鏈長度(chngd)為6, 如B1=a,c,d,e,f,h, B2=a,c,d,e,f,g, A=a,b,k可以劃分為A 1= a,b,i, c,j, d, e, f, g,h,k ,A 2= a,b, c,i, d,j, e,k, f, g,h |A|=11=25+1, A中既有長度(chngd)為2+1=3的反鏈,也有長度(chngd)為5+1=6的鏈第49頁/共63頁第四十九頁，共64頁。2021-12-16集合論與圖論(t ln)第8講50定理定理(dngl)31(證明證明(1) 定理(dngl)31:

31、 設(shè)為偏序集, A中最長鏈的長度為n, 則 (1) A中存在極大元 證明: (1) 設(shè)B是A中長度為n的最長鏈, B有極大元(也是最大元)y, 則y也是A的極大元, 否則A中還有比y“大”的元素z, B就不是最長鏈.第50頁/共63頁第五十頁，共64頁。2021-12-16集合論與圖論(t ln)第8講51定理定理(dngl)31(證明證明(2) 定理31: 設(shè)為偏序集, A中最長鏈的長度(chngd)為n, 則 (2) A存在n個劃分塊的劃分, 每個劃分塊都是反鏈(即A劃分成n個互不相交的反鏈) 證明: (2) A1 = x | x是A中的極大元 , A2 = x | x是(A-A1)中的極

32、大元 , An = x | x是(A-A1-An-1)中的極大元 , 則 A = A1, A2, An 是滿足要求的劃分.第51頁/共63頁第五十一頁，共64頁。2021-12-16集合論與圖論(t ln)第8講52定理定理(dngl)31(證明證明(2):舉例舉例)abcdefghijk最長鏈長度(chngd)為6, A1 = g, h, k , A2 = f, j , A3 = e, i , A4 = d , A5 = c , A6 = a, b , A = a,b, c, d, e,i, f,j, g,h,k 第52頁/共63頁第五十二頁，共64頁。2021-12-16集合論與圖論(t

33、ln)第8講53定理定理(dngl)31(證明證明(2)續(xù)續(xù)) 證明(續(xù)): 1 A1 = x | x是A中的極大元 , 極大元互相之間不可(bk)比, 所以A1是反鏈, 同理A2,An都是反鏈. 2 顯然A1,A2,An互不相交. 3 最長鏈上的元素分屬A1,A2,An, 所以A1,A2,An都非空. 4 假設(shè)zA-A1-An,則最長鏈上的元素加上z就是長度為n+1的鏈, 矛盾! 所以A=A1A2An. 綜上所述, A= A1,A2,An 確是所求劃分. #第53頁/共63頁第五十三頁，共64頁。2021-12-16集合論與圖論(t ln)第8講54定理定理(dngl)31推論推論(證明證明

34、) 推論: 設(shè)為偏序集, 若|A|=mn+1,則A中要么存在長度為m+1的反鏈, 要么存在長度為n+1的鏈. 證明: (反證)假設(shè)A中既沒有長度為m+1的反鏈, 也沒有長度為n+1的鏈, 則按照(nzho)定理31(2)中要求來劃分A, A至多劃分成n塊, 每塊至多m個元素, 于是A中至多有mn個元素, 這與|A|=mn+1矛盾! #第54頁/共63頁第五十四頁，共64頁。2021-12-16集合論與圖論(t ln)第8講55全序全序(total order)關(guān)系關(guān)系(gun x) 全序關(guān)系(gun x): 若偏序集滿足xy( xAyA x與y可比) 則稱 為全序關(guān)系(gun x), 稱為全序

35、集 全序關(guān)系(gun x)亦稱線序(linear order)關(guān)系(gun x) 例: , 第55頁/共63頁第五十五頁，共64頁。2021-12-16集合論與圖論(t ln)第8講56擬序擬序(quasi-order)關(guān)系關(guān)系(gun x) 擬序關(guān)系: 設(shè) RAA 且 A, 若R是反自反的, 傳遞的, 則稱R為擬序關(guān)系 通常用 表示擬序關(guān)系(對比:“嚴(yán)格小于”) 反自反性與傳遞性蘊(yùn)涵(ynhn)反對稱性 擬序集: , 是A上擬序關(guān)系 例子: 設(shè)AR, BZ+ A, | = | x,yB x|y xy第56頁/共63頁第五十六頁，共64頁。2021-12-16集合論與圖論(t ln)第8講57定理定理(dngl)29 定理29:設(shè) 是非空集合A上偏序關(guān)系, 是A上擬序關(guān)系,則 (1) 是反對稱的; (2) -IA是A上擬序關(guān)系;