等價關(guān)系與等價類.ppt

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

2、，對稱的和傳遞的，則稱R為集合A上的等價關(guān)系。,例如,平面上三角形集合中，三角形的相似關(guān)系； 同學(xué)集合A=a,b,c,d,e,f,g,A中的關(guān)系R：住在同一宿舍； 同性關(guān)系。,例1 設(shè)T1，2，3，4，,R1，1，1，4，4，1， 4，4，2，2，2，3， 3，2，3，3。 驗證R是集合T上的等價關(guān)系。,例2 設(shè)A = 1, 2, , 8 , 如下定義A上的關(guān)系R:,R = | x, yA且xy（mod3) 證明R為A上的等價關(guān)系。,證明: xA , 因為x-x=0=03,所以R; x,yA, 若x-y=3t(t為整數(shù)）, 則有: y-x=-3t,即 R; x,y,zA, 若x-y=3t, y

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

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

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

6、,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)的等價關(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 A R1R2，對任意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 所以 R1 a aR1 b