離散數(shù)學(xué)第二章

1、11 1第二章第二章 關(guān)關(guān) 系系 本本章討論的關(guān)系（主要是二元關(guān)系），它仍然是一種章討論的關(guān)系（主要是二元關(guān)系），它仍然是一種集合，但它是比第一章更為復(fù)雜的集合。它的元素是有序集合，但它是比第一章更為復(fù)雜的集合。它的元素是有序二元組的形式，這些有序二元組中的兩個元素來自于兩個二元組的形式，這些有序二元組中的兩個元素來自于兩個不同或者相同的集合。因此，關(guān)系是建立在其它集合基礎(chǔ)不同或者相同的集合。因此，關(guān)系是建立在其它集合基礎(chǔ)之上的集合。關(guān)系中的有序二元組反映了不同集合中元素之上的集合。關(guān)系中的有序二元組反映了不同集合中元素與元素之間的關(guān)系，或者同一集合中元素之間的關(guān)系。本與元素之間的關(guān)系，或者同

2、一集合中元素之間的關(guān)系。本章討論這些關(guān)系的表示方法、關(guān)系的運算以及關(guān)系的性質(zhì)，章討論這些關(guān)系的表示方法、關(guān)系的運算以及關(guān)系的性質(zhì)，最后討論集合最后討論集合A A上幾類特殊的關(guān)系。上幾類特殊的關(guān)系。 主要內(nèi)容如下：主要內(nèi)容如下：2.1 2.1 笛卡爾積與關(guān)系笛卡爾積與關(guān)系 2.5 2.5 等價關(guān)系等價關(guān)系2.2 2.2 關(guān)系的表示關(guān)系的表示 2.6 2.6 相容關(guān)系相容關(guān)系2.3 2.3 關(guān)系的復(fù)合運算關(guān)系的復(fù)合運算 2.7 2.7 偏序關(guān)系偏序關(guān)系2.4 2.4 關(guān)系的性質(zhì)與閉包關(guān)系的性質(zhì)與閉包22 2有序有序n n元組與元組與n n個元素的集合，是不相同的。個元素的集合，是不相同的。例如例如

3、 但但 ,cdbacdabdcba),(),(),(cdbacdabdcba2.1 2.1 笛卡爾積與關(guān)系笛卡爾積與關(guān)系 一、有序一、有序n n元組與笛卡爾積元組與笛卡爾積1. 1. 有序有序n n元組元組定義定義2-1 由由n n個具有給定次序的個體個具有給定次序的個體 組成的組成的序列稱為有序序列稱為有序n n元組，記作（元組，記作（ ）。）。naaa,21naaa,2133 3例如例如 4,4,3,2=4,3,24,4,3,2=4,3,2 但但 (4,4,3,2)(4,3,2)(4,4,3,2)(4,3,2) 定義定義2-22-2 設(shè)設(shè) 和和 是兩是兩個有序個有序n元組，若元組，若 ,則

4、稱這兩則稱這兩個有序個有序n元組相等，并記作元組相等，并記作 ),(21naaa),(21nbbbnnbababa,2211),(),(2121nnbbbaaa當(dāng)當(dāng)n=2n=2時，有序二元組時，有序二元組(a,b)(a,b)又稱為序偶。又稱為序偶。44 42. 2. 笛卡爾積笛卡爾積(1)(1)笛卡爾積的定義笛卡爾積的定義定義定義2-3 設(shè)設(shè)A,BA,B為任意集合，為任意集合， A A 和和 B B 的笛卡爾積用的笛卡爾積用 表表示，定義為示，定義為BA,| ),(BbAabaBA例例1 1 設(shè)設(shè) 則則 但但,1 , 0cbaBA), 1 (), 1 (), 1 (), 0(), 0(), 0

