关系的定义
//std::map with bool function
R = {<a,b> | a in A && b in B && bool(a,b)}
如果A == B，则称R为A上的关系
例如一个笛卡尔积
| y1 | y2 | |
|---|---|---|
| x1 | <x1,y1> | <x1,y2> |
| x2 | <x2,y1> | <x2,y2> |
| x3 | <x3,y1> | <x3,y2> |
这个矩阵就是X x Y的笛卡尔积，然后定义关系R
| 1 | 0 |
|---|---|
| 0 | 1 |
| 1 | 1 |
把对应元素取出来，R = {<x1,y1>, <x2,y2>, <x3,y1>, <x3,y2>}
记作x1Ry1, x2Ry2…
空关系
∅ \emptyset∅是AXA的子集，故为一种关系
画成矩阵，整个矩阵就是一个NaN，既不是0也不是1，而是什么都不是。
普通的空关系
| y1 | y2 | y3 | |
|---|---|---|---|
| x1 | NaN | NaN | NaN |
| x2 | NaN | NaN | NaN |
| x3 | NaN | NaN | NaN |
空集的空关系
画不出矩阵。
只要记住空集的空关系具有关系的5大性质: 自反，反自反，对称，反对称，传递性；这全部是由false->true推出来的。
全域关系
R = 全1
恒等关系I A I_AIA
I A I_AIA = 单位矩阵
逆关系
转置矩阵，但是要写成R − 1 R^{-1}R−1
关系的性质
自反
全自环 或 空集上的空关系(可以理解为某种程度上的自环)
I A ⊆ R I_A \subseteq RIA⊆R
反自反
无自环
对称
无单边
R = R T R = R^TR=RT，但是在本书里面逆关系用R − 1 R^{-1}R−1表示，所以变成了R = R − 1 R = R^{-1}R=R−1
反对称
并不是反对称矩阵。反对称矩阵是a[i][j] * a[j][i] == -1，而这里是0，且i != j。不涉及有没有自环的判断，因为那个是自反性的判断。
无双边
R ∩ R − 1 ⊆ I A R \cap R^{-1} \subseteq I_AR∩R−1⊆IA
传递
双边必双环&& 三角必矢量 && 无双边无三角时所有通路长度 <= 1
a i j ∗ a j k ⇒ a i k aij * ajk \Rightarrow aikaij∗ajk⇒aik
R 2 ⊆ R R^2\subseteq RR2⊆R
等价
自反 + 对称 + 传递
此时xRy记作x~y
等价类
x ∈ [ a ] R ∩ S ⟺ < x , a > ∈ R ∩ S ⟺ x R a ∧ x S a x \in [a]_{R \cap S} \iff <x,a> \in R\cap S \iff xRa \land xSax∈[a]R∩S⟺<x,a>∈R∩S⟺xRa∧xSa
关系的运算
除了复合和逆关系，关系的运算是集合的运算而不是矩阵的运算了，例如写R+S，是对称差，具体效果是elemwise取异或。
( A ∪ B ) − 1 = A − 1 ∪ B − 1 (A\cup B)^{-1} = A^{-1} \cup B^{-1}(A∪B)−1=A−1∪B−1
( R ○ S ) − 1 = S − 1 ○ R − 1 (R○S)^{-1} = S^{-1} ○ R^{-1}(R○S)−1=S−1○R−1
复合
满足结合律，满足∪ \cup∪的分配率
矩阵乘法，记作○
A ○ B = { < x , z > ∣ ∃ y ( x A y ∧ y B z ) } A ○ B = \{<x,z> | \exist y(xAy \land yBz)\}A○B={<x,z>∣∃y(xAy∧yBz)}
闭包
在图中添加尽可能少的边，使得R具有某些性质，具有极小性。
自反闭包
r ( R ) = R ∪ I A r(R) = R \cup I_Ar(R)=R∪IA
对称闭包
s ( R ) = R ∪ R − 1 s(R) = R \cup R^{-1}s(R)=R∪R−1
传递闭包
t ( R ) = ∪ 1 n − 1 R i t(R) = \cup_1^{n-1} R^it(R)=∪1n−1Ri
哈斯图
偏序
反对称 + 传递 + 自反
如果是反自反则称为严格偏序
哈斯图是根据偏序关系简化了的关系图，利用传递性尽量少画线，并且用上下关系省略了箭头。
偏序集
pair<set, 其偏序关系的集合>
可比
哈斯图中两点之间有连线
遮盖
哈斯图中的一条线，具有偏序关系的“最短性”
全序集
线序集
哈斯图是一条直线
∀ x ∀ y 可 比 \forall x \forall y可比∀x∀y可比
极元
哈斯图中向上/向下路径中的那些终点都是极元
定义为没有比极元更大/小的其他点，不可比，即没有线相连，也满足“没有其他更大”的定义。
最元
唯一的那个极元
定义为比其他的所有点都大/小，内涵了可比的性质。
界
能顺着重力流向所有元素/被所有元素流向的那些元素
确界
上界的最小元，下界的最大元
例如最小公倍数和最大公因子
良序
任何子图都存在最小元
划分
不漏，不空，不交的一种划分方式，写为vector<vector> = vector<划分块>，vecvec.size() = 秩
在同一个划分块中算一个等价关系
覆盖
如果即划分中的“不漏”的概念
例题
R1 ⊆ \subseteq⊆ R2，求证t(R1) ⊆ \subseteq⊆ t(R2)
