第3章〓关系
集合为描述系统中的各类对象提供了数学工具，而映射为描述事物之间的一种单值依赖关系提供了工具。单值依赖联系是事物之间比较简单的联系，通过这种联系，研究事物的运动规律和状态变化。现实世界中，事物不是孤立的，事物之间都有联系，不仅有单值依赖关系，更有多值依赖关系。“关系”这个概念就提供了一种描述事物之间的多值依赖关系的数学工具。映射是关系的一个特例。这样，集合、映射和关系等概念都是描述自然现象及其相互联系的有力工具，为建立系统和技术过程的数学模型提供了描述工具和方法。

本章系统地研究关系的概念及其性质，将给出关系的定义，特别给出了二元关系的几种等价定义和性质、二元关系的运算，其中特别讨论在计算机科学中具有重要应用的关系闭包运算、等价关系与偏序关系。

3.1关系的概念

数学中“关系”的概念是从自然界中的一般关系里抽象出来的，如父子关系、兄妹关系、国家间的外交关系、整数间的大于关系等。这些都是具体关系，都涉及了一些具体事物和某种性质。因此，关系是事物间的联系，至少指两个事物，并且具有一定的顺序。形式地定义关系如下。 

定义3.1设A和B是两个集合，一个从A×B到{是，否}的映射R称为从A到B的一个二元关系。(a,b)∈A×B，如果(a,b)在R作用下的象为“是”，则a与b符合关系R，记为aRb； 如果(a,b)在R作用下的象为“否”，则a与b不符合关系R，记为aR/b。如果A=B，则称R为A上的二元关系。

令f:A→B，则有Rf:A×B→{是，否}，对于(x,y)∈A×B，xRfy当且仅当f(x)=y。于是，映射f是A到B的一个二元关系。映射是二元关系的特例。于是，映射f作为二元关系仍记为f，x∈A，存在唯一y∈B使f(x)=y，即xfy。但对A到B的任意二元关系R未必有此性质，即对于x∈A，未必有y∈B使xRy。若某个x∈A有y∈B使xRy，那么y也可能不唯一，甚至有多个，乃至无穷多个。 

例3.1整数集合Z上的整除关系记为|。m、n∈Z，m|n当且仅当m能除尽n，于是，|是Z上的二元关系。

在通常的应用中，某个具体的二元关系总是用具体事物之间的某种联系来确定。由于直观的联系并不总是清楚的，因此有必要给出一个精确的定义。当抽去事物的属性和联系的属性时，剩下的就是一个序对对应的是“是”还是“否”了。于是，有二元关系的更形式化的等价定义如下。 

定义3.2设A和B是两个集合，A×B的任一子集R称为从A到B的一个二元关系。如果(a,b)∈R，则a与b符合关系R，记为aRb； 如果(a,b)R，则a与b不符合关系R，记为aR/b。如果A=B，则称R为A上的二元关系。

定义3.1说明了二元关系就是某种性质，而定义3.2告诉我们，这种性质就是A×B的一个子集，即满足这种性质的那些序对的集合。从形式逻辑角度看，定义3.1是使用揭示事物内涵的方法来定义二元关系的，而定义3.2是使用揭示二元关系的外延的方法来定义二元关系的，因此定义3.2比定义3.1更抽象。在抽象讨论二元关系时，使用定义3.2比较方便，在讨论具体问题中的具体二元关系时，使用定义3.1比较方便。

按照定义3.2，A×B的任一子集R都是从A到B的二元关系。若|A|=m，|B|=n，则|A×B|=m×n，A×B共有2m×n个子集，所以，从A到B的二元关系共有2m×n个。

特别地，A×B也是从A到B的二元关系，而空集称为从A到B的空关系，集合{(a,a)|a∈A}称为A上的恒等关系或相等关系，记为IA。

定义3.3设二元关系RA×B，集合{x|x∈A且y∈B使(x,y)∈R}称为R的定义域，并记为dom(R)； 而集合{y|y∈B且x∈A使(x,y)∈R}称为R的值域，并记为ran(R)。

一般地，dom(R)A，ran(R)B。






例3.2集合A={1,2,3,4}上的关系R={(1,2),(1,3),(1,4),(2,4),(4,4)}，则

dom(R)={1,2,4}，ran(R)={2,3,4}。

在日常生活以及数学、计算机科学中，常常要考虑3个事物、4个事物等之间的联系，例如，在考虑城市之间的位置关系时，长春位于哈尔滨和沈阳之间。因此，有必要将关系的概念推广到n元关系。

定义3.4设A1,A2,…,An是n个集合，A1×A2×…×An的一个子集R称为A1,A2,…,An间的一个n元关系，每个Ai称为R的一个域。

在数据库中，把n元关系R看成一个二维表，表中的每一行是关系R的一个n元组，表中有n列，每一列取一个名字，称为属性，而每个域Ai就是对应属性的取值范围，或者说是Ai代表的属性。因此，以A1,A2,…,An为属性的n元关系R，记为R(A1,A2,…,An)，称为一个关系模式。n元关系是关系数据模型的核心，而关系数据模型是关系数据库的基础。

例3.3设A1为某单位的职工姓名的集合，A2为性别的集合，A3为年龄的集合，A4为学历的集合，A5为工资的集合。于是，表3.1就是该单位的职工情况表，它是A1,A2,…,A5间的一个五元关系。


表3.1



姓名性别年龄学历工资

冯霆
男
21
高中
1800
赵悦
女
24
本科
2300
蒋睿
女
29
本科
2900
周枫
男
33
硕士研究生
3600

由于在数学和计算机科学中主要使用二元关系，因此，本章以后各节主要讨论二元关系的运算及性质。

习题

1. 用枚举法表示从A到B的二元关系R。

(1) A={0,1,2}，B={0,2,4}，R={(x,y)|x,y∈A∩B}。 

(2) A={1,2,3,4,5}，B={1,2,3}，R={(x,y)|x=y2}。

2. 用枚举法表示A={0,1,2,3,4}上的二元关系R。

