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

1离散数学(DiscreteMathematics)张捷第三章集合与关系（SetsandRelations)3.6关系的闭包运算(ClosureOperations)3.7集合的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(CompatibilityRelations)3.10序关系(OrderedRelations)3.1集合及其运算(Sets&Operationswithsets)3.2序偶与笛卡尔积(OrderedPairs&CartesianProduct)3.3关系(Relations)3.4关系的性质(ThePropetiesofRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)BABA3.5复合关系与逆关系(CompoundRelations&InverseRelations)3.5.1关系的并、交、补及对称差运算3.5.2逆关系(InverseRelations)3.5.3复合关系(CompoundRelations)第三章集合与关系(Sets&Relations)第三章集合与关系(Sets&Relations)3.5.1关系的并、交、补及对称差运算)},{(4221)}3,3(),2,1{(21例1设，则}3,3,4,2,2,1{1}2,4,4,2,3,1{2}.2,4,3,1,3,3,4,2,2,1{21}.4,2{21,RSR}.3,3,2,1{21定理3.5.1若R与S都是集合A到集合B的关系，则R∪S,R∩S,R-S,均为A到B的关系。}.2,4,3,1,3,3,2,1{213.5.2复合关系(CompoundRelations)1.复合关系的定义定义3.5.1设是由A到B的关系，是由B到C的关系，则和的复合关系是一个由A到C的关系，用表示，定义为：当且仅当存在元素，使得，时，有。这种由和求复合关系的运算称为关系的复合运算。由定义可知:121212Bbba1cb2ca)(211221)(()()(,{21BbbCcAaca))}()(21cbba于是复合关系例2设是由到的关系。是由B到的关系。分别定义为：12},4,3,2,1{A}4,3,2{B}6,5,3{C}2,4,3,3,4,2{}6|,{1baba}6,3,3,3,6,2{}|,{2cbcb整除}6,4,6,3,3,3{21例3设是所有人的集合于是复合关系CBA},,|,{1的兄弟是baAbaba},,|,{2的父亲是cbAcbcb21},,|,{的叔伯是caAcaca2.关系复合运算的性质定理3.5.2设是由集合A到B的关系，则例4以例2中的关系为例，从关系图，可得,BAII}2,4,3,3,4,2{1111AI11BI定理3.5.3设是由A到B的关系，是由B到C的关系，则有证:(3)反设则必存在使，从而使故且所以，这就与12121)(domdom(1)(2)(3)221)(ranran2121,则若domran,21,,CzAxzx21,By,,21zyyx,1rany,2domy21domrany21domran矛盾。,2定理3.5.4(1)设是由A到B的关系，是由B到C的关系，是由C到D的关系，则有(2)设是由A到B的关系，是由B到C的关系，则有(3)设是由A到B的关系，是由B到C的关系，则有123)()(32132113)()()(3121321,123)()()(3231321例5设，，,.A到B的关系B到C的关系C到D的关系则A到C的关系因此因此所以}3,2,1{C}4,3,2{B}6,5,4{D}2,4,3,2,4,2{1}6,3,6,2,5,1,4,2{3}3,4,2,3,1,2{2}1,4,2,2,3,2{21}4,3,2,1{A}6,4,6,3,4,3,5,2{32}5,4,4,2,6,2{)(321}5,4,4,2,6,2{)(321)()(321321一般地，若是一由到的关系，是由到的关系，…，是一由到的关系，则不加括号的表达式，唯一地表示一由到的关系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。特别,当，时，复合关系简记作，它也是集A上的一个关系。11A2A22A3AnnA1nAn211A1nAAAAAn121n21n23.求复合关系的几种方法（1）根据复合关系的定义求复合关系例5中求复合关系采用的就是这种方法。又例如下面的关系图给出了从集合A到B的关系和从B到C的关系12}1,3,3,2,2,2{21（2）运用关系矩阵的运算求复合关系•布尔运算其加法和乘法运算定义如下0001110+0=0,0+1=1+0=1+1=1,例如00001101111)11()000()111()10()001(•关系矩阵的乘积对两个关系矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。则例6设和是两个关系矩阵1M2M0010101000011M1010100012M00101010100121MM•复合关系的关系矩阵定理3.5.5设A、B、C均是有限集，是一由A到B的关系,是一由B到C的关系，它们的关系矩阵分别为和，则复合关系的关系矩阵121M2M212121MMM234123123}4,3,2,1{A}4,3,2{B例7设有集合，，A到B的关系B到C的关系则与例6比较得}3,2,1{C}2,4,3,3,4,2,2,1{1}3,4,1,4,2,3,1,2{2}1,4,2,3,3,2,1,2,1,1{2100101010000143211M1010100014322M001010101001432121M2121MMM例8设，A上的关系试求和。},,,{dcbaA},,,,,,,,,{cbdcccabba32因此0000110011100101000011000101001000001100010100102MMM解作出的关系矩阵abcd根据定理3.5.50000110001010010dcbaM},,,,,,,,,,,,,{2dcccdbcbbbcaaa又，所以因此2300001100110111100000110011100101000011000101001023MMM},,,,,,,,,,,,,,,{3dcccdbcbabdacaba设是有限集A上的关系，则复合关系也是A上的关系，由复合关系的定义，对于任意的，当且仅当存在，使得，时，有。反映在关系图上，这意味着，当且仅当在的关系图中有某一结点存在，使得有边由指向，且有边由指向时，在的关系图中有边从指向。kaja（3）利用关系图求复合关系n2Aaaji,Aakkiaajkaajiaa2kaiakakaja2iajaiakajajaia2根据的关系图构造出的关系图：对于的关系图中的每一结点，找出从经过长为n的路能够到达的结点，这些结点在的关系图中，边必须由指向它们。类似地，对于任意正整数n，当且仅当在的关系图中存在n-1个结点,使得有边由指向,由指向，…由指向时，在的关系图中，有边由结点指向。121,,,nkkkaaaia1ka1ka2ka1nkajaniajaniaiania解2例10试利用构造和的关系图的方法求例9中的和。例中（4）根据和的关系图直接写出和中的序偶.（1）先作出的关系图（2）构造的关系图。在的关系图中寻找长为2的路。（3）构造的关系图。在的关系图中寻找长为3的路.2323},,,,,,,,,{cbdcccabba233322例11.下图给出了集合上的关系的关系图，试画出关系和的关系图。}6,5,4,3,2,1{A583.5.3逆关系(InverseRelations)定义3.5.2设A、B是任意集合，是由A到B的关系，定义由B到A的关系称为关系的逆关系。},|,{1baab1于是解由的定义知例12设，，定义由A到B的关系：当且仅当a整除b时，有，试求的逆关系。}5,3,2{A}10,6,4{Bba1}10,5,6,3,10,2,6,2,4,2{}5,10,3,6,2,10,2,6,2,4{1关于逆关系我们有如下定理：定理3.5.6设A、B是任意集合，、和都是由A到B的关系，则有11)(1211121)(121211121)(ABBA1)(,)()(11BA1211121)(（1）（2）（3）（4）（5）（6）AI1关于逆关系我们有如下定理：定理3.5.7设A、B、C是任意集合，、分别是由A到B的关系和由B到C的关系，则有1112121)(12定理3.5.8设是集合A上的二元关系，则（1）对称当且仅当（2）反对称当且仅当证：1)(第三章集合与关系(Sets&Relations)小结:本节主要介绍了关系的复合运算与逆运算。重点掌握关系的复合运算及其性质、关系的逆运算的性质。作业：P118－119（1），（5），（6）