離散第四章二元關(guān)系2nd

1、1/36第四章第四章 二元關(guān)系二元關(guān)系2/452/45回顧回顧 關(guān)系的定義和性質(zhì)關(guān)系的定義和性質(zhì) 關(guān)系的表示方法關(guān)系的表示方法關(guān)系圖關(guān)系圖關(guān)系矩陣關(guān)系矩陣 關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系的合成關(guān)系的合成關(guān)系合成的規(guī)則關(guān)系合成的規(guī)則關(guān)系的冪關(guān)系的冪合成關(guān)系的矩陣表達(dá)與圖解合成關(guān)系的矩陣表達(dá)與圖解 關(guān)系的逆運(yùn)算關(guān)系的逆運(yùn)算逆運(yùn)算規(guī)則逆運(yùn)算規(guī)則3/453/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算閉包的定義：給定集合閉包的定義：給定集合X，R是是X中的二元關(guān)系。中的二元關(guān)系。如果有另一個(gè)關(guān)系如果有另一個(gè)關(guān)系 滿足滿足 R（1） 是自反的是自反的(對稱的、可傳遞的對稱的、可傳遞的)； （2）（3）對于任何自反

2、的）對于任何自反的(對稱的、可傳遞的對稱的、可傳遞的)關(guān)關(guān)系系 ，如果，如果 ，則，則RRR RRR RR則稱關(guān)系則稱關(guān)系 為為R的的 并用并用r(R)表示的表示的R自反閉包，用自反閉包，用s(R)表示表示R的對稱閉包，用的對稱閉包，用t(R)表示表示R的可傳遞閉包。的可傳遞閉包。 R4/454/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算定理：給定集合定理：給定集合X，R是是X中的關(guān)系。于是可中的關(guān)系。于是可有有(a) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ，R才是自反的。才是自反的。(b) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ，R才是對稱的。才是對稱的。(c) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ，R才是傳遞的。才是傳遞的。 ( )r RR( )s

3、 RR( )t RRR證明：僅給出（證明：僅給出（a）的證明過程）的證明過程 如果是如果是R自反的，則自反的，則R具有定義給出的應(yīng)具具有定義給出的應(yīng)具備備 的全部性質(zhì)。因此有的全部性質(zhì)。因此有 。反之，如。反之，如果果 ，則由定義的，則由定義的(1)得得R是自反的。是自反的。( )r RR( )r RR5/455/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算定理：定理： 設(shè)設(shè)X是任意集合，是任意集合，R是是X中的二元關(guān)系，中的二元關(guān)系，IX是是X中的恒等關(guān)系。于是可有中的恒等關(guān)系。于是可有 ( )Xr RRI在整數(shù)集合中，小于關(guān)系在整數(shù)集合中，小于關(guān)系“”的自反閉包是的自反閉包是“”；恒等關(guān)系；恒

4、等關(guān)系IX的自反閉包是的自反閉包是IX。不等關(guān)系。不等關(guān)系“”的自反閉包是全域關(guān)系；空關(guān)系的自反閉的自反閉包是全域關(guān)系；空關(guān)系的自反閉包是恒等關(guān)系。包是恒等關(guān)系。 6/456/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算定理：給定集合定理：給定集合X，R是是X中的二元關(guān)系。于是可有中的二元關(guān)系。于是可有 1( )S RRR在整數(shù)集合中，小于關(guān)系在整數(shù)集合中，小于關(guān)系“”的對稱閉包是不的對稱閉包是不等關(guān)系等關(guān)系“”；小于或等于關(guān)系；小于或等于關(guān)系“”的對稱閉的對稱閉包是全域關(guān)系；恒等關(guān)系包是全域關(guān)系；恒等關(guān)系IX的對稱閉包是的對稱閉包是IX；不等關(guān)系不等關(guān)系“”的對稱閉包是不等關(guān)系的對稱閉包是不等關(guān)