(1) R={(x,y)|x+y=4}。 

(2) R={(x,y)|x=2y}。

3. 设A={1,2,3,4}上的二元关系R={(1,2),(2,4),(3,3)}，S={(1,3),(2,4),(4,2)}。

(1) 求R∪S，R∩S，R＼S，Rc。 

(2) 求dom(R)、ran(S)、dom(R∪S)、ran(R∪S)。

4. 证明： 集合A上的任意二元关系R和S，有：

(1) dom(R∪S)=dom(R)∪dom(S)； 

(2) ran(R∩S)=ran(R)∩ran(S)。

5. 设A是n个元素的集合，证明A上有2n2个二元关系。

3.2关系矩阵和关系图

关系的概念对于计算机科学以及其他学科极其重要，因此，如何表示关系，使其直观、形象、便于计算机处理就显得十分重要。关系图及关系矩阵就是针对上述需要而提出来的，关系图直观形象，具有启发性； 关系矩阵便于计算机存储与处理。本节介绍有穷集合上二元关系的关系矩阵及关系图。

定义3.5设有穷集合A={a1,a2,…,an}和B={b1,b2,…,bm}，R是从A到B的一个二元关系，R的关系矩阵定义为一个n×m矩阵M=(mij)，其中

mij=1aiRbj0aiR/bj

例3.4集合A={1,2,3}和B={a,b,c,d}，从A到B的一个二元关系R={(1,b),(1,c),(2,a),(2,c),(3,b)}，则R的关系矩阵为

M=011010100100

例3.5集合A={a,b,c,d}，A上的一个二元关系R={(a,a),(a,b),(a,c),(b,b),(b,d),(c,a),(c,c)}，则R的关系矩阵为

M=1110010110100000

显然，从A到B的一个二元关系R的矩阵是以0或1为项的矩阵，这种矩阵称为布尔矩阵。在建立R的矩阵时，首先要确定集合A和B中元素的顺序，一般情况下，不同的元素顺序得到的矩阵是不相等的，但是都能忠实地反映关系的全部信息。尽管不同的元素顺序得到的关系矩阵不相同，但是可以相互转化，就是在行和列的同样变换下，可以将一种矩阵表示变为另一种矩阵表示。

对于具体的关系R，如何确定元素的顺序，使关系矩阵成为某种形式的简单矩阵，要根据关系R的具体情况而定。关系矩阵包含关系的全部信息，从关系矩阵很容易看出关系具有某些性质。

关系除了可以用关系矩阵表示外，还可以用关系图表示。从有穷集合A到有穷集合B的二元关系R用图表示时，首先用点表示A和B的元素，并在旁边标注元素的名字，然后用从点x到点y的矢线表示R中的序对(x,y)。若(x,x)∈R，则画一条从点x指向自身的线，称为环。这样由点和线组成的有向图称为R的关系图。

例3.6例3.4中的关系R的关系图如图3.1(a)所示，例3.5中的关系R的关系图如图3.1(b)所示。



图3.1


关系图也包含关系的全部信息，而且直观、形象，从关系图可以很容易地看出关系的一些性质。

习题

1. 画出下列二元关系的关系图。

(1) A={0,1,2,3,4}，R:A→A，R={(x,y)|x2=y}。 

(2) A={1,2,3,4}，R:A→A，R={(x,y)|x=2y}。 

(3) A={1,2,3},B={4,5,6,7,8}，R:A→B，R={(x,y)|x∈A,y∈B,x+y=8}。 

(4) A={5,6,7,8},B={1,2,3}，R:A→B，R={(x,y)|x∈A,y∈B,1≤x-y＜7}。

2. 写出下列二元关系的关系矩阵。

(1) A={1,2,3}，R:A→A，R={(1,2),(2,2),(3,1)}。 

(2) A={1,2,3,4,5}，R:A→A，R={(x,y)|x＜y或x是质数}。 

(3) A={1,2,3,4,5,6}，R:A→A，R={(x,y)|2x=y}。 

(4) A={1,2,3},B={4,5,6,7,8}，R:A→B，R={(1,5),(1,7),(2,4),(2,8),(3,6)}。

3.3关系的性质

在实际问题中，我们感兴趣的关系往往具有一些特殊的性质，如自反性、反自反性、对称性、反对称性、传递性等。本节讨论集合A上的二元关系R可能具有的一些特殊性质。

定义3.6集合A上的二元关系R称为自反的，如果x∈A，则有xRx。

在这个定义中要求A的每个元素x都有xRx，即(x,x)∈R，这并不排斥某个序对(x,y)，当x≠y时，仍有(x,y)∈R。显然，R是自反的，当且仅当IAR。

例3.7集合A上的恒等关系IA是自反的，但IA的任一真子集均不是A上的自反关系。

例3.8集合A={1,2,3}上的二元关系R={(1,1),(1,2),(2,2),(2,3),(3,2),(3,3)}是自反的，S={(1,1),(1,2),(2,2),(2,3),(3,2)}不是自反的，T={(1,3),(2,3)}也不是自反的。

定义3.7集合A上的二元关系R称为反自反的，如果x∈A，则有xR/x。

显然，R是反自反的，当且仅当R∩IA=。

例3.9自然数集上的小于关系是反自反的。

例3.10例3.8中R不是反自反的，S也不是反自反的，但T是反自反的。

显然，非空集合上的一个二元关系是自反的，必不是反自反的； 反之亦然。但是，一个二元关系不是自反的，未必是反自反的； 反之亦然，即存在既不是自反的也不是反自反的二元关系。

定义3.8集合A上的二元关系R，如果x、y∈A，只要xRy就有yRx，则称R是对称的。

例3.11人之间的朋友关系是对称的。

例3.12集合A={1,2,3}上的二元关系R={(1,2),(1,3),(2,1),(2,2),(3,1)}是对称的，S={(1,2),(2,1),(2,3)}不是对称的，T={(1,1),(1,2),(2,3)}也不是对称的。

定义3.9集合A上的二元关系R，对x、y∈A，如果xRy且yRx，则x=y，则称R是反对称的。

