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

1、3-10 3-10 等價(jià)關(guān)系與等價(jià)類等價(jià)關(guān)系與等價(jià)類 離散數(shù)學(xué)復(fù)習(xí)復(fù)習(xí)自反性自反性（ reflexive ）定義：定義：設(shè)設(shè)R為定義在集合為定義在集合A上的二元關(guān)系，如果上的二元關(guān)系，如果 對于每個(gè)對于每個(gè)xA，都有都有R,即即xRx，則稱，則稱二元關(guān)系二元關(guān)系R是自反的。是自反的。對稱性（對稱性（ symmetric symmetric ）定義：定義：設(shè)設(shè)R為定義在集合為定義在集合A上的二元關(guān)系，如果上的二元關(guān)系，如果對于每個(gè)對于每個(gè)x，yA，每當(dāng)每當(dāng)R，就有，就有R，則稱集合，則稱集合A上關(guān)系上關(guān)系R是對稱的。是對稱的。傳遞性（ transitive ）定義定義:設(shè)設(shè)R為定義在集合為定義在

2、集合A上的二元關(guān)系，上的二元關(guān)系， 如果對于任意如果對于任意x，y，zA， 每當(dāng)每當(dāng) R且且 R，就有就有 R，稱關(guān)系，稱關(guān)系R在在A上是傳遞的。上是傳遞的。1R110M100001abc1RR1 是對稱的。1R a,a,a,b ,b,a,c,c abc2R2R110M110001R2 是自反的、對稱的、傳遞的。2R a,a,a,b ,b,a,b,b ,c,c 等價(jià)關(guān)系與等價(jià)類的基本概念等價(jià)關(guān)系與等價(jià)類的基本概念1等價(jià)關(guān)系的基本性質(zhì)等價(jià)關(guān)系的基本性質(zhì)2主要內(nèi)容主要內(nèi)容商集與集合的劃分商集與集合的劃分3 3一、定義一、定義定義定義1:設(shè)設(shè)R為定義在集合為定義在集合A上的一個(gè)關(guān)系，上的一個(gè)關(guān)系，若

3、若R是自反的，對稱的和傳遞的是自反的，對稱的和傳遞的，則稱，則稱R為集為集合合A上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。例如例如n平面上三角形集合中，三角形的相似關(guān)平面上三角形集合中，三角形的相似關(guān)系；系；n同學(xué)集合同學(xué)集合A=a,b,c,d,e,f,g,A中的關(guān)系中的關(guān)系R：住在同一宿舍；：住在同一宿舍；n同性關(guān)系。同性關(guān)系。例例1 1 設(shè)設(shè)T T1 1，2 2，3 3，4 4，R R1 1，1 1，1 1，4 4，4 4，1 1， 4 4，4 4，2 2，2 2，2 2，3 3， 3 3，2 2，3 3，3 3。驗(yàn)證驗(yàn)證R R是集合是集合T T上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。100101100110100

