南京大学：《离散数学》课程教学资源（PPT课件讲稿）关系、函数及其运算

关系的运算(3) 口逆运算 口R1={(x,y|(,x)∈R} 注意:如果R是从A到酬关系,则R是从B到A的。 (R)1=R 口例子:(ZF)1=R1∪R21 (x,y∈(R∪R)分(x∈(RUR2 (x∈R或(x∈R2 令(x∈R1或(x,∈R2

关系的运算(3)  逆运算  R -1 = { (x, y) | (y,x)R} ◼ 注意:如果R是从A到B的关系,则R-1是从B到A的。  (R-1 ) -1 = R  例子：(R1R2 ) -1= R1 -1R2 -1 ◼ (x, y)  (R1R2 ) -1 (y, x)(R1R2 )  (y, x)R1或 (y, x)R2  (x, y)R1 -1或 (x, y)R2 -1 11

关系的运算(4) 口关系的复合(合成, Composition) 设RsA×B,R2∈BC R1与R2的复合(合成),记为R2°R1,定义如下 R2°R1={(a∈A×C|彐b∈B(a,b∈R∧(b∈R2)}

关系的运算(4)  关系的复合（合成, Composition） 设 R1AB, R2BC, R1与R2的复合（合成）, 记为 R2 ⃘R1 , 定义如下： R2 ⃘R1={(a, c) AC | bB ((a, b)R1(b, c)R2 )} 12 a b c R1 R2

例:关系的复合运算 口设A={ab,c,d},R1,R2为A上的关系,其中 R1={(a,a),(a,b),(b,d)} R2={(ad),(b,c),(b,d),(,b)} 则 R2OR1={(a,d,(a,c),(a,d)} R1R2={(c,d)} R2={(a2a),(ab),(a,d)}

例：关系的复合运算  设A={a, b, c, d}, R1 , R2为A上的关系，其中： R1 = { (a, a), (a, b), (b, d)} R2 = {(a, d), (b, c), (b, d), (c, b)} 则： R2 ⃘R1= {(a, d), (a, c), (a, d)} R1 ⃘R2 = {(c, d)} R1 2 = {(a, a), (a, b), (a, d)} 13

关系的复合运算的性质 口结合律 口给定RAxB,R2BxC,R3CXD,则 (R3°R2)R1=R3°(RPR1) 口证明左右两个集合相等 口复合关系的逆关系 口给定RAxB,R2CB×C,则: Ror=Rb R21 口同样,证明左右两个集合相等

关系的复合运算的性质  结合律  给定R1AB, R2BC, R3CD, 则： (R3 ⃘R2 ) ⃘R1 = R3 ⃘(R2 ⃘R1 )  证明左右两个集合相等  复合关系的逆关系  给定R1AB, R2BC, 则： (R2 ⃘R1 ) -1 = R1 -1 ⃘R2 -1  同样，证明左右两个集合相等 14

关系的复合运算的性质 口对集合并运算满足分配律 口给定 FCAXB, GCBXC,HBxC,则 (G∪HoF=(GoF∪(oF 口对集合交运算:(G∩HFsG∩(Ho 口注意:等号不一点成立。 A={a},B={s4,C={6}; F={(as),(a,},G={(sb)},H={(七b)} GnH=O, (GoF)n(HoF)=((a, b)

关系的复合运算的性质  对集合并运算满足分配律  给定FAB, GBC, HBC, 则： (GH) ⃘F = (G ⃘F)  (H ⃘F)  对集合交运算： (G  H) ⃘F  (G ⃘F)  (H ⃘F)  注意：等号不一点成立。 A={a}, B={s,t}, C={b}; F={(a,s), (a,t)}, G={(s,b)}, H={(t,b)}; GH=Ø, (G ⃘F)  (H ⃘F)={(a,b)} 15