例3.13集合A上的恒等关系IA是对称的，也是反对称的。

例3.14例3.12中R不是反对称的，S也不是反对称的，T是反对称的。

显然，二元关系的对称性和反对称性不是矛盾的，即存在既是对称的也是反对称的二元关系。

例3.15证明： 集合A上的二元关系R既是对称的也是反对称的，当且仅当RIA。

证若RIA，则显然R既是对称的也是反对称的。

若R既是对称的也是反对称的，则对于xRy，由R的对称性有yRx，再由R的反对称性有x=y。这表明xRy均有x=y，故(x,y)∈R均为(x,x)∈R，从而(x,x)∈IA，因此RIA。证毕。

定义3.10集合A上的二元关系R，对x、y、z∈A，如果xRy且yRz，则xRz，那么称R是传递的。

例3.16整数集合上的整除关系是传递的。

例3.17集合A={1,2,3}上的二元关系R={(1,2),(1,3),(2,3),(3,3)}是传递的，S={(1,3),(3,2),(3,3)}不是传递的，T={(1,2),(2,1)}也不是传递的。

例3.18集合A上的二元关系R，若R=，则R是反自反的、对称的和传递的。但是，若R≠且R是反自反的、对称的，则R不是传递的。

实际上，因为R≠，所以，x,y∈A使xRy，由R的对称性得yRx。若假设R是传递的，则xRx，这与R是反自反的矛盾。因此，R不是传递的。

在3.2节中指出关系矩阵和关系图均包含了关系的全部信息，从中可以看出关系具有某些性质，对于集合A上的二元关系R，R的关系矩阵为M，R的关系图为G，则

(1) R是自反的，当且仅当M的对角线上的全部元素均为1；

(2) R是反自反的，当且仅当M的对角线上的全部元素均为0；

(3) R是对称的，当且仅当M是对称矩阵；

(4) R是反对称的，当且仅当i≠j时，M中的元素mij与mji不同时为1；

(5) R是传递的，当且仅当M中的元素mij=1且mjk=1时，必有mik=1；

(6) R是自反的，当且仅当G的每个顶点上均有一个环；

(7) R是反自反的，当且仅当G中没有环；

(8) R是对称的，当且仅当G中任两不同的顶点之间有矢线，则必有两条方向相反的矢线；

(9) R是反对称的，当且仅当G中任两顶点之间最多有一条矢线；

(10) R是传递的，当且仅当G中从某顶点i沿矢线方向经两条矢线可到达另一顶点j，则必有从顶点i到顶点j的矢线。

由于二元关系是序对的集合，故有关集合的运算对二元关系也适用。特别是这些运算的交换律、结合律等运算律是运算本身所决定的，因此，在对二元关系进行集合运算时，各运算律保持不变。而关系的性质在关系的集合运算下是否能够保持呢？

例3.19集合A上的两个二元关系R和S，若R和S均是自反的，则R∩S和R∪S分别是自反的吗？

解若R和S均是自反的，则R∩S和R∪S分别是自反的。下面予以证明。

对于x∈A，因为R是自反的，所以(x,x)∈R。因为S是自反的，所以(x,x)∈S。可得(x,x)∈R∩S，因此R∩S是自反的。

对于x∈A，因为R是自反的，所以(x,x)∈R，可得(x,x)∈R∪S，因此R∪S是自反的。证毕。

例3.20集合A上的两个二元关系R和S，若R和S均是对称的，则R∩S和R∪S分别是对称的吗？

解若R和S均是对称的，则R∩S和R∪S分别是对称的。下面予以证明。

对于x、y∈A，若(x,y)∈R∩S，则(x,y)∈R且(x,y)∈S。因为R是对称的，所以(y,x)∈R。因为S是对称的，所以(y,x)∈S。可得(y,x)∈R∩S，因此R∩S是对称的。

对于x,y∈A，若(x,y)∈R∪S，则(x,y)∈R或(x,y)∈S。

若(x,y)∈R，因为R是对称的，所以(y,x)∈R，可得(y,x)∈R∪S。

若(x,y)∈S，因为S是对称的，所以(y,x)∈S，可得(y,x)∈R∪S。

因此R∪S是对称的。证毕。

例3.21集合A上的两个二元关系R和S，若R和S均是传递的，则R∩S和R∪S分别是传递的吗？

解若R和S均是传递的，则R∩S是传递的，但R∪S不一定是传递的。

实际上，对于x、y、z∈A，若(x,y)∈R∩S且(y,z)∈R∩S，则(x,y)∈R、(x,y)∈S、(y,z)∈R、(y,z)∈S。

因为R是传递的，所以，由(x,y)∈R、(y,z)∈R，可得(x,z)∈R。

因为S是传递的，所以，由(x,y)∈S、(y,z)∈S，可得(x,z)∈S。

因此(x,z)∈R∩S，于是，R∩S是传递的。

然而，对于集合A={1,2,3，4}上的二元关系R={(1,2),(1,3),(2,3)}和S={(1,1),(4,3)}，有R∪S={(1,1),(1,2),(1,3),(2,3),(4,3)}，这时，R和S均是传递的，R∪S也是传递的。

对于集合A={1,2,3}上的二元关系R={(1,2),(1,3),(2,3)}和S={(3,2)}，有R∪S={(1,2),(1,3),(2,3),(3,2)}，这时，R和S均是传递的，但R∪S不是传递的。

习题

1. 确定整数集合Z上的等于关系、小于等于关系、小于关系、整除关系具有哪些性质，将结果填入表3.2中。

表3.2



关 系 类 型自反性反 自 反 性对称性反 对 称 性传递性

等于关系

小于等于关系

小于关系

整除关系


2. 集合A上的两个二元关系R和S，若R和S均是反自反的，则R∩S和R∪S分别是反自反的吗？证明你的断言。

3. 集合A上的两个二元关系R和S，若R和S均是反对称的，则R∩S和R∪S分别是反对称的吗？证明你的断言。

4. 设R是集合A上的反自反的和传递的二元关系。证明： R是反对称的。

