老師第四章二元關系3rd

1、第四章 二元1/36回顧性質的的表示圖 矩陣的運算的的規(guī)則的冪的矩陣表達與圖解的逆運算 逆運算規(guī)則2/45四、的閉包運算閉包的定義：給定集合X，R是X中的二元。R¢ 滿足如果有另一個（1） R¢ 是自反的(對稱的、可傳遞的)；（2） R¢ Ê R（3）對于任何自反的(對稱的、可傳遞的)關系R¢¢，如果R¢¢ Ê R ，則 R¢¢ Ê R¢R¢為R的自反的(對稱的，可傳遞的)閉則稱包。 并用r(R)表示的R自反閉包，用s(R)表示R 的對稱閉包，用t(R)表

2、示R的可傳遞閉包。3/45四、的閉包運算定理：給定集合X，R是X中的有。于是可(a) 當且僅當，R才是自反的。(b) 當且僅當s(R) = R，R才是對稱的。(c) 當且僅當t(R) = R ，R才是傳遞的。證明：僅給出（a）的證明過程如果是R自反的，則R具有定義給出的備 R¢的全部性質。因此有r(R) = R。反之，如果r(R) = R ，則由定義的(1)得R是自反的。4/45四、的閉包運算定理： 設X是任意集合，R是X中的二元，IX是X中的恒等。于是可有r(R) = R U IX在整數集合中，小于“<”的自反閉包是“”；恒等IX的自反閉包是IX。不等“”的自反閉包是全域；空

3、的自反閉包是恒等。5/45四、的閉包運算定理：給定集合X，R是X中的二元S (R) = R U R。于是可有“<”的對稱閉包是不在整數集合中，小于“”；小于或等于“”的對稱閉等IX的對稱閉包是IX；包是全域；恒等“”的對稱閉包是不等“”。不等6/45四、的閉包運算定理：給定集合X，R是X中的二元¥。于是可有t(R) = U Ri = R1 U R2 U R3 U×××i=1當A是有限集時，A上只有有限個不同的某個正整數m，使得，因此，事實上，可以證明，若，則7/45四、的閉包運算例：給定集合X=a,b,c，R和S是X中的，給R = á a

4、, bñ, á a, cñ, ác, bñS = á a, bñ, áb, cñ, ác, añ定試求出t(R),t(S)，并畫出圖t(R) = R1 U R2 U R3 U××× = R解：t(S ) = S1 U S 2 U S 3 U××× = S1 U S 2 U S 3áa, bñ, áb, cñ, ác, añ, áa, cñ, 

5、25;b, añ, ác, bñ, áa, añ, áb, bñ, ác, cñR,t(R)St(S)8/45四、的閉包運算定理：設X是集合，R是X中的二元，于是有（1） 如果R是自反的，那么s(R),t(R)也是自反的；（2） 如果R是對稱的，那么r(R),t(R)也是對稱的；（3） 如果R是可傳遞的，那么r(R)也是可傳遞的。證明（1）：若R是自反的，則對于所有的x Î X都有á x, xñ Î R Þ á x, xñ Î

6、 R U R = s(R)¥á x, xñ Î R Þ á x, xñ Î= t(R)Rii=1即s(R),t(R)是自反的9/45四、的閉包運算證明（2）：10/45四、的閉包運算證明（2）：11/45四、證明（3）：的閉包運算12/45四、的閉包運算定理：設X是集合，R是集合中的二元(a) rs(R) = sr(R)(b) rt(R) = tr(R)(c) ts(R) Ê st(R)sr(R) = s(R U IX )，于是有證明： (a)= (R U IX ) U (R U IX )I%X= RIX

7、R= R U RU IX= r(R U R)= rs(R)13/45四、的閉包運算證明（b）：因為tr(R) = t(R U IX ) ，rt(R) = t(R) U IX ，而I= Ino R = R o I= R 。n Î N，以及I對于所有的根據這些有XXXXn式，可有(R U I= I)nU U RiXXi=1¥tr(R) = t(R U I= (R U I) = U(R U I)i于是XXi=1IX ) U×××32= IX= IX×××R2R3RU t(R)= rt(R)14/45四、的閉包運算

8、2; R2 ，則 s(R1 ) Ê s(R2 )，t(R1 ) Ê t(R2 )證明（c）：如果R1根據對稱閉包的定義，有 s(R) Ê R。首先上式兩側的可傳遞閉包，再依次兩側的對稱閉包,可以求得ts(R) Ê t(R) 以及sts(R) Ê st(R) 。而ts(R) 是對稱的，所以sts(R) = ts(R)，從而有 ts(R) Ê st(R) 。15/45四、的閉包運算注意：（1） 通常用R+表示R的可傳遞閉包t(R)，并讀作“R加”。（2） 通常用R*表示R的自反可傳遞閉包tr(R)，并讀作“R星”。16/454.5特殊一、

