離散第四章二元關(guān)系-3rd zhou

1、1/36第四章 二元關(guān)系2/452/45回顧關(guān)系的性質(zhì)關(guān)系的閉包運算3/453/45四、關(guān)系的閉包運算定理：設(shè)X是集合，R是集合中的二元關(guān)系，于是有證明：4/454/45四、關(guān)系的閉包運算證明（b）：因為 ， ，而對于所有的 有 ，以及 。根據(jù)這些關(guān)系式，可有于是5/455/45四、關(guān)系的閉包運算證明（c）：如果 ，則 ，根據(jù)對稱閉包的定義，有 。首先構(gòu)成上式兩側(cè)的可傳遞閉包，再依次構(gòu)成兩側(cè)的對稱閉包,可以求得 以及 。而ts(R)是對稱的，所以 ，從而有 。 6/456/45四、關(guān)系的閉包運算注意：（1）通常用R+表示R的可傳遞閉包t(R)，并讀作“R加”。（2）通常用R*表示R的自反可傳遞

2、閉包tr(R)，并讀作“R星”。7/457/454.5特殊關(guān)系一、集合的劃分和覆蓋定義：給定非空集合S，設(shè)非空集合A=A1,A2, An，如果有則稱集合A是集合S的覆蓋。注意：集合的覆蓋不唯一。例如：S=a,b,c，A =a,b,b,c，B=a,b,c，A和B都是集合S的覆蓋。8/458/45一、集合的劃分和覆蓋定義：給定非空集合S，設(shè)非空集合A=A1,A2, An，如果有則稱集合A是集合S的一個劃分。劃分中的元素Ai稱為劃分的類。 劃分的類的數(shù)目叫劃分的秩。 劃分是覆蓋的特定情況，即中元素互不相交的特定情況。 9/459/45一、集合的劃分和覆蓋例：設(shè)S=1,2,3，考慮下列集合S的覆蓋S的

3、覆蓋S的覆蓋、劃分，秩為2S的覆蓋、劃分，秩為1，最小劃分S的覆蓋、劃分，秩為3，最大劃分10/4510/45一、集合的劃分和覆蓋定義：設(shè)A和A是非空集合S的兩種劃分，并可以表示成如果A的每一類Aj，都是A的某一類Ai的子集，那么稱劃分A是劃分A的加細，并稱A加細了A。如果A是A的加細并且AA，則稱A是A的真加細。11/4511/45極小項、完全交集定義：劃分全集E的過程，可看成是在表達全集的文氏圖上劃出分界線的過程。設(shè)A，B，C是全集E的三個子集。由A，B和C生成的E的劃分的類，稱為極小項或完全交集。 n個子集生成2n個極小項，用 表示。12/4512/45一、集合的劃分和覆蓋定理： 由全集

4、的n個子集A1,A2, An所生成的全部極小項集合，能夠構(gòu)成全集E的一個劃分。 證明：證明這個定理，只需證明全集E中的每一個元素，都僅屬于一個完全交集就夠了。 如果 ，則 ，或 ， 或 ； 或 。由此可見，定有這里 或是Ai或是 Ai 。試考察兩個不同的完全交集T。因為兩個完全交集是不同的，就是說存在這樣一個i，使得 和 ，因此可有 ，即 ；因而任何一個 都不能同時屬于兩個不同的完全交集。 13/4513/45一、集合的劃分和覆蓋注意：不難看出，這里所說的完全交集，與命題演算中的極小項相似。但是和極小項的集合不同，極大項的集合不能構(gòu)成全集的劃分。 14/4514/45二、等價關(guān)系定義：設(shè)X是任

5、意集合, R是集合中的二元關(guān)系。如果R是自反的、對稱的和可傳遞的， 則稱R是等價關(guān)系。即滿足以下幾點：如果R是集合X中的等價關(guān)系，則R的域是集合X自身，所以，稱R是定義于集合X中的關(guān)系。 例如 數(shù)的相等關(guān)系是任何數(shù)集上的等價關(guān)系。 又例如一群人的集合中姓氏相同的關(guān)系也是等價關(guān)系。但朋友關(guān)系不是等價關(guān)系，因為它不可傳遞。 15/4515/45二、等價關(guān)系例：給定集合X=1,2,7，R是X中的二元關(guān)系，并且給定成 試證明R是等價關(guān)系。解：R的關(guān)系矩陣如下： R的關(guān)系圖如下：16/4516/45二、等價關(guān)系注意：上例是模數(shù)系統(tǒng)中模等價關(guān)系的特定情況。 設(shè)Z+是正整數(shù)集合，m是個正整數(shù)。對于 來說，可

6、將R定義成 。 這里，“x-y可被m整除”等價于命題“當用m去除x和y時，它們都有同樣的余數(shù)”。故關(guān)系R也稱為模m同余關(guān)系。 17/4517/45元素的等價 設(shè)R是集合A上的等價關(guān)系，若元素aRb，則稱a與b等價，或稱b與a等價。定義：設(shè)m是個正整數(shù)， 。如果對于某一個整數(shù)n，有x-y=nm,則稱x模m等價于y，并記作 整數(shù)m稱為等價的模數(shù)。“ ”表示模m等價關(guān)系R。18/4518/45二、等價關(guān)系定理：任何集合 中的模m相等關(guān)系，是一個等價關(guān)系。 證明：設(shè)R是任何集合 中的模m相等價關(guān)系。如果X=，則R是個空關(guān)系，顯然有是自反的、對稱的和可傳遞的。如果X ，則需考察下列三條： (1)對于任何