5.  (1) 找一个非空最小集合，在其上定义一个既不是自反的也不是反自反的关系。

(2) 找一个非空最小集合，在其上定义一个既不是对称的也不是反对称的关系。

(3) 若(1)和(2)允许用空集合，结果将会怎样？

6. 问在基数为n的有限集A上，有多少种不同的自反关系、反自反关系、对称关系和反对称关系？

3.4复合关系和逆关系

关系是映射的推广，所以，关系还有两种有用的运算，即复合运算和逆运算。

关系的复合运算，也称为合成运算，是来自日常生活的实践和数学的实践。例如，由母子关系和夫妻关系的存在，产生了婆媳关系。

定义3.11设R是A到B的二元关系，S是B到C的二元关系，则R与S的复合关系为一个从A到C的二元关系，记为RS，并且

RS={(x,z)|x∈A,z∈C,y∈B使xRy且ySz}。

例3.22设集合A={1,2,3,4,5}上的二元关系R={(1,2),(2,2),(3,4)}，S={(2,5),(3,1),(4,2)}，T={(2,4),(5,1),(5,2)}，则

RS={(1,5),(2,5),(3,2)}，SR={(3,2),(4,2)}，

ST={(2,1),(2,2),(4,4)}，RR={(1,2),(2,2)}，

(RS)T={(1,1),(1,2),(2,1),(2,2),(3,4)}，

R(ST)={(1,1),(1,2),(2,1),(2,2),(3,4)}。

可见，关系的复合运算既不满足交换律，也不满足幂等律，但是关系的复合运算满足结合律。

定理3.1设R、S、T分别是集合A到B、B到C和C到D的二元关系，则(RS)T=R(ST)。

证设(a,d)∈(RS)T，则c∈C使(a,c)∈RS 且(c,d)∈T。

由(a,c)∈RS，则b∈B使(a,b)∈R 且(b,c)∈S。

由(b,c)∈S和(c,d)∈T得(b,d)∈ST，再由(a,b)∈R和(b,d)∈ST得(a,d)∈R(ST)，因此(RS)TR(ST)。

反之，设(a,d)∈R(ST)，则b∈B使(a,b)∈R，(b,d)∈ST。

由(b,d)∈ST，则c∈C使(b,c)∈S且(c,d)∈T。

由(a,b)∈R和(b,c)∈S得(a,c)∈RS，再由(a,c)∈RS和(c,d)∈T得(a,d)∈(RS)T。因此，R(ST)(RS)T。

于是(RS)T=R(ST)。证毕。

设R是A上的一个二元关系，递归地定义R的非负整数次幂为 

R0=IA，R1=R，Rn+1=RnR

由于关系的复合运算满足结合律，因此，容易证明定理3.2。

定理3.2设R是A上的一个二元关系，对任意的非负整数m、n，有

RmRn=Rm+n，(Rm)n=Rmn

定理3.3设A是一个有限集且|A|=n，R是A上的一个二元关系，则存在非负整数s，t使0≤s＜t≤2n2且Rs=Rt。

证因为|A|=n，所以|A×A|=n2，从而|2A×A|=2n2，故A上共有2n2个不同的二元关系。而R0，R，R2，…，R2n2是A上的2n2+1个二元关系，由抽屉原理得至少有两个关系是相等的，因此，存在非负整数s,t使0≤s＜t≤2n2且Rs=Rt。证毕。

定理3.4设R是A到B的二元关系，则

IAR=RIB=R

该定理的证明作为习题。

定理3.5设R1是A到B的二元关系，R2和R3是B到C的二元关系，R4是C到D的二元关系，则

(1) R1(R2∪R3)=(R1R2)∪(R1R3)；

(2) R1(R2∩R3)=(R1R2)∩(R1R3)；

(3) (R2∪R3)R4=(R2R4)∪(R3R4)；

(4) (R2∩R3)R4=(R2R4)∩(R3R4)。

证(1) 设(a,c)∈R1(R2∪R3)，则b∈B使(a,b)∈R1且(b,c)∈R2∪R3。

由(b,c)∈R2∪R3得(b,c)∈R2或(b,c)∈R3。

若(b,c)∈R2，有(a,c)∈R1R2； 若(b,c)∈R3，有(a,c)∈R1R3。所以，(a,c)∈(R1R2)∪(R1R3)。因此，R1(R2∪R3)(R1R2)∪(R1R3)。

反之，设(a,c)∈(R1R2)∪(R1R3)，则(a,c)∈R1R2或(a,c)∈R1R3。

所以，b∈B使(a,b)∈R1且(b,c)∈R2，或b∈B使(a,b)∈R1且(b,c)∈R3。

由(b,c)∈R2或(b,c)∈R3得(b,c)∈R2∪R3，所以(a,c)∈R1(R2∪R3)。因此(R1R2)∪(R1R3)R1(R2∪R3)。

于是R1(R2∪R3)=(R1R2)∪(R1R3)。

(2)(3)(4)的证明类似于(1)的证明。证毕。

关系的复合运算可以使用矩阵运算实现。由于关系矩阵是布尔矩阵，因此，在集合{0,1}上定义交运算(∧)和并运算(∨)，运算表见表3.3。

表3.3



∧01∨01

000001
101111


设X和Y是两个布尔矩阵，X与Y的交运算是X与Y的对应元素的交运算，记为X∧Y=(xij∧yij)，而X与Y的并运算是X与Y的对应元素的并运算，记为X∨Y=(xij∨yij)。

设X=(xij)为m×p布尔矩阵，Y=(yij)为p×n布尔矩阵，则X与Y的布尔乘法定义为： XY=(zij)为m×n矩阵，其中zij=∨pk=1(xik∧ykj)。显然，布尔乘法运算是可结合的。

设R和S都是A到B的二元关系，其关系矩阵分别为MR和MS，R∪S与R∩S的关系矩阵分别记为MR∪S和MR∩S，易证： MR∪S=MR∨MS，MR∩S=MR∧MS。

