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

韩曙亮

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

2.9K0

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

文章目录

一、关系幂运算

关系

的

次幂定义 :

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^0

是恒等关系

I_A

, 关系

的

n + 1

次幂等于

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

其中

n \geq 0

;

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

, 恒等关系与关系

逆序合成 , 结果还是关系

, 这个关系

可以是任意关系 ;

恒等关系就是集合

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

关系

幂运算结果

R^n

关系也是集合

上的二元关系 , 因此有

R^n \subseteq A \times A

关系

的

次幂 , 就是

个

关系逆序合成 :

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

二、关系幂运算示例

集合

A = \{ a, b, c \}

关系

是集合

上的二元关系 ,

R \subseteq A \times A

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

关系

的幂集个数 :

是有限集 ,

上的有序对个数是

3 \times 3 = 9

个 ,

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

2^{3\times 3} =512

个 ;

关系

的

次幂 :

R^0 = I_A

关系的

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

关系

的

次幂 :

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

, 恒等关系

I_A

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

关系

的

次幂 :

\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_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_2

相同

关系

的

次幂 : 与

R_1

相同

关系

的

偶数次幂 (

k=1,2, \cdots

) : 与

R_2

相同

关系

的

2k + 1

奇数次幂 (

k=0,1,2, \cdots

) : 与

R_1

相同

三、关系幂运算性质

关系幂运算性质 :

关系

是集合

上的关系 ,

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}

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

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

集合