离散数学(3.7复合关系与逆关系)复习过程

1离散数学(DiscreteMathematics)张捷第一页，共27页。第三章集合(jíhé)与关系（SetsandRelations)

3.6关系的闭包运算(ClosureOperations)3.7集合(jíhé)的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(CompatibilityRelations)3.10序关系(OrderedRelations)3.1集合(jíhé)及其运算(Sets&Operationswithsets)3.2序偶与笛卡尔积(OrderedPairs&CartesianProduct)3.3关系(Relations)3.4关系的性质(ThePropetiesofRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)第二页，共27页。3.5复合关系与逆关系(Compound

Relations&InverseRelations)3.5.1关系的并、交、补及对称差运算3.5.2逆关系(InverseRelations)3.5.3

复合关系(Compound

Relations)第三章集合(jíhé)与关系(Sets&Relations)第三页，共27页。第三章集合(jíhé)与关系(Sets&Relations)3.5.1关系的并、交、补及对称差运算例1

设，

则定理3.5.1

若R与S都是集合A到集合B的关系，则R∪S,R∩S,R-S,均为A到B的关系。第四页，共27页。3.5.2复合(fùhé)关系(CompoundRelations)1.复合(fùhé)关系的定义

定义3.5.1

设是由A到B的关系，是由B到C的关系，则和的复合关系是一个由A到C的关系，用表示，定义为：当且仅当存在元素，使得，时，有。这种由和求复合关系的运算称为关系的复合运算。

由定义可知:

第五页，共27页。于是复合关系

例2

设是由到的关系。是由B到的关系。分别定义为：第六页，共27页。例3设是所有人的集合(jíhé)于是复合(fùhé)关系第七页，共27页。2.关系复合运算的性质定理3.5.2

设是由集合A到B的关系，则

例4

以例2中的关系为例，从关系图，可得,第八页，共27页。

定理3.5.3设是由A到B的关系，是由B到C的关系，则有证:(3)反设则必存在使，从而使故且所以，这就与(1)(2)(3)矛盾。第九页，共27页。

定理3.5.4(1)设是由A到B的关系，是由B到C的关系，是由C到D的关系，则有(2)设是由A到B的关系，是由B到C的关系，则有(3)设是由A到B的关系，是由B到C的关系，则有第十页，共27页。

例5

设，，,.A到B的关系B到C的关系C到D的关系则A到C的关系因此因此所以第十一页，共27页。一般地，若是一由到的关系，是由到的关系，…，是一由到的关系，则不加括号的表达式，唯一地表示一由到的关系，在计算这一关系时，可以运用结合律将其中(qízhōng)任意两个相邻的关系先结合。特别,当，时，复合关系简记作，它也是集A上的一个关系。第十二页，共27页。

3.求复合关系的几种方法（1）根据复合关系的定义求复合关系

例5中求复合关系采用的就是这种方法。又例如

下面的关系图给出了从集合A到B的关系和从B到C的关系第十三页，共27页。（2）运用关系矩阵(jǔzhèn)的运算求复合关系布尔运算其加法(jiāfǎ)和乘法运算定义如下0+0=0,0+1=1+0=1+1=1,例如

第十四页，共27页。•关系(guānxì)矩阵的乘积对两个关系(guānxì)矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。则例6

设和是两个关系矩阵第十五页，共27页。复合关系的关系矩阵

定理3.5.5

设A、B、C均是有限集，是一由A到B的关系,是一由B到C的关系，它们的关系矩阵分别为和，则复合关系的关系矩阵第十六页，共27页。234123123例7

设有集合，，

A到B的关系B到C的关系

则与例6比较得

第十七页，共27页。

例8

设，A上的关系试求和。因此(yīncǐ)解

作出的关系矩阵abcd根据定理3.5.5第十八页，共27页。又，所以因此第十九页，共27页。设是有限集A上的关系，则复合关系也是A上的关系，由复合关系的定义，对于任意(rènyì)的，当且仅当存在，使得，时，有。反映在关系图上，这意味着，当且仅当在的关系图中有某一结点存在(cúnzài)，使得有边由指向，且有边由指向时，在的关系图中有边从指向。（3）利用关系图求复合关系第二十页，共27页。根据的关系图构造出的关系图：对于的关系图中的每一结点，找出从经过长为n的路能够到达的结点，这些结点在的关系图中，边必须由指向它们。类似地，对于任意正整数n，当且仅当在的关系图中存在n-1个结点,使得有边由指向,由指向，…由指向时，在的关系图中，有边由结点指向。第二十一页，共27页。解例10

试利用构造和的关系图的方法求例9中的和。

例中（4）根据和的关系图直接写出和中的序偶.（1）先作出的关系图

（2）构造的关系图。在的关系图中寻找长为2的路。（3）构造的关系图。在的关系图中寻找长为3的路.第二十二页，共27页。例11.下图给出了集合上的关系的关系图，试画出关系和的关系图。第二十三页，共27页。

3.5.3逆关系(InverseRelations)

定义3.5.2

设A、B是任意集合，是由A到B的关系，定义由B到A的关系称为关系的逆关系。于是

解

由的定义知

例12

设，，定义由A到B的关系：当且仅当a整除b时，有，试求的逆关系。

第二十四页，共27页。

关于逆关系我们有如下定理：

定理3.5.6

设A、B是任意集合，、和都是由A到B的关系，则有（1）（2）（3）（4）（5）（6）第二十五页，共27页。

关于逆关系我们有如下定理：

定理3.5.7

设A、B、C是任意集合，、分别是由A到B的关系和由B到C的关系，则有定理3.5.