设R是A到B的二元关系，S是B到C的二元关系，其关系矩阵分别为MR和MS，RS的关系矩阵记为MRS，易证： MRS=MRMS。

例3.23设MR=100100011，MS=110100001，则MRS=110110101。

定义3.12设R是A到B的二元关系，则从B到A的二元关系R-1={(y,x)|(x,y)∈R}称为R的逆关系。

例3.24设集合A={1,2,3}，B={a,b,c}，R={(1,a),(2,c),(3,a),(3,b)}，则R-1={(a,1),(c,2),(a,3),(b,3)}。

定理3.6设R是A到B的二元关系，则(R-1)-1=R。

证(x,y)∈(R-1)-1，由逆关系的定义得(y,x)∈R-1，从而(x,y)∈R，所以(R-1)-1R。

反之，(x,y)∈R，由逆关系的定义得(y,x)∈R-1，从而(x,y)∈(R-1)-1，所以R(R-1)-1。

因此(R-1)-1=R。证毕。

定理3.7设R和S分别是A到B、B到C的二元关系，则

(RS)-1=S-1R-1

证(z,x)∈(RS)-1，由逆关系的定义得(x,z)∈RS，从而y∈B使(x,y)∈R且(y,z)∈S。再由逆关系的定义得(y,x)∈R-1且(z,y)∈S-1。

根据复合关系的定义，(z,x)∈S-1R-1。所以，(RS)-1S-1R-1。

反之，(z,x)∈S-1R-1，由复合关系的定义得y∈B使(z,y)∈S-1且(y,x)∈R-1，从而由逆关系的定义得(y,z)∈S且(x,y)∈R。再由复合关系的定义得(x,z)∈RS。

根据逆关系的定义得(z,x)∈(RS)-1。所以S-1R-1(RS)-1。

因此(RS)-1=S-1R-1。证毕。

关系的逆运算也可以使用矩阵运算实现，逆关系R-1的关系矩阵MR-1是关系R的关系矩阵MR的转置矩阵，即MR-1=(MR)T。

例3.25设MR=100100011，则MR-1=110001001。

例3.26集合A上的两个二元关系R和S，若R和S均是自反的，则RS和R-1分别是自反的吗？

解若R和S均是自反的，则RS和R-1分别是自反的。下面予以证明。

对于x∈A，因为R是自反的，所以(x,x)∈R。因为S是自反的，所以(x,x)∈S。可得(x,x)∈RS，因此RS是自反的。

对于x∈A，因为R是自反的，所以(x,x)∈R，可得(x,x)∈R-1，因此R-1是自反的。证毕。

例3.27集合A上的两个二元关系R和S，若R和S均是对称的，则RS和R-1分别是对称的吗？

解若R和S均是对称的，则RS不一定是对称的。

对于集合A={1,2,3}上的二元关系R={(1,2),(2,1),(3,3)}和S={(1,1),(2,2)}，有RS={(1,2),(2,1)}，这时，R和S均是对称的，RS也是对称的。

对于集合A={1,2,3}上的二元关系R={(1,2),(2,1),(3,3)}和S={(2,3),(3,2)}，有RS={(1,3),(3,2)}，这时，R和S均是对称的，但RS不是对称的。

R是对称的，则R-1是对称的。下面予以证明。

对于x,y∈A，若(x,y)∈R-1，则(y,x)∈R。因为R是对称的，所以(x,y)∈R。根据逆关系的定义得(y,x)∈R-1，因此R-1是对称的。证毕。

习题

1. 设集合A={1,2,3,4}上的二元关系R={(i,j)|j=i+1或j=i/2}，S={(i,j)|i=j+2}，求RS、SR、R2、S3。

2. 设R是A到B的二元关系，证明： IAR=RIB=R。

3. 设R和S都是集合A上的二元关系，判断下列命题正确与否，并证明之。

(1) 若R和S都是反自反的，则RS亦是反自反的。 

(2) 若R和S都是反对称的，则RS亦是反对称的。 

(3) 若R和S都是传递的，则RS亦是传递的。

4. 设R是集合A上的二元关系，当R分别为反自反的、反对称的和传递的时，R-1是否也相应地为反自反的、反对称的和传递的？并证明之。

5. 设A={a,b,c}，R和S都是A上的二元关系，其关系矩阵为 

MR=110010001，MS=101010110 

求MRS、MR(S-1)、M(RS)-1。


3.5关系的闭包

关系的另一种重要的运算是闭包运算，闭包运算是一元运算。通过闭包运算能够利用已知的关系得到另一个复杂的关系。引入闭包运算的一个目的是在已知的关系上进行扩大使得到的新关系具有所需要的性质。闭包运算包括传递闭包、自反闭包和对称闭包等，在计算机科学中，传递闭包、自反传递闭包具有极其重要的应用。

定义3.13设R是A上的一个二元关系，A上一切包含R的传递关系的交称为R的传递闭包，记为R+，即

R+= ∩RR′R′传递R′

于是，R+是包含R的那些传递关系中最小的那个关系。

定理3.8二元关系R的传递闭包R+是传递关系。

证设R是A上的一个二元关系，(x,y)∈R+且(y,z)∈R+，由传递闭包的定义，对每个包含R的传递关系R′，(x,y)∈R′且(y,z)∈R′，由于R′的传递性使得(x,z)∈R′，从而(x,z)∈R+，因此，R+是传递关系。证毕。

由传递闭包的定义，若R是传递的，则R+=R。

定理3.9设R是A上的一个二元关系，则

R+=∪∞i=1Ri=R∪R2∪R3∪…

证首先证明R+∪∞i=1Ri。

由传递闭包的定义，只需证明∪∞i=1Ri是包含R的传递关系。而显然有R∪∞i=1Ri。

下面证明∪∞i=1Ri是传递关系。

设(x,y)∈∪∞i=1Ri且(y,z)∈∪∞i=1Ri，则存在正整数m和n使(x,y)∈Rm且(y,z)∈Rn，于是(x,z)∈RmRn=Rm+n，从而(x,z)∈∪∞i=1Ri，所以∪∞i=1Ri是传递关系。

