離散數(shù)學(xué) 3-9 集合的劃分和覆蓋3-10 等價(jià)關(guān)系與等價(jià)類_第1頁
離散數(shù)學(xué) 3-9 集合的劃分和覆蓋3-10 等價(jià)關(guān)系與等價(jià)類_第2頁
離散數(shù)學(xué) 3-9 集合的劃分和覆蓋3-10 等價(jià)關(guān)系與等價(jià)類_第3頁
離散數(shù)學(xué) 3-9 集合的劃分和覆蓋3-10 等價(jià)關(guān)系與等價(jià)類_第4頁
離散數(shù)學(xué) 3-9 集合的劃分和覆蓋3-10 等價(jià)關(guān)系與等價(jià)類_第5頁
已閱讀5頁,還剩36頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡介

離散數(shù)學(xué)DiscreteMathematics

山東科技大學(xué)信息科學(xué)與工程學(xué)院3-8關(guān)系的閉包關(guān)系的自反閉包關(guān)系的對稱閉包關(guān)系的傳遞閉包一、關(guān)系的閉包定義定義3-8.1:設(shè)R是X上的二元關(guān)系,如果另外有一個(gè)關(guān)系R’滿足:(1)R’是自反的(對稱的,傳遞的);(2)R’R;(3)對于任何自反的(對稱的,傳遞的)關(guān)系R’’,如果有R’’R,就有R’’R’。則稱關(guān)系R’為R的自反(對稱,傳遞)閉包。記作r(R),(s(R),t(R))例:設(shè)集合X={x,y,z},X上的關(guān)系R={<x,x>,<x,y>,<y,z>},則:自反閉包r(R)={<x,x>,<x,y>,<y,z>,<y,y>,<z,z>}對稱閉包s(R)={<x,x>,<x,y>,<y,z>,<y,x>,<z,y>}傳遞閉包t(R)={<x,x>,<x,y>,<y,z>,<x,z>}

由閉包的定義可以知道,構(gòu)造關(guān)系R的閉包方法就是向R中加入必要的有序?qū)?,使其具有所希望的性質(zhì)。下面定理體現(xiàn)了這一點(diǎn)。二、關(guān)系的性質(zhì)與閉包的關(guān)系1、定理3-8.1:設(shè)R是X上的二元關(guān)系,則(1)R是自反的,當(dāng)且僅當(dāng)r(R)=R(2)R是對稱的,當(dāng)且僅當(dāng)s(R)=R(3)R是傳遞的,當(dāng)且僅當(dāng)t(R)=R證明只證明①①必要性:令R為自反.由于RR,并取右方R為S,以及任何包含R的自反關(guān)系T,有ST,可見R滿足自反閉包定義,即r(R)=R.

充分性:由自反閉包定義R是自反的.二、關(guān)系的性質(zhì)與閉包的關(guān)系1、定理3-8.1:設(shè)R是X上的二元關(guān)系,則(1)R是自反的,當(dāng)且僅當(dāng)r(R)=R(2)R是對稱的,當(dāng)且僅當(dāng)s(R)=R(3)R是傳遞的,當(dāng)且僅當(dāng)t(R)=R2、定理3-8.2:設(shè)R是集合X上的二元關(guān)系,則r(R)=Rx證明:RRx,Rx是自反的,定義的前兩條滿足了。設(shè)R”滿足RR”,R”是自反的,<x,y>Rx,則<x,y>R或<x,y>x。如果<x,y>R則由RR”,<x,y>R”。如果<x,y>x則必有x=y,即<x,x>x,由R”的自反性,則<x,y>R”,總之均有<x,y>R”,所以RXR”,滿足定義第三條。得r(R)=Rx。對關(guān)系矩陣而言,r(R)的關(guān)系矩陣只要將MR的對角元置1即可。3、定理3-8.3:設(shè)R是集合X上的二元關(guān)系,則s(R)=RRc。證明:RRRc滿足定義第一條。<x,y>RRc<x,y>R<x,y>Rc<y,x>Rc<y,x>R<y,x>RRc,所以RRc是對稱的,滿足定義的第二條。如果RR”,且R”是對稱的,<x,y>RRc,則<x,y>R或<x,y>Rc,如<x,y>R,由RR”,則<x,y>R”,如<x,y>Rc則<y,x>R則<y,x>R”,又因R”對稱,所以<x,y>R”,所以RRcR”,滿足定義第三條。得s(R)=RRc。4、定理3-8.4:設(shè)R是集合X上的二元關(guān)系,則

