《【教学课件】第二章关系(第三部分).ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章关系(第三部分).ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章关系（第三部分）复合关系（复合运算）逆关系（逆运算）闭包运算1复合关系定义n设R是A到B的二元关系，S是B到C的二元关系nR和S的复合是一个A到C的二元关系n(a,c)RS当且仅当(a,b)R并且(b,c)Sn记作RS2两个二元关系的复合可产生一个新的二元关系，因此，二元关系的复合也是二元关系的一种二元运算。3关系的复合举例n例例:设A=a,b,c,R1=,R2=,分别求R1R1，R1R2和R2R1的集合表达式.R1R1=,R1R2=,R2R1=,4关系的复合图形表示a1a2a3b1b2b3b4c1c2c3ARBSCRS=(a1,c1),(a1,c2),(a2,c3),(a3,c3)n设
2、R是A到B的二元关系，S是B到C的二元关系；R=,S=,若从xA有有向路径到达yC，则R R S S5复合关系的矩阵表示nR是A到B的二元关系，|A|=n,|B|=m,R的关系矩阵为:nS是B到C的二元关系，|C|=p,S的关系矩阵为：nM(R)M(S)为n行p列的矩阵nM(RSS)为n行p列的矩阵6复合关系的矩阵与矩阵乘法（1）设A=a1,a2,an,B=b1,b2,bm,C=c1,c2,cpR是A到B的二元关系，S是B到C的二元关系7复合关系的矩阵与矩阵乘法（1）nR和S的关系矩阵MR和Ms分别为：8复合关系的矩阵与矩阵乘法（2）设zij为M(R)M(S)的第i行第j列对应的元素；设wij
3、为M(R S)的第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;9若将M(R)M(S)中所有值大于等于1的zij的值改为1，则修改后的矩阵与RS的矩阵相等。10由布尔加运算可知：（为区分普通加法，此处用表示布尔加运算符）zij1xi1y1j+xi2y2j+ximymj1xi1y1jxi2y2jximymj=10 0=0；0 1=11 0=1；1 1=1若将矩阵乘积M(R)M(S)M(R)M(S)改为
4、布尔乘积，记为M(R)M(S)M(R)M(S)，则有：M(RS)=M(R)M(RS)=M(R)M(S)M(S)11复合关系的矩阵表示（定理）定理定理：设R是A到B的二元关系，S是B到C的二元关系，则有：M(RS)=M(R)M(S)（其中右边的为矩阵的布尔乘运算）12复合关系举例1nR1=,R2=,R1R2=,.13复合关系的特殊性质设IA、IB为集合A、B上的恒等关系,RAB,则(1)IAR=RIB=R可由M(R)与单位矩阵作乘法运算得到。(2)R=R=。randomR=(3)何时使得R1R2=?ranranRR1 1domdomRR22=14复合关系的结合律n定理:设R1,R2,R3为集合,
5、则(R1R2)R3=R1(R2R3)证明:复合关系R1R2的关系矩阵等于R1的关系矩阵与R2的关系矩阵的乘积。而矩阵乘法满足结合律，故关系的复合也满足结合律。15复合关系对和的结合律n(1)F(GH)=FGFH(2)(GH)F=GFHF(3)F(GH)=FGFH(4)(GH)F=GFHFn只证明(3)，其它留作练习。任取,F(GH)存在t，满足：F且GH/*复合关系定义*/存在t，满足：F，G和H存在t，满足：(F和G)且(F和H)/*分拆*/存在t，满足：(F且G)同时存在t，满足：(F且H)FG且FHFGFHF(GH)=FGFH。16关系的n次幂n关系的n次幂(nthpower):设RAA
6、,nN,则(1)R0=IA;(2)Rn+1=RnR,(n1).nRn表示的关系,是R的关系图中长度为n的有向路径的起点与终点的关系.。12nn-117关系幂运算的指数律n由关系复合运算满足结合律可知：(1)RmRn=Rm+n;(2)(Rm)n=Rmn18关系幂运算的指数律(证明)n(1)RmRn=Rm+n;证明明:(数学归纳法)，由m,nN给定m,对n归纳.n=0时,RmRn=RmR0=RmIA=Rm=Rm+0.假设RmRn=Rm+n成立,则RmRn+1=Rm(RnR1)=(RmRn)R1/*幂运算的结合律*/=Rm+nR=R(m+n)+1=Rm+(n+1).(2)同样给定n，对m归纳.19传
7、递判定定理（1）例：例：设R是集合A上的二元关系，如果RR2，则R是传递的。(P50:例2.10)n证明：明：设R,R,则R2/*R2=RR,由复合关系定义得*/R/*R2R*/nR是传递的20传递判定定理（2）反之，若R是传递的，RR2是否一定成立？Answer：是。证明：若R2;存在cA，满足R和R2R（R是传递的）RR221传递判定定理（3）定理：设R是集合A上的二元关系，R是传递的当且仅当RR2。推论：R是传递的当且仅当M(R)M(R)2 2所得矩阵的元素中没有负数。注意：可用该推论方便地判定一个关系是否具有传递性22例2.11设R和S是A上的二元关系，判断下列命题是否正确：（1）如果
8、R和S都是自反关系，则RS也是自反关系。（2）如果R和S都是反自反关系，则RS也是反自反关系。（3）如果R和S都是对称关系，则RS也是对称关系。（4）如果R和S都是反对称关系，则RS也是反对称关系。（5）如果R和S都是传递关系，则RS也是传递关系。23（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都具备反自反性（3）等价于判断：若(a,b)RS且(b,a)RS，则R和S是否能保持对称性。若(a,b)RS且(b,a)
9、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都具备对称性24(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是满足上述条件的传递关系。25重点掌握n复合关系的概念n复合关系满足结合律n求利用矩阵乘法求复合关系n利用复合关系判断关系的传递性26课堂练习nP55：1、227作业nP55n3，428