離散數(shù)學(xué)第4章(屈)

1、1第4章 關(guān)系n4.1 關(guān)系的定義及其表示關(guān)系的定義及其表示n4.2 關(guān)系運(yùn)算關(guān)系運(yùn)算n4.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)n4.4 等價(jià)關(guān)系與偏序關(guān)系等價(jià)關(guān)系與偏序關(guān)系24.1 關(guān)系的定義及其表示n4.1.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積n4.1.2 二元關(guān)系的定義二元關(guān)系的定義n4.1.3 二元關(guān)系的表示二元關(guān)系的表示3定義定義4.1 由兩個(gè)元素，如由兩個(gè)元素，如x和和y，按照一定的順序，按照一定的順序組成的二元組稱為組成的二元組稱為有序?qū)τ行驅(qū)?，記作，記?實(shí)例：點(diǎn)的直角坐標(biāo)實(shí)例：點(diǎn)的直角坐標(biāo) (3, 4) 有序?qū)Φ男再|(zhì)有序?qū)Φ男再|(zhì) 有序性有序性 （當(dāng)（當(dāng)x y時(shí)）時(shí)） 與與相等的充分必要條

2、件是相等的充分必要條件是 = x=u y=v例例1 =，求，求 x, y. 解解 3y 4=2, x+5=y y=2, x= 3 有序?qū)?笛卡兒積定義定義4.2 設(shè)設(shè)A, B為集合，為集合，A與與B 的的笛卡兒積笛卡兒積記作記作A B， A B = | x A y B .例例2 A=0, 1, B=a, b, c A B=, B A =, A = , B = P(A) A = , P(A) B = 5笛卡兒積的性質(zhì)對(duì)于并或交運(yùn)算滿足分配律對(duì)于并或交運(yùn)算滿足分配律 A (B C)=(A B) (A C) (B C) A=(B A) (C A) A (B C)=(A B) (A C) (B C)

3、A=(B A) (C A) 若若A或或B中有一個(gè)為空集，則中有一個(gè)為空集，則A B就是空集就是空集. A=B= 不適合交換律不適合交換律 A B B A (A B, A, B)不適合結(jié)合律不適合結(jié)合律 (A B) C A (B C) (A, B, C)若若|A|=m, |B|=n, 則則 |A B|=mn 6有序 n 元組和 n 階笛卡爾積 定義定義4.3 (1) 由由 n 個(gè)元素個(gè)元素 x1, x2, , xn按照一定的順序排列構(gòu)成按照一定的順序排列構(gòu)成 有序有序 n 元組元組，記作，記作 (2) 設(shè)設(shè)A1, A2, , An為集合，稱為集合，稱 A1 A2 An= | xi Ai, i=1

4、,2, ,n 為為 n 階笛卡兒積階笛卡兒積. 實(shí)例實(shí)例 (1,1,0)為空間直角坐標(biāo)，為空間直角坐標(biāo)，(1,1,0) R R R7二元關(guān)系的定義定義定義4.4如果一個(gè)集合滿足以下條件之一：如果一個(gè)集合滿足以下條件之一：（1）集合非空）集合非空, 且它的元素都是有序?qū)η宜脑囟际怯行驅(qū)Γ?）集合是空集）集合是空集則稱該集合為一個(gè)則稱該集合為一個(gè)二元關(guān)系二元關(guān)系, 簡(jiǎn)稱為簡(jiǎn)稱為關(guān)系關(guān)系，記作，記作R.如如R, 可記作可記作 xRy；如果；如果 R, 則記作則記作x y實(shí)例：實(shí)例：R=, S=,a,b. R是二元關(guān)系是二元關(guān)系, 當(dāng)當(dāng)a, b不是有序?qū)r(shí)，不是有序?qū)r(shí)，S不是二元關(guān)系不是二元關(guān)系

5、根據(jù)上面的記法，可以寫根據(jù)上面的記法，可以寫1R2, aRb, a c等等. 8實(shí)例 例3 (1) R= | x,yN, x+y3 =, , , , , (2) C= | x,yR, x2+y2=1，其中R代表實(shí)數(shù)集合， C是直角坐標(biāo)平面上點(diǎn)的橫、縱坐標(biāo)之間的關(guān)系， C中的所有的點(diǎn)恰好構(gòu)成坐標(biāo)平面上的單位圓. (3) R= | x,y,zR, x+2y+z=3， R代表了空間直角坐標(biāo)系中的一個(gè)平面. 95元關(guān)系的實(shí)例數(shù)據(jù)庫實(shí)體模型員工號(hào)員工號(hào)姓名姓名年齡年齡性別性別工資工資301302303304 張張 林林王曉云王曉云李鵬宇李鵬宇趙趙 輝輝 50434721 男男女女男男男男 1600125

6、01500900 5元組：元組：，10從A到B的關(guān)系與A上的關(guān)系nm2定義定義4.5 設(shè)設(shè)A,B為集合為集合, AB的任何子集所定義的二元關(guān)系叫做的任何子集所定義的二元關(guān)系叫做從從 A 到到 B 的二元關(guān)系的二元關(guān)系, 當(dāng)當(dāng) A=B 時(shí)則叫做時(shí)則叫做 A上的二元關(guān)系上的二元關(guān)系.例例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=, 從從A到到B的關(guān)系的關(guān)系: R1, R2, R3, R4, A上的關(guān)系上的關(guān)系R3和和R4. 計(jì)數(shù)：計(jì)數(shù)：|A|=n, |B|=m, |AB|=nm, AB 的子集有的子集有 個(gè)個(gè). 所以從所以從A到到B有有 個(gè)不同的二元關(guān)系個(gè)不同的二

