1、离 散 数 学第二部分 集合论关系论 3 关系的合成关系的合成关系的逆本节主要内容 :关系的合成x是 y的父亲 y是 z的母亲x是 z的什么关系？x是 y的父亲 y是 x的什么关系？设 R 是从集合 X 到集合 Y 的关系，合成关系关系的合成 定义S 是从集合 Y 到集合 Z 的关系。于是，可把从 X 到 Z 的关系 RS 定义成 : RS=|(xX)(zZ)(y)(yY)(R)(S) 通常称 RS 是关系 R 和 S 的 合成关系 。 从 R 和 S 求得 R S 的运算，称为 关系的合成 。 合成关系关系的合成 例 1:R=|x,yI(1)RS=I是整数集合， R,S是 I上的关系S=|x
2、,yI|xI(2)SR= |xI(3)RR=|xI(4)SS= |xI合成关系关系的合成 例 1: I是整数集合， R,S是 I上的关系RS的关系图合成关系关系的合成 例 2:R=|x,yPx是 y的父亲 (1)RR表示的关系是 :P是所有人的集合， R和 S是 P上的关系S=|x,yPx是 y的母亲 xRRy表示 x是 y的祖父(2)RS表示的关系是 : xRSy表示 x是 y的外祖父(3)|x,yPx是 y的祖母 的集合表示为 : SR合成关系关系的合成 注 若 R1的值域与 R2的定义域的交集为空，则 R1R2为空关系 设 IA、 IB分别为 A和 B上的相等关系， R是 A到 B的二元
3、关系则 IAR=RIB=R但 RIA,RIB无意义 在关系图上， R1R2是由 这样的序偶组成，从aA到 cC有一长度为 2的路径，其中第一条弧属于 R1第二条弧属于 R2.给定集合 X,Y,Z 和 W。设 R1是从 X 到 Y 的关系； R2和 R3都是从 Y到 Z的关系， R4是从 Z到 W的关系 ,于是应有：合成关系合成关系的分配率定理 (1) R1(R2 R3)=(R1R2) (R1R3)(3) R1(R2 R3) (R1R2) (R1R3)(4) (R2 R3)R4 (R2R4)(R3R4)(2) (R2 R3 )R4=(R2R4) (R3R4)合成关系证明 : (1) R1(R2 R3)=(R1R2) (R1R3)即证明两个序偶集合相等R1(R2 R3)(y)(R1) ( R2 R3) (y)(R1) (R2 R3) (y)(R1 R2) (R1 R3) (y)(R1 R2) (y)(R1 R3) R1R2R1R2 R1R3 合成关系的分配率 R1R3合成关系合成关系的结合率给定集合 X,Y,Z 和 W。定理(R1R2)R3=R1(R2R3)设 R1是从 X 到 Y 的关系 R2是从 Y到 Z的关系，R3是从 Z到 W的关系 ,于是有：
