第4章二元關(guān)系(一)

1、第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系4.1 4.1 4.1 4.1 4.1 4.1 二元關(guān)系及其表示二元關(guān)系及其表示二元關(guān)系及其表示二元關(guān)系及其表示二元關(guān)系及其表示二元關(guān)系及其表示4.2 4.2 4.2 4.2 4.2 4.2 關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系的運(yùn)算4.3 4.3 4.3 4.3 4.3 4.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)關(guān)系的性質(zhì)關(guān)系的性質(zhì)關(guān)系的性質(zhì)關(guān)系的性質(zhì)4.4 4.4 4.4 4.4 4.4 4.4 關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算4.5 4.

2、5 4.5 4.5 4.5 4.5 等價關(guān)系等價關(guān)系等價關(guān)系等價關(guān)系等價關(guān)系等價關(guān)系4.6 4.6 4.6 4.6 4.6 4.6 相容關(guān)系相容關(guān)系相容關(guān)系相容關(guān)系相容關(guān)系相容關(guān)系第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 4 4 4.1 .1 .1二元關(guān)系及其表示二元關(guān)系及其表示二元關(guān)系及其表示 4 4 .1.1.1二元關(guān)系的概念二元關(guān)系的概念二元關(guān)系的概念 定義定義定義.14.1.1設(shè)設(shè)設(shè)A A A和和和B B B是任意集合，如果是任意集合，如果是任意集合，如果R R R A A AB B B，則稱則稱則稱

3、R R R是是是A A A到到到B B B的二元關(guān)系。如果的二元關(guān)系。如果的二元關(guān)系。如果R R R是是是A A A到到到A A A的二元關(guān)系，則稱的二元關(guān)系，則稱的二元關(guān)系，則稱R R R是是是A A A上上上的二元關(guān)系。的二元關(guān)系。的二元關(guān)系。 設(shè)設(shè)設(shè)A A A= = = 1,2,31,2,31,2,3 ，B B B= = = a a a, , ,b b b ，R=R=R=1, 1, 1,a a a , , , 2, 2, 2,a a a , , , 3, 3, 3,b b b。R R R是是是A A A到到到B B B的二元關(guān)系。的二元關(guān)系。的二元關(guān)系。S=S=S=3,13,13,1 ,

4、 , , 2,22,22,2 , , , 2,12,12,1 , , , 1,11,11,1。S S S是是是A A A上上上的的的二元關(guān)系。二元關(guān)系。二元關(guān)系。 定義定義定義.24.1.2設(shè)設(shè)設(shè)A A A和和和B B B是任意集合，是任意集合，是任意集合，R R R A A AB B B，若，若，若 x x x, , ,y y yR R R，則稱則稱則稱x x x與與與y y y有有有R R R關(guān)系。關(guān)系。關(guān)系。記為記為記為xRyxRyxRy。若。若。若 x x x, , ,y y yR R R，則稱，則稱，則稱x x x與與與y y y沒有沒有沒有R R R關(guān)系。記為關(guān)系。

5、記為關(guān)系。記為x yx yx y。R 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系定義定義定義.34.1.3設(shè)設(shè)設(shè)A A A和和和B B B是任意集合，空集是任意集合，空集是任意集合，空集叫做叫做叫做A A A到到到B B B的空關(guān)系，仍的空關(guān)系，仍的空關(guān)系，仍然記為然記為然記為。A A A，B B B的笛卡爾積的笛卡爾積的笛卡爾積A A AB B B叫做叫做叫做A A A到到到B B B的全域關(guān)系，記的全域關(guān)系，記的全域關(guān)系，記為為為E E E。集合。集合。集合a a a, , ,a a a | |a a a A A A 叫做叫做叫做A A A上的恒等關(guān)系。記為上的恒等關(guān)

6、系。記為上的恒等關(guān)系。記為I I IA A A。 【例【例【例】設(shè)】設(shè)】設(shè)A A A= = = a a a, , ,b b b ，B B B= = = 1,21,21,2 ，求，求，求A A A上的恒等關(guān)系上的恒等關(guān)系上的恒等關(guān)系I I IA A A和和和A A A到到到B B B的全域關(guān)系的全域關(guān)系的全域關(guān)系A(chǔ) A AB B B。 解：解：解：A A A上的恒等關(guān)系上的恒等關(guān)系上的恒等關(guān)系I I IA A A= = =a a a, , ,a a a , , , b b b, , ,b b b，A A A到到到B B B的全域關(guān)系的全域關(guān)系的全域關(guān)系E E E = = =A

7、A AB B B= = =a a a,1 ,1 ,1 , , , a a a,2 ,2 ,2 , , , b b b,1 ,1 ,1 , , , b b b,2 ,2 ,2 定理定理定理.14.1.1設(shè)設(shè)設(shè)A A A是具有是具有是具有n n n個元素的有限集，則個元素的有限集，則個元素的有限集，則A A A上的二元關(guān)上的二元關(guān)上的二元關(guān)系有系有系有2 2 2n n n2 2 2種。種。種。 證明證明證明：設(shè)設(shè)設(shè)A A A為具有為具有為具有n n n個元素的有限集，即個元素的有限集，即個元素的有限集，即| |A A A|= |= |=n n n，由排列組，由排列組，由排列組合原理