其次证明∪∞i=1RiR+。

设(x,y)∈∪∞i=1Ri，则存在正整数m使(x,y)∈Rm。若m=1，则(x,y)∈RR+； 若m＞1，则z1,z2,…,zm-1∈A使(x,z1)∈R，(z1,z2)∈R，…，(zm-1,y)∈R。

因为RR+，所以，(x,z1)∈R+，(z1,z2)∈R+，…，(zm-1,y)∈R+。由定理3.8知R+是传递关系，得(x,y)∈R+，于是∪∞i=1RiR+。

因此R+=∪∞i=1Ri。证毕。

定理3.10设A是n元集，R是A上的一个二元关系，则

R+=∪ni=1Ri

证只需证明对任意自然数k＞n有Rk∪ni=1Ri。

设(x,y)∈Rk，则z1,z2,…,zk-1∈A使(x,z1)∈R，(z1,z2)∈R，…，(zk-1,y)∈R。因为x,y,z1,z2,…,zk-1是A的k+1个元素，而A是n元集，由k＞n得x,y,z1,z2,…,zk-1中必有两个相等的元素。

记x=z0,y=zk，设zi=zj(0≤i＜j≤k)，于是(x,z1)∈R，…，(zi-1,zi)∈R，(zj,zj+1)∈R，…，(zk-1,y)∈R，故(x,y)∈Rk-(j-i)，令p1=k-(j-i)，则p1＜k。若p1＞n，则重复上述论述，有p2＜p1使(x,y)∈Rp2。如此进行下去，必有m≤n使(x,y)∈Rm。于是Rk∪ni=1Ri。

因此R+=∪ni=1Ri。证毕。

例3.28设A是人的集合，R是A上的“父子”关系，则(x,y)∈R+当且仅当存在正整数n使(x,y)∈Rn，即y是x的后代，因此，R+为A上的“后代子孙”关系。另外，根据传递闭包运算可以由“直接领导”关系得到“间接领导”关系。

传递闭包运算可以使用矩阵运算实现，即MR+=∨ni=1MRi=MR∨MR2∨…∨MRn。

例3.29设MR=0110001100000000，求MR+。

解MR2=0011000000000000，MR3=0000000000000000，MR4=0000000000000000

则


MR+=∨4i=1MRi=MR∨MR2∨MR3∨MR4=0111001100000000

定义3.14设R是A上的一个二元关系，A上包含R的所有自反且传递的二元关系的交称为R的自反传递闭包，记为R*。

由自反传递闭包的定义可知，R*是自反且传递的二元关系。

定理3.11设R是A上的一个二元关系，则

R*=R0∪R+

证显然R0∪R+是A上的自反传递关系，由自反传递闭包的定义得R*R0∪R+。

下面证明R0∪R+R*。

设(x,y)∈R0∪R+，则当x=y时，(x,x)∈R0； 当x≠y时，(x,y)∈R+，故对每个包含R的传递关系R′有(x,y)∈R′，于是(x,y)∈R0∪R′。

又包含R的每个自反传递关系S是包含R的传递关系，因此(x,y)∈S，(x,y)∈R*，从而R0∪R+R*。

因此R*=R0∪R+。证毕。

于是R*=∪ni=0Ri。

定理3.11表明了传递闭包与自反传递闭包的联系比较简单。

例3.30设R是自然数集合N上的“后继”关系，即(x,y)∈R当且仅当x+1=y，易得R+为“小于”关系，R*为“小于等于”关系。

传递闭包和自反传递闭包在计算机科学中应用较多。除了传递闭包和自反传递闭包外，还有其他的闭包，如自反闭包和对称闭包等，它们在计算机科学中不常用，在此仅简单作一介绍。

定义3.15A上的二元关系R的自反闭包是A上包含R的所有自反关系的交，记为r(R)，易知

r(R)=R0∪R

而且R是自反的，当且仅当r(R)=R。

例3.31设集合A={1,2,3}上的二元关系R={(1,2),(2,3),(3,3)}，则r(R)={(1,1),(1,2),(2,2),(2,3),(3,3)}。

定义3.16A上的二元关系R的对称闭包是A上包含R的所有对称关系的交，记为s(R)，易知

s(R)=R∪R-1

而且R是对称的，当且仅当s(R)=R。

例3.32设集合A={1,2,3}上的二元关系R={(1,2),(2,3),(3,3)}，则s(R)={(1,2),(2,1),(2,3),(3,2),(3,3)}。

习题

1. 设A={1,2,3,4,5}上的二元关系R={(1,2),(2,3),(3,1),(3,4),(4,5)}，求R+和R*。

2. 设R是A上的二元关系，证明： 

(1) (R+)+=R+； 

(2) (R*)*=R*； 

(3) RR*=R*R=R+； 

(4) (R+)*=(R*)+=R*。

3. 是否存在A(|A|=n)上的二元关系R使R,R2,…,Rn两两不相等？

4. 设R是A上的二元关系，证明： 若R是对称的，则R+也是对称的。

5. 设R是A上的二元关系，证明： R的传递闭包可定义为： 

(1) 若(a,b)∈R，则(a,b)∈R+； 

(2) 若(a,b)∈R+且(b,c)∈R，则(a,c)∈R+； 

(3) 除了(1)和(2)的序对之外，R+再无别的序对。

3.6等价关系与集合的划分

本节讨论一种重要的二元关系，就是等价关系，它具有很好的性质，等价关系在数学和计算机科学中有极其重要的应用。

定义3.17设R为集合A上的二元关系，若R是自反的、对称的和传递的，则称R为等价关系。

例3.33平面上三角形集合中，三角形的相似关系是等价关系。

例3.34试证明： 整数集合Z上的模k同余关系R={(x,y)|x,y∈Z,x≡y(mod k)}是等价关系，其中x≡y(mod k)表示x除以k所得的余数与y除以k所得的余数相等。

证(1) 对x∈Z有x≡x(mod k)，所以(x,x)∈R，因此，R是自反的。