7、 來說，因為x-x=0m，所以有 。因此，模m相等關(guān)系是自反的。 (2)對于任何 來說，如果 ，則存在某一個 ，能使x-y=nm。于是可有y-x=(-n)m，因此有 ，即模m相等關(guān)系是對稱的。 (3)設(shè) ， 和 。于是存在 ，能使 和 。而 ，從而可有 ，即模m相等關(guān)系是可傳遞的。 19/4519/45等價類 定義 設(shè) 是集合A上的等價關(guān)系，則A 中等價于元素 的所有元素組成的集合稱為 生成的等價類，用 表示，即 說明：簡單起見，有時候把aR簡單寫作a或a/R。20/4520/45等價類例：設(shè)X=a,b,c,d，R是X中的等價關(guān)系，并把R給定成 則：21/4521/45等價類的性質(zhì)設(shè)X是一集合

8、，X是R中的等價關(guān)系2. 對于所有的 ，或者 ，或者證明：當X=，上述結(jié)論肯定為真。當X時，分兩種情況討論 (1)xRy (2)xRy. 如果xX,則x xR。該性質(zhì)是明顯的，因為是自反的，所以有xRx,于是x xR22/4522/45等價類的性質(zhì)(1) xRy故 。 類似地可以證明由上得若 ，則xRz ， 由R 的對稱性有zRx， 又由R的傳遞性有zRy ，因此 (2) xRy假設(shè) , 因此有 且 ，故 于是由xRz,zRy，得xRy，與xRy相矛盾23/4523/45等價類的性質(zhì)3.證明：假定 ，對于某個 ，有 。由于 ，會有 ，因而 。設(shè) ，于是因而證畢。24/4524/45等價類的性質(zhì)

9、例 設(shè)A=a,b,c,d，A上的關(guān)系R是A上的等價關(guān)系 同一個等價類中元素均相互等價。不同等價類中的元素互不等價。 由A的各元素所生成的等價類必定覆蓋A，決定了集合A的一種劃分。 25/4525/45二、等價關(guān)系定理：設(shè)R是非空集合X中的等價關(guān)系。R的等價類的集合 ，是X的一個劃分。 定義：設(shè)R是非空集合X中的等價關(guān)系。R的各元素生成的等價類集合 叫按R去劃分X的商集，記作X/R，也可以寫成X(mod R)。由定義可知，按R對集合X的劃分X/R是一個集合，并且X/R的基數(shù)是X的不同的R等價類的數(shù)目，因此X/R的基數(shù)又稱為等價關(guān)系R的秩。 26/4526/45特殊的等價關(guān)系全域關(guān)系：令等價關(guān)系R

10、1=X X，這里X的每一個元素與X的所有元素都有R1的關(guān)系。按R1劃分X的商集乃是集合X。等價關(guān)系R1是全域關(guān)系。全域關(guān)系會造成集合X的最小劃分。 恒等關(guān)系R：X的每一個元素僅關(guān)系到它自身，而不關(guān)系到其它元素。顯然，R是個恒等關(guān)系。按R劃分X的商集，僅由單元素集合組成。恒等關(guān)系R會造成集合X的最大劃分。這些劃分均稱作X的平凡劃分。 27/4527/45等價關(guān)系與集合的劃分例：令R是整數(shù)集合I中的“模3同余”關(guān)系，R可給定成 求Z的元素所生成的R等價類。 解：等價類是可以看出，等價關(guān)系可以造成集合的一個劃分。 28/4528/45等價關(guān)系與集合的劃分定理：設(shè)C是非空集合X的一個劃分，則由這個劃分

11、所確定的下述關(guān)系R必定是個等價關(guān)系，并稱R為由C劃分導(dǎo)出的X中的等價關(guān)系。 證明：要證明R是個等價關(guān)系，就必須證明R是自反的、對稱的和可傳遞的。(a)由于C是X的劃分，C必定覆蓋X。對任意的 ，必有x屬于C的某一個元素S。所以對于每一個 ，都有xRx，即R是自反的。 29/4529/45等價關(guān)系與集合的劃分證明：（b） 假定xRy。于是存在一個 ，且 和 ，所以有yRx。因此，R是對稱的。（c）假定xRy和yRz。于是存在兩個元素 和 ，且 和 ，所以有 。這樣就有S1=S2，因此， 。從而xRz，所以有R是可傳遞的。綜上，R是個等價關(guān)系。證畢。 可以看出，給定集合的一種劃分，就可以寫出一個等價關(guān)系。反過來，集合中的等價關(guān)系也能夠生成該集合的劃分。30/4530/45等價關(guān)系與集合的劃分例：設(shè)X=a,b,c,d,e和C=a,b,c,d,e。試寫出由劃分C導(dǎo)出的X中的等價關(guān)系。 解：用R表示這個等價關(guān)系，（每一個類做笛卡爾乘積）注意：集合中的等價關(guān)系能夠生成該集合的劃分，反過來集合中的任何一種劃分又能確定