7、元關(guān)系. |A|=n, A上有上有 不同的二元關(guān)系不同的二元關(guān)系. 例如例如 |A|=3, 則則 A上有上有512個(gè)不同的二元關(guān)系個(gè)不同的二元關(guān)系. 22nnm211A上重要關(guān)系的實(shí)例設(shè)設(shè)A為任意集合，為任意集合，是是A上的關(guān)系，稱為上的關(guān)系，稱為空關(guān)系空關(guān)系定義定義 4.6 EA, IA分別稱為分別稱為全域關(guān)系全域關(guān)系與與恒等關(guān)系恒等關(guān)系，其中，其中 EA= | xA yA=AA IA= | xA例如例如, A=1,2, 則則 EA=, IA=,12A上重要關(guān)系的實(shí)例（續(xù)）小于等于關(guān)系小于等于關(guān)系LA, 整除關(guān)系整除關(guān)系DA, 包含關(guān)系包含關(guān)系R 定義如下：定義如下：定義定義4.7 LA=|

8、 x,yAxy, 這里這里A R，R為實(shí)數(shù)集合為實(shí)數(shù)集合 DB=| x,yBx整除整除y, B Z*, Z*為非為非0整數(shù)集整數(shù)集 R =| x,yAx y, 這里這里A是集合族是集合族.例如例如 A=1,2,3, B=a,b, 則則 LA=, DA=, A=P(B)=,a,b,a,b, 則則A上的包含關(guān)系是上的包含關(guān)系是 R =, ,類似的還可以定義類似的還可以定義大于等于關(guān)系大于等于關(guān)系, 小于關(guān)系小于關(guān)系, 大于關(guān)系大于關(guān)系, 真真包含關(guān)系包含關(guān)系等等等等. 13矩陣的定義定義定義 由由mn個(gè)數(shù)個(gè)數(shù)aij(i(i=1,2,m, j=1,2,n)=1,2,m, j=1,2,n)排成的排成的

9、一個(gè)一個(gè)m行行n列的矩形表，稱為列的矩形表，稱為mn矩陣。記為矩陣。記為mnm2m12n22211n1211aaaaaaaaa14定義定義 矩陣的乘法msm2m12s22211s1211smijaaaaaaaaa)a (Asns2s12n22211n1211nsijbbbbbbbbb)b(Bmnm2m12n22211n1211nmijccccccccc)c (AB，其中，skbabababac1kjiksjis2ji21ji1ij(i=1,2,(i=1,2,m, j=1,2,m, j=1,2,n),n) 15矩陣的乘法64533134037160513230017263503743101216

10、關(guān)系的表示表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖 定義定義4.8 關(guān)系矩陣關(guān)系矩陣 若若A=x1, x2, , xm，B=y1, y2, , yn，R是從是從A到到B的關(guān)系，的關(guān)系，R的關(guān)系矩陣是布爾矩陣的關(guān)系矩陣是布爾矩陣MR = rij m n, 其中其中 rij = 1 R. 定義定義4.9 關(guān)系圖關(guān)系圖 若若A= x1, x2, , xm，R是從是從A上的關(guān)系，上的關(guān)系，R的關(guān)系圖是的關(guān)系圖是GR=, 其中其中A為結(jié)點(diǎn)集，為結(jié)點(diǎn)集，R為邊集為邊集.如果如果屬于關(guān)系屬于關(guān)系R，在圖中就有一條從，在圖中就有一條從 xi 到到 xj 的有向邊

11、的有向邊. 注意：設(shè)注意：設(shè)A, B為有窮集為有窮集關(guān)系矩陣適合于表示從關(guān)系矩陣適合于表示從A到到B 的關(guān)系或者的關(guān)系或者A上的關(guān)系上的關(guān)系關(guān)系圖適合于表示關(guān)系圖適合于表示A上的關(guān)系上的關(guān)系 17實(shí)例例例5 A=a, b, c, d, R=,R的關(guān)系矩陣的關(guān)系矩陣 MR 和關(guān)系圖和關(guān)系圖 GR 如下：如下：001000000001011118n4.2.1 關(guān)系的基本運(yùn)算關(guān)系的基本運(yùn)算n定義域、值域、域、逆、合成定義域、值域、域、逆、合成n基本運(yùn)算的性質(zhì)基本運(yùn)算的性質(zhì)n4.2.2 關(guān)系的冪運(yùn)算關(guān)系的冪運(yùn)算n冪運(yùn)算的定義冪運(yùn)算的定義n冪運(yùn)算的方法冪運(yùn)算的方法n冪運(yùn)算的性質(zhì)冪運(yùn)算的性質(zhì)4.2 關(guān)系運(yùn)

12、算19關(guān)系的基本運(yùn)算定義定義4.10 定義域定義域、值域值域 和和 域域 domR = x | y ( R) ranR = y | x ( R) fldR = domR ranR 例例1 R=, 則則 domR = ranR = fldR = a, c, a, d, b, d a, c, a, d b, d, d20關(guān)系的基本運(yùn)算（續(xù)）定義定義4.11 R 的的逆逆 R 1 = | R定義定義4.12 R與與S的的合成合成 R S = | y ( R S) 例例2 R=, , , S=, , , , R 1 = R S = S R =, , , , , , , 21合成運(yùn)算的圖示方法 利用圖示

13、（不是關(guān)系圖）方法求合成利用圖示（不是關(guān)系圖）方法求合成 R S =, , S R =, , , 22 ）（jkijnjiksrc1用矩陣表示兩個(gè)關(guān)系的復(fù)合23100000100010RM00010000011000000100SM000101000010000 SRCMM1)()()()(451435132512151115srsrsrsrc例題24基本運(yùn)算的性質(zhì) 定理定理4.1 設(shè)設(shè)F是任意的關(guān)系是任意的關(guān)系, 則則(1) (F 1) 1=F(2) domF 1=ranF, ranF 1=domF證證 (1) 任取任取, 由逆的定義有由逆的定義有 (F 1) 1 F 1 F所以有所以有 (

14、F 1) 1=F(2) 任取任取x, xdomF 1 y (F 1) y (F) xranF 所以有所以有domF 1= ranF. 同理可證同理可證 ranF 1 = domF.25定理定理4.2 設(shè)設(shè)F, G, H是任意的關(guān)系是任意的關(guān)系, 則則 (1) (F G) H=F (G H) (2) (F G) 1= G 1 F 1 證證 (1) 任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)基本運(yùn)算的性質(zhì)（續(xù)） 26(2) 任取任取, (F G)