(2) 对x、y∈Z，若(x,y)∈R，有k|x-y，则k|y-x，所以(y,x)∈R，因此，R是对称的。

(3) 对x、y、z∈Z，若(x,y)∈R且(y,z)∈R，有k|x-y且k|y-z，则k|x-z，所以(x,z)∈R，因此，R是传递的。

故R是等价关系。证毕。

定义3.18设R为集合A上的等价关系，对任何x∈A，集合［x］={y|y∈A,(x,y)∈R}称为元素x关于R的等价类。

x关于R的等价类也可记为Ex={y|y∈A,(x,y)∈R}。

由等价类的定义，x′∈［x］，则［x′］=［x］。

例3.35整数集合Z上的模3同余关系R={(x,y)|x,y∈Z,x≡y(mod 3)}有3个等价类，即{…,-6,-3,0,3,6,…}、{…,-5,-2,1,4,7,…}、{…,-4,-1,2,5,8，…}。

定义3.19
设A为集合，若A的一些非空子集形成的集族X={A1,A2,…,Am}具有性质： 

(1) Ai、Aj∈X，若Ai≠Aj，则Ai∩Aj=。

(2) ∪Ai∈XAi=A。

则称X为A的一个划分。

若X为A的一个划分，当|X|=m时，称X为A的一个m划分。

例3.36若A={1,2,3,4,5,6}，则X={{1,2,3，4},{5,6}}是A的一个划分。

例3.37{{…,-6,-3,0,3,6,…},{…,-5,-2,1,4,7,…},{…,-4,-1,2,5,8，…}}是整数集合Z的一个划分，它是Z的一个3划分。

定理3.12设R是集合A上的一个等价关系，则R的所有等价类的集合是A的一个划分。

证等价关系R的所有等价类的集合为X，对于x∈A，由于R是自反的，得x∈［x］，故R的每个等价类是A的非空子集。

首先，对于Ai、Aj∈X，即Ai、Aj是R的两个等价类，假设Ai≠Aj，且Ai∩Aj≠，则x∈Ai∩Aj。对于y∈Ai，由等价类的定义，(x,y)∈R，所以y∈Aj，故AiAj。类似地，对于z∈Aj，由等价类的定义，(x,z)∈R，所以z∈Ai，故AjAi。因此Ai=Aj。这与假设Ai≠Aj矛盾，从而Ai∩Aj=。于是，Ai与Aj或相等或不相交。

其次，对于x∈A，［x］={y|y∈A,(x,y)∈R}是R的一个等价类，所以［x］∈X，因此，x∈A，x∈∪Ai∈XAi。所以∪Ai∈XAi=A。于是，X是A的一个划分。证毕。

定理3.13设X是集合A的一个划分，则R=∪Ai∈XAi×Ai是A上的一个等价关系，且X就是R的所有等价类的集合。

证显然，对于x、y∈A，(x,y)∈R当且仅当Ai∈X使x、y∈Ai。故R是自反的、对称的和传递的，即R是A上的一个等价关系。

由于X是A的一个划分，所以，x∈A，存在唯一的Ai∈X使x∈Ai。从而，y∈Ai，有(x,y)∈R，故y∈［x］，即Ai［x］。由等价关系的定义和X是A的一个划分，得Ai=［x］。因此，Ai是R的一个等价类，所以［x］∈X，因此x∈A，x∈∪Ai∈XAi。所以，X就是R的所有等价类的集合。证毕。

由定理3.12和定理3.13，可得定理3.14。

定理3.14集合A上的一个二元关系R是等价关系，当且仅当存在A的一个划分X使(x,y)∈R的充分条件是Ai∈X使x、y∈Ai。

综上可得，集合A上的等价关系与A的划分是一一对应且互相确定的。所以有定义3.20。

定义3.20设R是集合A上的一个等价关系，由R所确定的A的划分X={［x］|x∈A,［x］是x的等价类}，称为A关于R的商集，记做A/R。

等价关系、集合的划分和商集是3个重要的概念。集合的划分有时也称为集合的分类。分类的目的在于研究每一类中对象的共性。通常，分类总是根据需要，按照某一原则将集合中的元素分成一类一类的。但是，分类的准则不能完全任意，分类的准则应该满足哪些条件呢？粗略地说，这个条件要求被分类的每个事物必须被分到一类中且仅被分到一类中，当把它抽象为一个数学问题时，就是集合划分的定义所述的条件。一种分类确定一个等价关系，这个等价关系就是“在同一类中”的关系。而等价关系在直观上反映了“有相同特征”的事物之间的联系。而商集用来产生新的对象，这种新的对象与原来的对象有着截然不同的性质。

习题

1. 设R是集合A上的等价关系，将A的元素按照R的等价类顺序排列，则等价关系的关系矩阵MR有何特征？

2. 设R和S都是集合A上的等价关系，证明： 

(1) R∩S仍为A上的等价关系； 

(2) R∪S不一定是等价关系。(选取尽可能小的集合A，举反例证明)

3. 写出整数集合Z上的模10同余关系的各等价类。

4. 给出集合A={1,2,3,4}上的两个等价关系R和S，使RS不是等价关系。

5. 设R和S都是集合A上的等价关系，证明： (R∪S)+是A上的等价关系。

6. 设{A1,A2,…，An}是集合A的一个划分，A∩B≠，证明： {A1∩B,A2∩B,…An∩B}是A∩B的划分。

3.7偏序关系

本节讨论另一种极其重要的关系，就是序关系，它反映了事物之间的次序。当一个集合引入某种序关系后，就称该集合有了序结构。最重要的序关系就是偏序关系。

定义3.21设R为集合A上的二元关系，如果R是自反的、反对称的和传递的，则称R为偏序关系，称二元组(A,R)为偏序集。

当抽象地讨论集合A上的偏序关系时，常用“≤”表示偏序关系。如果x≤y，则读为“x小于或等于y”。约定x≤y且x≠y简记为x＜y。

