離散數(shù)學(xué) 7

1、第4章 關(guān)系,1,4-1.關(guān)系及其運算,關(guān)系的基本概念“關(guān)系”是一個很基本的概念,為了用數(shù)學(xué)的方法來研究和討論各種關(guān)系,下面從集合論的觀點來描述關(guān)系.例:設(shè)A={a , b , c , d , e , f}, a , b , c , d , e , f分別表示６個男人,其中a是b和c的父親 ,b是d的父親,c是 e和f的父親.則這6個人中所有符合父子關(guān)系的兩個人可分別用有序偶(a , b) , (a , c) , (b , d

2、) , (c , e) , (c , f)來表示，則集合 Ｒ＝｛ (a , b) , (a , c) , (b , d) , (c , e) , (c , f)｝可完整地描述出集合Ａ中元素的父子關(guān)系．稱R為集合上的一個關(guān)系(父子關(guān)系).　例:Ａ＝｛１，２，３｝上的小于關(guān)系可表示為,2,Ｒ＝｛(1 , 2) , (1 , 3) , (2 , 3)},兩個集合之間的關(guān)系,設(shè)A={a ,b ,c ,d} ,B={m ,p ,e} ,

3、A中的元素a ,b ,c ,d分別表示4位中學(xué)教師,B中的元素m ,p ,e分別表示數(shù)學(xué)課程、物理課程和英語課程。如果a和b是數(shù)學(xué)教師，c是物理教師，d是英語教師。則有序偶:,3,(a ,m) ,(b ,m) (c ,p) ,(d ,e),表示了這4位教師和他們所講授課程的關(guān)系。由這些有序偶作為元素構(gòu)成的集合 R={(a ,m) ,(b ,m) (c ,p) ,(d ,e)} 稱為A到B的二元關(guān)系。,二元關(guān)系的實質(zhì)是什么？,關(guān)系

4、的實質(zhì),由于二元關(guān)系就是符合某種特定要求的有序偶的集合.因此A到B的二元關(guān)系應(yīng)是笛卡兒乘積A × B的子集A上的二元關(guān)系應(yīng)是A上的笛卡兒乘積A × A的子集。為了便于對二元關(guān)系進行一般性的討論，下面把二元關(guān)系的概念抽象化，即抽象地把二元關(guān)系看做是笛卡兒乘積的子集。,4,二元關(guān)系的定義,定義　 設(shè)A, B 是集合，R是笛卡兒乘積A × B的子集，則稱R為A到B的一個二元關(guān)系。例如:設(shè)A = {a,

5、b, c, d}, B = {x, y, z}, 令R = {(a, y), (b, x), (b, y), (d, x)}由于R是A × B的子集，所以R是A到B的一個二元關(guān)系。類似,可定義n元關(guān)系.,5,n元關(guān)系的定義,定義,6,二元關(guān)系的定義,對于二元關(guān)系R,如果 (a, b) ∈R，也可記作aRb，并稱a 與b 有關(guān)系R。如果(a, b) 　R，也可記作a R b，并稱a與b沒有關(guān)系R。定義 設(shè)A是集合

6、，R是A上的笛卡兒乘積A × A的子集，則稱R為A上的一個二元關(guān)系。例如:設(shè)A = {1，2，3，4，5}, R = {（1，1）,（2，5）,（3，1）,（4,3）,(4,5)}，由于R是A × A的子集，所以R為A上的一個二元關(guān)系。,7,,,二元關(guān)系的定義域和值域,定義 設(shè)S是A到B的二元關(guān)系，使(x, y) ∈S的所有x組成的集合稱為S的定義域，記作D(S)；使(x, y) ∈S的所有y組成的集合稱為S的值