15、1 F G t (F(t, x)G) t (G 1(t, y)F 1) G 1 F 1所以所以 (F G) 1 = G 1 F 1 基本運(yùn)算的性質(zhì)（續(xù)） 27定理定理4.3 設(shè)設(shè) R 為為 A上的關(guān)系上的關(guān)系, 則則 R IA= IA R = R 證明證明任取任取 R IA t (RIA) t (Rt=yyA) R從而有從而有R IA=R. 同理可證同理可證 IA R=R. 基本運(yùn)算的性質(zhì)（續(xù)） 28A上關(guān)系的冪運(yùn)算定義定義定義4.13 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, n為自然數(shù)為自然數(shù), 則則 R 的的 n次冪次冪是是 (1) R0 = | xA = IA (2) Rn+1 = Rn R 注

16、意：注意： 對(duì)于對(duì)于A上的任何關(guān)系上的任何關(guān)系R1和和R2都有都有 R10 = R20 = IA 對(duì)于對(duì)于A上的任何關(guān)系上的任何關(guān)系 R 都有都有 R1 = R 29冪運(yùn)算的方法對(duì)于集合表示的關(guān)系對(duì)于集合表示的關(guān)系R，計(jì)算，計(jì)算Rn 就是就是 n 個(gè)個(gè) R 合成合成 . 矩陣表示的關(guān)系就是矩陣相乘矩陣表示的關(guān)系就是矩陣相乘, 其中相加采用邏輯加其中相加采用邏輯加. 例例3 設(shè)設(shè)A = a, b, c, d, R = , 求求R的各次冪的各次冪, 分別用矩陣和關(guān)系圖表示分別用矩陣和關(guān)系圖表示.解解 R與與R2的關(guān)系矩陣分別為的關(guān)系矩陣分別為 0000100001010010M 000000001

17、0100101000010000101001000001000010100102M30同理同理R3和和R4的矩陣是：的矩陣是：因此因此M4 = M2, 即即R4 = R2. 因此可以得到因此可以得到R2 = R4 = R6 = , R3 = R5 = R7 = 而而R0 = IA的關(guān)系矩陣的關(guān)系矩陣 0000000010100101,000000000101101043MM 10000100001000010M冪運(yùn)算的方法（續(xù)）31用關(guān)系圖的方法得到用關(guān)系圖的方法得到R0, R1, R2, R3,的關(guān)系圖如下圖所示的關(guān)系圖如下圖所示冪運(yùn)算的方法（續(xù)）32冪運(yùn)算的性質(zhì)定理定理4.4 設(shè)設(shè) A 為

18、為 n 元集元集, R是是A上的關(guān)系上的關(guān)系, 則存在自然數(shù)則存在自然數(shù) s 和和 t, 使得使得 Rs = Rt.證證 R 為為A上的關(guān)系上的關(guān)系, 由于由于|A| = n, A上的不同關(guān)系只有上的不同關(guān)系只有 個(gè)個(gè). 當(dāng)列出當(dāng)列出 R 的各次冪的各次冪 R0, R1, R2, , , , 必存在自然數(shù)必存在自然數(shù) s 和和 t 使得使得 Rs = Rt.22n33定理定理4.5 設(shè)設(shè) R 是是 A 上的關(guān)系上的關(guān)系, m, nN, 則則 (1) Rm Rn = Rm+n (2) (Rm)n = Rmn 證證 用歸納法用歸納法 (1) 對(duì)于任意給定的對(duì)于任意給定的 mN, 施歸納于施歸納于

19、n.若若n=0, 則有則有 Rm R0 = Rm IA= Rm = Rm+0 假設(shè)假設(shè) Rm Rn = Rm+n, 則有則有Rm Rn+1 = Rm (Rn R) = (Rm Rn) R = Rm+n+1 , 所以對(duì)一切所以對(duì)一切 m, nN 有有 Rm Rn = Rm+n. 冪運(yùn)算的性質(zhì)（續(xù)）34(2) 對(duì)于任意給定的對(duì)于任意給定的 mN, 施歸納于施歸納于 n. 若若 n = 0, 則有則有 (Rm)0 = IA = R0 = Rm0 假設(shè)假設(shè) (Rm)n = Rmn, 則有則有(Rm)n+1 = (Rm)n Rm = (Rmn) Rm = Rmn+m = Rm(n+1) 所以對(duì)一切所以對(duì)

