一、关系幂运算

---

关系 $R$ 的 $n$ 次幂定义 :

$R\subseteq A\times A,n\in N$

$\{\begin{array}{ll}{R}^0=I_A& \\ R^{n+1}=R^n\circ R& (n\ge 0)\end{array}$

关系 $R$ 是 集合 $A$ 上的 二元关系 , $R$ 的 $0$ 次幂 $R^0$ 是恒等关系 $I_A$ , 关系 $R$ 的 $n+1$ 次幂等于 $R^{n+1}=R^n\circ R$ 其中 $n\ge 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{array}{c}\underbrace{R\circ R\circ \cdots \circ R}\\ n个R逆序合成\end{array}$

二、关系幂运算示例

---

集合 A = { a , b , c } A = \{ a, b, c \} A={a,b,c} 关系 $R$ 是 集合 $A$ 上的二元关系 , $R\subseteq A\times A$ ,

R = { < a , b > , < b , a > , < a , c > } R = \{ <a,b> , <b,a> , <a, c> \} 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$ 次幂 :

R 2 = R 0 ∘ R = R ∘ R = { < a , b > , < b , a > , < a , c > } ∘ { < a , b > , < b , a > , < a , c > } = { < a , a > , < b , b > , < b , c > } \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} R2​====​R0∘RR∘R{<a,b>,<b,a>,<a,c>}∘{<a,b>,<b,a>,<a,c>}{<a,a>,<b,b>,<b,c>}​

注意上述 $\circ$ 运算时逆序合成 , 从后面的关系中合成前面的关系 ;

关系 $R$ 的 $3$ 次幂 : 与 $R_1$ 相同

R 3 = R 1 ∘ R = { < a , a > , < b , b > , < b , c > } ∘ { < a , b > , < b , a > , < a , c > } = { < a , b > , < a , c > , < b , a > } = 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} R3​====​R1∘R{<a,a>,<b,b>,<b,c>}∘{<a,b>,<b,a>,<a,c>}{<a,b>,<a,c>,<b,a>}R1​

关系 $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^{mn}$