7、域，記作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一個元素構(gòu)成的集合, C(S)就是S的所有有序偶的第二個元素構(gòu)成的集合.,8,,,,求關(guān)系的定義域和值域,例如:設(shè) 則R的定義域D(R) ， 值域C(R),9,,,,例1,例1:設(shè)A = {2，4，6，8}，R是A上的小于關(guān)系，即當(dāng)a, b∈A且a< b時，（a, b）∈R，求R及D( R ),C(

8、 R ) 解:R = {（2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）}.　　R的定義域D( R ) ={2，4，6}，　　R的值域C( R ) = {4，6，8}。,10,例2,例2:設(shè)A = {2，3，4，6，12}，R是A上的整除關(guān)系，即當(dāng)a, b∈A且a能整除b時，（a, b）∈R，求R及D( R ),C( R ) 解:A上有整除關(guān)系為R = {（2，2）,（2，4）,（2，6）,（2，1

9、2）,（3，3）,（3，6）,（3，12）,（4，4）,（4，12）,（6，6）,（6，12）,（12，12）}，　R的定義域D( R ) ={2，3，4，6，12}，　R的值域C( R ) = {2，3，4，6，12}。,11,例3 設(shè)A = {a, b}，B = { x，y }，寫出所有A到B的二元關(guān)系。,12,例3,,，,,,,例3 設(shè)A = {a, b}，B = { x，y }，寫出所有A到B的二元關(guān)系。 解: 由于

10、 ，所以 ，由此可知，A × B共有子集數(shù)為 = 16，即共有16種A到B的二元關(guān)系：,13,例3,,，,,,,例3的說明,此例說明，當(dāng)時 ，A到B共可定義 種不同的二元關(guān)系。問:在一個有n個元素的集合A上，可以有多少種不同的二元關(guān)系？　答：共有　　　種．,14,,,,三種特殊的關(guān)系,對于任意集合，空集和集合本身都是它的子集，常

11、稱這兩種子集為平凡子集。定義　笛卡兒乘積A × B的兩個平凡子集，空集　和A × B本身稱為集合A到B的空關(guān)系和全域關(guān)系。定義　 設(shè)R是A上的二元關(guān)系且滿足則稱R為A上的恒等關(guān)系，并記作　　。,15,,,,例子,例4:設(shè)集合A = {1，2，3}，R是A上的二元關(guān)系， 當(dāng)a, b∈A且a×b>0時，（a, b）∈R。則R = {（1，1）,（1，2）,（1，3）,（2，1）,（2，2）,

12、（2，3）,（3，1）,（3，2）,（3，3）} 所以R是A上的全域關(guān)系。 若令當(dāng)a, b∈A且a×b < 0時，（a, b）∈R，則R= 即R是A上的空關(guān)系。例5:設(shè)A = {a, b, c, d },則A上的恒等關(guān)系 = {(a, a), (b, b), (c, c), (d, d)}。,16,,,練習(xí),2 關(guān)系的表示方法,1.關(guān)系矩陣 設(shè)集合

13、 ，R是A到B的二元關(guān)系，令 則稱為R的關(guān)系矩陣.,17,,,關(guān)系的表示方法,例1:設(shè) R是A到B的二元關(guān)系，且則R的關(guān)系矩陣為,18,,,,A是行數(shù)，B是列數(shù),關(guān)系的表示方法,設(shè) , R為A上的二元關(guān)系,令 則n階方陣稱為R的關(guān)系矩陣,19,,,,關(guān)系的表示方法,例2 設(shè)A =

14、{1,2,3,4,5}, R是A上的小于等于關(guān)系, 即當(dāng)a ≤ b時, (a, b) ∈R。求R的關(guān)系矩陣。解:易知A上的小于等于關(guān)系為R ={（1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3), (2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)}其關(guān)系矩陣為,20,,關(guān)系的表示方法,2.關(guān)系圖 設(shè)集合

15、 ，R是A到B的二元關(guān)系。R的圖形表示是在平面上用n 個點分別表示A中的元素 ；再在平面上畫出m個點分別表示B中元素 ；當(dāng) 時，從點 至 畫一條有向邊，其箭頭指向 ，否則就不畫邊。例3:R是A到B的二元關(guān)系，且則R的關(guān)系圖為？,21,,,,,,,,,,關(guān)系的表示方法,當(dāng)R是A上的二元關(guān)系時，經(jīng)常采用如下的圖形表示方法： 在平面

16、上僅僅畫n個點分別表示A中的元素 ， 當(dāng) 時，從點 至 畫一條有向邊，箭頭指向 。例如， ，R是A上的二元關(guān)系，且 則R的關(guān)系圖為？,22,,,,,,,,小結(jié),二元關(guān)系的表示方法（它們可唯一相互確定）集合表達式關(guān)系矩陣（用矩陣表示關(guān)系，便于在計算機中對關(guān)系進行存儲和計算，并可充分利用矩陣的結(jié)論）關(guān)系圖（關(guān)系圖直觀清

