二元关系

维基百科，自由的百科全书
跳转至： 导航、 搜索

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

目录

定义 [编辑]

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

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

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

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

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

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

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

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

话虽如此，我们很多時候索性把R定义为G(R)而“有序对 (x,Y) \in G(R) ”亦即是“(x,Y) \in R”。

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

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

特殊的二元关系 [编辑]

设 A 是一个集合，则

  1. 空集 \varnothing 称作 A 上的空关系
  2. E_{A} = A \times A 称作 A 上的全域关系
  3. 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 的定义域，记作 \mbox{dom}(R)。形式化表示为
\mbox{dom}(R) = \{ x | \exists y, ~(x, y) \in R \}
  • 设 R 为二元关系，R 中所有有序对的第二元素构成的集合称为 R 的值域，记作 \mbox{ran}(R)。形式化表示为
\mbox{ran}(R) = \{ y | \exists x, ~(x, y) \in R \}
  • 设 R 为二元关系，R 的定义域和值域的并集称作 R 的域，记作 \mbox{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 的五种性质成立的充要条件：

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

关系的闭包 [编辑]

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

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

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

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

  1. r(R) = R \cup R^0
  2. s(R) = R \cup R^{-1}
  3. 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://zh.wikipedia.org/w/index.php?title=二元关系&oldid=25327341”