20、一切 m, nN 有有 (Rm)n = Rmn. 冪運(yùn)算的性質(zhì)（續(xù)）35定理定理4.6 設(shè)設(shè)R 是是A上的關(guān)系上的關(guān)系, 若存在自然數(shù)若存在自然數(shù) s, t (st) 使得使得 Rs = Rt, 則則 (1) 對(duì)任何對(duì)任何 kN 有有 Rs+k = Rt+k (2) 對(duì)任何對(duì)任何 k, iN 有有Rs+kp+i = Rs+i, 其中其中p = t s (3) 令令S=R0,R1, , Rt 1, 則對(duì)于任意的則對(duì)于任意的 qN有有 RqS證明證明 (1) Rs+k = Rs Rk = Rt Rk = Rt+k （2）對(duì)）對(duì) k 歸納歸納. 若若k=0, 則有則有 Rs+0p+i = Rs+i假

21、設(shè)假設(shè) Rs+kp+i = Rs+i, 其中其中p = t s, 則則Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+i Rp = Rs+i Rp = Rs+p+i = Rs+t s+i = Rt+i = Rs+i 由歸納法命題得證由歸納法命題得證.冪運(yùn)算的性質(zhì)（續(xù)）36(3) 任取任取 qN, 若若qt, 顯然有顯然有 RqS. 若若 qt, 則存在自然數(shù)則存在自然數(shù) k 和和 i 使得使得 q = s+kp+i，其中，其中0ip 1. 于是于是Rq = Rs+kp+i = Rs+i 而而 s+i s+p 1 = s+t s 1 = t 1 這就證明了這就證明了 RqS.冪運(yùn)

22、算的性質(zhì)（續(xù)）374.3 關(guān)系的性質(zhì)n4.3.1關(guān)系性質(zhì)的定義和判別關(guān)系性質(zhì)的定義和判別n自反性與反自反性自反性與反自反性n對(duì)稱性與反對(duì)稱性對(duì)稱性與反對(duì)稱性n傳遞性傳遞性n4.3.2 關(guān)系的閉包關(guān)系的閉包n閉包定義閉包定義n閉包計(jì)算閉包計(jì)算n Warshall算法算法 38自反性與反自反性定義定義4.14 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1) 若若 x(xA R), 則稱則稱R在在A上是上是自反自反的的. (2) 若若 x(xA R), 則稱則稱R在在A上是上是反自反反自反的的.自反：自反：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA, 小于等于關(guān)系小于等于關(guān)系LA, 整除關(guān)系整除

23、關(guān)系DA反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系.R2自反自反, R3 反自反反自反, R1既不自反也不反自反既不自反也不反自反.例例1 A = a, b, c, R1, R2, R3 是是 A上的關(guān)系上的關(guān)系, 其中其中 R1 = , R2 = , R3 = 39對(duì)稱性與反對(duì)稱性例例2 設(shè)設(shè)Aa,b,c, R1, R2, R3和和R4都是都是A上的關(guān)系上的關(guān)系, 其中其中 R1,， R2, R3,， R4,定義定義4.15 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1) 若若 x y(x,yARR), 則稱則稱R為為A上上 對(duì)稱對(duì)稱的關(guān)系的關(guān)系.(

24、2) 若若 x y(x,yARRx=y), 則稱則稱R 為為A上的上的反對(duì)稱反對(duì)稱關(guān)系關(guān)系.實(shí)例實(shí)例 對(duì)稱：對(duì)稱：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA和空關(guān)系和空關(guān)系 反對(duì)稱：恒等關(guān)系反對(duì)稱：恒等關(guān)系IA，空關(guān)系是空關(guān)系是A上的反對(duì)稱關(guān)系上的反對(duì)稱關(guān)系R1 對(duì)稱、反對(duì)稱對(duì)稱、反對(duì)稱. R2 對(duì)稱對(duì)稱. R3 反對(duì)稱反對(duì)稱. R4 不對(duì)稱、也不反對(duì)稱不對(duì)稱、也不反對(duì)稱40傳遞性 例例3 設(shè)設(shè)Aa, b, c, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中 R1, R2, R3定義定義4.16 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 若若 x y z(x,y,zARRR),則稱

25、則稱R是是A上的上的傳遞傳遞關(guān)系關(guān)系.實(shí)例：實(shí)例：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)系R1 和和 R3 是是A上的傳遞關(guān)系上的傳遞關(guān)系, R2不是不是A上的傳遞關(guān)系上的傳遞關(guān)系.41關(guān)系性質(zhì)的充要條件設(shè)設(shè) R 為為 A 上的關(guān)系上的關(guān)系, 則則 (1) R 在在 A 上自反當(dāng)且僅當(dāng)上自反當(dāng)且僅當(dāng) IA R (2) R 在在 A 上反自反當(dāng)且僅當(dāng)上反自反當(dāng)且僅當(dāng) RIA= (3) R 在在 A 上對(duì)稱當(dāng)且僅當(dāng)上對(duì)稱當(dāng)且僅當(dāng) R=R 1 (4)

26、R 在在 A 上反對(duì)稱當(dāng)且僅當(dāng)上反對(duì)稱當(dāng)且僅當(dāng) RR 1 IA (5) R 在在 A 上傳遞當(dāng)且僅當(dāng)上傳遞當(dāng)且僅當(dāng) R R R 42自反性證明證明模式證明模式 證明證明 R 在在 A 上自反上自反 任取任取 x, x A . . R 前提前提 推理過程推理過程 結(jié)論結(jié)論例例4 證明若證明若 IA R ，則則 R 在在 A 上自反上自反. 證證 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的上是自反的.43對(duì)稱性證明證明模式證明模式 證明證明 R 在在 A 上對(duì)稱上對(duì)稱 任取任取 R . . R 前提前提 推理過程推理過程 結(jié)論結(jié)論例例5 證明若證明若 R=R 1 , 則則

