提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

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

关系 传递 闭包 对称 集合论
2023-06-13 09:17:48 时间

文章目录

一、关系闭包

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

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

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

相关文章