Knowledge
关系知识点
用于复习关系章节的核心概念、性质判定和常见题型。
二元关系
从 A 到 B 的二元关系是 A×B 的任意子集；A 上的关系是 A×A 的子集。
定义
- R⊆A×B 称为从 A 到 B 的二元关系。
- 若 B=A，则 R 称为 A 上的二元关系。
重要公式
- |A|=n 时，A 上的二元关系共有 2^(n²) 个。
常见考法
列举关系、计算关系数量、判断关系是否满足性质。
复习提示
- 关系的本质是“有序对在不在某个集合里”。
易错提醒
关系不一定是映射，一个元素可以对应多个元素或不对应元素。
空关系、全域关系、恒等关系、余关系
特殊关系常作为性质判断、矩阵识别和闭包计算的基础对象。
定义
- 空关系：∅
- 全域关系：E_A=A×A
- 恒等关系：I_A={(x,x) | x∈A}
- 余关系：R̄=A×A−R
典型例子
- I_A 的关系矩阵是单位阵，全域关系矩阵全为 1。
常见考法
识别 ∅、A×A、I_A、R̄，并判断它们的性质。
复习提示
- 恒等关系只保留主对角线上的自环。
易错提醒
余关系是相对于 A×A 的补集，不是普通逆关系。
关系的表示：矩阵、关系图、集合表示
关系可用有序对集合、0-1 矩阵或有向图表示，三者可以互相转换。
定义
- M_R=(r_ij)，r_ij=1 表示 (a_i,b_j)∈R。
常见考法
从矩阵读有序对、从关系图判断性质。
复习提示
- 图上自环对应 (x,x)，双向箭头对应两个有序对。
易错提醒
矩阵行索引是前件，列索引是后件。
关系运算：交、并、差、余、逆
关系作为有序对集合，可直接做集合运算；逆关系把每个有序对调头。
重要公式
- R^{-1}={(y,x) | (x,y)∈R}
- (R^{-1})^{-1}=R
- (R∪S)^{-1}=R^{-1}∪S^{-1}
- M_{R^{-1}}=M_R^T
常见考法
计算 R∪S、R∩S、R−S、R^{-1}，判断性质是否保持。
复习提示
- 求逆关系时逐个调换有序对坐标即可。
易错提醒
R^{-1} 不是补关系，R̄ 也不是逆关系。
关系复合与逆关系
R^{-1} 交换有序对方向；R∘S 表示先按 S 再按 R 连接关系。
定义
- R∘S={(x,z) | 存在 y，使 xSy 且 yRz}。
重要公式
- (R∘S)^{-1}=S^{-1}∘R^{-1}
- R∘I_A=I_A∘R=R
- ∅∘R=R∘∅=∅
典型例子
- 计算复合时可以理解为有向图中走两步。
常见考法
计算复合关系、逆关系及其交并运算。
复习提示
- 矩阵法中使用布尔乘法：乘法取“且”，加法取“或”。
易错提醒
复合顺序很重要，R∘S 与 S∘R 通常不同。
关系的幂与闭包
关系的幂描述重复复合；闭包是在原关系上尽量少加有序对，使其满足指定性质。
定义
- R⁰=I_A，R^{n+1}=R^n∘R。
重要公式
- r(R)=R∪I_A
- s(R)=R∪R^{-1}
- t(R)=R∪R²∪R³∪...
- 若 |A|=n，则 t(R)=R∪R²∪...∪R^n
常见考法
计算自反闭包、对称闭包、传递闭包。
复习提示
- 有限集上关系幂序列必然出现重复，这是传递闭包有限计算的依据。
易错提醒
传递闭包不一定只是 R∪R²，必须继续合成直到稳定。
自反性、反自反性、对称性、反对称性、传递性
这五种性质是判断关系类型的基础，也是等价关系和偏序关系的前置条件。
重要公式
- 自反：∀x∈A, xRx
- 反自反：∀x∈A, x̸Rx
- 对称：R^{-1}=R
- 反对称：R∩R^{-1}⊆I_A
- 传递：R²⊆R
常见考法
根据关系集合、矩阵或关系图逐项判断性质。
复习提示
- 矩阵判断：自反看主对角全 1，反自反看主对角全 0，对称看矩阵是否关于主对角线对称。
易错提醒
反对称不是“不对称”，自环不影响反对称性。
关系性质在运算下的保持性
关系的并、交、差、补并不总保持原有性质，考试常用反例考察。
常见考法
判断两个自反/对称/传递关系做运算后是否仍保性质。
复习提示
- 交运算对五种性质都较稳定；对称性在并、交、差、补下都保持。
易错提醒
两个传递关系的并不一定传递；两个反对称关系的并也不一定反对称。
- 看到“R1、R2 都传递，所以 R1∪R2 传递”要警惕。
等价关系与商集
等价关系同时满足自反、对称、传递；商集 A/R 是所有等价类组成的集合。
定义
- [a]_R={x∈A | xRa}
- A/R={[a]_R | a∈A}
典型例子
- 模 3 同余会把整数按余数分为 3 个等价类。
常见考法
判断等价关系、识别合法划分和商集。
复习提示
- 等价关系的使命是“分类”。
易错提醒
等价类必须互不相交且并起来等于原集合。
划分、第二类 Stirling 数与加细
等价关系与集合划分一一对应；第二类 Stirling 数计数把 n 个不同元素划分成 r 个非空无序块的方法。
定义
- 划分 C 满足：每块非空、并为 A、不同块不相交。
- {n \brace r} 表示 n 个不同元素划分为 r 个非空无序块的方案数。
重要公式
- {n \brace r}=r{n−1 \brace r}+{n−1 \brace r−1}
- 等价关系个数 = Σ_{r=1}^n {n \brace r}
常见考法
判断商集是否合法、计算有限集合上等价关系个数。
复习提示
- 划分越细，对应的等价关系越小。
易错提醒
划分要求每块非空、两两不交、并起来等于全集。
偏序关系与 Hasse 图
偏序关系满足自反、反对称、传递；Hasse 图只保留覆盖关系并省略自环和传递边。
定义
- 偏序集常记作 (A,≤)。
- Hasse 图默认向上读，小元素在下，大元素在上。
常见考法
求极大/极小元、上界/下界、上确界/下确界。
复习提示
- 画 Hasse 图时：不画自环，不画由传递性推出的边。
易错提醒
极大元不一定唯一，上确界也不一定属于给定子集。
- 哈斯图中相邻覆盖边才连线，不能把所有可比较元素都连起来。
链、全序、拟序与上下确界
链是两两可比的子集，全序要求任意两元素可比；上下确界描述子集在偏序中的最紧上界和下界。
定义
- 上确界 sup M 是 M 的最小上界。
- 下确界 inf M 是 M 的最大下界。
- 拟序关系具有反自反性和传递性。
典型例子
- 整除偏序中，{2,3} 的上界是共同倍数，下界是共同因数。
常见考法
区分最大元/极大元，最小元/极小元，求 sup 和 inf。
复习提示
- 求上下确界时，候选元素必须来自当前偏序集。
易错提醒
最大元必是极大元，反之不一定；最大元若存在则唯一。