§2.2　关系的运算

由于关系是序偶的集合，因此，集合A到B的两个不同的关系R和S可以进行集合的∪、∩、-、和-运算，其结果仍为A到B的关系，并分别R∪S、R∩S、R-S、和（或）.然而，关系又是一种特殊的集合，故它还应有自己特有的运算.

定义2.2.1　设R是A到B的关系，S是B到C的关系，令

并称R·S为R与S的复合关系（complemented relation）.特别地，若A=B，则R·S为R与S的乘积.

例如，设集合A={1，2，3}，R={<1，2>，<3，3>}，S={<2，3>}，则

R·S={<1，3>}，S·R={<2，3>}

这表明关系的复合运算不满足交换律.

定理2.2.1　设R是A到B的关系，S是B到C的关系，T是C到D的关系，则

（R·S）·T=R·（S·T）

证明：任取<x，w>∈（R·S）·T，则存在z∈C，使得<x，z>∈R·S且<z，w>∈T，又由<x，z>∈R·S知，存在y∈B，使得<x，y>∈R，<y，z>∈S.再由<y，z>∈S且<z，w>∈T知，<y，w>∈S·T.最后由<x，y>∈R且<y，w>∈S·T推出<x，w>∈R·（S·T）.于是有（R·S）·T⊆R·S·（T）.

同理可证，R·（S·T）⊆（R·S）·T.总之，我们有

（R·S）·T=R·（S·T）

此定理表明，关系的复合运算满足结合律.

定义在同一集合上的关系R可与自身复合任意多次.

定义2.2.2　设R是集合A上的二元关系，则Rn=R·R·…·R，n≥0，定义如下：

Rn+1=Rn·R

例如，设A={1，2，3}，R={<1，2>，<2，1>，<1，3>}，则

R0={<1，1>，<2，2>，<3，3>}

R1=R0·R={<1，2>，<2，1>，<1，3>}

R2=R1·R={<1，1>，<2，2>，<2，3>}

R3=R2·R={<1，2>，<1，3>，<2，1>}

R4=R3·R=R·R=R2

不难看出，在本例中

R2n=R2（n≥1）

R2n+1=R（n≥0）

利用关系的幂运算，可判断关系是否具有传递性.

定理2.2.2　集合A上的关系R是传递的，当且仅当R2⊆R.

证明：必要性.设R是传递的，任取<x，y>∈R2，则存在z∈A使得xRz且zRy，因R是传递的，所以xRy，即<x，y>∈R，故R2⊆R.

充分性.设R2⊆R.若xRy，yRz，则xR2z，即<x，z>∈R2，于是xRz，故R是传递的.

定义2.2.3　设R是A到B的二元关系，令

称R-1为R的逆关系（inverse relation）.

易知，R的逆关系R-1就是R中所有序偶颠倒次序后所得序偶的集合，因此，（R-1）-1=R.

定理2.2.3　设R是A到B的二元关系，S是B到C的关系，则

（R·S）-1=S-1·R-1

证明：因为<x，z>∈（R·S）-1，当且仅当<z，x>∈R·S，当且仅当存在y∈B使得<z，y>∈R且<y，x>∈S，当且仅当<y，z>∈R-1且<x，y>∈S-1，当且仅当<x，z>∈S-1·R-1，因此，

（R·S）-1=S-1·R-1

可利用逆关系来判断关系的某些性质.

定理2.2.4　设R为X上的二元关系，则

（1）R是对称的，当且仅当R=R-1；

（2）R是反对称的，当且仅当R∩R-1⊆R0.

证明：（1）设R是对称的.因为<x，y>∈R当且仅当<y，x>∈R，当且仅当<x，y>∈R-1，故R=R-1；

再设R=R-1.于是若<x，y>∈R，则有<x，y>∈R-1，从而<y，x>∈R，故R是对称的.

（2）设R是反对称的.若<x，y>∈R∩R-1，则<x，y>∈R且<x，y>∈R-1，即<x，y>∈R且<y，x>∈R，于是x=y，从而<x，y>=<x，x>∈R0，即R∩R-1⊆R0；

再设R∩R-1⊆R0.若<x，y>∈R且<y，x>∈R，则有<x，y>∈R，且<x，y>∈R-1，即<x，y>∈R∩R-1，于是有<x，y>∈R0，从而x=y.故R是反对称的.

设R是集合A上的一个二元关系，则R不一定是自反的、对称的或传递的，我们希望在R的基础上添加一些元素（序偶），得到一个包含R的且具有自反性或对称性或传递性的二元关系.

定义2.2.4　设R为集合A上的二元关系.如果A上的二元关系R′满足：

（1）R′是自反（对称、传递）的；

（2）R⊆R′；

（3）若A上的二元关系R″也满足（1）和（2）则R′⊆R″.

则称R′为R的自反（对称、传递）闭包（closure），记为r（R）s（（R），t（R））.

【例2.2】　设集合A={a，b，c，d}上的二元关系R={<a，b>，<b，c>}，如何形成关系R′，使之包含R并且具有自反性？

解：A上的自反关系必定包含R0，于是R1=R∪R0，此外，向R1添加新的序偶

R2=R1∪{<a，c>}

R3=R1∪{<a，c>，<b，d>}

……

这些关系R1，R2，R3，…，Ri，…都是自反的，且R1⊆R2⊆R3⊆…⊆Ri⊆…，其中R1是包含R的最小的具有自反性的关系，即R1是R的自反闭包.

从定义不难看出，R的自反（对称，传递）闭包即是包含R的最小的具有自反（对称、传递）性的关系.此外，从定义即可得出：

定理2.2.5设R为集合A上的二元关系，于是：

（1）R是自反的，当且仅当r（R）=R；

（2）R是对称的，当且仅当s（R）=R；

（3）R是传递的，当且仅当t（R）=R.

下面讨论如何求一个关系的R的三种闭包.

定理2.2.6　设R为集合A上的二元关系，于是：

证明：（1）、（2）容易证明，下证（3）.

令　　R+=R∪R2∪R3∪…

显然R⊆R+.

设<x，y>，<y，z>∈R+，则存在正整数m，n，使得<x，y>∈Rm，<y，z>∈Rn.于是

<x，z>∈Rm·Rn=Rm+n⊂R+

故R+具有传递性.

设S是A上的一个传递关系，且R⊆S.下证R+⊆S.任取<x，y>∈R+，不妨设<x，y>∈Rn.若n=1，则<x，y>∈R⊆S，于是<x，y>∈S；若n>1，则有z1，…，zn-1，使

xRz1，z1Rz2，…，zn-2Rzn-1，zn-1Ry

由于R⊆S，且S具有传递性，所以

<x，z2>∈S，<x，z3>∈S，…，<x，y>∈S

故　　R+⊆S

综上所述，　　t（R）=R∪R2∪R3∪…

当集合A为有限集时，我们有：

定理2.2.7　设A为n个元素的集合，R是定义在A上的二元关系，则

证明：只须证明对任何整数k≥1有

任取<x，y>∈Rn+k，令z0=x，zn+k=y，则存在z1，z2，…，zn+k-1∈A，使得

z0Rz1，z1Rz2，…，zn+k-1Rzn+k　　（2.1）

注意到式（2.1）中共有n+k+1个元素，而A只有n个元素，故必存在0≤i<j≤n+k，使得zi=zj，于是，有

z0Rz1，z1Rz2，…，zi-1Rzi，ziRzj+1，…，zn+k-1Rzn+k　　（2.2）

易知，式（2.2）中共有m=n+k+1-（j-i）个元素，若m>n，则重复以上过程，直到m≤n，从而，即<x，y>∈Rm，因此