date: 2025-06-14T15:40:00 aliases:

• 离散数学第七章

二元关系

有序对

• 定义：两个元素按照固定顺序组成的组合，记作 $(a,b)$
• 特性：
  • 有序性：$(a,b) \neq (b,a)$（除非 $a=b$）
  • 相等判定：$(a,b)=(c,d) \iff a=c \land b=d$
• 与集合区别：
  • $\{a,b\}=\{b,a\}$（无序）
  • $(a,b)\neq(b,a)$（有序）

二元关系

• 定义：$A \times B$ 的任意子集 $R$ 称为从 $A$ 到 $B$ 的二元关系
• 表示方法：
  • 集合表示：$R = \{(a_1,b_1), (a_2,b_2)...\}$
  • 关系矩阵：$M_R = [m_{ij}]$ 其中 $m_{ij} = 1$ 当且仅当 $(a_i,b_j) \in R$
  • 关系图：顶点表示元素，有向边表示关系
• 特殊关系：
  • 空关系 $\varnothing$
  • 全域关系 $A \times B$
  • 恒等关系 $I_A = \{(a,a) | a \in A\}$

二元关系示例

基础示例

设集合：

• $A = \{1, 2, 3\}$
• $B = \{x, y\}$

则笛卡尔积：

可能的二元关系：

1. 空关系： $R_1 = \varnothing$

2. 全关系： $R_2 = A \times B$

3. 自定义关系（如"小于"关系）： $R_3 = \{(1,x), (1,y), (2,y)\}$

实际意义解释

当 $A$ 是学生集合，$B$ 是课程集合时：

• $A = \{\text{Alice}, \text{Bob}\}$
• $B = \{\text{数学}, \text{物理}\}$

定义选课关系 $R$：

关系矩阵表示

对于 $R_3$ 关系：

（行对应 $A$ 的元素顺序 1,2列对应 $B$ 的元素顺序 x,y）

关系图表示

graph LR
    1 --> x
    1 --> y
    2 --> y

关系的运算

• 基本运算：
  • 并：$R_1 \cup R_2$
  • 交：$R_1 \cap R_2$
  • 补：$\sim R = (A \times B) - R$
• 复合运算：
  • $R \circ S = \{(a,c) | \exists b, (a,b) \in R \land (b,c) \in S\}$
• 逆关系：
  • $R^{-1} = \{(b,a) | (a,b) \in R\}$
• 幂运算：
  • $R^n = R \circ R \circ ... \circ R$（n次复合）

关系的性质

设 $R \subseteq A \times A$：

• 自反性：
  • $\forall a \in A, (a,a) \in R$
  • 关系矩阵主对角线全1
• 反自反性：
  • $\forall a \in A, (a,a) \notin R$
• 对称性：
  • $(a,b) \in R \Rightarrow (b,a) \in R$
  • 关系矩阵对称
• 反对称性：
  • $(a,b) \in R \land (b,a) \in R \Rightarrow a=b$
• 传递性：
  • $(a,b) \in R \land (b,c) \in R \Rightarrow (a,c) \in R$

关系的闭包

• 定义：在关系 $R$ 中添加最少数量的有序对使其具有特定性质
• 闭包类型：
  • 自反闭包：$r(R) = R \cup I_A$
  • 对称闭包：$s(R) = R \cup R^{-1}$
  • 传递闭包：$t(R) = R \cup R^2 \cup R^3 \cup ... = \bigcup_{i=1}^\infty R^i$

Warshall算法（含示例）

算法步骤

1. 输入：关系矩阵 $M_R$（n×n）
2. 初始化：$M = M_R$
3. 核心迭代：

   for k in range(n):
       for i in range(n):
           if M[i][k]:
               for j in range(n):
                   M[i][j] = M[i][j] or M[k][j]

4. 输出：传递闭包矩阵 $M_{t(R)}$

具体示例

设集合 $A = \{1,2,3\}$，关系：

步骤演示：

1. 初始关系矩阵：

   $$M^{(0)} = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix}$$

2. k=1（检查经节点1的路径）：

   • 更新 M[2][1] 和 M[3][1] 无变化 $M^{(1)} = M^{(0)}$

3. k=2（检查经节点2的路径）：

   • 发现 M[1][2]=1 且 M[2][3]=1 ⇒ 添加 (1,3)
   $$M^{(2)} = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix}$$

4. k=3（检查经节点3的路径）：

   • 无新增路径 $M^{(3)} = M^{(2)}$

最终传递闭包：

复杂度分析

• 三重循环 ⇒ $O(n^3)$
• 空间复杂度：$O(n^2)$（邻接矩阵存储）
• 优化：可用位运算加速

应用场景：网络可达性分析/编译器数据流分析/社交网络间接关系计算

等价关系的划分

• 等价关系定义： 同时满足自反、对称、传递的关系
• 等价类： $[a]_R = \{x | (a,x) \in R\}$
• 商集： $A/R = \{[a]_R | a \in A\}$
• 划分定理：
  • 每个等价关系对应一个唯一划分
  • 每个划分对应一个唯一等价关系

偏序关系（含详细示例）

定义与示例

设集合 $A = \{2, 3, 4, 6, 8\}$，定义整除关系：

具体关系：

验证性质：

1. 自反性：每个元素整除自己 ✅
2. 反对称性：若 $a \preceq b$ 且 $b \preceq a$，则 $a=b$ ✅
3. 传递性：$a \preceq b$ 且 $b \preceq c$ ⇒ $a \preceq c$ ✅

哈斯图绘制

graph BT
    8 --> 4 --> 2
    6 --> 2
    6 --> 3

绘制规则：

1. 移除自环（如 2→2）
2. 移除传递边（如 2→8 因存在 2→4→8）
3. 箭头方向默认向上可省略

特殊元素示例

在 $(A, \preceq)$ 中：

• 极大元：8, 6（没有比它们更大的元素）
• 极小元：2, 3（没有比它们更小的元素）
• 最大元：不存在（8和6不可比）
• 最小元：不存在（2和3不可比）

全序 vs 偏序

• 偏序示例：上述整除关系（2和3不可比）
• 全序示例：$(\{1,2,3\}, \leq)$ 的哈斯图：

  graph BT
      3 --> 2 --> 1

界的概念

设 $B = \{2, 4\} \subseteq A$：

• 上界：4, 8（大于等于$Max\{2,4\}$）
• 下界：2（小于等于$Min\{2,4\}$）
• 上确界：4（上界中的最小者）
• 下确界：2（下界中的最大者）

应用场景

1. 任务调度中的依赖关系
2. 文件系统目录结构
3. 软件版本控制中的继承关系