離散數(shù)學(xué) 2-3(關(guān)系的運算)2014-10-8課件

1、主講教師：常亮E-mail: QQ：737059669辦公室電話: 2291071 手機:導(dǎo)教師：周小川答疑時間：星期四 上午 10:20-11:50答疑地點：5教5樓 軟件工程教研室離散數(shù)學(xué)2.3 關(guān)系的運算基本運算交、并、補、差、對稱差運算復(fù)合運算逆運算冪運算閉包運算復(fù)合運算的矩陣實現(xiàn)令A(yù)、B、C為有限集合，R是A到B的關(guān)系，S是B到C的關(guān)系，MR和MS分別為R和S的關(guān)系矩陣。則，RS的關(guān)系矩陣為MRS = MRMS 。關(guān)系矩陣乘法:按照傳統(tǒng)矩陣乘法進行運算，得到初步結(jié)果；將大于等于1的地方修改為1。復(fù)合運算的性質(zhì)定理2.3給定任意集合A、B、C和D，設(shè)R、S和T

2、分別是集合A到B、B到C和C到D的關(guān)系，那么(RS)T = R(ST)。 復(fù)合運算滿足結(jié)合律！復(fù)合運算的性質(zhì)定理2.4對于任意集合A、B、C和D，設(shè)R, S1, S2和T分別是A到B, B到C, B到C和C到D的關(guān)系。那么 ： R(S1 S2) = (RS1) (RS2) R(S1 S2) (RS1) (RS2) (S1S2)T = (S1T) ( S2T) (S1S2)T (S1T) ( S2T)復(fù)合對并運算滿足分配律！復(fù)合對交運算不滿足分配律！例2.34設(shè)R = , , , , ， S = , , , , 計算R-1、S-1、(R-1)-1、(S-1)-1、(RS) -1和S-1R-1；解

3、 根據(jù)逆運算和復(fù)合運算的定義，有R-1 = , , , , S-1 = , , , , (R-1)-1 = , , , , (S-1)-1 = , , , , RS = , , , , , (RS) -1= , , , , , S-1R-1 = , , , , , 逆運算的性質(zhì)定理2.5對于任意集合A和B，設(shè)R是集合A到B的關(guān)系，則有： (R-1)-1 = R。 逆運算的性質(zhì)定理2.7對于任意集合A、B和C，設(shè)R和S分別是集合A到B和集合B到C的關(guān)系，那么： (RS) -1 = R-1 S-1 (RS) -1 = R-1 S-1 (RS) -1 = R-1S-1 (R) -1 = (R-1)

4、(AB) -1 = BA R-1 S-1當(dāng)且僅當(dāng)R S 自反性反自反性對稱性反對稱性傳遞性定義對于所有aA都有R對于所有aA都有R若R,則有R若R并且R,則有a=b若R并且R,則有R關(guān)系矩陣主對角線上全為1主對角線上全為0對稱陣反對稱陣(當(dāng)ij時rij和rji不能同時為1)如果rik=1并且rkj=1，則rij=1關(guān)系圖圖中每個結(jié)點都有環(huán)圖中每個結(jié)點都無環(huán)任意兩個不同的結(jié)點間要么沒有弧，要么有方向相反的一對弧。任意兩個結(jié)點間至多有一條弧若a到b有弧，b到c有弧，則a到c有弧集合IARRIA=R=R-1RR-1IARR R對關(guān)系性質(zhì)的判斷冪運算定義2.17設(shè)R是一個集合A上的關(guān)系，n為自然數(shù)，則

5、關(guān)系R的n次冪定義為： R0 = | xA = IA Rn+1 = Rn R 例冪運算的性質(zhì)定理2.9設(shè)R是集合A上的關(guān)系，m和n為自然數(shù)，那么 RmRn = Rm+n (Rm)n = Rmn R-n=(R-1)n例2.36設(shè)集合A = a, b, d, e, f上的關(guān)系 R = , , , , 求出最小的自然數(shù)s和t（st）使得Rs = Rt。 解：關(guān)系R的關(guān)系矩陣為那么，R2、R3、R4、R5、R6、R7的關(guān)系矩陣分別為：例由此，s= 0，t = 6。 關(guān)系的閉包運算問題：如果關(guān)系R不具有自反性（對稱性、傳遞性），那么給R增加盡可能少的有序?qū)?，使R具有這些性質(zhì)。要求： 添加序偶后使得二元關(guān)

6、系具有所希望的性質(zhì)； 添加的序偶最少。關(guān)系的自反閉包定義2.18 設(shè)R和R是集合A上的關(guān)系，如果滿足：（1）R是自反的；（2）R R；（3）對A上任何包含R的自反關(guān)系R都有RR。 則將R稱為R的自反閉包，記作r(R)。即，r(R)是包含R的最小的自反關(guān)系 。例2.37 求集合A=1,2,3上的關(guān)系R = , , , 的自反閉包。關(guān)系的對稱閉包定義2.18 設(shè)R和R是集合A上的關(guān)系，如果滿足：（1）R是對稱的；（2）R R；（3）對A上任何包含R的自反關(guān)系R都有RR。 則將R稱為R的對稱閉包，記作s(R)。即，s(R)是包含R的最小的對稱關(guān)系 。例2.38 求集合A=1,2,3上的關(guān)系R = ,

7、 , , 的對稱閉包。關(guān)系的傳遞閉包定義2.18 設(shè)R和R是集合A上的關(guān)系，如果滿足：（1）R是傳遞的；（2）R R；（3）對A上任何包含R的自反關(guān)系R都有RR。 則將R稱為R的傳遞閉包，記作t(R)。即，t(R)是包含R的最小的傳遞關(guān)系 。例2.39 求集合A=1,2,3上的關(guān)系R = , , , 的傳遞閉包。基于關(guān)系圖求解閉包例2.40 設(shè)集合A = 1, 2, 3上的關(guān)系R = , , , ，畫出關(guān)系R及其自反閉包、對稱閉包和傳遞閉包的關(guān)系圖。解:關(guān)系R及其自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)的關(guān)系圖 求r(R)：對不含自環(huán)的頂點添加自環(huán)。求s(R)：如果兩個不同的結(jié)點之

8、間只有一條邊，則在它們之間添加一條相反方向的邊。求t(R)：如果存在結(jié)點x指向y的一條邊，且存在y指向z的一條邊，但沒有x指向z的一條邊，則添加一條x指向z的邊；重復(fù)該過程，直到不再需要添加有向邊為止。 1 2 3 r(R) 1 2 3 R 1 2 3 s(R) 1 2 3 t (R)閉包運算的性質(zhì)定理2.11 設(shè)R是非空集合A上的關(guān)系（即A并且RAA），則：(1) r(R) = RIA(2) s(R) = RR1(3) t(R) = RR2R3 （注意：從R開始）(4) 如果|A|=n，則 t(R) = RR2Rn (5) 當(dāng)A為有窮集合時，存在自然數(shù)k1使得 t(R) = RR2Rk 用來求閉包！閉包的性質(zhì)對閉包再進行閉包運算rs(R) 、sr(R)rt(R) 、tr(R)st(R)、ts(R)定理2.12 設(shè)R是非空集合A上的關(guān)系（即A并且RAA），則：(1) rs(R) = sr(R)(2)