5、(cbacbaBA)1 ,(),1 ,(),1 ,(),0 ,(),0 ,(),0 ,(cbacbaAB當(dāng)當(dāng) 或者或者 時，時， ，即，即 。AB BAABABBA笛卡爾積笛卡爾積 我們常記作我們常記作AA2A,| ),(AaAaaaAjiji2 例例2 2 設(shè)設(shè) 則則 1 ,0A),(),(),(),(110110002AAA55 5（2 2）笛卡爾積的基數(shù)）笛卡爾積的基數(shù)當(dāng)當(dāng) A 和和 B 均 是 有 限 集 時 ，均 是 有 限 集 時 ， 必 為 有 限 集 ， 而 且必 為 有 限 集 ， 而 且當(dāng)其中有一個是無限集時，必為無限集。當(dāng)其中有一個是無限集時，必為無限集。（3 3）與笛卡

6、爾積有關(guān)的一些恒等式）與笛卡爾積有關(guān)的一些恒等式設(shè)設(shè)A、B、C是任意的集合，則有是任意的集合，則有 1） 2） 3） 4） )()()(CABACBA)()()(ACABACB)()()(CABACBA)()()(ACABACBBABABA#)(#66 6以第一個等式以第一個等式 為例，給出其證明。為例，給出其證明。)()()(CABACBA證明證明 設(shè)設(shè) ， )(),(CBAyx則則 ，且，且 , ,AxCBy因此因此 或或 。 ),(ByAx),(CyAx于是于是 或或 ， BAyx),(CAyx),(即即 ， )()(),(CABAyx故故 。 )()()(CABACBA即即 ，且（，且

7、（ 或或 ) )，AxCy By 77 7反之，設(shè)反之，設(shè) ， )()(),(CABAyx則則 或或 ， BAyx),(CAyx),(于是于是( ( 且且 ）或）或( ( 且且 ），）， AxByAxCy即即 且（且（ 或或 ）, , AxByCy即即 且且 ，因此，因此 , ,AxCBy)(),(CBAyx故故 。 )()()(CBACABA由上證得由上證得)()()(CABACBA88 8BABA 二、關(guān)系二、關(guān)系1. 1. 關(guān)系的定義關(guān)系的定義定義定義2-4 笛笛卡爾積卡爾積 的任意一個子集的任意一個子集 稱為稱為是由是由A到到B的一個二元關(guān)系，當(dāng)?shù)囊粋€二元關(guān)系，當(dāng) 時，稱時，稱 是是A

8、上的二元關(guān)系上的二元關(guān)系。 99 9例例3 設(shè)設(shè)A=a,b，B=2,5,8 則則 )8 ,(),5 ,(),2 ,(),8 ,(),5 ,(),2 ,(bbbaaaBA令令 )2 ,(),8 ,(),2 ,(1baa)5 ,(),2 ,(),5 ,(2bba)2 ,(3a因為因為 ， ， 。BA1BA2BA3所以，所以， , 和和 均是由均是由A到到B的關(guān)系。的關(guān)系。123又又 ), 8(), 5(), 2(), 8(), 5(), 2(bbbaaaAB令令 ), 2(), 2(4ba), 8(), 8(), 5(5baa因為因為 , 。AB4AB5所以所以 和和 均是由均是由 B 到到 A

9、的關(guān)系。的關(guān)系。45101010對于對于 ,)8 , 8 (),5 , 8 (),2 , 8 (),8 , 5 (),5 , 5 (),2 , 5 (),8 , 2 (),5 , 2 (),2 , 2(BB,852B令令 ),(),(),(2825226)5 , 2(),8 , 2(),2 , 5(),5 , 8(7因為因為 ， . . BB6BB751a所以所以 和和 均是集合均是集合B上的關(guān)系。上的關(guān)系。若若 ，則稱，則稱a與與b有關(guān)系有關(guān)系 ，又記作，又記作 。 若若 ，則稱，則稱a與與b沒有關(guān)系沒有關(guān)系 ，又記作，又記作 。例如例如 在例在例3中中 ， ，但，但 67),(baba),

10、(baba81a21a111111 全域關(guān)系（或普遍關(guān)系）全域關(guān)系（或普遍關(guān)系） 因為因為 , , 。 所以所以 是一個由是一個由 到到 的關(guān)系。的關(guān)系。 是是 上的一個關(guān)系。上的一個關(guān)系。 常將常將 記作記作 BABAAAAAAA,| ),(AaaaaUjijiAAAABAAB2. 2. 幾種特殊的關(guān)系幾種特殊的關(guān)系 空關(guān)系空關(guān)系 對任意集合對任意集合 . .所以所以 是由是由 到到 的關(guān)系，的關(guān)系， 也是也是 上的關(guān)系，稱為空關(guān)系。上的關(guān)系，稱為空關(guān)系。 AABABA,ABA121212 恒等關(guān)系恒等關(guān)系定義集合定義集合 上的恒等關(guān)系上的恒等關(guān)系| ),(AaaaIAA例例4 4 設(shè)設(shè) ,

11、cbaA 則下面集合則下面集合 AAUA),(),(),(cabaaa),(),(),(cbbbab 是是 上的恒等關(guān)系。上的恒等關(guān)系。 ),(),(),(ccbbaaIAA),(),(),(ccbcac是是 上的普遍關(guān)系。上的普遍關(guān)系。A131313 3. 3. 關(guān)系的定義域和值域關(guān)系的定義域和值域 定義定義2-5 設(shè)設(shè) 是由是由 到到 的一個關(guān)系，的一個關(guān)系， 的的定義域定義域記作記作 ， 的的值域值域記作記作 ，分別定義為：，分別定義為：ABRD,|baBbAaaD使得且存在 ,|baAaBbbR使得且存在 顯然有顯然有 BRAD,例例5 5 設(shè)設(shè) 。 9 , 8 , 7 , 6 , 2

12、,5 , 3 , 2BA 由由 到到 的關(guān)系的關(guān)系 定義為：當(dāng)且僅當(dāng)定義為：當(dāng)且僅當(dāng)a a整除整除b b時，時，有有 。ABba于是于是 )9 , 3(),6 , 3(),8 , 2(),6 , 2(),2 , 2( 的定義域的定義域 ，值域，值域3 , 2D9 , 8 , 6 , 2RAB14141420,),4 , 0(),2 , 0(),0 , 0(210,420,)2 , 4(),1 , 1 (4 , 13 , 2 , 1B5 , 4 , 3 , 2 , 1A2.2.設(shè)設(shè) ， ，由，由 到到 的關(guān)系的關(guān)系則用列舉法表示則用列舉法表示 AB| ),(2babaDR2 , 1練習(xí)練習(xí)2-1

13、2-11.1.設(shè)設(shè) ，由，由 到到 的關(guān)系的關(guān)系則用列舉法表示則用列舉法表示 4 , 2 , 0,2 , 1 , 0BA| ),(BAabbaBADRAB),2 , 1 (),0 , 1 ()0 , 2(151515)2 , 1 (),1 , 1 (),2 , 0(),1 , 0(3. 3. 設(shè)設(shè) , , 。則則 ,2110BA BA BB)2 , 2(),1 , 2(),2 , 1 (),1 , 1 (624. ,4. ,則則 _ _ _ _ 由由 到到 不同的關(guān)系的個數(shù)是不同的關(guān)系的個數(shù)是 _ _ 2#A3#B)(#BA)2(#BAAB626161616165. 5. 設(shè)設(shè) 則則 _ _

14、_ A上不同關(guān)系的個數(shù)是上不同關(guān)系的個數(shù)是 _ 4A#)(#AA)(#AA21621622n6. 6. 設(shè)設(shè)則則 _ _ _ A上不同關(guān)系的個數(shù)是上不同關(guān)系的個數(shù)是 _ _ nA #)(#AA)(#AA2)(22n)(22n1717172.2 2.2 關(guān)系的表示關(guān)系的表示 一、集合表示法一、集合表示法用用表示集合的列舉法或描述法來表示關(guān)系表示集合的列舉法或描述法來表示關(guān)系。,751B 例例1 1 設(shè)設(shè) , , , , 用描述用描述法定義由法定義由A A到到B B的關(guān)系的關(guān)系 ，試，試用列舉法將用列舉法將 表示出來。表示出來。 ,8432A| ),(baba解解 ),(),(7252),(),(

15、7353),(),(7454181818 例例2 2 有王、張、李、何是某校的老師，該校有有王、張、李、何是某校的老師，該校有三門課程：語文、數(shù)學(xué)和英語，已知王可以教語文三門課程：語文、數(shù)學(xué)和英語，已知王可以教語文和數(shù)學(xué)，張可以教語文和英語，李可以教數(shù)學(xué)，何和數(shù)學(xué)，張可以教語文和英語，李可以教數(shù)學(xué)，何可以教英語，若記可以教英語，若記A=A=王，張，李，何王，張，李，何 ，B=B=語文，語文，數(shù)學(xué)，英語數(shù)學(xué)，英語 。那么這些老師與課程之間的對應(yīng)關(guān)系。那么這些老師與課程之間的對應(yīng)關(guān)系就可以用由就可以用由A A到到B B的一個關(guān)系的一個關(guān)系 中的序偶來表示。中的序偶來表示。 =(王王,語文語文),(

16、王王,數(shù)學(xué)數(shù)學(xué)),(張張,語文語文),(張張,英語英語),(李李,數(shù)數(shù) 學(xué)學(xué)),(何何,英語英語)191919二、矩陣表示法二、矩陣表示法 ijrM 定義定義2-6 設(shè)設(shè) A A 、B B 都是有限集，都是有限集， , , ，由，由A A到到B B的關(guān)系的關(guān)系 可以用一個可以用一個 的矩陣的矩陣 來表示，來表示， 的第的第i i行第行第j j列的元素列的元素 取值如下：取值如下：矩陣矩陣 稱為稱為 的關(guān)系矩陣。的關(guān)系矩陣。 ,naaaA21,21mbbbBmnMjijiijbabar若若01M例例1 1中由中由A A到到B B的關(guān)系的關(guān)系 可以用可以用一個一個 的矩陣來表示。的矩陣來表示。34

17、0001101101108432M 1 5 7 1 5 7202020例例3 3 設(shè)設(shè) ，A上的關(guān)系上的關(guān)系解解 ,4321A| ),(的整數(shù)倍是xyyx),(),(),(),(),(),(),(),(4433422241312111則則 可以用一個可以用一個 的矩陣來表示。的矩陣來表示。 4410000100101011114321M 1 2 3 4212121三、關(guān)系圖表示法三、關(guān)系圖表示法關(guān)系圖由結(jié)點和邊組成關(guān)系圖由結(jié)點和邊組成 例如例如 例例1 1中的中的 ， , ,8 , 4 , 3 , 2A,751B),(),(),(),(),(),(745473537252則則的關(guān)系圖如下的關(guān)系

18、圖如下AB222222例如例如 例例3 3中的中的 ，,4321A),(),(),(),(),(),(),(),(4433422241312111 的關(guān)系圖如下：的關(guān)系圖如下： 232323,210A,420B),(),(),(),(),(),(022101402000練習(xí)練習(xí)2.22.21.1. 設(shè)設(shè) ， ，A A到到B B的關(guān)系的關(guān)系 試構(gòu)造出試構(gòu)造出 的關(guān)系矩陣的關(guān)系矩陣 0 2 4 210M001011111242424122. 2. 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系 試畫出試畫出 和和 的關(guān)系圖。的關(guān)系圖。 ,654321A| ),(jiji整除1| ),(是素數(shù)jiji2252525

19、 2.3 2.3 關(guān)系的復(fù)合運算關(guān)系的復(fù)合運算 一、關(guān)系的并、交、補運算一、關(guān)系的并、交、補運算例例1 1 設(shè)設(shè) ， ),(),(),(3342211),(),(),(2442312則則),(),(),(),(),(243133422121),( 4221),(),(332121若若 和和 都是由集合都是由集合 A A 到到 B B 的關(guān)系，的關(guān)系，則則 ， 。于是于是 ， ，因此因此 ， 和和 也都是由也都是由 A A 到到 B B 的關(guān)系。的關(guān)系。12BA1BA2BA21BA21BA21212121262626若將若將 看作是全集看作是全集U U，則，則也都是由也都是由A A到到B B的關(guān)

20、系。的關(guān)系。BA),( | ),(11baba),( | ),(22baba例例2 2 設(shè)設(shè) ，, 32A,984B這里這里 . . ),(),(),(),(),(),(938343928242 BA設(shè)由設(shè)由A A到到B B的關(guān)系的關(guān)系 , , ),(),(82421),( 932則則 ； ； ),(),(),(9382422121),(),(824221),(),(),(),(938343921均是由均是由A A到到B B的關(guān)系。的關(guān)系。 272727 二、求逆關(guān)系的運算二、求逆關(guān)系的運算 定義定義2-7 設(shè)設(shè) A A 、 B B 是任意集合，是任意集合， 是由是由 A A 到到 B B 的

21、關(guān)系，的關(guān)系，定義由定義由 B B 到到 A A 的關(guān)系的關(guān)系稱稱 為關(guān)系為關(guān)系 的逆關(guān)系。的逆關(guān)系。 ),( | ),(baab解解 由由 的定義知的定義知),(),(),(1026242于是于是 ),(),(),(),(),(510362102624),( 63),( 105 例例3 3 設(shè)設(shè) ， ， 定義由定義由A A到到B B的關(guān)的關(guān)系系 ：當(dāng)且僅當(dāng)：當(dāng)且僅當(dāng) a a 整除整除 b b 時，有時，有 ，試求，試求 的逆關(guān)系的逆關(guān)系 。 ,532A,1064Bba282828三、關(guān)系的復(fù)合運算三、關(guān)系的復(fù)合運算1. 1. 復(fù)合關(guān)系的定義復(fù)合關(guān)系的定義21 定義定義2-8 設(shè)設(shè) 是由是由A

22、 A到到B B的關(guān)系，的關(guān)系， 是由是由B B到到C C的的關(guān)系，則關(guān)系，則 和和 的復(fù)合關(guān)系是一個由的復(fù)合關(guān)系是一個由A A到到C C的關(guān)系，的關(guān)系，用用 表示，定義為：當(dāng)且僅當(dāng)存在元素表示，定義為：當(dāng)且僅當(dāng)存在元素 ，使得使得 ， 時，有時，有 。 這種由這種由 和和 求復(fù)合關(guān)系求復(fù)合關(guān)系 的運算稱為的運算稱為關(guān)系的復(fù)合運算。關(guān)系的復(fù)合運算。 12Bbba1cb2ca)(21122112292929 例例4 4 設(shè)設(shè) 是由是由 到到 的關(guān)系。的關(guān)系。 是由是由 B B 到到 的關(guān)系。的關(guān)系。分別定義為：分別定義為：1 ,4321A,432B2,653C),(),(),(| ),(24334

23、261baba),(),(),(| ),(6333622cbcb整除于是復(fù)合關(guān)系于是復(fù)合關(guān)系 ),(),(),(646333213030302. 2. 關(guān)系復(fù)合運算的性質(zhì)關(guān)系復(fù)合運算的性質(zhì)定理定理2-12-1 設(shè)設(shè) 是由集合是由集合A A到到B B的關(guān)系，則的關(guān)系，則 BAII1例例5 5 以例以例4 4中的關(guān)系中的關(guān)系 為例，為例， ),(),(),(243342111AI11BI),(),(),(),(44332211AI),(),(),(443322BI ,從關(guān)系圖，可得從關(guān)系圖，可得 ,313131 定理定理2-22-2 設(shè)設(shè) 是由是由A A到到B B的關(guān)系，的關(guān)系， 是由是由B B到

24、到C C的關(guān)的關(guān)系，系， 是由是由C C到到D D的關(guān)系，則有的關(guān)系，則有 123)()(321321 例例6 6 設(shè)設(shè) ， ， , ., . A A到到B B的關(guān)系的關(guān)系 B B到到C C的關(guān)系的關(guān)系 C C到到D D的關(guān)系的關(guān)系 ,4321A,432B,321C,654D),(),(),(2432421),(),(),(3423122),(),(),(),(636251423則則A A到到C C的關(guān)系的關(guān)系 ),(),(),(14223221因此因此),(),(),()(544262321),(),(),(),(6463435232因此因此),(),(),()(544262321所以所以)

25、()(321321323232一般地，若一般地，若 是一由是一由 到到 的關(guān)系，的關(guān)系， 是由是由 到到 的關(guān)系，的關(guān)系， 是一由是一由 到到 的關(guān)系，則不的關(guān)系，則不加括號的表達加括號的表達式式 ， 唯一地表示一由唯一地表示一由 到到 的關(guān)系，在計算這一關(guān)系時，可以運用結(jié)合律的關(guān)系，在計算這一關(guān)系時，可以運用結(jié)合律將其中任意兩個相鄰的關(guān)系先結(jié)合。將其中任意兩個相鄰的關(guān)系先結(jié)合。特別特別, ,當(dāng)當(dāng) ， 時，復(fù)合關(guān)系時，復(fù)合關(guān)系 簡記作簡記作 ，它也是集，它也是集 A A 上的一個關(guān)系。上的一個關(guān)系。11A2A23A2AnnA1nAn211A1nAAAAAn121n21n333333 3. 3.

26、 求復(fù)合關(guān)系的幾種方法求復(fù)合關(guān)系的幾種方法（1 1）根據(jù)復(fù)合關(guān)系的定義求復(fù)合關(guān)系）根據(jù)復(fù)合關(guān)系的定義求復(fù)合關(guān)系 例例6 6中求復(fù)合關(guān)系采用的就是這種方法。中求復(fù)合關(guān)系采用的就是這種方法。 12又例如又例如 下面的關(guān)系圖給出了從集合下面的關(guān)系圖給出了從集合A A到到B B的關(guān)系的關(guān)系 和從和從B B到到C C的關(guān)系的關(guān)系),(),(),(13322221343434（2 2）運用關(guān)系矩陣的運算求復(fù)合關(guān)系）運用關(guān)系矩陣的運算求復(fù)合關(guān)系布爾運算布爾運算其加法和乘法運算定義如下其加法和乘法運算定義如下00011101101110000110 , ,例如例如 11100011110001)()()()(

27、)(353535 關(guān)系矩陣的乘積關(guān)系矩陣的乘積 對兩個關(guān)系矩陣求其乘積時，其運算法則與一般對兩個關(guān)系矩陣求其乘積時，其運算法則與一般矩陣的乘法是相同的，但其中的加法運算和乘法運矩陣的乘法是相同的，但其中的加法運算和乘法運算應(yīng)改為布爾加和布爾乘。算應(yīng)改為布爾加和布爾乘。 00101010100121MM則則例例7 7 設(shè)設(shè) 和和 是兩個關(guān)系矩陣是兩個關(guān)系矩陣0010101000011M1010100012M1M2M363636 復(fù)合關(guān)系的關(guān)系矩陣復(fù)合關(guān)系的關(guān)系矩陣 定理定理2-32-3 設(shè)設(shè)A A、B B、C C均是有限集，均是有限集， 是一由是一由A A到到B B的關(guān)系的關(guān)系, , 是一由是一

28、由B B到到C C的關(guān)系，它們的關(guān)系的關(guān)系，它們的關(guān)系矩陣分別為矩陣分別為 和和 ，則復(fù)合關(guān)系，則復(fù)合關(guān)系 的的關(guān)系矩陣關(guān)系矩陣 121M2M212121MMM373737例例8 8 設(shè)有集合設(shè)有集合 ， ， A A到到B B的關(guān)系的關(guān)系 B B到到C C的關(guān)系的關(guān)系 則則,4321A,432B3 , 2 , 1C),(),(),(),(341423122),(),(),(),(243342211),(),(),(),(),(1423321211212 3 4 1 2 3 1 2 300101010000143211M1010100014322M001010101001432121M與例與例7

29、 7比較得比較得 2121MMM383838 例例9 9 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系 試求試求 和和 。,dcbaA ),(),(),(),(),(cbdcccabba23 解解 作出的關(guān)系矩陣作出的關(guān)系矩陣 a b c da b c d0000110001010010dcbaM0000110011100101000011000101001000001100010100102MMM因此因此),(),(),(),(),(),(),(2dcccdbcbbbcaaa根據(jù)定理根據(jù)定理2-32-3393939又又 ，所以，所以2300001100110111100000110011100101000

30、011000101001023MMM因此因此),(),(),(),(),(),(),(),(3dcccdbcbabdacaba404040（3 3）利用關(guān)系圖求復(fù)合關(guān)系）利用關(guān)系圖求復(fù)合關(guān)系n 設(shè)設(shè) 是有限集是有限集A A上的關(guān)系，則復(fù)合關(guān)系上的關(guān)系，則復(fù)合關(guān)系 也是也是A A上的關(guān)上的關(guān)系，由復(fù)合關(guān)系的定義，對于任意的系，由復(fù)合關(guān)系的定義，對于任意的 ，當(dāng)且僅，當(dāng)且僅當(dāng)當(dāng) 存在，使得存在，使得 ， 時，有時，有 。2Aaaji,Aakkiaajkaajiaa2 反映在關(guān)系圖上，這意味著，當(dāng)且僅當(dāng)在反映在關(guān)系圖上，這意味著，當(dāng)且僅當(dāng)在 的關(guān)系圖中有的關(guān)系圖中有某一結(jié)點某一結(jié)點 存在，使得有邊由

31、存在，使得有邊由 指向指向 ，且有邊由，且有邊由 指指向向 時，在時，在 的關(guān)系圖中有邊從的關(guān)系圖中有邊從 指向指向 。 kaiakaka2iajajajakaiajaia2414141 類似地，對于任意正整數(shù)類似地，對于任意正整數(shù)n n，當(dāng)且僅當(dāng)在，當(dāng)且僅當(dāng)在 的的關(guān)系圖中存在關(guān)系圖中存在n-1n-1個結(jié)點個結(jié)點 , ,使得有使得有邊由邊由 指向指向 , ,由由 指向指向 ，由由 指向指向 時，在時，在 的關(guān)系圖中，有邊由結(jié)點的關(guān)系圖中，有邊由結(jié)點 指向指向 。121nkkkaaa,ia1ka1ka2ka1nkajaniaja根據(jù)根據(jù) 的關(guān)系圖構(gòu)造出的關(guān)系圖構(gòu)造出 的關(guān)系圖：的關(guān)系圖： n

32、對于對于 的關(guān)系圖中的每一結(jié)點的關(guān)系圖中的每一結(jié)點 ，找出從，找出從 經(jīng)過長為經(jīng)過長為n n的路能夠到達的結(jié)點，這些結(jié)點在的路能夠到達的結(jié)點，這些結(jié)點在 的關(guān)系圖中，邊必須由的關(guān)系圖中，邊必須由 指向它們。指向它們。iaiania424242例例1010 試利用構(gòu)造試利用構(gòu)造 和和 的關(guān)系圖的方法求例的關(guān)系圖的方法求例9 9中的中的 和和 。例中例中2323),(),(),(),(),(cbdcccabba（4 4）根據(jù)）根據(jù) 和和 的關(guān)的關(guān)系圖直接寫出系圖直接寫出 和和 中的序偶中的序偶. .2323解解（1 1）先）先作出作出 的關(guān)系圖的關(guān)系圖（2 2）構(gòu)造）構(gòu)造 的關(guān)系圖。的關(guān)系圖。在在

33、 的關(guān)的關(guān)系圖中尋系圖中尋找長為找長為2 2的的路。路。 2（3 3）構(gòu)造）構(gòu)造 的關(guān)系圖。的關(guān)系圖。在在 的關(guān)的關(guān)系圖中尋系圖中尋找長為找長為3 3的的路路. .3434343)3 , 3(),3 , 2(),2 , 2(),3 , 1 (),2 , 1 (),1 , 1 (練習(xí)練習(xí)2-32-31.1. 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系則則用列舉法表示用列舉法表示 3 , 2 , 1A| ),(yxyx1| ),(yxyx212111AA21)2 , 3(),1 , 3(),3 , 2(),1 , 2)(3 , 1 (),2 , 1 ()3 , 2(),3 , 1 (),2 , 3(),2 ,

34、 1 (),1 , 3(),1 , 2()2 , 3(),1 , 3(),1 , 2() 3 , 3(),2 , 2(),1 , 1 (444444則復(fù)合關(guān)系則復(fù)合關(guān)系 2. 2. 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系,3210A),(),(),(),(),(00123221101),(),(13022211221121) 1 , 2(),0 , 1 ()2 , 3(),0 , 2(),1 , 2()0 , 0(),1 , 0(),2 , 2(),1 , 1 (),3 , 1 (),2 , 0()2 , 2(),0 , 1 (),1 , 1 (454545 3. 3. 下圖給出了集合下圖給出了集合

35、上的關(guān)上的關(guān)系系 的關(guān)系圖，試畫出關(guān)系的關(guān)系圖，試畫出關(guān)系 和和 的關(guān)系圖。的關(guān)系圖。 ,654321A584646462.4 2.4 關(guān)系的性質(zhì)與閉包關(guān)系的性質(zhì)與閉包 一、集合一、集合A A上關(guān)系的性質(zhì)上關(guān)系的性質(zhì) 定義定義2-9 設(shè)設(shè) 是集合是集合A A上的關(guān)系上的關(guān)系 （1 1）若對于所有的）若對于所有的 ，均有，均有 ，則稱，則稱 在在A A上是自反的。上是自反的。 Aaaa （2 2）若對于所有的）若對于所有的 ，均有，均有 ，則稱，則稱 在在A A上是反自反的。上是反自反的。 Aaaa （3 3）對于所有的）對于所有的 ，若每當(dāng)有，若每當(dāng)有 就必有就必有 , , ，則稱則稱 在在

36、A A 上是對稱的。上是對稱的。 Aba,abba （4 4）對于所有的）對于所有的 ，若每當(dāng)有，若每當(dāng)有 和和 就就必有必有 ，則稱，則稱 在在 A A 上是反對稱的。上是反對稱的。 Aba,abba ba （5 5）對于所有的）對于所有的 ，若每當(dāng)有，若每當(dāng)有 和和 就必有就必有 ，則稱，則稱 在在 A A 上是可傳遞的。上是可傳遞的。 Acba,bacbca474747例例1 1 設(shè)設(shè) ， （1 1）自反與反自反）自反與反自反 ,3210A),(),(),(),(332211001),(),(),(),(),(),(3211223321002),(),(),(3300123),(),()

37、,(2132104自反自反自反自反非自反非自反反自反反自反484848 （2 2）對稱與反對稱）對稱與反對稱),(),(),(),(),(23321221115),(),(),(),(132011216),(),(),(),(233222217),(),(),(1122008對稱，非反對稱對稱，非反對稱非對稱，反對稱非對稱，反對稱非對稱，非反對稱非對稱，非反對稱對稱，反對稱對稱，反對稱494949（3 3）可傳遞與不可傳遞）可傳遞與不可傳遞),(),(),(),(303220009),(),(),(),(3212211110),(),(),(23032111可傳遞可傳遞不可傳遞不可傳遞可傳遞可

38、傳遞505050例例2 2 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系,54321A| ),(是偶數(shù)baba),(),(),(513111則則),(),(),(531333),(),(4424),(),(),(553515),(),(4222自反自反對稱對稱不是反對稱不是反對稱對于任意的對于任意的 ，若，若 ， Acba,ncbmba22,則則 也是偶數(shù)。也是偶數(shù)。 )()()(nmcbbaca2因此因此 是可傳遞的。是可傳遞的。 515151二、如何利用關(guān)系矩陣和關(guān)系圖來判斷關(guān)系二、如何利用關(guān)系矩陣和關(guān)系圖來判斷關(guān)系的性質(zhì)的性質(zhì)1. 1. 關(guān)系矩陣關(guān)系矩陣 10000100101011114321M 1

39、 2 3 4若若 是對稱的，則關(guān)系矩陣關(guān)于主對角線對稱。是對稱的，則關(guān)系矩陣關(guān)于主對角線對稱。若若 是反對稱的，則關(guān)系矩陣中，關(guān)于主對角線對稱的元是反對稱的，則關(guān)系矩陣中，關(guān)于主對角線對稱的元素不同時為素不同時為1 1。 若若 是自反的，則關(guān)系矩陣的主對角線上的所有元素均為是自反的，則關(guān)系矩陣的主對角線上的所有元素均為1 1。若若 是反自反的，則關(guān)系矩陣的主對角線上所有元素均為是反自反的，則關(guān)系矩陣的主對角線上所有元素均為0 0。 5252522. 2. 關(guān)系圖關(guān)系圖 若若 是自反的，則關(guān)系圖中每一結(jié)點引出一個指向自身是自反的，則關(guān)系圖中每一結(jié)點引出一個指向自身的單邊環(huán)。的單邊環(huán)。 若若 是反

40、自反的，則關(guān)系圖中每一結(jié)點均沒有單邊環(huán)。是反自反的，則關(guān)系圖中每一結(jié)點均沒有單邊環(huán)。 若若 是對稱的，則在關(guān)系圖中，若兩結(jié)點之間存在有邊，是對稱的，則在關(guān)系圖中，若兩結(jié)點之間存在有邊，則必存在兩條方向相反的邊。則必存在兩條方向相反的邊。 若若 是反對稱的，則在關(guān)系圖中，任意兩個不同的結(jié)點間是反對稱的，則在關(guān)系圖中，任意兩個不同的結(jié)點間至多只有一條邊。至多只有一條邊。 ka 若若 是可傳遞的，則在關(guān)系圖中，若每當(dāng)有邊由是可傳遞的，則在關(guān)系圖中，若每當(dāng)有邊由 指指向向 ，且又有邊由，且又有邊由 指向指向 ，則必有一條邊由，則必有一條邊由 指向指向 。 iajaiajaka535353例例3 3 設(shè)

41、設(shè) ，下面分別給出集合，下面分別給出集合A A上三個關(guān)系的上三個關(guān)系的關(guān)系圖，試判斷它們的性質(zhì)。關(guān)系圖，試判斷它們的性質(zhì)。 ,321A解解 （1 1） 是自反的，非對稱，不是反對稱，不可傳遞。是自反的，非對稱，不是反對稱，不可傳遞。 1（2 2） 非自反，也不是反自反，非對稱，反對稱，非自反，也不是反自反，非對稱，反對稱， 可傳遞。可傳遞。 2（3 3） 是自反的，對稱的，可傳遞的，不是反自反，是自反的，對稱的，可傳遞的，不是反自反，也不是反對稱。也不是反對稱。 3545454三、集合三、集合A A上關(guān)系的閉包上關(guān)系的閉包1. 1. 閉包的定義閉包的定義 例例4 4 設(shè)設(shè) ，A A上的關(guān)系上的

42、關(guān)系 , ,則則 ,3210A),(),(),(321000),(),(),(),(),(),(),(),(),(),(),(),(),()(32103322110033221100321000AIr顯然，顯然， 是自反的。是自反的。 )(r 定義定義2-10 設(shè)設(shè) 是集合是集合A A上的關(guān)系，由下式定義的上的關(guān)系，由下式定義的A A上上的關(guān)系的關(guān)系 稱為稱為 的自反閉包。的自反閉包。 AIr)(555555 定義定義2-11 設(shè)設(shè) 是集合是集合A A上的關(guān)系，由下式定上的關(guān)系，由下式定義的義的A A上的關(guān)系上的關(guān)系 稱為稱為 的對稱閉包。的對稱閉包。 )(s例例5 5 例例4 4中的中的 。

43、 ),(),(),(321000它不是對稱的它不是對稱的, , ),(),(),(230100則則),(),(),(),(),(),(),(),(),(),(),()(2332011000230100321000s顯然，顯然， 是對稱的。是對稱的。 )(s565656 定義定義2-12 設(shè)設(shè) 是集合是集合A A上的關(guān)系，由下式定義的上的關(guān)系，由下式定義的A A上上的關(guān)系的關(guān)系稱為稱為 的傳遞閉包。的傳遞閉包。 321iit)( 當(dāng)當(dāng)A A是有限集時，是有限集時，A A上只有有限個不同的關(guān)系，因此，上只有有限個不同的關(guān)系，因此，存在某個正整數(shù)存在某個正整數(shù)m m，使得，使得imit1)( 事實上

44、，可以證明，若事實上，可以證明，若 ，則，則nA #init1)(575757例例6 6 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系 ,dcbaA ),(),(),(),(dccbabba則則),(),(),(),(2dbbbcaaa),(),(),(),(3cbabdaba),(),(),(),(4dbbbcaaa注意到注意到 , 則則 ，24,357246354131iiiidcdbcbbbabdacaaabat),(),(),(),(),(),(),(),(),()(585858)(rr)(r 2. 2. 閉包的性質(zhì)閉包的性質(zhì) 集合集合A A上關(guān)系的三個不同的閉包具有如下類似的性質(zhì)。上關(guān)系的三個不同

45、的閉包具有如下類似的性質(zhì)。 定理定理2-4 設(shè)設(shè) 是集合是集合A A上的關(guān)系，則上的關(guān)系，則 的自反閉包的自反閉包 具有以下性質(zhì)：具有以下性質(zhì)： （1 1） 。 （2 2） 是自反的。是自反的。 （3 3）對于）對于A A上任何關(guān)系上任何關(guān)系 ，若，若 自反且自反且 ，則則)(rrrrr)( 證明證明 ，所以性質(zhì)（，所以性質(zhì)（1 1）, ,（2 2）顯然成立。）顯然成立。 IAr)(設(shè)設(shè) 是是A A上的關(guān)系，上的關(guān)系， 自反且自反且 ，rrr則由則由 自反，可知自反，可知rrAI由由 和和 知知 ，即，即 。rAIrrAIrr)(595959s 定理定理2-5 設(shè)設(shè) 是集合是集合A A上的關(guān)系

46、，則上的關(guān)系，則 的對稱閉包的對稱閉包 具有如下性質(zhì)：具有如下性質(zhì)： （1 1） （2 2） 是對稱的是對稱的 （3 3）對于）對于A A上任何關(guān)系上任何關(guān)系 ，若，若 對稱且對稱且 ， 則則)(s)(s)(ssSss)(證明證明 所以性質(zhì)（所以性質(zhì)（1 1）、（）、（2 2）顯然成立，）顯然成立， )(s設(shè)設(shè) 是是A A上的關(guān)系，上的關(guān)系， 對稱且對稱且 ，則對任意，則對任意sss),(ab必有必有 ，由，由 ，必有，必有 ， ),(bassba),(又由又由 的對稱性，有的對稱性，有 ，因此，因此 。 ssab),(s由由 和和 知知 ，即，即 。 sssss)(606060 定理定理2-

47、6 設(shè)設(shè) 是集合是集合A A上的關(guān)系，則上的關(guān)系，則 的傳遞閉包的傳遞閉包 具有如下性質(zhì)具有如下性質(zhì): : （1 1） （2 2） 是可傳遞的是可傳遞的 （3 3）對于）對于A A上任何關(guān)系上任何關(guān)系 ，若，若 可傳遞且可傳遞且 ， 則則 。 )(t)(t)(tttttt)( 證明證明 根據(jù)根據(jù) ，性質(zhì)（，性質(zhì)（1 1）顯然成立。）顯然成立。 1iit)(設(shè)設(shè) ，)(),(),(),(tcbtba 則必存在正整數(shù)則必存在正整數(shù)h和和k，使得使得 ，即，即 ，khcbba),( ,),(cbbakh, 于是于是 ， 即即 ，cakhkhca),( 因此因此 ，故，故 是可傳遞的是可傳遞的.)()

48、,(tca)(t616161設(shè)設(shè) 是是A A上的任意一個包含上的任意一個包含 的可傳遞關(guān)系。的可傳遞關(guān)系。 t又設(shè)又設(shè))(),(tba121kbbb, 因此必存在元素因此必存在元素 ，使得使得bbbbbak1211,因為因為 ，所以，所以 。tbbbbbatktt1211,而而 是可傳遞的，因此是可傳遞的，因此 即即 ，故，故有有 。 tbattba),(tt)(bakkba),( ，則存在正整數(shù)，則存在正整數(shù)k k，使得，使得 ，626262四、如何利用關(guān)系矩陣和關(guān)系圖求關(guān)系四、如何利用關(guān)系矩陣和關(guān)系圖求關(guān)系的閉包的閉包例例7 7 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系求求 。 ,dcbaA ),(

49、),(),(),(dccbabba)(),(),(tsr1. 1. 利用關(guān)系矩陣求利用關(guān)系矩陣求 的閉包的閉包(1)(1)0000100001010010dcbaMdcba1000010000100001dcbaMdcbaAI636363因為因為 所以所以AIr)(100011000111001110000100001000010000100001010010dcbaMdcbar)(于是于是 ),(),(),(),(),(),(),(),()(dddccccbbbabbaaar646464 (2) (2) 若若 ，則，則 ； ， 則則 ， ),(jiaa),(ijaa),(jiaa),(ija

50、a即為若即為若 中中 , ,則則 中中M1ijr1jirM若若 中中 ，則，則 中中 。這說明。這說明 是是 的轉(zhuǎn)置矩陣。的轉(zhuǎn)置矩陣。 M0ijrM0jirMM根據(jù)根據(jù) 的關(guān)系矩陣。的關(guān)系矩陣。)(,)(ss)(MMMs010010100101001001000010000100100000100001010010dcbaMdcbas)(于是于是),(),(),(),(),(),()(cddcbccbabbas656565（3 3）因為）因為 ，所以，所以4#A41432iit)(對任意對任意 ，只要，只要 屬于屬于 、 、 、中任何一個關(guān)系，則中任何一個關(guān)系，則 ， AAba),(),(ba

51、234)(),(tba于是于是432MMMMMt)(00000000010110100000000010100101000010000101001023MMM0000000010100101000010000101001000001000010100102MMM66666600000000101001010000000001011010000010000101001034MMM32MMMMt)(0000000001011010000000001010010100001000010100100000100011111111dcba于是于是 ),(),(),(),(),(),(),(),(),()

52、(dcdbcbbbabdacabaaat6767672. 2. 利用關(guān)系圖求利用關(guān)系圖求 的閉包的閉包例例8 8 對例對例7 7中的關(guān)系中的關(guān)系 ，利用關(guān)系圖求其閉包。，利用關(guān)系圖求其閉包。的關(guān)系圖的關(guān)系圖r r() 的關(guān)系圖的關(guān)系圖t t()()的關(guān)系圖的關(guān)系圖S()S()的關(guān)系圖的關(guān)系圖686868練習(xí)練習(xí)2-42-41. 1. 從下列各題給出的備選答案中選出正確的答案，并將其代從下列各題給出的備選答案中選出正確的答案，并將其代號填入題后面的括號內(nèi)。號填入題后面的括號內(nèi)。(1) (1) 設(shè)設(shè)A=0,1,2,3A=0,1,2,3，A A上的關(guān)系上的關(guān)系=(0,0),(0,2),(1,1),(

53、1,3),(2,2),(2,0),(3,1)=(0,0),(0,2),(1,1),(1,3),(2,2),(2,0),(3,1)，則，則是是A.A. 自反的自反的 B. B. 對稱的對稱的 C. C. 反對稱的反對稱的 D. D. 可傳遞的可傳遞的 ( ) B （2) 2) 設(shè)設(shè)是整數(shù)集是整數(shù)集I I上的關(guān)系，定義為當(dāng)且僅當(dāng)上的關(guān)系，定義為當(dāng)且僅當(dāng) 時時 ， ，則，則是是A. 自反的自反的 B. B. 對稱的對稱的 C. C. 反對稱的反對稱的 D. D. 可傳遞的可傳遞的 ( )( )1021ii21ii A、B6969692.2. 下圖給出了下圖給出了1,2,31,2,3上三個關(guān)系的關(guān)系圖

54、，試對每一個圖上三個關(guān)系的關(guān)系圖，試對每一個圖所表示的關(guān)系的性質(zhì)作出判別，并將選中的性質(zhì)的代號填入所表示的關(guān)系的性質(zhì)作出判別，并將選中的性質(zhì)的代號填入相應(yīng)的括號內(nèi)。相應(yīng)的括號內(nèi)。 若若 A. A. 自反的自反的 B. B. 對稱的對稱的 C. C. 反對稱的反對稱的 D. D. 可傳遞可傳遞 E. E. 反自反反自反則則 是（是（ ）則則 是（是（ ）則則 是（是（ ） 123A AB B A A E E707070 3. 3. 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系對下列求出的閉包判斷正確與否，分別將對下列求出的閉包判斷正確與否，分別將“Y”Y”或或“N”N”填入后面的括號。填入后面的括號。 （ ）

55、 （ ） （ ） ,dcbaA ),(),(),(bcdbba),(),(),(),(),(),()(ddccbbaadbbar),(),(),(),(),(),()(cadcdabcdbbat),(),(),(),(),(),()(cbbdabbcdbbasN NY YN N7171712.5 2.5 等價關(guān)系等價關(guān)系 一、等價關(guān)系的定義一、等價關(guān)系的定義1. 1. 等價關(guān)系等價關(guān)系 定義定義2-13 集合集合A A上的關(guān)系上的關(guān)系，如果它是自反的，對，如果它是自反的，對稱的，且可傳遞的，則稱稱的，且可傳遞的，則稱是是A A上的等價關(guān)系。上的等價關(guān)系。 例如例如 數(shù)的相等關(guān)系是任何數(shù)集上的等

56、價關(guān)系。數(shù)的相等關(guān)系是任何數(shù)集上的等價關(guān)系。 又例如又例如 一群人的集合中姓氏相同的關(guān)系也是一群人的集合中姓氏相同的關(guān)系也是等價關(guān)系。等價關(guān)系。但朋友關(guān)系不是等價關(guān)系，因為它不可傳遞。但朋友關(guān)系不是等價關(guān)系，因為它不可傳遞。 727272 例例1 1 設(shè)設(shè)A A是任意集合，則是任意集合，則A A上的恒等關(guān)系和普上的恒等關(guān)系和普遍關(guān)系遍關(guān)系U UA A均是均是A A上的等價關(guān)系。上的等價關(guān)系。 例例2 2 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系,dcbaA ),(),(),(),(),(),(),(),(ddcddcccbbabbaaa是是A A上的等價關(guān)系。上的等價關(guān)系。 2. 2. 元素元素a a與

57、與b b等價等價 設(shè)設(shè)是集合是集合A A上的等價關(guān)系，若元素上的等價關(guān)系，若元素ab ab ，則，則稱稱a a與與b b等價，或稱等價，或稱b b與與a a等價。等價。 7373733. 3. 等價類等價類 定義定義2-14 設(shè)設(shè)是集合是集合A A上的等價關(guān)系，則上的等價關(guān)系，則 A A 中中等價于元素等價于元素 a a 的所有元素組成的集合稱為的所有元素組成的集合稱為 a a 生成生成的等價類，用的等價類，用 表示，即表示，即 a|baAbba且例如例如 對于例對于例2 2中的中的來說來說,babbaa,dcddcc7474741. 1. 對任意對任意 , 二、等價類的性質(zhì)二、等價類的性質(zhì)

58、Aaa因為對于任意的因為對于任意的aA,aA,有有aaaa，所以，所以 。aa 2. 2. 對任意的對任意的a,bA a,bA 若若 ab ab ，則，則 。ba由由的對稱性有的對稱性有xa xa ， 證明證明 若若 ，則，則ax ax ， ax又由又由的傳遞性有的傳遞性有xb xb ，因此，因此 bx故故 。 ba類似地可以證明類似地可以證明由上得由上得abba7575753. 3. 對任意對任意a,bAa,bA，若，若 ，則，則baba 證明證明（用反證法）（用反證法）假設(shè)假設(shè) , , ba則則A A中至少有一元素中至少有一元素 bax因此因此 且且 ，axbx即即xaxa，且，且xb,x

59、b, 于是由于是由ax,xbax,xb，得，得abab，故故 baba與與 相矛盾。相矛盾。767676例例3 3 設(shè)設(shè)A=a,b,c,dA=a,b,c,d，A A上的關(guān)系上的關(guān)系),(),(),(),(),(),(),(),(),(),(ddacbcabbbcccacbbaaa是是A上的等價關(guān)系上的等價關(guān)系 ,cbacbadd 同一個等價類中元素均相互等價。不同等價類同一個等價類中元素均相互等價。不同等價類中的元素互不等價。中的元素互不等價。 777777三、等價關(guān)系與分劃三、等價關(guān)系與分劃 集合集合A A上的等價關(guān)系與集合上的等價關(guān)系與集合A A上的分劃具有一一對應(yīng)關(guān)系。上的分劃具有一一對

60、應(yīng)關(guān)系。 定理定理2-7 設(shè)設(shè)是集合是集合A A上的一個等價關(guān)系，則集合上的一個等價關(guān)系，則集合A A中所中所有元素產(chǎn)生的等價類的集合有元素產(chǎn)生的等價類的集合 是是A A的一個分劃。的一個分劃。 （1 1）對每一元素）對每一元素aAaA， 是是A A的非空子集。的非空子集。 Aa （2 2）對任意）對任意a,bAa,bA，或者，或者 與與 是是A A的同一子集或的同一子集或者者 abba另一方面，對任一另一方面，對任一 ，而，而 ,xxAx有Aaax|Aaa （3 3）對所有的元素的等價類求并集，顯然有）對所有的元素的等價類求并集，顯然有 . .aAaA所以所以 ，因此，因此 ，故，故 。Aa