1、3-10 3-10 等價關系與等價類等價關系與等價類 離散數學復習復習自反性自反性（ reflexive ）定義：定義：設設R為定義在集合為定義在集合A上的二元關系，如果上的二元關系，如果 對于每個對于每個xA，都有都有R,即即xRx，則稱，則稱二元關系二元關系R是自反的。是自反的。對稱性（對稱性（ symmetric symmetric ）定義：定義：設設R為定義在集合為定義在集合A上的二元關系，如果上的二元關系，如果對于每個對于每個x，yA，每當每當R，就有，就有R，則稱集合，則稱集合A上關系上關系R是對稱的。是對稱的。傳遞性（ transitive ）定義定義:設設R為定義在集合為定義在

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

3、若R是自反的，對稱的和傳遞的是自反的，對稱的和傳遞的，則稱，則稱R為集為集合合A上的等價關系。上的等價關系。例如例如n平面上三角形集合中，三角形的相似關平面上三角形集合中，三角形的相似關系；系；n同學集合同學集合A=a,b,c,d,e,f,g,A中的關系中的關系R：住在同一宿舍；：住在同一宿舍；n同性關系。同性關系。例例1 1 設設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。驗證驗證R R是集合是集合T T上的等價關系。上的等價關系。100101100110100

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

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

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

7、aRb當且僅當a,b在同一個分塊中。則R是一個等價關系。、a與a在同一個分塊中，則有aRa ，即自反性、 a與b在同一個分塊中，則b與a在同一個分塊中，即若aRb，有bRa，故R是對稱的。、 a與b在同一個分塊中， b與c在同一個分塊中，而由劃分的定義b只能屬于且屬于一個分塊，故a與c必在同一分塊中，即若有aRb,bRc則必有aRc，即傳遞性成立。所以R是一個等價關系。SA/R定理定理3集合A的一個劃分確定A的元素間的一個等價關系。說明說明n等價關系 等價類 商集 劃分nA上的等價關系與A的劃分是一一對應的。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設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誘導的劃分S=a,b,c,d,e.反之,若A的劃分S=a,b,c,d,e,則所誘導的等價關系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充分性：反之設aR1|a AaR2|a A對任意aR1 A/R1則有cR2 A/R2,使得aR1cR2