【正文】 = F?(G?H) 第三章 集合與關(guān)系 復(fù)合關(guān)系 如 :已知集合 X={x1,x2,…,x m}到集合 Y={y1,y2,…y n}有 關(guān)系 R，則 MR=[uij]表示 R的關(guān)系矩陣，其中： uij = 1 當(dāng) xi, yj ? R 0 當(dāng) xi, yj R 因為關(guān)系可用矩陣表示，故復(fù)合關(guān)系亦可用矩陣表示 R ? S。 同理從集合 Y= {y1,y2,…y n}到集合 Z= {z1,z2,…z p}有關(guān)系S，可用矩陣 Ms=[vjk]表示，其中 : ujk = 1 當(dāng) yj, zk ? S 0 當(dāng) yj, zk S ??第三章 集合與關(guān)系 復(fù)合關(guān)系 如果 Y至少有一個這樣的元素 yj ，使得 xi, yj ? R且 yj, zk ? S，則 xi, zk ? R ? S。（在集合 Y中能夠滿足 這樣條件的元素可能不止 yj一個） 當(dāng)掃描 MR的第 i行和 MS第 k列時，如若發(fā)現(xiàn)至少有一個 這樣的 j，使得此行第 j個位置上的記入值和第 k列的第 j個位 置上的記入值都是 1時，則在 M R ? S的第 i行和第 k列 (i,k)上 的記入值是 1；否則為 0。 則表示復(fù)合關(guān)系 R ? S的矩陣 M R ? S可構(gòu)造如下： 第三章 集合與關(guān)系 復(fù)合關(guān)系 則掃描過 MR的第一行和 MS的每一列，就能給出的一行， 再繼續(xù)類似的方法就可得到的其它各行。 因此， M R ? S就可用類似于矩陣乘法的方法得到，即：M R ? S = MR ? MS=[wik] 其中 wik=∨(u ij∧v ik) （ j=1…m ） 則表示復(fù)合關(guān)系 R ? S的矩陣 M R ? S可構(gòu)造如下： 式中 ∨ 代表邏輯加，滿足 0∨ 0=0， 0∨ 1=1， 1∨ 0=1， 1∨ 1=1 ∧ 代表邏輯乘，滿足 0∧ 0=0， 0∧ 1=0， 1∧ 0=0， 1∧ 1=1 第三章 集合與關(guān)系 例 1 設(shè) A={a,b,c,d}, R={a, b, b,a, b,c, c,d}, 求 R2. 解 :R的關(guān)系矩陣 : R2, 關(guān)系矩陣是： ???????????????0000100001010010RM????????????????????????????????????????????0000000010100101000010000101001000001000010100102M第三章 集合與關(guān)系 逆關(guān)系 設(shè) R為 X到 Y的二元關(guān)系，如將 R中每一序偶的元素順序互換，所得到的集合稱為 R的 逆關(guān)系 。 記作 Rc。 Rc={y,x|x,y?R} 定義 2： 如： R上的小于等于關(guān)系的逆關(guān)系是大于等于；全域 關(guān)系的逆關(guān)系仍是全域關(guān)系。 第三章 集合與關(guān)系 3. 7復(fù)合關(guān)系與逆關(guān)系 3. 逆關(guān)系 1） （ R1 ? R2） c=R1c ? R2c 2）（ R1 ? R2） c=R1c? R2c 3）（ A ? B） c=B ? A 4）（ ~ R） c= ~Rc 5）（ R1R2） c=R1cR2c 設(shè) R , R1,R2 均為從 A到 B的二元關(guān)系，那么 定理 1： 第三章 集合與關(guān)系 3. 7復(fù)合關(guān)系與逆關(guān)系 3. 逆關(guān)系 則 （ T?S） c=Sc?Tc 設(shè) T 均為從 X到 Y的關(guān)系， S為從 Y到 Z的關(guān)系， 定理 2： 證： ∵ x,y ?(T?S)c ? y,x?T?S ? ?t(y,t?T∧ t,x?S) ? ?t(x,t?Sc∧ t,y?Tc) ? x,y?(Sc?Tc) ∴ (T?S)c=Sc?Tc 第三章 集合與關(guān)系 3. 7復(fù)合關(guān)系與逆關(guān)系 3. 逆關(guān)系 則 1） R是對稱的 ， 當(dāng)且僅當(dāng) R=Rc 2） R是反對稱的，當(dāng)且僅當(dāng) R?R c=Ix 設(shè) R為 X上的二元關(guān)系， 定理 3： 第三章 集合與關(guān)系 3. 7復(fù)合關(guān)系與逆關(guān)系 證明：設(shè) R是 A上的關(guān)系 , 則 R?IA = IA?R = R. 證 : ∵ x,y?(R?IA) ? ?t(x,t?R∧ t,y?IA) ? ?t(x,t?R∧ t=y) ? x,y?R x,y?R ? x,y?R∧ y?A ? x,y?R∧ y,y?IA ? x,y?(R?IA) ∴ R?IA = R 同理可證 IA?R = R 第三章 集合與關(guān)系 3. 7復(fù)合關(guān)系與逆關(guān)系 證明： 設(shè) F,G,H是關(guān)系 ,則 (1) F?(G∪ H)= F?G∪ F?H。 (2) (G∪ H)?F = G?F∪ H?F。 (3) F?(G∩H)? F?G∩F?H。 (4) (G∩H)?F ? G?F∩H?F. 證 : 以 (3)為例 . ∵ x,y ?F?(G∩H) ? ?t(x,t?F∧ t,y?(G∩H)) ? ?t(x,t?F∧ t,y?G∧ t,y?H) ? ?t((x,t?F∧ t,y?G)∧ (x,t?F∧ t,y?H)) ? ?t(x,t?F∧ t,y?G)∧ ?t(x,t?F∧ t,y?H) ? x,y?F?G∧ x,y?F?H ? x,y?F?G∩F?H ∴ F?(G∩H)=F?G∩F?H 第三章 集合與關(guān)系 3. 7復(fù)合關(guān)系與逆關(guān)系 例： 設(shè) R為 A上的關(guān)系 , m,n?N, 則 (1) Rm ? Rn=Rm+n。 (2) (Rm)n=Rmn 證 : (1) 對于任意取定的 m?N， 關(guān)于 n作數(shù)學(xué)歸納法 。 當(dāng) n=0時 ， Rm ? R0=Rm ? IA=Rm=Rm+0 假設(shè) Rm ? Rn =Rm+n, 則 Rm ? Rn+1=Rm ?(Rn ? R)=(Rm ? Rn)?R=Rm+n ? R1=Rm+n+1 由歸納法原理 , 知命題成立。 (2) 對任意取定的 m?N,關(guān)于 n作數(shù)學(xué)歸納法 。 當(dāng) n=0時 , (Rm)0=IA=R0=Rm 0 假設(shè) (Rm)n=Rmn, 則 (Rm)n+1=(Rm)n?Rm=Rmn? Rm=Rmn+m=Rm(n+1) 由歸納法原理 ,知命題成立 。 第三章 集合與關(guān)系 關(guān)系的閉包運算 關(guān)系的合成和關(guān)系的逆都可構(gòu)成新關(guān)系。有時需用擴充一些序偶的方法得到具有某些特殊性質(zhì)的新關(guān)系，這就是閉包運算。 重點： 三種閉包的計算公式。 第三章 集合與關(guān)系 關(guān)系的閉包運算 定義 1： 設(shè) R是 X上的二元關(guān)系，若有另一關(guān)系 R39。滿足： 1） R39。是自反的（對稱的、傳遞的）； 2） R?R39。 ； 3） 對于任何自反的（對稱的、傳遞的）關(guān)系 R39。39。， 若有 R?R39。39。就有 R39。?R39。39。， 則稱關(guān)系 R39。為 R的 自反閉包 (對稱閉包 ， 傳遞閉包 )。 分別記作： r(R)、 s(R)、 t(R) 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 定理 1： 設(shè) R是 X上的二元關(guān)系，則： 1） R是自反的，當(dāng)且僅當(dāng) r(R)=R 2） R是對稱的，當(dāng)且僅當(dāng) s(R)=R 3） R是傳遞的，當(dāng)且僅當(dāng) t(R)=R 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 設(shè) R是 X上的二元關(guān)系，則： r(R)=R ? Ix s(R)=R ? Rc t(R)= ? Ri （ I=1 ? ∞） =R ? R2 ? R3 ?? 定理 2： 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 (1) r(R)=R∪ Ix。 (2) s(R)= R∪ Rc。 (3) t(R)= R∪ R2∪ R3∪ … . 證明 ： (1) 由 Ix? R∪ Ix 知， R∪ Ix是自反的，且 R? R∪ Ix。 設(shè) R39。39。是 A上包含 R的自反關(guān)系，則 R? R39。39。 , Ix? R39。39。, 因 x,y? R∪ Ix ? x,y? R ∨ x,y? Ix? x,y? R39。39。 ∪ R39。39。= R39。39。 . 即 R∪ Ix? R39。39。 。 可見 R∪ Ix滿足自反閉包的定義 ， 從而 r(R)= R∪ Ix. (2) 略 。 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 (3) t(R)= R∪ R2∪ R3∪ … . 先證 R∪ R2∪ … ? t(R), 為此只需證明對任意正整數(shù) n都有 Rn?t(R)即可 。 用歸納法 。 當(dāng) n=1時 ， R1 = R ? t(R). 假設(shè) Rn ? t(R), 下證 Rn+1?t(R) 事實上 ， 由于 x, y?Rn+1 = Rn ? R ? ?t(x,t?Rn ∧ t,y?R) ? ?t(x,t?t(R) ∧ t,y?t(R)) ?x,y?t(R) 從而 Rn+1 ? t(R) . 由歸納法完成證明 。 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 下證 R∪ R2∪ … 是傳遞的 。 事實上 ， 對任意 x, y,y, z, (x, y ? R∪ R2∪ … )∧ (y, z ? R∪ R2∪ … ) ??t (x, y?Rt) ∧ ?s(y, z?Rs) ? ?t?s(x, z ? Rt ? Rs) ??t?s(x, z ? Rt+s) ? x, z ? R∪ R2∪ … 從而 R∪ R2∪ … 是傳遞的 。 因 t(R)是傳遞閉包 ， 故 t(R) ? R∪ R2∪ … 。 由以上兩方面知 ， t(R) ＝ R∪ R2∪ … 。 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 設(shè) X是含有 n個元素的集合， R是 X上的二元關(guān)系，則 存在一個正整數(shù) k≤n，使得 t(R)= R ? R2 ? R3 ?? Rk 定理 3： 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 通過關(guān)系矩陣求閉包 設(shè)關(guān)系 R, r(R), s(R), t(R)的關(guān)系矩陣分別為 M, Mr, Ms, Mt, 則： Mr = M+E, Ms = M+M39。, Mt = M+M2+M3+… , 其中 E是與 M同階的單位矩陣 。 M39。是 M的轉(zhuǎn)置矩陣 ， 矩陣元素相加時使用 邏輯加 。 第三章 集合與關(guān)系 3. 8 關(guān)系的閉包運算 設(shè)關(guān)系 R, r(R), s(R), t(R)的關(guān)系圖分別記為 G, Gr, Gs, Gt, 則 Gr, Gs, Gt的頂點集與 G的頂點集相同 。 除了 G的邊外 ， 依下述方法添加新邊： (1) 對 G的每個頂點 ， 如果無環(huán) ， 則添加一條環(huán) ， 由此得到 Gr。 (2) 對 G的每條邊 ， 如果它是單向邊 ， 則添加一條反方向的邊 。 由此得到 Gs。 ),2,1( klx lj ??(3) 對 G的每個頂點 xi , 找出從 xi 出發(fā)的所有 2步 , 3步 , … , n步