关系的运算教学课件

《关系的运算教学课件》由会员分享，可在线阅读，更多相关《关系的运算教学课件（24页珍藏版）》请在装配图网上搜索。

1、12022-11-287.3关系的运算关系的运算n关系的关系的定义域、值域、域定义域、值域、域n关系的关系的逆逆运算及其性质运算及其性质n关系的关系的复合（合并）复合（合并）运算及其性质运算及其性质n关系的关系的“限制限制”运算及其性质运算及其性质n集合在关系下的集合在关系下的“像像”及性质及性质n关系的关系的幂运算幂运算及其性质及其性质22022-11-28一、关系的一、关系的定义域、值域、域定义域、值域、域e.g.设设A=a,b,c,d,e，B=x,y,z，R=,关系关系R的定义域为：的定义域为：domR=a,b,c；关系关系R的值域：的值域：ranR=x,y；关系关系R的域：的域：fld

2、R=a,b,c,x,y。32022-11-28一、关系的一、关系的定义域、值域、域定义域、值域、域 定义：设定义：设R是二元关系，由是二元关系，由 R的所有的所有x组成的集合称为组成的集合称为R的定义域的定义域(前域），记作前域），记作domR；使；使 R的所有的所有y组成的集合称为组成的集合称为R的值域，记作的值域，记作ranR。domR=x|y(R)；ranR =y|x(R)定义：定义：R的域，即的域，即fldR=domR ranR 42022-11-28二、关系的二、关系的逆运算逆运算及其性质及其性质定义：二元关系定义：二元关系R的的逆关系逆关系记为记为R 1 R 1=|R例例1：R=,

3、，求，求R 1 R 1=,52022-11-28二、关系的二、关系的逆运算逆运算及其性质及其性质 关系逆运算的相关性质：关系逆运算的相关性质：定理定理1：设设R是任意的关系是任意的关系,则则(1)(R 1)1=R(2)domR 1=ranR,ranR 1=domR问题：关系问题：关系R和和R 1的关系矩阵之间有怎样的的关系矩阵之间有怎样的联系？联系？互为转置矩阵。互为转置矩阵。62022-11-28二、关系的二、关系的逆运算逆运算及其性质及其性质 设设R、S是任意的二元关系，是任意的二元关系，n(RS)-1=R-1S-1n(RS)-1=R-1S-1n(R)-1=(R-1)n(R-S)-1=R-

4、1-S-1n R SR-1 S-172022-11-28兄弟兄弟父子父子叔侄叔侄RSR S引例：引例：82022-11-28三、关系的三、关系的复合运算复合运算及其性质及其性质定义：二元关系定义：二元关系R、S的复合运算记作的复合运算记作R S R S=|y(R S)例例2：R=,S=,R S=,S R=,92022-11-28三、关系的三、关系的复合运算复合运算及其性质及其性质问题：问题：如果将如果将R S的关系矩阵记为的关系矩阵记为MRS，R的关系矩阵记为的关系矩阵记为MR，S的关系矩阵记为的关系矩阵记为MS，则则MRS和和MR,MS之间有怎样的关系？之间有怎样的关系？102022-11-

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

6、1=,=,R1 (R2 R1)=,=,132022-11-28三、关系的三、关系的复合运算复合运算及其性质及其性质复合运算的相关性质：复合运算的相关性质：定理定理2:设设F,G,H是任意的关系是任意的关系,则则 (1)(F G)H=F (G H)(2)(F G)1=G 1 F 1定理定理3：设设R A A，则，则R IA=IA R=R142022-11-28三、关系的三、关系的复合运算复合运算及其性质及其性质定理定理4：若若F,G,H是任意的二元关系，则是任意的二元关系，则 F(GH)=F G F H(GH)F=G F H F F(GH)F G F H(GH)F G F H F152022-1

7、1-28四、关系的四、关系的“限制限制”运算及其性运算及其性质质例例4：R=,R A R R 1=,R =R 1,2=,定义：二元关系定义：二元关系R在集合在集合A上的限制上的限制 即即R A=|R x A定理定理5：设设F为关系，为关系，A,B为集合，则：为集合，则：F (AB)=F AF BF (AB)=F AF B162022-11-28五、集合在关系下的五、集合在关系下的“像像”及性及性质质 定义：定义：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：设

8、设F为关系，为关系，A,B为集合，则：为集合，则：FAB=FA FB FAB FA FB172022-11-28六、关系的六、关系的幂运算幂运算及其性质及其性质 定义：设定义：设R为为A上的关系上的关系,n为自然数为自然数,则则 R 的的 n次幂次幂定义为：定义为：(1)R0=|xA=IA (2)Rn+1=Rn R 对于对于A上的任何关系上的任何关系R1和和R2都有：都有：R10=R20=IA 对于对于A上的任何关系上的任何关系 R 都有：都有：R1=R 182022-11-28六、关系的六、关系的幂运算幂运算及其性质及其性质 关系幂运算的求解方法：关系幂运算的求解方法：n用集合表示给出用集合

9、表示给出R时，通过时，通过n-1次的右复合得到次的右复合得到Rn；n用关系矩阵用关系矩阵M给出给出R时，时，Rn的关系矩阵由的关系矩阵由n个个M相乘相乘得到；得到；n用关系图用关系图G给出给出R时，具体步骤见例题。时，具体步骤见例题。192022-11-28例例6:设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解:R0IA它的关系矩它的关系矩阵记作阵记作M0六、关系的六、关系的幂运算幂运算及其性质及其性质 10000100001000010M202022-11-28六、关系的六、关系的幂运算幂运算及其性质及其性质R2对应的关系矩阵为对应的

10、关系矩阵为M2 0000000010100101000010000101001000001000010100102M 0000100001010010MR对应的关系矩阵为对应的关系矩阵为M212022-11-28同理，同理，R3和和R4的矩阵分别是：的矩阵分别是：0000000010100101000000000101101043M MM M因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=,R3=R5=R7=六、关系的六、关系的幂运算幂运算及其性质及其性质222022-11-28R0,R1,R2,R3,的关系图如下图所示：的关系图如下图所示：六、关系的六、关系的幂

11、运算幂运算及其性质及其性质R0R1R2=R4=R6=,R3=R5=R7=232022-11-28六、关系的六、关系的幂运算幂运算及其性质及其性质 定理定理7：设设A为为n元集元集,R是是A上的关系上的关系,则存则存在自然数在自然数 s 和和 t,使得使得 Rs=Rt.幂运算的性质幂运算的性质:定理定理6：设设 R 是是 A 上的关系上的关系,m,nN,则则 (1)Rm Rn=Rm+n (2)(Rm)n=Rmn 242022-11-28六、关系的六、关系的幂运算幂运算及其性质及其性质 定理定理8（周期性）（周期性）：设：设R为为A上的关系，若存上的关系，若存在自然数在自然数s,t(st)使得使得Rs=Rt，则：，则：(2)对任何对任何k,iN有有 ,其中其中p=t-si is si ikpkps sR RR R (3)令令 ，则对于任意的，则对于任意的qN有有RqS,110 t tR RR RR RS Sk kt tk ks sR RR R (1)对任何对任何kN有有