8、知合原理知合原理知| |A A AA A A|= |= |=n n n2 2 2。根據(jù)定理。根據(jù)定理。根據(jù)定理.23.1.2有有有| |P P P ( ( (A A AA A A) |=2) |=2) |=2| |A A AA A A| |=2 =2 =2 ，即即即A A AA A A的的的子集有子集有子集有2 2 2 個。個。個。所以具有所以具有所以具有n n n個元素的有限集個元素的有限集個元素的有限集A A A上有上有上有2 2 2 種種種二元關(guān)系。二元關(guān)系。二元關(guān)系。2n2n2n第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系例：若例：若例：若|A|=m|A|=m|A|

9、=m，|B|=n|B|=n|B|=n，問，問，問A A A到到到B B B共有多少個不同的二元關(guān)系？共有多少個不同的二元關(guān)系？共有多少個不同的二元關(guān)系？ 解：解：解： 2 2 2mm mn n n 4.1.2 4.1.2 4.1.2二元關(guān)系的表示二元關(guān)系的表示二元關(guān)系的表示 1. 1. 1.用列舉法表示二元關(guān)系用列舉法表示二元關(guān)系用列舉法表示二元關(guān)系 例例例中的中的中的A A A到到到B B B的全域關(guān)系的全域關(guān)系的全域關(guān)系 E E E= = =A A AB B B= = =a a a,1 ,1 ,1 , , , a a a,2 ,2 ,2 , , , b b b,1 ,1

10、,1 , , , b b b,2 ,2 ,2 A A A上的恒等關(guān)系上的恒等關(guān)系上的恒等關(guān)系 I I IA A A= = =a a a, , ,a a a , , , b b b, , ,b b b都都都是用列舉法表示的。是用列舉法表示的。是用列舉法表示的。 2. 2. 2.用描述法表示二元關(guān)系用描述法表示二元關(guān)系用描述法表示二元關(guān)系 設(shè)設(shè)設(shè)R R R是實(shí)數(shù)集，是實(shí)數(shù)集，是實(shí)數(shù)集，L L LR R R= = = x x x, , ,y y y | | | x x x R R Ry y y R R Rx x xy y y ， L L LR R R是是是實(shí)數(shù)集實(shí)數(shù)集實(shí)數(shù)集R R R上的二元關(guān)系。上

11、的二元關(guān)系。上的二元關(guān)系。第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 3. 3. 3.用用用矩陣矩陣矩陣表示二元關(guān)系表示二元關(guān)系表示二元關(guān)系 如果如果如果A A A，B B B是有限集，是有限集，是有限集， A A A= = = a a a1 1 1, , ,a a a2 2 2, , , , ,a a am m m ， B B B= = = b b b1 1 1, , ,b b b2 2 2, , , , ,b b bn n n ， R R R是是是A A A到到到B B B 的二元關(guān)系，的二元關(guān)系，的二元關(guān)系，R R R的關(guān)系矩陣定義為：的關(guān)系矩陣定義為：的關(guān)系矩陣定義為： MMMR

12、 R R= = = m m m n n nRRbbaarjjiiij,01 i= i= i=1, 1, 1, , ,m m m j=j=j=1, 1, 1, , ,n n n稱為二元關(guān)系稱為二元關(guān)系稱為二元關(guān)系R R R的關(guān)系矩陣。的關(guān)系矩陣。的關(guān)系矩陣。 ijr第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 【例【例【例】設(shè)設(shè)設(shè)A A A= = = a a a1 1 1, , ,a a a2 2 2, , ,a a a3 3 3, , ,a a a4 4 4 ，B B B= = = b b b1 1 1, , ,b b b2 2 2, , ,b b b3 3 3 ，R R

13、 R是是是A A A到到到B B B的二元關(guān)系，定義為：的二元關(guān)系，定義為：的二元關(guān)系，定義為：R R R= = =a a a1 1 1, , ,b b b1 1 1 , , , a a a1 1 1, , ,b b b3 3 3 , , , a a a2 2 2, , ,b b b2 2 2 , , , a a a2 2 2, , ,b b b3 3 3 , , , a a a3 3 3, , ,b b b1 1 1 , , , a a a4 4 4, , ,b b b1 1 1 , , , a a a4 4 4, , ,b b b2 2 2寫出寫出寫出R R R的關(guān)系矩陣。的關(guān)系矩陣。的關(guān)

14、系矩陣。 解：解：解：R R R的關(guān)系矩陣為：的關(guān)系矩陣為：的關(guān)系矩陣為：MMMR R R= = = 011001110101第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 【例【例【例】設(shè)】設(shè)】設(shè)A A A= = = 1,2,3,41,2,3,41,2,3,4 ，R R R是是是A A A的二元關(guān)系，定義為：的二元關(guān)系，定義為：的二元關(guān)系，定義為：R R R= = =1,11,11,1 , , , 1,21,21,2 , , , 2,12,12,1 , , , 3,23,23,2 , , , 3,13,13,1 , , , 4,34,34,3 , , , 4,24,24,

