打开主菜单

二元关系

任何一組有序對; (在甲組上)甲的有序元素對的集合,即甲×甲的子集; (在兩組甲和乙之間)有序對的集合,其中甲中的第一個元素和乙中的第二個元素

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

定义编辑

集合 与集合 上的二元关系是 ,当中 ,称为 ,是笛卡兒積 子集。若 则称  有关系 ,并记作  

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

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

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

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

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

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

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

话虽如此,我们很多時候索性把 定义为 而“有序对 ”亦即是“ ”。

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

 ,則稱  上的關係。

特殊的二元关系编辑

 是一个集合,则

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

关系矩阵编辑

      上的关系,令

 

则0,1矩阵

 

称为 关系矩阵,记作 

关系图编辑

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

运算编辑

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

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

性质编辑

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

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

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

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

闭包编辑

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

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

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

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

  1.  
  2.  
  3.  

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

 

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

参见编辑