5、系“”。 7/457/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算定理：給定集合定理：給定集合X，R是是X中的二元關(guān)系。于是可有中的二元關(guān)系。于是可有 1231( )iit RRRRR 當(dāng)當(dāng)A A是有限集時(shí)，是有限集時(shí)，A A上只有有限個(gè)不同的關(guān)系，因此，上只有有限個(gè)不同的關(guān)系，因此，存在某個(gè)正整數(shù)存在某個(gè)正整數(shù)m m，使得，使得1( )miit RR 事實(shí)上，可以證明，若事實(shí)上，可以證明，若 ，則，則nA #1( )niit RR8/458/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算例：給定集合例：給定集合X=a,b,c，R和和S是是X中的關(guān)系，給中的關(guān)系，給定定,Ra ba cc bSa bb

6、cc a 試求出試求出t(R),t(S)，并畫出關(guān)系圖，并畫出關(guān)系圖解：解：123( )t RRRRR123123( ),t SSSSSSSa bb cc aa cb ac ba ab bc c R,t(R)St(S)9/459/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算定理：設(shè)定理：設(shè)X是集合，是集合，R是是X中的二元關(guān)系，于是有中的二元關(guān)系，于是有（1）如果）如果R是自反的，那么是自反的，那么s(R),t(R)也是自反的；也是自反的；（2）如果）如果R是對稱的，那么是對稱的，那么r(R),t(R)也是對稱的；也是對稱的；（3）如果）如果R是可傳遞的，那么是可傳遞的，那么r(R)也是可傳遞的。

7、也是可傳遞的。xX證明（證明（1）：若）：若R是自反的，則對于所有的是自反的，則對于所有的 都有都有 ,( )x xRx xRRs R 1,( )iix xRx xRt R 即即s(R),t(R)是自反的是自反的10/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算證明（證明（2）：）：11/45四、關(guān)系的閉包運(yùn)算證明（2）：12/45四、關(guān)系的閉包運(yùn)算證明（3）：13/4513/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算定理：設(shè)定理：設(shè)X是集合，是集合，R是集合中的二元關(guān)系，于是有是集合中的二元關(guān)系，于是有( )( )( )( )( )( )( )( )( )ars Rsr Rbrt Rtr Rcts

8、 Rst R證明：證明：( )( )()()()()( )XXXXXXasr Rs RIRIRIRIRIRRIr RRrs R14/4514/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算證明（證明（b）：因?yàn)椋阂驗(yàn)?， ，而，而對于所有的對于所有的 有有 ，以及，以及 。根據(jù)這些關(guān)系式，可有根據(jù)這些關(guān)系式，可有( )()Xtr Rt RI( )( )Xrt Rt RInNnXXIIXXIRR IR1()nniXXiRIIR于是于是12323( )()()()()()( )( )iXXiXXXXXtr Rt RIRIRIRIRIIRRRIt Rrt R15/4515/45四、關(guān)系的閉包運(yùn)算四、關(guān)系

9、的閉包運(yùn)算證明（證明（c）：如果）：如果 ，則，則 ，12RR12()()s Rs R12()()t Rt R根據(jù)對稱閉包的定義，有根據(jù)對稱閉包的定義，有 。首先構(gòu)成上。首先構(gòu)成上式兩側(cè)的可傳遞閉包，再依次構(gòu)成兩側(cè)的對稱閉式兩側(cè)的可傳遞閉包，再依次構(gòu)成兩側(cè)的對稱閉包包,可以求得可以求得 以及以及 。而。而ts(R)是對稱的，所以是對稱的，所以 ，從而有，從而有 。 ( )s RR( )( )ts Rt R( )( )sts Rst R( )( )s s RtstR( )( )ts Rst R16/4516/45四、關(guān)系的閉包運(yùn)算四、關(guān)系的閉包運(yùn)算注意：注意：（1）通常用）通常用R+表示表示R的

