離散數(shù)學(xué)課件：3-9 等價(jià)關(guān)系與等價(jià)類

1、等價(jià)關(guān)系等價(jià)關(guān)系：若集合：若集合A上的二元關(guān)系上的二元關(guān)系R是：是：(1)自反的，自反的，(2)對(duì)稱的，對(duì)稱的，(3)傳遞的，傳遞的，則稱則稱R是是A上的等價(jià)關(guān)系。若上的等價(jià)關(guān)系。若aRb，則稱，則稱a等價(jià)于等價(jià)于b.(一一) 等價(jià)關(guān)系的定義等價(jià)關(guān)系的定義 判斷以下判斷以下整數(shù)集整數(shù)集(Z)上的關(guān)系是否是等價(jià)關(guān)系上的關(guān)系是否是等價(jià)關(guān)系.關(guān)系關(guān)系自反自反對(duì)稱對(duì)稱傳遞傳遞等價(jià)關(guān)系等價(jià)關(guān)系空關(guān)系空關(guān)系全域關(guān)系全域關(guān)系相等關(guān)系相等關(guān)系同余關(guān)系同余關(guān)系整除關(guān)系整除關(guān)系“”關(guān)系關(guān)系” ”關(guān)系關(guān)系YNYYYYYYYYYYYNYYNNYNYNYYYNNN九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類 判斷以下關(guān)系是

2、否是等價(jià)關(guān)系判斷以下關(guān)系是否是等價(jià)關(guān)系.(5)在一群人的集合上年齡相等的關(guān)系；在一群人的集合上年齡相等的關(guān)系；(2)同一平面上三角形之間的全等關(guān)系；同一平面上三角形之間的全等關(guān)系；(3) 同一平面上三角形之間的相似關(guān)系；同一平面上三角形之間的相似關(guān)系；(4) 直線間的平行關(guān)系；直線間的平行關(guān)系；(6)在一群人的集合上的朋友關(guān)系在一群人的集合上的朋友關(guān)系. 不自反不自反不一定，可能不傳遞不一定，可能不傳遞(1)命題演算中命題演算中“”關(guān)系關(guān)系； 九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類證：證：(1)因?yàn)橐驗(yàn)閍-a=k 0, (2) 若若 R, 即即a b(mod k), 設(shè)設(shè)Z 為整數(shù)集，為整數(shù)

3、集，k為正整數(shù)，令為正整數(shù)，令R=| x,y Z x y(mod k),稱稱R為為模模k同余關(guān)系同余關(guān)系，并稱，并稱x與與y模模k相等相等. 證明證明R是等是等價(jià)價(jià)關(guān)系關(guān)系.任取任取a, b, c Z， 所以所以 R ； 可令可令a-b=kt(t為整數(shù)為整數(shù))，所以所以b a(mod k),即即 R. 則則b-a=-kt，(3) 若若 R, R,即即a b(mod k), b c(mod k), 可令可令a-b=kt, b-c=ks(其中其中t, s為整數(shù)為整數(shù))，那么那么a-c= (a-b)+(b-c) =k(t+s).所以所以a c(mod k),即即 R. 綜上，綜上，R是等價(jià)關(guān)系是等價(jià)

4、關(guān)系. 九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類等價(jià)類：等價(jià)類：設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系，上的等價(jià)關(guān)系， a A，令，令 aR=x x A aRx稱稱aR為為a關(guān)于關(guān)于R的的等價(jià)類等價(jià)類，簡(jiǎn)稱為，簡(jiǎn)稱為a的等價(jià)類，簡(jiǎn)記為的等價(jià)類，簡(jiǎn)記為a. a稱為等價(jià)類稱為等價(jià)類aR的的代表元素代表元素. 設(shè)集合設(shè)集合A=1,2,3,10，R是模是模3同余關(guān)系，求同余關(guān)系，求由由R 所產(chǎn)生的等價(jià)類所產(chǎn)生的等價(jià)類.3R=1R=5R= 8R證：證：6R=9R=3,6,9.= 7R= 10R=1,4,7,104R2R= 2, 5, 8(二二) 等價(jià)類等價(jià)類九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類等價(jià)

5、類的性質(zhì)等價(jià)類的性質(zhì)性質(zhì)一：性質(zhì)一：設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, a, b A, 有有 aRbaR=bR.(1) 若若aRb, 證：證：任取任取c aR ,則則c aR aRc cRa cRb bRc c bR 故故 aR bR .同理可證同理可證bR aR . 所以所以aR = bR .(2) 反之，若反之，若aR=bR,a aR a bR bRa aRb.九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類則由則由R是自反的可得是自反的可得等價(jià)類的性質(zhì)等價(jià)類的性質(zhì)性質(zhì)二：性質(zhì)二：設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, a A, 有有 aR是非空的是非空的. a

6、 A,因因R是自反的，故是自反的，故a aR，證：證：所以所以aR非空非空.性質(zhì)三：性質(zhì)三：設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系,有有(1) a A, a aR, 證：證： .RaAaA (2)由由aR的定義可得的定義可得aR A， .RaAaA 從而從而 .RaAAa 故故九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類性質(zhì)四：性質(zhì)四：設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, a, b A, 有有或者或者aR=bR，或者，或者aRbR=.等價(jià)類的性質(zhì)等價(jià)類的性質(zhì) a, b A，假設(shè)，假設(shè)aRbR ,證：證：則則 c aRbR，從而從而aRc, bRc.因因R是傳遞的，是

