跳转到内容

二元关系

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

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

参见