1、 上節(jié)課內(nèi)容上節(jié)課內(nèi)容 關(guān)系的運算關(guān)系的運算基本運算定義基本運算定義交、并、差和對稱差交、并、差和對稱差定義域、值域、域定義域、值域、域逆、復(fù)合逆、復(fù)合基本運算的性質(zhì)基本運算的性質(zhì)冪運算冪運算1 二元關(guān)系的性質(zhì)與閉包（二元關(guān)系的性質(zhì)與閉包（7.3-7.47.3-7.4）性質(zhì)性質(zhì)自反性、反自反性自反性、反自反性對稱對稱性、反對稱性性、反對稱性傳遞性傳遞性閉包閉包自反閉包自反閉包r(R)對稱對稱閉包閉包s(R)傳遞閉包傳遞閉包t(R)23/497.3 二元關(guān)系的性質(zhì)二元關(guān)系的性質(zhì)1、自反性與反自反性自反性與反自反性定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1) 若若 x(xA(x,x) R),

2、則稱則稱R在在A上是上是自反自反的的.(2) 若若 x(xA(x,x) R), 則稱則稱R在在A上是上是反自反反自反的的.實例：實例：反關(guān)系：反關(guān)系：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA 反自反關(guān)系：實數(shù)集上的小于關(guān)系反自反關(guān)系：實數(shù)集上的小于關(guān)系 冪集上的真包含關(guān)系冪集上的真包含關(guān)系例例1 A=1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中R1,R2,R34R2自反自反, R3反自反反自反, R1既不是自反也不是反自反的既不是自反也不是反自反的52、對稱性與反對稱性對稱性與反對稱性定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1) 若若 x y(x,yA

3、RR), 則稱則稱R為為A上上對稱對稱的關(guān)系的關(guān)系. (2) 若若x y(x,yARRx=y), 則稱則稱R為為A上的上的反對稱反對稱關(guān)系關(guān)系.實例：實例： 對稱關(guān)系：對稱關(guān)系：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA和和 空關(guān)系空關(guān)系 反對稱關(guān)系：恒等關(guān)系反對稱關(guān)系：恒等關(guān)系IA，空關(guān)系空關(guān)系例例2 設(shè)設(shè)A1,2,3, R1, R2, R3和和R4都是都是A上的關(guān)系上的關(guān)系, 其中其中 R1,， R2, R3,， R4, 6R1 對稱、反對稱對稱、反對稱. R2 對稱，不反對稱對稱，不反對稱. R3 反對稱，不對稱反對稱，不對稱. R4 不對稱、也不反對稱不對稱、也不反對稱.7

4、 3、傳遞性傳遞性 定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 若若 x y z(x,y,zA(x,y)R(y,z)R(x,z)R),則稱則稱R是是A上的上的傳遞傳遞關(guān)系關(guān)系.實例：實例： A上的全域關(guān)系上的全域關(guān)系EA,恒等關(guān)系恒等關(guān)系IA和空關(guān)系和空關(guān)系 小于等于關(guān)系小于等于關(guān)系, 小于關(guān)系，整除關(guān)系，包含關(guān)系，小于關(guān)系，整除關(guān)系，包含關(guān)系， 真包含關(guān)系真包含關(guān)系例例3 設(shè)設(shè)A1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中 R1, R2, R3 R4,8R1 、 R3 和和R4是是A上的傳遞關(guān)系上的傳遞關(guān)系 R2不是不是A上的傳遞關(guān)系上的傳遞關(guān)系9例例 設(shè)設(shè)A是一個任意

5、的非空集合是一個任意的非空集合lA上的全域關(guān)系具有自反性，對稱性和傳遞性。上的全域關(guān)系具有自反性，對稱性和傳遞性。lA上的恒等關(guān)系具有自反性、對稱性、反對稱上的恒等關(guān)系具有自反性、對稱性、反對稱性和傳遞性。性和傳遞性。 自反反自反對稱反對稱傳遞全關(guān)系全關(guān)系恒等關(guān)系恒等關(guān)系10/49例例1 設(shè)設(shè) A=1A=1，2 2，3 3 ，令，令R R1 1(1,1),(2,2),(3,3),(1,2)(1,1),(2,2),(3,3),(1,2)R R2 2(2,3),(3,2)(2,3),(3,2)R R3 3(1,1),(2,2),(2,3),(3,2),(3,1)(1,1),(2,2),(2,3),