4、1RM輊犏犏犏=犏犏犏臌2100110011001011001100110011001100110100110011001RM輊輊輊犏犏犏犏犏犏犏犏犏=犏犏犏犏犏犏犏犏犏臌臌臌例例2 2 設(shè)設(shè)A = 1, 2, A = 1, 2, , 8 , , 8 , 如下定義如下定義A A上的關(guān)系上的關(guān)系R:R: R = | x, y A且且xy（mod3) 證明證明R為為A上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。證明證明: xA , 因?yàn)閤-x=0=03,所以R; x,yA, 若x-y=3t(t為整數(shù)）, 則有: y-x=-3t,即 R; x,y,zA, 若x-y=3t, y-z=3s, 則有: x-z=3(t+s

5、),即 R. 關(guān)系圖如下圖所示關(guān)系圖如下圖所示.等價(jià)類等價(jià)類定義定義2：設(shè)設(shè)R為集合為集合A上的等價(jià)關(guān)系，對任意上的等價(jià)關(guān)系，對任意aA，集合集合 aR=x|x A,R 稱為元素稱為元素a關(guān)于關(guān)于R的等價(jià)類。的等價(jià)類。例2可求出三個(gè)不同的等價(jià)類1R=4R=7R=1,4,72R=5R=8R=2,5,83R=6R=3,6定義定義3:集合A上的等價(jià)關(guān)系R，其等價(jià)類集合aR|a A稱作A關(guān)于R的商集商集(quotient set) 。記作A/R (1) a aR (2)定理定理1:設(shè)給定集合A上的等價(jià)關(guān)系R，對于a,bA，若R,iff aR=bR。 二、性質(zhì)二、性質(zhì) (3)設(shè)R為集合A上的等價(jià)關(guān)系，則

6、任意a,b A,若 RRba 4Ra AaA R,則證明證明設(shè)集合A上的一個(gè)等價(jià)關(guān)系R，則aR是A的一個(gè)子集，則所有這樣的子集可做成商集A/R1、A/R=aR|a A中,aR=A 2、 對任意a A，都有aRa，即aaR，即A中的每一個(gè)元素都屬于一個(gè)分塊。3、A的每個(gè)元素只能屬于一個(gè)分塊反證設(shè)abR ，acR,且bR cR，則bRa,cRa成立，所以有aRc,所以bRc，即bR cR所以A/R是A上對應(yīng)于R的一個(gè)劃分。定理定理2：集合A上的等價(jià)關(guān)系R，決定了A的一個(gè)劃分，該劃分就是商集A/R。三三 商集與集合的劃分商集與集合的劃分證明：證明：設(shè)集合A的一個(gè)劃分SS1,S2Sm，現(xiàn)定義一個(gè)關(guān)系：

7、aRb當(dāng)且僅當(dāng)a,b在同一個(gè)分塊中。則R是一個(gè)等價(jià)關(guān)系。、a與a在同一個(gè)分塊中，則有aRa ，即自反性、 a與b在同一個(gè)分塊中，則b與a在同一個(gè)分塊中，即若aRb，有bRa，故R是對稱的。、 a與b在同一個(gè)分塊中， b與c在同一個(gè)分塊中，而由劃分的定義b只能屬于且屬于一個(gè)分塊，故a與c必在同一分塊中，即若有aRb,bRc則必有aRc，即傳遞性成立。所以R是一個(gè)等價(jià)關(guān)系。SA/R定理定理3集合A的一個(gè)劃分確定A的元素間的一個(gè)等價(jià)關(guān)系。說明說明n等價(jià)關(guān)系 等價(jià)類 商集 劃分nA上的等價(jià)關(guān)系與A的劃分是一一對應(yīng)的。R1a,bxa,b=R2=c xc=R3= d,exd,e=R=R1R2R3例例3A=

8、a,b,c,d,e，Sa,b,c,d,e，求由，求由S確定的確定的R。例4設(shè)A=a,b,c,d,e,R=a,a,a,b,a,c,b,b,b,a,b,c,c,c,c,a,c,b,d,d,d,e,e,e,e,d,其有向圖如圖所示,則R誘導(dǎo)的劃分S=a,b,c,d,e.反之,若A的劃分S=a,b,c,d,e,則所誘導(dǎo)的等價(jià)關(guān)系R=a,b,ca,b,cd,ed,e=a,a,a,b,a,c,b,b,b,a,b,c,c,c,c,a,c,b,d,d,d,e,e,e,e,d證明 必要性：A/R1aR1|a A，A/R2 aR2|a AR1R2，對任意a A, 有aR1x|x A,aR1x=x|x A,aR2x= aR2所以有aR1|a AaR2|a A即有A/R1=A/R2充分性：反之設(shè)aR1|a AaR2|a A對任意aR1 A/R1則有cR2 A/R2,使得aR1cR2