離散數(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)系。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)系是一個(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)系因此因此所以一般地，若是一由到的關(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)系