15、2 , , , 4,14,14,1寫出寫出寫出A A A上二元關(guān)系上二元關(guān)系上二元關(guān)系R R R的關(guān)系矩陣。的關(guān)系矩陣。的關(guān)系矩陣。 解：解：解：R R R的關(guān)系矩陣為：的關(guān)系矩陣為：的關(guān)系矩陣為： MMMR R R= = =0111001100010011 例例例中的中的中的二元關(guān)系二元關(guān)系二元關(guān)系R R R是是是A A A上的二元關(guān)系，只需看成上的二元關(guān)系，只需看成上的二元關(guān)系，只需看成A A A到到到A A A的二元關(guān)系，利用上述定義，就可以方便地寫出它的二元關(guān)系，利用上述定義，就可以方便地寫出它的二元關(guān)系，利用上述定義，就可以方便地寫出它的關(guān)系矩陣。的關(guān)系矩陣。的關(guān)系

16、矩陣。A A A上的二元關(guān)系和上的二元關(guān)系和上的二元關(guān)系和A A A到到到B B B的二元關(guān)系的關(guān)系的二元關(guān)系的關(guān)系的二元關(guān)系的關(guān)系矩陣的定義是相同的。矩陣的定義是相同的。矩陣的定義是相同的。第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 4. 4. 4.用用用圖圖圖表示二元關(guān)系表示二元關(guān)系表示二元關(guān)系 如果如果如果A A A和和和B B B是有限集，是有限集，是有限集，R R R是是是A A A到到到B B B二元關(guān)系，表示二元二元關(guān)系，表示二元二元關(guān)系，表示二元關(guān)系關(guān)系關(guān)系R R R的圖叫做的圖叫做的圖叫做R R R的關(guān)系圖。的關(guān)系圖。的關(guān)系圖。A A A到到到B B B二元關(guān)系的二元關(guān)

17、系的二元關(guān)系的關(guān)系圖和關(guān)系圖和關(guān)系圖和A A A上的二元關(guān)系上的二元關(guān)系上的二元關(guān)系的的的關(guān)系圖的定義是不一樣的。關(guān)系圖的定義是不一樣的。關(guān)系圖的定義是不一樣的。分別描述如分別描述如分別描述如下下下： A A A到到到B B B二元關(guān)系二元關(guān)系二元關(guān)系R R R的的的關(guān)系圖關(guān)系圖關(guān)系圖 設(shè)設(shè)設(shè)A A A= = = a a a1 1 1, , ,a a a2 2 2, , , , ,a a am m m ，B B B= = = b b b1 1 1, , ,b b b2 2 2, , , , ,b b bn n n ，R R R是是是A A A到到到B B B二元二元二元關(guān)系，關(guān)系，關(guān)系，R R

18、 R的關(guān)系圖的繪制方法如下：的關(guān)系圖的繪制方法如下：的關(guān)系圖的繪制方法如下： 畫出畫出畫出m m m個小圓圈表示個小圓圈表示個小圓圈表示A A A的元素，再畫出的元素，再畫出的元素，再畫出n n n個小圓圈個小圓圈個小圓圈表示表示表示B B B的元素。這些的元素。這些的元素。這些小圓圈叫做小圓圈叫做小圓圈叫做關(guān)系圖的結(jié)點(diǎn)關(guān)系圖的結(jié)點(diǎn)關(guān)系圖的結(jié)點(diǎn)( ( (下同下同下同) ) )。 如果如果如果 a a ai i i, , ,b b bj j j R R R，則從，則從，則從a a ai i i到到到b b bj j j畫一根有方向畫一根有方向畫一根有方向( ( (帶箭頭帶箭頭帶箭頭) ) )的線

19、。這些有方向的線。這些有方向的線。這些有方向( ( (帶箭頭帶箭頭帶箭頭) ) )的線的線的線叫做叫做叫做關(guān)系圖的邊關(guān)系圖的邊關(guān)系圖的邊( ( (下同下同下同) ) )。 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 A A A上的二元關(guān)系上的二元關(guān)系上的二元關(guān)系R R R的的的關(guān)系圖關(guān)系圖關(guān)系圖 設(shè)設(shè)設(shè)A A A= = = a a a1 1 1, , ,a a a2 2 2, , , , ,a a am m m ，R R R是是是A A A上的二上的二上的二元關(guān)系，其關(guān)系圖如元關(guān)系，其關(guān)系圖如元關(guān)系，其關(guān)系圖如下繪制：下繪制：下繪制： 畫出畫出畫出m m m個小圓圈表示個小圓圈表示個小圓

20、圈表示A A A的的的元素。元素。元素。 如果如果如果 a a ai i i, , ,a a aj j jR R R，則從，則從，則從a a ai i i到到到a a aj j j畫一根有方向畫一根有方向畫一根有方向( ( (帶箭頭帶箭頭帶箭頭) ) )的線。的線。的線。 例例例、例例例中的二元關(guān)系中的二元關(guān)系中的二元關(guān)系R R R的關(guān)系圖如下圖的關(guān)系圖如下圖的關(guān)系圖如下圖 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 4.2 4.2 4.2關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系的運(yùn)算 定義定義定義.14.2.1設(shè)設(shè)設(shè)A A A，B B B是集合，是集

