本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

前面介绍了集合上二元关系的五种特性：自反性、反自反性、对称性、反对称性、传递性。对于一个集合上的二元关系，可以通过增加必要的序偶，使其满足自反、对称或传递性。为此，这里引入关系的闭包 closure 运算。

定义8.1.1 设 R R R 是集合 A A A 上的二元关系，如果 A A A 上另外一个二元关系 R ′ R' R′ 满足： （1） R ′ R' R′ 是自反的（对称的、传递的）； （2） R ⊆ R ′ R \subseteq R' R⊆R′ ； （3）对于 A A A 上的任何自反的（对称的、传递的）关系 R ′ ′ R'' R′′ ，若 R ⊆ R ′ ′ R \subseteq R'' R⊆R′′ ，有 R ′ ⊆ R ′ ′ R' \subseteq R'' R′⊆R′′ ，则称 R ′ R' R′ 是 R R R 的自反（对称、传递）闭包。

集合 A A A 上二元关系 R R R 的自反闭包 reflexive closure 、对称闭包 symmetric closure 、传递闭包 transitive closure 分别记为 r ( R ) , s ( R ) , t ( R ) r(R), s(R), t(R) r(R),s(R),t(R) 。由定义可知， R R R 的自反闭包 r ( R ) r(R) r(R) 、对称闭包 s ( R ) s(R) s(R) 、传递闭包 t ( R ) t(R) t(R) 分别是包含 R R R 的最小的、自反的（对称的、传递的）关系。

定理8.1.1 设 R R R 是集合 A A A 上的二元关系，则有： （1） R R R 是自反的当且仅当 r ( R ) = R r(R) = R r(R)=R ； （2） R R R 是对称的当且仅当 s ( R ) = R s(R) = R s(R)=R ； （3） R R R 是传递的当且仅当 t ( R ) = R t(R) = R t(R)=R 。 证明 （1）要证明必要性和充分性。

（2）要证明必要性和充分性。

（3）要证明必要性和充分性。

例1 设 A = { a , b } A = \{a, b\} A={a,b} ，分别求以下 A A A 上的二元关系的自反、对称和传递闭包。 （1） R = { ⟨ a , a ⟩ , ⟨ b , b ⟩ } R = \{\langle a, a\rangle, \langle b, b\rangle\} R={⟨a,a⟩,⟨b,b⟩} （2） S = A × A S = A\times A S=A×A （3） T = ∅ T = \varnothing T=∅ 解： （1）因为 R = { ⟨ a , a ⟩ , ⟨ b , b ⟩ } R = \{\langle a, a\rangle, \langle b, b\rangle\} R={⟨a,a⟩,⟨b,b⟩} 是自反的、对称的和传递的，所以有： r ( R ) = s ( R ) = t ( R ) = R r(R) = s(R) = t(R) = R r(R)=s(R)=t(R)=R

（2）因为 S = { ⟨ a , a ⟩ , ⟨ a , b ⟩ , ⟨ b , a ⟩ , ⟨ b , b ⟩ } S = \{\langle a, a\rangle, \langle a, b\rangle, \langle b, a\rangle, \langle b, b\rangle\} S={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,b⟩} 是自反的、对称的和传递的，因此有： r ( S ) = s ( S ) = t ( S ) = S r(S) = s(S) = t(S) = S r(S)=s(S)=t(S)=S

（3） T T T 不是自反的，但是对称和传递的（定义在某个非空集合上的空集不是自反的，但是对称的、传递的），因此 s ( T ) = t ( T ) = T = ∅ s(T) = t(T) = T = \varnothing s(T)=t(T)=T=∅ ，而根据自反闭包的定义， r ( T ) = ⟨ a , a ⟩ , ⟨ b , b ⟩ } r(T) = \langle a, a\rangle, \langle b, b\rangle\} r(T)=⟨a,a⟩,⟨b,b⟩} 。

根据定理8.1.1，如果 R R R 本身就是自反（对称、传递）的，那么 R R R 的自反（对称、传递）闭包就等于 R R R 。反过来说，若 R R R 不是自反（对称、传递）的，那么有 r ( R ) ≠ R , s ( R ) ≠ R , t ( R ) ≠ R r(R) \ne R, s(R) \ne R, t(R) \ne R r(R)​=R,s(R)​=R,t(R)​=R 。在这种情况下，如何求关系 R R R 的闭包呢？