27、R 在在A上對(duì)稱上對(duì)稱. 證證 任取任取 R R 1 R 因此因此 R 在在 A 上是對(duì)稱的上是對(duì)稱的.44反對(duì)稱性證明證明模式證明模式 證明證明 R 在在 A 上反對(duì)稱上反對(duì)稱 任取任取 R R . x=y 前提前提 推理過程推理過程 結(jié)論結(jié)論例例6 證明若證明若 RR 1 IA , 則則 R 在在 A 上反對(duì)稱上反對(duì)稱. 證證 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反對(duì)稱的上是反對(duì)稱的.45傳遞性證明證明模式證明模式 證明證明 R 在在 A上傳遞上傳遞 任取任取， R R . R 前提前提 推理過程推理過程 結(jié)論結(jié)論例例7 證明若證明若 R R

28、R , 則則 R 在在 A 上傳遞上傳遞. 證證 任取任取， R R R R R 因此因此 R 在在 A 上是傳遞的上是傳遞的.46關(guān)系性質(zhì)判別自反性自反性反自反性反自反性對(duì)稱性對(duì)稱性反對(duì)稱性反對(duì)稱性傳遞性傳遞性表達(dá)式表達(dá)式IA RRIA=R=R 1 RR 1 IA R R R關(guān)系關(guān)系矩陣矩陣主對(duì)角主對(duì)角線元素線元素全是全是1主對(duì)角線主對(duì)角線元素全是元素全是0矩陣是對(duì)稱矩陣是對(duì)稱矩陣矩陣若若rij1, 且且ij, 則則rji0對(duì)對(duì)M2中中1所所在位置在位置,M中相應(yīng)位置中相應(yīng)位置都是都是1關(guān)系圖關(guān)系圖每個(gè)頂每個(gè)頂點(diǎn)都有點(diǎn)都有環(huán)環(huán)每個(gè)頂點(diǎn)每個(gè)頂點(diǎn)都沒有環(huán)都沒有環(huán)如果兩個(gè)頂如果兩個(gè)頂點(diǎn)之間有邊點(diǎn)之

29、間有邊, 一定是一對(duì)一定是一對(duì)方向相反的方向相反的邊邊(無單邊無單邊)如果兩點(diǎn)之如果兩點(diǎn)之間有邊間有邊, 一一定定是一條有向是一條有向邊邊(無雙向邊無雙向邊)如果頂點(diǎn)如果頂點(diǎn)xi到到xj有邊有邊, xj到到xk有邊有邊,則則從從xi到到xk也也有邊有邊 47實(shí)例例例8 判斷下圖中關(guān)系的性質(zhì)判斷下圖中關(guān)系的性質(zhì), 并說明理由并說明理由(3) 自反，不是反自反；反對(duì)稱，不是對(duì)稱；不傳遞自反，不是反自反；反對(duì)稱，不是對(duì)稱；不傳遞. (1)(2)(3)(1) 不是自反也不是反自反；對(duì)稱不是自反也不是反自反；對(duì)稱, 不是反對(duì)稱；不傳遞不是反對(duì)稱；不傳遞.(2) 反自反反自反, 不是自反；反對(duì)稱不是自反；

30、反對(duì)稱, 不是對(duì)稱；傳遞不是對(duì)稱；傳遞.48運(yùn)算與性質(zhì)的關(guān)系自反性自反性反自反性反自反性對(duì)稱性對(duì)稱性反對(duì)稱性反對(duì)稱性傳遞性傳遞性R1 1 R1R2 R1R2 R1 R2 R1 R2 49閉包定義定義定義4.17 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, R 的的自反自反 (對(duì)稱對(duì)稱或或傳遞傳遞) 閉包閉包 是是A上的關(guān)系上的關(guān)系R , 使得使得 R 滿足以下條件：滿足以下條件： (1) R 是自反的（對(duì)稱的或傳遞的）是自反的（對(duì)稱的或傳遞的） (2) R R (3) 對(duì)對(duì)A上任何包含上任何包含R 的自反（對(duì)稱或傳遞）關(guān)系的自反（對(duì)稱或傳遞）關(guān)系R 有有 R R . 一般將一般將 R 的自

31、反閉包記作的自反閉包記作 r(R), 對(duì)稱閉包記作對(duì)稱閉包記作 s(R), 傳遞傳遞閉包記作閉包記作 t(R). 50閉包的構(gòu)造方法集合表示集合表示定理定理4.7 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則有則有 (1) r(R)=RR0 (2) s(R)=RR 1 (3) t(R)=RR2R3說明：說明：對(duì)于有窮集合對(duì)于有窮集合A (|A|=n) 上的關(guān)系上的關(guān)系, (3)中的并最多不超過中的并最多不超過Rn. 若若R 是自反的，則是自反的，則 r(R)=R; 若若 R 是對(duì)稱的，則是對(duì)稱的，則 s(R)=R;若若R 是傳遞的，則是傳遞的，則 t(R)=R. 51定理4.7的證明只證只證 (1) 和

32、和 (3) 證證 r(R)=RR0 只需證明只需證明RR0 滿足閉包定義滿足閉包定義. RR0包含了包含了R 由由IA RR0可知可知 RR0 在在 A上是自反的上是自反的. 下面證明下面證明RR0是包含是包含R 的最小的自反關(guān)系的最小的自反關(guān)系. 假設(shè)假設(shè)R 是包含是包含R 的自反關(guān)系，那么的自反關(guān)系，那么IA R , R R ，因此有因此有 RR0=IA R R 52任取任取和和 RR2R3. RR2R3. RR2R3.于是，由于是，由RR2R3.的傳遞性得的傳遞性得 t(R) RR2R3 對(duì)對(duì)n 進(jìn)行歸納證明進(jìn)行歸納證明 Rn t(R).n=1時(shí)顯然為真時(shí)顯然為真. 假設(shè)假設(shè)n=k時(shí)為真