t(R)=R(i)=RR(2)R(3)…證明首先證明Rt(R).用歸納法證明如下:

基礎(chǔ)步:根據(jù)傳遞閉包定義,Rt(R);

歸納步:假設(shè)n≥1時(shí)Rnt(R),欲證Rn+1t(R)令x,yX,則:xRn+1yxRn

*Ry(z)(xRnz∧zRy)

xRnz∧zRy

xt(R)z∧zt(R)yxt(R)y

因此,Rnt(R).于是,Ri

t(R).次證t(R)Ri,由于包含R的傳遞關(guān)系都包含t(R),且RRi,因此只需證明Ri是傳遞即可.令x,y,zX,則

x(Ri)y∧y(Ri)z

(j)(xRjy)∧(k)(yRkz)

xRjy∧yRkz

xRjy

*yRkz

xRj+kz

x(Ri)z因此,Ri是傳遞的.綜上可知,t(R)=Ri.例題1:設(shè)A={a,b,c},R是A上的二元關(guān)系,且給定R={<a,b>,<b,c>,<c,a>},求r(R),s(R),t(R)。解:r(R)={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}s(R)={<a,b>,<b,a>,<b,c>,<c,b>,<c,a>,<a,c>}為了求t(R),先寫出

010MR=001100010010001MR2=001001=100100100010001010010MR3=100001=001010100100繼續(xù)計(jì)算求解,會(huì)得出R4=R=R3n+1,R5=R2=R3n+2,R6=R3=R3n+3所以t(R)=RR2

R35、定理3-8.5:設(shè)X含有n個(gè)元素的集合,R是X上的二元關(guān)系,則存在一個(gè)正整數(shù)k≤n,使得t(R)=RR(2)R(3)…R(K)例:A={a,b,c,d},R={<a,b>,<a,c>,<b,c>,<b,d>},求t(R)。解:R(2)={<a,c>,<a,d>},R(3)=R(4)=所以t(R)=RR(2)R(3)R(4)={<a,b>,<a,c>,<b,c>,

<b,d>,<a,d>}6、Warshall算法設(shè)R是n個(gè)元素集合X上的二元關(guān)系,(1)A是R的關(guān)系矩陣;(2)置i=1;(3)對所有j,如果aji=1,則對k=1,2,…,n

ajk=ajk+aik(第i行與第j行邏輯相加,記于第j行)(4)i=i+1;(5)如果i≤n,則轉(zhuǎn)到步驟(3),否則停止。舉例P124例3Warshall算法的C語言實(shí)現(xiàn)7、求閉包的關(guān)系圖作法:(1)r(R)在R的基礎(chǔ)上添加自回路,使得每點(diǎn)均有自回路。(2)s(R)在R中兩結(jié)點(diǎn)間只有一條弧時(shí),再添一條反向弧,使兩結(jié)點(diǎn)間或是0條弧,或是兩條弧,原來兩點(diǎn)間沒有弧不能添加。(3)t(R)在R中如結(jié)點(diǎn)x通過有向路能通到z,則添加一條從x到z的有向弧,其中包括如x能達(dá)到自身,則必須添從x到x的自回路。8、定理3-8.6:若RAA,則①rs(R)=sr(R)②rt(R)=tr(R)③st(R)ts(R)作業(yè)P127:(1),(2),(7):a,c3-9集合的劃分和覆蓋