定理8.2.1 设 R R R 是集合 A A A 上的二元关系，那么有： （1） r ( R ) = R ∪ I A r(R) = R\cup I_A r(R)=R∪IA​ ； （2） s ( R ) = R ∪ R − 1 s(R) = R\cup R^{-1} s(R)=R∪R−1 ； （3） t ( R ) = ⋃ i = 1 ∞ R i t(R) = \displaystyle \bigcup^\infin_{i = 1} R^i t(R)=i=1⋃∞​Ri 证明 （1）令 R ′ = R ∪ I A R' = R\cup I_A R′=R∪IA​ 。 ① 任取 x ∈ A x \in A x∈A ， ⟨ x , x ⟩ ∈ I A \langle x, x\rangle \in I_A ⟨x,x⟩∈IA​ ，则 ⟨ x , x ⟩ ∈ R ∪ I A \langle x, x\rangle \in R\cup I_A ⟨x,x⟩∈R∪IA​ ，故 R ′ R' R′ 是自反的； ② 显然 R ⊆ R ′ R \subseteq R' R⊆R′ ； ③ 任取 A A A 上的自反关系 R ′ ′ R'' R′′ ，若 R ⊆ R ′ ′ R \subseteq R'' R⊆R′′ ，现证明 R ′ ⊆ R ′ ′ R' \subseteq R'' R′⊆R′′ 。 任取 ⟨ x , y ⟩ ∈ R ′ \langle x, y\rangle \in R' ⟨x,y⟩∈R′ ，由 R ′ = R ∪ I A R' = R\cup I_A R′=R∪IA​ 知， ⟨ x , y ⟩ ∈ R \langle x, y\rangle \in R ⟨x,y⟩∈R 或 ⟨ x , y ⟩ ∈ I A \langle x, y\rangle \in I_A ⟨x,y⟩∈IA​ 。 若 ⟨ x , y ⟩ ∈ R \langle x, y\rangle \in R ⟨x,y⟩∈R ，则有 ⟨ x , y ⟩ ∈ R ′ ′ \langle x, y\rangle \in R'' ⟨x,y⟩∈R′′ ； 若 ⟨ x , y ⟩ ∈ I A \langle x, y\rangle \in I_A ⟨x,y⟩∈IA​ ，则 x = y x = y x=y ，又因为 R ′ ′ R'' R′′ 是自反的，所以 ⟨ x , y ⟩ ∈ R ′ ′ \langle x, y\rangle \in R'' ⟨x,y⟩∈R′′ 。 故有 R ′ ⊆ R ′ ′ R' \subseteq R'' R′⊆R′′ 。由此可知， r ( R ) = R ′ = R ∪ I A r(R) = R' = R\cup I_A r(R)=R′=R∪IA​ 。

（2）令 R ′ = R ∪ R − 1 R' = R\cup R^{-1} R′=R∪R−1 。 ① R ′ − 1 = ( R ∪ R − 1 ) − 1 = R − 1 ∪ R = R ′ R'^{-1} = (R\cup R^{-1})^{-1} = R^{-1}\cup R = R' R′−1=(R∪R−1)−1=R−1∪R=R′ ，所以 R ′ R' R′ 是对称的； ② 显然 R ⊆ R ′ R \subseteq R' R⊆R′ 。 ③ 任取 A A A 上的对称关系 R ′ ′ R'' R′′ ，若 R ⊆ R ′ ′ R \subseteq R'' R⊆R′′ ，现证明 R ′ ⊆ R ′ ′ R' \subseteq R'' R′⊆R′′ 。 任取 ⟨ x , y ⟩ ∈ R ′ \langle x, y\rangle \in R' ⟨x,y⟩∈R′ ，由 R ′ = R ∪ R − 1 R' = R\cup R^{-1} R′=R∪R−1 知， ⟨ x , y ⟩ ∈ R \langle x, y\rangle \in R ⟨x,y⟩∈R 或 ⟨ x , y ⟩ ∈ R − 1 \langle x, y\rangle \in R^{-1} ⟨x,y⟩∈R−1 。 若 ⟨ x , y ⟩ ∈ R \langle x, y\rangle \in R ⟨x,y⟩∈R ， 则 ⟨ x , y ⟩ ∈ R ′ ′ \langle x, y\rangle \in R'' ⟨x,y⟩∈R′′ ； 若 ⟨ x , y ⟩ ∈ R − 1 \langle x, y\rangle \in R^{-1} ⟨x,y⟩∈R−1 ，则 ⟨ y , x ⟩ ∈ R \langle y, x\rangle \in R ⟨y,x⟩∈R ，则 ⟨ y , x ⟩ ∈ R ′ ′ \langle y, x\rangle \in R'' ⟨y,x⟩∈R′′ ， 因为 R ′ ′ R'' R′′ 是对称的，所以 ⟨ x , y ⟩ ∈ R ′ ′ \langle x, y\rangle \in R'' ⟨x,y⟩∈R′′ 。 故有 R ′ ⊆ R ′ ′ R' \subseteq R'' R′⊆R′′ 。由此可知， s ( R ) = R ′ = R ∪ R − 1 s(R) = R' = R\cup R^{-1} s(R)=R′=R∪R−1 。

