離散數(shù)學(xué) 關(guān)系4_第1頁(yè)
離散數(shù)學(xué) 關(guān)系4_第2頁(yè)
離散數(shù)學(xué) 關(guān)系4_第3頁(yè)
離散數(shù)學(xué) 關(guān)系4_第4頁(yè)
離散數(shù)學(xué) 關(guān)系4_第5頁(yè)
已閱讀5頁(yè),還剩58頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第8講等價(jià)關(guān)系與序關(guān)系內(nèi)容提要等價(jià)關(guān)系,等價(jià)類,商集劃分,第二類Stirling數(shù)偏序,線序,擬序,良序特殊元素:最?元,極?元,?界,?確界(反)鏈2022/11/51等價(jià)(equivalence)關(guān)系定義同余關(guān)系等價(jià)類商集劃分劃分的加細(xì)Stirling子集數(shù)2022/11/52等價(jià)(equivalence)關(guān)系定義等價(jià)關(guān)系:設(shè)RAA且A,若R是自反的,對(duì)稱的,傳遞的,則稱R為等價(jià)關(guān)系例9:判斷是否等價(jià)關(guān)系(A是某班學(xué)生):R1={<x,y>|x,yAx與y同年生}R2={<x,y>|x,yAx與y同姓}R3={<x,y>|x,yAx的年齡不比y小}R4={<x,y>|x,yAx與y選修同門課程}R5={<x,y>|x,yAx的體重比y重}2022/11/53例9(續(xù))2022/11/54例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)=t(s(r(R)))解:st(R)ts(R),sr(R)=rs(R),…tsr(R)=trs(R)=rts(R)str(R)=srt(R)=rst(R)2022/11/55例10(續(xù))2022/11/56等價(jià)類(equivalenceclass)等價(jià)類:設(shè)R是A上等價(jià)關(guān)系,xA,令[x]R={y|yAxRy},稱[x]R為x關(guān)于R的等價(jià)類,簡(jiǎn)稱x的等價(jià)類,簡(jiǎn)記為[x].等價(jià)類性質(zhì):[x]R;xRy[x]R=[y]R;xRy[x]R[y]R=;U{[x]R|xA}=A.2022/11/57定理27定理27:設(shè)R是A上等價(jià)關(guān)系,x,yA,(1)[x]R(2)xRy[x]R=[y]R;(3)xRy[x]R[y]R=;(4)U{[x]R|xA}=A.證明:(1)R自反xRxx[x]R[x]R.x2022/11/58定理27(證明(2))(2)xRy[x]R=[y]R;證明:(2)只需證明[x]R[y]R和[x]R[y]R.()z,z[x]RxRy

zRxxRy

zRyz[y]R

.

[x]R[y]R.()同理可證.xyz2022/11/59定理27(證明(3))(3)xRy[x]R[y]R=;證明:(3)(反證)假設(shè)z,z[x]R[y]R,則z[x]R[y]RzRxzRyxRzzRy

xRy,這與xRy矛盾![x]R[y]R=.xyz2022/11/510定理27(證明(4))(4)U{[x]R|xA}=A.證明:(4)A=U{{x}|xA}U{[x]R

|xA}U{A

|xA}=A.U{[x]R|xA}=A.#xy2022/11/511同余關(guān)系:設(shè)n{2,3,4,…},x,yZ,則x與y模n同余(becongruentmodulon)xy(modn)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)系

639875421101102022/11/512例11例11:設(shè)A={1,2,3,4,5,8},求R3={<x,y>|x,yAxy(mod3)}的等價(jià)類,畫(huà)出R3的關(guān)系圖.解:[1]=[4]={1,4},[2]=[5]=[8]={2,5,8},[3]={3}.#1425832022/11/513商集(quotientset)商集:設(shè)R是A上等價(jià)關(guān)系,A/R={[x]R|xA}稱為A關(guān)于R的商集,簡(jiǎn)稱A的商集.顯然UA/R=A.例11(續(xù)):A/R3