17、晰，是分析關(guān)系性質(zhì)的方便形式，但它不便于進行運算）,23,練習(xí),3.關(guān)系的運算,關(guān)系的交、并、差、對稱差、補設(shè)R和S是集合A上的兩個二元關(guān)系,則 R∩S , R∪S , R - S , R + S , ～R 仍是A上的二元關(guān)系.,24,關(guān)系的運算,例：X={a,b,c}，Y={1，2}， 關(guān)系R={(a,1),(b,2),(c,1)} S={(a,1),(b,1),(c,1)}則：R∪S={(a,1)

18、,(b,1), (b,2),(c,1)} R∩S={(a,1),(c,1)} E={(a,1), (a,2), (b,1), (b,2), (c,1), (c,2),}R=E-R={(a,2), (b,1), (c,2)},25,,練習(xí),復(fù)合關(guān)系,1. 復(fù)合關(guān)系的定義定義 R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，R和S的復(fù)合記作RοS，它是A到C的二元關(guān)系，僅當(dāng) (a, b)∈R，且(b , c)

19、∈S時，(a, c)∈RοS。例:設(shè) 　，R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，且 則R和S的復(fù)合,26,,,,用關(guān)系圖法求復(fù)合關(guān)

20、系,R S A B C a1 b1 c1 a2

21、 b2 c2 a3 b3 c3 b4,27,,,,,,,,,,,,,,,,,,,用關(guān)系圖法求復(fù)合關(guān)系,

22、由R和S的關(guān)系圖得，復(fù)合關(guān)系 R S A A A a1

23、 a1 a1 a2 a2 a2 a3 a3

24、 a3 a4 a4 a4 a5 a5 a5,28,,,,,,,,,,,,,,,,,,,,復(fù)合關(guān)系的矩陣表

25、示,定理 R是A到B的二元關(guān)系，其關(guān)系矩陣為 ，S是B到C的二元關(guān)系，其關(guān)系矩陣為 ，復(fù)合關(guān)系RοS是A到C的二元關(guān)系，其關(guān)系矩陣為 ，則 注意:按普通矩陣乘法求 ,只不過是將乘法改為布爾乘,加法改為布爾加.,29,,,,,,,例1,設(shè)A = {1，2，3}，B = {a, b, c, d}, C = {x, y, z}，R是A到B的二元關(guān)系，R = {(1, a), (1, b), (2,

26、b), (3, c)}，S是B到C的二元關(guān)系，S = {(a, x), (b, x), (b, y), (b, z)}。求復(fù)合關(guān)系RοS的關(guān)系矩陣.解:因為 所以,30,,,例2,設(shè)A = {1，2，3，4}，R和S都是A上的二元關(guān)系，R = {（1，1），（1，2），（2，3），（2，4），（3，2），（4，3），（4，4）}，S = {（1，2），（1，3），（2，3），（2，4），（3，3），（4，3）},求復(fù)合

27、關(guān)系RοS的關(guān)系矩陣 。 解:,31,,,,RοS={(1,2),(1,3),(1,4),(2,3),(3,3).(3,4),(4,3)},練習(xí),二元關(guān)系的冪,二元關(guān)系的復(fù)合可產(chǎn)生一個新的二元關(guān)系，因此二元關(guān)系的復(fù)合也是二元關(guān)系的一種運算。由于二元關(guān)系與其關(guān)系矩陣一一對應(yīng)，復(fù)合關(guān)系RοS的關(guān)系矩陣等于R的關(guān)系矩陣與S的關(guān)系矩陣的乘積，而矩陣的乘法是滿足結(jié)合律的，所以關(guān)系的復(fù)合也滿足結(jié)合律，即 (RοS)οT

28、 = Rο(SοT)二元關(guān)系的冪 由于二元關(guān)系的復(fù)合滿足結(jié)合律,所以二元關(guān)系的冪是有意義的.,32,,逆關(guān)系,定義 設(shè)R是A到B的二元關(guān)系，如果把R中的每一個有序偶中的元素順序互換，所得的B到A的二元關(guān)系稱為R的逆關(guān)系，記作 例1:設(shè)A = {x, y, z}, B = {a, b}，R是A到B的二元關(guān)系，且有 R = {(x, a), (y, b), (z, a)} 則R的逆關(guān)系 是B到A的

