数学上,二元关系(英語:Binary relation,或简称关系)用於讨论两种物件的连系。诸如算术中的「大於」及「等於」、几何学中的「相似」或集合论中的「为……之元素」、「为……之子集」。
定义
设为集合,的任何子集称作到的二元关系,特别是当时,称作上的二元关系,一般记作。若, 是从到的二元关系;若,那么是上的二元关系
或是以正式的邏輯符號表述為
例一:有四件物件 {球,糖,车,枪} 及四个人 {甲,乙,丙,丁} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有车,则「擁有」的二元关系可以寫為
- = {(球,甲), (糖,乙), (车,丁)}
其中二元有序对的第一项是被擁有的物件,第二项是擁有者。
例二:實數系 上的「大於關係」可定義為
由於習慣上 通常都是寫為 ,更一般來說,不引起混淆的話會把 簡寫成 。
集合的關係
集合与集合上的二元关系則定義為 ,当中 ( 請參見笛卡儿积 ) ,称为 的图。若 则称 与 有关系 ,并记作 或 。
但经常地我们把关系与其图等价起来,即若 则 是一个关系。
话虽如此,我们很多時候索性把集合間的關係 定义为 而 “有序对 ” 即是 “ ”。
特殊的二元关系
设是一个集合,则
- 空集称作上的空关系
- 称作上的全域关系(完全關係)
- 称作上的恒等关系
关系矩阵
设及,是 和上的关系,令
则0,1矩阵
称为的关系矩阵,记作。
关系图
设,是上的关系,令图,其中顶点集合,边集合为,且对于任意的,满足当且仅当。则称图是关系的关系图,记作。
运算
关系的基本运算有以下几种:
- 设为二元关系,中所有有序对的第一元素构成的集合称为的定义域,记作。形式化表示为
- 设为二元关系,中所有有序对的第二元素构成的集合称为的值域,记作。形式化表示为
- 设为二元关系,的定义域和值域的并集称作的域,记作,形式化表示为
- 设为二元关系,的逆关系,简称的逆,记作,其中
- 设为二元关系,與的合成關係记作,其中
- 设为二元关系,是一个集合。在上的限制记作,其中
- 设为二元关系,是一个集合。在下的像记作,其中
- 设为上的二元关系,在右复合的基础上可以定义关系的幂运算:
-
性质
关系的性质主要有以下五种:
- 自反性:
- 在集合X上的关系R,如对任意,有,则称R是自反的。
- 非自反性(自反性的否定的強型式):
- 在集合X上的关系R,如对任意,有,则称R是非自反的。
- 对称性:
- 在集合X上的关系R,如果有且必有,则称R是对称的。
- 反对称性(不是對稱性的否定):
- 非對稱性(對稱性的否定的強型式):
- 非對稱性是 滿足非自反性的反對稱性。
- 传递性:
设为集合上的关系,下面给出的五种性质成立的充要条件:
- 在上自反,当且仅当
- 在上非自反,当且仅当
- 在上对称,当且仅当
- 在上反对称,当且仅当
- 在上非對稱,当且仅当
- 在上传递,当且仅当
闭包
设是非空集合上的关系,的自反(对称或传递)闭包是上的关系,满足
- 是自反的(对称的或传递的)
- 对上任何包含的自反(对称或传递)关系有
一般将的自反闭包记作,对称闭包记作,传递闭包记作。
下列三个定理给出了构造闭包的方法:
对于有限集合上的关系,存在一个正整数,使得
求传递闭包是图论中一个非常重要的问题,例如给定了一个城市的交通地图,可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包,但那样做复杂度比较高;好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度;但最好的方法是利用基于动态规划的Floyd-Warshall算法来求传递闭包。
参见
|