二元关系

维基百科,自由的百科全书
跳转至: 导航搜索

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

定义[编辑]

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

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

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

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

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

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

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

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

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

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

X=Y,則稱RX上的關係。

特殊的二元关系[编辑]

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\}RX  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\}RA上的关系,令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 \circ G = \{ (x, y) | \exists t,~(x, t) \in F \wedge (t, y) \in G \}
  • R为二元关系,A是一个集合。RA上的限制记作R \upharpoonright A,其中

R \upharpoonright A = \{ (x, y) | (x, y) \in R \wedge x \in A\}
  • R为二元关系,A是一个集合。AR下的记作R[A],其中

R[A] = \mbox{ran}(R \upharpoonright A)
  • RA上的二元关系,在右复合的基础上可以定义关系的幂运算
R^0 = I_A \
R^{n+1} = R^n \circ 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 Rx \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. RA上自反当且仅当I_A \subseteq R
  2. RA上反自反当且仅当R \cap I_{A} = \emptyset
  3. RA上对称当且仅当R = R^{-1} \
  4. RA上反对称当且仅当R \cap R^{-1} \subseteq I_{A}
  5. RA上非對稱當且僅當R \cap R^{-1} = \emptyset
  6. RA上传递当且仅当R \circ 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算法来求传递闭包。

参见[编辑]