【集合论】关系闭包 ( 关系闭包求法 | 关系图求闭包 | 关系矩阵求闭包 | 闭包运算与关系性质 | 闭包复合运算 )

韩曙亮

发布于 2023-03-28 18:05:24

1.8K0

发布于 2023-03-28 18:05:24

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、闭包求法

R

关系是

A

集合上的二元关系 ,

R \subseteq A

, 且

A

集合不为空集 ,

A \not= \varnothing

求自反闭包 :

r(R) = R \cup I_A

, 给每个顶点添加环 ;

如果

R

关系是自反的 , 当且仅当 ,

I_A \subseteq R

求对称闭包 :

s(R) = R \cup R^{-1}

原来没有有向边 ( 有序对 ) , 自然也没有对应的逆 , 此时不添加边
原来有一条有向边 ( 有序对 ) , 再添加一个反向的有向边 , 组成关系图中的顶点间的双向有向边
原来有两条有向边 ( 有序对 ) , 此时就不用添加其它边
如果

R

关系是对称的 , 当且仅当 ,

R = R^{-1}

求传递闭包 :

t(R) = R \cup R^2 \cup R^3 \cup \cdots

将

R

关系所有的幂运算值并起来 , 就是其传递闭包 ,

R

关系的

1

次幂 ,

R

关系的

2

次幂 ,

R

关系的

3

次幂 ,

\cdots

,

R

关系的

n

次幂 , 并起来 , 就是其传递闭包 ;

如果

A

是有穷集 , 其关系也是有穷的 , 求出其所有的

n

次幂 , 不用求出很多幂运算 , 因为关系的幂运算后面都是循环的 , 求出已知的所有

n

次幂取并集即可 ;

如果

R

关系是传递的 , 当且仅当 ,

R^2 \subseteq R

二、求闭包示例 ( 关系图角度 )

集合

A = \{ a, b, c , d \}

关系

R = \{ <a,b> , <b,a> , <b,c> , <c,d> \}

求关系

R

的自反闭包

r(R)

, 对称闭包

s(R)

, 传递闭包

t(R)

求自反闭包 : 就是给每个顶点加上环 :

求对称闭包 : 将顶点间单向边改成双向边 , 不管顶点间双向边和顶点间没有边的情况 ;

求传递闭包 : 将能到的点直接连起来 ;

a 可以到 b , 路径 a -> b ; a 可以到 c , 路径是 a -> b -> c ; a 可以到 d , 路径是 a -> b -> c -> d ; 因此添加 a 到 c , d 的有向边 ;
b 可以到 a , 路径 b -> a ; b 可以到 c , 路径是 b -> c ; b 可以到 d , 路径是 b -> c -> d ; 因此添加 b 到 d 的有向边 ;
c 可以到 d , 路径 c -> d ; 没有可连接的边 ;
d 哪都到不了 , 没有可连接的边 ;
另外出现双向边时 , 两个顶点必须加环 ;

三、求闭包示例 ( 关系矩阵角度 )

关系

R = \{ <a, b> , <b,a> , <b,c> , <c,d> \}

使用关系矩阵方法求其自反闭包 , 对称闭包 , 传递闭包 ;

将上述关系写成矩阵形式为 :

M(R) = \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}

自反闭包 : 将主对角线值 , 全部改成

1

, 左上角到右下角为主对角线 ;

M(r(R)) = \begin{bmatrix} 1 & 1 & 0 & 0 \\\\ 1 & 1 & 1 & 0 \\\\ 0 & 0 & 1 & 1 \\\\ 0 & 0 & 0 & 1 \end{bmatrix}

对称闭包 : 主对角线两端要对称 , 以对角线为基准 , 使对角线两边的值对称 ;

M(s(R)) = \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \end{bmatrix}

传递闭包 : 求该关系矩阵的二次幂 , 三次幂 , 四次幂 ,

\cdots

, 直到出现相同的循环的值为止 ;

