注意
表格没写 $\Leftrightarrow$ 没有固定关系！
证明技巧
很多性质证明用反证法会更轻松
关系性质
| 保留性质 | 自反 | 反自反 | 对称 | 反对称 | 传递 |
|---|---|---|---|---|---|
| 逆 $A^{-1}$ | ✅ | ✅ | ✅ | ✅ | ✅ |
| 交 $A\cap B$ | ✅ | ✅ | ✅ | ✅ | ✅ |
| 并 $A\cup B$ | ✅ | ✅ | ✅ | ||
| 差 $A-B$ | ✅ | ✅ | ✅ | ||
| 复合 $A \circ B$ | ✅ | ||||
| Warshall 幂 $A^{n}$ | ✅ | ✅ | ✅ | ||
| 自反闭包 $r(A)$ | $\to$ ✅ | ✅ | ✅ | ||
| 对称闭包 $s(A)$ | ✅ | $\to$ ✅ | |||
| 传递闭包 $t(A)$ | ✅ | ✅ | $\to$ ✅ |
代数性质
| 关系运算 | 笛卡尔积 $A\times B$ | 关系复合 $A \circ B$ | Warshall 幂 $R^{n}$ |
|---|---|---|---|
| 交换律 | ❌ | ❌ | |
| 结合律 | ❌ | $(A\circ B) \circ C = A\circ (B \circ C)$ | |
| 交 | $A\times (B\cap C)=(A\times B) \cap (A\times C)$ | $A \circ (B \cap C) \subset (A \circ B) \cap (A \circ C)$ | $(R\cap S)^{n}\subset R^{n}\cap S^{n}$ |
| 并 | $A\times (B\cup C)=(A\times B) \cup (A\times C)$ | $A \circ (B \cup C) = (A \circ B) \cup (A \circ C)$ | $(R\cup S)^{n}=R^{n}\cup S^{n}$ |
| 差 | $A\times (B\cap C)=(A\times B) \cap (A\times C)$ | $A \circ (B - C) \supset (A \circ B) - (A \circ C)$ | |
| 逆 | $(A\times B)^{-1}=B\times A$ | $(A\circ B)^{-1}=B^{-1}\circ A^{-1}$ | $(R^{n})^{-1}=(R^{-1})^{n}$ |
| 闭包运算 | 自反闭包 $r(R)$ | 对称闭包 $s(R)$ | 传递闭包 $t(R)$ |
|---|---|---|---|
| 对交换序 | $r(A\cap B)=r(A)\cap r(B)$ | $s(A\cap B)\subset s(A)\cap s(B)$ | $t(A\cap B)\subset t(A)\cap t(B)$ |
| 对并换序 | $r(A\cup B)=r(A)\cup r(B)$ | $s(A\cup B) = s(A)\cup s(B)$ | $t(A\cup B)\supset t(A)\cup t(B)$ |
| 对逆换序 | $r(R^{-1})=(r(R))^{-1}$ | $s(R^{-1})=s(R)$ | $t(R^{-1})=(t(R))^{-1}$ |
| 对幂换序 | $r(R^{n})\subset(r(R))^{n}$ | $s(R^{n})\subset(s(R))^{n}$ | $t(R^{n})\subset(t(R))^{n}$ |
| 闭包换序 | $rt=tr,ts=sr$ | $st=ts,sr=rs$ | $tr=rt,ts=st$ |
约定
表中所有运算的所有分配律都是 左分配 $\land$ 右分配的 例子只写左分配
子集性质
| 运算 | 保留子集性质 |
|---|---|
| 交 | ✅ |
| 并 | ✅ |
| 逆 | $R\subset S \Leftrightarrow R^{-1}\subset S^{-1}$ |
| 差 | ❌ |
| 复合 | $R\subset S \Leftrightarrow R\circ T\subset S\circ T$ |
| 三闭包 | $R\subset S \Leftrightarrow r(R)\subset r(S)$ |
| 幂 | $R\subset S \Leftrightarrow R^{n} \subset S^{n}$ |