21、合，是集合，R R R A A AB B B。 domdomdom R R R= = = x x x| | x x x, , ,y y yR R R 叫做叫做叫做R R R的定義域。的定義域。的定義域。 ran ran ran R R R= = = y y y| | | x x x, , ,y y yR R R 叫做叫做叫做R R R的值域。的值域。的值域。 FLD FLD FLD R R R= dom= dom= dom R R Rran ran ran R R R叫做叫做叫做R R R的域。的域。的域。 .14.2.1二元關(guān)系的交、并、補(bǔ)、對稱差運(yùn)算二元關(guān)系的交、并、補(bǔ)、對

22、稱差運(yùn)算二元關(guān)系的交、并、補(bǔ)、對稱差運(yùn)算 定理定理定理.14.2.1設(shè)設(shè)設(shè)R R R，S S S是是是X X X到到到Y(jié) Y Y的二元關(guān)系，則的二元關(guān)系，則的二元關(guān)系，則R R RS S S，R R R S S S，R R R- - -S S S， R R R，R SR SR S也是也是也是X X X到到到Y(jié) Y Y的二元關(guān)系的二元關(guān)系的二元關(guān)系。 證明證明證明：因?yàn)橐驗(yàn)橐驗(yàn)镽 R R，S S S是是是X X X到到到Y(jié) Y Y的二元關(guān)系，所以，的二元關(guān)系，所以，的二元關(guān)系，所以， R R R X X XY Y Y且且且S S S X X XY Y Y。顯然，。顯然，。顯然，

23、R R RS S S X X XY Y Y，即，即，即R R RS S S是是是X X X到到到Y(jié) Y Y的二元關(guān)系。的二元關(guān)系。的二元關(guān)系。 R R RS S S X X XY Y Y，即，即，即R R RS S S是是是X X X到到到Y(jié) Y Y的二元關(guān)系。的二元關(guān)系。的二元關(guān)系。 R R R- - -S S S X X XY Y Y，即，即，即R R R- - -S S S是是是X X X到到到Y(jié) Y Y的二元關(guān)系。的二元關(guān)系。的二元關(guān)系。第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 在二元關(guān)系運(yùn)算中，認(rèn)為全域關(guān)系是全集。所以在二元關(guān)系運(yùn)算中，認(rèn)為全域關(guān)系是全集。所以在二元關(guān)系運(yùn)算中

24、，認(rèn)為全域關(guān)系是全集。所以 R R R= = = X X XY Y Y- - -R R R X X XY Y Y，即，即，即 R R R是是是X X X到到到Y(jié) Y Y的二元關(guān)系。的二元關(guān)系。的二元關(guān)系。 由以上結(jié)論可以得到：由以上結(jié)論可以得到：由以上結(jié)論可以得到： ( ( (R R RS S S) ) ) X X XY Y Y和和和( ( (S S SR R R) ) ) X X XY Y Y，從而，從而，從而 ( ( (R R RS S S) ) )( ( (S S SR R R) ) ) X X XY Y Y，所以，所以，所以 R SR SR S=(=(=(R R RS S S) ) )

25、( ( (S S SR R R) ) ) X X XY Y Y，即，即，即R SR SR S是是是X X X到到到Y(jié) Y Y的二元關(guān)的二元關(guān)的二元關(guān)系。系。系。 【例【例【例】設(shè)設(shè)設(shè)X X X= = = 1,2,3,41,2,3,41,2,3,4 ，X X X上的二元關(guān)系上的二元關(guān)系上的二元關(guān)系H H H和和和S S S定義如定義如定義如下：下：下： H H H= = =x x x, , ,y y y | | | 是整數(shù)是整數(shù)是整數(shù) S S S= = =x x x, , ,y y y | | | 是正整數(shù)是正整數(shù)是正整數(shù) 試求試求試求H H HS S S，H H HS S S

26、， H H H，S S S- - -H H H2yx 3yx 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 解：解：解：將將將H H H和和和S S S用列舉法表示：用列舉法表示：用列舉法表示： H H H= = =1,11,11,1 , , , 1,31,31,3 , , , 2,22,22,2 , , , 2,42,42,4 , , , 3,33,33,3 , , , 3,13,13,1 , , , 4,44,44,4 , , , 4,24,24,2 S S S= = =4,14,14,1 H H HS S S= = =1,11,11,1 , , , 1,31,31,3 , , , 2

27、,22,22,2 , , , 2,42,42,4 , , , 3,33,33,3 , , , 3,13,13,1 , , , 4,44,44,4 , , , 4,24,24,2 , , , 4,14,14,1 H H HS S S= = = H H H= = =X X X2 2 2- - - H H H= = =1,21,21,2 , , , 1,41,41,4 , , , 2,12,12,1 , , , 2,32,32,3 , , , 3,23,23,2 , , , 3,43,43,4 , , , 4,34,34,3 , , , 4,14,14,1 S S SH H H= = =4,14,1

28、4,1 .24.2.2二元關(guān)系的復(fù)合運(yùn)算二元關(guān)系的復(fù)合運(yùn)算二元關(guān)系的復(fù)合運(yùn)算二元關(guān)系的復(fù)合運(yùn)算二元關(guān)系的復(fù)合運(yùn)算二元關(guān)系的復(fù)合運(yùn)算 定義定義定義.24.2.2 設(shè)設(shè)設(shè)X X X，Y Y Y，Z Z Z是集合，是集合，是集合，R R R X X XY Y Y，S S S Y Y YZ Z Z，集，集，集合合合 x x x, , ,z z zx x x X X Xz z z Z Z Z( ( ( y y y)( )( )(y y y Y Y Y x x x, , ,y y yR R R y y y, , ,z z zS S S) ) ) 叫做叫做叫做R R R和和和

