關(guān)系21(運算)

1、1 二元關(guān)系的運算二元關(guān)系的運算與關(guān)系閉包與關(guān)系閉包 二元關(guān)系是集合，集合二元關(guān)系是集合，集合存在并，交，差，非和對存在并，交，差，非和對稱差的運算。稱差的運算。 故二元關(guān)系也存在這樣故二元關(guān)系也存在這樣的運算。的運算。 還有還有復(fù)合運算和逆運算復(fù)合運算和逆運算2設(shè)設(shè)1 1和和2 2是到的二元關(guān)系，則是到的二元關(guān)系，則（1）12 2（，）（，）（，）（，） 1 1或或 （，）（，）2 2（2 2）1 12 2（，）（，）（，）（，） 1 1 且且 （，）（，）2 2（3 3）1 1- -2 2（，）（，）（，）（，） 1 1 但但 （，）（，） 2 23n (4)n（5）1 2 （，）（，）（

2、，）（，）12 但但（，）（，） 1211RBAR11RBAR4例：，例：， 為整數(shù)集為整數(shù)集 （，），2ba （，），3ba , ab求：，R，5解：與都是上的二元關(guān)系解：與都是上的二元關(guān)系 （，），（，），（，），（，）， （，），（，），（，），（，），（，），（，），（，），（，），（，）（，），（，），（，）（，）（，）（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，）（，）nR 6R （，） ， （，） ， （，） ， （，） ，（，） ， （，） ， （，） ， （，） ，7關(guān)系矩陣可表示二元關(guān)系

3、，故可用矩陣的關(guān)系矩陣可表示二元關(guān)系，故可用矩陣的邏輯運算來研究二元關(guān)系的運算。邏輯運算來研究二元關(guān)系的運算。設(shè)設(shè): : 1 1，2 2，n n 1 1，2 2，m m 1（ij），），2（ij） 則：12（cijij）12（ijij）12（ijijd）1R（ijC）8其中其中: :邏輯加邏輯加()()：， ，邏輯乘邏輯乘()()：， ， ， 邏輯非（） ：0，19對上例： 1010010110100101， 0001000000000000則用矩陣的邏輯運算:1011010110100101=SR10 0000000000000000， 0101101001011010R，11對任意二元關(guān)系

4、對任意二元關(guān)系R，G， 可以定義可以定義:n逆逆(inverse) : RC = | yRx n合成合成(復(fù)合復(fù)合)(composite):RG = | z( xRz zGy ) xzyGF12關(guān)于合成n順序合成順序合成(右合成右合成):RG = | z( xRz zGy ) n逆序合成逆序合成(左合成左合成):RG = | z( xGz zRy ) 13二元關(guān)系的復(fù)合（具體）二元關(guān)系的復(fù)合（具體）定義：定義： 設(shè)設(shè)1 1為到的二元關(guān)系，為到的二元關(guān)系，2 2為為 到的二元關(guān)系，到的二元關(guān)系，3 3（，）（，）（，）（，）1 1， 且且 （，）（，）2 2 記記 3 31 12 2 則則12是

5、由到的二元關(guān)系，是由到的二元關(guān)系， 稱為稱為1，2的復(fù)合關(guān)系的復(fù)合關(guān)系14例例2： 是父子關(guān)系，則是父子關(guān)系，則是祖孫關(guān)系。是祖孫關(guān)系。例：4321aaaa李蘭，陳平，王兵，張華是學(xué)生集合4321bbbb遙感，自動化，硬件，軟件是專業(yè)集合C4321cccc離散數(shù)學(xué)，操作系統(tǒng)，電子線路，工程制圖 是課程集合15則：則：1 1（1 1，1 1），（），（1 1，3 3），）， （2 2，2 2），（），（2 2，4 4），）， （3 3，3 3），（），（3 3，4 4）, , （4 4，1 1），（），（4 4，4 4） 是選雙學(xué)位專業(yè)的二元關(guān)系。是選雙學(xué)位專業(yè)的二元關(guān)系。2 2（1 1，3 3

6、），（），（1 1，4 4），），（2 2，2 2），（），（2 2，3 3），（），（2 2，4 4），），（3 3，1 1），（），（3 3，2 2），（），（4 4，2 2），），（4 4，4 4） 是各專業(yè)本學(xué)期必修課的二元關(guān)系。是各專業(yè)本學(xué)期必修課的二元關(guān)系。163 31 12 2（1 1，1 1），（），（1 1，2 2），）， （1 1，3 3），（），（1 1，4 4），（），（2 2，2 2），）， （2 2，3 3），（），（2 2，4 4），（），（3 3，1 1），）， （3 3，2 2），（），（3 3，4 4），（），（4 4，2 2），）， （4 4，3 3），（

