等價(jià)關(guān)系與劃分

1、7.6 等價(jià)關(guān)系與劃分 1 等價(jià)關(guān)系是一類重要的關(guān)系。 定義7.15(等價(jià)關(guān)系) 設(shè)R非空集合上的關(guān)系，如果R是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。 設(shè)R是一個(gè)等價(jià)關(guān)系，若R，稱x等價(jià)于y，記作xy。 例 設(shè)A=1,2,3，R1，R2，R3是A上的關(guān)系 R1=, R2=,， R3=,2例 設(shè)A為某班學(xué)生的集合，討論下列關(guān)系是否為等價(jià)關(guān)系。 R1=|x, yA x與y同年生 R2=|x, yA x與y同姓 R3=|x, yA x的年齡比y小解：R1是等價(jià)關(guān)系； R2是等價(jià)關(guān)系； R3不是等價(jià)關(guān)系； 3 如tsr(R)必為一個(gè)等價(jià)關(guān)系 例 A=1,2,3，A上的關(guān)系R=, tsr(R)

2、=,通過(guò)閉包運(yùn)算將任意的關(guān)系R構(gòu)造成為一個(gè)等價(jià)關(guān)系4 對(duì)R求三種閉包共有6種順序，問(wèn)每種順序的運(yùn)算結(jié)果是否一定為等價(jià)關(guān)系？ 不一定。 由于對(duì)稱閉包不一定保持關(guān)系的傳遞性，因此先求傳遞閉包后求對(duì)稱閉包得到的關(guān)系不一定是等價(jià)關(guān)系 例 A=1,2,3，A上的關(guān)系R=, str(R)=IA, 顯然str(R)不是等價(jià)關(guān)系 用閉包運(yùn)算去構(gòu)造等價(jià)關(guān)系時(shí)，傳遞閉包運(yùn)算應(yīng)該放在對(duì)稱閉包運(yùn)算的后面5 例 設(shè)AN，R=|x, yAxy (mod 3) 為A上的關(guān)系，其中xy (mod 3)叫做x與y模3相等，其含義為x除以3的余數(shù)與y除以3的余數(shù)相等。證明R為A上的等價(jià)關(guān)系。 證明: xA，有xx (mod 3)

3、，即R，所以R是自反的。 x,yA，若xy (mod 3)，則有yx (mod 3)。所以R是對(duì)稱的。 x,y,zA，若xy (mod 3)，yz (mod 3)，則有xz (mod 3)。所以R是傳遞的。 綜上R為A上的等價(jià)關(guān)系。 6例：已知A=P(X), CX, x, yA, R xyC。 證明R為A上的等價(jià)關(guān)系.證明：（1）xA，由于xx=C R, 所以R是自反的。（2）x,yA，RxyCyxCR, 所以R是對(duì)稱的。（3）x,y,zA，若R，R， 則有xyC， yzC。 xz=(xy)(yz)C R. 所以R是傳遞的。 綜上所證，R是A上的等價(jià)關(guān)系。7 畫出等價(jià)關(guān)系R=|x,yAxy(m

4、od 3)的關(guān)系圖 ，其中A=1,2,8。 不難看出，上述關(guān)系圖被分為三個(gè)分離（互不連通）的部分。每部分中的數(shù)兩兩都有關(guān)系(模3相等)，位于不同部分中的數(shù)之間則沒(méi)有關(guān)系。稱每一部分中的頂點(diǎn)構(gòu)成了一個(gè)等價(jià)類。 8 定義7.16（等價(jià)類） 設(shè)R為非空集合上的等價(jià)關(guān)系，xA，令xR=y|yAxRy，稱xR為x關(guān)于R的等價(jià)類，簡(jiǎn)稱為x的等價(jià)類，簡(jiǎn)記為x。 說(shuō)明： x的等價(jià)類是A中所有與x等價(jià)的元素構(gòu)成的集合。9 集合A=1,2,8上的等價(jià)關(guān)系 R=|x, yAxy（mod 3）等價(jià)類是： 1=4=7=1，4，7 2=5=8=2，5，8 3=6=3，610 將模3的等價(jià)關(guān)系加以推廣，可以得到整數(shù)集合Z上