10、可傳遞閉包的可傳遞閉包t(R)，并，并讀作讀作“R加加”。（2）通常用）通常用R*表示表示R的自反可傳遞閉包的自反可傳遞閉包tr(R)，并讀作并讀作“R星星”。17/4517/454.7特殊關(guān)系特殊關(guān)系一、集合的劃分和覆蓋一、集合的劃分和覆蓋定義：給定非空集合定義：給定非空集合S，設(shè)非空集合，設(shè)非空集合A=A1,A2, , An，如果有，如果有1( )(1,2, )( )iniiaASinbAS則稱集合則稱集合A是集合是集合S的的覆蓋覆蓋。注意：集合的覆蓋不唯一。注意：集合的覆蓋不唯一。例如：例如：S=a,b,c，A =a,b,b,c，B=a,b,c，A和和B都是集合都是集合S的覆蓋。的覆蓋。

11、18/4518/45一、集合的劃分和覆蓋一、集合的劃分和覆蓋定義：給定非空集合定義：給定非空集合S，設(shè)非空集合，設(shè)非空集合A=A1,A2, An，如果有，如果有1( )(1,2, )( )()()( )iijijniiaAS inbAAijAAijcAS 或則稱集合則稱集合A是集合是集合S的一個(gè)的一個(gè)劃分劃分。劃分中的元素劃分中的元素Ai稱為劃分的稱為劃分的。 劃分的類的數(shù)目叫劃分的劃分的類的數(shù)目叫劃分的。 劃分是覆蓋的特定情況，即中元素互不相交的劃分是覆蓋的特定情況，即中元素互不相交的特定情況。特定情況。 19/4519/45一、集合的劃分和覆蓋一、集合的劃分和覆蓋例：設(shè)例：設(shè)S=1,2,3

12、，考慮下列集合，考慮下列集合1,2,2,3;1,1,2,1,3;1,2,3;1,2,3;1,2,3; , , ;ABCDEFaa cS的覆蓋的覆蓋S的覆蓋的覆蓋S的覆蓋、劃分，秩為的覆蓋、劃分，秩為2S的覆蓋、劃分，秩為的覆蓋、劃分，秩為1，最小劃分，最小劃分S的覆蓋、劃分，秩為的覆蓋、劃分，秩為3，最大劃分最大劃分20/4520/45一、集合的劃分和覆蓋一、集合的劃分和覆蓋定義：設(shè)定義：設(shè)A和和A是非空集合是非空集合S的兩種劃分，并可以的兩種劃分，并可以表示成表示成1miiAA1njjAA如果如果A的每一類的每一類Aj，都是，都是A的某一類的某一類Ai的子集，那的子集，那么稱劃分么稱劃分A是

13、劃分是劃分A的加細(xì)，并稱的加細(xì)，并稱A加細(xì)了加細(xì)了A。如。如果果A是是A的加細(xì)并且的加細(xì)并且AA，則稱，則稱A是是A的真加細(xì)。的真加細(xì)。21/4521/45極小項(xiàng)、完全交集極小項(xiàng)、完全交集定義：劃分全集定義：劃分全集E的過程，可看成是在表達(dá)全集的的過程，可看成是在表達(dá)全集的文氏圖上劃出分界線的過程。設(shè)文氏圖上劃出分界線的過程。設(shè)A，B，C是全集是全集E的三個(gè)子集。由的三個(gè)子集。由A，B和和C生成的生成的E的劃分的類，稱的劃分的類，稱為為。 n個(gè)子集生成個(gè)子集生成2n個(gè)極小項(xiàng)，個(gè)極小項(xiàng)，用用 表示。表示。0121,nIII01234567IABCIABCIABCIABCIABCIABCIABCI

