二元关系

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

数学上,二元关系英语: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算法来求传递闭包。

参见[编辑]