图3-11 例3.5.8的关系图
例3.5.9 设A?{1,2,3,4,5}，R?{1,2,1,5,2,2,3,2,3,1,4,3}，画出R的关系图。
解 因为R是A上的关系，故只需画出A中的每个元素即可。如果aiRaj，就画一条由ai到
aj的有向弧。若ai?aj，则画出的是一条自回路。本题的关系图如图3-12所示。
3 2
1 4 5 图3-12 例3.5.9的关系图 关系图主要表达结点与结点之间的邻接关系，故关系图与结点位置和线段的长短无关。 从X到Y的关系R是X?Y的子集，即R?X?Y，而X?Y?(X?Y)?(X?Y)，所以，R?(X?Y)?(X?Y)。令Z?X?Y，则R?Z?Z。因此，我们今后通常限于讨论同一集合上的关系。
3.6 关系的性质及其判定方法
3.6.1 关系的性质
定义3.6.1设R是定义在集合X上的二元关系，如果
（1）对于每一个x?X，都有xRx，则称R是自反的(Reflexive)。即
R在X上自反?(?x)(x?X?xRx) （2）对于每一个x?X，都有xRx，则称R是反自反的(Antireflexive)。即
R在X上反自反?(?x)(x?X?xRx)
（3）对于任意x,y?X，若xRy，就有yRx，则称R是对称的(Symmetric)。即
R在X上对称?(?x)(?y)((x?X)?(y?X)?(xRy)?(yRx))
（4）对于任意x,y?X，若xRy，yRx，必有x?y，则称R在X上是反对称的(Antisymmetric)。即
R在X上反对称?(?x)(?y)((x?X)?(y?X)?(xRy)?(yRx)?(x?y))
（5）对于任意x,y,z?X，若xRy，yRz，就有xRz，则称R在X上是传递的(Transitive)。即
R在X上传递?(?x)(?y)(?z)((x?X)?(y?X)?(z?X)?(xRy)?(yRz)?(xRz))
例3.6.1 设A?{1,2,3}，则集合A上的关系
R1?{1,1,2,2,2,1,3,3}是自反而不是反自反的关系； R2?{1,2,1,3,2,1,2,3}是反自反而不是自反的关系； R3?{1,1,1,3,2,1,2,3}是既不是自反也不是反自反的关系； R4?{1,1,1,3,3,1,2,3,3,2}是对称的而不是反对称的关系； R5?{1,1,1,3,2,1,2,3}是反对称的而不是对称的关系；
84
R6?{1,1,2,2,3,3}是既对称也反对称的关系； R7?{1,2,2,3,3,2}是既不对称也不反对称关系。
R8?{1,1,1,2,2,1,2,2}，R9?{1,2,3,2}是可传递的关系；
R10?{1,2,2,3,1,3,2,1}是不可传递的关系，因为1,2?R10，2,1?R10，但1,1?R10。
由定义3.6.1及例3.6.1可知：
（1）对任意一个关系R，若R自反则它一定不反自反，若R反自反则它也一定不自反；但R不自反，它未必反自反，若R不反自反，也未必自反。
（2）存在着既对称也反对称的关系。
图3-5表明了自反与反自反、对称与反对称性之间的关系。
图3-5
例3.6.2 (1) 集合之间的?关系是自反的、反对称的和可传递的。因为：
1） 对于任意集合A，均有A?A成立，所以?是自反的；
2） 对于任意集合A,B，若A?B且B?A，则A?B，所以?是反对称的； 3） 对于任意集合A,B,C，若A?B且B?C，则A?C，所以?是可传递的。 （2）平面上三角形集合中的相似关系是自反的、对称的和可传递的。因为：任意一个三角形都与自身相似；若三角形A相似于三角形B，则三角形B必相似于三角形A；若三角形A相似于三角形B，且三角形B相似于三角形C，则三角形A必相似于三角形C。
（3）人类的祖先关系是反自反、反对称和可传递的。
（4）实数集上的“>”关系是反自反、反对称和可传递的。 （5）实数集上的“”关系是自反、反对称和可传递的。
（6）实数集上的“=”关系是自反、对称、反对称和可传递的。 （7）人群中的父子关系是反自反和反对称的。
（8）正整数集上的整除关系是自反、反对称和可传递的。 （9）?是反自反、对称、反对称和可传递的。
（10）任意非空集合上的全关系是自反的、对称的和可传递的。 例3.6.3 设整数集Z上的二元关系R定义如下：
R?{x,yx,y?Z,(x?y)/2是整数}，
验证R在Z上是自反和对称的。
证明 ?x?Z,(x?x)/2?0，即x,x?R，故R是自反的。
又设?x,y?Z，如果xRy，即(x?y)/2是整数，则(y?x)/2也必是整数，即yRx，因此R是对称的。
85
3.6.2 由关系图、关系矩阵判别关系的性质
例3.6.4 集合A?{1,2,3,4}，A上的关系R的关系矩阵为：
?1?0???1??0010010110??0?， 1??1?MRR的关系图如图3-6所示。讨论R的性质。
图3-6
解 从R的关系矩阵和关系图容易看出，R是自反的、对称的。 一般地，我们有：
（1）若关系R是自反的，当且仅当其关系矩阵的主对角线上的所有元素都是1；其关系图上每个结点都有自环。
（2）若关系R是对称的，当且仅当其关系矩阵是对称矩阵；其关系图上任意两个结点间若有定向弧，必是成对出现的。
（3）若关系R是反自反的，当且仅当其关系矩阵的主对角线上的元素皆为0；关系图上每个结点都没有自环。
（4）若关系R是反对称的，当且仅当其关系矩阵中关于主对角线对称的元素不能同时为1；其关系图上任意两个不同结点间至多出现一条定向弧。
（5）若关系R是可传递的，当且仅当其关系矩阵满足：对?i,j,k,i?j,j?k，若rij?1 且rjk?1，则rik?1；其关系图满足：对?i,j,k,i?j,j?k，若有弧由ai指向aj，且又有弧由aj指向ak，则必有一条弧由ai指向ak。
例3.6.5 图3-7是由关系图所表示的A?{a,b,c}上的5个二元关系。
（1） （2）
86
（3） （4）
（5）
图3-7
请判断它们的性质。
解 (1) 是反对称、传递但不是对称的关系，而且是既不自反也不反自反的关系； (2) 是自反、传递、反对称的关系，但不是对称也不是反自反的关系； (3) 是反自反但不是对称、不是反对称、不是自反也不是传递的关系；
(4) 是不自反、不反自反但是传递的关系，而且既是对称也是反对称的关系； (5) 是自反、反对称但不是传递、不是对称也不是反自反的关系。
3.7 复合关系和逆关系
3.7.1 复合关系
1. 复合关系的定义
定义3.7.1 设R是从X到Y的关系，S是从Y到Z的关系，则R?S称为R和S的复合关系( Compositive Relation)，表示为
R?S?{x,zx?X?z?Z?(?y)(y?Y?xRy?ySz)}
从R和S求R?S，称为关系的复合运算。
复合运算是关系的二元运算，它能够由两个关系生成一个新的关系，以此类推。例如，R是从X到Y的关系，S是从Y到Z的关系，P是从Z到W的关系，则(R?S)?P是从X到W的关系。
,}B?{2,3,4}的关系，S是由B到C?{3,5,6} 例3.7.1设R是由A?{1,2,3,4到
的关系，分别定义为：
R?{a,b|a?b?6}?{2,4,3,3,4,2} S?{b,c|b整除c}?{2,6,3,3,3,6}
于是复合关系
R?S?{3,3,3,6,4,6}。
例3.7.2 设A是所有人的集合。
R1?{a,b|a,b?A,a是b的兄弟}， R2?{b,c|b,c?A,b是c的父亲}，
87
那么
R1?R2?{a,c|a,c?A,a是c的叔伯}；
而
R2?R2?{a,c|a,c?A,a是c的祖父}。
例3.7.3 设R1和R2是集合A?{0,1,2,3}上的关系，
R1?{i,jj?i?1或j?i/2}，R2?{i,ji?j?2}
（R1?R2）?R1和（R1?R1）?R1。 求R1?R2、R2?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,0,1,1,3,1,1,0,0,2,2}
（R1?R1）?R1?{0,3,0,1,0,2,1,2,0,0,2,3,2,1}
2. 关系的复合运算的性质
定理3.7.1 设R是由集合X到Y的关系，则IX?R?R?IY?R。 定理3.7.2 设R是从X到Y的关系，S是从Y到Z的关系，则有 （1）dom(R?S)?domR （2）ran(R?S)?ranS
（3）若ranR?domS??，则R?S??。 证 （1）和（2）是显然的，下面我们证明（3）。用反证法。
反设R?S??，则必存在x?X,z?Z，使x,z?R?S，从而?y?Y，使
x,y?R,y,z?S，故y?ranR且 y?domS，所以y?ranR?domS，这就与ranR?domS??矛盾，因此，R?S??。
定理3.7.3 （1）设R1、R2和R3分别是从X到Y、Y到Z和Z到W的关系，则
(R1?R2)?R3?R1?(R2?R3)
即关系的复合运算满足结合律。
（2）设R1和R2都是从X到Y的关系，S是从Y到Z的关系，则
1）(R1?R2)?S?(R1?S)?(R2?S) 2）(R1?R2)?S?(R1?S)?(R2?S)
（3）设S是从X到Y的关系，R1和R2都是从Y到Z的关系，则 1）S?(R1?R2)?(S?R1)?(S?R2) 2）S?(R1?R2)?(S?R1)?(S?R2) 证 我们只证明（2），其它证明类似。 1）?x,z?(R1?R2)?S
?(?y)(y?Y?x,y?R1?R2?y,z?S)
88