29、二元關(guān)系，且有,33,,,,逆關(guān)系,例2:設(shè)A = {1, 2, 3, 4}, R是A上的二元關(guān)系, 且有 R = {(1, 2), (2, 3), (3, 4)} 則其逆關(guān)系 由逆關(guān)系的定義可知 如果二元關(guān)系R的關(guān)系矩陣為 ，則 的轉(zhuǎn)置矩陣 就是逆關(guān)系 的關(guān)系矩陣，即　　　如果把R的關(guān)系圖中每條有向邊的方向顛倒，就得到逆關(guān)系 的關(guān)系圖。,

30、34,,,,,,,,逆關(guān)系,又由矩陣的運算法則可知由此可得以下定理。定理 設(shè)R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，則,35,,,練習(xí),4-2 關(guān)系的重要性質(zhì),關(guān)系的基本類型：　　?。保苑吹亩P(guān)系　　　２．反自反的二元關(guān)系　　?。常畬ΨQ的二元關(guān)系　　　４．反對稱的二元關(guān)系　　?。担蓚鬟f的二元關(guān)系　　或稱為關(guān)系的性質(zhì)：自反性、反自反性、對稱性、反對稱性、可傳遞性,36,1. 自反的二元關(guān)系,定義 設(shè)R

31、是A上的二元關(guān)系，如果對于A中每一個元素x ，都有(x, x )∈R，則稱R是自反的，也稱R具有自反性。例1: A = {a, b, c}, A上的二元關(guān)系R = {(a, a), (b, b), (c,c), (a,c), (c, b) }，則R是自反的二元關(guān)系。例2:設(shè)A={1,2,3,4}, R={(1,1),(2,2),(3,4),(4,2)},因為3∈A,但(3,3) , 所以R不是A上的自反關(guān)系.,

32、37,,1. 自反的二元關(guān)系,例3：設(shè)A = {1,2,3}, 1.R是A上的小于關(guān)系, 即當(dāng) a<b 時, (a, b) ∈R。求R的關(guān)系矩陣。2.S是A上的等于關(guān)系, 即當(dāng) a=b 時, (a, b) ∈R。求S的關(guān)系矩陣。解:R = {(1,2)(1,3)(2,3)},38,1. 自反的二元關(guān)系,一個集合的關(guān)系R是自反的：當(dāng)且僅當(dāng)關(guān)系矩陣的對角線元素都為1。例： A = {a, b, c}, A上的二元關(guān)系R =

33、 {(a, a),(b, b),(c, c),(a, c),(c, b)},39,R是自反關(guān)系,2. 反自反的二元關(guān)系,定義 R是A上的二元關(guān)系，如果對于A中每一個元素x,都有(x, x ) ,則稱R是反自反的，也稱R具有反自反性。例1:設(shè)A = {a, b, c}, R = {(a, c), (b, a), (b, c), (b, b) }因為(b,b)∈R, 則R不是A上的反自反關(guān)系。 例2:設(shè)A = {1，2，3}，

34、R是A上的小于關(guān)系，即Ｒ＝｛(1,2),(1,3),(2,3)}由于(1, 1), (2, 2), (3, 3)都不屬于R，所以R是A上的反自反關(guān)系。,40,,,,2. 反自反的二元關(guān)系,例3:設(shè)A={1,2,3},R={(1,2),(2,3),(3,2),(3,3)}, S={(1,1),(2,2),(2,3),(3,3)},則 R既不是A上的反自反關(guān)系(因(3,3)∈R), 也不是A上的自反關(guān)系(因(1,1)

35、 ) S是A上的自反關(guān)系,但不是反自反關(guān)系.注意:一個關(guān)系R如果不是自反關(guān)系，不一定是反自反關(guān)系.,41,,,2. 反自反的二元關(guān)系,一個集合的關(guān)系R是反自反的：當(dāng)且僅當(dāng)關(guān)系矩陣的對角線元素都為0。例： A = {a, b, c}, A上的二元關(guān)系R = {(a, b),(a, c),(c, b)},42,R是反自反關(guān)系,3. 對稱的二元關(guān)系,定義 R是A上的二元關(guān)系，每當(dāng)(x, y) ∈R時，就一定有(y, x

36、) ∈R，則稱R是對稱的，也稱R具有對稱性。例1:設(shè)A = {a, b, c}, R = {(a, b), (b, a), (a, c), (c, a) }，所以R是對稱的。例2:設(shè)A={1,2,3,4}上的二元關(guān)系 R={(1,1),(1,2),(2,1),(3.3),(4,3),(4,4)},因為(4,3)∈R但(3,4) 。所以R不是對稱的。,43,,3. 對稱的二元關(guān)系,一個集合的關(guān)系R是對稱的：當(dāng)且僅當(dāng)關(guān)系矩陣

