《等價關(guān)系和劃分》PPT課件.ppt

1、2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,2,第三章 二元關(guān)系,3.1 基本概念 3.2 關(guān)系的合成 3.3 關(guān)系上的閉包運算 3.4 次序關(guān)系 3.5 等價關(guān)系和劃分,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,3,第3-5講 等價關(guān)系和劃分,1. 等價關(guān)系 2. 劃分 3. 劃分的積與和 4. 第3-5講 作業(yè),2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,4,等價關(guān)系是最重要、最常見的二元關(guān)系之一。它有良好的性質(zhì)。在計算機科學(xué)和計算機技術(shù)、信息科學(xué)和信息工程中都有廣泛的應(yīng)用。 定義1 設(shè)RAA，如果R是自反的、對稱的和傳遞的，則稱R是A上的等價關(guān)系。設(shè)R是等

2、價關(guān)系，若x,yR，稱x等價于y。 例如：三角形的相似關(guān)系是等價關(guān)系 等價關(guān)系的特性 關(guān)系矩陣：主對角線全為1且是對稱矩陣； 關(guān)系圖：每一個結(jié)點上都有自回路；每兩個不同結(jié)點間或沒有弧線連接，或有成對弧出現(xiàn)。,1、等價關(guān)系,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,5,例1 設(shè)A=1,2,3,4,5，R是A上的二元關(guān)系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5，證明R是A上的等價關(guān)系。 證明：寫出R的關(guān)系矩陣MR如下： MR的主對角線全為1且是對稱陣，所以R是自反的和對稱的；還可以用二元關(guān)系傳遞性的定義證明R是傳遞的。故R是A上的等價關(guān)系。,202

3、0年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,6,在R的關(guān)系圖中每一個結(jié)點上都有自回路；每兩個不同結(jié)點間如果有邊，一定有方向相反的兩條邊。所以R是自反的和對稱的。與前面一樣，也可以用二元關(guān)系傳遞性的定義證明R是傳遞的。故R是A上的等價關(guān)系。 注：等價關(guān)系R的關(guān)系圖被分為三個互不連通的部分。每部分中的結(jié)點兩兩都有關(guān)系，不同部分中的任意兩個結(jié)點則沒有關(guān)系。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,7,定義2 設(shè)x和y是兩個整數(shù)，k是一個正整數(shù)，若x，y用k除的余數(shù)相等，就稱x和y模k同余，也稱x和y模k等價。記為 x y (mod k) 設(shè)x (y)用k除的商為t1 (t2 )，余

4、數(shù)為a1 ( a2 )，數(shù)學(xué)上將x(y)表示成為： x= kt1a1， t1I，a1I 且 0a1k。 y= kt2a2， t2I，a2I 且 0a2k。 若x，y用k除的余數(shù)相等，x-y= k(t1-t2)，t1-t2I。 即x-y可以被k整除。所以，x和y模k同余還可以描述為：x-y可以被k整除。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,8,例2 設(shè)R=x,y xI yI x y （mod k）是整數(shù)集合I上的二元關(guān)系。證明R是等價關(guān)系。 證明：設(shè)a,b,c是任意的整數(shù)。 因為 a-a=k0，所以 aa mod k，a,aR。故R是自反的。 若a,bR，a b mod k，a

5、-b = kt，tI，b-a =-(a-b)=k(t)，tI，ba mod k，b,aR。故R是對稱的。 若a,bR且b,cR， a-b = kt1，t1I，b-c = kt2， t2 I， a-c=(a-b)+(b-c)=kt1+kt2=k(t1+t2)，t1+t2I，a,cR，故R是傳遞的。 所以R是整數(shù)集合I上的等價關(guān)系。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,9,定義3 設(shè)R是A上的等價關(guān)系，xA，集合 y yAxRy 叫做x形成的R等價類。記為 xR 在例1中，等價關(guān)系R等價類為：1R=2R=1,2，3R=4R=3,4，5R=5。在R的關(guān)系圖中，三個互不連通的部分，每

6、一部分中的所有結(jié)點構(gòu)成一個等價類。 上述模3等價關(guān)系的等價類叫模3等價類，模3等價類有以下三個： 0R=，6，3，0，3，6， 1R=，5，2，1，4，7， 2R=，4，1，2，5，8， 定理1 設(shè) R是X上的等價關(guān)系，xX，則有 xRX xxR,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,10,注：等價關(guān)系的任何等價類是該等價關(guān)系前域(或陪域)的子集。例如，模3等價類是整數(shù)集合的子集：0RI，1RI，2RI。 任何等價類是非空集合。x形成的R等價類xR至少有一個元素x。例如，在模3等價類中，00R，11R，22R。 定理2 設(shè)R是X上的等價關(guān)系，對于X的任意元素a和b，aRb 的充

7、分必要條件是aR=bR 證明：設(shè)aRb，下證 aR=bR caR，aRc，由R的對稱性有cRa，由條件aRb和R的傳遞性得cRb，再根據(jù)R的對稱性有bRc，cbR，故aRbR。 類似地可以證明 bRaR。這就證明了aR=bR。 設(shè) aR=bR，下證aRb。 由定理1知aaR，因為aR=bR，所以abR，bRa，由R的對稱性有aRb。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,11,定義4 設(shè)A是非空集合，=S1，S2，Sm，Si，i=1, m，且滿足： Si，SiA S1S2Sm = A 則稱是A的一個覆蓋。 定義5 設(shè)A是非空集合，=S1，S2，Sm，Si，i=1, m，是A的一

