【集合论】关系闭包 ( 自反闭包 | 对称闭包 | 传递闭包 )

韩曙亮

发布于 2023-03-28 18:04:45

3.7K0

发布于 2023-03-28 18:04:45

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

文章目录

一、关系闭包

包含给定的元素 , 并且具有指定性质的最小的集合 , 称为关系的闭包 ; 这个指定的性质就是关系

R

自反闭包 r ( R ) : 包含

R

关系 , 向

R

关系中 , 添加有序对 , 变成自反的最小的二元关系

对称闭包 s ( R ) : 包含

R

关系 , 向

R

关系中 , 添加有序对 , 变成对称的最小的二元关系

传递闭包 t ( R ) : 包含

R

关系 , 向

R

关系中 , 添加有序对 , 变成传递的最小的二元关系

定义中有三个重要要素 :

包含给定元素
具有指定性质
最小的二元关系

二、自反闭包

自反闭包 r ( R ) : 包含

R

关系 , 向

R

关系中 , 添加有序对 , 变成自反的最小的二元关系

R \subseteq r(R)

r(R)

是自反的

\forall S ( ( R \subseteq S\land S 自反 ) \to r(R) \subseteq S)

关系

R

的关系图

G(R)

:

R

的自反闭包

G(r ( R ))

关系图 : 在

R

的基础上 , 添加有些有序对 , 使

r(R)

变成自反的最小的二元关系 , 自反的条件是所有的顶点都有环 , 这里为四个顶点都添加环 ;

三、对称闭包

自反闭包 r ( R ) : 包含

R

关系 , 向

R

关系中 , 添加有序对 , 变成对称的最小的二元关系

R \subseteq s(R)

s(R)

是对称的

\forall S ( ( R \subseteq S\land S 对称 ) \to r(R) \subseteq S)

关系

R

的关系图

G(R)

:

R

的对称闭包

G(s ( R ))

关系图 : 在

R

的基础上 , 添加有些有序对 , 使

s(R)

变成对称的最小的二元关系 , 对称的条件是任意两个顶点之间有

0/2

条有向边 , 有

0

条边的不管 , 有

1

条边的在添加一条反向有向边 ;

四、传递闭包

自反闭包 r ( R ) : 包含

R

关系 , 向

R

关系中 , 添加有序对 , 变成传递的最小的二元关系

R \subseteq t(R)

t(R)

是对称的

\forall S ( ( R \subseteq S\land S 传递 ) \to r(R) \subseteq S)

关系

R

的关系图

G(R)

:

R

的对称闭包

G(t ( R ))

关系图 : 在

R

的基础上 , 添加有些有序对 , 使

t(R)

变成传递的最小的二元关系 , 传递的条件是 ① 前提

a\to b, b \to c

成立 ,

a \to c

存在 , 或 ② 前提不成立 , 前提不成立的情况下不管默认就是传递的 , 如果前提成立 , 则必修添加对应的第三条边 ;

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

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

闭包

基础

集合

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

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

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

闭包

基础

集合

登录后参与评论

0 条评论

热度