7、），（4 4，4 4） 是選雙學(xué)位學(xué)生本學(xué)期必修課的二元關(guān)系是選雙學(xué)位學(xué)生本學(xué)期必修課的二元關(guān)系17 )(ijanm， )(jkbLn， 則則：)(ikcLm ikjkijnjbaV1普通的矩陣乘法：普通的矩陣乘法：而二元關(guān)系的復(fù)合的矩陣布爾型乘法：而二元關(guān)系的復(fù)合的矩陣布爾型乘法：而 iknjjkijba118對 例 3， 有 ： 11001110010100101,2=1010001111101100 3 1 21110101111101111 在行處標上姓名，列處標上課程，就知在行處標上姓名，列處標上課程，就知誰該必修哪些課了。誰該必修哪些課了。19若是上二元關(guān)系，若是上二元關(guān)系， 若設(shè)

8、若設(shè): : 1 1(1)(1)2 22 2（，）（，） （，），（，）（，），（，）(2)(2)設(shè)設(shè)n nn n已定義，則已定義，則 n+1n+1n nn nn+1n+1 = （，）（，），）（，）， （，）（，） 20關(guān)系的n次冪n關(guān)系的關(guān)系的n次冪次冪(nth power): 設(shè)設(shè)R A A, n N, 則則 (1) R0 = I IA; (2) Rn+1 = RnR, (n 1).n Rn表示的關(guān)系表示的關(guān)系, 是是R的關(guān)系圖中長度為的關(guān)系圖中長度為n的有向路徑的起點與終點的關(guān)系的有向路徑的起點與終點的關(guān)系.RnnRRRR個12nn-121 R0,R1,R2,R3,是否互不相等?R0R1

9、R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47=R6=R20=R34=R48=R7=R21=R35=R49=R8=R22=R36 =R15R9R10R11R14R16R1722n定理定理1: 設(shè)設(shè) R A A, m,n N, 則則 (1) RmRn = Rm+n ; (2) (Rm)n = Rmn.n定理定理2: 設(shè)設(shè) |A|=n, R A A, 則則 s,t N, 并并且且 使得使得 Rs = Rt. 23例：（，），（，），例：（，），（，）， （，），（，），（，），（，）， （，），（，）（，），（，） 是有限集，上的二元是有限集，上的二元關(guān)系。關(guān)系。的關(guān)

10、系圖：的關(guān)系圖：242 2（，），（，），（，），（，），（，），（，）， （，），（，），（，），（，），（，），（，）， ( (，），（，），（，），），（，），（，） 25 2 2的關(guān)系圖中不存在的關(guān)系圖中不存在（，），（，）， （，），故（，），故 2n n的關(guān)系圖的構(gòu)造：的關(guān)系圖的構(gòu)造： 可由的關(guān)系圖來構(gòu)造，從的每個結(jié)點可由的關(guān)系圖來構(gòu)造，從的每個結(jié)點a ai i出發(fā)，數(shù)出發(fā)，數(shù)n n條邊。凡通過數(shù)條邊。凡通過數(shù)n n條邊能到達的結(jié)條邊能到達的結(jié)點點a aj j，則有（則有（a ai i，a aj j）n n。關(guān)系圖中從關(guān)系圖中從i i出出發(fā)到發(fā)到j(luò) j的邊是存在的。的邊是存在的。

11、這樣處理容易出錯，用相關(guān)矩陣的布爾型這樣處理容易出錯，用相關(guān)矩陣的布爾型乘法來做，簡單，又不容易錯，還適宜于計算乘法來做，簡單，又不容易錯，還適宜于計算機處理。機處理。2621011110100001101010010110000100101001011000010010100101100001001R27n把逆關(guān)系也看成是一種運算，那么與其他一些運算把逆關(guān)系也看成是一種運算，那么與其他一些運算的組合可以有一些結(jié)論。設(shè)，是到的二元的組合可以有一些結(jié)論。設(shè)，是到的二元關(guān)系，是到的二元關(guān)系，是到的二元關(guān)系，是到的二元關(guān)系，是到的二元關(guān)系關(guān)系n1）（）（）cccn2）（）（）cccn3）n4）（）（

12、）CCCn5）（）（）C二元關(guān)系的運算RBAR286）（）（）CCC 7） (8) （） （） (9) （） 但： 且（） (10)CC29 1、函數(shù)復(fù)合運算應(yīng)用到二元關(guān)系中、函數(shù)復(fù)合運算應(yīng)用到二元關(guān)系中 2、求滿足給定性質(zhì)的二元關(guān)系、求滿足給定性質(zhì)的二元關(guān)系 -原有二元關(guān)系的擴充原有二元關(guān)系的擴充 3、從二元關(guān)系到多元關(guān)系、從二元關(guān)系到多元關(guān)系進一步的思考30關(guān)系的閉包n自反閉包自反閉包r( R )n對稱閉包對稱閉包s( R )n傳遞閉包傳遞閉包t( R )n閉包的閉包的性質(zhì)性質(zhì), 求法求法, 相互關(guān)系相互關(guān)系31什么是閉包n閉包閉包(closure): 包含一些給定對象包含一些給定對象,

13、具有具有指定性質(zhì)的最小集合指定性質(zhì)的最小集合n“最小最小”: 任何包含同樣對象任何包含同樣對象, 具有同樣具有同樣性質(zhì)的集合性質(zhì)的集合, 都包含這個閉包集合都包含這個閉包集合n例例: (平面上平面上點點的凸包凸包)32自反閉包(reflexive closure)n自反閉包自反閉包: 包含給定關(guān)系包含給定關(guān)系R的最小自反關(guān)的最小自反關(guān)系系, 稱為稱為R的自反閉包的自反閉包, 記作記作r( R ). (1) R r( R ); (2) r( R )是自反的是自反的; (3) S( (R S S自反自反) t( R ) S ).G( R )G(t( R )33對稱閉包(symmetric closure)n對稱閉包對稱閉包: 包含給定關(guān)系包含給定關(guān)系R的最小的最小對稱對稱關(guān)關(guān)系系, 稱為稱為R的的對稱對稱閉包閉包, 記作記作s( R ). (1) R s( R ); (2) s( R )是對稱的是對稱的; (3) S(