一、关系的基本概念

1. 定义

关系是集合论中的核心概念，指两个集合笛卡尔积的任意子集。形式化定义为：
设集合 $A$ 和 $B$，其笛卡尔积 $A \times B$ 的子集 $R$ 称为从 $A$ 到 $B$ 的二元关系。若 $A = B$，则称 $R$ 为 $A$ 上的关系。

2. 基本概念

• 定义域 (Domain)：$dom(R) = \{ x \mid \exists y, (x, y) \in R \}$
• 值域 (Range)：$ran(R) = \{ y \mid \exists x, (x, y) \in R \}$
• 域 (Field)：$fld(R) = dom(R) \cup ran(R)$
  示例：若 $R = \{(1, a), (2, b)\}$，则 $dom(R) = \{1, 2\}$，$ran(R) = \{a, b\}$，$fld(R) = \{1, 2, a, b\}$。

二、特殊关系类型

1. 空关系

• 定义：$R = \emptyset$，即不包含任何有序对的关系。
• 性质：不具有自反性。具有对称性，反对称性，传递性。

2. 全域关系

• 定义：$U_A = A \times A$，包含集合 $A$ 上所有可能的有序对。
• 性质：自反、对称、传递。

3. 恒等关系

• 定义：$I_A = \{ (x, x) \mid x \in A \}$，每个元素与自身构成有序对。
• 性质：自反、对称、反对称。

三、关系的表示方法

1. 集合表示法

通过枚举所有有序对或描述规则来定义关系。
示例：$R = \{ (1, a), (2, b) \}$ 或 $R = \{ (x, y) \mid x \in A, y \in B, x > y \}$。

2. 矩阵表示法

• 关系矩阵：设 $A = \{a_1, a_2, \dots, a_m\}$，$B = \{b_1, b_2, \dots, b_n\}$，关系矩阵 $M_R$ 是一个 $m \times n$ 的0-1矩阵，其中：

$$M_R[i][j] = \begin{cases} 1 & \text{若 } (a_i, b_j) \in R \\ 0 & \text{否则} \end{cases}$$

示例：若 $A = \{1, 2\}$，$B = \{a, b\}$，$R = \{(1, a), (2, b)\}$，则：

$$M_R = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$$

3. 图表示法

• 顶点：集合中的元素。
• 边：若 $(a, b) \in R$，则从顶点 $a$ 到 $b$ 画一条有向边。
  示例：若 $R = \{(1, 2), (2, 3)\}$，则图中顶点1指向2，顶点2指向3。

四、关系的性质

1. 自反性

• 定义：$\forall x \in A$，有 $(x, x) \in R$。
• 矩阵特征：主对角线全为1。

2. 反自反性

• 定义：$\forall x \in A$，有 $(x, x) \notin R$。
• 矩阵特征：主对角线全为0。

3. 对称性

• 定义：若 $(x, y) \in R$，则 $(y, x) \in R$。
• 矩阵特征：矩阵是对称矩阵。

4. 反对称性

• 定义：若 $(x, y) \in R$ 且 $(y, x) \in R$，则 $x = y$。
• 矩阵特征：非对角线元素中，若 $M_R[i][j] = 1$，则 $M_R[j][i] = 0$。

5. 传递性

• 定义：若 $(x, y) \in R$ 且 $(y, z) \in R$，则 $(x, z) \in R$。
• 矩阵特征：$M_R^2 \leq M_R$（矩阵幂运算后元素不超过原矩阵）。

五、例题

例题1：验证自反性

题目：设集合 $A = \{1, 2, 3\}$，关系 $R = \{(1,1), (2,2), (3,3), (1,2)\}$，验证 $R$ 是否自反。
解：

• 所有元素 $(1,1)$、$(2,2)$、$(3,3)$ 均属于 $R$，故 $R$ 是自反的。

例题2：构造关系矩阵

题目：设 $A = \{a, b, c\}$，$R = \{(a, b), (b, c), (c, a)\}$，写出关系矩阵 $M_R$。
解：

$$M_R = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}$$

例题3：判断传递性

题目：设 $R = \{(1,2), (2,3)\}$，验证其传递性。
解：

• 需检查是否存在 $(1,3)$。由于 $(1,3) \notin R$，故 $R$ 不满足传递性。

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)