《離散數(shù)學(xué)課件》6等價(jià)關(guān)系

1、二元關(guān)系的性質(zhì)與閉包（7.3-7.4）,性質(zhì)自反性、反自反性對(duì)稱性、反對(duì)稱性傳遞性閉包自反閉包r(R)對(duì)稱閉包s(R)傳遞閉包t(R),1,2/49,特 點(diǎn),3/55,7.5.1 等價(jià)關(guān)系與等價(jià)類7.5.2 商集合7.5.3 集合的劃分,7.5 等價(jià)關(guān)系和集合的劃分,4/55,例 試畫(huà)出關(guān)系圖,A={1,2,3,4,5,6,7,8} R={(x,y) │x,y ?A, x≡y(mod 3)}其中x

2、≡y(mod 3)的含義就是x-y可以被3整除.,5/55,等價(jià)關(guān)系,定義1 A是一個(gè)非空集, R是A上的一個(gè)二元關(guān)系， 若R有自反性、 對(duì)稱性、 傳遞性， 則說(shuō)R是A上的等價(jià)關(guān)系。,設(shè) R 是一個(gè)等價(jià)關(guān)系, 若∈R, 稱 x 等價(jià)于y, 記做 x～y.,

3、6/55,例（1）人類集合中的“同齡”、 “同鄉(xiāng)”關(guān)系都是 等價(jià)關(guān)系。 （2） 三角形集合的相似關(guān)系、 全等關(guān)系都是 等價(jià)關(guān)系。 （3） 住校學(xué)生的"同寢室關(guān)系"是等價(jià)關(guān)系。 （4）命題公式間的邏輯等價(jià)關(guān)系是等價(jià)關(guān)系。 （5） 對(duì)任意集合A， A上的恒等關(guān)系IA和全域關(guān) 系EA是等價(jià)關(guān)系。,7/55,例

4、3 (p106) Z是整數(shù)集，在Z上定義一個(gè)二元關(guān)系R：對(duì)于任意的 x,y?Z, (x,y) ?R當(dāng)且僅當(dāng)x與y被5除余數(shù)相同。R是Z上的等價(jià)關(guān)系。,顯然, x與y被5除同余的充要條件是5|(x-y), 這里符號(hào)a|b表示a整除b，a與b是兩個(gè)整數(shù)。對(duì)于? x?Z，有5|(x-x), 即(x,x) ?R，亦即R有自反性。對(duì)于? x,y?Z，若(x,y) ?R, 即5|(x-y)， 也即5|(y-x), 所以(y,

5、x) ?R， 亦即R有對(duì)稱性。對(duì)于? x,y,z?Z，若(x,y) ?R, 且(y,z) ?R， 即5|(x-y)，且5|(z-y)，則 5|[(x-y)+(y-z)]， 亦即5|(x-z)，所以(x,z) ?R，亦即R有傳遞性。故R是A上的等價(jià)關(guān)系。,8/55,例設(shè)A={1,2,3,…},并設(shè)~是A×A上的關(guān)系，其定義為：若ad=bc， 則(a,b) ~(c,d)。證明 ~ 是一個(gè)等

6、價(jià)關(guān)系。,證： (1) 自反性 對(duì)于?(a,b)?A×A, 因?yàn)閍b=ba， 則有(a,b) ~(a,b) 。 (2) 對(duì)稱性 如果(a,b) ~(c,d)，即有 ad=bc， 即有 cb=da， 故有(c,d) ~(a,b)。 (3) 傳遞性 如果(a,b) ~(c,d)，(c,d) ~

7、(e,f)， 即有 ad=bc, cf=de, 于是有 adcf=bcde 即 af=be, 故有 (a,b)~(e,f),9/55,等價(jià)類、代表元,若R是A上的等價(jià)關(guān)系， a是A中任意一個(gè)元素，集合 {x?A│(x,a) ? R} 稱

8、為集合A關(guān)于關(guān)系R的一個(gè)等價(jià)類，記 [a]R= {x?A│(x,a) ? R}, 簡(jiǎn)記[a] 其中a叫代表元。,10/55,例1,A={1,2,3},R={(1,1), (2,2), (3,3), (1,2), (2,1)} 則R是A上一個(gè)等價(jià)關(guān)系。,顯然 [1]R＝{1,2} [2]R＝{1,2} [3]R＝{3},1 2

9、 3,11/55,例2 A={ 1, 2, … , 8 }上模 3 等價(jià)關(guān)系的等價(jià)類：,[1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6},12/55,定理1(p107) 等價(jià)類的性質(zhì),A是一個(gè)非空集合，R是A上的一個(gè)等價(jià)關(guān)系，則有(1) ∪[x]R=A，(2) 對(duì)于任意的x,y?A， 若[x]R∩[y]R≠Ø，則[x]R=

