关系的运算教学ppt课件

1、7.3关系的运算关系的运算n关系的定义域、值域、域关系的定义域、值域、域n关系的逆运算及其性质关系的逆运算及其性质n关系的复合合并运算及其性质关系的复合合并运算及其性质n关系的关系的“限制运算及其性质限制运算及其性质n集合在关系下的集合在关系下的“像及性质像及性质n关系的幂运算及其性质关系的幂运算及其性质一、关系的定义域、值域、域一、关系的定义域、值域、域e.g.设设A = a,b,c,d,e，B = x,y,z， R = , 关系关系R的定义域为：的定义域为：domR = a,b,c； 关系关系R的值域：的值域：ranR = x,y； 关系关系R的域：的域：fldR = a,b,c,x,y。

2、一、关系的定义域、值域、域一、关系的定义域、值域、域 定义：设定义：设R是二元关系，由是二元关系，由 R的一切的一切x组成的集合称为组成的集合称为R的定义域的定义域(前域，记作前域，记作domR；使；使 R的一切的一切y组成的集合称组成的集合称为为R的值域，记作的值域，记作ranR。domR = x | y (R) ；ranR = y | x (R) 定义：定义： R的域，即的域，即fldR = domR ranR 二、关系的逆运算及其性质二、关系的逆运算及其性质定义：二元关系定义：二元关系R的逆关系记为的逆关系记为R1 R1 = | R例例1：R=, , , ，求，求R1 R1=, , ,

3、二、关系的逆运算及其性质二、关系的逆运算及其性质 关系逆运算的相关性质：关系逆运算的相关性质： 定理定理1：设：设R是恣意的关系是恣意的关系, 那么那么(1) (R1)1=R(2) domR1=ranR, ranR1=domR问题：关系问题：关系R和和R1的关系矩阵之间有怎样的关系矩阵之间有怎样的联络？的联络？ 互为转置矩阵。互为转置矩阵。二、关系的逆运算及其性质二、关系的逆运算及其性质 设设R、S是恣意的二元关系，是恣意的二元关系，(RS)-1= R-1S-1(RS)-1= R-1S-1(R)-1= (R-1)(R-S)-1= R-1-S-1 RSR-1S-1兄弟兄弟父子父子叔侄叔侄RSR

4、S引例：引例：三、关系的复合运算及其性质三、关系的复合运算及其性质定义：二元关系定义：二元关系R、S的复合运算记作的复合运算记作R S R S = | y (RS) 例例2：R=, , , S=, , , , R S =, , S R =, , , 三、关系的复合运算及其性质三、关系的复合运算及其性质问题：问题： 假设将假设将R S的关系矩阵记为的关系矩阵记为MRS ， R的关系矩阵记为的关系矩阵记为MR， S的关系矩阵记为的关系矩阵记为MS ， 那么那么MRS和和MR ,MS之间有怎样的关之间有怎样的关系？系？三、关系的复合运算及其性质三、关系的复合运算及其性质e.g. A=a,b, R=,

5、 S=, 01010010S SR RM MM MR S = 0001RSRSM M 01010010S SR RM MM M 三、关系的复合运算及其性质三、关系的复合运算及其性质例3：给定集合X=0,1,2中的两个关系如下：)2/1(,|,1ijijxjijiR 2,|,2 jixjijiR试求复合关系：试求复合关系： R1 R2 R1 ， R1 (R2 R1 )三、关系的复合运算及其性质三、关系的复合运算及其性质解：解：R1 = ,R2 = R1 R2 R1 = , =,R1 (R2 R1 ) = , , =,三、关系的复合运算及其性质三、关系的复合运算及其性质复合运算的相关性质：复合运算

6、的相关性质： 定理定理2: 设设F, G, H是恣意的关系是恣意的关系, 那么那么 (1) (F G) H=F (G H) (2) (F G)1= G1 F1定理定理3：设：设RAA，那么，那么R IA=IA R=R三、关系的复合运算及其性质三、关系的复合运算及其性质定理定理4：假设：假设F,G,H是恣意的二元关系，那是恣意的二元关系，那么么 F(GH)= FG FH (GH)F =GF HF F(GH) FG FH (GH)F GF HF四、关系的四、关系的“限制运算及其性限制运算及其性质质例例4：R=, , , R AR R 1=, R =R 1,2=, , , 定义：二元关系定义：二元关

7、系R在集合在集合A上的限制上的限制 即即R A = |RxA定理定理5：设：设F为关系，为关系，A,B为集合，那么：为集合，那么：F (AB)=F AF BF (AB)=F AF B五、集合在关系下的五、集合在关系下的“像及性像及性质质 定义：定义：A 在在R下的像记作下的像记作RA，RA = ran(R A)例例5：R=, , , RA ranR R1=ran(R 1)=ran,=2,4R1,2= ran(R 1,2)=2,3,4定理定理5：设：设F为关系，为关系，A,B为集合，那么：为集合，那么： FAB=FA FB FAB FA FB六、关系的幂运算及其性质六、关系的幂运算及其性质 定义

8、：设定义：设R为为A上的关系上的关系, n为自然数为自然数, 那么那么 R 的的 n次幂定义为：次幂定义为： (1) R0= | xA =IA (2) Rn+1 = Rn R 对于对于A上的任何关系上的任何关系R1和和R2都有：都有： R10 = R20 = IA 对于对于A上的任何关系上的任何关系 R 都有：都有： R1 = R 六、关系的幂运算及其性质六、关系的幂运算及其性质 关系幂运算的求解方法：关系幂运算的求解方法：用集合表示给出用集合表示给出R时，经过时，经过n-1次的右复合得到次的右复合得到Rn ；用关系矩阵用关系矩阵M给出给出R时，时， Rn的关系矩阵由的关系矩阵由n个个M相乘得

9、相乘得到；到；用关系图用关系图G给出给出R时，详细步骤见例题。时，详细步骤见例题。 例例6: 设设A=a,b,c,d, R=, 求求R的各次幂的各次幂, 分别用矩阵和关系图表示分别用矩阵和关系图表示.解解: R0IA它的关系矩它的关系矩阵记作阵记作M0六、关系的幂运算及其性质六、关系的幂运算及其性质 10000100001000010M六、关系的幂运算及其性质六、关系的幂运算及其性质R2对应的关系矩阵为对应的关系矩阵为M2 0000000010100101000010000101001000001000010100102M 0000100001010010MR对应的关系矩阵为对应的关系矩阵为M

10、同理，同理，R3和和R4的矩阵分别是：的矩阵分别是： 0000000010100101000000000101101043M MM M因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到R2=R4=R6=, R3=R5=R7=六、关系的幂运算及其性质六、关系的幂运算及其性质R0, R1, R2, R3,的关系图如以下图所示：的关系图如以下图所示：六、关系的幂运算及其性质六、关系的幂运算及其性质R0R1R2=R4=R6=,R3=R5=R7=六、关系的幂运算及其性质六、关系的幂运算及其性质 定理定理7： 设设A为为n元集元集, R是是A上的关系上的关系, 那么那么存在自然数存在自然数 s 和和 t, 使得使得 Rs = Rt.幂运算的性质幂运算的性质:定理定理6： 设设 R 是是 A 上的关系上的关系, m, nN, 那那么么 (1) Rm Rn=Rm+n (2) (Rm)n=Rmn 六、关系的幂运算及其性质六、关系的幂运算及其性质 定理定理8周期性：设周期性：设R为为A上的关系，假设上的关系，