（3）令 R ′ = ⋃ i = 1 ∞ R i R' = \displaystyle \bigcup^\infin_{i = 1}R^i R′=i=1⋃∞​Ri 。 ① 任取 ⟨ x , y ⟩ ∈ R ′ \langle x, y\rangle \in R' ⟨x,y⟩∈R′ ， ⟨ y , z ⟩ ∈ R ′ \langle y, z\rangle \in R' ⟨y,z⟩∈R′ ，那么必存在正整数 s , t s, t s,t ，使得 ⟨ x , y ⟩ ∈ R s , ⟨ y , z ⟩ ∈ R t \langle x, y\rangle \in R^s, \langle y, z\rangle \in R^t ⟨x,y⟩∈Rs,⟨y,z⟩∈Rt ，则有 ⟨ x , z ⟩ ∈ R s ∘ R t = R s + t ⊆ ⋃ i = 1 ∞ R i \langle x, z\rangle \in R^s \circ R^t = R^{s+t} \subseteq \displaystyle \bigcup_{i = 1}^\infin R^i ⟨x,z⟩∈Rs∘Rt=Rs+t⊆i=1⋃∞​Ri ，所以 ⟨ x , z ⟩ ∈ R ′ \langle x, z\rangle \in R' ⟨x,z⟩∈R′ ，即 R ′ R' R′ 是传递的。 ② 显然 R ⊆ ⋃ i = 1 ∞ R i = R ′ R \subseteq \displaystyle \bigcup^\infin_{i = 1} R^i = R' R⊆i=1⋃∞​Ri=R′ 。 ③ 任取 A A A 上的传递关系 R ′ ′ R'' R′′ ，若 R ⊆ R ′ ′ R \subseteq R'' R⊆R′′ ，现证明 R ′ ⊆ R ′ ′ R' \subseteq R'' R′⊆R′′ 。 任取 ⟨ x , y ⟩ ∈ R ′ \langle x, y\rangle \in R' ⟨x,y⟩∈R′ ，则存在某正整数 k k k 使得 ⟨ x , y ⟩ ∈ R k \langle x, y\rangle \in R^k ⟨x,y⟩∈Rk ，而 R k = R ∘ R ∘ ⋯ ∘ R ⏟ k 个 R^k = \underbrace{R\circ R\circ \dots \circ R}_{k个} Rk=k个 R∘R∘⋯∘R​​ ，由复合运算的定义可知： A A A 中存在元素 x 1 , x 2 , … x k − 1 x_1, x_2, \dots x_{k-1} x1​,x2​,…xk−1​ ，使得 ⟨ x , x 1 ⟩ ∈ R ,   ⟨ x 1 , x 2 ⟩ ∈ R ,   … ,   ⟨ x k − 1 , y ⟩ ∈ R \langle x, x_1\rangle \in R,\ \langle x_1, x_2\rangle \in R,\ \dots,\ \langle x_{k - 1}, y\rangle \in R ⟨x,x1​⟩∈R, ⟨x1​,x2​⟩∈R, …, ⟨xk−1​,y⟩∈R 。因为 R ⊆ R ′ ′ R \subseteq R'' R⊆R′′ ，所以有 ⟨ x , x 1 ⟩ ∈ R ′ ′ ,   ⟨ x 1 , x 2 ⟩ ∈ R ′ ′ ,   … ,   ⟨ x k − 1 , y ⟩ ∈ R ′ ′ \langle x, x_1\rangle \in R'',\ \langle x_1, x_2\rangle \in R'',\ \dots,\ \langle x_{k - 1}, y\rangle \in R'' ⟨x,x1​⟩∈R′′, ⟨x1​,x2​⟩∈R′′, …, ⟨xk−1​,y⟩∈R′′ 。 又因为 R ′ ′ R'' R′′ 是传递的，所以 ⟨ x , y ⟩ ∈ R ′ ′ \langle x, y\rangle \in R'' ⟨x,y⟩∈R′′ ，从而有 R ′ ⊆ R ′ ′ R'\subseteq R'' R′⊆R′′ 。 综上所述有 t ( R ) = R ′ = ⋃ i = 1 ∞ R i t(R) = R' = \displaystyle\bigcup^\infin_{i = 1}R^i t(R)=R′=i=1⋃∞​Ri 。