={{1,4},{2,5,8},{3}}.2022/11/514例12(1)例12(1):設(shè)A={a1,a2,…,an},IA,EA,Rij=IA{<ai,aj>,<aj,ai>}都是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/IA{{ai,aj}}-{{ai},{aj}}.不是A上等價(jià)關(guān)系(非自反).#2022/11/515劃分(partition)劃分:設(shè)A,AP(A),若A滿足(1)A;(2)x,y(x,yAxyxy=)(3)UA=A則稱A為A的一個(gè)劃分,A中元素稱為劃分塊(block).2022/11/516劃分(舉例)設(shè)A1,A2,…,AnE,則以下都是劃分:

Ai={Ai,~Ai},(i=1,2,…,n)

Aij={AiAj,~AiAj,Ai~Aj,

~Ai~Aj}-{}(i,j=1,2,…,nij)……

A12…n={~A1~A2…~An,…,~A1~A2…~An-1An,…A1A2…An}-{}.#2022/11/517劃分(舉例,續(xù))Ai~Ai2022/11/518等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的定理28:設(shè)A,則(1)R是A上等價(jià)關(guān)系A(chǔ)/R是A的劃分(2)A是A的劃分RA是A上等價(jià)關(guān)系,其中xRAy

z(zAxzyz)RA稱為由劃分A

所定義的等價(jià)關(guān)系(同塊關(guān)系).#2022/11/519例12(2)例12(2):A={a,b,c},求A上全體等價(jià)關(guān)系.解:A上不同劃分共有5種:abcabcabcabcabcR1=EA,R2=IA{<b,c><c,b>},R3=IA{<a,c><c,a>},R4=IA{<a,b><b,a>},R5=IA.#2022/11/520Bell數(shù)(Bellnumber)問(wèn)題:給n個(gè)對(duì)象分類,共有多少種分法?答案:Bell數(shù)Bn=

(EricTempleBell,1883~1960)Stirling子集數(shù)(Stirlingsubsetnumber):把n個(gè)對(duì)象分成k個(gè)非空子集的分法個(gè)數(shù).

遞推公式:2022/11/521Stirling子集數(shù)遞推公式:剔除一個(gè)其余分k類加入一類其余分k-1類自成一類2022/11/522第一、二類Stirling數(shù)第一類Stirling數(shù)(Stirlingnumberofthefirstkind):s(n,k)

第二類Stirling數(shù)(Stirlingnumberofthesecondkind):S(n,k)=2022/11/523Bell數(shù)表nBn

nBn1184,14022921,1473510115,97541511678,570552124,213,59762031327,644,437787714190,899,3222022/11/524第二類Stirling數(shù)表2022/11/525例13例13:問(wèn)A={a,b,c,d}上有多少種等價(jià)關(guān)系?解:#2022/11/526劃分的加細(xì)(refinement)劃分的加細(xì):設(shè)A和B都是集合A的劃分,若A的每個(gè)劃分塊都包含于B的某個(gè)劃分塊中,則稱A為B的加細(xì).

A為B的加細(xì)RARB

2022/11/527例14例14:考慮A={a,b,c}上的劃分之間的加細(xì).解:abcabcabcabcabc加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)加細(xì)#2022/11/528序關(guān)系偏序,線序,擬序,良序哈斯圖特殊元素:最?元,極?元,?界,?確界(反)鏈2022/11/529偏序(partialorder)關(guān)系偏序關(guān)系:設(shè)RAA且A,若R是自反的,反對(duì)稱的,傳遞的,則稱R為偏序關(guān)系通常用?表示偏序關(guān)系,讀作“小于等于”<x,y>RxRyx?y“嚴(yán)格小于”:x?yx?y

xy偏序集(poset):<A,?>,?是A上偏序關(guān)系例子:<A,>,<A,|>,<A,>,<,?加細(xì)>2022/11/530偏序集<A,>,<A,>,<A,|>AR={<x,y>|x,yAxy},