6、(3,2),(3,1)。問問R R1 1、R R2 2、R R3 3具有哪些性質(zhì)？具有哪些性質(zhì)？自反反自反對稱反對稱傳遞R1R2R3答：答： R1有自反性、傳遞性、反對稱性；有自反性、傳遞性、反對稱性； R2有反自反性、對稱性；有反自反性、對稱性； R3沒有這五個性質(zhì)中的任何一個。沒有這五個性質(zhì)中的任何一個。11/49 例例2 試判斷下圖中所表示的三個關(guān)系的性質(zhì)。試判斷下圖中所表示的三個關(guān)系的性質(zhì)。答：答： (a)中的關(guān)系是對稱的、傳遞的；中的關(guān)系是對稱的、傳遞的； (b)中的關(guān)系是反自反的、反對稱的；中的關(guān)系是反自反的、反對稱的； (c)中的關(guān)系是自反的、反對稱的、傳遞的。中的關(guān)系是自反的、

7、反對稱的、傳遞的。212/49特點自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性定義對每個對每個x A，有，有(x,x) R對每個對每個x A，有，有(x,x) R若若(x,y) R,則有則有(y,x) R若若(x,y) R且且(y,x) R,則則xy若若(x,y) R且且(y,z) R則則(x,z) R關(guān)系矩陣的特點主對角線元素全為1主對角線元素全為0矩陣為對稱矩陣如果rij=1,且ij,則rji=0關(guān)系圖的特點每個頂點都有環(huán)每個頂點都沒有環(huán)如果兩個頂點之間有邊,一定是一對方向相反的邊如果兩個頂點之間有邊,一定是一條有向邊如果頂點A到B有邊,B到C有邊,則從A到C有邊1

8、3/49定理定理 (p100) R是集合是集合A上的一個二元關(guān)系，則上的一個二元關(guān)系，則(1) R有自反性當且僅當有自反性當且僅當 AR(2) R有反自反性當且僅當有反自反性當且僅當AR(3) R有對稱性當且僅當有對稱性當且僅當 RR (4) R有反對稱性當且僅當有反對稱性當且僅當 RRA (5) R有傳遞性當且僅當有傳遞性當且僅當 R RR14/49證明證明(3): R有對稱性當且僅當有對稱性當且僅當 RR 設(shè)設(shè)R R有對稱性，要證明有對稱性，要證明 R R 1 =R=R。 對于任意的對于任意的(x(x，y)y) R R， 則由對稱性定義則由對稱性定義,(y,(y，x)x) R R， 進而進

