離散數(shù)學(xué)關(guān)系精品課件

1、離散數(shù)學(xué)關(guān)系2022/9/25集合論與圖論第8講1第1頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講2等價(jià)(equivalence)關(guān)系定義同余關(guān)系等價(jià)類商集劃分劃分的加細(xì)Stirling子集數(shù)第2頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講3等價(jià)(equivalence)關(guān)系定義等價(jià)關(guān)系: 設(shè) RAA 且 A, 若R是自反的, 對(duì)稱的, 傳遞的,則稱R為等價(jià)關(guān)系例9: 判斷是否等價(jià)關(guān)系(A是某班學(xué)生): R1=|x,yAx與y同年生R2=|x,yAx與y同姓R3=|x,yAx的年齡不比y小R4=|x

2、,yAx與y選修同門課程R5=|x,yAx的體重比y重第3頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講4例9(續(xù))定義自反對(duì)稱傳遞等價(jià)關(guān)系R1x與y同年生R2x與y同姓R3x的年齡不比y小R4x與y選修同門課程R5x的體重比y重第4頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講5例10例10: 設(shè) RAA 且 A, 對(duì)R依次求三種閉包共有6種不同順序, 其中哪些順序一定導(dǎo)致等價(jià)關(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 )第5頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講6例10(續(xù))tsr(R)=trs(R) =rts( R )str(R)=srt(R)=rst( R )自反對(duì)稱傳遞等價(jià)關(guān)系(等價(jià)閉包)第6頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講7等價(jià)類(equivalence class)等價(jià)類: 設(shè)R是A上等價(jià)關(guān)系

4、,xA,令 xR= y | yA xRy ,稱xR為x關(guān)于R的等價(jià)類, 簡(jiǎn)稱x的等價(jià)類,簡(jiǎn)記為x.等價(jià)類性質(zhì): xR ;xRy xR=yR ;xRy xRyR= ;U xR | xA =A.第7頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講8定理27定理27:設(shè)R是A上等價(jià)關(guān)系,x,yA, (1) xR (2) xRy xR=yR ; (3) xRy xRyR= ; (4) U xR | xA =A. 證明: (1) R自反xRxxxRxR.x第8頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講9定理27

