数学上,二元关系(英語:Binary relation,或简称关系)用於讨论两种物件的连系。诸如算术中的「大於」及「等於」、几何学中的「相似」或集合论中的「为……之元素」、「为……之子集」。
设
为集合,
的任何子集称作
到
的二元关系,特别是当
时,称作
上的二元关系,一般记作
。若
,
是从
到
的二元关系;若
,那么
是
上的二元关系
或是以正式的邏輯符號表述為
![{\displaystyle (\forall r\in R)(\exists x)(\exists y)[\,r=(x,\,y)\,]}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy84N2EzNmI3OTE4ZDc3YzNiNTRlNDBmYWVhZDk4Zjc3NDk4YTU1ZDU2&__proxy_form=0)
例一:有四件物件 {球,糖,车,枪} 及四个人 {甲,乙,丙,丁} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有车,则「擁有」的二元关系可以寫為
= {(球,甲), (糖,乙), (车,丁)}
其中二元有序对的第一项是被擁有的物件,第二项是擁有者。
例二:實數系
上的「大於關係」可定義為
![{\displaystyle >\,:=\{\,(a,\,b)\in {\mathbb {R} }^{2}\,|\,(\exists r\in \mathbb {R} )[\,(a=b+r)\wedge (r\neq 0)\,]\}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy83YzFkMzU3MDQ0NWQwZDg2YjJjY2FjNWMyNjk5ZjFjOGY5YjA4MWZm&__proxy_form=0)
由於習慣上
通常都是寫為
,更一般來說,不引起混淆的話會把
簡寫成
。
集合
与集合
上的二元关系則定義為
,当中
( 請參見笛卡儿积 ) ,称为
的图。若
则称
与
有关系
,并记作
或
。
但经常地我们把关系与其图等价起来,即若
则
是一个关系。
话虽如此,我们很多時候索性把集合間的關係
定义为
而 “有序对
” 即是 “
”。
设
是一个集合,则
- 空集
称作
上的空关系
称作
上的全域关系(完全關係)
称作
上的恒等关系
设
及
,
是
和
上的关系,令
![{\displaystyle r_{ij}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\notin R\end{cases}}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hZGIxOTFkZjQyMTA4YTJkOGQ2MjU2ZjcyMDJiZmY4ZWM3MzkwNmE0&__proxy_form=0)
则0,1矩阵
![{\displaystyle (r_{ij})={\begin{bmatrix}r_{11}&r_{12}&\cdots &r_{1m}\\r_{21}&r_{22}&\cdots &r_{2m}\\\vdots &\vdots &\vdots &\vdots \\r_{n1}&r_{n2}&\cdots &r_{nm}\end{bmatrix}}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8yNjc0MTQzNWU1YjU0YzYyNTk4ZjlkNzhiYmIxNTk5MmU1MzI1YzBi&__proxy_form=0)
称为
的关系矩阵,记作
。
设
,
是
上的关系,令图
,其中顶点集合
,边集合为
,且对于任意的
,满足
当且仅当
。则称图
是关系
的关系图,记作
。
关系的基本运算有以下几种:
- 设
为二元关系,
中所有有序对的第一元素构成的集合称为
的定义域,记作
。形式化表示为
![{\displaystyle {\mbox{dom}}(R)=\{\,x\,|\,(\exists y)[\,(x,y)\in R\,]\,\}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9jZTFmOWZhNDAyOWE2MzhhNjQzYjhhYzQzNzQ4Yzc2M2MwOTM2NjM0&__proxy_form=0)
- 设
为二元关系,
中所有有序对的第二元素构成的集合称为
的值域,记作
。形式化表示为
![{\displaystyle {\mbox{ran}}(R)=\{\,y\,|\,(\exists x)[\,(x,y)\in R\,]\,\}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zZWI5YTk3MjE4ZTU4ZWU0MDMxZjgwMWMxZTIyOThlYzVjN2ViODgx&__proxy_form=0)
- 设
为二元关系,
的定义域和值域的并集称作
的域,记作
,形式化表示为
![{\displaystyle {\mbox{fld}}(R)={\mbox{dom}}(R)\cup {\mbox{ran}}(R)}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lMGQ4NDFiMWQ4ZmJlMjkyMjI4YjhiZjAyMjY3ZTM0MTc4NzNhZDdl&__proxy_form=0)
- 设
为二元关系,
的逆关系,简称
的逆,记作
,其中
![{\displaystyle R^{-1}=\{\,p\,|\,(\exists x)(\exists y)[\,(x,y)\in R\wedge p=(y,x)\,]\,\}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lYWEyMzI4YzM3NGE4NDg3OGI1ZmZhNDZhMDYxMDg0MzY5OTEzM2Yw&__proxy_form=0)
- 设
为二元关系,
與
的合成關係记作
,其中
![{\displaystyle F\circ G=\{(x,y)|\exists t,~(x,t)\in F\wedge (t,y)\in G\}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lNTdjZGI2MjkwZDBkMjhkMzljNTEzY2I2ZjgwZGEyYTYyMDZmNGNk&__proxy_form=0)
- 设
为二元关系,
是一个集合。
在
上的限制记作
,其中
![{\displaystyle R\upharpoonright A=\{(x,y)|(x,y)\in R\wedge x\in A\}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8xOTM5ZGJlMDRiY2E2ZmVhMDY1MDQ1YTFiNGYzMTdmNWJlODY4MDU0&__proxy_form=0)
- 设
为二元关系,
是一个集合。
在
下的像记作
,其中
![{\displaystyle R[A]={\mbox{ran}}(R\upharpoonright A)}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy84YTA0ZmQ2NWIxNTRhNmEyY2NlZTA3ODIzYTUwOGExN2NhNDNiOTJi&__proxy_form=0)
- 设
为
上的二元关系,在右复合的基础上可以定义关系的幂运算:
![{\displaystyle R^{n+1}=R^{n}\circ R\ }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zNjQ5M2U3MzFmODk3OTU1MGIxMWM2MTEwOTU3OWVjNTM0NzI4MWNi&__proxy_form=0)
关系的性质主要有以下五种:
- 自反性:
![{\displaystyle \forall x\in A,~(x,x)\in R}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy84MTdhZTVkMjg4ODFjMzhiMWFkZjA0ZDA5MmUwZWI0MzYwM2IyOTUy&__proxy_form=0)
- 在集合X上的关系R,如对任意
,有
,则称R是自反的。
- 非自反性(自反性的否定的強型式):
![{\displaystyle \forall x\in A,~~(x,x)\notin R}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82NmZkYzg1NWJmYzdiYTEwMzdiZTRjMzdiNjE1NzA2NDBiMTM3MTNi&__proxy_form=0)
- 在集合X上的关系R,如对任意
,有
,则称R是非自反的。
- 对称性:
![{\displaystyle \forall x,y\in A,~(x,y)\in R\implies (y,x)\in R}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9jZDgyMWE3ODI2NmM1NzUwYjhlNmQyNmU4YzY0YTczNWYwMTRhN2Qw&__proxy_form=0)
- 在集合X上的关系R,如果有
且
必有
,则称R是对称的。
- 反对称性(不是對稱性的否定):
![{\displaystyle \forall x,y\in A,~((x,y)\in R\wedge (y,x)\in R)\implies x=y}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lM2U1ZjhlYzYwNGQ3ZGY0YWQ3NzQ0NzE3Mjc2MzBiMjY4OGQ3NTUz&__proxy_form=0)
- 非對稱性(對稱性的否定的強型式):
![{\displaystyle \forall x,y\in A,~(x,y)\in R\implies (y,x)\notin R}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy83YTI3MWE2YjA3YTdjODc4ZDhkOWZkZmRjNWNhZTE3MTc2YTY0YWIy&__proxy_form=0)
- 非對稱性是 滿足非自反性的反對稱性。
- 传递性:
![{\displaystyle \forall x,y,z\in A,~((x,y)\in R\wedge (y,z)\in R)\implies (x,z)\in R}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zMThiNjJhOTMyMWMwODU5OWQ0OWIyYTU5YWYwZGYwYjhmYmU2ZDE3&__proxy_form=0)
设
为集合
上的关系,下面给出
的五种性质成立的充要条件:
在
上自反,当且仅当![{\displaystyle I_{A}\subseteq R}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iZjIwMGU2Njg0MTJhMmZhMjZiZDNmOGRjOTkwNTk2YWU5Nzg1NThk&__proxy_form=0)
在
上非自反,当且仅当![{\displaystyle R\cap I_{A}=\emptyset }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8xODBkZTEwNGMzNzFjMTEyZWE0YTg1OWY0YTk4ZDY0YmM0NDQ1YjZh&__proxy_form=0)
在
上对称,当且仅当![{\displaystyle R=R^{-1}\ }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9kYTIwYjgzMGI2NjE4MDdhNzc3ZDAxZjk3M2NmN2U0NTUwYjViNTM5&__proxy_form=0)
在
上反对称,当且仅当![{\displaystyle R\cap R^{-1}\subseteq I_{A}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hOTAyYmNhZGJjNjlkZDUyZDQ5MDFiYzYwZTdiMGYwMmQ5Mjg0ZmFj&__proxy_form=0)
在
上非對稱,当且仅当![{\displaystyle R\cap R^{-1}=\emptyset }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zMWE2NTAxMGIyYjM4Mzk5ODhmN2NmOWE0NTI4OTllMzI1MGUxNjQx&__proxy_form=0)
在
上传递,当且仅当![{\displaystyle R\circ R\subseteq R}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iZWM4NzQ5MjZmODRjMzM2YjZiZDBjMmFlN2ZjOGRlMzVhNGFiZTE3&__proxy_form=0)
设
是非空集合
上的关系,
的自反(对称或传递)闭包是
上的关系
,满足
是自反的(对称的或传递的)
![{\displaystyle R\subseteq R'}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iMzU5MWFmOTliMTQ4YjA0ZDU4MTJhYjRjZGE4M2ZiNWFkNmU4NzM5&__proxy_form=0)
- 对
上任何包含
的自反(对称或传递)关系
有![{\displaystyle R'\subseteq R''}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lZjZkMjcwYmZkMmE3NWFhOWMwZTU1MTBhY2IwYmUyNDhjOWM1YTg3&__proxy_form=0)
一般将
的自反闭包记作
,对称闭包记作
,传递闭包记作
。
下列三个定理给出了构造闭包的方法:
![{\displaystyle r(R)=R\cup R^{0}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lNDlhNWQ1YjI2NTg2MTllNjdmODdhMTQyN2JlMTFjZTAwNGI1ZDJl&__proxy_form=0)
![{\displaystyle s(R)=R\cup R^{-1}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy81YTY5OThmMWE3MjNlNzE2ZjEwY2JlN2QzYzQ1YTM1NmI3Yjc1NjY5&__proxy_form=0)
![{\displaystyle t(R)=R\cup R^{2}\cup R^{3}\cup \cdots }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8wOTJlZjVmMWFiNGVhNWY5M2UwNjZjNDZhNDg3YzE5OTg2YjM1ZTg2&__proxy_form=0)
对于有限集合
上的关系
,存在一个正整数
,使得
![{\displaystyle t(R)=R\cup R^{2}\cup \cdots \cup R^{r}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zYTlhNjdjZjcwYzM4YjU3MDQxNWFmMGNmYzkwNDMyMDk4ZGNlNjZm&__proxy_form=0)
求传递闭包是图论中一个非常重要的问题,例如给定了一个城市的交通地图,可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包,但那样做复杂度比较高;好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度;但最好的方法是利用基于动态规划的Floyd-Warshall算法来求传递闭包。