Appearance
关系是描述元素之间联系的核心工具。本笔记梳理关系的定义与表示、关系的运算与性质、闭包、等价关系（等价类/商集）以及偏序关系（哈斯图/特殊元素）。
关系的基本概念
定义与表示
- 有序对 (a,b)：有序，a≠b 时 (a,b)≠(b,a)
- 笛卡尔积 A×B = {(a,b) | a∈A, b∈B}；|A×B| = |A|·|B|
- 二元关系 R：A×B 的子集。aRb 表示 (a,b)∈R
- A 上的关系：R ⊆ A×A
三种表示方法：
- 关系矩阵：MR = (rij)，rij = 1 当且仅当 (ai,bj)∈R
- 关系图：结点表示元素，有向边表示关系
- 集合列举法：{(a,b), (c,d), …}
特殊关系
- 空关系 ∅、全域关系 A×A、恒等关系 IA = {(x,x) | x∈A}
关系的运算
| 运算 | 定义 |
|---|---|
| 逆关系 R⁻¹ | {(y,x) |
| 复合 R∘S | {(x,z) |
| 幂 Rⁿ | 关系自身复合 n 次 |
- 复合满足结合律：(R∘S)∘T = R∘(S∘T)
- (R∘S)⁻¹ = S⁻¹∘R⁻¹
关系的性质（核心考点）
| 性质 | 定义 | 矩阵特征 | 图特征 |
|---|---|---|---|
| 自反 | ∀x∈A, xRx | 主对角线全 1 | 每个结点有环 |
| 反自反 | ∀x∈A, (x,x)∉R | 主对角线全 0 | 无环 |
| 对称 | xRy ⇒ yRx | 矩阵对称 | 双向边成对 |
| 反对称 | xRy∧yRx ⇒ x=y | 对称位置不同时为 1 | 无成对双向边 |
| 传递 | xRy∧yRz ⇒ xRz | — | 间接可达则直达 |
自反与反自反不是非此即彼（可都不是）；对称与反对称也不是。
关系的闭包（考点）
在 R 中添加最少元素使其满足某性质：
| 闭包 | 定义 | 求法 |
|---|---|---|
| 自反闭包 r(R) | R ∪ IA | 主对角线置 1 |
| 对称闭包 s(R) | R ∪ R⁻¹ | 矩阵与转置求并 |
| 传递闭包 t(R) | 最小传递关系 | R ∪ R² ∪ R³ ∪ …（或 Warshall 算法） |
复合闭包公式：tsr(R) = t(s(r(R)))（先自反、再对称、再传递）。
等价关系（重点）
定义
满足自反、对称、传递的关系称为等价关系。例：模 m 同余关系、学生按班级分组。
等价类与商集
- 等价类 [a]R = {x | xRa}：与 a 等价的所有元素
- 商集 A/R：所有等价类构成的集合
- 等价类性质：不同等价类不相交；所有等价类的并 = A（划分）
- 等价关系 ⇔ 划分一一对应：每个等价关系决定一个划分，反之亦然
偏序关系（重点）
定义
满足自反、反对称、传递的关系称为偏序关系，记作 ≼。(A, ≼) 为偏序集。
哈斯图
简化关系图：去掉自环、去掉传递边、调整位置使边向上。例：整除关系、集合包含关系。
特殊元素（考点）
| 元素 | 定义 |
|---|---|
| 极大元 | 没有比它更大的元素（可能多个） |
| 极小元 | 没有比它更小的元素 |
| 最大元 | 比所有元素都大（唯一） |
| 最小元 | 比所有元素都小（唯一） |
| 上界/下界 | 比某子集所有元素都大/小 |
| 上确界/下确界 | 上界中的最小者/下界中的最大者 |
- 全序关系：任意两元素可比（如 ≤ 在自然数上）
- 若偏序集中任意两元素都有最小上界和最大下界 → 构成格（见代数系统）
一句话总结
关系三性质组合定类型：自反对称传递 = 等价关系（对应划分），自反反对称传递 = 偏序关系（哈斯图找特殊元素）；传递闭包是最常考的闭包计算。
相关概念
- 离散数学-函数 — 函数是特殊关系（每个 x 对应唯一 y）
- 离散数学-集合与证明方法 — 集合运算是关系运算的基础
- 离散数学-代数系统 — 偏序集加上下界运算即格
- 离散数学-初等数论 — 模 m 同余是等价关系的典型实例