8、個覆蓋，滿足SiSj=，ij，則稱是A的一個劃分。稱Si，i=1,m，是A的劃分塊。 定義中的“SiSj=，ij”是指中的元素兩兩互不相交。,2、劃分,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,12,例3 設(shè) A=a,b,c，以下是A的子集構(gòu)成的集合： S=a,b,b,c Q=a,a,b,a,c D=a,b,c G=a,b,c E=a,b,c F=a,a,c 試確定哪些集合是A的覆蓋？哪些集合是A的劃分？哪些集合既不是覆蓋，也不是劃分？ 解：S和Q是A的覆蓋，但不是劃分；D、G和E是A的覆蓋，也是劃分；F不是A的覆蓋，也不是劃分。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)

9、院,13,集合G=a,b,c是單元素集，它有一個元素a,b,c。對單元素集a,b,c，認(rèn)為它的元素的并集就是a,b,c，同時也認(rèn)為它的元素是兩兩互不相交的。所以集合G=a,b,c是A的劃分。 在A的所有劃分中基數(shù)最大的劃分叫做A的最大劃分，基數(shù)最小的劃分叫做A的最小劃分。 在例3中，E是A的最大劃分，G是A的最小劃分。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,14,例4 設(shè)A=1,2,3，試確定A的所有劃分。 解：有一個劃分塊的劃分是：1,2,3 有兩個劃分塊的劃分是：1,2,3 2,1,3 3,1,2 有三個劃分塊的劃分是：1,2,3 圖3.9是A的所有劃分的示意圖。(a)表示

10、有一個劃分塊的劃分1,2,3。(b)、(c)和(d)表示有兩個劃分塊的劃分1,2,3、2,1,3和3,1,2。(e) 表示有三個劃分塊的劃分1,2,3。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,15,定理3 設(shè) R是X上的等價關(guān)系，X關(guān)于R的商集X/R是X 的一個劃分。,定義6 設(shè)R是X上的等價關(guān)系，R的所有等價類組成的集 合xRxX叫做X關(guān)于R的商集。記為X/R。,在例1中，等價關(guān)系R 有三個等價類：1R=2R=1,2，3R=4R=3,4，5R=5，A關(guān)于R的商集 A/R=1R，2R，5R = 1,2，3,4，5,模3等價關(guān)系R的等價類有以下三個：0R，1R和2R，由它確定的整

11、數(shù)集合I關(guān)于R的商集I/R=0R，1R，2R,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,16,定理4 設(shè)S=S1，S2，Sm是X的一個劃分， R=x,y| x和y在同一個劃分塊中， 則R是X上的等價關(guān)系。 證明：設(shè)xX=S1S2Sm，因為S是X的一個劃分，所以存在惟一的劃分塊SjS，使xSj，于是有x,xR，即R是自反的。 設(shè)x,yR，x和y在某個劃分塊Sj中，則y和x也在劃分塊Sj中，所以y,xR，即R是對稱的。 設(shè)x,yRy,zRx和y在Si中且y和z在Sj中 ySiSj，因為S是X的一個劃分，其中元素兩兩互不相交，故必有Si=Sjx和z在Sj中x,zR，即R是傳遞的。 將定理

12、4中的等價關(guān)系R叫做劃分S導(dǎo)出的等價關(guān)系。劃分S導(dǎo)出的等價關(guān)系R也可以表示為： R =(S1S1)(S2S2)(SmSm),2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,17,例5 設(shè)X=1,2,3,4，X的劃分S=1，2,3， 4，試寫出S導(dǎo)出的等價關(guān)系R。 解：R=1,1,2,2,2,3,3,2,3,3,4,4 =112,32,344 可以驗證R是X上的等價關(guān)系。 定理5 設(shè)R，S是集合X上的等價關(guān)系，則R=S當(dāng)且僅當(dāng) X/R=X/S 證明：設(shè)R=S，證明X/R=X/S。 先證 xX，xR=xS axRxRaxSaaxS，所以xRxS。 類似地可以證明 xS xR，這就證明了xR=

13、xS。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,18,再證 X/R=X/S。 xRX/R，xR=xSX/S，即xRX/S，所以X/RX/S。 類似地可以證明X/SX/R，于是X/R=X/S。 設(shè)X/R=X/S，證明R=S。 因為X/R=X/S，aRX/R，必存在cSX/S，使aR=cS a,bRaRbbaRbaRaaR bcSacS cSbcSabSccSa (因為S是對稱的) bSa (因為S是傳遞的) aSb (因為S是對稱的) a,bS 所以R S。 類似地可以證明S R，于是R=S。,2020年9月12日星期六,南京信息工程大學(xué)數(shù)理學(xué)院,19,例6 設(shè)X=1,2,3，寫出集合X上的所有等價關(guān)系。 解：先寫出集合X上的所有劃分，它們是： S1=1,2,3， S2=1,2,3， S3=1,3,2 S4=2,3,1, S5=1,2,3 對應(yīng)的等價關(guān)