2.4 二元关系基本概念

二元关系基本概念

关系的定义

二元关系（Binary Relation）：设 $A,B$ 为两个非空集合，$A\times B$ 的任意子集 $R$ 称为从 $A$ 到 $B$ 的二元关系。若 $(x,y)\in R$，则称 $x$ 与 $y$ 有 $R$ 关系，记作 $xRy$；若 $(x,y)\notin R$，则称 $x$ 与 $y$ 没有 $R$ 关系。

当 $A=B$ 时，$R$ 称为 $A$ 上的二元关系。

空关系：空集 $\varnothing$ 也是一个二元关系，称为空关系。

全关系：$E_A=A\times A$ 称为 $A$ 上的全域关系（或全关系）。

恒等关系：$I_A=\{(x,x)\mid x\in A\}$ 称为 $A$ 上的恒等关系。

关系的表示方法

集合表示法

直接用有序对的集合表示关系，如 $R=\{(a_1,b_1),(a_2,b_2),\dots \}$。

关系矩阵

设 $A=\{a_1,a_2,\dots ,a_m\}$，$B=\{b_1,b_2,\dots ,b_n\}$，$R$ 是从 $A$ 到 $B$ 的关系。定义 $m\times n$ 矩阵 $M_R=(r_{ij})$，其中：

• $r_{ij}=1$ 当 $(a_i,b_j)\in R$
• $r_{ij}=0$ 当 $(a_i,b_j)\notin R$

关系图

以 $A$ 中元素为结点，若 $(a_i,b_j)\in R$，则从 $a_i$ 到 $b_j$ 画一条有向边。当 $A=B$ 时，关系图是有向图，自环表示 $(a_i,a_i)\in R$。

关系的定义域与值域

定义域（Domain）：$\mathrm{dom}R=\{x\mid \exists y(xRy)\}$，即 $R$ 中所有有序对的第一元素构成的集合。

值域（Range）：$\mathrm{ran}R=\{y\mid \exists x(xRy)\}$，即 $R$ 中所有有序对的第二元素构成的集合。

域（Field）：$\mathrm{fld}R=\mathrm{dom}R\cup \mathrm{ran}R$。

特殊关系

• 空关系 $\varnothing$：任何元素之间都不具有的关系。
• 全域关系 $E_A=A\times A$：$A$ 中任意两个元素之间都具有的关系。
• 恒等关系 $I_A=\{(x,x)\mid x\in A\}$：每个元素仅与自身相关的关系。
• 小于等于关系 $L_A=\{(x,y)\mid x,y\in A,x\le y\}$，常用于偏序。
• 整除关系 $D_A=\{(x,y)\mid x,y\in A,x\mid y\}$，用于偏序集。
• 包含关系 $R\subseteq P(A)\times P(A)$：$R=\{(x,y)\mid x\subseteq y\}$。

关系的基数

若 $|A|=m$，$|B|=n$，则从 $A$ 到 $B$ 的不同二元关系共有 $2^{mn}$ 个。特别地，$A$ 上的不同二元关系共有 $2^{n^2}$ 个。

相关运算简述

二元关系的基本运算包括：关系的复合运算（右复合 $R\circ S$、左复合 $S\circ R$）、逆运算 $R^{-1}$、以及集合运算（并、交、补、差）。关系的幂运算具有周期性。

在合成运算的计算中，采用矩阵的布尔乘法：对前关系矩阵的每一行，记录其中为 1 的列位置，然后对于这些列对应的后关系的行，进行逻辑加（布尔或）运算，得到新关系对应行的值。

链接到

• 上一个知识点：2.3 集合计数与基数
• 下一个知识点：2.5 二元关系性质