离散数学(3.7复合关系与逆关系)教学文案.ppt

《离散数学(3.7复合关系与逆关系)教学文案.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1离散数学(DiscreteMathematics)张捷第三章集合与关系（SetsandRelations)3.6关系的闭包运算(ClosureOperations)3.7集合的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(Compatibility　Relations)3.10序关系(OrderedRelations)3.1集合及其运算(Sets&Operationswithsets)3.2序偶与笛卡尔积(OrderedPa

2、irs&CartesianProduct)3.3关系(Relations)3.4关系的性质(ThePropetiesofRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)3.5.1关系的并、交、补及对称差运算3.5.2逆关系(InverseRelations)3.5.3复合关系(CompoundRelations)第三章集合与关系(Sets&Relat

3、ions)第三章集合与关系(Sets&Relations)3.5.1关系的并、交、补及对称差运算例1设，则定理3.5.1若R与S都是集合A到集合B的关系，则R∪S,R∩S,R-S,均为A到B的关系。3.5.2复合关系(CompoundRelations)1.复合关系的定义定义3.5.1设是由A到B的关系，是由B到C的关系，则和的复合关系是一个由A到C的关系，用表示，定义为：当且仅当存在元素，使得，时，有。这种由和求复合关系的运算称为关系的复合运算。由定义可知:于是复合关系例2设是由到的关系。是由B到的关系。

4、分别定义为：例3设是所有人的集合于是复合关系2.关系复合运算的性质定理3.5.2设是由集合A到B的关系，则例4以例2中的关系为例，从关系图，可得,定理3.5.3设是由A到B的关系，是由B到C的关系，则有证:(3)反设则必存在使，从而使故且所以，这就与(1)(2)(3)矛盾。定理3.5.4(1)设是由A到B的关系，是由B到C的关系，是由C到D的关系，则有(2)设是由A到B的关系，是由B到C的关系，则有(3)设是由A到B的关系，是由B到C的关系，则有例5设，，,.A到B的关系B到C的关系C到D的关系则A到C的关

5、系因此因此所以一般地，若是一由到的关系，是由到的关系，…，是一由到的关系，则不加括号的表达式，唯一地表示一由到的关系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。特别,当，时，复合关系简记作，它也是集A上的一个关系。3.求复合关系的几种方法（1）根据复合关系的定义求复合关系例5中求复合关系采用的就是这种方法。又例如下面的关系图给出了从集合A到B的关系和从B到C的关系（2）运用关系矩阵的运算求复合关系布尔运算其加法和乘法运算定义如下0+0=0,0+1=1+0=1+1=1,例如•关系矩阵的乘

6、积对两个关系矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。则例6设和是两个关系矩阵复合关系的关系矩阵定理3.5.5设A、B、C均是有限集，是一由A到B的关系,是一由B到C的关系，它们的关系矩阵分别为和，则复合关系的关系矩阵234123123例7设有集合，，A到B的关系B到C的关系则与例6比较得例8设，A上的关系试求和。因此解作出的关系矩阵abcd根据定理3.5.5又，所以因此设是有限集A上的关系，则复合关系也是A上的关系，由复合关系的定义，对于任意的，当

7、且仅当存在，使得，时，有。反映在关系图上，这意味着，当且仅当在的关系图中有某一结点存在，使得有边由指向，且有边由指向时，在的关系图中有边从指向。（3）利用关系图求复合关系根据的关系图构造出的关系图：对于的关系图中的每一结点，找出从经过长为n的路能够到达的结点，这些结点在的关系图中，边必须由指向它们。类似地，对于任意正整数n，当且仅当在的关系图中存在n-1个结点,使得有边由指向,由指向，…由指向时，在的关系图中，有边由结点指向。解例10试利用构造和的关系图的方法求例9中的和。例中（4）根据和的关系图直接写出

8、和中的序偶.（1）先作出的关系图（2）构造的关系图。在的关系图中寻找长为2的路。（3）构造的关系图。在的关系图中寻找长为3的路.例11.下图给出了集合上的关系的关系图，试画出关系和的关系图。3.5.3逆关系(InverseRelations)定义3.5.2设A、B是任意集合，是由A到B的关系，定义由B到A的关系称为关系的逆关系。于是解由的定义知例12设，，定义由A到B的关系：当且仅当a整除b时，有，试求的逆关系。