離散數(shù)學(xué)(3.7復(fù)合關(guān)系與逆關(guān)系)課件

1、1離散數(shù)學(xué)(Discrete Mathematics)張捷第三章 集合與關(guān)系（Sets and Relations) 3.6 關(guān)系的閉包運算(Closure Operations)3.7 集合的劃分與覆蓋(Partition & Cover of Sets) 3.8 等價關(guān)系(Equivalent Relations) 3.9 相容關(guān)系(CompatibilityRelations) 3.10 序關(guān)系(Ordered Relations)3.1 集合及其運算(Sets & Operations with sets) 3.2 序偶與笛卡爾積(Ordered Pairs & Cartesian P

2、roduct)3.3 關(guān)系 (Relations) 3.4 關(guān)系的性質(zhì)(The Propeties of Relations) 3.5 復(fù)合關(guān)系與逆關(guān)系(Compound Relations & Inverse Relations)3.5 復(fù)合關(guān)系與逆關(guān)系(Compound Relations & Inverse Relations)3.5.1 關(guān)系的并、交、補及對稱差運算3.5.2 逆關(guān)系(Inverse Relations)3.5.3 復(fù)合關(guān)系 (Compound Relations)第三章 集合與關(guān)系(Sets & Relations)第三章 集合與關(guān)系(Sets & Relations

3、) 3.5.1 關(guān)系的并、交、補及對稱差運算例1 設(shè) ， 則定理3.5.1 若R與S都是集合A到集合B的關(guān)系，則 RS,RS,R-S, 均為A到B的關(guān)系。3.5.2 復(fù)合關(guān)系 (Compound Relations)1. 復(fù)合關(guān)系的定義 定義3.5.1 設(shè) 是由A到B的關(guān)系， 是由B到C的關(guān)系，則 和 的復(fù)合關(guān)系是一個由A到C的關(guān)系，用 表示，定義為：當(dāng)且僅當(dāng)存在元素 ，使得 ， 時，有 。 這種由 和 求復(fù)合關(guān)系 的運算稱為關(guān)系的復(fù)合運算。 由定義可知: 于是復(fù)合關(guān)系 例2 設(shè) 是由 到 的關(guān)系。 是由 B 到 的關(guān)系。 分別定義為： 例3 設(shè) 是所有人的集合 于是復(fù)合關(guān)系 定理3.5.4

4、(1) 設(shè) 是由A到B的關(guān)系， 是由B到C的關(guān)系， 是由C到D的關(guān)系，則有 (2)設(shè) 是由A到B的關(guān)系， 是由B到C的關(guān)系，則有 (3)設(shè) 是由A到B的關(guān)系， 是由B到C的關(guān)系，則有 例5 設(shè) ， ， , . A到B的關(guān)系 B到C的關(guān)系 C到D的關(guān)系 則A到C的關(guān)系 因此因此所以一般地，若 是一由 到 的關(guān)系， 是由 到 的關(guān)系， 是一由 到 的關(guān)系，則不加括號的表達式 ， 唯一地表示一由 到 的關(guān)系，在計算這一關(guān)系時，可以運用結(jié)合律將其中任意兩個相鄰的關(guān)系先結(jié)合。特別,當(dāng) ， 時，復(fù)合關(guān)系 簡記作 ，它也是集 A 上的一個關(guān)系。 復(fù)合關(guān)系的關(guān)系矩陣 定理3.5.5 設(shè)A、B、C均是有限集，

5、是一由A到B的關(guān)系, 是一由B到C的關(guān)系，它們的關(guān)系矩陣分別為 和 ，則復(fù)合關(guān)系 的關(guān)系矩陣 2 3 4 1 2 3 1 2 3例7 設(shè)有集合 ， ， A到B的關(guān)系 B到C的關(guān)系 則與例6比較得 例8 設(shè) ，A上的關(guān)系 試求 和 。因此 解 作出的關(guān)系矩陣 a b c d根據(jù)定理3.5.5又 ，所以因此例11. 下圖給出了集合 上的關(guān)系 的關(guān)系圖，試畫出關(guān)系 和 的關(guān)系圖。 3.5.3 逆關(guān)系(Inverse Relations) 定義3.5.2 設(shè) A 、 B 是任意集合， 是由 A 到 B 的 關(guān)系，定義由 B 到 A 的關(guān)系稱 為關(guān)系 的逆關(guān)系。 于是 解 由 的定義知 例12 設(shè) ， ， 定義由A到B的關(guān)系 ：當(dāng)且僅當(dāng) a 整除 b 時，有 ，試求 的逆關(guān)系 。 關(guān)于逆關(guān)系我們有如下定理： 定理3.5.6 設(shè) A 、 B 是任意集合， 、 和 都是由 A 到 B 的關(guān)系，則有（1）（2）（3）（4）（5）（6） 關(guān)于逆關(guān)系我們有如下定理： 定理3.5.7 設(shè) A 、 B、C 是任意集合， 、 分別是 由 A 到 B 的關(guān)系和由 B 到 C 的關(guān)系，則有定理3.5.8 設(shè) 是集合A上的二元關(guān)系 ， 則 （1） 對稱當(dāng)且僅當(dāng) （2） 反對稱當(dāng)且僅當(dāng)證：第三章 集合與關(guān)系(