例2 设 A = { a , b , c } A = \{ a, b, c\} A={a,b,c} ， A A A 上的二元关系 R = { ⟨ a , b ⟩ , ⟨ b , c ⟩ , ⟨ c , a ⟩ } R = \{ \langle a, b\rangle , \langle b, c\rangle , \langle c, a\rangle \} R={⟨a,b⟩,⟨b,c⟩,⟨c,a⟩} ，求 r ( R ) , s ( R ) , t ( R ) r(R), s(R), t(R) r(R),s(R),t(R) ，并给出各闭包的关系矩阵和关系图。 解： R R R 的关系图如下所示。 （a）求自反闭包 r ( R ) r(R) r(R) 。 r ( R ) = { ⟨ a , b ⟩ , ⟨ b , c ⟩ , ⟨ c , a ⟩ , ⟨ a , a ⟩ , ⟨ b , b ⟩ , ⟨ c , c ⟩ } M r ( R ) = [ 1 1 0 0 1 1 1 0 1 ] r(R) = \{ \langle a, b \rangle, \langle b, c\rangle, \langle c, a\rangle , \langle a, a\rangle, \langle b, b\rangle, \langle c, c \rangle \}\\ \\ {} \\ M_{r(R)} = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\\ \end{bmatrix} r(R)={⟨a,b⟩,⟨b,c⟩,⟨c,a⟩,⟨a,a⟩,⟨b,b⟩,⟨c,c⟩}Mr(R)​=⎣⎡​101​110​011​⎦⎤​

r ( R ) r(R) r(R) 的关系图如下所示：

定理8.2.2 设 R R R 是有限集合 A A A 上的二元关系且 ∣ A ∣ = n |A| = n ∣A∣=n ，那么有： t ( R ) = R ∪ R 2 ∪ ⋯ ∪ R n t(R) = R\cup R^2\cup \dots \cup R^n t(R)=R∪R2∪⋯∪Rn 证明

定理8.2.3 设 R R R 是集合 A A A 上的二元关系，则有： （1）如果 R R R 是自反的，那么 s ( R ) s(R) s(R) 和 t ( R ) t(R) t(R) 也是自反的； （2）如果 R R R 是对称的，那么 r ( R ) r(R) r(R) 和 t ( R ) t(R) t(R) 也是对称的； （3）如果 R R R 是传递的，那么 r ( R ) r(R) r(R) 也是传递的。

集合 A A A 上的二元关系 R R R 的闭包运算可以进行复合运算，例如 t s ( R ) = t ( s ( R ) ) ts(R) = t(s(R)) ts(R)=t(s(R)) 表示 R R R 的对称闭包的传递闭包，通常简称为 R R R 的对称传递闭包；而 t s r ( R ) tsr(R) tsr(R) 则表示 R R R 的自反对称传递闭包。 R R R 的传递闭包有时用 R + R^+ R+ 表示，而 R R R 的自发传递闭包 t r ( R ) tr(R) tr(R) 用 R ∗ R^* R∗ 表示。

定理8.3.1 设 R R R 是集合 A A A 上的二元关系，则有： （1） s r ( R ) = r s ( R ) sr(R) = rs(R) sr(R)=rs(R) ； （2） t r ( R ) = r t ( R ) tr(R) = rt(R) tr(R)=rt(R) ； （3） s t ( R ) ⊆ t s ( R ) st(R) \subseteq ts(R) st(R)⊆ts(R) 。