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

zl程序教程

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

当前栏目

【集合论】关系幂运算 ( 关系幂运算 | 关系幂运算示例 | 关系幂运算性质 )

示例 关系 运算 性质 集合论
2023-06-13 09:17:48 时间

文章目录

一、关系幂运算

关系

R

的

n

次幂定义 :

R \subseteq A \times A , n \in N
\begin{cases} R^0 = I_A & \\ R^{n +1} = R^n \circ R & ( n \geq 0 ) \end{cases}

关系

R

是 集合

A

上的 二元关系 ,

R

的

0

次幂

R^0

是恒等关系

I_A

, 关系

R

的

n + 1

次幂等于

R^{n + 1} = R^n \circ R

其中

n \geq 0

;

R^1 = R^0 \circ R = R

, 恒等关系与 关系

R

逆序合成 , 结果还是关系

R

, 这个关系

R

可以是任意关系 ;

恒等关系就是 集合

A

中每个元素自己跟自己有关系 ;

关系

R

幂运算结果

R^n

关系 也是集合

A

上的二元关系 , 因此有

R^n \subseteq A \times A

关系

R

的

n

次幂 , 就是

n

个

R

关系逆序合成 :

R^n = \begin{matrix} \underbrace{ R \circ R \circ \cdots \circ R } \\ n 个 R 逆序合成 \end{matrix}

二、关系幂运算示例

集合

A = \{ a, b, c \}

关系

R

是 集合

A

上的二元关系 ,

R \subseteq A \times A

,

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

关系

R

的 幂集个数 :

A

是有限集 ,

A

上的有序对个数是

3 \times 3 = 9

个 ,

A

上的二元关系个数 , 即有序对集合的幂集个数 , 是

2^{3\times 3} =512

个 ;

关系

R

的

0

次幂 :

R^0 = I_A

,

R

关系的

0

次幂是恒等关系 , 关系图是每个顶点都有环 , 顶点之间没有关系 ;

关系

R

的

1

次幂 :

R^1 = R^0 \circ R = R

, 恒等关系

I_A

与任何关系逆序合成 , 结果还是那个关系 ;

关系

R

的

2

次幂 :

\begin{array}{lcl}R^2 & = & R^0 \circ R \\\\ &=& R \circ R \\\\ &=& \{ <a,b> , <b,a> , <a, c> \} \circ \{ <a,b> , <b,a> , <a, c> \} \\\\ &=& \{ <a,a>, <b, b> , <b,c> \}\end{array}

注意上述

\circ

运算时逆序合成 , 从后面的关系中合成前面的关系 ;

关系

R

的

3

次幂 : 与

R_1

相同

\begin{array}{lcl}R^3 & = & R^1 \circ R \\\\ &=& \{ <a,a>, <b, b> , <b,c> \} \circ \{ <a,b> , <b,a> , <a, c> \} \\\\ &=& \{ <a,b>, <a, c> , <b,a> \} \\\\ &=& R^1 \end{array}

关系

R

的

4

次幂 : 与

R_2

相同

关系

R

的

5

次幂 : 与

R_1

相同

关系

R

的

2k

偶数次幂 (

k=1,2, \cdots

) : 与

R_2

相同

关系

R

的

2k + 1

奇数次幂 (

k=0,1,2, \cdots

) : 与

R_1

相同

三、关系幂运算性质

关系幂运算性质 :

关系

R

是 集合

A

上的关系 ,

R \subseteq A \times A

,

m,n

是自然数 ,

m,n \in N

; 关系幂运算有以下两个性质 :

R^m \circ R^n = R^{m + n}
(R^m ) ^n = R^{m n}

相关文章