29、S S S的復(fù)合關(guān)系。記為的復(fù)合關(guān)系。記為的復(fù)合關(guān)系。記為R R R S S S，R R R S S S X X XZ Z Z，即，即，即R R R S S S是是是X X X到到到Z Z Z的二元關(guān)系。的二元關(guān)系。的二元關(guān)系。 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 【例【例【例】X X X= = = 1,2,3,4,51,2,3,4,51,2,3,4,5 ，X X X上的二元關(guān)系上的二元關(guān)系上的二元關(guān)系R R R和和和S S S定義如下：定義如下：定義如下： R R R= = =1,21,21,2 , , , 3,43,43,4 , , , 2,22,22,2

30、S S S= = =4,24,24,2 , , , 2,52,52,5 , , , 3,13,13,1 , , , 1,31,31,3試求試求試求R R R S S S，S S S R R R，R R R ( ( (S S S R R R) ) )，( ( (R R R S S S) ) ) R R R，R R R R R R，S S S S S S，R R R R R R R R R 解：解：解：R R R S S S= = =1,51,51,5 , , , 3,23,23,2 , , , 2,52,52,5 S S S R R R= = =4,24,24,2 , , , 3,23,23,2

31、 , , , 1,41,41,4 ( ( (R R R S S S) ) ) R R R= = =3,23,23,2 R R R ( ( (S S S R R R)=)=)=3,23,23,2 R R R R R R= = =1,21,21,2 , , , 2,22,22,2 S S S S S S= = =4,54,54,5 , , , 3,33,33,3 , , , 1,11,11,1 R R R R R R R R R = = =1,21,21,2 , , , 2,22,22,2 從從從例例例可以看出可以看出可以看出，R R R S S SS S S R R R，這說明