9、集合的劃分和覆蓋定義：給定非空集合S，設非空集合A=A1,A2,An，如果有Ai Í S(i = 1, 2,×××, n)(a)nU A i = S(b)i=1則稱集合A是集合S的覆蓋。注意：集合的覆蓋不唯一。例如：S=a,b,c，A =a,b,b,c，B=a,b,c，A和B都是集合S的覆蓋。17/45一、集合的劃分和覆蓋定義：給定非空集合S，設非空集合A=A1,A2,An，如果有Aj = Æ (i ¹ j)或AiAj ¹ Æ (i =(b)Aij)nU Ai = S(c)i=1則稱集合A是集合S的一個劃分。劃分中

10、的元素Ai稱為劃分的類。劃分的類的數目叫劃分的秩。劃分是覆蓋的特定情況，即中元素互不相交的特定情況。18/45一、集合的劃分和覆蓋例：設S=1,2,3，考慮下列集合A = 1, 2,2, 3;B = 1,1, 2,1, 3;S的覆蓋S的覆蓋C = 1,2, 3;D = 1, 2, 3;S的覆蓋、劃分，秩為2S的覆蓋、劃分，秩為1，最小劃分E = 1,2,3;S的覆蓋、劃分，秩為3，最大劃分F = a,a, c;19/45一、集合的劃分和覆蓋定義：設A和A'是非空集合S的兩種劃分，并可以表示成mn¢¢A =A =UUAAjij =1i=1如果A'的每一類A&#

11、39;j，都是A的某一類Ai的子集，那 劃分A'是劃分A的加細，并稱A'加細了A。如果A'是A的加細并且A'A，則稱A'是A的。20/45極小項、完全交集定義：劃分全集E的過程，可看成是在表達全集的 文氏圖上劃出分界線的過程。設A，B，C是全集E 的三個子集。由A，B和C生成的E的劃分的類，稱為極小項或完全交集。= AI BI C= AI B I C= A I BI C= A I B I CI0 I1 I2I3I4I5I6III462I7= A B CI5I3= AI B I C= AB CI1I0= A I B I CI7n個子集生成2n個極小項，用

12、I0 , I1 ,×××, I2n -1表示。21/45一、集合的劃分和覆蓋定理： 由全集的n個子集A1,A2, An所生成的全部全集E的一個劃分。極小項集合，能夠證明：證明這個定理，只需證明全集E中的每一個元素，都僅屬于一個完全交集就夠了。 如果x Î E，則 x Î A1，或 x Î A2 ；x Î An 或 x Î An 。由此或 x Î A1 ，x Î A2可見，定有nÙx Î(IA )ii=1Ù這里 Ai或是Ai或是 Ai 。試考察兩個不同的完全交集T。因

