?(?y)(y?Y?(x,y?R1?x,y?R2)?y,z?S)
?(?y)(y?Y?x,y?R1?y,z?S)?(?y)(y?Y?x,y?R2)?y,z?S) ?x,z?R1?S?x,z?R2?S ?x,z?(R1?S)?(R2?S) 所以 (R1?R2)?S?(R1?S)?(R2?S)
2）?x,z?(R1?R2)?S
?(?y)(y?Y?x,y?R1?R2?y,z?S) ?(?y)(y?Y?x,y?R1?x,y?R2?y,z?S) ?x,z?R1?S?x,z?R2?S ?x,z?(R1?S)?(R2?S) 所以 (R1?R2)?S?(R1?S)?(R2?S)。
注意：一般来说，
（1）(R1?R2)?S?(R1?S)?(R2?S)；
（2）关系的复合运算不满足交换律。
例3.7.4 （1）设A?{a,b,c}，B?{x,y,z}，R1和R2都是从A到B的关系，S是从B到
A的关系，R1?{a,x,a,y}，R2?{a,x,a,z}，S?{x,b,y,c,z,c}，则
(R1?R2)?S?{a,b}，(R1?S)?(R2?S)?{a,b,a,c}，
可见，(R1?R2)?S?(R1?S)?(R2?S)，但(R1?R2)?S?(R1?S)?(R2?S)。
（2）设A?{a,b,c}，R1和R2都是集合A上的关系，R1?{a,b}，R2?{b,a}，则
R1?R2?{a,a}，而R2?R1?{b,b}，所以R1?R2?R2?R1。
由于关系的复合运算满足结合律，所以(R1?R2)?R3?R1?(R2?R3)可以写成R1?R2?R3。一般地，若R1是一由A1到A2的关系，R2是由A2到A3的关系，…，Rn是一由An到An?1的关系，则不加括号的表达式R1?R2???Rn唯一地表示一由A1到An?1的关系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。特别地，当A1?A2???An?1?A ，
R1?R2???Rn?R，即R是集合A上的关系时，复合关系R1?R2???Rn??R??R???R ???n简记作R，它也是集A上的一个关系。
3.7.2 复合关系的矩阵表示及图形表示
因为关系可用矩阵表示，所以复合关系也可用矩阵表示。
已知从集合X?{x1,x2,?,xm}到集合Y?{y1,y2,?,yn}上的关系为R，关系矩阵
MMRn?S???uij?m?n，从集合Y?{y1,y2,?,yn}到集合Z?{z1,z2,?,zp}的关系，关系矩阵????vij?n?p，表示复合关系R?S的矩阵MR?SS可构造如下：
若?yj?Y，使得xi,yj?R且yj,zk?S，则xi,zk?R?S。在集合Y中能够满足这
89
样条件的元素可能不止yj一个，例如另有yj?也满足xi,yj??R且yj?,zk?S。在所有这样的情况下，xi,zk?R?S都是成立的。这样，当我们扫描MR的第i行和MS的第k列时，若发现至少有一个这样的j，使得第i行的第j个位置上的记入值和第k列的第j个位置上的记入值都是1时，则MM?MR?S的第i行和第k列上的记入值为1；否则为0。因此M??wikR?S可以用类似于矩
阵乘法的方法得到：
R?SR?MnS?m?p
其中 wik??(uj?1ij?vjk)
式中?代表逻辑加，满足0?0?0，0?1?1，1?0?1，1?1?1；
?代表逻辑乘，满足0?0?0，0?1?0，1?0?0，1?1?1。
例3.7.5 给定集合A?{1,2,3,4,5}，在集合A上定义两种关系：R?{1,2,3,4,2,2}，
S?{4,2,2,5,3,1,1,3}，求R?S和S?R的矩阵。
解
?0?0???0??0?0??0?0???1??0?0?1100000010000001000000100000000??0??00??0???1??0??0?0???00??0??10??0???0??0??0?0???00001011000100000000000000001000??0??10??0???0??0??0?0???00??0??00??0???0??0??0?0???00010000110000000000000000100001??1?0? ?0?0??0??0?0? ?0?0??MR?SMS?R因为关系可用图形表示，所以复合关系也可用图形表示。
例3.7.6 例3.7.1中的两个关系R与S的复合R?S很容易通过下面的关系图（见图3-8）得到。
图3-8 R?S示意图
由该图立即可得R?S?{3,3,3,6,4,6}。
3.7.3 逆关系
关系是序偶的集合，由于序偶的有序性，关系还有一些特殊的运算。
90
定义3.7.2 设R是从X到Y的二元关系，若将R中每一序偶的元素顺序互换， 得到的集合称为R的逆关系(Inverse Relation)，记为RR?1?1。即
?{y,x?1x,y?R}
例如，在实数集上，关系“<”的逆关系是“>”。 从逆关系的定义，我们容易看出 (R)?1?1?1（1）(R1?R2)?R1?R2 ?1?1?1（2）(R1?R2)?R1?R2
?1?R。
定理3.7.4 设R、R1和R2都是从X到Y的二元关系，则下列各式成立。
(3) (X?Y)?1?Y?X (4) (R)?1?R?1 这里 R?X?Y-R
?1?1?1?1(5) (R1?R2)?R1?R2
证明 （1）x,y?(R1?R2)??1?y,x?R1?R2
y,x?R1?y,x?R2x,y?R1?x,y?R2 x,y?R1?R2?1?1?1?1 ??（4）x,y?(R) ?x,y?R??y,x?R?x,y?R?1y,x?R
?1
（5）因为R1?R2?R1?R2， 故有 (R1?R2)?1?(R1?R2)?1?R1?(R2)?1?1?R1?R2?R1?R2
?1?1?1?1其它自证。
定理3.7.5 设R为从X到Y的关系，S是从Y到Z的关系，则 （1）?R?S??1?S?1?R?1
?1?1（2）R1?R2?R1?R2 证明 （1）z,x?(R?S)?x,z?R?S
?1 ?(?y)(y?Y?x,y?R?y,z?S) ?(?y)(y?Y?y,x?R ?z,x?S?1?1?z,y?S?1)
?1?R?1
所以 (R?S)?S?R
（2）自证。
定理3.7.6 设R是X上的二元关系，则
（1）R是对称的，当且仅当R?R；
?1（2）R是反对称的，当且仅当R?R?IX； （3）R是传递的，当且仅当R?R； （4）R是自反的，当且仅当IX?R；
2?1?1?1 91
（5）R是反自反的，当且仅当IX?R?? 证明 （1）若R是对称的，则对?x,y?X， x,y?R?所以，R?R?1y,x?R?,xy??1 R；
，则对?x,y?X，
y,x?R?1若 R?R?1x,y?R??y,x?R
所以，R是对称的。
（3）若R?R，则对?x,y,z?X，
x,y?R?y,z?R?x,z?R?22x,z?R
所以，R是传递的；
若R是传递的，
?x,z?R?(?y)(y?X?x,y?R?所以，R?R。
其它证明留为作业。
关系R?122y,z?)R?,xz ?R的图形，是关系R图形中将其弧的箭头方向反置。R?1的关系矩阵MR?1是MR的
转置矩阵。
例3.7.7 设R?{1,a,2,b,3,a}是A?{1,2,3}到B?{a,b,c}的二元关系，S是B到
C?{x,y,z}的二元关系，且S?{a,x,b,x,a,y}，求R?S和R?1。
解 R?S?{1,x,1,y,2,x,3,x,3,y} R?1?{a,1,b,2,a, 3 }或从 MR?1??0???1?1??0???10100100??0，M??0?S?1??1???01000??0 ?0??1111?0?0 0?1??0得 MR?S0??1??0?1???0???01??0 ?0??1?0???00???0??0??故取到R?S同样的序元素； 而 M?1??0???0010R?1故取到R同样的序元素。
例3.7.8 给定集合X?{a,b,c}，R是X上的二元关系，R的关系矩阵
?1??1???10111??0 ?1???1MR 92
求R?1和R?R的关系矩阵
?1??0???1?1??1???1?1110011解 MR?11??1 ?1??1??1??0?0??1????11101??1??1?1??1????11111??1?1??MR?R?1
3.8 关系的闭包运算
关系作为集合, 在其上已经定义了并、交、差、补、复合及逆运算。现在再来考虑一种新的关系运算－关系的闭包运算，它是由已知关系，通过增加最少的序偶生成满足某种指定性质的关系的运算。
例如, 设A?{a,b,c}，A上的二元关系R?{a,a,a,b,b,c,c,c}，则A上含R且最小的自反关系是：
r(R)?R?{b,b}；
A上含R且最小的对称关系是：
s(R)?R?{b,a,c,b；}
A上含R且最小的传递关系是：
} t(R)?R?{a,c。
定义3.8.1 设R是X上的二元关系，如果有另一个X上的关系R满足： （1）R是自反的（对称的，传递的）； （2）R?R；
（3）对于任何X上的自反的（对称的，传递的）关系R??，若R???R，就有R???R'。则称关系R为R的自反（对称，传递） 闭包(Reflexive (Symmetric，Transitive) Closure)，记作
r(R)?s?R?,t?R??。
''''显然，自反（对称，传递）闭包是包含R的最小自反（对称，传递）关系。
定理3.8.1 设R是X上的二元关系，那么 （1）R是自反的，当且仅当r?R??R （2）R是对称的，当且仅当s?R??R （3）R是传递的，当且仅当t?R??R 证明 （1）若R是自反的，
R?R，对任何包含R的自反关系R??，有R???R，故r?R??R；
若r?R??R，根据闭包定义，R必是自反的。 （2）、（3）的证明完全类似。
下面讨论由给定关系R，求取R的方法。 定理3.8.2 设R是集合X上的二元关系，则
（1）r?R??R?IX；
' 93