《-_复合关系和逆关系》-课件设计（公开).pptVIP

3-7 复合关系和逆关系 本节讲述关系的运算。 一、复合关系 引例：a、b、c三人，a、b是兄妹关系，b、c是母子关系，则a、c是舅甥关系，若设R是兄妹关系，S是母子关系，则R与S的复合T是舅甥关系。如R是父子关系，R与R复合是祖孙关系。 1、复合关系(关系的复合运算) 定义3-7.1：设X、Y、Z是三个集合，R是X到Y的关系，S是Y到Z的关系，则R?S称为R和S的复合关系，表示为 R?S={x,z?x?X?z?Z?(?y)(y?Y?x,y?R?y,z?S)} 从R和S求R?S，称为关系的合成运算。 说明：R与S能进行复合的必要条件是R的值域所属集合Y与S前域所属集合Y是同一个集合。 例：X={1，2，3，4，5}，Y={3，4，5}，Z={1，2，3}，R是X到Y的关系，S是Y到Z的关系： R={x，y|x+y=6}={1，5，2，4，3，3}， S={y，z?y-z=2}={3，1，4，2，5，3}， 则R?S={1，3，2，2，3，1} 另可以用推导：∵x+y=6，y-z=2，消去y得x+z=4 例：集合X={x，y，z，d，e}， R={x，y，y，y，z，d}， S={d，y，y，e，z，x}， 则R?S={x，e，y，e，z，y}， S?R={d，y，z，y}，R?R={x，y，y，y}， S?S={d，e} 例题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} 关系的复合运算不满足交换律，满足结合律。 例题2：设R1和R2是集合X={0，1，2，3}上的关系， R1={I，j|j=I+1或j=I/2}，R2={I，j|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,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，则R(2)是无意义的，因为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)一般是不成立的。因为： (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)=R R(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,2,1,5,2,4,1,3} R(5)={1,2,1,4,2,1,2,3,2,5} 2、关系矩阵：设集合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=1 n 例题3：给定集合A={1，2，3，4，5}，在A上定义两个关系。R={1，2，2，2，3，4}，S={1，3，2，5，3，1，4，2}。求R?S和S?R的矩阵。 解： 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 M R?S= 0 0 0 1 0 1 0 0 0 0 = 0 1 0 0