离散数学课件3.7 复合关系和逆关系

,引例：a、b、c三人，若设R=是兄妹关系，S=是母子关系，则T=是舅甥关系即T是R与S的复合。,一、复合关系,1、复合关系(关系的复合运算)定义3-7.1：设X、Y、Z是三个集合，R是X到Y的关系，S是Y到Z的关系，则RS称为R和S的复合关系，表示为RS=xXzZ(y)(yYRS)。从R和S求RS，称为关系的合成运算。,一、复合关系,说明：R与S能进行复合的必要条件是R的值域所属集合Y与S的前域所属集合Y是同一个集合。,R,S,例：X=1，2，3，4，5，Y=3，4，5，Z=1,2,3，R是X到Y的关系，S是Y到Z的关系：R=|x+y=6=，S=y-z=2=，求RS则RS=，另可以用推导：x+y=6，y-z=2，消去y得x+z=4,一、复合关系,R1,R2,X,Y,Z,一、复合关系,例：集合X=x，y，z，d，e，R=，S=，则RS=，SR=，RR=，SS=,一、复合关系,p114例题1：令R=，S=，试求RS，SR，R(SR)，(RS)R，RR，SS，RRR。解：RS=，SR=，R(SR)=(RS)R=RR=，SS=，RRR=，,关系的复合运算，满足结合律。,一、复合关系,p115例题2：设R1和R2是集合X=0，1，2，3上的关系，R1=|j=i+1或j=i/2，R2=|i=j+2试求R1R2，R2R1，R1R2R1，R1R1，R1R1R1。解：R1=,R2=,R1R2=,R2R1=,R1R2R1=,R1R1=,R1R1R1=,关系的n次幂：设R是X上的二元关系，nN，则关系的n次幂R(n)定义为：(1)R(0)=x；(2)R(n+1)=R(n)R说明：如果R是X到Y的关系，且XY，则R2是无意义的，因为RR是无法复合的。,定理：设R是集合X上的二元关系，m，nN，则(1)R(m)R(n)=R(m+n)(称第一指数律)(2)(R(m)(n)=R(mn)(称第二指数律)此定理证明可以用数学归纳法加以证明。,说明：第三指数律(RS)(n)=R(n)S(n)一般是不成立的。因为：(RS)(2)=(RS)(RS)=R(SR)S，R(2)S(2)=(RR)(SS)=R(RS)S，只要交换律不成立，第三指数律不成立。,例：设X=1，2，3，4，5，X上关系R为R=,，则：R(0)=x=,，R(1)=RR(2)=,R(3)=,R(4)=,R(5)=,一、复合关系,关系矩阵：设集合X=x1，x2，xm，Y=y1，y2，yn，Z=z1，zP，R是X到Y的关系，其关系矩阵MR=(uij)mn，S是Y到Z的关系，其关系矩阵MS=(vjk)np，复合关系RS是X到Z的关系，其关系矩阵MRS=(wik)mp，则wik=(uijvjk)。,一、复合关系,例题3：给定集合A=1，2，3，4，5，在A上定义两个关系。R=，S=，。求RS和SR的矩阵。解：010000010000001010000000100001MRS=0001010000=01000=,000000100000000,000000000000000001000100000010000010100000000MSR=1000000010=01000=,010000000001000,000000000000000,一、复合关系,复合关系的性质(1)复合运算结合律设R、S、T分别是X到Y、Y到Z、Z到D的关系，则(RS)T=R(ST)证明：(RS)TzZ，RS，T，yY，R，S，TR，STR(ST)所以(RS)TR(ST)类似可以证R(ST)(RS)T，从而(RS)T=R(ST),一、复合关系,复合关系的性质(2)复合运算与，的关系设R是从集合X到Y的关系，S和T均为Y到Z的关系，U是Z到D的关系，则R(ST)=RSRTR(ST)RSRT(ST)U=SUTU(ST)USUTU证明：R(ST)yY，R(y，z)STR(ST)(RS)(RT)RSRT)RSRT从而R(ST)=RSRT,一、复合关系,2020/4/30,Copyright：张捷,17,一、复合关系,2020/4/30,Copyright：张捷,18,（2）运用关系矩阵的运算求复合关系,布尔运算其加法和乘法运算定义如下,0+0=0,0+1=1+0=1+1=1,例如,一、复合关系,2020/4/30,Copyright：张捷,19,关系矩阵的乘积对两个关系矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。,2020/4/30,Copyright：张捷,20,2020/4/30,Copyright：张捷,21,234123123,2020/4/30,Copyright：张捷,22,例8设，A上的关系试求和。,因此,解作出的关系矩阵abcd,2020/4/30,Copyright：张捷,23,2020/4/30,Copyright：张捷,24,当且仅当在R的关系图中有某一结点ak存在，使得有边由ai指向ak，且有边由ak指向aj时，在R2的关系图中有边从ai指向aj。,（3）利用关系图求复合关系,2020/4/30,Copyright：张捷,25,2020/4/30,Copyright：张捷,26,解,2020/4/30,Copyright：张捷,27,例11.下图给出了集合上的关系的关系图，试画出关系和的关系图。,定义3-7.2：设R是集合X到Y的二元关系，如将R中每一序偶中的元素顺序互换，所得到的集合称为R的逆关系，记作Rc=|R。说明：Rc的关系矩阵是R的关系矩阵的转置，Rc的关系图是将R的关系图中的弧改变方向。例：设某合X=x，y，z，X上的关系R=，则Rc=，,二、逆关系,例题4：给定集合X=a，b，c，R是X上的二元关系。R的关系矩阵101MR=110111求Rc和RRc的关系矩阵。解：111MRc=011101101111111MRRc=110011=111111101111,二、逆关系,定理3-7.1：设R，R1和R2均是A到B的二元关系，则(1)(Rc)c=R(2)(R1R2)c=R1cR2c(3)(R1R2)c=R1cR2c(4)(AB)c=BA(5)(R)c=RcR=AB-R(6)(R1-R2)c=R1c-R2c证明：(2)(R1R2)cR1R2R1R2R1cR2cR1cR2c,定理3-7.2：设R是X到Y的关系，S是Y到Z的关系，则(RS)c=ScRc。证明：(RS)cRS(y)(yYRS)(y)(yYRcScScRc,例：X=x，y，z，Y=1，2，3，4，5，R是X上关系，S是X到Y的关系。R=，S=，则RS=，Rc=，Sc=，ScRc=，可验证：ScRc=(RS)c,定理3-7.3：设R是X上的二元关系，则(1)R是对称的，当且仅当R=Rc(2)R是反对称的，当且仅当RRcIx证明：(1)因为R是对称的，故RRRc，所以R=Rc。反之，若R=Rc，因为RRcR，所以R是对称的。(2)设R是反对称的，RRcRRcRR，因为R是反对称的，所以x=y，故RRcIx。反之，若RRcIx，RRc有Ix，即x=y。又RRcRRcRR，但x=y，故R是反对称的