1、1,主要內(nèi)容：,4.4 等價關(guān)系與劃分 等價關(guān)系 定義 等價類 集合的劃分 等價關(guān)系與集合劃分的聯(lián)系,2,4.4 等價關(guān)系與集合的劃分 1. 等價關(guān)系（1）,等價關(guān)系：設(shè)A是集合，RAA，若R是自反的、對稱的和傳遞的， 則稱R為A上的等價關(guān)系。 若aRb，則稱a與b等價。 例1：設(shè)A=1,2,3,4,5,6,7,8,RAA,xRy iff 3|(x-y),則R是等價關(guān)系。,等價關(guān)系圖的特點： 每個結(jié)點都有自環(huán) 雙向邊 分成幾個不相連的部分 為什么有這些特點？,等價類,3,4.4 等價關(guān)系與集合的劃分 1. 等價關(guān)系（2）,等價類 定義：設(shè)R是A上的等價關(guān)系，對任意的aA, 稱aR=x|xAxR

2、a為a關(guān)于R的等價類，a為代表元， 不同等價類的個數(shù)為R的秩（若有限）， 以等價類為元素組成的集合aR|aA稱為A關(guān)于R的商集A/R. 例2中：1R=1，4，7，,2R=2，5，8，,A/R=1R，2R，3R= 1，4，7，2，5，8，3,6 性質(zhì)(定理4.4.1): 設(shè)R是A上的等價關(guān)系，A, a,bA,則 (1) aR; (2) aRb iff aR=bR (3) aR=bR 或 aRbR=,3R=3，6,4,證明:(2) aRb iff aR=bR (3) aR=bR 或 aRbR =,證明(2)：(必要性) 對xaR 有xRa, aRb 且R傳遞，, xbR , xRb,故 aRbR

3、,同理可證bRaR 。,(充分性) 若aR=bR , aaR , abR ,因此，aRb 。,根據(jù)(2)得：aR=bR .,(3): 若aRbR 則有caRbR 即caR且cbR, 有cRa且cRb, R對稱，, 又有 aRc,又 R傳遞 aRb,5,4.4 等價關(guān)系與劃分 2. 集合的劃分,定義：設(shè)A，(A)，若滿足： (1) ; (2) 中任意兩個不同元素不相交； (3) =A; 則稱是A的一個劃分，稱中的元素為劃分塊，|稱為的秩。 例2：設(shè)A= a,b,c,d ,以下的i哪些是A的劃分？ 1=a,b, c,d, 2=a,b,c,c,d, 3=a,b,c,d, 4=a,b,c,d 上節(jié)課的

4、例題1：A=1,2,3,4,5,6,7,8,RAA,xRy iff 3|(x-y), A/R= 1,4,7,2,5,8,3,6 是A的一個劃分。,求等價關(guān)系,6,4.4 等價關(guān)系與劃分 3.等價關(guān)系與集合劃分的聯(lián)系(1),定理4.4.2: 設(shè)R是非空集合A上的等價關(guān)系，則A/R是A的一個劃分。 （由等價類的性質(zhì)可推出,見P94） 定理4.4.3: 設(shè)R1,R2是非空集A上的等價關(guān)系,則R1=R2 iff A/R1=A/R2 。, 必有aR2A/R2 使aR2=xR1=yR1, x,yaR2 xR2a且yR2a R2對稱, aR2y,又 R2傳遞 xR2y 即R2 所以，R1R2 同理可證 R2

5、R1,證明 必要性是顯然的。 (充分性) 對R1,有xR1=yR1 且xxR1, yyR1 A/R1=A/R2,一個等價關(guān)系誘導(dǎo)出的劃分是唯一的,所以 R1=R2,設(shè) RII,xRy iff 3|(x-y),R誘導(dǎo)的劃分=？,7,4.4 等價關(guān)系與劃分 3.等價關(guān)系與集合劃分的聯(lián)系（2）,定理4.4.4 設(shè)為非空集合A的一個劃分，定義A上的關(guān)系R: aRb iff a和b屬于同一劃分塊，,則a與b屬于同一劃分塊。, b與a屬于同一劃分塊，, bRa,(傳遞性) 若aRb且bRc，,則a與b屬于同一劃分塊Bi,且b與c屬于同一劃分塊Bj, b屬于劃分塊Bi 同時又有b屬于劃分塊Bj Bi=Bj 因此，a,b和c屬于同一劃分塊, aRc,證明(自反性) aA, a與a屬于同一劃分塊，,則R是A上的等價關(guān)系。, aRa。 (對稱性) 若aRb,8,4.4 等價關(guān)系與劃分 3.等價關(guān)系與集合劃分的聯(lián)系(3),例3：求例2中劃分1和3所確定的等價關(guān)系。 A= a,b,c,d , 1=a,b,c,d, 3=a,b,c,d 解：R1=(a,ba,b)(c,dc,d) =,