5、的模n等價(jià)關(guān)系。 對(duì)于任意的整數(shù)x和y，定義模n相等關(guān)系： xyxy（mod n） 易證是整數(shù)集合Z上的等價(jià)關(guān)系。11將Z中所有的整數(shù)根據(jù)它們除以n的余數(shù)分類如下： 余數(shù)為0的數(shù)，其形式為nz，zZ 余數(shù)為1的數(shù)，其形式為nz+1，zZ 余數(shù)為n-1的數(shù)，其形式為nz+n-1，zZ 以上構(gòu)成了n個(gè)等價(jià)類： i=n+i=2n+i=nz+i|zZ，i=0,1,n-112 定理7.14（等價(jià)類的性質(zhì)） 設(shè)R為非空集合A上的等價(jià)關(guān)系，則 （1）x是A的非空子集 （2）x，yA，如果xRy，則x=y （3）x，yA，如果xRy，則x與y不交 （4）x|xA =A定理的含義： （1）：任何等價(jià)類都是集合A

6、的非空子集 （2）和（3）：在A中任何兩個(gè)元素，它們的等價(jià)類相等或不相交，不能部分相交。 （4）：所有等價(jià)類的并集就是A （3）和（4）：等價(jià)關(guān)系將A劃分成若干個(gè)互不相交的子集13 例集合A=1,2,8上的等價(jià)關(guān)系R=|x, yAxy（mod 3） 等價(jià)類是1, 4, 7、2, 5, 8、3, 614 定義7.17（商集）設(shè)R為非空集合A上的等價(jià)關(guān)系，以R的所有等價(jià)類為元素的集合叫做A在R下的商集，記作A/R，即A/R=xR|xA 例 集合A=1,2,8上的等價(jià)關(guān)系R=|x, yAxy（mod 3）等價(jià)類是1, 4, 7、2, 5, 8、3, 6。 所以A在R下的商集為1, 4, 7, 2,

7、5, 8, 3, 6。 A在R下的商集也可寫成1, 2, 3。 整數(shù)集Z在模n等價(jià)關(guān)系下的商集是 nz+i|zZ | i=0,1,n-1 或0, 1, ., n-1 15 定義7.18（劃分）設(shè)A為非空集合，若A的子集族（P(A)，是A的子集構(gòu)成的集合）滿足以下的條件： （1） （2）xy（x，yxy xy=） 即中任意兩個(gè)集合不相交 （3）=A，即中所有集合的并集等于A 則稱是A的一個(gè)劃分，稱中的元素為A的劃分塊 16 例設(shè)A=a,b,c,d，給定1,2,3,4,5,6如下，判別它們是否為A的劃分。 1= a，b，c ， d 2= a，b ， c ， d 3= a ， a，b，c，d 4=

8、a，b ， c 5= ， a，b ， c，d 6= a， a ， b，c，d 其中1,2是A的劃分，3,4,5,6不是A的劃分17 集合A的等價(jià)關(guān)系與集合A的劃分一一對(duì)應(yīng) （1）每個(gè)A上的等價(jià)關(guān)系所產(chǎn)生的商集是一個(gè)劃分 （2）每個(gè)A的劃分決定一個(gè)A上等價(jià)關(guān)系R 通過(guò)A的一個(gè)劃分來(lái)確定等價(jià)關(guān)系R的方法是：對(duì)任意的x,yA，R當(dāng)且僅當(dāng)x和y在的同一劃分塊中。 例 A=a,b,c,d的一個(gè)劃分為=a,b,c,d 則對(duì)應(yīng)的等價(jià)關(guān)系為： R=, IA18a b cda bdc 劃分的圖形表示 一般用“圓”來(lái)表示一個(gè)劃分，將圓劃分成若干份來(lái)表示劃分塊。例如: 1= a，b，c ， d 2= a，b ， c ， d 19 例7.18 給出A=1，2，3上