等价关系与等价类 - NOI提高级教程

📖 离散数学性质：等价关系与集合划分

在离散数学中，二元关系 (Binary Relation) 描述了集合中元素之间的某种关联。如果某种关系满足以下三个条件，则称其为等价关系 (Equivalence Relation)：

📐 等价关系三大核心性质

设 $R$ 是定义在集合 $A$ 上的二元关系：

自反性 (Reflexivity)：对于集合中任意元素 $x \in A$，均有 $(x, x) \in R$。（在关系矩阵中表现为：对角线元素全为 1）
对称性 (Symmetry)：若元素 $x, y \in A$ 满足 $(x, y) \in R$，则必然有 $(y, x) \in R$。（在关系矩阵中表现为：矩阵关于主对角线对称）
传递性 (Transitivity)：若 $(x, y) \in R$ 且 $(y, z) \in R$，则必然有 $(x, z) \in R$。（如果在矩阵中 $M_{i,j}=1$ 且 $M_{j,k}=1$，则必须 $M_{i,k}=1$）

📐 等价类与划分定理 (Partitions)

如果关系 $R$ 是等价关系，那么对于任意元素 $x \in A$，所有与 $x$ 满足等价关系的元素构成的集合称为 $x$ 的等价类 (Equivalence Class)，记作 $[x]$：

$[x] = \{ y \in A \mid (x, y) \in R \}$

划分定理：等价关系可将集合 $A$ 唯一地划分为若干个两两不相交的子集之和。这些子集即为等价类。

预设快捷矩阵：

直接点击下方矩阵的方格可修改元素之间的关系（1 代表有关系，0 代表无关系）。

自反性 (Reflexive) 是

对称性 (Symmetric) 是

传递性 (Transitive) 是

是否为等价关系是

📋 5 × 5 关系邻接矩阵与等价类泡泡划分

等价类划分集合 (Partitions)

// 检查二元关系性质 (N = 5)
bool checkTransitive(bool R[5][5]) {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 5; k++) {
                // 存在 R[i][j] 和 R[j][k] 为 1，但 R[i][k] 为 0
                if (R[i][j] && R[j][k] && !R[i][k]) {
                    return false; // 违反传递性
                }
            }
        }
    }
    return true;
}

📋 关系属性分析步骤