将上述所有的不同的矩阵幂运算进行逻辑相加 ( 或 ) 操作 , 就是其传递闭包对应的矩阵 , 计算机算法适合使用该方法 , 如果人计算 , 还是关系图比较形象 ;

注意逆序合成

M(R^2) = M(R \circ R) = M(R) \bullet M(R) =\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}

M(R^3) = M(R^2 \circ R) = M(R) \bullet M(R^2) = \begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 1 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}

M(R^4) = M(R^3 \circ R) = M(R) \bullet M(R^3) =\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} \bullet \begin{bmatrix} 0 & 1 & 0 & 1 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix} = M(R^2)

因此其

R^4

之后的幂运算值 , 偶数次幂关系矩阵与

M(R^2)

值相同 , 奇数次幂关系矩阵与

M(R^3)

值相同 ;

M(t(R)) = M(R) \lor M(R^2) \lor M(R^3) =\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & 1 & 1 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \end{bmatrix}

四、闭包运算与关系性质

	自反性	对称性	传递性
r ( R ) r(R) r(R)	1 1 1 ( 本身性质 )	1 1 1	1 1 1
r ( R ) r(R) r(R)	1 1 1	1 1 1 ( 本身性质 )
r ( R ) r(R) r(R)	1 1 1	1 1 1	1 1 1 ( 本身性质 )

r(R)

1

( 本身性质 )

1

r(R)

1

( 本身性质 )

r(R)

1

( 本身性质 )

上述表格中值为

1

, 说明原来存在该性质 , 求对应的自反/对称/传递闭包后 , 仍具有该性质 , 反之不具有该性质 ;

表格第二行含义 :

r(R)

对应的行 ;

自反性 : 假如

R

原来是自反的 , 那么

r(R)

也是自反的 ;

对称性 : 假如

R

原来是对称的 , 那么

r(R)

也是对称的 ; 求自反闭包 , 只是给顶点加环 , 不影响对称性 ;

传递性 : 假如

R

原来是传递的 , 那么

r(R)

也是传递的 ; 求自反闭包 , 只是给顶点加环 , 不影响传递性 ;

仅有一个特例 : 原来

R

是传递的 , 如果求对称闭包 , 其对称闭包的传递性就不存在了 ;

表格第二列说明 ( 自反性 ) : 如果

R

关系是自反的 , 那么其对称闭包

s(R)

和传递闭包

t(R)

也是自反的 ;

R 自反 \Rightarrow s(R) 和 t(R) 自反

表格第三列说明 ( 对称性 ) : 如果

R

关系是对称的 , 那么其自反闭包

r(R)

和传递闭包

t(R)

也是对称的 ;

R 对称 \Rightarrow r(R) 和 t(R) 对称

表格第四列说明 ( 传递性 ) : 如果

R

关系是传递的 , 那么其自反闭包

r(R)

也是传递的 ;

R 传递 \Rightarrow r(R) 传递

五、闭包复合运算

R

关系是

A

集合上的二元关系 ,

R \subseteq A

, 且

A

集合不为空集 ,

A \not= \varnothing

1.

rs(R) = sr(R)

:

rs( R ) : 先求

R

关系的自反闭包 , 然后再求自反闭包的对称闭包

sr( R ) : 先求

R

关系的对称闭包 , 然后再求对称闭包的自反闭包

上述两个闭包运算的结果相同

2.

rt(R) = tr(R)

rt( R ) : 先求

R

关系的自反闭包 , 然后再求自反闭包的传递闭包

tr( R ) : 先求

R

关系的传递闭包 , 然后再求传递闭包的自反闭包

上述两个闭包运算的结果相同

3.

st(R) \subseteq ts(R)

st( R ) : 先求

R

关系的对称闭包 , 然后再求对称闭包的传递闭包

ts( R ) : 先求

R

关系的传递闭包 , 然后再求传递闭包的对称闭包

上述两个闭包运算的结果 ,

ts(R)

关系包含

st(R)

关系 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-08，如有侵权请联系 cloudcommunity@tencent.com 删除

闭包

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度