33、，那么對(duì)于任意時(shí)為真，那么對(duì)于任意 Rk+1 Rk R t ( Rk R) t ( t(R) t(R) t(R) （t(R)傳遞）傳遞） 于是，于是， RR2R3 t(R) 定理4.7的證明（續(xù)）53矩陣表示矩陣表示設(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 同階的單位矩陣同階的單位矩陣, M 是是 M 的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣. 注意：在上述等式中矩陣的元素相加時(shí)使用邏輯加注意：在上述等式中矩陣的元素相加時(shí)使用邏輯加

34、. 閉包的構(gòu)造方法（續(xù)）54圖表示圖表示設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系圖分別記為的關(guān)系圖分別記為G, Gr, Gs, Gt , 則則Gr, Gs, Gt 的頂點(diǎn)集與的頂點(diǎn)集與G 的頂點(diǎn)集相等的頂點(diǎn)集相等. 除了除了G 的邊以的邊以外外, 以下述方法添加新的邊：以下述方法添加新的邊： 考察考察G 的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn), 如果沒有環(huán)就加上一個(gè)環(huán)如果沒有環(huán)就加上一個(gè)環(huán). 最終得到最終得到的是的是Gr. 考察考察G 的每一條邊的每一條邊, 如果有一條如果有一條 xi 到到 xj 的單向邊的單向邊, ij, 則則在在G中加一條中加一條 xj 到到 xi 的反方向邊的反方向邊.

35、最終得到最終得到Gs. 考察考察G 的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn) xi, 找從找從 xi 出發(fā)的每一條路徑，如果出發(fā)的每一條路徑，如果從從 xi 到路徑中的任何結(jié)點(diǎn)到路徑中的任何結(jié)點(diǎn) xj 沒有邊，就加上這條邊沒有邊，就加上這條邊. 當(dāng)當(dāng)檢查完所有的頂點(diǎn)后就得到圖檢查完所有的頂點(diǎn)后就得到圖Gt . 閉包的構(gòu)造方法（續(xù)）55實(shí)例例例1 設(shè)設(shè)A=a,b,c,d, R=,R和和 r(R), s(R), t(R)的關(guān)系圖如下圖所示的關(guān)系圖如下圖所示. Rr(R)s(R)t(R)56傳遞閉包的計(jì)算Warshall算法算法思路：算法思路：考慮考慮 n+1個(gè)矩陣的序列個(gè)矩陣的序列M0, M1, , Mn , 將矩陣

36、將矩陣 Mk 的的 i 行行 j 列列的元素記作的元素記作Mki,j. 對(duì)于對(duì)于k=0,1,n, Mki,j=1當(dāng)且僅當(dāng)在當(dāng)且僅當(dāng)在R 的關(guān)系圖中存在一條從的關(guān)系圖中存在一條從 xi 到到 xj 的路徑，并且這條路徑的路徑，并且這條路徑除端點(diǎn)外中間只經(jīng)過除端點(diǎn)外中間只經(jīng)過x1, x2, , xk中的頂點(diǎn)中的頂點(diǎn). 不難證明不難證明M0就是就是R 的關(guān)系矩陣，而的關(guān)系矩陣，而 Mn 就對(duì)應(yīng)了就對(duì)應(yīng)了R 的傳遞閉包的傳遞閉包. Warshall算法算法：從從M0開始，順序計(jì)算開始，順序計(jì)算 M1, M2, , 直到直到 Mn 為止為止. 57Warshall算法的依據(jù)從從 Mk i, j 計(jì)算計(jì)算

37、 Mk+1i, j: i, j V. 頂點(diǎn)集頂點(diǎn)集 V1=1,2, , k, V2=k+2, ,n,V=V1 k+1 V2，Mk+1i,j=1 存在從存在從i 到到 j 中間只經(jīng)過中間只經(jīng)過V1 k+1中點(diǎn)的路徑中點(diǎn)的路徑這些路徑分為兩類：這些路徑分為兩類：第第1類：只經(jīng)過類：只經(jīng)過 V1中點(diǎn)中點(diǎn)第第2類：經(jīng)過類：經(jīng)過 k+1點(diǎn)點(diǎn)存在第存在第1類路徑：類路徑：Mki,j=1存在第存在第2類路徑：類路徑： Mki,k+1=1 Mkk+1,j=158Warshall算法及其效率算法算法4.1 Warshall算法算法 輸入：輸入：M （R 的關(guān)系矩陣）的關(guān)系矩陣）輸出：輸出：Mt （t(R)的關(guān)系

38、矩陣）的關(guān)系矩陣） 1. MtM2. for k1 to n do3. for i1 to n do4. for j1 to n do5. Mti, j Mti, j + Mti, k Mtk, j 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 T(n)=O(n3)594.4 等價(jià)關(guān)系與偏序關(guān)系n4.4.1 等價(jià)關(guān)系等價(jià)關(guān)系n4.4.2 等價(jià)類和商集等價(jià)類和商集n4.4.3 集合的劃分集合的劃分n4.4.4 偏序關(guān)系偏序關(guān)系n4.4.5 偏序集與哈斯圖偏序集與哈斯圖60等價(jià)關(guān)系的定義與實(shí)例定義定義4.18 設(shè)設(shè)R為非空集合上的關(guān)系為非空集合上的關(guān)系. 如果如果R是自反的、對(duì)稱的是自反的、對(duì)稱的和傳遞的和傳遞的, 則稱