37、關(guān)于對角線對稱。例： A = {a, b, c，d}, A上的二元關(guān)系R = {(a, b),(a, d),(b,a),(b,c),(c, b), (c,d),(d,a),(d,c),(d,d) },44,R是對稱關(guān)系,3. 對稱的二元關(guān)系,例： A = {a, b, c，d}, A上的二元關(guān)系R = {(a, b),(a,d),(b,a),(d,d) },45,R不是對稱關(guān)系,4. 反對稱的二元關(guān)系,定義 R是A

38、上的二元關(guān)系，當(dāng)x ≠ y時，如果 (x, y)∈ R，則必有(y, x) ，稱R是反對稱的，也稱R具有反對稱性。例1: A={1,2,3,}上的關(guān)系R={(1,2),(2,2),(3,1)},則R是反對稱的.但S={(1,2),(1,3),(2,2),(3,1)}不是反對稱的.因為1≠3但(1,3)∈S,且(3,1)∈S,46,,4. 反對稱的二元關(guān)系,例2: 設(shè)A = {2，3，4，6，}，R是A上的整除關(guān)系(即當(dāng)a, b

39、∈A且a能整除b時，（a, b）∈R)，問R是否是A上的反對稱關(guān)系?解:因為R = {（2，2）,（2，4）,（2，6）,（3，3）,（3，6）,（4，4）,（6，6）} 由定義知：R是反對稱的.例3: 實數(shù)集合上的小于關(guān)系和小于等于關(guān)系都是反對稱的.,47,,4. 反對稱的二元關(guān)系,關(guān)系R是反對稱的，則其關(guān)系矩陣為：如果rij=1,并且i≠j，則rji=0A = {2，3，4，6，}R = {(2,4),(2,6),(3,6

40、)},48,4. 反對稱的二元關(guān)系,例4:設(shè)A={a, b, c, d}上的關(guān)系 R={(a ,a) ,(b ,c) ,(c ,d) ,(d ,c)} ,　S={(a ,a) ,(b ,b) ,(d ,d)},則　R既不是對稱的(因為(b ,c)∈R但(c ,b) ),也不是反對稱的 (因為(c ,d)∈R且(d ,c)∈R) 而S既是對稱的,也是反對稱的.,49,,4. 反對稱的二元關(guān)系 小結(jié),注意:對稱關(guān)系和反對稱關(guān)系不

41、是兩個相互否定的概念. 存在既是對稱的也是反對稱的二元關(guān)系,　也存在既不是對稱的也不是反對稱的二元關(guān)系.,50,,5. 可傳遞的二元關(guān)系,定義 設(shè)R是A上的二元關(guān)系，每當(dāng)(x, y) ∈R且(y, z) ∈ R時，必有 (x, z)∈ R，則稱R是可傳遞的，也稱R具有可傳遞性。例1:實數(shù)集上的小于關(guān)系和小于等于關(guān)系都是可傳遞關(guān)系.如：a<b,b<c 則a<c,51,,5. 可傳遞的二元關(guān)系,例2:設(shè)A={a

42、 ,b ,c}上的關(guān)系R={(a ,a) ,(a ,b) ,(b ,c) ,(a ,c)}, S={(a ,b) ,(c ,b)} , T={(a,b) ,(b ,b) ,(b ,c)},則R,S,T是否可傳遞？ R,S是可傳遞的,T不是可傳遞的 因為T中有(a ,b)∈T ,(b ,c)∈ T但(a ,c) ,所以T不是可傳遞關(guān)系,52,,例3,設(shè)A = {a, b, c}， R是A上的二元關(guān)系，

43、 R = {(a, a), (b, b), (a, b), (a, c) , (c, a)}，問：R是自反的嗎？是反自反的嗎？是對稱的嗎？是反對稱的嗎？是可傳遞的嗎？解 由于c∈ A，而(c, c) ，所以R不是自反的。由于(a, a) ∈R，(b, b) ∈R，所以R不是反自反的。由于(a, b) ∈R，而(b, a) ，所以R不是對稱的。由于(a, c) ∈R，且(c, a) ∈R，所以R不是反對稱的