={<x,y>|x,yAxy},AZ+={x|xZx>0}|={<x,y>|x,yAx|y}2022/11/531偏序集<A,>AP(A),={<x,y>|x,yAxy}設(shè)A={a,b},A1={,{a},},A2={{a},{a,b}},A3=P(A)={,{a},,{a,b}},則1=IA1{<,{a}>,<,>}2=IA2{<{a},{a,b}>}3=IA3{<,{a}>,<,>,<,{a,b}>,<{a},{a,b}>,<,{a,b}>}2022/11/532偏序集<,?加細(xì)>A,是由A的一些劃分組成的集合?加細(xì)

={<x,y>|x,yx是y的加細(xì)}設(shè)A={a,b,c},A1={{a,b,c}},A2={{a},{b,c}},A3={,{a,c}},A4={{c},{a,b}},A5={{a},,{c}}取1={A1,A2},2={A2,A3},3={A1,A2,A3,A4,A5}?1=I1{<A2,A1>},?2=I2,?3=I3{<A2,A1>,<A3,A1>,<A4,A1>,<A5,A1>,<A5,A2>,<A5,A3>,<A5,A4>}.#2022/11/533哈斯圖(Hassediagram)設(shè)<A,?>是偏序集,x,yA可比(comparable):x與y可比x?yy?x覆蓋(cover):y覆蓋x

x?y

z(zAx?z?y)哈斯圖:當(dāng)且僅當(dāng)y覆蓋x時(shí),在x與y之間畫(huà)無(wú)向邊,并且x畫(huà)在y下方2022/11/534例16(1)(2)例16:畫(huà)出下列偏序關(guān)系的哈斯圖.(1)<A,|>,A={1,2,3,4,5,6,9,10,15}(2)<A,>,A={a,b,c},AP(A),A={,{a},,{c},{a,b},{b,c},{a,c}}解:12436915510{a}{c}{a,b}{a,c}{b,c}2022/11/535例16(3)例16:畫(huà)出下列偏序關(guān)系的哈斯圖.(3)<,?加細(xì)>,={A1,A2,A3,A4,A5,A6},A={a,b,c,d}A1={{a},,{c},1jfrd7x},A2={{a,b},{c,d}},A3={{a,c},{b,d}},A4={{a},{b,c,d}},A5={{a},,{c,d}},A6={{a,b,c,d}}解:A1A2A5A3A4A6#2022/11/536偏序關(guān)系中的特殊元素最大元,最小元極大元,極小元上界,下界最小上界(上確界),最大下界(下確界)2022/11/537最大元,最小元設(shè)<A,?>為偏序集,BA,yB最大元(maximum/greatestelement):y是B的最大元x(xBx?y)最小元(minimum/leastelement):y是B的最小元x(xBy?x)2022/11/538最大元,最小元舉例(例16(1))例16(1):<A,|>,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的最小元是{1}12436915510124369155102022/11/539極大元,極小元設(shè)<A,?>為偏序集,BA,yB極大元(maximalelement):y是B的極大元x(xBy?xx=y)極小元(minimalelement):y是B的極小元x(xBx?yx=y)2022/11/540極大元,極小元舉例(例16(1))例16(1):<A,|>,A={1,2,3,4,5,6,9,10,15}

