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

1離散數(shù)學(xué)(DiscreteMathematics)張捷第三章集合與關(guān)系〔SetsandRelations)

3.6關(guān)系的閉包運(yùn)算(ClosureOperations)3.7集合的劃分與覆蓋(Partition&CoverofSets)3.8等價(jià)關(guān)系(EquivalentRelations)3.9相容關(guān)系(CompatibilityRelations)3.10序關(guān)系(OrderedRelations)3.1集合及其運(yùn)算(Sets&Operationswithsets)

3.2序偶與笛卡爾積(OrderedPairs&CartesianProduct)3.3關(guān)系(Relations)3.4關(guān)系的性質(zhì)(ThePropetiesofRelations)3.5復(fù)合關(guān)系與逆關(guān)系(CompoundRelations&InverseRelations)3.5復(fù)合關(guān)系與逆關(guān)系(Compound

Relations&InverseRelations)3.5.1關(guān)系的并、交、補(bǔ)及對(duì)稱差運(yùn)算3.5.2逆關(guān)系(InverseRelations)3.5.3

復(fù)合關(guān)系(Compound

Relations)第三章集合與關(guān)系(Sets&Relations)第三章集合與關(guān)系(Sets&Relations)

3.5.1關(guān)系的并、交、補(bǔ)及對(duì)稱差運(yùn)算例1

設(shè)，

則定理3.5.1

若R與S都是集合A到集合B的關(guān)系，則R∪S,R∩S,R-S,均為A到B的關(guān)系。

復(fù)合關(guān)系(Compound

Relations)1.

復(fù)合關(guān)系的定義

定義3.5.1

設(shè)是由A到B的關(guān)系，是由B到C的關(guān)系，則和的復(fù)合關(guān)系是一個(gè)由A到C的關(guān)系，用表示，定義為：當(dāng)且僅當(dāng)存在元素，使得，時(shí)，有。這種由和求復(fù)合關(guān)系的運(yùn)算稱為關(guān)系的復(fù)合運(yùn)算。

由定義可知:

于是復(fù)合關(guān)系

例2

設(shè)是由到的關(guān)系。是由B到的關(guān)系。分別定義為：

例3

設(shè)是所有人的集合于是復(fù)合關(guān)系

2.關(guān)系復(fù)合運(yùn)算的性質(zhì)定理3.5.2

設(shè)是由集合A到B的關(guān)系，則

例4

以例2中的關(guān)系為例，從關(guān)系圖，可得,

定理3.5.3設(shè)是由A到B的關(guān)系，是由B到C的關(guān)系，則有證:(3)反設(shè)則必存在使，從而使故且所以，這就與(1)(2)(3)矛盾。

定理3.5.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)系因此因此所以一般地，假設(shè)是一由到的關(guān)系，是由到的關(guān)系，…，是一由到的關(guān)系，那么不加括號(hào)的表達(dá)式，唯一地表示一由到的關(guān)系，在計(jì)算這一關(guān)系時(shí)，可以運(yùn)用結(jié)合律將其中任意兩個(gè)相鄰的關(guān)系先結(jié)合。特別,當(dāng)，時(shí)，復(fù)合關(guān)系簡(jiǎn)記作，它也是集A上的一個(gè)關(guān)系。

3.求復(fù)合關(guān)系的幾種方法（1）根據(jù)復(fù)合關(guān)系的定義求復(fù)合關(guān)系

例5中求復(fù)合關(guān)系采用的就是這種方法。又例如

下面的關(guān)系圖給出了從集合A到B的關(guān)系和從B到C的關(guān)系〔2〕運(yùn)用關(guān)系矩陣的運(yùn)算求復(fù)合關(guān)系布爾運(yùn)算其加法和乘法運(yùn)算定義如下0+0=0,0+1=1+0=1+1=1,例如

?關(guān)系矩陣的乘積對(duì)兩個(gè)關(guān)系矩陣求其乘積時(shí)，其運(yùn)算法那么與一般矩陣的乘法是相同的，但其中的加法運(yùn)算和乘法運(yùn)算應(yīng)改為布爾加和布爾乘。則例6

設(shè)和是兩個(gè)關(guān)系矩陣

復(fù)合關(guān)系的關(guān)系矩陣

定理3.5.5

設(shè)A、B、C均是有限集，是一由A到B的關(guān)系,是一由B到C的關(guān)系，它們的關(guān)系矩陣分別為和，則復(fù)合關(guān)系的關(guān)系矩陣234123123例7

設(shè)有集合，，

A到B的關(guān)系B到C的關(guān)系

則與例6比較得

例8

設(shè)，A上的關(guān)系試求和。因此解

作出的關(guān)系矩陣abcd根據(jù)定理3.5.5又，所以因此設(shè)是有限集A上的關(guān)系，那么復(fù)合關(guān)系也是A上的關(guān)系，由復(fù)合關(guān)系的定義，對(duì)于任意的，當(dāng)且僅當(dāng)存在，使得，時(shí)，有。反映在關(guān)系圖上，這意味著，當(dāng)且僅當(dāng)在的關(guān)系圖中有某一結(jié)點(diǎn)存在，使得有邊由指向，且有邊由指向時(shí)，在的關(guān)系圖中有邊從指向。（3）利用關(guān)系圖求復(fù)合關(guān)系根據(jù)的關(guān)系圖構(gòu)造出的關(guān)系圖：對(duì)于的關(guān)系圖中的每一結(jié)點(diǎn)，找出從經(jīng)過(guò)長(zhǎng)為n的路能夠到達(dá)的結(jié)點(diǎn)，這些結(jié)點(diǎn)在的關(guān)系圖中，邊必須由指向它們。類似地，對(duì)于任意正整數(shù)n，當(dāng)且僅當(dāng)在的關(guān)系圖中存在n-1個(gè)結(jié)點(diǎn),使得有邊由指向,由指向，…由指向時(shí)，在的關(guān)系圖中，有邊由結(jié)點(diǎn)指向。解例10

試?yán)脴?gòu)造和的關(guān)系圖的方法求例9中的和。

例中（4）根據(jù)和的關(guān)系圖直接寫出和中的序偶.（1）先作出的關(guān)系圖

（2）構(gòu)造的關(guān)系圖。在的關(guān)系圖中尋找長(zhǎng)為2的路。（3）構(gòu)造的關(guān)系圖。在的關(guān)系圖中尋找長(zhǎng)為3的路.例11.下圖給出了集合上的關(guān)系的關(guān)系圖，試畫出關(guān)系和的關(guān)系圖。

3.5.3逆關(guān)系(InverseRelations)

定義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時(shí)，有，試求的逆關(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)系和