二元关系

维库，知识与思想的自由文库

跳转到: 导航, 搜索

1个分类: 数学关系

数学上，二元关系（或简称关系)用於讨论两种物件的连系。诸如算术中的"大於"及"等於"，几何学中的 "相似"，或集合论中的"为...之元素" 或"为...之子集"。

[编辑] 定义

集合 X 与集合 Y 上的二元关系是 R=(X, Y, G(R)) 当中 G(R)，称为R 的图，是笛卡兒積 X × Y的子集。若 (x,y) ∈ G(R) 则称 x 是 R-关系於 y 并记作 xRy 或 R(x,y)。

但经常地我们把关系与其图等价起来，即若 R ⊆ X × Y 则 R 是一个关系。

例子：有四件物件 {球，糖，车，枪} 及四个人 {甲，乙，丙，丁}。若甲拥有球，乙拥有糖，及丁拥有车－即无人有枪及丙一无所有－则二元关系"为...拥有"便是

R=({球，糖，车，枪}, {甲，乙，丙，丁}, {(球,甲), (糖,乙), (车,丁)})。

其中 R 的首项是物件的集合，次项是人的集合，而未项是由有序对（物件，主人）组成的集合。比如有序对（球，甲）以_球R_甲表示，代表球为甲拥有。

不同的关系可以有相同的图。以下的关系

({球，糖，车，枪}, {甲，乙，丁}, {(球,甲), (糖,乙), (车,丁)}

中人人皆是物主，所以与 R 不同，但两者有相同的图。

话虽如此，我们很多時候索性把R 定义为 G(R) 而 "有序对 (x,y) ∈ G(R)" 亦即是 "(x,y) ∈ R"。

二元关系可看作成二元函数，這種二元函数把输入元 x ∈ X 及 y ∈ Y 視為獨立變數並求真偽值（包括「有序对(x, y) 是或非二元关系中的一元。」此一問題）。

若 X=Y，則稱 R為 X上的關係。

[编辑] 特殊的二元关系

设 $A$ 是一个集合，则

空集 $\emptyset$ 称作 $A$ 上的空关系
$E_{A} = A \times A$ 称作 $A$ 上的全域关系
$I_{A} = \{(x, x)|x \in A\}$ 称作 $A$ 上的恒等关系

[编辑] 关系矩阵

设 $X = \{x_1, x_2, \ldots, x_n\}$ 及 $Y = \{y_1, y_2, \ldots, y_m\}$ ， $R$ 是 $X$ $Y$ 上的关系，令

$r_{ij} = \begin{cases} 1 & (x_i, y_j) \in R \\ 0 & (x_i, y_j) \notin R \end{cases}$

则0,1矩阵

$(r_{ij}) = \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1m} \\ r_{21} & r_{22} & \cdots & r_{2m} \\ \vdots & \vdots & \vdots & \vdots \\ r_{n1} & r_{n2} & \cdots & r_{nm} \end{bmatrix}$

称为 $R$ 的关系矩阵，记作 $M R$ 。

[编辑] 关系图

设 $A = \{x_1, x_2, \ldots, x_n\}$ ， $R$ 是 $A$ 上的关系，令图 $G = (V, E)$ ，其中顶点集合 $V = A$ ，边集合为 $E$ ，且对于任意的 $x_i, x_j \in V$ ，满足 $(x_i, x_j) \in E$ 当且仅当 $(x_i, x_j) \in R$ 。则称图 $G$ 是关系 $R$ 的关系图，记作 $G R$ 。

[编辑] 关系的运算

关系的基本运算有以下几种：

设 $R$ 为二元关系， $R$ 中所有有序对的第一元素构成的集合称为 $R$ 的定义域，记作 $dom(R)$ 。形式化表示为

$\mbox{dom}(R) = \{ x | \exists y, ~(x, y) \in R \}$

设 $R$ 为二元关系， $R$ 中所有有序对的第二元素构成的集合称为 $R$ 的值域，记作 $ran(R)$ 。形式化表示为

$\mbox{ran}(R) = \{ y | \exists x, ~(x, y) \in R \}$

设 $R$ 为二元关系， $R$ 的定义域和值域的并集称作 $R$ 的域，记作 $fld(R)$ ，形式化表示为

