二元关系

关系的表示

关系的性质

偏序关系

等价关系

笛卡尔积

关系的概念

注意

定义

由n个具有给定次序的个体a1，a2，a3，……an组成的序列称为有序n元组，记作（a1，a2，a3，……an）
其中第i个元素ai称为该有序n元组的第i个坐标。当n=2时，有序n元组（a，b）又称为序偶

设（a1，a2，a3，……an）和（b1，b2，b3，……bn）是两个有序n元组，若a1=b1，a2=b2，……an=bn，则称这两个有序n元组相等，并记作（a1，a2，a3，……an）=（b1，b2，b3，……bn）

设A1，A2，……An为任意集合，称集合{(a1，a2，a3……an)|ai∈Ai，i=1，2，……，n}为A1，A2，……An的笛卡尔积，记为A1×A2×……×An

一般情况下A×B≠B×A

笛卡尔积的基数

与笛卡尔积有关的一些恒等式

笛卡尔积不满足交换律和结合律

(B∪C)×A=(B×A)∪(C×A)

A×(B∩C)=(A×B)∩(A×C)

A×(B∪C)=(A×B)∪(A×C)

(B∩C)×A=(B×A)∩(C×A)

当A和B是有限集时，A×B必有限，而且#(A×B)=#A×#B，当其中有一个有限集合时，A×B必为无限集合

推广到一般，对任意有限集合A1，A2，……An，则A1×A2×……×An也是有限集，且#（A1×A2×……×An）=#(A1)×#(A2)×……×#(An)

当A1=A2=……=An=A时，A1×A2×……×An=A^n，称为A的n次幂集

当A=Ø或者B=Ø时，A×B=Ø，即Ø×B=A×Ø=Ø

笛卡尔积A×A，我们常记作A^2

即设A、B、C是任意集合，则A×B≠B×A（除非A=Ø或B=Ø或A=B）
A×B×C≠(A×B)×C≠A×(B×C)

说明

关系的定义域和值域

逆关系

定义

笛卡尔积A1×A2×……×An的任意一个子集称为A1×A2×……An的任意一个子集称为A1×A2×……An上的一个n元关系

当n=2时，A1×A2的任意一个子集，称为由A1到A2的一个二元关系

如无特殊指定，“关系”概指二元关系

元素与“关系”

几种特殊的关系

若(a,b)∈ρ，则称a与b有关系ρ，又记作aρb

若(a,b)∉ρ，则称a与b没有关系ρ，又记作aρ'b

空关系

普通关系

恒等关系

对任意集合A,B,Ø⊆A×B，Ø⊆A×A，所以Ø是由A到B的关系，Ø也是A上的关系，称为空关系

因为A×B⊆A×B，A×A⊆A×A，所以A×B是一个由A到B的关系，A×A是A上的关系，常将A×A记作UA={(ai,aj)|ai,aj∈A}

定义集合A上的恒等关系IA={(a,a)|a∈A}

设ρ是由A到B的一个关系，ρ的定义域记作Dρ，ρ的值域记作Rρ，分别定义为：
Dρ={a|a∈A且存在b∈B，使得aρb}
Rρ={b|b∈B且存在a∈A，使得aρb}
显然有Dρ⊆A，Rρ⊆B

设A、B是任意集合，ρ是由A到B的关系，定义由B到A的关系ρ^-1={(b,a)|(a,b)∈ρ}，称ρ^-1为关系ρ的逆关系

集合表示法

矩阵表示法

关系图表示法

用集合的列举法或描述法来表示关系

关系图由结点和边组成

关系的闭包

关系的运算

关系的交、并、补运算

关系的合成运算

合成关系的方法

关系合成运算的性质

运用关系矩阵的运算求合成运算

利用关系图求合成关系R^n

根据合成关系的定义求合成运算

设R是由集合A到B的关系，则IA·R=R·IB=R

设R1是由A到B的关系，R2是由B到C的关系，R3是由C到D的关系，则有(R1·R2)R3=R1·(R2·R3)

注意

如何利用关系矩阵和关系图来判断关系的性质

集合A上关系的性质

对于所有的a,b∈A，若每当有aρb就必有bρa，则称ρ在A上是对称的

对于所有的a,b∈A,若每当有aρb和bρa就必有a=b，则称ρ在A上是反对称的

若对于所有的a∈A，均有aρ‘a，则称ρ在A上是反自反的

对于所有的a,b,c∈A，若每当有aρb和bρc就必有aρc，则称ρ在A上是可传递的

若对于所有的a∈A，均有aρa，则称ρ在A上是自反的

由关系性质的定义可以得到的若干结论

非对称和反对称是不同的

自反关系与恒等关系是由区别的，恒等关系一定是自反的，但自反关系不一定恒等

空关系既是对称的，也是反对称的

关系矩阵

关系图

若ρ是自反的，则关系矩阵的主对角线上的所有元素均为1