在集合的研究中,除了常常把兩個(gè)集合相互比較之外,有時(shí)也要把一個(gè)集合分成若干子集加以討論。一、集合的劃分和覆蓋定義3-9.1:若把一個(gè)集合A分成若干個(gè)叫做分塊的非空集合,使得A中每個(gè)元素至少屬于一個(gè)分塊,那么這些分塊的全體構(gòu)成的集合叫做A的一個(gè)覆蓋。如果A中每個(gè)元素屬于且僅屬于一個(gè)分塊,那么這些分塊的全體構(gòu)成的集合叫做A的一個(gè)劃分(或分劃)。一、集合的劃分和覆蓋定義3-9.1:令A(yù)為非空集合,S={S1,S2,···,Sm},其中①Si,②SiA,③Si=A,集合S稱作集合A的覆蓋。如果除以上條件外,另有Si∩Sj=(ij),則稱S是A的劃分(或分劃)。例如,A={a,b,c},考慮下列子集:S={{a,b},{b,c}},Q={{a},{a,b},{a,c}}D={{a},{b,c}},G={{a,b,c}}E={{a},,{c}},F(xiàn)={{a},{a,c}}則:D、E、G、S、Q是A的覆蓋D、E、G是A的劃分F既不是劃分也不是覆蓋。