44、。由于(c, a) ∈R且(a, c) ∈R，但(c, c) ，所以R不是可傳遞的。,53,,,,自反,反自反,對稱,反對稱,可傳遞關(guān)系判定方法,定義法關(guān)系矩陣法關(guān)系圖法,54,幾種基本關(guān)系的關(guān)系矩陣和關(guān)系圖的特征,55,,,,,,,,,,,例1：判斷關(guān)系的性質(zhì),設(shè)A = {1，2，3}，分析A上的下述5個關(guān)系各具有哪些性質(zhì)？ L = {, , , , } N = {, } S = {, , } G = {,

45、 , },56,L = {, , , , },57,1.自反性：,對角線全為1，所以具自反性 √,矩陣對稱，所以具對稱性 √,3.對稱性：,對角線全不為0，所以不具自反性 ×,2.反自反性：,不具反對稱性 ×,4.反對稱性：,5.傳遞性：,具傳遞性 √,關(guān)系矩陣法,N = {, },58,1.自反性：,對角線全為0，所以不具自反性 ×,矩陣不對稱，所以不具對稱性

46、×,3.對稱性：,對角線全為0，所以具反自反性 √,2.反自反性：,具反對稱性 √,4.反對稱性：,5.傳遞性：,具傳遞性 √,關(guān)系矩陣法,S = {, , },59,1.自反性：,所有點均無環(huán)，所以不具自反性 ×,出現(xiàn)單邊，所以不具對稱性 ×,3.對稱性：,所有點均無環(huán)，所以具反自反性 √,2.反自反性：,出現(xiàn)雙邊，不具反對稱性 ×,4.反對稱性

47、：,5.傳遞性：,不具傳遞性 ×,關(guān)系圖法,G = {, , },60,1.自反性：,存在點無環(huán)，所以不具自反性 ×,出現(xiàn)單邊，所以不具對稱性 ×,3.對稱性：,點1有環(huán)，所以不具反自反性 ×,2.反自反性：,沒有出現(xiàn)雙邊，具反對稱性 √,4.反對稱性：,5.傳遞性：,不具傳遞性 ×,關(guān)系圖法,例2：,61,A={1，2，3}，R1=

48、6;，R2=A×A，試判斷兩關(guān)系的性質(zhì)。,R1：,反自反,對稱,反對稱,傳遞,R2：,自反,對稱,傳遞,R2={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)},例題３,設(shè)R1,R2為A上的對稱關(guān)系，證明R1∩R2也是A上的對稱關(guān)系。,62,,,,,,,,,,,,所以(x,y)和(y,x)成對的出現(xiàn)在R1∩R2中， R1∩R2是對稱關(guān)系,思考R1∪R2是對稱的嗎？

49、,例題４,設(shè) 為A上的反對稱關(guān)系，則 不一定是A上的反對稱關(guān)系。 例如 這里 R1,R2都是A上的反對稱關(guān)系，但　 　　　　R1∪R2 不是A上的反對稱關(guān)系，卻是對稱的。思考: R1∩R2 在A上是否是反對稱的? 　　　　　　　是反對稱的！,63,,,,,,,,,,,,,例5,

50、設(shè)R是集合A上的二元關(guān)系，如果R?R2，證明R是傳遞關(guān)系。證明 當(dāng)存在(a, b)∈R，(b, c) ∈R時，由復(fù)合關(guān)系的定義可知，必有(a,c)∈R2 ，而R?R2 ，所以(a, c) ∈R，由此證得R是傳遞關(guān)系。證畢。,64,,,,練習(xí),§4-3 關(guān)系的閉包運算,1.自反閉包、對稱閉包、傳遞閉包的定義定義： R是A上的二元關(guān)系，若A上二元關(guān)系 R′滿足（1）R′是自反的（對稱的，傳遞的）（2）R′? R（3）

51、對于任何自反的（對稱的，傳遞的）二元關(guān)系R〞如果 R〞? R，就有R〞? R′則稱R′為R的自反閉包（對稱閉包，傳遞閉包）。,65,,,,,,,,關(guān)系上的閉包運算,由上述定義可知，R的自反閉包（對稱閉包，傳遞閉包） R′：是含有R并且具有自反性質(zhì)（對稱性質(zhì)，傳遞性質(zhì)）的“最小”的二元關(guān)系。通常把二元關(guān)系R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R)。,66,,,,,,,,例：A={1,2,3}R={(1,1)

52、,(2,2)}R1={(1,1),(2,2),(3,2),(3,3)}R2={(1,1),(2,2),(3,3)}R3={(1,1),(2,2),(1,2),(3,2),(3,3)}哪一個關(guān)系是R的自反閉包？,包含R，并且自反，并且元素個數(shù)最少,關(guān)系的閉包運算分析,求R的自反閉包比較簡單，只需把所有　(a, a)? R 的有序?qū)ρa上即可。求R的對稱閉包也比較簡單，每當(dāng)(a, b)∈R，而(b, a) ? R 時，把有序偶

