关系的运算

关系的复合运算

关系的逆运算

复合运算的逆是逆的反序复合

$$|R|=|R^{-1}|$$ $$I_A\circ R=R\circ I_B=R$$

满足结合律

---

A ---> B ---> C ---> D
   R     S1S2    T

上面都不是空集

复合关系满足对并的分配律，内层符号（并）不变

$$R\circ (S_1\cup S_2)=(R\circ S_1)\cup (R\circ S_2)$$

交的话 $S_1\cap S_2$ 更加严格，分配完会放大（中间元素可以不同）

$$R\circ (S_1\cap S_2)\subseteq (R\circ S_1)\cap (R\circ S_2)$$

T 在后面的情况也是一样的

---

逆关系满足对交并差的 分配律，内层符号不变

$$S^{-1}\subseteq R^{-1}⟺S\subseteq R$$ $${\bar{S}}^{-1}=\overline{(S^{-1})}$$

---

幂运算

$$R^0=I_A$$ $$R^i=R^{i-1}\circ R$$

不满足 交换律，但是用 结合律 可以写成幂的形式

---

$$|A|=n$$

R 是 A 上的二元关系，则

$$\bigcup _{i=1}^{\infty }{R}^i=\bigcup _{i=1}^n{R}^i$$

证明 只要证明大于 n 的情况

通过 鸽笼原理 可以消掉中间环路，让关系属于右边的子集，显然右边是左边的子集，所以两边相等