天津理工大学：《离散数学》课程教学资源（PPT课件）第四章 二元关系与函数 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包

关系的基本运算定义(续）逆与合成R-1 = [<y,x> /<x,y>eR)RoS=<x,z>IE y(<x,y>eSA<y,z>eR) )例2R=[<1,2>, <2,3>, <1,4>, <2,2>]S=[<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}R-1=[<2,1>,<3,2>, <4,1>, <2,2>]SoR =[<1,3>, <2,2>, <2,3>}RoS =[<1,2>, <1,4>, <3,2>, <3,3>]

6 关系的基本运算定义（续） 逆与合成 R−1 = {<y,x> | <x,y>R} R∘S = |<x,z> |  y (<x,y>S<y,z>R) } 例2 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R−1={<2,1>, <3,2>, <4,1>, <2,2>} S∘R ={<1,3>, <2,2>, <2,3>} R∘S ={<1,2>, <1,4>, <3,2>, <3,3>}

合成运算的图示方法利用图示（不是关系图）方法求合成RoS =[<1,2>, <1,4>, <3,2>, <3,3>]SoR =[<1,3>, <2,2>, <2,3>]213ASoRRoS

7 合成运算的图示方法 利用图示（不是关系图）方法求合成 R∘S ={<1,2>, <1,4>, <3,2>, <3,3>} S∘R ={<1,3>, <2,2>, <2,3>} S∘R R∘S

例、设 R=((1,2),(2,2),(3,4))S = (1,3),(2,5),(3,1),(4,2),(4,5))求RoS,SoR,RoR,SoS,(RoR)oR,(RoS)oR。解: RoS =(1,4),(3,2),(4,2))S o R= ((1,5),(2,5),(3,2),(3,5))Ro R= ((1,2),(2,2))0

8 例、 设 R =  1,2 , 2,2 , 3,4  S =  1,3 , 2,5 , 3,1 , 4,2 , 4,5  求 R S S R R R S S ( ) R R R ， ， ， ， ， ( ) R S R 。 解： R S =  1,4 , 3,2 , 4,2  S R =  1,5 , 2,5 , 3,2 , 3,5  R R =  1,2 , 2,2 

例、设 R=((1,2),(2,2),(3,4))S = (1,3),(2, 5),(3,1),(4,2),(4,5))求RoS,SoR,RoR,SoS,(RoR)oR ,(RoS)oR。解: SoS =((1,1),(3,3),(4,5))(RoR) oR= ((1,2),(2,2)(RoS)R=(3,2)):

9 例、 设 R =  1,2 , 2,2 , 3,4  S =  1,3 , 2,5 , 3,1 , 4,2 , 4,5  求 R S S R R R S S ( ) R R R ， ， ， ， ， ( ) R S R 。 解： S S =  1,1 , 3,3 , 4,5  ( ) 1,2 , 2,2 R R R =   ( ) 3,2 R S R =  

限制与像定义 F在A上的限制FIA= [<x,y>|xFy ^xEA)A在F下的像F[A] = ran(FIA)实例R=[<1,2>,<2,3>,<1,4>,<2,2>]R{1}=[<1,2>,<1,4>}R[(1]]={2,4]RQ=OR[(1,2]]=[2,3,4]注意： FIACF, F[A] CranF10

10 限制与像 定义 F 在A上的限制 F↾A = {<x,y> | xFy  xA} A 在F下的像 F[A] = ran(F↾A) 实例 R={<1,2>, <2,3>, <1,4>, <2,2>} R↾{1}={<1,2>,<1,4>} R[{1}]={2,4} R↾= R[{1,2}]={2,3,4} 注意：F↾AF, F[A] ranF