14、ABC22/4522/45一、集合的劃分和覆蓋一、集合的劃分和覆蓋定理：定理： 由全集的由全集的n個(gè)子集個(gè)子集A1,A2, An所生成的全部所生成的全部極小項(xiàng)集合，能夠構(gòu)成全集極小項(xiàng)集合，能夠構(gòu)成全集E的一個(gè)劃分。的一個(gè)劃分。 證明：證明這個(gè)定理，只需證明全集證明：證明這個(gè)定理，只需證明全集E中的每一個(gè)元素，中的每一個(gè)元素，都僅屬于一個(gè)完全交集就夠了。都僅屬于一個(gè)完全交集就夠了。 如果如果 ，則，則 ，或或 ， 或或 ； 或或 。由此。由此可見，定有可見，定有xE1xA1xA2xA2xAnxAnxA1()niixA這里這里 或是或是Ai或是或是 Ai 。試考察兩個(gè)不同的完全。試考察兩個(gè)不同的完

15、全交集交集T。因?yàn)閮蓚€(gè)完全交集是不同的，就是說存在。因?yàn)閮蓚€(gè)完全交集是不同的，就是說存在這樣一個(gè)這樣一個(gè)i，使得，使得 和和 ，因此可有，因此可有 ，即即 ；因而任何一個(gè)；因而任何一個(gè) 都不能同時(shí)屬于兩都不能同時(shí)屬于兩個(gè)不同的完全交集。個(gè)不同的完全交集。 iAiTAiTAiiTAAT xE23/4523/45一、集合的劃分和覆蓋一、集合的劃分和覆蓋 注意：注意：不難看出，這里所說的完全交集，與命題演算不難看出，這里所說的完全交集，與命題演算中的極小項(xiàng)相似。但是和極小項(xiàng)的集合不同，中的極小項(xiàng)相似。但是和極小項(xiàng)的集合不同，極大項(xiàng)的集合不能構(gòu)成全集的劃分。極大項(xiàng)的集合不能構(gòu)成全集的劃分。 24/45

16、24/45二、等價(jià)關(guān)系二、等價(jià)關(guān)系定義：設(shè)定義：設(shè)X是任意集合是任意集合, R是集合中的二元關(guān)系。如是集合中的二元關(guān)系。如果果R是是自反的、對稱的和可傳遞自反的、對稱的和可傳遞的，的， 則稱則稱R是等價(jià)是等價(jià)關(guān)系。即滿足以下幾點(diǎn)：關(guān)系。即滿足以下幾點(diǎn)：( )()()( )()()()( )()()()()ax xXxRxbxy xXyXxRyyRxcxyz xXyXzXxRyyRzxRz 如果如果R是集合是集合X中的等價(jià)關(guān)系，則中的等價(jià)關(guān)系，則R的域是集合的域是集合X自身，自身，所以，稱所以，稱R是定義于集合是定義于集合X中的關(guān)系。中的關(guān)系。 例如例如 數(shù)的相等關(guān)系是任何數(shù)集上的等價(jià)關(guān)系。數(shù)的

17、相等關(guān)系是任何數(shù)集上的等價(jià)關(guān)系。 又例如又例如一群人的集合中姓氏相同的關(guān)系也是等價(jià)關(guān)一群人的集合中姓氏相同的關(guān)系也是等價(jià)關(guān)系。系。但朋友關(guān)系不是等價(jià)關(guān)系，因?yàn)樗豢蓚鬟f。但朋友關(guān)系不是等價(jià)關(guān)系，因?yàn)樗豢蓚鬟f。 25/4525/45二、等價(jià)關(guān)系二、等價(jià)關(guān)系例：給定集合例：給定集合X=1,2,7,7，R是是X中的二元關(guān)系，并且中的二元關(guān)系，并且給定成給定成 ,|()Rx y xXyXxy 可被整除）試證明試證明R是等價(jià)關(guān)系。是等價(jià)關(guān)系。解：解：R的關(guān)系矩陣如下：的關(guān)系矩陣如下： 1001001010010000100101001001010010000100101001001RMR的關(guān)系圖如下：

