【教学课件】第二章关系(第三部分).ppt

《【教学课件】第二章关系(第三部分).ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章关系(第三部分).ppt（28页珍藏版）》请在三一办公上搜索。

1、1,第二章 关 系（第三部分）,复合关系（复合运算）逆关系（逆运算）闭包运算,2,复合关系定义,设R是A到B的二元关系，S是B到C的二元关系R和S的复合是一个A到C的二元关系(a,c)RS 当且仅当(a,b)R 并且(b,c)S记作 RS,3,两个二元关系的复合可产生一个新的二元关系，因此，二元关系的复合也是二元关系的一种二元运算。,4,关系的复合 举例,例:设 A=a,b,c,R1=,R2=,分别求R1 R1，R1 R2和R2 R1的集合表达式.R1R1=,R1R2=,R2R1=,5,关系的复合图形表示,RS=(a1,c1),(a1,c2),(a2,c3),(a3,c3),设R是A到B的二元

2、关系，S是B到C的二元关系；R=,S=,若从xA有有向路径到达yC，则RS,6,复合关系的矩阵表示,R是A到B的二元关系，|A|=n,|B|=m,R的关系矩阵为:,S是B到C的二元关系，|C|=p,S的关系矩阵为：,M(R)M(S)为n行p列的矩阵M(RS)为n行p列的矩阵,7,复合关系的矩阵与矩阵乘法（1）,设A=a1,a2,an,B=b1,b2,bm,C=c1,c2,cp R是A到B的二元关系，S是B到C的二元关系,8,复合关系的矩阵与矩阵乘法（1）,R和S的关系矩阵MR 和 Ms分别为：,9,复合关系的矩阵与矩阵乘法（2）,设zij为 M(R)M(S)的第i行第j列对应的元素；设wij为

3、M(RS)的第i行第j列对应的元素；由矩阵定义：zij=xi1y1j+xi2y2j+ximymj；zij1 存在k，满足:xikykj=1;存在k，满足：xik=1 且 ykj=1；存在k，满足：(ai,bk)R 且(bk,cj)S；(ai,cj)RS;wij=1;,10,若将 M(R)M(S)中所有值大于等于1的zij的值改为1，则修改后的矩阵与RS的矩阵相等。,11,由布尔加运算可知：（为区分普通加法，此处用表示布尔加运算符）zij 1 xi1y1j+xi2y2j+ximymj 1 xi1y1j xi2y2j ximymj=1,0 0=0；0 1=11 0=1；1 1=1,若将矩阵乘积M(

4、R)M(S)改为布尔乘积，记为M(R)M(S)，则有：M(RS)=M(R)M(S),12,复合关系的矩阵表示（定理）,定理：设R是A到B的二元关系，S是B到C的二元关系，则有：M(RS)=M(R)M(S)（其中右边的 为矩阵的布尔乘运算）,13,复合关系 举例1,R1=,R2=,R1R2=,.,14,复合关系的特殊性质,设IA、IB为集合A、B上的恒等关系,RAB,则(1)IA R=R IB=R 可由M(R)与单位矩阵作乘法运算得到。(2)R=R=。ran dom R=(3)何时使得R1 R2=?ran R1 dom R2=,15,复合关系的结合律,定理:设R1,R2,R3为集合,则(R1R2

5、)R3=R1(R2R3)证明:复合关系R1R2的关系矩阵等于R1的关系矩阵与R2的关系矩阵的乘积。而矩阵乘法满足结合律，故关系的复合也满足结合律。,16,复合关系对和的结合律,(1)F(GH)=F GF H(2)(GH)F=G FH F(3)F(GH)=F GF H(4)(GH)F=G FH F只证明(3)，其它留作练习。任取,F(GH)存在t，满足：F且GH/*复合关系定义*/存在t，满足：F，G和H 存在t，满足：(F和G)且(F 和 H)/*分拆*/存在t，满足：(F且G)同时存在t，满足：(F且H)F G 且 F H F GF H F(GH)=F GF H。,17,关系的n次幂,关系的

6、n次幂(nth power):设RAA,nN,则(1)R0=IA;(2)Rn+1=Rn R,(n1).Rn表示的关系,是R的关系图中长度为n的有向路径的起点与终点的关系.。,1,2,n,n-1,18,关系幂运算的指数律,由关系复合运算满足结合律可知：(1)Rm Rn=Rm+n;(2)(Rm)n=Rmn,19,关系幂运算的指数律(证明),(1)Rm Rn=Rm+n;证明:(数学归纳法)，由m,nN 给定m,对n归纳.n=0时,Rm Rn=Rm R0=Rm IA=Rm=Rm+0.假设 Rm Rn=Rm+n成立,则 Rm Rn+1=Rm(Rn R1)=(Rm Rn)R1/*幂运算的结合律*/=Rm+

7、n R=R(m+n)+1=Rm+(n+1).(2)同样给定n，对m归纳.,20,传递判定定理（1）,例：设R是集合A上的二元关系，如果R R2，则R是传递的。(P50:例2.10)证明：设R,R,则 R2/*R2=RR,由复合关系定义得*/R/*R2 R*/R是传递的,21,传递判定定理（2）,反之，若R是传递的，R R2是否一定成立？Answer：是。证明：若R2;存在cA，满足R和R2 R（R是传递的）R R2,22,传递判定定理（3）,定理：设R是集合A上的二元关系，R是传递的当且仅当 R R2。推论：R是传递的当且仅当M(R)M(R)2所得矩阵的元素中没有负数。,注意：可用该推论方便地

8、判定一个关系是否具有传递性,23,例2.11,设R和S是A上的二元关系，判断下列命题是否正确：（1）如果R和S都是自反关系，则RS也是自反关系。（2）如果R和S都是反自反关系，则RS也是反自反关系。（3）如果R和S都是对称关系，则RS也是对称关系。（4）如果R和S都是反对称关系，则RS也是反对称关系。（5）如果R和S都是传递关系，则RS也是传递关系。,24,（1）对任意xA，RS是否成立？由R和S都具有自反性R且S，因此，RS。（2）等价于判断：若(a,a)RS,R和S能否保持反自反性。若(a,a)RS 存在x，使得(a,x)R和(x,a)S 若R=(a,x),S=(x,a)，则R和S都具备反

9、自反性（3）等价于判断：若(a,b)RS且(b,a)RS，则R和S是否能保持对称性。若(a,b)RS且(b,a)RS 存在x，使得(a,x)R和(x,b)S(a,x)R,(x,a)R 和(x,b)S,(b,x)S 若R=(a,x),(x,a),S=(x,b),(b,x)，则R和S都具备对称性,25,(4)等价于判断：若RS且RS，R和S能否是反对称关系？RS 存在xA，满足：R和S；RS 存在yA，满足：R和S；显然，当R=,和S=,时，R和S是反对称关系。(5)等价于判断：若RS,RS但RS，R和S能否是传递关系？RS 存在xA，满足：R和S；RS 存在yA，满足：R和S；显然，当R=,和S=,时，R和S是满足上述条件的传递关系。,26,重点掌握,复合关系的概念复合关系满足结合律求利用矩阵乘法求复合关系利用复合关系判断关系的传递性,27,课堂练习,P55：1、2,28,作业,P553，4,