《離散數(shù)學課件》6等價關系

1、二元關系的性質與閉包（7.3-7.4）,性質自反性、反自反性對稱性、反對稱性傳遞性閉包自反閉包r(R)對稱閉包s(R)傳遞閉包t(R),1,2/49,特 點,3/55,7.5.1 等價關系與等價類7.5.2 商集合7.5.3 集合的劃分,7.5 等價關系和集合的劃分,4/55,例 試畫出關系圖,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,等價關系,定義1 A是一個非空集, R是A上的一個二元關系， 若R有自反性、 對稱性、 傳遞性， 則說R是A上的等價關系。,設 R 是一個等價關系, 若∈R, 稱 x 等價于y, 記做 x～y.,

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

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

5、x) ?R， 亦即R有對稱性。對于? 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上的等價關系。,8/55,例設A={1,2,3,…},并設~是A×A上的關系，其定義為：若ad=bc， 則(a,b) ~(c,d)。證明 ~ 是一個等

6、價關系。,證： (1) 自反性 對于?(a,b)?A×A, 因為ab=ba， 則有(a,b) ~(a,b) 。 (2) 對稱性 如果(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,等價類、代表元,若R是A上的等價關系， a是A中任意一個元素，集合 {x?A│(x,a) ? R} 稱

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

9、 3,11/55,例2 A={ 1, 2, … , 8 }上模 3 等價關系的等價類：,[1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6},12/55,定理1(p107) 等價類的性質,A是一個非空集合，R是A上的一個等價關系，則有(1) ∪[x]R=A，(2) 對于任意的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): 對于任意的x,y ?A，若[x]R∩[y]R≠Ø， 則存在a?[x]R∩[y]R。 由a?[x]R，得(a,x)?R； 再由R的對稱性，有(x,a) ?R。 由

11、a?[y]R, 有(a,y) ?R。 利用R的傳遞性，得(x,y)?R。 下面開始證明[x]R=[y]R。 對于任意的z? [x]R，有(z,x) ?R, 又因為剛才已得到(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是一個非空集合，R是A上的一個等價關系，則有(1) ∪[x]R=A，(2) 對于任意的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是一個非空集合，R是A上的一個等價關系，集合{[x]R│x?A} 叫集合A的商集合，記為 A/R= {[x]R│x?A},,16/55,例 Z是整數(shù)集，在Z上定義一個二元關系R： 對于任意的 x,y?Z, (x,y) ?R 當且僅當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關于恒等關系和全域關系的商集為： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} },18/55,集合的劃分,α?B,定義3 設A為非空集合, 若A的子集族π(π?P(A)) 滿

16、足下面條件： (1) ??π (2) ?x?y (x,y∈π∧x≠y→x∩y=?) (3) ∪π=A 則稱π是A的一個劃分, 稱π中的元素為A的劃分塊.,19/55,例1 設A＝{a, b, c, d}, 給定π1,π2,π3,π4,π5,π6如下： π1= { {a, b, c}, ihwbqm5 }， π2= { {a, b}, {c}, 4e8keud } π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,集合的劃分——等價關系,若給定集合A上的一個劃分π，可以在A上定義一個

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

19、 ={{a},{b,c},hhjkpw1},例：考慮集合A={a,b,c,d}的一個劃分: {{a}, {b,c}, bfq0ehs} 求該劃分所對應的等價關系.,例：給出A＝{1,2,3}上所有的等價關系,22,π1 對應等價關系 R1 ={,}∪IAπ2 對應等價關系 R2={,}∪IAπ3 對應等價關系 R3={,}∪IA,π4 對應于全域關系 EA，π5 對應于恒等關系 IA,實例,

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