18、的關(guān)系圖如下：26/4526/45二、等價(jià)關(guān)系二、等價(jià)關(guān)系注意：注意：上例是模數(shù)系統(tǒng)中模等價(jià)關(guān)系的特定情況。上例是模數(shù)系統(tǒng)中模等價(jià)關(guān)系的特定情況。 設(shè)設(shè)R+是正整數(shù)集合，是正整數(shù)集合，m是個(gè)正整數(shù)。對于是個(gè)正整數(shù)。對于 來來說，可將說，可將R定義成定義成 。 這這里，里，“x-y可被可被m整除整除”等價(jià)于命題等價(jià)于命題“當(dāng)用當(dāng)用m去除去除x和和y時(shí)，它們都有同樣的余數(shù)時(shí)，它們都有同樣的余數(shù)”。故關(guān)系。故關(guān)系R也稱為也稱為。 , x yI,|mRx yxy 可被 所整除27/4527/45元素的等價(jià)元素的等價(jià) 設(shè)設(shè)R R是集合是集合A A上的等價(jià)關(guān)系，若元素上的等價(jià)關(guān)系，若元素aRbaRb，則稱

19、，則稱a a與與b b等價(jià)，或稱等價(jià)，或稱b b與與a a等價(jià)。等價(jià)。定義：設(shè)定義：設(shè)m是個(gè)正整數(shù)，是個(gè)正整數(shù)， 。如果對于某一個(gè)整。如果對于某一個(gè)整數(shù)數(shù)n，有，有x-y=nm,則稱則稱x模模等價(jià)等價(jià)于于y，并記作，并記作 , x yI(mod)xym整數(shù)整數(shù)m稱為稱為。“ ”表示模表示模m等價(jià)關(guān)系等價(jià)關(guān)系R。28/4528/45二、等價(jià)關(guān)系二、等價(jià)關(guān)系定理：任何集合定理：任何集合 中的模中的模m相等關(guān)系，是一個(gè)等相等關(guān)系，是一個(gè)等價(jià)關(guān)系。價(jià)關(guān)系。 XI證明：設(shè)證明：設(shè)R是任何集合是任何集合 中的模中的模m相等價(jià)關(guān)系。如果相等價(jià)關(guān)系。如果X=，則，則R是個(gè)空關(guān)系，顯然有是自反的、對稱的和可是個(gè)

20、空關(guān)系，顯然有是自反的、對稱的和可傳遞的。如果傳遞的。如果X ，則需考察下列三條：，則需考察下列三條： XI(1)對于任何對于任何 來說，因?yàn)閬碚f，因?yàn)閤-x=0m，所以有，所以有 。因此，模因此，模m相等關(guān)系是自反的。相等關(guān)系是自反的。 xX(mod)xxm(2)對于任何對于任何 來說，如果來說，如果 ，則存在某一，則存在某一個(gè)個(gè) ，能使，能使x-y=nm。于是可有。于是可有y-x=(-n)m，因此，因此有有 ，即模，即模m相等關(guān)系是對稱的。相等關(guān)系是對稱的。 , x yX(mod)xym, x yX(mod)yxm(3)設(shè)設(shè) ， 和和 。于是存。于是存在在 ，能使，能使 和和 。而而 ，從

21、而，從而可有可有 ，即模，即模m相等關(guān)系是可傳遞的。相等關(guān)系是可傳遞的。 ,x y zX(mod)xym(mod)yxm12,n nI1()xyn m2()yznm1212()xzxyyzn mnmnnm(mod)xzm29/4529/45等價(jià)類等價(jià)類 定義定義 設(shè)設(shè) 是集合是集合A A上的等價(jià)關(guān)系，則上的等價(jià)關(guān)系，則A A 中等中等價(jià)于元素價(jià)于元素 的所有元素組成的集合稱為的所有元素組成的集合稱為 生成的等生成的等價(jià)類，用價(jià)類，用 表示，即表示，即 Ra |Rab bAaRb 且aaR說明：簡單起見，有時(shí)候把說明：簡單起見，有時(shí)候把a(bǔ)R簡單寫作簡單寫作a或或a/R。30/4530/45等價(jià)類