10、[y]R。,x?A,13/55,定理1 證明 若[x]R∩[y]R≠Ø，則[x]R=[y]R,證明(2): 對(duì)于任意的x,y ?A，若[x]R∩[y]R≠Ø， 則存在a?[x]R∩[y]R。 由a?[x]R，得(a,x)?R； 再由R的對(duì)稱性，有(x,a) ?R。 由

11、a?[y]R, 有(a,y) ?R。 利用R的傳遞性，得(x,y)?R。 下面開(kāi)始證明[x]R=[y]R。 對(duì)于任意的z? [x]R，有(z,x) ?R, 又因?yàn)閯偛乓训玫?x,y) ?R， 由R的傳遞性，得到(z,y) ?R, 所以有z?

12、[y]R。從而證得 [x]R?[y]R。 同理可證[y]R?[x]R。 所以最后得到[x]R=[y]R。,14/55,定理1’,A是一個(gè)非空集合，R是A上的一個(gè)等價(jià)關(guān)系，則有(1) ∪[x]R=A，(2) 對(duì)于任意的x,y?A，若[x]R∩[y]R≠Ø， 則[x]R=[y]R。(3) [x]R≠Ø, 且[x]R?A.(4) 若xRy, 則[

13、x]R=[y]R.(5) 若xRy, 則[x]R∩[y]R=Ø,x?A,,15/55,商集合,定義2 A是一個(gè)非空集合，R是A上的一個(gè)等價(jià)關(guān)系，集合{[x]R│x?A} 叫集合A的商集合，記為 A/R= {[x]R│x?A},,16/55,例 Z是整數(shù)集，在Z上定義一個(gè)二元關(guān)系R： 對(duì)于任意的 x,y?Z, (x,y) ?R 當(dāng)且僅當(dāng)x與y被5除

14、余數(shù)相同。 則 Z/R={ [0]R, [1]R, [2]R, [3]R, [4]R},[0]R={x?Z│?n?Z, x=5n}[1]R={x?Z│?n?Z, x=5n+1}[2]R={x?Z│?n?Z, x=5n+2}[3]R={x?Z│?n?Z, x=5n+3}[4]R={x?Z│?n?Z, x=5n+4},17/55,例 A={1,2,3,4,5,6,7,8} R={(x,

15、y) │x,y ?A, x≡y(mod 3)},A/R={[1]R, [2]R, [3]R},={ {1,4,7}, {2,5,8}, {3,6} },A關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} },18/55,集合的劃分,α?B,定義3 設(shè)A為非空集合, 若A的子集族π(π?P(A)) 滿

16、足下面條件： (1) ??π (2) ?x?y (x,y∈π∧x≠y→x∩y=?) (3) ∪π=A 則稱π是A的一個(gè)劃分, 稱π中的元素為A的劃分塊.,19/55,例1 設(shè)A＝{a, b, c, d}, 給定π1,π2,π3,π4,π5,π6如下： π1= { {a, b, c}, l15njm1 }， π2= { {a, b}, {c}, 1ldvn1e } π3=

17、 { {a}, {a, b, c, d} }, π4= { {a, b}, {c} } π5= { ?,{a, b}, {c, d} }, π6= { {a, {a}}, {b, c, d} } 則π1和π2 是A的劃分, 其他都不是 A 的劃分.,(1) ??π (2) ?x?y (x,y∈π∧x≠y→x∩y=?)(3) ∪π=A,20/55,集合的劃分——等價(jià)關(guān)系,若給定集合A上的一個(gè)劃分π，可以在A上定義一個(gè)

18、二元關(guān)系R，使得R成為A上的一個(gè)等價(jià)關(guān)系，且有 A/R ＝π,21/55,解: R={(a,a), (b,b), (c,c), (b,c),(c,b),(d,d)} 求其等價(jià)類 [a]={a}, [b]=[c]={b,c}, [d]=xucaskb 商集A/R={[a],[b],[c]}

19、 ={{a},{b,c},bzwebo0},例：考慮集合A={a,b,c,d}的一個(gè)劃分: {{a}, {b,c}, ro1ghvm} 求該劃分所對(duì)應(yīng)的等價(jià)關(guān)系.,例：給出A＝{1,2,3}上所有的等價(jià)關(guān)系,22,π1 對(duì)應(yīng)等價(jià)關(guān)系 R1 ={,}∪IAπ2 對(duì)應(yīng)等價(jià)關(guān)系 R2={,}∪IAπ3 對(duì)應(yīng)等價(jià)關(guān)系 R3={,}∪IA,π4 對(duì)應(yīng)于全域關(guān)系 EA，π5 對(duì)應(yīng)于恒等關(guān)系 IA,實(shí)例,

20、23,例3 設(shè) A={1, 2, 3, 4}，在 A?A上定義二元關(guān)系R： ,>?R ? x+y = u+v，求 R 導(dǎo)出的劃分.,解 A?A={, , , , , , ,, , , , , , , , },根據(jù) 的 x + y = 2,3,4,5,6,7,8 將A?A劃分成7個(gè)等價(jià)類