9、而(x(x，y)y) R R 1 ，故故 R R 1 R R。 反之，對于任意的反之，對于任意的(x(x，y)y) R R 1 ， 則由逆關(guān)系定義，則由逆關(guān)系定義，(y(y，x)x) R R， 又由于對稱性，有又由于對稱性，有(x(x，y)y) R R，故，故 R R 1 R R 。 再設(shè)再設(shè) R R 1 =R, =R, 要證明有對稱性。要證明有對稱性。 任取任取(x,y) (x,y) R (y,x) R 1 (y,x) R 因此因此 R 在在 A 上是對稱的上是對稱的.15/49例例3 (p101 R1和和R2是集合是集合A上兩個二元關(guān)系，上兩個二元關(guān)系， 若若R1和和R2均有對稱性，問均有

10、對稱性，問 R1R2，R1R2，R1R2，R1 R2 哪些仍有對稱性？哪些仍有對稱性？解：解：R1R2，R1R2，R1R2，R1 R2 都仍有對稱性。都仍有對稱性。 僅證明僅證明R1R2有對稱性，見下頁。有對稱性，見下頁。 16/49例例 R1和和R2是集合是集合A上兩個二元關(guān)系，上兩個二元關(guān)系， 若若R1和和R2均有對稱性，則均有對稱性，則 R1R2仍有對稱性。仍有對稱性。解：解： 對于任意的對于任意的 (x,y) R1R2， 要證明，要證明，(y,x) R1R2。 事實上，事實上，(x,y) R1，或，或(x,y) R2。 若若(x,y) R1，因為，因為R1對稱，對稱， 故故(y,x)

11、R1，即有，即有(y,x) R1R2 ； 若若(x,y) R2，因為，因為R2對稱，對稱， 故故(y,x) R2，即有，即有(y,x) R1R2。 所以所以 R1R2是對稱的。是對稱的。17/49例自反 反自反對稱反對稱傳遞R1R2R1R2R1R2R1R2R1 R2可以參考各種性質(zhì)的直觀意義來理解這張表可以參考各種性質(zhì)的直觀意義來理解這張表自反 反自反對稱反對稱傳遞R1R2R1R2R1R2R1R2R1 R218/557.4 二元關(guān)系的閉包運算二元關(guān)系的閉包運算7.4.1 自反閉包自反閉包、對稱閉包、傳遞閉包對稱閉包、傳遞閉包7.4.2 閉包閉包的判斷定理的判斷定理19/55例例 設(shè)設(shè) A=1,

12、2,3，R=(1,1), (1,2). 顯然，顯然，R不具有自反性。不具有自反性。 添加兩個元素添加兩個元素(2,2)與與(3,3)或更多的二元組后，或更多的二元組后， 所得的關(guān)系都具有自反性：所得的關(guān)系都具有自反性： R1(1,1), (1,2), (2,2), (3,3) R2(1,1), (1,2), (2,2), (3,3), (3,1) R3(1,1), (1,2), (2,2), (3,3), (2,3) R4(1,1), (1,2), (2,2), (3,3), (2,3),(2,1),(1,3) 20/55例例 設(shè)設(shè) A=1,2,3，R=(1,1), (1,2). 顯然，顯然，

13、R不具有對稱性。不具有對稱性。 添加元素添加元素(2,1)，或適當再添加一些元素后，或適當再添加一些元素后， 所得的關(guān)系可以具有對稱性：所得的關(guān)系可以具有對稱性： R1(1,1), (1,2), (2,1) R2(1,1), (1,2), (2,1), (2,2) R3(1,1), (1,2), (2,1), (3,2), (2,3) R4(1,1), (1,2), (2,1), (1,3), (3,1),(3,3) 21/55例例 設(shè)設(shè) A=1,2,3，R=(2,1), (1,2). 顯然，顯然，R不具有傳遞性。不具有傳遞性。 添加添加(1,1)與與(2,2)，或適當再添加一些元素后，或適當

14、再添加一些元素后， 所得的關(guān)系可以具有傳遞性：所得的關(guān)系可以具有傳遞性： R1(2,1), (1,2), (1,1), (1,2) R2(2,1), (1,2), (1,1), (2,2), (2,3) R3(2,1), (1,2), (1,1), (2,2), (2,3), (3,3) R4(2,1), (1,2), (1,1), (2,2), (3,2), (3,3) 22/55閉包閉包設(shè)是一個集合，是上的一個二元關(guān)系。設(shè)是一個集合，是上的一個二元關(guān)系。 假定是關(guān)系的某一性質(zhì)。假定是關(guān)系的某一性質(zhì)。 包含了關(guān)系、且具有性質(zhì)的包含了關(guān)系、且具有性質(zhì)的最小最小集合集合RR （關(guān)系），（關(guān)系），

15、 被稱為的具有性質(zhì)的被稱為的具有性質(zhì)的閉包閉包。這里，性質(zhì)僅限于自反性、對稱性、傳遞性。這里，性質(zhì)僅限于自反性、對稱性、傳遞性。23/55（1）是自反是自反(對稱、傳遞對稱、傳遞)的；的；（2） ；（3）對任一關(guān)系）對任一關(guān)系”，若，若” ，且，且”有自反有自反(對稱、傳遞對稱、傳遞)性，則性，則” 。則則R被稱為的自反被稱為的自反(對稱、傳遞對稱、傳遞)閉包閉包.定義定義 是一個非空集合，是一個非空集合， 是上的一個二元關(guān)系，是上的一個二元關(guān)系， 若關(guān)系若關(guān)系 滿足以下三個條件：滿足以下三個條件： 自反閉包、對稱閉包、傳遞閉包自反閉包、對稱閉包、傳遞閉包24/55r(R)、 s(R)、 t(

16、R) 記號記號 r(R)表示表示R的自反閉包的自反閉包(reflexive closure) s(R)表示表示R的對稱閉包的對稱閉包(symmetric closure) t(R)表示表示R的傳遞閉包的傳遞閉包(transitive closure)例例 設(shè)設(shè) A=1,2,3， R=(1,1), (1,2), (2,3) 則則 r(R)(1,1), (2,2), (3,3), (1,2), (2,3) s(R)(1,1), (1,2), (2,1), (2,3), (3,2) t(R) (1,1), (1,2), (2,3), (1,3) 25定理定理1 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則有則

17、有 (1) r(R) = RR0(2) s(R) = RR 1(3) t(R) = RR2R3閉包的構(gòu)造方法閉包的構(gòu)造方法1說明：說明： 對于有窮集合對于有窮集合A (|A|=n) 上的關(guān)系上的關(guān)系, (3)中的并最中的并最多不超過多不超過 Rn. 若若 R是自反的，則是自反的，則 r(R)=R; 若若R是對稱的，則是對稱的，則 s(R)=R; 若若R是傳遞的，則是傳遞的，則 t(R)=R. 26例例2 (p105)設(shè)設(shè) A=a, b, c, d R=(a,b), (b,c), (c,d)。 求求 r(R)，s(R)，t(R)。解：解： r(R)RA (a,b), (b,c), (c,d),

18、(a,a), (b,b), (c,c), (d,d) s(R)RR 1 (a,b), (b,c), (c,d), (b,a), (c,b), (d,c) 要求要求t(R)，先求，先求R2，R3，R4。 R2(a,c), (b,d) R3(a,d) R4= 則則 t(R)RR2R3R4= (a,b), (b,c), (c,d), (a,c), (b,d), (a,d) 27設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為的關(guān)系矩陣分別為M, Mr, Ms 和和 Mt , 則則 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和是和 M 同

19、階的單位矩陣同階的單位矩陣, M是是 M 的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣. 注意在上述等式中矩陣的元素相加時使用邏輯加注意在上述等式中矩陣的元素相加時使用邏輯加.閉包的構(gòu)造方法閉包的構(gòu)造方法228例例 設(shè)設(shè)A=1,2,3， R=(1,2),(2,3),(3,1)試用關(guān)系矩陣求試用關(guān)系矩陣求其其閉包。閉包。001100010RM( )110011101r RM( )011101110s RM解：用關(guān)系矩陣求的方法如下：解：用關(guān)系矩陣求的方法如下：290100011000011000100011000102RRRMMM10001000100110001001000110023RRRMMM1111111113

20、2)(RRRRtMMMM其中，表示矩陣的對應(yīng)元素進行析取運算。 30設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系圖分別記為的關(guān)系圖分別記為G, Gr, Gs, Gt , 則則Gr, Gs, Gt 的頂點集與的頂點集與G 的頂點集相等的頂點集相等. 除了除了G 的邊以外的邊以外, 以下述方法以下述方法添加新邊添加新邊： 考察考察G的每個頂點的每個頂點, 如果沒有環(huán)就如果沒有環(huán)就加加上一個上一個環(huán)環(huán)，最，最終得到終得到Gr . 考察考察G的每條邊的每條邊, 如果有一條如果有一條 xi 到到 xj 的單的單向邊向邊, ij, 則在則在G中中加加一條一條 xj 到到 xi 的的反方向邊反方

21、向邊，最終，最終得到得到Gs. 考察考察G的每個頂點的每個頂點 xi, 找從找從 xi 出發(fā)的每一條路出發(fā)的每一條路徑，如果從徑，如果從 xi 到路徑中任何結(jié)點到路徑中任何結(jié)點 xj 沒有邊，就加上沒有邊，就加上這條邊這條邊. 當檢查完所有的頂點后就得到圖當檢查完所有的頂點后就得到圖Gt . 閉包的構(gòu)造方法閉包的構(gòu)造方法331/55例例 A=a, b, c, d, e, R如下圖所示如下圖所示, 求求r(R).abcdeabcder(R)=R A 解：解：32/55例例 求求s(R)abcdeabcdes(R)=RR解：解：33/55例例 求求t(R).abcdeT(R)= R R2 R3ab

22、cde解：解： 小結(jié)小結(jié)關(guān)系的性質(zhì)關(guān)系的性質(zhì)自反性、反自反性自反性、反自反性對稱對稱性、反對稱性性、反對稱性傳遞性傳遞性閉包閉包自反閉包自反閉包r(R)對稱對稱閉包閉包s(R)傳遞閉包傳遞閉包t(R)3435/55例例3(p105) 設(shè)設(shè)R是自反的是自反的,問問s(R)與與t(R)是否自反的？是否自反的？ 設(shè)設(shè)R是對稱的是對稱的,問問r(R)與與t(R)是否對稱的？是否對稱的？ 設(shè)設(shè)R是傳遞的是傳遞的,問問r(R)與與s(R)是否傳遞的？是否傳遞的？r(R)s(R)t(R)R自反: ARAs(R)?At(R)?對稱: R=Rr(R)=r(R)?t(R)=t(R)?傳遞: R RRr(R) r(

23、R)r(R)?s(R) s(R)s(R)?36/55r(R)s(R)t(R)R自反對稱傳遞例例3(p105) 設(shè)設(shè)R是自反的是自反的,問問s(R)與與t(R)是否自反的？是否自反的？ 設(shè)設(shè)R是對稱的是對稱的,問問r(R)與與t(R)是否對稱的？是否對稱的？ 設(shè)設(shè)R是傳遞的是傳遞的,問問r(R)與與s(R)是否傳遞的？是否傳遞的？37/55例4 (p105) 設(shè)設(shè)RAA ，試證：，試證：（1） rs(R)sr(R) （2） rt(R)tr(R) （3） st(R) ts(R)，并給出，并給出st(R)ts(R)的例子的例子.其中其中 rs(R) r(s(R)表示表示R的對稱閉包的自反閉包，的對稱閉包的自反閉包， sr(R) s(r(R)表示表示R的自反閉包的對稱閉包，的自反閉包的對稱閉包， rt(R) r(t(R)表示表示R的傳遞閉包的自反閉包，的傳遞閉包的自反閉包， tr(R) t(r(R)表示表示R的自反閉包的傳遞閉包，的自反閉包的傳遞閉包， st(R) s(t(R)表示表示R的傳遞閉