22、等價(jià)類例：設(shè)例：設(shè)X=a,b,c,d，R是是X中的等價(jià)關(guān)系，并把中的等價(jià)關(guān)系，并把R給定成給定成 ,Ra aa bb ab bc cc dd cd d 則：則： , RRaba b , RRcdc d31/4531/45等價(jià)類的性質(zhì)等價(jià)類的性質(zhì)設(shè)設(shè)X是一集合，是一集合，X是是R中的等價(jià)關(guān)系中的等價(jià)關(guān)系2. 對于所有的對于所有的 ，或者，或者 ，或者，或者, x yX RRxy RRxy證明：當(dāng)證明：當(dāng)X=，上述結(jié)論肯定為真。，上述結(jié)論肯定為真。當(dāng)當(dāng)X時(shí)，分兩種情況討論時(shí)，分兩種情況討論 (1)xRy (2)xRy. 如果如果xX,則則x xR。該性質(zhì)是明顯的，因?yàn)槭亲苑础Ｔ撔再|(zhì)是明顯的，因?yàn)槭?/p>

23、自反的，所以有的，所以有xRx,于是于是x xR32/4532/45等價(jià)類的性質(zhì)等價(jià)類的性質(zhì)(1) xRy故故 。 RRxy類似地可以證明類似地可以證明由上得由上得 RRyx RRxy若若 ，則，則xRxRz z ， Rzx由由R R 的對稱性有的對稱性有zRxzRx， 又由又由R R的傳遞性有的傳遞性有zRyzRy ，因此，因此 Rzy(2) xRy假設(shè)假設(shè) , , RRxy因此有因此有 且且 ， Rzx Rzy故故 RRxy于是由于是由xRzxRz, ,zRyzRy，得，得xRyxRy，與，與xRy相矛盾相矛盾33/4533/45等價(jià)類的性質(zhì)等價(jià)類的性質(zhì)3. Rx XxX證明：假定證明：假

24、定 ，對于某個(gè)，對于某個(gè) ，有，有 。由于由于 ，會(huì)有，會(huì)有 ，因而，因而 。設(shè)設(shè) ，于是，于是因而因而證畢。證畢。 Rx Xzx xX Rzx RxXzX Rx XxXzX RRx Xzzx Rx XXx 34/4534/45等價(jià)類的性質(zhì)等價(jià)類的性質(zhì)例例 設(shè)設(shè)A A=a,b,c,da,b,c,d ，A A上的關(guān)系上的關(guān)系 ,Ra aa bb ca cc cb bb ac bc ad d R是是A上的等價(jià)關(guān)系上的等價(jià)關(guān)系 , , RRRabca b c Rdd 同一個(gè)等價(jià)類中元素均相互等價(jià)。不同等價(jià)類同一個(gè)等價(jià)類中元素均相互等價(jià)。不同等價(jià)類中的元素互不等價(jià)。中的元素互不等價(jià)。 由由A A的各元

25、素所生成的等價(jià)類必定覆蓋的各元素所生成的等價(jià)類必定覆蓋A A，決定，決定了集合了集合A A的一種劃分。的一種劃分。 35/4535/45二、等價(jià)關(guān)系二、等價(jià)關(guān)系定理：設(shè)定理：設(shè)R是非空集合是非空集合X中的等價(jià)關(guān)系。中的等價(jià)關(guān)系。R的等價(jià)類的等價(jià)類的集合的集合 ，是，是X的一個(gè)劃分。的一個(gè)劃分。 |RxxX定義：設(shè)定義：設(shè)R是非空集合是非空集合X中的等價(jià)關(guān)系。中的等價(jià)關(guān)系。R的各元素的各元素生成的等價(jià)類集合生成的等價(jià)類集合 叫按叫按R去劃分去劃分X的的，記作記作X/R，也可以寫成，也可以寫成X(mod R)。 |RxxX由定義可知，按由定義可知，按R對集合對集合X的劃分的劃分X/R是一個(gè)集是一個(gè)

