关系的特殊性质及其闭包
特殊性质
| 自反关系 | 反自反关系 | 对称关系 | 反对称关系 | 传递关系 | |
|---|---|---|---|---|---|
| 内容 | |||||
| 充要条件 | 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 | |
| 备注 | 可以推出 ∀ n ∈ Z + , R n ⊆ R \forall n\in Z^+,R^n\subseteq R ∀n∈Z+,Rn⊆R |
闭包
设 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′.
三个特殊闭包
自反闭包
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∈NRn
推论
若 ∣ X ∣ = n |X|=n ∣X∣=n，则 t ( R ) = ⋃ m = 1 n R n t(R)=\bigcup_{m=1}^n R^n t(R)=⋃m=1nRn
关系矩阵
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
等价关系和划分
等价关系和等价类
集合 X X X上自反、对称且传递的关系称为 X X X上的等价关系。
设
R
R
R是
X
X
X上的等价关系，
x
∈
X
x\in X
x∈X，定义
X
X
X的子集
[
x
]
R
=
{
y
∣
y
∈
X
,
且
y
R
x
}
[x]_R=\{y|y\in X,且yRx\}
[x]R={y∣y∈X,且yRx}
称
[
x
]
R
[x]_R
[x]R为
x
x
x（关于
R
R
R）的等价类，
x
x
x为等价类
[
x
]
R
[x]_R
[x]R的代表元。
也就是说， x ( ∈ X ) x(\in X) x(∈X)的等价类 [ x ] R [x]_R [x]R由 X X X中所有与 x x x等价的元素组成。
性质
-
若 ( x , y ) ∈ R (x,y)\in R (x,y)∈R，则 [ x ] R = [ y ] R [x]_R=[y]_R [x]R=[y]R
x , y x,y x,y同样具有关系 R R R
- 任意等价类中的任意一个元素都可以作为该等价类的代表元
-
若 ( x , y ) ∉ R (x,y)\notin R (x,y)∈/R，则 [ x ] R ∩ [ y ] R = ∅ [x]_R\cap [y]_R=\empty [x]R∩[y]R=∅
- 任意两个等价类要么相等要么没有公共元素
-
⋃ z ∈ X [ z ] R = X \bigcup_{z\in X}[z]_R=X ⋃z∈X[z]R=X
- 等价类是由所有那些相互等价的元素组成的，且其外的元素都不与其中的元素等价
商集
X
X
X上关于
R
R
R的所有等价类组成的集合称为
X
X
X关于
R
R
R的商集，记为
X
/
R
X/R
X/R，即
X
/
R
=
{
[
x
]
R
∣
x
∈
X
}
X/R=\{[x]_R|x\in X\}
X/R={[x]R∣x∈X}
划分
设 π \pi π是集合 X X X的非空子集的集合（ π ⊆ P ( X ) \pi\subseteq P(X) π⊆P(X) ），满足
- ∀ A , B ∈ π , A = B 或 A ∩ B = ∅ \forall A,B\in \pi,A=B或A\cap B=\empty ∀A,B∈π,A=B或A∩B=∅
- ⋃ A ∈ π = X \bigcup_{A\in\pi}=X ⋃A∈π=X
则称 π \pi π是 X X X的划分， π \pi π中的元素称为该划分的划分块。
划分和等价关系
等价关系和划分可以相互导出。
性质
-
设 R R R是 X X X上的等价关系，那么商集 X / R X/R X/R是 X X X的划分
记由 R R R导出的划分 X / R X/R X/R为 π R \pi_R πR
-
设 π \pi π是集合 X X X的划分，则关系
R = { ( x , y ) ∣ x , y 同 属 于 π 的 一 个 划 分 块 } R=\{(x,y)|x,y同属于\pi的一个划分块\} R={(x,y)∣x,y同属于π的一个划分块}
则 R R R是 X X X上的等价关系。这样导出的 R R R记为 R π R_{\pi} Rπ
推论
R = R π R , π = π R π R=R_{\pi_R},\quad \pi=\pi_{R_{\pi}} R=RπR,π=πRπ
所以本质上，等价关系和划分描述的是同一件事情的两个方面。
证明
π R = X / R ; R π R = { ( x , y ) ∣ x , y ∈ [ u ] R } ⇒ ( x , y ) ∈ R \pi_R=X/R;R_{\pi_R}=\{(x,y)|x,y\in[u]_R\}\Rightarrow (x,y)\in R πR=X/R;RπR={(x,y)∣x,y∈[u]R}⇒(x,y)∈R
偏序关系
集合 X X X上自反、反对称和传递的关系称为 X X X上的偏序关系（偏序），又称部分序关系（部分序）。
- 通常用 ≤ \leq ≤表示 x x x和 y y y满足这种偏序关系
- x < y x<y x<y表示 x ≤ y x\leq y x≤y且 x ≠ y x\neq y x=y，这时称 x x x在 y y y的前面或 y y y在 x x x的后面
全序关系
若" ≤ \leq ≤"是 X X X上的偏序，且对于 X X X中的任意两个元素 x , y x,y x,y， x ≤ y x\leq y x≤y和 y ≤ x y\leq x y≤x总有一个成立（可比较），则称“ ≤ \leq ≤”为 X X X上的全序关系（全序）。
偏序集
( X , ≤ ) (X,\leq) (X,≤)
若 ≤ \leq ≤是全序，则上述标记为全序集。
哈斯图
有限偏序集可以直观地表示为哈斯图。
覆盖
设 ( X , ≤ ) (X,\leq) (X,≤)是偏序集，对于任意的 x , y ∈ X x,y\in X x,y∈X，若 x < y x<y x<y，且不存在 z z z，使得 x < z < y x<z<y x<z<y，则称 y y y覆盖 x x x，或称 y y y是 x x x的直接后继。
哈斯图
规定结点 x , y x,y x,y之间有箭头当且仅当 y y y覆盖 x x x，且 y y y位于 x x x的上方。
全序集的哈斯图是一条直线。
性质
最大元和最小元