B1={1,2,3},B2={3,5,15},B3=A.B1的極大元是{2,3},B1的極小元是{1}B2的極大元是{15},B2的極小元是{3,5}B3的極大元是{4,6,9,15,10},B3的極小元是{1}12436915510124369155102022/11/541上界,下界設(shè)<A,?>為偏序集,BA,yA上界(upperbound):y是B的上界x(xBx?y)下界(lowerbound):y是B的下界x(xBy?x)2022/11/542上界,下界舉例(例16(1))例16(1):<A,|>,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的下界是{1}12436915510124369155102022/11/543最小上界,最大下界設(shè)<A,?>為偏序集,BA最小上界(leastupperbound):設(shè)C={y|y是B的上界},C的最小元稱為B的最小上界,或上確界.最大下界(greatestlowerbound):設(shè)C={y|y是B的下界},C的最大元稱為B的最大下界,或下確界.2022/11/544最小上界,最大下界舉例(例16(1))例16(1):<A,|>,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的最大下界是{1}12436915510124369155102022/11/545特殊元素比較2022/11/546鏈(chain),反鏈(antichain)設(shè)<A,?>為偏序集,BA,鏈(chain):B是A中的鏈xy(

xByBx與y可比)|B|稱為鏈的長(zhǎng)度反鏈(antichain):B是A中的反鏈xy(

xByBxyx與y不可比)

|B|稱為反鏈的長(zhǎng)度2022/11/547鏈,反鏈(舉例)設(shè)偏序集<A,?>如圖所示,A={a,b,…,k}.abcdefghijkB1={a,c,d,e}是長(zhǎng)為4的鏈上界{e,f,g,h},上確界{e}

下界{a},下確界{a}B2={a,e,h}是長(zhǎng)為3的鏈B3={b,g}是長(zhǎng)為2的鏈B4={g,h,k}是長(zhǎng)為3的反鏈上界,下界,上確界,下確界:無(wú)B5={a}是長(zhǎng)為1的鏈和反鏈B6={a,b,g,h}既非鏈,亦非反鏈2022/11/548定理31定理31:設(shè)<A,?>為偏序集,A中最長(zhǎng)鏈的長(zhǎng)度為n,則(1)A中存在極大元(2)A存在n個(gè)劃分塊的劃分,每個(gè)劃分塊都是反鏈(即A劃分成n個(gè)互不相交的反鏈)推論:設(shè)<A,?>為偏序集,若|A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈,要么存在長(zhǎng)度為n+1的鏈.2022/11/549定理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},hp7jvrf,{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的鏈2022/11/550定理31(證明(1))定理31:設(shè)<A,?>為偏序集,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)鏈.2022/11/551定理31(證明(2))定理31:設(shè)<A,?>為偏序集,A中最長(zhǎng)鏈的長(zhǎng)度為n,則(2)A存在n個(gè)劃分塊的劃分,每個(gè)劃分塊都是反鏈(即A劃分成n個(gè)互不相交的反鏈)證明:(2)A1={x|x是A中的極大元},A2={x|x是(A-A1)中的極大元},…An={x|x是(A-A1-…-An-1)中的極大元},則A={A1,A2,…,An}是滿足要求的劃分.2022/11/552定理31(證明(2):舉例)abcdefghijk最長(zhǎng)鏈長(zhǎng)度為6,A1={g,h,k},A2={f,j},A3={e,i},A4=7r1vrvz,A5={c},A6={a,b},A={{a,b},{c},tj79rln,{e,i},{f,j},{g,h,k}}2022/11/553定理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=A1A2…An.綜上所述,A={A1,A2,…,An}確是所求劃分.#2022/11/554定理31推論(證明)推論:設(shè)<A,?>為偏序集,若|A|=mn+1,則A中要么存在長(zhǎng)度為m+1的反鏈,要么存在長(zhǎng)度為n+1的鏈.證明:(反證)假設(shè)A中既沒(méi)有長(zhǎng)度為m+1的反鏈,也沒(méi)有長(zhǎng)度為n+1的鏈,則按照定理31(2)中要求來(lái)劃分A,A至多劃分成n塊,每塊至多m個(gè)元素,于是A中至多有mn個(gè)元素,這與|A|=mn+1矛盾!#2022/11/555全序(totalorder)關(guān)系全序關(guān)系:若偏序集<A,?>滿足xy(xAyAx與y可比)則稱?為全序關(guān)系,稱<A,?>為全序集全序關(guān)系亦稱線序(linearor

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論