39、則稱R為為A上的上的等價(jià)關(guān)系等價(jià)關(guān)系. 設(shè)設(shè) R 是一個(gè)等價(jià)關(guān)系是一個(gè)等價(jià)關(guān)系, 若若R, 稱稱 x等價(jià)于等價(jià)于y, 記做記做xy. 例例1 設(shè)設(shè) A=1, 2, , 8, 如下定義如下定義 A上的關(guān)系上的關(guān)系R： R=| x,yA xy (mod 3)其中其中 xy (mod 3) 叫做叫做 x與與y 模模3相等相等, 即即 x 除以除以3的余數(shù)與的余數(shù)與 y 除以除以3的余數(shù)相等的余數(shù)相等. 不難驗(yàn)證不難驗(yàn)證R為為A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 因?yàn)橐驗(yàn)?xA, 有有xx(mod 3) x,yA, 若若xy(mod 3), 則有則有yx(mod 3) x,y,zA, 若若xy(mod 3),

40、 yz(mod 3), 則有則有 xz(mod 3)61模3等價(jià)關(guān)系的關(guān)系圖設(shè)設(shè) A=1, 2, , 8, R= | x,yA xy (mod 3) R 的關(guān)系圖如下：的關(guān)系圖如下：62等價(jià)類定義定義4.19 設(shè)設(shè)R為非空集合為非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, xA，令，令 xR = y | yA xRy 稱稱 xR 為為x關(guān)于關(guān)于R 的的等價(jià)類等價(jià)類, 簡(jiǎn)稱為簡(jiǎn)稱為 x 的等價(jià)類的等價(jià)類, 簡(jiǎn)記為簡(jiǎn)記為x. 實(shí)例實(shí)例 A= 1, 2, , 8 上模上模 3 等價(jià)關(guān)系的等價(jià)類：等價(jià)關(guān)系的等價(jià)類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,663等價(jià)類的性質(zhì)AxAx 定理定

41、理4.8 設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 則則 (1) xA, x 是是A的非空子集的非空子集. (2) x, yA, 如果如果 xRy, 則則 x=y. (3) x, yA, 如果如果 x y, 則則 x與與y不交不交. (4) ，即所有等價(jià)類的并集就是即所有等價(jià)類的并集就是A. 64性質(zhì)的證明(1)由等價(jià)類定義可知由等價(jià)類定義可知, xA有有x A. 由自反性有由自反性有xRx，因此因此xx, 即即x非空非空. (2)任取任取z, 則有則有zx R RR R R R 從而證明了從而證明了zy. 綜上所述必有綜上所述必有x y. 同理可證同理可證y x. 這就得到了這

42、就得到了x=y.(3) 假設(shè)假設(shè)xy, 則存在則存在zxy, 從而有從而有 zx zy, 即即R R 成立成立. 根據(jù)根據(jù)R 的對(duì)稱性和傳遞性必有的對(duì)稱性和傳遞性必有R, 與與x y矛盾矛盾65性質(zhì)的證明（續(xù)）(4) 先證先證 . 任取任取y, y x (xA yx) yx x A yA 從而有從而有 .再證再證A . 任取任取y, yA yy yA y從而有從而有A 成立成立. 綜上所述得綜上所述得AxAx Axx AxAxAxAx Axx Axx Axx 66商集定義定義4.20 設(shè)設(shè)R 為非空集合為非空集合A 上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 以以R 的所有的所有等等價(jià)類作為元素的集合稱為價(jià)類

43、作為元素的集合稱為A關(guān)于關(guān)于R 的的商集商集, 記做記做 A/R, A/R = xR | xA 例例2令令A(yù)=1, 2, , 8，A關(guān)于模關(guān)于模 3 等價(jià)關(guān)系等價(jià)關(guān)系R 的商集為的商集為 A/R = 1, 4,7, 2, 5, 8, 3, 6 A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 67集合的劃分定義定義4.21 設(shè)設(shè)A為非空集合為非空集合, 若若A的子集族的子集族 ( P(A) 滿滿足下面條件：足下面條件： (1) (2) x y (x,y xyxy=) (3) =A 則稱則稱 是是A的一個(gè)的一個(gè)劃分劃

44、分, 稱稱 中的元素為中的元素為A的的劃分塊劃分塊.例例3 設(shè)設(shè)Aa, b, c, d, 給定給定 1, 2, 3, 4, 5, 6如下：如下： 1=a, b, c,d， 2=a, b,c,d 3=a,a, b, c, d， 4=a, b,c 5=,a, b,c, d， 6=a,a,b, c, d 則則 1和和 2是是A的劃分的劃分, 其他都不是其他都不是A的劃分的劃分. 68等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)商集商集 A/R 就是就是A 的一個(gè)劃分的一個(gè)劃分 不同的商集對(duì)應(yīng)于不同的劃分不同的商集對(duì)應(yīng)于不同的劃分 任給任給A 的一個(gè)劃分的一個(gè)劃分 , 如下定義如下定義A 上的關(guān)系上的關(guān)系 R：R = |

