关系的运算

定义4．9 设ρ1为从集合A到集合B的关系，ρ2为从集合B到集合C的关系，则称A到C的关系

｛（x，z）｜x∈A，z∈C，有y∈B使（x，y）∈ρ1且（y，z）∈ρ2｝

定理4．4 设A，B，C，D为任意四个集合，ρ1是从A到B的关系，ρ2和ρ3是从B到C的关系，ρ4是从C到D的关系，于是有：

定义4．10 设ρ1，ρ2，…，ρn分别是A1到A2，A2到A3，…，An到An＋1的关系，则称关系

｛（x1，xn＋1）｜x1∈A，xn＋1∈An＋1，存在x2∈A2，…，xn∈An，

使（x1，x2）∈ρ1，…，（xn，xn＋1）∈ρn｝

定义4．11 设A为任意集合，ρ为A上的任意二元关系，则有：

（1）ρ0是A上的恒等关系，即ρ0＝IA；

定理4．5 设m，n∈N，ρ为集合A上的二元关系，则：

（1）ρmρn＝ρm＋n

（2）（ρn）m＝ρm·n

定理4．6 设A，B，C是非空有限集，ρ1是从A到B的关系，ρ2是从B到C的关系，则：

Mρ1ρ2＝Mρ1＊Mρ2

推论4．2 设A1，A2，…，An＋1是有限集合，ρ1，ρ2，…，ρn分别是A1到A2，A2到A3，…，An到An＋1的关系，它们的关系矩阵分别为Mρ1，Mρ2，…，Mρn，则有：

推论4．3 ρ是集合A上的关系，Mρ为其关系矩阵，则有：

Mnρ＝（Mρ）n

由ρ的关系图构成ρn的关系图的步骤如下：

（1）对ρ的关系图（假设有m个结点）中每个结点ai（i＝1，2，…，m），找出从ai经由长为n的路能够到达的结点aj；

（2）连接aiaj得ρn的一条边；

（3）前两步得到的所有边组成ρn的关系图。

定义4．12 设ρ是从集合A到B的关系，则如下从B到A的关系

｛（y，x）｜y∈B，x∈A且（x，y）∈ρ｝

称为关系ρ的逆关系，记为ρ－1，这种从ρ得到ρ－1的运算，叫作关系的逆运算。

显然，从集合A到B的关系ρ的逆关系是将ρ中每一个序偶的坐标顺序互换所得到的集合。

定理4．7 设A，B为非空有限集，ρ是从A到B的关系，则有：

（2）把Gρ的每条有向边反向，就得到ρ－1的关系图Gp－1。

定理4．8 设ρ和ρi（i＝1，2，…）都是从集合A到集合B的二元关系，则有：

（1）（ρ－1）－1＝ρ；

（2）若ρ1⊆ρ2，则ρ1－1⊆ρ2－1；

（3）若ρ1＝ρ2，则ρ1－1＝ρ2－1。

定理4．9 设ρ是集合A上的二元关系，则有：

（1）ρ是自反的，当且仅当ρ－1是自反的；

（2）ρ是反自反的，当且仅当ρ－1是反自反的；

（3）ρ是对称的，当且仅当ρ－1是对称的；

（4）ρ是反对称的，当且仅当ρ－1是反对称的；

（5）ρ是传递的，当且仅当ρ－1是传递的。

定理4．10 设A，B，C是三个集合，ρ1是从A到B的关系，ρ2是从B到C的关系，则有：

推论4．4 设n∈N，ρ是集合A上的二元关系，则（ρn）－1＝（ρ－1）n。

定义4．13 设ρ为集合A上的二元关系，如果A上的二元关系ρ′满足：

（1）ρ′是自反（对称，传递）的；

（2）ρ⊆ρ′；

（3）若A上的二元关系ρ″也满足（1）、（2），则ρ′⊆ρ″；则称ρ′为ρ的自反（对称，传递）闭包，记为r（ρ）（s（ρ），t（ρ））。

从定义可以看出，ρ的自反（对称，传递）闭包就是包含ρ并且具有自反（对称，传递）性质的最小关系。显然，若ρ已经是自反（对称，传递）的，那么ρ的自反（对称，传递）闭包就是它自身。

定理4．11 设ρ是A上的二元关系，则：

（1）ρ是自反的，当且仅当r（ρ）＝ρ；

（2）ρ是对称的，当且仅当s（ρ）＝ρ；

（3）ρ是传递的，当且仅当t（ρ）＝ρ。

定理4．12 设ρ是集合A上的二元关系，则：

（1）r（ρ）＝ρ∪IA；

（2）s（ρ）＝ρ∪ρ－1；

定理4．13 设A为n个元素的有限集，ρ为A上的二元关系，则：