32、，二元關(guān)系，這說明，二元關(guān)系，這說明，二元關(guān)系的復(fù)合運(yùn)算不滿足交換律。的復(fù)合運(yùn)算不滿足交換律。的復(fù)合運(yùn)算不滿足交換律。 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 定理定理定理.24.2.2 設(shè)設(shè)設(shè)X X X，Y Y Y，Z Z Z，WWW是集合，是集合，是集合，R R R X X XY Y Y，S S S Y Y YZ Z Z，T T T Z Z ZWWW，則，則，則 ( ( (R R R S S S) ) ) T T T= = = R R R ( ( (S S S T T T) ) ) 證明：證明：證明： x x x, , ,w w w( ( (R R R S S S

33、) ) ) T T T( ( ( z z z)( )( )( x x x, , ,z z zR R R S S S z z z, , ,w w wT T T) ) ) ( ( ( z z z)()()( y y y)( )( )( x x x, , ,y y yR R R y y y, , ,z z zS S S) ) ) z z z, , ,w w wT T T) ) ) ( ( ( z z z)( )( )( y y y)()()( x x x, , ,y y yR R R y y y, , ,z z zS S S) ) ) z z z, , ,w w wT T T) ) ) ( ( (

34、y y y)( )( )( z z z)( )( )( x x x, , ,y y yR R R( ( ( y y y, , ,z z zS S S z z z, , ,w w wT T T) ) ) ( ( ( y y y)( )( )( x x x, , ,y y yR R R( ( ( z z z)( )( )( y y y, , ,z z zS S S z z z, , ,w w wT T T) ) ) ( ( ( y y y)( )( )( x x x, , ,y y yR R R y y y, , ,w w wS S S T T T) ) )x x x, , ,w w wR R R

35、 ( ( (S S S T T T) ) )所以所以所以 ( ( (R R R S S S) ) ) T T T= = =R R R ( ( (S S S T T T) ) )( ( ( y y y)( )( )( x x x, , ,y y yR R R y y y, , ,z z zS S S) ) )( ( ( y y y) ) )( ( ( y y y)( )( )( z z z) ) )( ( ( y y y, , ,z z zS S S z z z, , ,w w wT T T) ) )( ( ( z z z) ) ) y y y, , ,w w wS S S T T T第第第4

36、4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 定理定理定理.34.2.3 設(shè)設(shè)設(shè)R R R是是是A A A上的二元關(guān)系，上的二元關(guān)系，上的二元關(guān)系，R R R I I IA A A= = =I I IA A A R R R= = =R R R 證明證明證明：先證先證先證R R R I I IA A A= = =R R R x x x, , ,y y yR R R I I IA A A( ( ( z z z)( )( )( x x x, , ,z z zR R R z z z, , ,y y yI I IA A A) ) ) ( ( ( z z z)( )( )( x x x, , ,

37、z z zR R Rz z z= = =y y y) ) )x x x, , ,y y yR R R所以所以所以 R R R I I IA A A R R R x x x, , ,y y yR R Rx x x, , ,y y yR R R y y y, , ,y y yI I IA A Ax x x, , ,y y yR R R I I IA A A所以所以所以 R R R R R R I I IA A A 故故故 R R R I I IA A A= = =R R R 類似的，可以證明類似的，可以證明類似的，可以證明I I IA A A R R R= = = R R R 第第第4 4 4章章

38、章 二元關(guān)系二元關(guān)系二元關(guān)系 定理定理定理.44.2.4 設(shè)設(shè)設(shè)R R R，S S S，T T T是是是A A A上的二元關(guān)系上的二元關(guān)系上的二元關(guān)系, , , 則則則 R R R ( ( (S S ST T T)=)=)=R R R S S SR R R T T T ( ( (R R RS S S) ) ) T T T= = =R R R T T TS S S T T T R R R ( ( (S S ST T T) ) ) R R R S S SR R R T T T ( ( (R R RS S S) ) ) T T T R R R T T TS S S T T T 證明證

39、明證明：僅證明僅證明僅證明，類似地可證明，類似地可證明，類似地可證明、和和和。 x x x, , ,y y yR R R ( ( (S S ST T T) ) )( ( ( z z z)( )( )( x x x, , ,z z zR R R z z z, , ,y y yS S ST T T) ) ) ( ( ( z z z)( )( )( x x x, , ,z z zR R R( ( ( z z z, , ,y y yS S S z z z, , ,y y yT T T) ) ) ( ( ( z z z)()()( x x x, , ,z z zR R R z z z, , ,y y y

40、S S S) ) )( ( ( x x x, , ,z z zR R R z z z, , ,y y yT T T) ) ) ( ( ( z z z)( )( )( x x x, , ,z z zR R R z z z, , ,y y yS S S) ) )( ( ( z z z)( )( )( x x x, , ,z z zR R R z z z, , ,y y yT T T) ) ) x x x, , ,y y yR R R S S S x x x, , ,y y yR R R T T T x x x, , ,y y yR R R S S SR R R T T T故故故 R R R ( (

41、 (S S ST T T) ) ) R R R S S SR R R T T T第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 一般地說，一般地說，一般地說，R R R S S SR R R T T T R R R ( ( (S S ST T T) ) )，舉反例如下：，舉反例如下：，舉反例如下： 設(shè)設(shè)設(shè)A=A=A= 1,2,3,4,51,2,3,4,51,2,3,4,5 R R R= = =4,14,14,1 , , , 4,24,24,2A A AA A A S S S= = =1,51,51,5 , , , 3,53,53,5A A AA A A T T T= = =2, 2, 2,5

42、 5 5 , , , 3,53,53,5A A AA A A R R R S S SR R R T T T = = =4,54,54,54,54,54,5 = = =4,54,54,5 R R R ( ( (S S ST T T) =) =) =4,14,14,1 , , , 4,24,24,2 3,53,53,5= = = R R R S S SR R R T T T R R R ( ( (S S ST T T) ) ) 定理定理定理.44.2.4的的的說明，關(guān)系的復(fù)合運(yùn)算說明，關(guān)系的復(fù)合運(yùn)算說明，關(guān)系的復(fù)合運(yùn)算“ ” ” ”對并運(yùn)算對并運(yùn)算對并運(yùn)算“” ” ”滿足左分配律。

43、滿足左分配律。滿足左分配律。說明，關(guān)系的復(fù)合運(yùn)算說明，關(guān)系的復(fù)合運(yùn)算說明，關(guān)系的復(fù)合運(yùn)算“ ” ” ”對對對并運(yùn)算并運(yùn)算并運(yùn)算“” ” ”滿足右分配律。所以，復(fù)合運(yùn)算滿足右分配律。所以，復(fù)合運(yùn)算滿足右分配律。所以，復(fù)合運(yùn)算“ ” ” ”對并對并對并運(yùn)算運(yùn)算運(yùn)算“” ” ”滿足分配律。由滿足分配律。由滿足分配律。由和和和知，復(fù)合運(yùn)算知，復(fù)合運(yùn)算知，復(fù)合運(yùn)算“ ” ” ”對對對交運(yùn)算交運(yùn)算交運(yùn)算“” ” ”不滿足分配律。不滿足分配律。不滿足分配律。 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系例：A=a, b B=1, 2 C=x, y R=a,1,a,2AB S=1,x,2,yBC T=1,

44、yBC求： R SR T R (ST) 解：解：解： R R R S S SR R R T T T = = =a a a, , ,x x x , , , a a a, , ,y y y a,ya,ya,y = = =a,ya,ya,y R R R ( ( (S S ST T T) =) =) =a,1a,1a,1 , , , a,2a,2a,2 = = =第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 定義定義定義4.2.3 4.2.3 4.2.3 設(shè)設(shè)設(shè)R R R是是是A A A上的二元關(guān)系，上的二元關(guān)系，上的二元關(guān)系，n n n為自然數(shù)，為自然數(shù)，為自然數(shù)，R R R的的的n n n次冪

45、次冪次冪記為記為記為R R Rn n n，定義為：，定義為：，定義為： R R R0 0 0= = =I I IA A A R R Rn n n+1+1+1= = = R R Rn n n R R R 由定義由定義由定義.34.2.3可以看出，可以看出，可以看出，A A A上的任何二元關(guān)系的上的任何二元關(guān)系的上的任何二元關(guān)系的0 0 0次冪都相次冪都相次冪都相等，等于等，等于等，等于A A A上的恒等關(guān)系上的恒等關(guān)系上的恒等關(guān)系I I IA A A。由定義。由定義。由定義.34.2.3還可以看出：還可以看出：還可以看出： R R R1 1 1= = = R R

46、R0 0 0 R R R= = =I I IA A A R R R= = =R R R R R R2 2 2= = = R R R1 1 1 R R R= = = R R R R R R R R R3 3 3= = = R R R2 2 2 R R R=(=(=(R R R R R R) ) ) R R R 因?yàn)閺?fù)合運(yùn)算滿足結(jié)合律，所以因?yàn)閺?fù)合運(yùn)算滿足結(jié)合律，所以因?yàn)閺?fù)合運(yùn)算滿足結(jié)合律，所以R R R3 3 3又可以寫成：又可以寫成：又可以寫成： R R R3 3 3= = = R R R R R R R R R 同樣的道理同樣的道理同樣的道理R R Rn n n也可以寫成：也可以寫成：也可以

47、寫成： R R Rn n n= = =R R R R R R R R R 第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 例如例如例如, , ,在在在例例例中中中 R R R2 2 2= = =R R R R R R= = =1,21,21,2 , , , 2,22,22,2 S S S2 2 2 = = =S S S S S S= = =4,54,54,5 , , , 3,33,33,3 , , , 1,11,11,1 R R R3 3 3= = =R R R R R R R R R= = =1,21,21,2 , , , 2,22,22,2 定理定理定理

48、.54.2.5設(shè)設(shè)設(shè)A A A是具有是具有是具有n n n個元素的有限集，個元素的有限集，個元素的有限集，R R R是是是A A A上的二元上的二元上的二元關(guān)系，則必存在自然數(shù)關(guān)系，則必存在自然數(shù)關(guān)系，則必存在自然數(shù)s s s和和和t t t，使得，使得，使得R R Rs s s= = =R R Rt t t，0 0 0s s st t t2 2 2 。 證明：證明：證明：R R R是是是A A A上的二元關(guān)系，對任何自然數(shù)上的二元關(guān)系，對任何自然數(shù)上的二元關(guān)系，對任何自然數(shù)k k k，由復(fù)合關(guān)，由復(fù)合關(guān)，由復(fù)合關(guān)系的定義知，系的定義知，系的定義知，R R Rk k k仍然是仍然是仍然是A A

49、 A上的二元關(guān)系，即上的二元關(guān)系，即上的二元關(guān)系，即R R Rk k k A A AA A A。另一。另一。另一方面，根據(jù)定理方面，根據(jù)定理方面，根據(jù)定理.14.1.1， A A A上的二元關(guān)系僅有上的二元關(guān)系僅有上的二元關(guān)系僅有2 2 2 種。列出種。列出種。列出R R R的的的各次冪各次冪各次冪R R R0 0 0，R R R1 1 1，R R R2 2 2 ， ，共有，共有，共有2 2 2 1 1 1個，必存在自然數(shù)個，必存在自然數(shù)個，必存在自然數(shù)s s s和和和t t t，使得，使得，使得R R Rs s s= = =R R Rt t t，0 0 0s s st t t

50、2 2 2 。2n2n2n22nR2n第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系【例【例【例】A A A= = = 1,2,3,4 1,2,3,4 1,2,3,4 ，A A A上的二元關(guān)系上的二元關(guān)系上的二元關(guān)系R R R定義如下：定義如下：定義如下： R R R= = =1,21,21,2 , , , 2,12,12,1 , , , 2,32,32,3 , , , 3,43,43,4求二元關(guān)系求二元關(guān)系求二元關(guān)系R R R的各次冪，驗(yàn)證的各次冪，驗(yàn)證的各次冪，驗(yàn)證定理定理定理.54.2.5。 解：解：解：| |A|=A|=A|=4 4 4 R R R0

51、 0 0= = =I I IA A A= = =1,11,11,1 , , , 2,22,22,2 , , , 3,33,33,3 , , , 4,44,44,4 R R R1 1 1= = =R R R= = =1,21,21,2 , , , 2,12,12,1 , , , 2,32,32,3 , , , 3,43,43,4 R R R2 2 2= = =R R R1 1 1 R R R= = = R R R R R R= = =1,11,11,1 , , , 1,31,31,3 , , , 2,22,22,2 , , , 2,42,42,4 R R R3 3 3= = = R R R2 2

52、 2 R R R = = =1,21,21,2 , , , 2,12,12,1 , , , 2,32,32,3 , , , 1,41,41,4 R R R4 4 4= = =R R R3 3 3 R R R= = =1,11,11,1 , , , 1,31,31,3 , , , 2,22,22,2 , , , 2,42,42,4= = =R R R2 2 2， 0 0 02 2 24 4 42 2 2161616=2=2=2 R R R5 5 5= = =R R R4 4 4 R R R= = =R R R2 2 2 R R R= = =R R R3 3 3 R R R6 6 6= = =R

53、R R5 5 5 R R R= = =R R R3 3 3 R R R= = =R R R4 4 4= = = R R R2 2 2 R R R2 2 2n n n= = =R R R2 2 2 R R R2 2 2n n n+1+1+1= = =R R R3 3 3, , , n n n =1,2,3,=1,2,3,=1,2,3,第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 定理定理定理.64.2.6設(shè)設(shè)設(shè)R R R是是是A A A上的二元關(guān)系，上的二元關(guān)系，上的二元關(guān)系，m m m，n n n為自然數(shù)，則為自然數(shù)，則為自然數(shù)，則 R R Rm m m R R Rn n

54、n = = =R R Rm m m+ + +n n n ( ( (R R Rm m m) ) )n n n= = =R R Rmnmnmn 證明：證明：證明：對任意給定的對任意給定的對任意給定的m m m N N N，關(guān)于，關(guān)于，關(guān)于n n n進(jìn)行歸納證明：進(jìn)行歸納證明：進(jìn)行歸納證明： 當(dāng)當(dāng)當(dāng)n n n=0=0=0時，時，時，R R Rm m m R R R0 0 0= = =R R Rm m m I I IA A A= = =R R Rm m m= = =R R Rm m m+0+0+0 設(shè)設(shè)設(shè)n n n= = =k k k時，時，時，R R Rm m m R R Rk k k= = =R

55、R Rm m m+ + +k k k。下證。下證。下證n n n= = =k k k+1+1+1時，結(jié)果也對。時，結(jié)果也對。時，結(jié)果也對。 R R Rm m m R R Rk k k+1+1+1= = =R R Rm m m ( ( (R R Rk k k R R R)=()=()=(R R Rm m m R R Rk k k) ) ) R R R= = =R R Rm m m+ + +k k k R R R= = = R R Rm m m+ + +k k k+1+1+1 對任意給定的對任意給定的對任意給定的m m m N N N，關(guān)于，關(guān)于，關(guān)于n n n進(jìn)行歸納證明：進(jìn)行歸納證明：進(jìn)行歸納

56、證明： 當(dāng)當(dāng)當(dāng)n n n=0=0=0時，時，時，( ( (R R Rm m m) ) )0 0 0= = =I I IA A A= = =R R R0 0 0= = =R R Rm m m 0 0 0 設(shè)設(shè)設(shè)n n n= = =k k k時，時，時，( ( (R R Rm m m) ) )k k k= = =R R Rmkmkmk。下證。下證。下證n n n= = =k k k+1+1+1時，結(jié)果也對。時，結(jié)果也對。時，結(jié)果也對。 ( ( (R R Rm m m) ) )k k k+1+1+1=(=(=(R R Rm m m) ) )k k k R R Rm m m= = =R R Rmkmk

57、mk R R Rm m m= = =R R Rmkmkmk+ + +m m m= = =R R Rm m m( ( (k k k+1)+1)+1) 設(shè)設(shè)設(shè)X X X，Y Y Y，Z Z Z是集合，是集合，是集合，R R R X X XY Y Y，S S S Y Y YZ Z Z，R R R S S S是是是R R R和和和S S S的復(fù)的復(fù)的復(fù) 合關(guān)系，合關(guān)系，合關(guān)系，R R R S S S X X XZ Z Z，它們的關(guān)系矩陣分別是，它們的關(guān)系矩陣分別是，它們的關(guān)系矩陣分別是MMMR R R、MMMS S S和和和MMMR R R S S S。以下研究這三個矩陣之間的關(guān)系。以下研究這三個矩陣

58、之間的關(guān)系。以下研究這三個矩陣之間的關(guān)系。第第第4 4 4章章章 二元關(guān)系二元關(guān)系二元關(guān)系 設(shè)設(shè)設(shè)X X X= = = x x x1 1 1, , ,x x x2 2 2, , , , , ,x x xm m m ，Y Y Y= = = y y y1 1 1, , ,y y y2 2 2, , , , , ,y y yn n n ， Z Z Z= = = z z z1 1 1, , ,z z z2 2 2, , , , , ,z z zP P P R R R X X XY Y Y， S S S Y Y YZ Z Z， R R R S S S X X XZ Z Z MMMR R R= = = m

59、 m m n n n i i i=1, =1, =1, , , ,m m m，j j j=1, =1, =1, , , ,n n n M M MS S S= = = n n n p p p i i i=1,=1,=1, , ,n n n，j j j =1,=1,=1, , , p p p M M MR R R S S S= = = m m m p p p i i i=1,=1,=1, , ,m m m，j j j =1,=1,=1, , , p p p ijuRRyyxxujjiiij,01 ijvSSzzyyvjjiiij,01ijwSSRRzzxxwjjiiij,01第第第4 4 4章章章

60、 二元關(guān)系二元關(guān)系二元關(guān)系 與與與 ， 有如下的關(guān)系：有如下的關(guān)系：有如下的關(guān)系： = = = i i i=1,=1,=1, , ,m m m，j j j=1,=1,=1, , ,p p p 將上述關(guān)系用矩陣符號記為：將上述關(guān)系用矩陣符號記為：將上述關(guān)系用矩陣符號記為： MMMR R R S S S= = =MMMR R R MMMS S S， 其中，其中，其中，i i i=1,=1,=1, , ,m m m，j j j =1,=1,=1, , ,p p p 矩陣運(yùn)算矩陣運(yùn)算矩陣運(yùn)算“ ” ” ”叫做關(guān)系矩陣叫做關(guān)系矩陣叫做關(guān)系矩陣MMMR R R和和和MMMS S S的布爾乘法。的布爾乘法。