如果≤是集合A上的偏序关系，则一般来说，只是A中部分元素之间才具有此关系。如果x、y∈A，x≤y或y≤x，则称x与y可以比较。如果x、y∈A使x
≤/y且y≤/x，则称x与y不可比较。

例3.38实数集R上通常的“小于或等于”关系≤是偏序关系，于是，R对≤构成偏序集。

例3.39正整数集合Z+上的整除关系|是偏序关系，于是，(Z+,|)是偏序集。在这里有可以比较的元素，也有不可比较的元素。例如，由2|4得2和4可以比较； 由23且32得2和3不可比较。

例3.40设S是一个集合，S的子集间的包含关系是2S上的偏序关系，于是，(2S,)是偏序集。

设≤是集合A上的偏序关系，则≤的逆≤-1也是A上的偏序关系，以后，用≥表示≤的逆关系≤-1，读成“大于或等于”。若x≥y且x≠y，则简记为x＞y。

定义3.22设≤是集合A上的偏序关系，若x，y∈A，x≤y与y≤x至少有一个成立，则称≤为A上的全序关系，或线性序关系，而(A,≤)称为全序集。

偏序集与全序集的主要区别在于，全序集中的任意两个元素均可以比较，而偏序集中未必任意两个元素均可以比较。

例3.41数间通常的“小于或等于”关系≤是全序关系，整除关系不是全序关系，集合的包含关系也不是全序关系。

定义3.23设(A,≤)是一个偏序集，x，y∈A，如果x＜y且对z∈A，如果x≤z≤y，则x=z或z=y，称y盖住x，记为x∝y，并且y被称为x的后继，x被称为y的前驱。

于是，盖住关系是集合A上的一个二元关系。

对于给定偏序集(A,≤)，它的盖住关系是唯一的，所以，可用盖住关系的关系图表示偏序关系，称为哈斯图，其作图规则为： 用点表示集合A中的元素，对于x，y∈A，有从x到y的矢线当且仅当y盖住x。若y盖住x，则表示y的点将画在表示x的点的上方。

例3.42集合A={1,2,3,4,5,6}及其上的整除关系|构成偏序集(A,|)。它的哈斯图如图3.2所示。

例3.43集合A={1,2,3,4,5,6}及其上通常的小于或等于关系≤构成偏序集(A,≤)。它的哈斯图如图3.3所示。



图3.2




图3.3



全序关系的哈斯图像是一条链一样。

定义3.24设(A,≤)是一个偏序集，BA，如果x，y∈B有x≤y或y≤x，则称B为A中的链。如果x，y∈B有x≤y和y≤x均不成立，则称B为A中的一个反链。B称为其长度。

定义3.25设(A,≤)是一个偏序集，且BA，如果s∈B使B中不存在元素x，满足x≠s且s≤x，则称s为B的极大元； 同理，如果d∈B使B中不存在元素x，满足x≠d且x≤d，则称d为B的极小元。

B中可能有极大元(极小元)，也可能没有极大元(极小元)。若B中有极大元(极小元)，则极大元(极小元)未必唯一，甚至可能有无穷多个。

定义3.26设(A,≤)是一个偏序集，且BA，如果a∈B使x∈B有x≤a，则称a为B的最大元； 同理，如果b∈B使x∈B有b≤x，则称b为B的最小元。

定理3.15设(A,≤)是偏序集，且BA，如果B有最大元，则最大元是唯一的。

证若a1、a2∈B均为最大元，由a1是最大元，有a2≤a1，由a2是最大元，有a1≤a2，因为(A,≤)是偏序集，所以，≤是反对称的，因此a1=a2，即最大元是唯一的。证毕。

同理，若B有最小元，则最小元也是唯一的。

B中可能有最大元(最小元)，也可能没有最大元(最小元)。B的最大元(最小元)必为极大元(极小元)，但是，B的极大元(极小元)未必是最大元(最小元)。

定义3.27设(A,≤)是一个偏序集，且BA，如果a∈A使x∈B有x≤a，则称a为B的一个上界； 同理，如果b∈A使x∈B有b≤x，则称b为B的一个下界。

子集B在A中可能有上界(下界)，也可能没有上界(下界)。若子集B在A中有上界(下界)，则上界(下界)未必唯一，甚至可能有无穷多个。B的最大元(最小元)必为B的一个上界(下界)，但是，B的上界(下界)未必是B的最大元(最小元)。

定义3.28设(A,≤)是一个偏序集，且BA，如果B有上界且B的上界的集合有最小元素，则这个最小元素称为B的最小上界(上确界)，记为sup B。类似地，如果B有下界且B的下界的集合有最大元素，则这个最大元素称为B的最大下界(下确界)，记为inf B。

子集B可能有上确界(下确界)，也可能没有上确界(下确界)。若子集B有上确界(下确界)，则上确界(下确界)必唯一。

例3.44在偏序集(Z+,|)中，若令B={1,2,3,4,5,6}，则B的极小元是1，B的极大元有4、5、6，B的最小元也是1，B中没有最大元。B的下界是1，B的上界有60、120等无穷多个。B的下确界是1，B的上确界是60。

习题

1. 偏序集(A,R)的哈斯图如图3.4所示。



图3.4


(1) 下列关系式哪些为真？

aRb,dRa,cRe,bRe,aRa,bRc,dRe,eRa。

(2) 求下列子集的上界、下界及上确界、下确界： 

{b,c,d},{c,d,e},{a,b,c}

2. 说明图3.5中的关系哪些是偏序关系？哪些是全序关系？并画出偏序关系的哈斯图。



图3.5


3. 设集合A={1,2,3}，画出偏序集(2A,)的哈斯图，并给出一个A的例子，使是2A上的全序关系。

4. 对下述每一条件，分别构造一个有限集和一个无限集的例子。

(1) 非空偏序集，其中某些子集无最大元； 

(2) 非空偏序集，其中有一子集存在下确界但无最小元素； 

(3) 非空偏序集，其中有一子集存在上界但无上确界。

5. 给出某一集合A上的一个二元关系R，使R既是偏序关系又是等价关系。