53、(b, a)添加到R上即得。,67,,,,,,,,,,,關(guān)系的閉包運算分析,求二元關(guān)系的傳遞閉包并不是一件容易的事情。例如：A = {a, b, c, d},R = {(a, b), (b, c), (c, d)}。易見:R不是傳遞關(guān)系，在R中有:　　(a, b) ∈R和(b, c) ∈R，但(a, c) ? R 　　(b, c) ∈R和(c, d) ∈R，但(b, d) ? R,68,,,,,,,,,,,如果把有序?qū)?a, c

54、)和(b, d)添加到R中去，使之?dāng)U充為R1，,所以R1仍然不是傳遞關(guān)系，也即R1不是R的傳遞閉包。,R1= {(a, b), (b, c), (c, d), (a, c), (b, d)},但是，由于(a, c)∈R1和(c, d)∈ R1,而(a, d) ? R1，,總結(jié)：求閉包的算法,設(shè)R為A上的關(guān)系，則有,69,,,證明（3）先證：,70,總結(jié)：求閉包的算法,根據(jù)數(shù)學(xué)歸納法：1)根據(jù)閉包的定義，R?t(R)，所以n=1時R1

55、?t(R)成立2) 首先假設(shè)當(dāng)n≥1時， Rn?t(R)成立，則再看看任意(x,y) ∈Rn+1時，(x,y)是否也屬于t(R)。因為： Rn+1 =Rn ·R，根據(jù)復(fù)合關(guān)系的定義，必存在(x,c) ∈Rn, (c,y) ∈R, 才能滿足復(fù)合關(guān)系。因此 又可以得到(x,c) ∈ t(R)， (c,y) ∈t(R), 根據(jù)傳遞閉包的定義，(x,y) ∈t(R). 根據(jù)包含的定義，所以Rn+1?t(R)3) 所以:,總

56、結(jié)：求閉包的算法,再證：,71,1) 假設(shè)任意(x,y) ∈ , (y,z) ∈必存在(x,y) ∈Rs，(y,z)∈Rt, 因此：(x,z) ∈Rs?Rt =Rs+t,所以(x,z) ∈所以對于關(guān)系 來說，它是傳遞的。包含R的全傳遞關(guān)系都包含了t(R)，所以兩個集合互相包含，只能說明兩者相等，所以,總結(jié)：求閉包的算法,72,可以證明，當(dāng)A為有限集：,求閉包的例子：,例1：設(shè)

57、A = {a, b, c, d}，A上的關(guān)系 R = {(a, b), (b, a), (b, c), (c, d)} 求r(R)、s(R)、t(R),73,,,例1（續(xù)）,74,,,,R = {(a, b), (b, a), (b, c), (c, d)},關(guān)系矩陣下 閉包的構(gòu)造方法,設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為M, Mr, Ms 和 Mt , 則

58、 Mr = M + E Ms = M + M T Mt = M + M2 + M3 + …E 是和 M 同階的單位矩陣, MT是 M 的轉(zhuǎn)置矩陣. 注意在上述等式中矩陣的元素相加時使用邏輯加.,75,76,例：A={a,b,c}, R={(a,b),(b,c),(c,a)}求r(R), S(R)和t(R),r(R)=M+E=,r(R)={(a,b),(b,c),(c,a),

59、(a,a),(b,b),(c,c)},77,例：A={a,b,c}, R={(a,b),(b,c),(c,a)}求r(R), S(R)和t(R) (續(xù)1),s(R)=M+MT=,s(R)={(a,b),(b,c),(c,a),(a,c),(b,a),(c,b)},78,例：A={a,b,c}, R={(a,b),(b,c),(c,a)}求r(R), S(R)和t(R) (續(xù)2),t(R)=M+M2+M3=,s(R)={(a,

60、b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}},M,M2,M3,關(guān)系圖下 閉包的構(gòu)造方法,79,設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系圖分別記為G, Gr, Gs, Gt , 則Gr, Gs, Gt 的頂點集與G 的頂點集相等. 除了G 的邊以外, 以下述方法添加新邊：,3.考察G的每個頂點 xi, 找從 xi 出發(fā)的每一條路徑，如果從 xi 到xj存在路徑，但沒有