45、 x, yA x 與與 y 在在 的同一劃分塊中的同一劃分塊中 則則R 為為A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 且該等價(jià)關(guān)系確定的商集就是且該等價(jià)關(guān)系確定的商集就是 . 例例4 給出給出A1,2,3上所有的等價(jià)關(guān)系上所有的等價(jià)關(guān)系求解思路：先做出求解思路：先做出A的所有劃分的所有劃分, 然后根據(jù)劃分寫出然后根據(jù)劃分寫出 對(duì)應(yīng)的等價(jià)關(guān)系對(duì)應(yīng)的等價(jià)關(guān)系. 69例 4 1, 2和和 3分別對(duì)應(yīng)于等價(jià)關(guān)系分別對(duì)應(yīng)于等價(jià)關(guān)系 R1, R2和和R3. 其中其中 R1=,IA R2=,IA R3=,IAA上的等價(jià)關(guān)系與劃上的等價(jià)關(guān)系與劃分之間的對(duì)應(yīng)：分之間的對(duì)應(yīng)： 4對(duì)應(yīng)于全域關(guān)系對(duì)應(yīng)于全域關(guān)系EA 5對(duì)應(yīng)于恒等

46、關(guān)系對(duì)應(yīng)于恒等關(guān)系IA70實(shí)例根據(jù)有序?qū)Ω鶕?jù)有序?qū)Φ牡?x+y=2,3,4,5,6,7,8 將將A A劃分劃分. (A A)/R=, , , , , , , , , , , , , , 例例5 設(shè)設(shè)A=1,2,3,4，在，在A A上定義二元關(guān)系上定義二元關(guān)系 R： , R x+y = u+v，求求R 導(dǎo)出的劃分導(dǎo)出的劃分. 解解 A A=, , , , , , , , , , , , , , 71偏序關(guān)系定義定義4.22 非空集合非空集合A上的自反、反對(duì)稱和傳遞的關(guān)系，上的自反、反對(duì)稱和傳遞的關(guān)系，稱為稱為A上的上的偏序關(guān)系偏序關(guān)系，記作，記作 . 設(shè)設(shè) 為偏序關(guān)系為偏序關(guān)系, 如果如果 ,

47、則記作則記作 x y, 讀作讀作 x“小于或等于小于或等于”y. 實(shí)例實(shí)例 集合集合A上的恒等關(guān)系上的恒等關(guān)系 IA 是是A上的偏序關(guān)系上的偏序關(guān)系. 小于或等于關(guān)系小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)集合整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系上的偏序關(guān)系. 72相關(guān)概念定義定義4.23 x與與y可比可比 設(shè)設(shè)R為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, x, y A, x與與y 可比可比 x y y x.結(jié)論：結(jié)論： x, y A，下述幾種情況發(fā)生其一且僅發(fā)生其一，下述幾種情況發(fā)生其一且僅發(fā)生其一. x y, y x, xy, x與與y不可比不可比定義定義4.24 擬序擬序

48、 R為非空集合為非空集合A上的關(guān)系上的關(guān)系,如果如果R是反自反和傳遞的，是反自反和傳遞的，則稱則稱R是是A上的擬序關(guān)系，簡(jiǎn)稱為擬序，記作上的擬序關(guān)系，簡(jiǎn)稱為擬序，記作 . 定義定義4.25 全序全序 R為非空集合為非空集合A上的偏序上的偏序, x, y A, x與與y 都可比，都可比，則稱則稱R為全序?yàn)槿? 定義定義4.26 覆蓋覆蓋 x,yA, 如果如果x y且不存在且不存在 z A使得使得 x z y, 則則稱稱 y覆蓋覆蓋x.實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系 整除關(guān)系不是正整數(shù)集合上的全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系 1, 2, 4

49、, 6集合上的整除關(guān)系集合上的整除關(guān)系, 2覆蓋覆蓋1, 4 和和 6 覆蓋覆蓋2. 但但4不覆蓋不覆蓋1.73偏序集與哈斯圖定義定義4.27 集合集合A和和A上的偏序關(guān)系上的偏序關(guān)系 一起叫做一起叫做偏序集偏序集, 記記作作.實(shí)例：整數(shù)集和數(shù)的小于等于關(guān)系構(gòu)成偏序集實(shí)例：整數(shù)集和數(shù)的小于等于關(guān)系構(gòu)成偏序集 冪集冪集P(A)和包含關(guān)系構(gòu)成偏序集和包含關(guān)系構(gòu)成偏序集. 哈斯圖哈斯圖：利用偏序自反、反對(duì)稱、傳遞性簡(jiǎn)化的關(guān)系圖：利用偏序自反、反對(duì)稱、傳遞性簡(jiǎn)化的關(guān)系圖特點(diǎn)：特點(diǎn)： 每個(gè)結(jié)點(diǎn)沒有環(huán)每個(gè)結(jié)點(diǎn)沒有環(huán) 兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低

50、表示，位置低的元素的順序在前表示，位置低的元素的順序在前 具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊74哈斯圖實(shí)例例例6 75 例例7 已知偏序集已知偏序集的哈斯圖如下圖所示的哈斯圖如下圖所示, 試求出集合試求出集合A和關(guān)系和關(guān)系R的表達(dá)式的表達(dá)式. 哈斯圖實(shí)例（續(xù)）A=a, b, c, d, e, f, g, h R=, IA 76偏序集的特定元素定義定義4.28 設(shè)設(shè)為偏序集為偏序集, B A, yB. (1) 若若 x(xBy x)成立成立, 則稱則稱 y 為為 B 的的最小元最小元. (2) 若若 x(xBx y)成立成立, 則稱則稱 y 為為 B 的的最大元最大元. (3) 若若 x(xBx yx=y)成立成立, 則稱則稱 y 為為B的的極小元極小元. (4) 若若 x(xBy xx=y)成立成立, 則稱則稱 y 為為B的的極大元極大元. 性質(zhì)：性質(zhì)：對(duì)于有窮集，極小元和極大元必存在，可