13、為兩個完全交集是不同的，就是說，因此可有T Í Ai I ， Ai這樣一個i，使得T Í Ai和T Í Ai即T = Æ ；因而任何一個 x Î E 都不能同時屬于兩個不同的完全交集。22/45一、集合的劃分和覆蓋 注意：不難看出，這里所說的完全交集，與命題演算中的極小項相似。但是和極小項的集合不同，極大項的集合不能全集的劃分。23/45二、等價定義：設X是任意集合, R是集合中的二元。如果R是自反的、對稱的和可傳遞的， 則稱R是等價。即滿足以下幾點：® xRx)(a)(b)(c)("x)("y)(x Î

14、 X Ù y Î X Ù xRy ® yRx)("x)("y)("z)(xÙ xRy Ù yRz ® xRz)，則R的域是集合X自身，如果R是集合X中的等價所以，稱R是定義于集合X中的。例數的相等是任何數集上的等價。又例如一群人的集合中姓氏相同的系。也是等價關但朋友不是等價，因為它不可傳遞。24/45二、等價例：給定集合X=1,2,7，R是X中的二元給定成，并且R = á x, yñ|x Î X Ù y Î X Ù (x - y)可被整

15、除）試證明R是等價。解：R的é1矩陣如下：R的圖如下：1ù01001000010010100100101001000010010ê00úêê0ú0úM= ê11úêúRê00úêúê0êë10ú1úû25/45二、等價注意：上例是模數系統中模等價的特定情況。設R+是正整數集合，m是個正整數。對于x, y Î I+ 來說，可將R定義成R = á x, y

16、41; | x - y可被m所整除。 這里，“x-y可被m整除”等價于命題“當用m去除x和y時，它們都有同樣的余數”。故R也稱為模m同余。26/45元素的等價設R是集合A上的等價，若元素aRb，則稱a與b等價，或稱與等價。定義：設m是個正整數，x, y Î I 。如果對 數n，有x-y=nm,則稱x模等價于y，并記作一個整xy(mod m)整數m稱為等價的模數?！?#186;”表示模m等價R。27/45二、等價定理：任何集合 X Í I中的模m相等，是一個等價。證明：設R是任何集合X Í I 中的模m相等價。如果X=，則R是個空，顯然有是自反的、對稱的和可傳遞的。

17、如果X ，則需考察下列三條：(1)對于任何 x Î X 來說，因為x-x=0m，所以有x º x(mo。d m)因此，模m相等是自反的。(2)對于任何x, y Î X來說，如果x º y(mod m)，則某一個 x, y Î X，能使x-y=nm。于是可有y-x=(-n)m，因此有 y º x(mod m)，即m相等是對稱的。(3)設x, y, z Î X ，x º y(mod m)和y º x(mod m) 。于是存在n1 , n2 Î I ，能使(x - y) = n1 m和( y - z)

18、 = n2 m。而x - z = x - y + y - z = n1 m + n2 m = (n1 + n2 ) m，從而可有x º z(mod m) ，即模m相等是可傳遞的。28/45等價類是集合A上的等價，則A定義價于元素價類，用設中等的所有元素組成的集合稱為表示，即生成的等說明：簡單起見，有時候把aR簡單寫作a或a/R。29/45等價類例：設X=a,b,c,d，R是X中的等價，并把R給定成R = áa, añ, áa, bñ, áb, añ, áb, bñ, ác, cñ, &

19、#225;c, d ñ, ád , cñ, ád , d ñaR = bRcR = d R= a, b= c, d則：30/45等價類的性質設X是一集合，X是R中的等價.如果xX,則x xR。該性質是明顯的，因為是自反的，所以有xRx,于是x xR2. 對于所有的x, y Î X，或者xR= yR，或者xRI yR= Æ證明：當X=，上述結論肯定為真。當X時，分兩種情況討論(1)xRy (2)xR'y31/45等價類的性質(1) xRy，則xRz若由R，的對稱性有zRx，又由R的傳遞性有zRy，因此故類似地可以證明由

20、上得。(2) xR'y假設因此有,且，于是由xRz,zRb，得xRy，與xR'y相故32/45等價類的性質、對任何xX,xR=X我們用證左邊是右邊的子集并且右邊也是集的來證上面的等式對任何xX,則xxR而xRxR于是xxR即XxR而xxR則有xxR而xR于是有x即xR綜上xR=X33/45等價類的性質U xR = X4.xÎXz Î U xR ，對個x Î X ，有 z Îx 。證明：RxÎX由于xÍ X ，會有 z Î XU xÍ X，因而。RRxÎX，于是 z ÎzRU xR

21、Í設z Î XxÎXU xRX Í因而xÎX證畢。34/45等價類的性質設A=a,b,c,d，A上的例R是A上的等價同一個等價類中元素均相互等價。不同等價類中的元素互不等價。由A的各元素所生成的等價類必定覆蓋A，決定了集合A的一種劃分。35/45二、等價定理：設R是非空集合X中的等價。R的等價類的集合 X ，是X的一個劃分。定義：設R是非空集合X中的等價。R的各元素生成的等價類集合 叫按R去劃分X的，記作X/R，也可以寫成X(mod R)。由定義可知，按R對集合X的劃分X/R是一個集 合，并且X/R的基數是X的不同的R等價類的數目，因此X/R的

22、基數又稱為等價R的秩。36/45特殊的等價R1=X ´ X，這里X的每一個全域：令等價元素與X的所有元素都有R1的。按R1劃分X的商集乃是集合X。等價R1是全域。全域關系會造成集合X的最小劃分。R：X的每一個元素僅恒等不到它自身，而到其它元素。顯然，R是個恒等。按RR劃分X的，僅由單元素集合組成。恒等會造成集合X的最大劃分。這些劃分均稱作X的平凡劃分。37/45等價與集合的劃分例：令R是整數集合I中的“模3同余”，R可給定成R = á x, yñ | x Î I Ù y Î I Ù (x - y)被3整除求I的元素所生成的R

23、等價類。解：等價類是0R = ×××, -6, -3, 0, 3, 6,×××1R = ×××, -5, -2,1, 4, 7,×××2R = ×××, -4, -1, 2, 5,8,×××I R = 0 ,1 ,2 RRR可以看出，等價劃分?？梢栽斐杉系囊粋€38/45等價與集合的劃分定理：設C是非空集合X的一個劃分，則由這個劃分R所確定的下述xRy Û ($S )(S Î C Ù x

24、 Î S Ù y Î S )，并稱R為由C劃分導出的X中必定是個等價的等價。證明：要證明R是個等價的、對稱的和可傳遞的。，就必須證明R是自反(a)由于C是X的劃分，C必定覆蓋X。對任意的x Î X必有X屬于C的某一個元素S。所以對于每一x Î X，都有xRx，即R是自反的。個39/45等價與集合的劃分證明：（b） 和y Î S，且 x Î SxRy。于是一個SC，所以有yRx。因此，R是對稱的。（c）xRy和yRz。于是兩個元素S1 Î C和S2Î C，且x, y Î S1 和 y, z Î S2¹ Æ。這樣就有S1=S2，所以有S1I S2因此，z &