关系的幂运算
R n R^n Rn：在 R R R的有向图中找长度为 n n n的线段
关系的特殊性质及其闭包
特殊性质
| 自反关系 | 反自反关系 | 对称关系 | 反对称关系 | 传递关系 | |
|---|---|---|---|---|---|
| 内容 | |||||
| 充要条件 | I X ? R I_X\subseteq R IX??R | R ∩ I X = ? R\cap I_X=\empty R∩IX?=? | R ? 1 = R R^{-1}=R R?1=R | R ∩ R ? 1 ? I X R\cap R^{-1}\subseteq I_X R∩R?1?IX? | R 2 ? R R^2\subseteq R R2?R |
| 关系矩阵 | 对角线全为 1 1 1 | 对角线全为 0 0 0 | 对称 | 任意两个相互对称的位置上至少有一个 0 0 0 | |
| 不动点 | r ( R ) = R r(R)=R r(R)=R | s ( R ) = R s(R)=R s(R)=R | t ( R ) = R t(R)=R t(R)=R | ||
| 备注 | 可以推出 ? n ∈ Z + , R n ? R \forall n\in Z^+,R^n\subseteq R ?n∈Z+,Rn?R |
特殊结论
-
存在既对称又反对称的关系
即满足 ? ( x , y ) ∈ R , ( y , x ) ∈ R \forall (x,y)\in R,(y,x)\in R ?(x,y)∈R,(y,x)∈R（对称）， ? ( x , y ) ∈ R 且 ( y , x ) ∈ R , x = y \forall (x,y)\in R且(y,x)\in R,x=y ?(x,y)∈R且(y,x)∈R,x=y（反对称）。于是有两个找特例的角度，
- 该关系中的所有 ( x , y ) (x,y) (x,y)都满足上述条件，即恒等关系；
- 不存在 ( x , y ) ∈ R (x,y)\in R (x,y)∈R，即空关系。
对称不可以推出非反对称，反对称不可以推出非对称
-
存在既非对称又非反对称的关系
将对称、反对称关系取反，全称量词化为存在量词，即满足 ? ( x , y ) ∈ R , ( y , x ) ? R \exist (x,y)\in R,(y,x)\notin R ?(x,y)∈R,(y,x)∈/?R（非对称）， ? ( x , y ) ∈ R , ( y , x ) ∈ R , x ≠ y \exist (x,y)\in R,(y,x)\in R,x\neq y ?(x,y)∈R,(y,x)∈R,x??=y（非反对称）。于是只要找到一个关系，使其中即存在一对对称的 ( x , y ) (x,y) (x,y)，又存在一个单独的 ( x , y ) (x,y) (x,y)，例如
R = { ( 1 , 2 ) , ( 2 , 1 ) , ( 3 , 4 ) } R=\{(1,2),(2,1),(3,4)\} R={ (1,2),(2,1),(3,4)}非对称不可以推出反对称，非反对称不可以推出对称
闭包
设 R R R是 X X X上的关系， P P P是某种关系的性质。包含 R R R的、具有性质 P P P的、 X X X上的最小关系为 R R R的 P P P闭包，记为 R P R^P RP.
条件
- R ? R P R\subseteq R^P R?RP
- R P R^P RP具有性质 P P P
- ? X \forall X ?X上的具有性质 P P P的关系 R ′ R' R′，若 R ? R ′ R\subseteq R' R?R′，则 R P ? R ′ R^P\subseteq R' RP?R′
? S [ ( R ? S ∧ S 有 性 质 P ) → P ( R ) ? S ] \forall S[(R\subseteq S \wedge S有性质P)\rightarrow P(R)\subseteq S] ?S[(R?S∧S有性质P)→P(R)?S]
三个特殊闭包
【单调性】和【闭包和并运算的关系】中的前提 R 1 ? R 2 ? A × A R_1\subseteq R_2\subseteq A\times A R1??R2??A×A省略。
| 自反闭包 | 对称闭包 | 传递闭包 | |
|---|---|---|---|
| 表达式 | r ( R ) = R ∪ I X r(R)=R\cup I_X r(R)=R∪IX? | s ( R ) = R ∪ R ? 1 s(R)=R\cup R^{-1} s(R)=R∪R?1 | t ( R ) = ? n ∈ N R n t(R)=\bigcup_{n\in N} R^n t(R)=?n∈N?Rn |
| 关系图 | 加环 | 将单向线扩充为双向线 | 将两步可达的路径直接首尾相连 |
| 关系矩阵 | 把主对角线全置1 | 以主对角线为基准进行对称操作 | M t ( r ) = M R ∨ M R 2 ∨ ? ∨ M R n M_{t(r)}=M_R \vee M_{R^2} \vee \cdots \vee M_{R^n} Mt(r)?=MR?∨MR2?∨?∨MRn? |
| 单调性 | r ( R 1 ) ? r ( R 2 ) r(R_1)\subseteq r(R_2) r(R1?)?r(R2?) | s ( R 1 ) ? s ( R 2 ) s(R_1)\subseteq s(R_2) s(R1?)?s(R2?) | t ( R 1 ) ? t ( R 2 ) t(R_1)\subseteq t(R_2) t(R1?)?t(R2?) |
| 闭包和并运算的关系 | r ( R 1 ) ∪ r ( R 2 ) = r ( R 1 ∪ R 2 ) r(R_1)\cup r(R_2)=r(R_1\cup R_2) r(R1?)∪r(R2?)=r(R1?∪R2?) | s ( R 1 ) ∪ s ( R 2 ) = s ( R 1 ∪ R 2 ) s(R_1)\cup s(R_2)=s(R_1\cup R_2) s(R1?)∪s(R2?)=s(R1?∪R2?) | t ( R 1 ) ∪ t ( R 2 ) ? t ( R 1 ∪ R 2 ) t(R_1)\cup t(R_2)\subseteq t(R_1\cup R_2) t(R1?)∪t(R2?)?t(R1?∪R2?) |
| 推论 | 若$ |
证明
单调性
（以自反闭包为例）由定义出发，由于 R 1 ? r ( R 1 ) R_1\subseteq r(R_1) R1??r(R1?)，且 r ( R 1 ) r(R_1) r(R1?)是包含 R 1 R_1 R1?的最小自反二元关系，同时 R 1 ? R 2 ? r ( R 2 ) R_1\subseteq R_2\subseteq r(R_2) R1??R2??r(R2?)，且 r ( R 2 ) r(R_2) r(R2?)自反，所以 r ( R 1 ) ? r ( R 2 ) r(R_1)\subseteq r(R_2) r(R1?)?r(R2?)。
闭包和并运算的关系
自反闭包和对称闭包
（以自反闭包为例）
-
先证 r ( R 1 ) ∪ r ( R 2 ) ? r ( R 1 ∪ R 2 ) r(R_1)\cup r(R_2)\subseteq r(R_1\cup R_2) r(R1?)∪r(R2?)?r(R1?∪R2?).
由单调性，
R 1 ∪ R 2 ? r ( R 1 ) ∪ r ( R 2 ) ? r ( R 1 ∪ R 2 ) R_1\cup R_2\subseteq r(R_1)\cup r(R_2)\subseteq r(R_1\cup R_2) R1?∪R2??r(R1?)∪r(R2?)?r(R1?∪R2?) -
再证 r ( R 1 ∪ R 2 ) ? r ( R 1 ) ∪ r ( R 2 ) r(R_1\cup R_2) \subseteq r(R_1)\cup r(R_2) r(R1?∪R2?)?r(R1?)∪r(R2?).
由定义， r ( R 1 ∪ R 2 ) r(R_1\cup R_2) r(R1?∪R2?)是包含 R 1 ∪ R 2 R_1\cup R_2 R1?∪R2?的最小自反二元关系，同时 R 1 ∪ R 2 ? r ( R 1 ) ∪ r ( R 2 ) R_1\cup R_2 \subseteq r(R_1)\cup r(R_2) R1?∪R2??r(R1?)∪r(R2?)，且 r ( R 1 ) ∪ r ( R 2 ) r(R_1)\cup r(R_2) r(R1?)∪r(R2?)自反，所以 r ( R 1 ∪ R 2 ) ? r ( R 1 ) ∪ r ( R 2 ) r(R_1\cup R_2) \subseteq r(R_1)\cup r(R_2) r(R1?∪R2?)?r(R1?)∪r(R2?)。
综上， r ( R 1 ) ∪ r ( R 2 ) = r ( R 1 ∪ R 2 ) r(R_1)\cup r(R_2)=r(R_1\cup R_2) r(R1?)∪r(R2?)=r(R1?∪R2?).
传递闭包
问题在于 t ( R 1 ) ∪ t ( R 2 ) t(R_1)\cup t(R_2) t(R1?)∪t(R2?)不一定传递。
例如 R 1 = { ( a , b ) , ( b , c ) , ( a , c ) } , R 2 = { ( c , d ) } R_1=\{(a,b),(b,c),(a,c)\},R_2=\{(c,d)\} R1?={ (a,b),(b,c),(a,c)},R2?={ (c,d)}.
关系图理解
求自反/对称闭包时，分别加环和一起加环/分别加边和一起加边是等效的。但在求传递闭包时，需要找长度为2的边，那么并集后可能出现新的长度为2的边，这是之前未曾首尾连接的。
表达式
自反闭包
对称闭包
传递闭包
闭包运算和关系性质
自反
对称
传递
交换性
r s ( R ) = r ( s ( R ) ) rs(R)=r(s(R)) rs(R)=r(s(R))
r s ( R ) = s r ( R ) rs(R)=sr(R) rs(R)=sr(R)
r s ( R ) = r ( R ∪ R ? 1 ) = R ∪ R ? 1 ∪ I A = ( I A ∪ R ) ∪ ( I A ? 1 ∪ R ? 1 ) = ( I A ∪ R ) ∪ ( I A ∪ R ) ? 1 = s ( I A ∪ R ) = s r ( R ) \begin{aligned} rs(R) &= r(R\cup R^{-1}) \\ &= R\cup R^{-1}\cup I_A \\ &= (I_A\cup R)\cup (I_A^{-1}\cup R^{-1}) \\ &= (I_A\cup R)\cup (I_A\cup R)^{-1} \\ &= s(I_A\cup R) \\ &=sr(R) \end{aligned} rs(R)?=r(R∪R?1)=R∪R?1∪IA?=(IA?∪R)∪(IA?1?∪R?1)=(IA?∪R)∪(IA?∪R)?1=s(IA?∪R)=sr(R)?
r t ( R ) = t r ( R ) rt(R)=tr(R) rt(R)=tr(R)
r t ( R ) = r ( R ∪ R 2 ∪ ? ) = I A ∪ R ∪ R 2 ∪ ? = ( I A ∪ R ) ∪ ( I A ∪ R ∪ R 2 ) ∪ ? = t ( I A ∪ R ) = t r ( R ) \begin{aligned} rt(R) &= r(R\cup R^2\cup\cdots) \\ &= I_A\cup R\cup R^2\cup\cdots \\ &= (I_A\cup R)\cup (I_A\cup R\cup R^2)\cup\cdots \\ &= t(I_A\cup R) \\ &= tr(R) \end{aligned} rt(R)?=r(R∪R2∪?)=IA?∪R∪R2∪?=(IA?∪R)∪(IA?∪R∪R2)∪?=t(IA?∪R)=tr(R)?
s t ( R ) ? t s ( R ) st(R)\subseteq ts(R) st(R)?ts(R)
s t ( R ) ? s t ( s ( R ) ) 单 调 性 = s ( t s ( R ) ) 结 合 律 = t s ( R ) s ( R ) 对 称 ， 所 以 t s ( R ) 也 对 称 ( 定 理 2.25 ( 2 ) ) ， s ( t s ( R ) ) = t s ( R ) ( 不 动 点 ) \begin{aligned} st(R) &\subseteq st(s(R)) \quad 单调性 \\ &= s(ts(R)) \quad 结合律 \\ &= ts(R) \quad\quad s(R)对称，所以ts(R)也对称(定理2.25(2))，s(ts(R))=ts(R)(不动点) \\ \end{aligned} st(R)??st(s(R))单调性=s(ts(R))结合律=ts(R)s(R)对称，所以ts(R)也对称(定理2.25(2))，s(ts(R))=ts(R)(不动点)?
