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

韩曙亮

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

4.3K0

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

文章目录

一、关系闭包

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

$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 删除。

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

闭包

基础

集合

登录后参与评论

暂无评论