For faster navigation, this Iframe is preloading the Wikiwand page for 二元关系.

二元关系

维基百科,自由的百科全书

数学上,二元关系(英语:Binary relation,或简称关系)用于讨论两种物件的连系。诸如算术中的“大于”及“等于”、几何学中的“相似”或集合论中的“为……之元素”、“为……之子集”。

定义

实际上是以列举二元有序对的方式去定义二元关系 ,也就是一个集合满足

  • 对所有的 存在 且存在 使

或是以正式的逻辑符号表述为

例一:有四件物件 {} 及四个人 {丙,丁} 。若甲拥有球、乙拥有糖、丙一无所有但丁拥有车,则“拥有”的二元关系可以写为

= {(), (), ()}

其中二元有序对的第一项是被拥有的物件,第二项是拥有者。

例二:实数系 上的“大于关系”可定义为

由于习惯上 通常都是写为 ,更一般来说,不引起混淆的话会把 简写成

集合的关系

集合与集合上的二元关系则定义为 ,当中 ( 请参见笛卡儿积 ) ,称为 。若 则称 有关系 ,并记作

但经常地我们把关系与其图等价起来,即若 是一个关系。

话虽如此,我们很多时候索性把集合间的关系 定义为 而 “有序对 ” 即是 “ ”。

特殊的二元关系

是一个集合,则

  1. 空集称作上的空关系
  2. 称作上的全域关系完全关系
  3. 称作上的恒等关系

关系矩阵

上的关系,令

0,1矩阵

称为关系矩阵,记作

关系图

上的关系,令,其中顶点集合,边集合为,且对于任意的,满足当且仅当。则称图是关系关系图,记作

运算

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

  • 为二元关系,中所有有序对的第一元素构成的集合称为定义域,记作。形式化表示为
  • 为二元关系,中所有有序对的第二元素构成的集合称为值域,记作。形式化表示为
  • 为二元关系,定义域值域的并集称作,记作,形式化表示为
  • 为二元关系,逆关系,简称,记作,其中
  • 为二元关系,合成关系记作,其中
  • 为二元关系,是一个集合。上的限制记作,其中
  • 为二元关系,是一个集合。下的记作,其中
  • 上的二元关系,在右复合的基础上可以定义关系的幂运算

性质

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

  • 自反性:
在集合X上的关系R,如对任意,有,则称R是自反的。
  • 非自反性(自反性的否定的强型式):
在集合X上的关系R,如对任意,有,则称R是非自反的。
  • 对称性:
在集合X上的关系R,如果有必有,则称R是对称的。
  • 反对称性(不是对称性的否定):
  • 非对称性(对称性的否定的强型式):
非对称性是 满足非自反性的反对称性。
  • 传递性:

为集合上的关系,下面给出的五种性质成立的充要条件:

  1. 上自反,当且仅当
  2. 上非自反,当且仅当
  3. 上对称,当且仅当
  4. 上反对称,当且仅当
  5. 上非对称,当且仅当
  6. 上传递,当且仅当

闭包

是非空集合上的关系,的自反(对称或传递)闭包上的关系,满足

  1. 是自反的(对称的或传递的)
  2. 上任何包含的自反(对称或传递)关系

一般将的自反闭包记作,对称闭包记作传递闭包记作

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

对于有限集合上的关系,存在一个正整数,使得

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

参见

{{bottomLinkPreText}} {{bottomLinkText}}
二元关系
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.