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

zl程序教程

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

当前栏目

【集合论】关系性质 ( 对称性 | 对称性示例 | 对称性相关定理 | 反对称性 | 反对称性示例 | 反对称性定理 )

示例 相关 关系 性质 定理 集合论 对称性
2023-06-13 09:17:48 时间

文章目录

一、对称性

对称性 描述 :

R \subseteq A \times A
R

是对称的

\Leftrightarrow
\forall x \forall y ( x \in A \land y \in A \land xRy \to yRx )
\Leftrightarrow
( \forall x \in A ) (\forall y \in A)[xRy \to yRx]
R

是非对称的

\Leftrightarrow
\exist x \exist y ( x \in A \land y \in A \land xRy \land \lnot yRx )

对称性描述 : 任选两个元素

x, y

, 如果

x

与

y

有关系

R

即

xRy

, 那么

y

与

x

也有关系

R

即

yRx

;

非对称性描述 : 只要存在一个

x , y

组合 ,

x

与

y

有关系

R

, 但是

y

与

x

没有关系

R

, 那么该关系

R

就是非对称的 ;

二、对称性示例

对称性示例 :

关系图中 , 不考虑环 , 只看两点之间的关系 , 两个顶点之间的关系都是往返箭头 , 那么就是对称的 , 有一个单向箭头 , 就不是对称的 ;

上述关系图中 , 顶点之间的箭头都是双向的 , 该关系是对称的 ;

上述关系图中 , 都是单向箭头 , 有一个箭头是单向的 , 就不是对称的 ;

三、对称性定理

对称性定理 :

R

是对称的

\Leftrightarrow
R^{-1} = R
\Leftrightarrow
R^{-1}

是对称的

\Leftrightarrow
M(R)

关系矩阵是对称的

\Leftrightarrow
G(R)

的任意两个顶点之间如果有边 , 必定是两条边 ( 正向反向各一条 )

对称性 两个顶点之间 有

0

条或

2

条边 ;

四、反对称性

反对称性 :

R \subseteq A \times A
R

是反对称的

\Leftrightarrow
\forall x \forall y ( x \in A \land y \in A \land xRy \land yRx \to x=y )
\Leftrightarrow
(\forall x \in A)(\forall y \in A)[ xRy \land yRx \to x = y ]

非反对称性 :

R

是非反对称的

\Leftrightarrow
\exist x \exist y ( x \in A \land y \in A \land xRy \land yRx \land x \not=y )

反对称就是 防止两个顶点之间有两条边 , 两个顶点之间要么有

0

条边 , 要么有

1

条边 ;

对称是 任何两个顶点之间 , 要么有

0

条边 , 要么有

2

条边 ;

如果关系图中 , 两个顶点之间没有边 , 那么该关系 既是对称的 , 又是反对称的 ; ( 环不影响对称与反对称定义 )

五、反对称性示例

反对称性 : 顶点之间没有两条边的 , 只有

0

条边 或

1

条边

对称性 : 顶点之间只有

0

条边 , 或

1

条边

上图是反对称的 , 有两个

1

条边 , 一个

0

条边 ;

上图是非反对称的 , 有

0

条边 ,

1

条边 ,

2

条边的情况 , 是非反对称的 ;

六、反对称性定理

反对称性定理 :

R

是反对称的

\Leftrightarrow
R^{-1} \cap R \subseteq I_A
\Leftrightarrow
R^{-1}

是反对称的

\Leftrightarrow
M(R)

关系矩阵中 ,

\forall i \forall j (i \not= j \land r_{ij} = 1 \to r_{ji} = 0)
\Leftrightarrow
G(R)

关系图中 ,

\forall a_i \forall a_j (i \not= j)

, 如果存在有向边

<a_i, a_j>

, 则一定不存在

<a_j, a_i>
R^{-1} \cap R \subseteq I_A

说明 :

R

关系 与

R^{-1}

关系 (

R

的逆关系 ) 的交集 , 包含在 恒等关系中 ;

如果两个顶点之间有两条边 , 求逆之后 , 两个顶点的两个的两条边分别反向 , 还是相同的两条边 , 如果二者求交集 , 还是存在两条边 , 肯定不是恒等关系 , 恒等关系都是环 ; ( 不符合反对称 )

如果两个顶点之间有

1

条边 , 求逆之后 , 两个顶点之间是反向的一条边 , 两个关系的交集肯定为空 , 剩下的只有环 ; ( 反对称 )

如果两个顶点之间有

0

条边 , 求逆之后 , 两个顶点之间是

0

条边 , 两个关系的交集肯定为空 , 剩下的只有环 ; (反对称)

关系矩阵 :

M(R)

中 ,

\forall i \forall j ( i \not= j \land r_{ij} = 1 \to r_{ji} = 0 )

对角线以外的不能有对称的位置都是

1

的情况 , 如

r_{ij} = 1

, 其对称的元素

r_{ji}

一定不能是

1

, 必须是

0

;

关系图 :

G(R)

中 , 如果

\forall a_i \forall a_j ( i \not= j )

, 如果有有向边

<a_i, a_j>

, 则必须没有

<a_j , a_i>

;

关系图中 两个顶点 只存在单向边 , 或没有边 , 不存在两个方向的边 ;

七、对称性与反对称性示例

上述关系图中 , 两个顶点之间存在

0

条边 ,

2

条边 , 是对称的 ;

自反的 , 所有的顶点都有环 , 是自反的 ;

上述关系图是反对称的 , 都有 一条有向边 ;

所有的顶点 都没有环 是 反自反的 ;

上述图中 , 有的顶点之间有

1

条边 , 有的顶点之间有

2

条边 , 既不是对称的 , 又不是反对称的 ;

有的顶点有环 , 有的顶点没有环 , 既不是 自反的 , 又不是反自反的 ;

上述关系图中 , 顶点之间都是

0

条边 ;

顶点之间是

0

条边 /

2

条边 是对称的 ;

顶点之间是

0

条边 /

1

条边 是反对称的 ;

上述关系图 既是 对称的 , 又是反对称的 ;

有的顶点有环 , 有的顶点没有环 , 既不是 自反的 , 又不是反自反的 ;

相关文章