定义

集合X{\displaystyle X}与集合Y{\displaystyle Y}上的二元关系是R=(X,Y,G(R)){\displaystyle R=(X,Y,G(R))}，当中G(R){\displaystyle G(R)}，称为R{\displaystyle R}的图，是笛卡儿积X× × -->Y{\displaystyle X\times 子集的子集。若(x,y)∈ ∈ -->G(R){\displaystyle (x,y)\in G(R)}则称x{\displaystyle x}与y{\displaystyle y}有关系R{\displaystyle R}，并记作xRy{\displaystyle xRy}或R(x,y){\displaystyle R(x,y)}。

但经常地我们把关系与其图等价起来，即若R∈ ∈ -->X× × -->Y{\displaystyle R\in X\times Y}则R{\displaystyle R}是一个关系。

例子：有四件物件{球，糖，车，枪}及四个人{甲，乙，丙，丁}。若甲拥有球， 乙拥有糖，及丁拥有车－即无人有枪及丙一无所有－则二元关系为“……拥有……”便是

其中R{\displaystyle R}的首项是物件的集合，次项是人的集合，而末项是由有序对（物件，主人） 组成的集合。比如有序对（球，甲）以球R{\displaystyle R}甲表示， 代表球为甲拥有。

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

中人人皆是物主，所以与R{\displaystyle R}不同，但两者有相同的图。

话虽如此，我们很多时候索性把R{\displaystyle R}定义为G(R){\displaystyle G(R)}而“有序对(x,Y)∈ ∈ -->G(R){\displaystyle (x,Y)\in G(R)}”亦即是“(x,Y)∈ ∈ -->R{\displaystyle (x,Y)\in R}”。

二元关系可看作成二元函数，这种二元函数把输入元x∈ ∈ -->X{\displaystyle x\in X}及Y∈ ∈ -->Y{\displaystyle Y\in Y}视为独立变数并求真伪值（包括“有序对(x,Y){\displaystyle (x,Y)}是或非二元关系中的一元”此一问题）。

若X=Y{\displaystyle X=Y}，则称R{\displaystyle R}为X{\displaystyle X}上的关系。

特殊的二元关系

设A{\displaystyle A}是一个集合，则

空集∅ ∅ -->{\displaystyle \varnothing }称作A{\displaystyle A}上的空关系

EA=A× × -->A{\displaystyle E_{A}=A\times A}称作A{\displaystyle A}上的全域关系（完全关系）

IA={(x,x)|x∈ ∈ -->A}{\displaystyle I_{A}=\{(x,x)|x\in A\}}称作A{\displaystyle A}上的恒等关系

关系矩阵

设X={x1,x2,… … -->,xn}{\displaystyle X=\{x_{1},x_{2},\ldots ,x_{n}\}}及Y={y1,y2,… … -->,ym}{\displaystyle Y=\{y_{1},y_{2},\ldots ,y_{m}\}}，R{\displaystyle R}是X{\displaystyle X}Y{\displaystyle Y}上的关系，令

则0,1矩阵

称为R{\displaystyle R}的关系矩阵，记作MR{\displaystyle M_{R}}。

关系图

设A={x1,x2,… … -->,xn}{\displaystyle A=\{x_{1},x_{2},\ldots ,x_{n}\}}，R{\displaystyle R}是A{\displaystyle A}上的关系，令图G=(V,E){\displaystyle G=(V,E)}，其中顶点集合V=A{\displaystyle V=A}，边集合为E{\displaystyle E}，且对于任意的xi,xj∈ ∈ -->V{\displaystyle x_{i},x_{j}\in V}，满足(xi,xj)∈ ∈ -->E{\displaystyle (x_{i},x_{j})\in E}当且仅当(xi,xj)∈ ∈ -->R{\displaystyle (x_{i},x_{j})\in R}。则称图G{\displaystyle G}是关系R{\displaystyle R}的关系图，记作GR{\displaystyle G_{R}}。

运算

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

设R{\displaystyle R}为二元关系，R{\displaystyle R}中所有有序对的第一元素构成的集合称为R{\displaystyle R}的定义域，记作dom(R){\displaystyle {\mbox{dom}}(R)}。形式化表示为

设R{\displaystyle R}为二元关系，R{\displaystyle R}中所有有序对的第二元素构成的集合称为R{\displaystyle R}的值域，记作ran(R){\displaystyle {\mbox{ran}}(R)}。形式化表示为

设R{\displaystyle R}为二元关系，R{\displaystyle R}的定义域和值域的并集称作R{\displaystyle R}的域，记作fld(R){\displaystyle {\mbox{fld}}(R)}，形式化表示为

设R{\displaystyle R}为二元关系，R{\displaystyle R}的逆关系，简称R{\displaystyle R}的逆，记作R− − -->1{\displaystyle R^{-1}}，其中

设F,G{\displaystyle F,G}为二元关系，G{\displaystyle G}与F{\displaystyle F}的合成关系记作F∘ ∘ -->G{\displaystyle F\circ G}，其中

设R{\displaystyle R}为二元关系，A{\displaystyle A}是一个集合。R{\displaystyle R}在A{\displaystyle A}上的限制记作R↾ ↾ -->A{\displaystyle R\upharpoonright A}，其中

设R{\displaystyle R}为二元关系，A{\displaystyle A}是一个集合。A{\displaystyle A}在R{\displaystyle R}下的像记作R[A]{\displaystyle R[A]}，其中

设R{\displaystyle R}为A{\displaystyle A}上的二元关系，在右复合的基础上可以定义关系的幂运算：

性质

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

自反性：∀ ∀ -->x∈ ∈ -->A, (x,x)∈ ∈ -->R{\displaystyle \forall x\in A,~(x,x)\in R}

反自反性（自反性的否定的强型式）：∀ ∀ -->x∈ ∈ -->A,  (x,x)∉ ∉ -->R{\displaystyle \forall x\in A,~~(x,x)\notin R}

对称性：∀ ∀ -->x,y∈ ∈ -->A, (x,y)∈ ∈ -->R⟹ ⟹ -->(y,x)∈ ∈ -->R{\displaystyle \forall x,y\in A,~(x,y)\in R\implies (y,x)\in R}

反对称性（不是对称性的否定）：∀ ∀ -->x,y∈ ∈ -->A, ((x,y)∈ ∈ -->R∧ ∧ -->(y,x)∈ ∈ -->R)⟹ ⟹ -->x=y{\displaystyle \forall x,y\in A,~((x,y)\in R\wedge (y,x)\in R)\implies x=y}

非对称性（对称性的否定的强型式）：∀ ∀ -->a,b∈ ∈ -->A, aRb⟹ ⟹ -->¬ ¬ -->(bRa){\displaystyle \forall a,b\in A,\ aRb\implies \lnot (bRa)}

传递性：∀ ∀ -->x,y,z∈ ∈ -->A, ((x,y)∈ ∈ -->R∧ ∧ -->(y,z)∈ ∈ -->R)⟹ ⟹ -->(x,z)∈ ∈ -->R{\displaystyle \forall x,y,z\in A,~((x,y)\in R\wedge (y,z)\in R)\implies (x,z)\in R}

设R{\displaystyle R}为集合A{\displaystyle A}上的关系，下面给出R{\displaystyle R}的五种性质成立的充要条件：

R{\displaystyle R}在A{\displaystyle A}上自反当且仅当IA⊆ ⊆ -->R{\displaystyle I_{A}\subseteq R}

R{\displaystyle R}在A{\displaystyle A}上反自反当且仅当R∩ ∩ -->IA=∅ ∅ -->{\displaystyle R\cap I_{A}=\emptyset }

R{\displaystyle R}在A{\displaystyle A}上对称当且仅当R=R− − -->1 {\displaystyle R=R^{-1}\ }

R{\displaystyle R}在A{\displaystyle A}上反对称当且仅当R∩ ∩ -->R− − -->1⊆ ⊆ -->IA{\displaystyle R\cap R^{-1}\subseteq I_{A}}

R{\displaystyle R}在A{\displaystyle A}上非对称当且仅当R∩ ∩ -->R− − -->1=∅ ∅ -->{\displaystyle R\cap R^{-1}=\emptyset }

R{\displaystyle R}在A{\displaystyle A}上传递当且仅当R∘ ∘ -->R⊆ ⊆ -->R{\displaystyle R\circ R\subseteq R}

闭包

设R{\displaystyle R}是非空集合A{\displaystyle A}上的关系，R{\displaystyle R}的自反（对称或传递）闭包是A{\displaystyle A}上的关系R′{\displaystyle R"}，满足

R′{\displaystyle R"}是自反的（对称的或传递的）

R⊆ ⊆ -->R′{\displaystyle R\subseteq R"}

对A{\displaystyle A}上任何包含R{\displaystyle R}的自反（对称或传递）关系R″{\displaystyle R""}有R′⊆ ⊆ -->R″{\displaystyle R"\subseteq R""}

一般将R{\displaystyle R}的自反闭包记作r(R){\displaystyle r(R)}，对称闭包记作s(R){\displaystyle s(R)}，传递闭包记作t(R){\displaystyle t(R)}。

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

r(R)=R∪ ∪ -->R0{\displaystyle r(R)=R\cup R^{0}}

s(R)=R∪ ∪ -->R− − -->1{\displaystyle s(R)=R\cup R^{-1}}

t(R)=R∪ ∪ -->R2∪ ∪ -->R3∪ ∪ -->⋯ ⋯ -->{\displaystyle t(R)=R\cup R^{2}\cup R^{3}\cup \cdots }

对于有限集合A{\displaystyle A}上的关系R{\displaystyle R}，存在一个正整数r{\displaystyle r}，使得

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

参见

有序对

二元集合

笛卡儿积

偏序关系

等价关系

相容关系

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。