若是劃分則必是覆蓋,其逆不成立。任何一個(gè)集合的最小劃分,就是由這個(gè)集合的全部元素組成的一個(gè)分塊的集合。如G是A的最小劃分。任何一個(gè)集合的最大劃分,就是由每個(gè)元素構(gòu)成一個(gè)單元素分塊的集合。如E是A的最大劃分。二、交叉劃分定義3-9.2:若{A1,A2,···,Ar}與{B1,B2,···,Bs}是同一集合A的兩種劃分,則其中所有AiBj組成的集合,稱為原來兩種劃分的交叉劃分。例如,所有生物的集合X,可分割成{P,A},其中P表示所有植物的集合,A表示所有動(dòng)物的集合,又X也可分割成{E,F(xiàn)},其中E表示史前生物,F(xiàn)表示史后生物,則其交叉劃分為Q={PE,PF,AE,AF}。定理3-9.1:設(shè){A1,A2,···,Ar}與{B1,B2,···,Bs}是同一集合X的兩種劃分,則其交叉劃分亦是原集合的一種劃分。加細(xì)定義3-9.3:給定X的任意兩個(gè)劃分{A1,A2,···,Ar}與{B1,B2,···,Bs},若對每一個(gè)Aj均有Bk使AjBk,則{A1,A2,···,Ar}稱為{B1,B2,···,Bs}的加細(xì)。定理3-9.2:任何兩種劃分的交叉劃分,都是原來各劃分的一種加細(xì)。證明:設(shè){A1,A2,···,Ar}與{B1,B2,···,Bs}的交叉劃分為T,對T中任意元素AiBj必有AiBjAi,AiBjBj,故T必是原劃分的加細(xì)。作業(yè)P130:(4)、(5)3-10等價(jià)關(guān)系與等價(jià)類一、等價(jià)關(guān)系定義3-10.1:設(shè)R為集合A上的二元關(guān)系,若R是自反的、對稱的和傳遞的,則稱R為等價(jià)關(guān)系。aRb,稱為a等價(jià)于b。由于R是對稱的,a等價(jià)b即b等價(jià)a,反之亦然,a與b彼此等價(jià)。例如,平面上三角形集合中,三角形的相似關(guān)系是等價(jià)關(guān)系。鑒于空集合中的二元關(guān)系是等價(jià)關(guān)系,是一種平凡情形,因此,一般討論非空集合上的等價(jià)關(guān)系。例題1:設(shè)集合T={1,2,3,4},R={<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>}。驗(yàn)證R是T上的等價(jià)關(guān)系。解:畫出R的關(guān)系圖每個(gè)結(jié)點(diǎn)都有自回路,說明R是自反的。任意兩個(gè)結(jié)點(diǎn)間或沒有弧線連接,或有成對弧出現(xiàn),故R是對稱的。從序偶表示式中,可以看出,R是傳遞的。故R是T上的等價(jià)關(guān)系。模m等價(jià)是I(整數(shù)集合)或其子集上的等價(jià)關(guān)系,并且是一類重要的等價(jià)關(guān)系。定義:設(shè)m為一正整數(shù),而a,bI。若存在k,使a-b=km,則稱a與b是模m等價(jià),記為ab(modm)。如1與4是模3等價(jià),1與7是模3等價(jià),4與7是模3等價(jià),4與1是模3等價(jià),7與1是模3等價(jià),1與1是模3等價(jià),……例題2:設(shè)I是整數(shù)集,R={(a,b)|ab(modk),a,bI},證明R是等價(jià)關(guān)系。證明:設(shè)任意a,b,cI(1)因?yàn)閍-a=k0,所以<a,a>R,R是自反的。(2)若<a,b>R,ab(modk),a-b=kt(t為整數(shù)),則b-a=-kt,所以ba(modk),<b,a>R,R是對稱的。(3)若<a,b>R,<b,c>R,ab(modk),bc(modk),則a-b=kt,b-c=ks(t,s為整數(shù)),a-c=k(t+s),所以ac(modk),<a,c>R,R是傳遞的。因此R是等價(jià)關(guān)系。二、等價(jià)類1、定義3-10.2:設(shè)R為集合A上的等價(jià)關(guān)系,對任何aA,集合[a]R={x|xA,aRx}稱為元素a形成的R等價(jià)類。顯然,等價(jià)類[a]R非空,因?yàn)閍[a]R。例題3:設(shè)I是整數(shù)集,R是模3關(guān)系,即R={(x,y)|xy(mod3),x,yI},確定由I的元素所產(chǎn)生的等價(jià)類。解:由I的元素所產(chǎn)生的等價(jià)類是[0]R={…,-6,-3,0,3,6,…}[1]R={…,-5,-2,1,4,7,…}[2]R={…,-4,-1,2,5,8,…}例:A={52張撲克牌},R1={<a,b>|a與b同花,a,b是撲克},R2={<a,b>|a與b同點(diǎn),a,b是撲克},即R1是同花關(guān)系,R2是同點(diǎn)關(guān)系,R1和R2都是等價(jià)關(guān)系。R1把A分為四類同花類,R2把A分為13類同點(diǎn)類。例:A={0,1,2,3,4,5},R={<0,0>,<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,1>,<2,3>,<3,1>,<3,2>,<4,4>,<4,5>,<5,4>,<5,5>},R把A分成了三個(gè)等價(jià)類:{0},{1,2,3},{4,5}。2、定理3-10.1:設(shè)給定集合A上的等價(jià)關(guān)系R,對于a,bA有aRb

iff[a]R=[b]R。證明:假定[a]R=[b]R,因?yàn)閍[a]R,故a[b]R,即aRb。反之,若aRb,則bRa,設(shè)c[a]RaRcbRcc[b]R即[a]R[b]R同理,若aRb,設(shè)c[b]RbRcaRcc[a]R即[b]R[a]R由此證得若aRb,則[a]R=[b]R。三、商集1、定義3-10.3:集合A上的等價(jià)關(guān)系R,其等價(jià)類的集合{[a]R|aA}稱為A關(guān)于R的商集,記作A/R。如例題1中商集T/R={[1]R,[2]R},例題3中商集I/R={[0]R,[1]R,[2]R}

等價(jià)關(guān)系R把A的元素分為若干類,各類之間沒有公共元素。確定的R是對集合A進(jìn)行的一個(gè)劃分。2、定理3-10.2:集合A上的等價(jià)關(guān)系R

溫馨提示

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

評論

0/150

提交評論