二元關(guān)系4.5等價關(guān)系.ppt

《二元關(guān)系4.5等價關(guān)系.ppt》由會員分享，可在線閱讀，更多相關(guān)《二元關(guān)系4.5等價關(guān)系.ppt（22頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1,離散數(shù)學(xué)DiscreteMathematics,主講：陳哲云青島理工大學(xué)計算機工程學(xué)院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)系：設(shè)A上的二元關(guān)系R,如果R是自反的,對稱的，傳遞的，則稱R為等價關(guān)系。若∈R，稱x與y等價，記作x～y。,等價關(guān)系,例1數(shù)學(xué)中一些常見的等價關(guān)系：1.數(shù)理邏輯中的公式等值關(guān)系。2.無向圖中“點的連通”關(guān)系。3.方程組的“同解”關(guān)系。4.代數(shù)系統(tǒng)中的“同構(gòu)”關(guān)系。,等價關(guān)系,例2設(shè)集合A={1,2,3,4,5,6,7,8}，R是A上的模3同余關(guān)系，請畫出關(guān)系圖。1～4～72～5～83～6,等價類,定義等價類——把具有相同性質(zhì)的元素歸為一類設(shè)R是A上的等價關(guān)系，則稱[x]R={y|y∈A∧x～y}為x關(guān)于R的等價類。,等價類,例3設(shè)學(xué)生集合A={a,b,c,d,e,f},R1和R2分別是A上的“同性別”關(guān)系和“同宿舍”關(guān)系，求所有元素關(guān)于R1和R2的等價類，其中元素屬性如下表：解：關(guān)于R1的等價類：關(guān)于R2的等價類：,等價類,練習(xí)試寫出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.這種分類的特點是，各個不同類之間無共同元素，同類元素具有相同的特性，所有類的并集是原集合。,等價類,定理設(shè)R是非空集合A上的等價關(guān)系,則(1)?x?A,[x]≠?(2)?x,y?A,如果xRy,則[x]=[y](3)?x,y?A,如果xy,則[x]∩[y]=?(4),等價類或者完全相同，或者完全不同，其并集恰好是A,商集,定義商集——等價類的集合A/R={[x]|x∈A}性質(zhì)商集是集合的一個劃分。,集合的劃分,定義集合的劃分把集合A分為若干非空子集A1,A2,…,An,滿足：(1)當(dāng)i≠j時，Ai∩Aj＝?(2)則子集族?={A1，A2，…，An}稱為A的一個劃分，Ai(i=1,2,...,n)稱為劃分塊。,集合的劃分,例4分別給出學(xué)生集合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}}={A1，A2，A3},其中A1={a,d}，A2={f}，A3={b,d,c},集合的劃分,例5試給出集合A={1,2,3}的所有劃分。,集合的劃分與等價關(guān)系,性質(zhì)1.等價關(guān)系對應(yīng)集合的一個劃分。等價關(guān)系→等價類→商集→集合的劃分2.集合的一個劃分對應(yīng)著一個等價關(guān)系，這個等價關(guān)系的商集恰好是這個劃分。,集合的劃分與等價關(guān)系,例6試給出學(xué)生集合A={a,b,c,d,e,f}關(guān)于“性別”的劃分所對應(yīng)的等價關(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,=?,集合的劃分與等價關(guān)系,性質(zhì)設(shè)?={A1，A2，…，An}為A的一個劃分，則?所對應(yīng)的等價關(guān)系R可由如下方法得到：R?={|x,y屬于?的同一劃分塊（具有相同的性質(zhì)）}=A1A1?A2A2?......?AnAn=,小結(jié),等價關(guān)系是“分類關(guān)系”。集合的劃分與等價關(guān)系本質(zhì)上相同，可以相互導(dǎo)出。(1)等價關(guān)系導(dǎo)出劃分：等價關(guān)系→商集(2)集合的劃分導(dǎo)出等價關(guān)系：R?={|x,y屬于?的同一劃分塊（具有相同的性質(zhì)）}=,集合的劃分與等價關(guān)系,例7試寫出集合A={1,2,3}上的所有等價關(guān)系。解：1.寫出所有劃分：2.寫出每個劃分對應(yīng)的每個等價關(guān)系：(略),作業(yè),1.給定集合A={1,2,3,4}，且A中的關(guān)系R：R={,,,,,}求包含R的最小的等價關(guān)系R*（前已求）,并寫出商集A/R*。2.給定集合S={1,2,3,4,5},找出S上的等價關(guān)系R，此關(guān)系R能夠產(chǎn)生劃分{{1,2},{3},{4,5}}，并畫出關(guān)系圖。3.設(shè)A={1,2,3,4}，在A?A上定義等價關(guān)系R：,>?R?x+y=u+v，求R導(dǎo)出的劃分.,