61、邊，就加上這條邊. 當(dāng)檢查完所有的頂點后就得到圖Gt .,1.考察G的每個頂點, 如果沒有環(huán)就加上一個環(huán)，最終得到Gr .,2.考察G的每條邊, 如果有一條 xi 到 xj 的單向邊, i≠j, 則在G中加一條 xj 到 xi 的反方向邊，最終得到Gs.,實例,80,例1 設(shè)A={a,b,c,d}, R={,,,,}, R和 r(R), s(R), t(R)的關(guān)系圖如下圖所示.,R,r(R),s(R),t(R),練習(xí),求傳遞閉包的

62、算法,Warshall算法:（1）置新矩陣 是關(guān)系矩陣）（2）置 j = 1，i=1（3）對所有 i，如果 ，則對k = 1, 2, …, n ，置（4） j = j + 1（5）如果j ≤ n ，則轉(zhuǎn)到步驟（3），否則停止。,81,,,,例題：求傳遞閉包,設(shè)　 求R的傳遞閉包?！〗?利用Warshall算法，求解步驟如下?！∠葘懗鯮的關(guān)系矩

63、陣,82,,,例題：求傳遞閉包,,83,,,,,,,84,用程序?qū)崿F(xiàn)算法：,#include "stdafx.h"#include int main(int argc, char* argv[]){int R[5][5]={0,1,0,0,0, 0,0,1,0,0, 1,0,0,0,0, 0,0,0,0,1,

64、 0,0,0,1,0};int tR[5][5];for(int i=0;i<5;i++) //copy R to tR{ for(int j=0;j<5;j++)tR[i][j]=R[i][j];},85,for(int j=0;j<5;j++){for(int i=0;i<5;i++){if(tR[i

65、][j]==1){for(int k=0;k<5;k++)tR[i][k]=tR[i][k]||tR[j][k];}}// print for(int a=0;a<5;a++){for(int b=0;b<5;b++)cout<<tR[a][b]<<" ";cout<<en

66、dl;}cout<<endl;}},4-4 等價關(guān)系和相容關(guān)系,集合的覆蓋與劃分1.覆蓋給定非空集合S，有非空集合A={A1, A2, … Am}。若Ai?S，Ai≠空集(i=1,2,…m)且 則稱集合A為集合S的覆蓋。,86,等價關(guān)系,例如：S={a,b,c}A={{a,b},{a,c}}B={{a},{a,c},}C={{a},{a,c}}A、B是S的覆蓋C不是S的覆蓋,8

67、7,等價關(guān)系,2.劃分：給定非空集合S，有非空集合A={A1, A2, … Am}。若Ai?S，Ai≠空集(i=1,2,…m)且 ，還有Ai∩Aj=空集，則稱集合A為集合S的劃分。,88,等價關(guān)系,例如：S={a,b,c}A={{a,b},{a,c}}B={{a},{c},}C={{a},{b,c}}D={{a,b,c}},89,B、C、D是S的劃分。,A是S的覆蓋,但不是劃分,例題,例1 設(shè)A＝{a, b, c,

68、 d}, 給定π1,π2,π3,π4,π5,π6如下： π1= { {a, b, c}, nkrogew }， π2= { {a, b}, {c}, qngsu5h } π3= { {a}, {a, b, c, d} }, π4= { {a, b}, {c} } π5= { ?,{a, b}, {c, d} }, π6= { {a, {a}}, {b, c, d} } 則π1和π2 是A的劃分, 其他

69、都不是 A 的劃分. 為什么？,90,等價關(guān)系的定義與實例,91,定義 設(shè) R 為非空集合上的關(guān)系. 如果 R 是自反的、對稱的和傳遞的, 則稱 R 為 A 上的等價關(guān)系. 設(shè) R 是一個等價關(guān)系, 若(x,y)∈R, 稱 x 等價于y, 記做 x～y. 實例 設(shè) A={1,2,…,8}, 如下定義A上的關(guān)系 R： R = { (x,y) | x,y∈A∧x≡y(mod 3) }其中 x≡y(mod