二元關(guān)系等價(jià)關(guān)系

1、二元關(guān)系等價(jià)關(guān)系第1頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日第4章 二元關(guān)系第2頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日二元關(guān)系4.1二元關(guān)系基本概念 (重點(diǎn))4.2 關(guān)系的運(yùn)算4.3 關(guān)系的性質(zhì) (重點(diǎn))4.4 關(guān)系的閉包4.5 等價(jià)關(guān)系和偏序關(guān)系 (重點(diǎn)及難點(diǎn))4.6 函數(shù)的基本概念第3頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)關(guān)系 本節(jié)內(nèi)容主要說(shuō)明等價(jià)關(guān)系和集合的劃分(分類)之間的關(guān)系：1.等價(jià)關(guān)系 等價(jià)類 商集 集合的劃分2.集合的劃分 等價(jià)關(guān)系第4頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)關(guān)系定義 等價(jià)關(guān)系：設(shè)A上的二元關(guān)系

2、R, 如果R是自反的, 對(duì)稱的，傳遞的，則稱R為等價(jià)關(guān)系。若R，稱x與y等價(jià)，記作xy。第5頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)關(guān)系例1 數(shù)學(xué)中一些常見(jiàn)的等價(jià)關(guān)系：1. 數(shù)理邏輯中的公式等值關(guān)系。2.無(wú)向圖中“點(diǎn)的連通”關(guān)系。3.方程組的“同解”關(guān)系。4.代數(shù)系統(tǒng)中的“同構(gòu)”關(guān)系。第6頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)關(guān)系例2 設(shè)集合A=1,2,3,4,5,6,7,8， R是A上的模3同余關(guān)系，請(qǐng)畫出關(guān)系圖。 1 47 2 5 8 3 6第7頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)類定義 等價(jià)類把具有相同性質(zhì)的元素歸為一類設(shè)R是A

3、上的等價(jià)關(guān)系，則稱 xR = y | yAx y 為x關(guān)于R的等價(jià)類。 第8頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)類例3 設(shè)學(xué)生集合A=a,b,c,d,e,f, R1 和 R2分別是A上的“同性別”關(guān)系和“同宿舍”關(guān)系，求所有元素關(guān)于R1和R2 的等價(jià)類，其中元素屬性如下表：解：關(guān)于R1 的等價(jià)類： 關(guān)于R2 的等價(jià)類：abcdef性別女男男女男女宿舍1-2032-3022-3021-2032-3021-202第9頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)類練習(xí) 試寫出A=1,2,3,4,5,6,7,8上關(guān)于模3同余關(guān)系的等價(jià)類。解：1 = 4= 7= 1,

4、4,7, 2 = 5 = 8 =2,5,8, 3= 6 = 3,6.第10頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)類上述兩例可以看出，1. 等價(jià)關(guān)系實(shí)際上“同類關(guān)系”，是對(duì)集合按照某種性質(zhì)進(jìn)行的“分類” 。2. 這種分類的特點(diǎn)是，各個(gè)不同類之間無(wú)共同元素，同類元素具有相同的特性，所有類的并集是原集合。第11頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日等價(jià)類定理 設(shè)R是非空集合A上的等價(jià)關(guān)系, 則(1) xA, x (2) x,yA, 如果 xRy, 則 x = y(3) x,yA, 如果 x y, 則 x y= (4)等價(jià)類或者完全相同，或者完全不同，其并集恰好是A

5、第12頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日商集定義 商集等價(jià)類的集合 A/R=x|xA性質(zhì) 商集是集合的一個(gè)劃分。第13頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日集合的劃分定義 集合的劃分把集合A分為若干非空子集A1,A2 , ,An ,滿足： (1) 當(dāng) i j 時(shí)，AiAj (2) 則子集族 = A1，A2，An 稱為A的一個(gè)劃分， Ai(i=1,2, . , n)稱為劃分塊。A1A6A5A4A3A2A第14頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日集合的劃分例4 分別給出學(xué)生集合A=a,b,c,d,e,f根據(jù)“性別”和“宿舍”進(jìn)行的劃分1 和2

6、。解： 1 = a,d,f , b,c,d = A1，A2, 其中A1=a,d,f，A2=b,d,c 2 = a,d ,f, b,c,d = A1，A2 ，A3, 其中A1=a,d，A2=f ，A3=b,d,cabcdef性別女男男女男女宿舍1-2032-3022-3021-2032-3021-202第15頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日集合的劃分例5 試給出集合A=1,2,3的所有劃分。1231 1235123212341233第16頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日集合的劃分與等價(jià)關(guān)系性質(zhì) 1. 等價(jià)關(guān)系對(duì)應(yīng)集合的一個(gè)劃分。 等價(jià)關(guān)系 等價(jià)類 商集

7、 集合的劃分2.集合的一個(gè)劃分對(duì)應(yīng)著一個(gè)等價(jià)關(guān)系，這個(gè)等價(jià)關(guān)系的商集恰好是這個(gè)劃分。第17頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日集合的劃分與等價(jià)關(guān)系例6 試給出學(xué)生集合A=a,b,c,d,e,f關(guān)于“性別”的劃分所對(duì)應(yīng)的等價(jià)關(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 abcdef性別女男男女男女 = ?第18頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日集合的劃分與等價(jià)關(guān)系性質(zhì) 設(shè) = A1，A2，An 為A的一個(gè)劃分， 則 所對(duì)應(yīng)的等價(jià)

8、關(guān)系R可由如下方法得到：R=|x,y屬于的同一劃分塊（具有相同的性質(zhì)） = A1 A1 A2 A2 . An An = 第19頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日小結(jié)等價(jià)關(guān)系是“分類關(guān)系”。集合的劃分與等價(jià)關(guān)系本質(zhì)上相同，可以相互導(dǎo)出。(1)等價(jià)關(guān)系導(dǎo)出劃分：等價(jià)關(guān)系 商集(2)集合的劃分導(dǎo)出等價(jià)關(guān)系： R=|x,y屬于的同一劃分塊（具有相同的性質(zhì)） = 第20頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日集合的劃分與等價(jià)關(guān)系例7 試寫出集合A=1,2,3上的所有等價(jià)關(guān)系。解： 1. 寫出所有劃分：2.寫出每個(gè)劃分對(duì)應(yīng)的每個(gè)等價(jià)關(guān)系：(略)1231 1235123212341233第21頁(yè)，共22頁(yè)，2022年，5月20日，8點(diǎn)2分，星期日作業(yè)1.給定集合A=1, 2, 3, 4，且A中的關(guān)系R：R =, , , , , 求包含R的最小的等價(jià)關(guān)系R*（前已求）,并寫出商集A/R*。2.給定集合S= 1