若ρ是反自反的，则关系矩阵的主对角线上所有元素均为0

若ρ是对称的，则关系矩阵关于主对角线对称

若ρ是反对称的，则关系矩阵中，关于主对角对称的元素不同时为1

若ρ是自反的，则关系图中每一结点引出一个指向自身的单边环

若ρ是反自反的，则关系图中每一结点均没有单边环

若ρ是对称的，则在关系图中，若两结点之间存在有边，则必存在两条方向相反的边

若ρ是反对称的，则在关系图中，任意两个不同的结点间至多只有一条边

若ρ是可传递的，则在关系图中，若每当有边由ai指向ak，且又有边由ak指向aj，则必有一条边由ai指向aj

ρ是自反的，当且仅当IA⊆ρ

ρ是反自反的当且仅当ρ∩IA=Ø

ρ是对称的当且仅当ρ=ρ^-1

ρ是反对称的当且仅当ρ∩ρ^-1⊆IA

ρ是传递的当且仅当ρ·ρ⊆ρ

定义

性质

设ρ是集合A上的关系，由下式定义的A上的关系s(ρ)=ρ∪ρ^-1称为ρ的对称闭包

设ρ是集合A上的关系，由下式定义的A上的关系t(ρ)=U∞i=1ρi=ρ∪ρ²∪ρ³∪……称为ρ的传递闭包

设ρ是集合A上的关系，由下式定义的A上的关系r(ρ)=ρ∪IA称为ρ的自反闭包

设ρ是集合A上的关系，则ρ的自反闭包r(ρ)具有以下性质

设ρ是集合A上的关系，则ρ的对称闭包s(ρ)具有如下性质

设ρ是集合A上的关系，则ρ的传递闭包t(ρ)具有如下性质

ρ⊆r(ρ)

r(ρ)是自反的

对于A上任何关系ρr，若ρr自反且ρ⊆ρr，则r(ρ)⊆ρr

ρ⊆s(ρ)

s(ρ)是对称的

对于A上任何关系ρs，若ρs对称且ρ⊆ρs，则s(ρ)⊆ρs

ρ⊆t(ρ)

t(ρ)是可传递的

对于A上任何关系ρt，若ρt可传递且ρ⊆ρt，则t(ρ)⊆ρt

定义

等价类

集合A上的关系ρ，如果它是自反的，对称的，且可传递的，则称ρ是A上的等价关系

定义

全序和良序

集合A上的关系ρ，如果它是自反的，反对称的且可传递的，则称ρ是A上的偏序关系，偏序通常用符号“≤”表示

设≤是集合A上的一个偏序，若对于任意元素a,b∈A，必有a≤b或b≤a，则称≤为A上的一个全序

设≤是集合A上的一个偏序，若∀S⊆A,S≠Ø，∃as∈S，使得∀s∈S，必有as≤s（as称为S的最小元素），则称≤为A上的一个良序

设ρ是集合A上的等价关系，若元素aρb，则称a与b等价，或称b与a等价

定义

性质

设ρ是集合A上地等价关系，则A中等价于元素a的所有元素组成的集合称为a生成的等价类，用[a]ρ表示，即[a]ρ={b|b∈A且aρb}

对任意的a,b∈A，若aρb，则[a]ρ=[b]ρ

对任意a，b∈A，若aρ’b，则[a]ρ∩[b]ρ=Ø

对任意a∈A，[a]ρ≠Ø

等价关系与分划

设ρ是集合A上的一个等价关系，则集合A中所有元素产生的等价类的集合{[a]ρ|a∈A}是A的一个分划

设Π={A1,A2,……An}是集合A的一个分划，则存在A上的一个等价关系ρ，使得Π是A上由ρ导出的等价分划

A、B上关系R的关系图是一个有向图

当且仅当aRb时，用带方向的弧或线段联结a和b

若aRa，则在a处画一条自封闭的弧线

A、B中的每个元素分别用一个顶点表示

注意：关系图中顶点的位置，弧或线段的长度可任意

设A、B都是有限集，A={a1,a2,……an}，B={b1,b2,……bn}，由A到B的关系R可以用一个n×m的矩阵Mr来表示，Mr的第i行第j列的元素rij取值如下：
若aiRbj，则rij=1；若aiR‘bj，则rij=0
矩阵Mr称为R的关系矩阵

设R1是由A到B的关系，R2是由B到C的关系，则R1和R2的合成关系是一个由A到C的关系，用R1·R2表示，定义为：R1·R2={<a,c>|a∈A,c∈C且∃b∈B,使得aR1b，bR2c，有a<R1·R2>c},这种由R1和R2求合成关系R1·R2的运算称为关系的合成运算

设A、B、C均是有限集，R1是一由A到B的关系，R2是一由B到C的关系，它们的关系矩阵分别为MR1和MR2，则合成关系R1·R2的关系矩阵：MR1·R2=MR1·MR2