1、1,離散數(shù)學 Discrete Mathematics,主講：陳哲云 青島理工大學計算機工程學院 2013.09,第4章 二元關(guān)系,二元關(guān)系,4.1二元關(guān)系基本概念 (重點) 4.2 關(guān)系的運算 4.3 關(guān)系的性質(zhì) (重點) 4.4 關(guān)系的閉包 4.5 等價關(guān)系和偏序關(guān)系 (重點及難點) 4.6 函數(shù)的基本概念,等價關(guān)系,本節(jié)內(nèi)容主要說明等價關(guān)系和集合的劃分(分類)之間的關(guān)系：,1.等價關(guān)系, 等價類, 商集, 集合的劃分,2.集合的劃分, 等價關(guān)系,等價關(guān)系,定義 等價關(guān)系： 設A上的二元關(guān)系R, 如果R是自反的, 對稱的，傳遞的，則稱R為等價關(guān)系。 若R，稱x與y等價，記作xy。,等價關(guān)系

2、,例1 數(shù)學中一些常見的等價關(guān)系： 1. 數(shù)理邏輯中的公式等值關(guān)系。 2.無向圖中“點的連通”關(guān)系。 3.方程組的“同解”關(guān)系。 4.代數(shù)系統(tǒng)中的“同構(gòu)”關(guān)系。,等價關(guān)系,例2 設集合A=1,2,3,4,5,6,7,8， R是A上的模3同余關(guān)系，請畫出關(guān)系圖。 1 47 2 5 8 3 6,等價類,定義 等價類把具有相同性質(zhì)的元素歸為一類 設R是A上的等價關(guān)系，則稱 xR = y | yAx y 為x關(guān)于R的等價類。,等價類,例3 設學生集合A=a,b,c,d,e,f, R1 和 R2分別是A上的“同性別”關(guān)系和“同宿舍”關(guān)系，求所有元素關(guān)于R1和R2 的等價類，其中元素屬性如下表： 解：關(guān)于

3、R1 的等價類： 關(guān)于R2 的等價類：,等價類,練習 試寫出A=1,2,3,4,5,6,7,8上關(guān)于模3同余關(guān)系的等價類。 解：1 = 4= 7= 1,4,7, 2 = 5 = 8 =2,5,8, 3= 6 = 3,6.,等價類,上述兩例可以看出， 1. 等價關(guān)系實際上“同類關(guān)系”，是對集合按照某種性質(zhì)進行的“分類” 。 2. 這種分類的特點是，各個不同類之間無共同元素，同類元素具有相同的特性，所有類的并集是原集合。,等價類,定理 設R是非空集合A上的等價關(guān)系, 則 (1) xA, x (2) x,yA, 如果 xRy, 則 x = y (3) x,yA, 如果 x y, 則 x y= (4)

4、,等價類或者完全相同，或者完全不同，其并集恰好是A,商集,定義 商集等價類的集合 A/R=x|xA 性質(zhì) 商集是集合的一個劃分。,集合的劃分,定義 集合的劃分 把集合A分為若干非空子集A1,A2 , ,An ,滿足： (1) 當 i j 時，AiAj (2) 則子集族 = A1，A2，An 稱為A的一個劃分， Ai(i=1,2, . , n)稱為劃分塊。,集合的劃分,例4 分別給出學生集合A=a,b,c,d,e,f根據(jù)“性別”和 “宿舍”進行的劃分1 和2 。 解： 1 = a,d,f , b,c,d = A1，A2, 其中A1=a,d,f，A2=b,d,c 2 = a,d ,f, b,c,d

5、 = A1，A2 ，A3, 其中A1=a,d，A2=f ，A3=b,d,c,集合的劃分,例5 試給出集合A=1,2,3的所有劃分。,集合的劃分與等價關(guān)系,性質(zhì) 1. 等價關(guān)系對應集合的一個劃分。 等價關(guān)系 等價類 商集 集合的劃分 2.集合的一個劃分對應著一個等價關(guān)系，這個等價關(guān)系的商集恰好是這個劃分。,集合的劃分與等價關(guān)系,例6 試給出學生集合A=a,b,c,d,e,f關(guān)于“性別”的劃分所對應的等價關(guān)系R。 解： = a,d,f , b,c,d = A1，A2, R=|x,y同性別 =|x,y A1 x,y A2 =|x,y A1 |x,y A2 = A1 A1 A2 A2,= ?,集合的劃

6、分與等價關(guān)系,性質(zhì) 設 = A1，A2，An 為A的一個劃分， 則 所對應的等價關(guān)系R可由如下方法得到： R=|x,y屬于的同一劃分塊（具有相同的性質(zhì)） = A1 A1 A2 A2 . An An =,小結(jié),等價關(guān)系是“分類關(guān)系”。 集合的劃分與等價關(guān)系本質(zhì)上相同，可以相互導出。 (1)等價關(guān)系導出劃分：等價關(guān)系 商集 (2)集合的劃分導出等價關(guān)系： R=|x,y屬于的同一劃分塊（具有相同的性質(zhì)） =,集合的劃分與等價關(guān)系,例7 試寫出集合A=1,2,3上的所有等價關(guān)系。 解： 1. 寫出所有劃分： 2.寫出每個劃分對應的每個等價關(guān)系：(略),作業(yè),1.給定集合A=1, 2, 3, 4，且A中的關(guān)系R： R =, , , , , 求包含R的最小的等價關(guān)系R*（前已求）,并寫出商集A/R*。 2.給定集合S= 1 , 2 ,