7、傳遞的，所以，由性質(zhì)一知：所以，由性質(zhì)一知：aR=bR.故故aRb.因因R是對(duì)稱的是對(duì)稱的 ，故故cRb.九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類(三三) 商集商集商集商集： 設(shè)設(shè)R為非空集合為非空集合A上的等價(jià)關(guān)系，其等價(jià)類上的等價(jià)關(guān)系，其等價(jià)類集合集合aR a A稱為稱為A關(guān)于關(guān)于R的的商集商集(quotient set)，記為，記為A/R.A/R = 設(shè)集合設(shè)集合A=1,2,3,10，R是模是模3同余關(guān)系，求同余關(guān)系，求A關(guān)于關(guān)于R的商集的商集. 1R ,2R ,3R解：解：九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類 由由a與與a在同一分塊中，得在同一分塊中，得 R ，(四四) 等價(jià)關(guān)系與

8、劃分等價(jià)關(guān)系與劃分定理一定理一 非空集合非空集合A上的任一等價(jià)關(guān)系上的任一等價(jià)關(guān)系R誘導(dǎo)了誘導(dǎo)了A的一的一個(gè)劃分個(gè)劃分A/R.證：證： 略（由等價(jià)類的性質(zhì)二、三、四可得）略（由等價(jià)類的性質(zhì)二、三、四可得）.設(shè)設(shè)S=A1, A2, , Ak，定義關(guān)系，定義關(guān)系R為為R=|x, y在同一分塊中在同一分塊中 現(xiàn)證現(xiàn)證R是等價(jià)關(guān)系是等價(jià)關(guān)系.定理二定理二 非空集合非空集合A的任一劃分的任一劃分S誘導(dǎo)了誘導(dǎo)了A的一個(gè)等價(jià)的一個(gè)等價(jià)關(guān)系關(guān)系R.證：證：(1) 任取任取a A，九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類故故R是自反的是自反的.定理二定理二 非空集合非空集合A的任一劃分的任一劃分S誘導(dǎo)了誘導(dǎo)了A

9、的一個(gè)等價(jià)的一個(gè)等價(jià)關(guān)系關(guān)系R.證證(續(xù)續(xù))：(2) 若若 R, 則則a與與b屬于同一分塊，屬于同一分塊，當(dāng)然當(dāng)然b與與a也屬于同一分塊，也屬于同一分塊， 即即 R, 所以所以R是對(duì)稱的是對(duì)稱的.(3) 若若 R, R, 設(shè)設(shè)a, b同屬于分塊同屬于分塊Ai， b, c同屬于分塊同屬于分塊Aj .由劃分的定義，當(dāng)由劃分的定義，當(dāng)i j時(shí)，時(shí)，AiAj= 故故b只能屬于一個(gè)分塊，只能屬于一個(gè)分塊， 所以所以Ai=Aj.于是于是a, c屬于同一分塊，即屬于同一分塊，即 R.所以所以R是傳遞的是傳遞的.綜上，綜上，R是是A上的等價(jià)關(guān)系上的等價(jià)關(guān)系. 九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類 設(shè)設(shè)A=

10、a,b,c,d,e ，A有一個(gè)劃分有一個(gè)劃分S=a,b,c,d,e，試寫出劃分試寫出劃分S所確定的所確定的A上的等價(jià)關(guān)系上的等價(jià)關(guān)系.解：解：R1=R2=則則R=R1R2R3是由是由S誘導(dǎo)的等價(jià)關(guān)系誘導(dǎo)的等價(jià)關(guān)系.R3=令關(guān)系令關(guān)系a,b a,b=,=,c cd,e d,e=,九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類 求出集合求出集合A=1,2,3上的所有等價(jià)關(guān)系上的所有等價(jià)關(guān)系.解：解：EA=因因A的所有劃分如下圖所示：的所有劃分如下圖所示：A A,A上的所有等價(jià)關(guān)系就是上述上的所有等價(jià)關(guān)系就是上述5種劃分對(duì)應(yīng)的等價(jià)種劃分對(duì)應(yīng)的等價(jià)關(guān)系，它們依次為：關(guān)系，它們依次為：R2=R3=R4=IA=

11、 , , ., IA, IA, IA,123123123123123九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類 則對(duì)任意則對(duì)任意aR1 A/R1，必存，必存在在cR2 A/R2, 使得使得aR1= cR2.定理三定理三(誘導(dǎo)的唯一性誘導(dǎo)的唯一性) 設(shè)設(shè)R1, R2是非空集合是非空集合A上的兩個(gè)等價(jià)關(guān)系，則上的兩個(gè)等價(jià)關(guān)系，則 R1=R2A/R1=A/R2.證：證：(1)若若R1=R2, 因因A/R1=aR1| a A , A/R2=aR2| a A, 任取任取a A, 即即aR1=aR2, x aR1 R2 R1x aR2.所以所以A/R1=A/R2.同理可證同理可證R2 R1. 所以所以R1=

12、R2. 即即R1 R2.(2) 反之，若反之，若A/R1=A/R2, 所以，對(duì)任意所以，對(duì)任意 R1, 有有 a cR2 b cR2 R2a aR1 b aR1 R1F劃分與等價(jià)關(guān)系本質(zhì)上相同，唯一區(qū)別是等價(jià)關(guān)劃分與等價(jià)關(guān)系本質(zhì)上相同，唯一區(qū)別是等價(jià)關(guān)系可以在空集上定義，劃分則不能。系可以在空集上定義，劃分則不能。九、等價(jià)關(guān)系與等價(jià)類九、等價(jià)關(guān)系與等價(jià)類(3-10習(xí)題習(xí)題(9) 設(shè)設(shè) 和和 是非空集合是非空集合A的劃分，的劃分，R, R 分別是分別是由由 和和 誘導(dǎo)的等價(jià)關(guān)系，試證誘導(dǎo)的等價(jià)關(guān)系，試證 細(xì)分細(xì)分 R R.解：解： RHW: 3-10習(xí)題習(xí)題 (2);(3);(4);(5);(6);(10)所以，所以，Si=aR