5、(證明(2) (2) xRy xR=yR ;證明: (2) 只需證明xRyR和xRyR.() z, zxRxRy zRxxRy zRy zyR . xRyR.() 同理可證.xyz第9頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講10定理27(證明(3)(3) xRy xRyR= ;證明: (3) (反證) 假設(shè)z, zxRyR, 則 zxRyR zRxzRy xRzzRy xRy, 這與xRy矛盾! xRyR=.xyz第10頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講11定理27(證明(4) (4)

6、 U xR | xA = A. 證明: (4) A=U x | xA U xR | xA U A | xA =A. U xR | xA = A. #xy第11頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講12同余關(guān)系: 設(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)系是等價(jià)關(guān)系0 = kn|kZ, 1 = 1+kn|kZ, 2 = 2+kn|kZ, n-1=(n-1)+kn|kZ.同余(congruence)關(guān)系 6398754211011

7、0第12頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講13例11例11: 設(shè) A=1,2,3,4,5,8, 求R3 = | x,yA xy(mod 3) 的等價(jià)類, 畫出R3的關(guān)系圖.解: 1=4=1,4, 2=5=8=2,5,8, 3=3. #142583第13頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講14商集(quotient set)商集: 設(shè)R是A上等價(jià)關(guān)系, A/R = xR | xA 稱為A關(guān)于R的商集, 簡(jiǎn)稱A的商集. 顯然 U A/R = A.例11(續(xù)): A/R3 = 1,4,

8、2,5,8, 3 .第14頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講15例12(1)例12(1): 設(shè)A=a1,a2,an, IA, EA,Rij=IA,都是A上等價(jià)關(guān)系, 求對(duì)應(yīng)的商集, 其中ai,ajA, ij. 是A上等價(jià)關(guān)系嗎?解: A/IA= a1, a2, an A/EA= a1,a2,an A/Rij= A/IAai,aj - ai,aj. 不是A上等價(jià)關(guān)系(非自反). #第15頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講16劃分(partition)劃分: 設(shè)A, AP(A),若A

9、滿足 (1) A ; (2) x,y( x,yA xy xy= ) (3) UA = A 則稱A為A的一個(gè)劃分, A中元素稱為劃分塊(block).第16頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講17劃分(舉例)設(shè) A1,A2,AnE, 則以下都是劃分: 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-. #第17頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/

10、9/25集合論與圖論第8講18劃分(舉例,續(xù))AiAi第18頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講19等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的定理28: 設(shè)A, 則(1) R是A上等價(jià)關(guān)系 A/R是A的劃分(2) A是A的劃分 RA是A上等價(jià)關(guān)系,其中xRAy z(zA xz yz) RA稱為由劃分A 所定義的等價(jià)關(guān)系(同塊關(guān)系). #第19頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講20例12(2)例12(2): A=a,b,c, 求A上全體等價(jià)關(guān)系.解: A上不同劃分共有5種:abcabcabcabca

11、bcR1= EA, R2=IA, R3=IA, R4=IA, R5=IA. #第20頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講21Bell數(shù)(Bell number)問題: 給n個(gè)對(duì)象分類, 共有多少種分法?答案: Bell數(shù) Bn= (Eric Temple Bell, 18831960)Stirling子集數(shù)(Stirling subset number) : 把n個(gè)對(duì)象分成k個(gè)非空子集的分法個(gè)數(shù). 遞推公式: 第21頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講22Stirling子集數(shù)遞推公

12、式: 剔除一個(gè)其余分k類加入一類其余分k-1類自成一類第22頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講23第一、二類Stirling數(shù)第一類Stirling數(shù)(Stirling number of the first kind): s(n,k) 第二類Stirling數(shù)(Stirling number of the second kind): S(n,k)=第23頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講24Bell數(shù)表 nBn nBn1184,14022921,1473510115,97541

13、511678,570552124,213,59762031327,644,437787714190,899,322第24頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講25第二類Stirling數(shù)表nk01 23456789011012011301314017615011525101601319065151701633013501402118011279661,1701,0502662819012553,0357,7706,9512,64646236110015119,33034,50142,52522,8275,88075045第25頁，共63頁，

14、2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講26例13例13: 問A=a,b,c,d上有多少種等價(jià)關(guān)系?解: #第26頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講27劃分的加細(xì)(refinement)劃分的加細(xì): 設(shè)A和B都是集合A的劃分, 若A的每個(gè)劃分塊都包含于B的某個(gè)劃分塊中, 則稱A為B的加細(xì). A為B的加細(xì) RARB 第27頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講28例14例14: 考慮A=a,b,c上的劃分之間的加細(xì).解: abcabcabcabca

15、bc加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)#第28頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講29序關(guān)系偏序,線序,擬序,良序哈斯圖特殊元素: 最?元, 極?元, ?界, ?確界(反)鏈 第29頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講30偏序(partial order)關(guān)系偏序關(guān)系: 設(shè) RAA 且 A, 若R是自反的, 反對(duì)稱的, 傳遞的, 則稱R為偏序關(guān)系通常用表示偏序關(guān)系,讀作“小于等于”R xRy xy“嚴(yán)格小于”: xy xy xy偏序集(poset): , 是A上偏序關(guān)系例子: , , , 第3

16、0頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講31偏序集, , AR = | x,yA xy , = | x,yA xy ,AZ+= x | xZ x0 | = | x,yA x|y 第31頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講32偏序集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 , , 第32頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/

17、9/25集合論與圖論第8講33偏序集A, 是由A的一些劃分組成的集合加細(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=A1,A2,2=A2,A3,3=A1,A2,A3,A4,A51 = I1 , 2 = I2, 3 = I3 , , ,. #第33頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講34哈斯圖(Hasse diagram)設(shè)是偏序集, x,yA可比(comparable):x與y可比 xy yx覆蓋(cover):y覆蓋x xy z( zA

18、 xzy )哈斯圖: 當(dāng)且僅當(dāng)y覆蓋x時(shí),在x與y之間畫無向邊, 并且x畫在y下方第34頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講35例16(1)(2)例16: 畫出下列偏序關(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第35頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講36例16(3)例16: 畫出下列偏序關(guān)系的哈斯圖.(3) , =A1,A

19、2,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 = a, b,c,d , A5 = a, b, c,d , A6 = a,b,c,d 解: A1A2A5A3A4A6#第36頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講37偏序關(guān)系中的特殊元素最大元, 最小元極大元, 極小元上界, 下界最小上界(上確界), 最大下界(下確界)第37頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講38最大元, 最小元設(shè)

20、為偏序集, BA, yB最大元(maximum/greatest element): y是B的最大元 x( xB xy )最小元(minimum/least element): y是B的最小元 x( xB yx )第38頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講39最大元, 最小元舉例(例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的最小元是1124369155101

21、2436915510第39頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講40極大元,極小元設(shè)為偏序集, BA, yB極大元(maximal element): y是B的極大元 x( xB yx x=y )極小元(minimal element): y是B的極小元 x( xB xy x=y )第40頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講41極大元,極小元舉例(例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的極大元

22、是2,3, B1的極小元是1 B2的極大元是15, B2的極小元是3,5B3的極大元是4,6,9,15,10, B3的極小元是11243691551012436915510第41頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講42上界, 下界設(shè)為偏序集, BA, yA上界(upper bound): y是B的上界 x( xB xy )下界(lower bound): y是B的下界 x( xB yx )第42頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講43上界, 下界舉例(例16(1)例16(1): ,

23、A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的上界是6, B1的下界是1 B2的上界是15, B2的下界是1 B3的上界是, B3的下界是11243691551012436915510第43頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講44最小上界, 最大下界設(shè)為偏序集, BA最小上界(least upper bound): 設(shè) C = y | y是B的上界 , C的最小元稱為B的最小上界, 或上確界. 最大下界(greatest lower bound): 設(shè) C = y | y是B的下界

24、 , C的最大元稱為B的最大下界, 或下確界. 第44頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講45最小上界,最大下界舉例(例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的最小上界是6, B1的最大下界是1 B2的最小上界是15, B2的最大下界是1 B3的最小上界是, B3的最大下界是11243691551012436915510第45頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講46特殊元素比較存在(B非空有

25、窮)存在(B無窮)唯一B最大元(表示不一定)最小元極大元 (表示一定),B=Z極小元上界下界上確界下確界第46頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講47鏈(chain), 反鏈(antichain)設(shè)為偏序集, BA,鏈(chain): B是A中的鏈 xy( xByB x與y可比 ) |B|稱為鏈的長(zhǎng)度反鏈(antichain): B是A中的反鏈 xy( xByBxy x與y不可比 ) |B|稱為反鏈的長(zhǎng)度第47頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講48鏈, 反鏈(舉例)設(shè)偏序集如圖所示

26、, A=a,b,k.abcdefghijkB1=a,c,d,e是長(zhǎng)為4的鏈 上界e,f,g,h, 上確界e 下界a, 下確界aB2=a,e,h是長(zhǎng)為3的鏈B3=b,g是長(zhǎng)為2的鏈B4=g,h,k是長(zhǎng)為3的反鏈 上界,下界,上確界,下確界: 無B5=a是長(zhǎng)為1的鏈和反鏈B6=a,b,g,h既非鏈,亦非反鏈第48頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講49定理31定理31: 設(shè)為偏序集, A中最長(zhǎng)鏈的長(zhǎng)度為n, 則 (1) A中存在極大元 (2) A存在n個(gè)劃分塊的劃分, 每個(gè)劃分塊都是反鏈(即A劃分成n個(gè)互不相交的反鏈)推論: 設(shè)為偏序集, 若

27、|A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈, 要么存在長(zhǎng)度為n+1的鏈.第49頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講50定理31(舉例)abcdefghijk最長(zhǎng)鏈長(zhǎng)度為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中既有長(zhǎng)度為2+1=3的反鏈,也有長(zhǎng)度為5+1=6的鏈第50頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期

28、六2022/9/25集合論與圖論第8講51定理31(證明(1)定理31: 設(shè)為偏序集, A中最長(zhǎng)鏈的長(zhǎng)度為n, 則 (1) A中存在極大元證明: (1) 設(shè)B是A中長(zhǎng)度為n的最長(zhǎng)鏈, B有極大元(也是最大元)y, 則y也是A的極大元, 否則A中還有比y“大”的元素z, B就不是最長(zhǎng)鏈.第51頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講52定理31(證明(2)定理31: 設(shè)為偏序集, A中最長(zhǎng)鏈的長(zhǎng)度為n, 則 (2) A存在n個(gè)劃分塊的劃分, 每個(gè)劃分塊都是反鏈(即A劃分成n個(gè)互不相交的反鏈)證明: (2) A1 = x | x是A中的極大元 ,

29、 A2 = x | x是(A-A1)中的極大元 , An = x | x是(A-A1-An-1)中的極大元 , 則 A = A1, A2, An 是滿足要求的劃分.第52頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講53定理31(證明(2):舉例)abcdefghijk最長(zhǎng)鏈長(zhǎng)度為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 第53頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六20

30、22/9/25集合論與圖論第8講54定理31(證明(2)續(xù))證明(續(xù)): 1 A1 = x | x是A中的極大元 , 極大元互相之間不可比, 所以A1是反鏈, 同理A2,An都是反鏈. 2 顯然A1,A2,An互不相交. 3 最長(zhǎng)鏈上的元素分屬A1,A2,An, 所以A1,A2,An都非空. 4 假設(shè)zA-A1-An,則最長(zhǎng)鏈上的元素加上z就是長(zhǎng)度為n+1的鏈, 矛盾! 所以A=A1A2An. 綜上所述, A= A1,A2,An 確是所求劃分. #第54頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講55定理31推論(證明)推論: 設(shè)為偏序集, 若|

31、A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈, 要么存在長(zhǎng)度為n+1的鏈.證明: (反證)假設(shè)A中既沒有長(zhǎng)度為m+1的反鏈, 也沒有長(zhǎng)度為n+1的鏈, 則按照定理31(2)中要求來劃分A, A至多劃分成n塊, 每塊至多m個(gè)元素, 于是A中至多有mn個(gè)元素, 這與|A|=mn+1矛盾! #第55頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講56全序(total order)關(guān)系全序關(guān)系: 若偏序集滿足xy( xAyA x與y可比) 則稱為全序關(guān)系, 稱為全序集全序關(guān)系亦稱線序(linear order)關(guān)系例: , 第56頁，共63頁，2022年，5月20日，1點(diǎn)51分，星期六2022/9/25集合論與圖論第8講57擬序(quasi-order)關(guān)系擬序關(guān)系