$\mbox{fld}(R) = \mbox{dom}(R)~\cup~\mbox{ran}(R)$

设 $R$ 为二元关系， $R$ 的逆关系，简称 $R$ 的逆，记作 $R - 1$ ，其中

$R^{-1} = \{ (x, y) | (y, x) \in R \}$

设 $F, G$ 为二元关系， $G$ 與 $F$ 的合成關係记作 $F \circ G$ ，其中

$F \circ G = \{ (x, y) | \exists t,~(x, t) \in F \wedge (t, y) \in G \}$

设 $R$ 为二元关系， $A$ 是一个集合。 $R$ 在 $A$ 上的限制记作 $R \upharpoonright A$ ，其中

$R \upharpoonright A = \{ (x, y) | (x, y) \in R \wedge x \in A\}$

设 $R$ 为二元关系， $A$ 是一个集合。 $A$ 在 $R$ 下的像记作 $R [A]$ ，其中

$R[A] = \mbox{ran}(R \upharpoonright A)$

设 $R$ 为 $A$ 上的二元关系，在右复合的基础上可以定义关系的幂运算：

$R^0 = I_A \$
$R^{n+1} = R^n * R \$

[编辑] 关系的性质

关系的性质主要有以下五种：

自反性： $\forall x \in A,~(x, x) \in R$

在集合 X 上的关系 R，如对任意 $x \in X$ ，有 $(x,x) \in R$ ，则称 R 是自反的。

反自反性(自反性的否定的強型式)： $\forall x \in A,~~(x, x) \notin R$

在集合 X 上的关系 R，如对任意 $x \in X$ ，有 $(x,x) \notin R$ ，则称 R 是反自反的。

对称性： $\forall x, y \in A,~(x, y) \in R \implies (y, x) \in R$

在集合 X 上的关系 R，如果有 $(x,y) \in R$ 且 $x \neq y$ 必有 $(y,x) \in R$ ，则称 R 是对称的。

反对称性(不是對稱性的否定)： $\forall x, y \in A,~((x, y) \in R \wedge (y, x) \in R) \implies x = y$
非對稱性(對稱性的否定的強型式)： $\forall a, b \in A,\ a R b \implies \lnot(b R a)$

非對稱性是滿足反自反性的反對稱性。

传递性： $\forall x, y, z \in A, ~((x, y) \in R \wedge (y, z) \in R) \implies (x, z) \in R$

设 $R$ 为集合 $A$ 上的关系，下面给出 $R$ 的五种性质成立的充要条件：

$R$ 在 $A$ 上自反当且仅当 $I_A \subseteq R$
$R$ 在 $A$ 上反自反当且仅当 $R \cap I_{A} = \emptyset$
$R$ 在 $A$ 上对称当且仅当 $R = R^{-1} \$
$R$ 在 $A$ 上反对称当且仅当 $R \cap R^{-1} \subseteq I_{A}$
$R$ 在 $A$ 上非對稱當且僅當 $R \cap R^{-1} = \emptyset$
$R$ 在 $A$ 上传递当且仅当 $R * R \subseteq R$

[编辑] 关系的闭包

设 $R$ 是非空集合 $A$ 上的关系， $R$ 的自反(对称或传递)闭包是 $A$ 上的关系 $R'$ ，满足

$R'$ 是自反的(对称的或传递的)
$R \subseteq R'$
对 $A$ 上任何包含 $R$ 的自反(对称或传递)关系 $R''$ 有 $R$

一般将 $R$ 的自反闭包记作 $r (R)$ ，对称闭包记作 $s (R)$ ，传递闭包记作 $t (R)$ 。

下列三个定理给出了构造闭包的方法：

$r(R) = R \cup R^0$
$s(R) = R \cup R^{-1}$
$t(R) = R \cup R^2 \cup R^3 \cup \cdots$

对于有限集合 $A$ 上的关系 $R$ ，存在一个正整数 $r$ ，使得

$t(R) = R \cup R^2 \cup \cdots \cup R^r$

求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包，但那样做复杂度比较高；好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度；但最好的方法是利用基于动态规划的Floyd-Warshall算法来求传递闭包。

[编辑] 参见

来自“http://www.wikilib.com/wiki/%E4%BA%8C%E5%85%83%E5%85%B3%E7%B3%BB”

个人工具