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

《左孝凌离散数学课件3.7 复合关系和逆关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、引例：a、b、c三人，若设R={}是兄妹关系，S={}是母子关系，则T={}是舅甥关系即T是R与S的复合。一、复合关系1、复合关系(关系的复合运算)定义3-7.1：设X、Y、Z是三个集合，R是X到Y的关系，S是Y到Z的关系，则RS称为R和S的复合关系，表示为RS={xXzZ(y)(yYRS)}。从R和S求RS，称为关系的合成运算。一、复合关系XYZ说明：R与S能进行复合的必要条件是R的值域所属集合Y与S的前域所属集合Y是同一个集合。RS例：X={1，2，3，4，5}，Y={3，

2、4，5}，Z={1,2,3}，R是X到Y的关系，S是Y到Z的关系：R={

3、x+y=6}={<1，5>，<2，4>，<3，3>}，S={y-z=2}={<3，1>，<4，2>，<5，3>}，求RS则RS={<1，3>，<2，2>，<3，1>}另可以用推导：∵x+y=6，y-z=2，消去y得x+z=4一、复合关系①②③④⑤③④⑤①②③R1R2XYZ一、复合关系例：集合X={x，y，z，d，e}，R={，，}，S={，，}，则RS={，，}，SR={<

4、d，y>，}，RR={，}，SS={}一、复合关系p114例题1：令R={<1，2>，<3，4>，<2，2>}，S={<4，2>，<2，5>，<3，1>，<1，3>}，试求RS，SR，R(SR)，(RS)R，RR，SS，RRR。解：RS={<1，5>，<3，2>，<2，5>}SR={<4，2>，<3，2>，<1，4>}R(SR)={<3，2>}(RS)R={<3，2>}RR={<1，2>，<2，2>}SS={<4，5>，<3，3>，<1，1>}RRR={<1，2>，<2，2>}关系

5、的复合运算，满足结合律。一、复合关系p115例题2：设R1和R2是集合X={0，1，2，3}上的关系，R1={

6、j=i+1或j=i/2}，R2={

7、i=j+2}试求R1R2，R2R1，R1R2R1，R1R1，R1R1R1。解：R1={<0,1>,<1,2>,<2,3>,<0,0>,<2,1>}R2={<2,0>,<3,1>}R1R2={<1,0>,<2,1>}R2R1={<2,1>,<2,0>,<3,2>}R1R2R1={<1,1>,<1,0>,<2,2>}R1R1={<0,2>,<1,3>,<1,1>,<0,1>,<0

8、,0>,<2,2>}R1R1R1={<0,3>,<0,1>,<1,2>,<0,2>,<0,0>,<2,3>,<2,1>}关系的n次幂：设R是X上的二元关系，nN，则关系的n次幂R(n)定义为：(1)R(0)=x；(2)R(n+1)=R(n)R说明：如果R是X到Y的关系，且X≠Y，则R2是无意义的，因为RR是无法复合的。定理：设R是集合X上的二元关系，m，nN，则(1)R(m)R(n)=R(m+n)(称第一指数律)(2)(R(m))(n)=R(mn)(称第二指数律)此定理证明可以用数学归纳法加以证明。说明：第三指数律(RS)(n)=R(n)S(n

9、)一般是不成立的。因为：(RS)(2)=(RS)(RS)=R(SR)S，R(2)S(2)=(RR)(SS)=R(RS)S，只要交换律不成立，第三指数律不成立。例：设X={1，2，3，4，5}，X上关系R为R={<1,2>,<2,1>,<2,3>,<3,4>,<4,5>}，则：R(0)=x={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}，R(1)=RR(2)={<1,1>,<2,2>,<1,3>,<2,4>,<3,5>}R(3)={<1,2>,<2,1>,<1,4>,<2,3>,<2,5>}R(4)={<1,1>,<2,

10、2>,<1,5>,<2,4>,<1,3>}R(5)={<1,2>,<1,4>,<2,1>,<2,3>,<2,5>}一、复合关系关系矩阵：设集合X={x1，x2，…，xm}，Y={y1，y2，…，yn}，Z={z1，…，zP}，R是X到Y的关系，其关系矩阵MR=(uij)m×n，S是Y到Z的关系，其关系矩阵MS=(vjk)n×p，复合关系RS是X到Z的关系，其关系矩阵MRS=(wik)m×p，则wik=(uijvjk)。j=1n一、复合关系例题3：给定集合A={1，2，3，4，5}，在A上定义两个关系。R={<1，2>，<2，2>，<3，4>}，S={<1，

11、3>，<2