26、集合，并且合，并且X/R的基數(shù)是的基數(shù)是X的不同的的不同的R等價(jià)類的數(shù)等價(jià)類的數(shù)目，因此目，因此X/R的基數(shù)又稱為等價(jià)關(guān)系的基數(shù)又稱為等價(jià)關(guān)系R的的。 36/4536/45特殊的等價(jià)關(guān)系特殊的等價(jià)關(guān)系全域關(guān)系：令等價(jià)關(guān)系全域關(guān)系：令等價(jià)關(guān)系R1=X X，這里，這里X的每一個(gè)的每一個(gè)元素與元素與X的所有元素都有的所有元素都有R1的關(guān)系。按的關(guān)系。按R1劃分劃分X的商的商集乃是集合集乃是集合X。等價(jià)關(guān)系。等價(jià)關(guān)系R1是全域關(guān)系。全域關(guān)是全域關(guān)系。全域關(guān)系會(huì)造成集合系會(huì)造成集合X的的最小劃分最小劃分。 恒等關(guān)系恒等關(guān)系R：X的每一個(gè)元素僅關(guān)系到它自身，而的每一個(gè)元素僅關(guān)系到它自身，而不關(guān)系到其它元素

27、。顯然，不關(guān)系到其它元素。顯然，R是個(gè)恒等關(guān)系。按是個(gè)恒等關(guān)系。按R劃分劃分X的商集，僅由單元素集合組成。恒等關(guān)系的商集，僅由單元素集合組成。恒等關(guān)系R會(huì)造成集合會(huì)造成集合X的的最大劃分最大劃分。這些劃分均稱作。這些劃分均稱作X的的平平凡劃分凡劃分。 37/4537/45等價(jià)關(guān)系與集合的劃分等價(jià)關(guān)系與集合的劃分例：令例：令R是整數(shù)集合是整數(shù)集合I中的中的“模模3同余同余”關(guān)系，關(guān)系，R可給可給定成定成 3,|()Rx yxIyIxy 被 整除求求I的元素所生成的的元素所生成的R等價(jià)類。等價(jià)類。 解：等價(jià)類是解：等價(jià)類是0 , 6, 3,0,3,6,1 , 5, 2,1,4,7,2 , 4, 1

28、,2,5,8,RRR 0, 1, 2 RRRI R 可以看出，等價(jià)關(guān)系可以造成集合的一個(gè)可以看出，等價(jià)關(guān)系可以造成集合的一個(gè)劃分。劃分。 38/4538/45等價(jià)關(guān)系與集合的劃分等價(jià)關(guān)系與集合的劃分定理：設(shè)定理：設(shè)C是非空集合是非空集合X的一個(gè)劃分，則由這個(gè)劃分的一個(gè)劃分，則由這個(gè)劃分所確定的下述關(guān)系所確定的下述關(guān)系R()()xRySSCxSyS 必定是個(gè)等價(jià)關(guān)系，并稱必定是個(gè)等價(jià)關(guān)系，并稱R為由為由C劃分導(dǎo)出的劃分導(dǎo)出的X中中的等價(jià)關(guān)系。的等價(jià)關(guān)系。 證明：要證明證明：要證明R是個(gè)等價(jià)關(guān)系，就必須證明是個(gè)等價(jià)關(guān)系，就必須證明R是自反是自反的、對稱的和可傳遞的。的、對稱的和可傳遞的。(a)由于由于C是是X的劃分，的劃分，C必定覆蓋必定覆蓋X。對任意。對任意的的 ，必有，必有X屬于屬于C的某一個(gè)元素的某一個(gè)元素S。所以對于。所以對于每一個(gè)每一個(gè) ，都有，都有xRx，即，即R是自反的。是自反的。 xXxX39/4539/45等價(jià)關(guān)系與集合的劃分等價(jià)關(guān)系與集合的劃分證明證明：（b） 假定假定xRy。于是存在一個(gè)。于是存在一個(gè) ，且，