第 4章 关系
4.1 集合的笛卡儿积
4.2 二元关系的概念及其特性
4.3 二元关系的运算
4.4 关系的闭包运算
4.5 等价关系与集合的划分
4.6 偏序关系第 4章 关系关系是离散数学中刻画元素之间相互联系的一个重要的概念，在计算机科学与技术领域中有着广泛的应用，关系数据库模型就是以关系及其运算作为理论基础的,
在诸多的关系中，最基本的涉及两个事物之间的关系，即二元关系,本章主要讨论二元关系，先给出二元关系的定义和特性，
然后讨论关系的运算及关系的闭包运算，
最后给出最重要的二元关系 —— 等价关系和偏序关系,
4.1 集合的笛卡儿积
4.1.1 有序对的概念
4.1.2 笛卡儿积
4.1.1 有序对的概念给定一个集合，其成员之间往往存在某种关系,例如，
某一家庭集合,{父，母，儿，媳，孙 }这种成员的关系可以有多种，夫妻、上下辈份等,对于不同的两个集合，其成员之间也可能存在某种关系,例如,这个家庭集合中的成员与另一个家庭集合中的某成员是兄弟关系，两家的儿媳妇为姊妹关系等,
总之，可以将事物之间的结构联系抽象概括为集合中元素之间的关系,例如,A={a,b,c,d}表示男教师,B={x,y,z}表示女教师集合,如果 A,B的元素之间有夫妻关系，是 a和 y，
c和 z，那么
（ 1） a和 y是成对出现,c和 z是成对出现,
（ 2）根据谓词概念，这对元素具有一定顺序,
（ 3）应该给出特定的表示方法表达这种关系,
4.1.1 有序对的概念定义 4.1-1 由两个元素，比如 x和 y，按照一定顺序构成的序列称为有序对，也称序偶或二元组，记作〈 x,y〉
（也可记作（ x,y）），其中 x是它的第一元素,y是它的第二元素,且 x,y,可以相同,
例如，坐标系中点的坐标（ 3,4），（ -1,2）就是有序对,
一般说来有序对具有以下特点：
（ 1） 当 x≠y时，〈 x,y〉 ≠〈 y,x〉,即在一个有序对中，
如果两个元素不相等，那么它们是不能交换次序的,例如，
〈 0,1〉与〈 1,0〉代表不同的有序对,
（ 2） 两个有序对相等，即〈 x,y〉 =〈 u,v〉的充分必要条件是 x=u且 y=v.
4.1.1 有序对的概念定义 4.1-2 一个有序 n元组 (n≥3)是一个有序对，其中第一个元素是一个有序 n-1元组,一个有序 n元组记作
〈 x1,x2,…,x n〉，即
〈 x1,x2,…,x n〉 =〈〈 x1,…,x n-1〉,xn〉,
有序 3元组〈 x,y,z〉可以表示为〈〈 x,y〉,z〉，同样具有特点〈〈 x,y〉,z〉 =〈〈 u,v〉,w〉的充分必要条件是
〈 x,y〉 =〈 u,v〉,z=w，即 x=u,y=v,z=w.例如，空间直角坐标系中点的坐标〈 1,-1,3〉,〈 2,4.5,0〉等都是有序 3
元组,n维空间中点的坐标或 n维向量都是有序 n元组,
形式上也可以把〈 x〉看成有序 1元组，只不过这里的顺序性没有什么实际意义,以后提到有序 n元组，其中的 n
可以看成任何的正整数,
4.1.2 笛卡儿积定义 4.1-3 设 A,B为两个集合，称由
A中元素为第一个元素,B中元素为第二个元素的所有有序对组成的集合为 A与 B的笛卡儿积，记作 A× B.符号化表示为
A× B={〈 x,y〉 |x∈ A∧ y∈ B}.
4.1.2 笛卡儿积有穷集合的笛卡儿积运算满足下述性质：
（ 1）若 A,B中有一个是空集，则它们的笛卡儿积是空集，即
A× B=A× B=φ,
（ 2）当 A≠B且 A,B都不是空集时，有 A× B≠B× A.
（ 3）当 A,B,C都不是空集时，有
(A× B)× C={〈〈 a,b〉,c〉 |(〈 a,b〉 ∈ A× B)∧ (c∈ C)}，
A× (B× C)={〈 a,〈 b,c〉〉 |(a∈ A)∧ (〈 b,c〉 ∈ B× C)}，
由于〈 a,〈 b,c〉〉不是有序 3元组,(A× B)× C ≠
A× (B× C).
如果 A,B,C中有一个是空集，那么上面式子的左右两边都是空集,这条性质说明笛卡儿积运算不适合结合律,
4.1.2 笛卡儿积
（ 4）笛卡儿积运算对并和交运算满足分配律，即
A× (B∪ C)=(A× B)∪ (A× C)，
(B∪ C)× A=(B× A)∪ (C× A)，
A× (B∩C)=(A× B)∩(A× C)，
(B∩C)× A=(B× A)∩(C× A).
4.1.2 笛卡儿积定义 4.1-4 设 A1,A2,…,A n为 n个集合 (n≥2)，称集合
A1× A2× … × An={〈 x1,x2,…,x n〉 |xi∈ Ai,i=1,2,…,n}
为 n阶笛卡儿积,当 A1=A2=…=A n=A时，记 A生成的 n阶笛卡儿积为 An.
设 A1,A2,…,A n均为有限集合，并设 |Ai|=ni,i=1,2,…,n,
则 |A1× A2× … × An|=n1× n2× … × nn.
n维笛卡儿积的性质与二维笛卡儿积的性质类似，这里不再赘述,
4.2 二元关系的概念及其特性
4.2.1 二元关系的概念
4.2.2 关系的表示法
4.2.3 关系的性质
4.2.1 二元关系的概念客观事物之间的关系种类是相当繁多的,我们只能研究其抽象定义,对于具体关系只是抽象定义下的一个指派，
显然这种指派仅是笛卡儿积的一个子集,
定义 4.2-1 若集合 R中的全体元素均为有序的 n(n≥2)
元组，则称 R为 n元关系，特别地，当 n=2时，称 R为二元关系，简称为关系,
对于二元关系 R,若〈 x,y〉 ∈ R，则记为 xRy，若
〈 x,y〉? R,则记为 xRy.规定空集 φ为 n元空关系，当然也是二元空关系，简称空关系,
4.2.1 二元关系的概念定义 4.2-2 设 A,B为两个集合,A× B得任何子集 R均称为从 A到 B的二元关系，特别地，称 A× A得子集 R为 A上的二元关系,
设 A={a1,a2},B={b},A× B得子集 φ,
{〈 a1,b〉 },{〈 a2,b〉 },{〈 a1,b〉,〈 a2,b〉 },为 A到 B的全部二元关系,φ,{〈 b,a1〉 },{〈 b,a2〉 },{〈 b,a1〉,〈 b,a2〉 }为 B到
A的全部二元关系,而 B上的二元关系有两个,φ,{b,b},A上的二元关系共有 16个二元关系，这里不一一列举,
4.2.1 二元关系的概念定义 4.2-3 对任何集合 A，称 EA={〈 x,y〉 |x∈ A∧ y∈ A}=A× A为 A
上的全域关系,称 IA={〈 x,x〉 |x∈ A}为 A上的恒等关系,
若 A是实数集或其子集，还可以定义下面的各种关系：
称 DA={〈 x,y〉 |x∈ A∧ y∈ A∧ x|y}为 A上的整除关系，其中 x|y为 x
整除 y.
称 LA={〈 x,y〉 |x∈ A∧ y∈ A∧ x≤y}为 A上的小于等于关系,
4.2.2 关系的表示法前面给出的关系都是用集合表达式来定义的,对于有穷集合 A上的关系 R，还可以用关系矩阵和关系图来给出,下面给出关系矩阵和关系图的一般定义,
定义 4.2-4 设 A={x1,x2,…,x n},R是 A上的关系，令
1,若 xiRxj
rij=,(i,j=1,2,…,n)
0,若 xiRxj
r11 r12 … r1n
则 (rij)= r21 r22 … r 2n
… … … …
rn1 rn2 … r nn
是 R的关系矩阵,并记作 MR.
4.2.2 关系的表示法定义 4.2-5 设 A={x1,x2,…,x n},R A× A是 A上的关系，
以 A的元素为结点，若〈 xi,xj〉 ∈ R，则从结点 xi向 xj引一条有向边，这样得到的有向图称为 R的关系图 GR.
例如，设 A={1,2,3,4}，则 R={〈 1,1〉,〈 1,2〉,〈 2,3〉,
〈 2,4〉,〈 4,2〉 }是 A上的关系,R的关系矩阵和关系图表示为
1 1 0 0
0 0 1 1
0 0 0 0
0 1 0 0
4.2.3 关系的性质本小节涉及的主要内容是某个集合 A上的关系的性质，
有必要说明，本节内讨论的是非空集合上的二元关系的性质,
定义 4.2-6 设 R是集合 A上的二元关系，如果对于每一个 x∈ A均有 xRx，则称二元关系 R是自反的,即
R在 A (? x)(x∈ A→ 〈 x,x〉 ∈ R).
4.2.3 关系的性质定义 4.2-7 设 R是集合 A上的二元关系，如果对于每一个 x∈ A，均有〈 x,x〉? R，则称二元关系 R是反自反的,即
R在 A (? x)(x∈ A→ 〈 x,x〉? R).
例如,A={1,2,3},R={〈 2,1〉,〈 2,3〉,〈 3,2〉 }，显然 x可以取 1,2,3，〈 x,x〉? R，按定义,R是反自反的,
4.2.3 关系的性质定义 4.2-8 设 R是定义在集合 A上的一个二元关系，如果对于每一个 x,y∈ A，每当 xRy,则有 yRx，则称二元关系 R为 A上的对称关系,即
R在 A (? x)(? y)(x∈ A∧ y∈ A∧ xRy→ yRx).
定义 4.2-9 设 R是定义在集合 A上的一个二元关系,
如果对于每一个 x,y∈ A，每当 xRy且 yRx，则必有 x=y，称
R为 A上的反对称关系,即
R在 A
(? x)(? y)(x∈ A∧ y∈ A∧ xRy∧ yRx→x=y)
4.2.3 关系的性质定义 4.2-10 设 R是定义在集合 A上的二元关系：如果对于任意 x,y,z∈ A.每当 xRy且 yRz时，就有 xRz，则称 R是
A上的传递关系,即
(? x)(? y)(? z)(x∈ A∧ y∈ A∧ z∈ A∧ xRy∧ yRz→ xRz)
关于定义中的条件理解，要特别注意每当有 xRy,yRz
时，就有 xRz.换句话说，若没有 xRy,yRz,就不必去考虑
xRz.若存在一个 xRy,yRz,而没有 xRz就不是传递的,
4.3 二元关系的运算
4.3.1 定义域与值域
4.3.2 关系的基本运算
4.3.3 关系的幂运算
4.3.1 定义域与值域定义 4.3-1 设 R为二元关系,R的定义域、值域和域分别记作 domR,ranR,fldR，其中
domR={x|? y(〈 x,y〉 ∈ R)}，
ranR={y|? x(〈 x,y〉 ∈ R)}，
fldR=domR∪ ranR.
由定义不难看出，定义域 domR是 R中所有有序对的第一元素构成的集合，值域 ranR是 R中所有有序对的第二元素构成的集合，域 fldR是 R中有序对涉及的全体元素的集合,
4.3.2 关系的基本运算定义 4.3-2 设 R为二元关系,R的逆记作 R,其中
R ={〈 y,x〉 |〈 x,y〉 ∈ R}.
不难看出,R 就是把 R的每个有序对的两个元素交换以后得到的关系,如果 R是整数集 Z上的小于关系，那么 R
就是 Z上的大于关系,类似地，整除关系的逆就是倍数关系,
定义 4.3-3 设 R,S为二元关系,R与 S的合成记作 R o S,
R o S={〈 x,z〉 |? y(〈 x,y〉 ∈ R∧ 〈 y,z〉 ∈ S)}.
-1
-1
-1
-1
SR?
4.3.2 关系的基本运算定理 4.3-1 设 F是任意的关系，则
（ 1）（ F ） =F；
（ 2） domF =ranF,ranF =domF.
定理 4.3-2 设 F,G,H是任意的关系，则
（ 1）（ F o G） o H=F o (G o H)；
（ 2）（ F o G ） =G o F,
定理 4.3-3 设 R为 A上的关系，则
R o IA=IA o R=R.
定理 4.3-2 说明合成运算满足结合律，对于多个关系的合成，只要不交换它们的次序，不管谁先参与合成，最后的结果都是一样的,
-1-1
-1 -1
SR?
-1 -1 -1
4.3.3 关系的幂运算由于关系合成满足结合律，因此可以定义关系的幂运算,这里的关系指的是集合 A上的关系,
定义 4.3-4 设 R为 A上的关系,n为自然数，则 R的 n次幂定义为
（ 1） R ={〈 x,x〉 |x∈ A}=IA ；
（ 2） R =R o R.
-1
SR?
0
n+1 n
4.3.3 关系的幂运算定理 4.3-4 设 A为 n元集,R是 A上的关系，则存在自然数 s和 t，使得 R =R,
定理 4.3-5 设 R是 A上的关系,m,n∈ N,则
（ 1） R o R =R ；
（ 2）（ R ） =R,
定理 4.3-6 设 R是 A上的关系，若存在自然数 s,t(s<t)，
使得 R =R,则
（ 1）对任意 k∈ N，有 R =R ；
（ 2）对任意 k,i∈ N，有 R =R,其中 p=t-s；
（ 3）令 S={R,R,…,R },则对于任意的 q∈ N，有 R
∈ S.
s
SR?
m n m+n
t
mnm n
s t
s+k t+k
s+kp+i s+i
q0 1 t-1
4.4 关系的闭包运算设 R是集合 A上的关系，如果 R不具有某些性质，比如说对称性，那么可以通过在 R中加入最少数量的有序对来扩充 R，使得扩充后的 R′具有对称性,这种经过扩充的 R′称为 R的对称闭包,类似地也可以构造 R的自反和传递闭包,
关系的闭包运算是关系上的一元运算，是包含该关系且具有某种性质的最小关系,
SR?
4.4 关系的闭包运算定义 4.4-1 设 R是 A上的二元关系，如果有另一个关系 R′，满足：
（ 1） R′是自反的 (对称的、可传递的 )；
（ 2） R R′；
（ 3） 对于任何自反的 (对称的、可传递的 )关系 R″，都有 R′ R″，
则称关系 R′为 R的自反 (对称，传递 )闭包,R的自反、对称和传递闭包分别记为 r(R),s(R)和 t(R).
定理 4.4-1 设 R为非空集合 A上的关系，则
(1) R是自反的，当且仅当 r(R)=R；
(2) R是对称的，当且仅当 s(R)=R；
(3) R是传递的，当且仅当 t(R)=R.
SR?
4.4 关系的闭包运算定理 4.4-2 设 R为非空集合 A上的关系，则
(1) r(R)=R∪ IA；
(2) s(R)=R∪ R ；
(3) t(R)=∪ R =R ∪ R ∪ R ∪ ….
SR?
-1
∞
i=1
i 21 3
4.4 关系的闭包运算下面给出有关关系闭包的各种性质，有兴趣的读者自己证明,
定理 4.4-3 设 R1,R2是集合 A上的关系，且 R1 R2，则
（ 1） r(R1) r(R2)；
（ 2） s(R1) s(R2)；
（ 3） t(R1) t(R2).
定理 4.4-4 设 R1,R2是集合 A上的关系，则
（ 1） r(R1∪ R2)=r(R1)∪ r(R2)；
（ 2） s(R1∪ R2)=s(R1)∪ s(R2)；
（ 3） t(R1∪ R2) t(R1)∪ t(R2).
定理 4.4-5 设 R是集合 A上的关系，则
（ 1）若 R是自反的，则 s(R),t(R)也是自反的；
（ 2）若 R是对称的，则 r(R),t(R)也是对称的；
（ 3）若 R是传递的，则 r(R)也是传递的,
SR?
4.4 关系的闭包运算定义 4.4-2
（ 1）集合 A上的关系的自反对称闭包定义为 rs(R)=r(s(R))；
（ 2）集合 A上的关系的自反传递闭包定义为 rt(R)=r(t(R))；
（ 3）集合 A上的关系的对称传递闭包定义为 st(R)=s(t(R)).
同上，还可定义 sr(R),tr(R),ts(R),….
定理 4.4-6 设 R是集合 A上的关系，则
（ 1） rs(R)=sr(R)；
（ 2） rt(R)=tr(R)；
（ 3） st(R) ts(R).
上述（ 3）只能保证是单方面的包含关系，而无法证明其相等
SR?
4.5 等价关系与集合的划分
4.5.1 等价关系
4.5.2 集合的划分
4.5.1 等价关系前面讨论了关系的性质及运算，若一个关系满足不同的性质，则构成不同类型特征的关系空间,事实上，五种关系性质（自反、反自反、
对称、反对称、传递）的组合状态是较多的，我们只研究其中几种具有特别重要的二元关系,
定义 4.5-1 设 R为非空集合 A上的关系，若 R是自反的、对称的和传递的，则称 R为 A上的等价关系，简称等价关系,对任何 x,y∈ A，如果 <x,y>∈ R (R为等价关系 )，则记作 x～ y.
SR?
4.5.1 等价关系定义 4.5-2 设 R是非空集合 A上的等价关系,? x∈ A，令
［ x］ R={y|y∈ A∧ xRy},则称［ x］ R为 x的关于 R的等价类，简称为 x的等价类，在不引起混乱时，可将［ x］ R简记为［ x］,
定理 4.5-1 设 R是非空集合 A上的等价关系，对于任意的 x,y∈ A，
下面的结论成立：
(1)［ x］ R≠φ且［ x］ R A；
(2) 若 〈 x,y〉 ∈ R,则［ x］ R=［ y］ R；
(3) 若 〈 x,y〉? R,则［ x］ R∩ ［ y］ R= φ ；
(4)∪ {［ x］ R |x∈ A}=A.
定义 4.5-3 设 R是非空集合 A上的等价关系，以关于 R的全体不同的等价关系类为元素的集合称作 A关于 R的商集，简称 A的商集，记作
A/R.
SR?
4.5.2 集合的划分定义 4.5-4 设 A为非空集合，若存在 A的一个子集族 π(π P(A))满足：
（ 1） π≠ φ ；
（ 2）? x? y∈ π且 x≠y，则 x∩y= φ ；
（ 3） ∪ π=A,
则称 π是 A的一个划分，称 π中的元素为 A的划分块,
定理 4.5-2 设 A为非空集合，
(1) 设 R为 A上的任意一个等价关系，则对应 R的商集 A/R为 A的一个划分；
(2) 设 π为 A的任意一个划分，令 Rπ={〈 x,y〉 |x,y∈ A∧ x,y属于 π的同一划分块 }，则 Rπ为 A上的等价关系,
定理 4.5-3 说明在划分和等价关系之间存在着一一对应关系,即给定非空集合 A上的一个等价关系 R，由 R可以唯一产生集合 A的一个划分 π＝
A/R，反之，对非空集合 A的任一划分 π＝ {A1,A2,…,A k}，可以唯一对应集合 A上的一个等价关系：
R ＝（ A1× A1） ∪ （ A2× A2） ∪ … ∪ （ Ak× Ak）,
SR?
4.6 偏序关系
4.6.1 偏序关系
4.6.2 哈斯图
4.6.3 特殊元素
4.6.1 偏序关系集合 A上除了等价关系之外，另一种重要的关系是偏序关系，也称为为部分序关系，顾名思义就是 A上部分元素之间的顺序关系,这种关系在实际应用中广泛存在,比如，
通常的数之间的大于等于关系，集合之间的包含关系等都是偏序关系，下面给出偏序关系的定义,
定义 4.6-1 设 R是非空集合 A上的关系，若 R是自反的，
反对称和传递的，则称 R为 A上的偏序关系，简称偏序，
记作 ≤.称有序对 〈 A,R〉 为偏序集,
SR?
4.6.1 偏序关系定义 4.6-2 设〈 A,≤ 〉为偏序集，对于任意的 x,y∈ A，
如果 x ≤ y或者 y ≤ x成立，则称 x与 y是可比的；如果 x<y(即
x ≤ y∧ x≠y)，且不存在 z∈ A使得 x<z<y，则称 y盖住 x.其中
x<y读作 x“小于” y，它是指在偏序中,x排在 y的前边,
定义 4.6-3 设 〈 A,≤〉 为偏序集，若对任意的 x,y∈ A，
x和 y都可比，则称 ≤为 A上的全序关系（或线序），且称
〈 A,≤〉 为全序集，或线序集，或链,
SR?
4.6.2 哈斯图对于有穷的偏序集 〈 A,≤〉 可以用哈斯图来描述,哈斯图的画法如下：
（ 1）集合 A中的每个元素用一个结点表示,
（ 2）结点位置按它们在偏序中的次序从底向上排列,如果 y盖住 x，
则在 x和 y之间连成一条线,
实际上哈斯图就是简化的关系图,与关系图相比，哈斯图舍弃了反映关系的自反性的每个元素的环，去掉了弧线的箭头,对于 A的任意两个元素 x和 y，只要在其哈斯图中，从 x到 y有路相通，就表示其间有偏序关系，因此，其传递性已得到显示,而由下至上的方向充分表现出其反对称性,
SR?
4.6.3 特殊元素定义 4.6-4 设 〈 A,≤ 〉 为偏序集,B A.
(1)若? y∈ B，使得?x(x∈ B→y ≤ x)成立，则称 y是 B的最小元,
(2)若? y∈ B，使得?x(x∈ B→ x ≤ y)成立，则称 y是 B的最大元,
(3)若? y∈ B，使得 x(x∈ B∧ x < y)成立，则称 y是 B的极小元,
(4)若? y∈ B，使得 x(x∈ B∧ y < x)成立，则称 y是 B的极大元,
SR?
4.6.3 特殊元素定义 4.6-5 设〈 A,≤ 〉为偏序集,B A.
(1)若? y∈ A，使得?x(x∈ B→ x ≤ y)成立，则称 y是 B的上界,
(2)若? y∈ A，使得?x(x∈ B→ y ≤ x)成立，则称 y是 B的下界,
(3)令 C={y|y为 B的上界 }，则称 C的最小元为 B的最小上界或上确界,
(4)令 D={y|y为 B的下界 }，则称 D的最大元为 B的最大下界或下确界,
SR?
本章小结本章主要讨论了：
(1) 有序对（序偶）,n元组、笛卡儿积的概念及性质,
(2) 二元关系的定义与表示方法（集合表示、关系矩阵和关系图）
及关系的性质（自反性、反自反性、对称性、反对称性和传递性）,
(3) 关系定义域，值域的概念，逆关系，合成关系等的概念及性质,
(4) 关系的自反、对称和传递闭包的概念及求法,
(5) 等价关系及划分,
(6) 偏序关系及偏序集，偏序关系的关系图用哈斯图来表示,
(7) 一些特殊的二元关系：空关系、恒等关系、全域关系等,
SR?
4.1 集合的笛卡儿积
4.2 二元关系的概念及其特性
4.3 二元关系的运算
4.4 关系的闭包运算
4.5 等价关系与集合的划分
4.6 偏序关系第 4章 关系关系是离散数学中刻画元素之间相互联系的一个重要的概念，在计算机科学与技术领域中有着广泛的应用，关系数据库模型就是以关系及其运算作为理论基础的,
在诸多的关系中，最基本的涉及两个事物之间的关系，即二元关系,本章主要讨论二元关系，先给出二元关系的定义和特性，
然后讨论关系的运算及关系的闭包运算，
最后给出最重要的二元关系 —— 等价关系和偏序关系,
4.1 集合的笛卡儿积
4.1.1 有序对的概念
4.1.2 笛卡儿积
4.1.1 有序对的概念给定一个集合，其成员之间往往存在某种关系,例如，
某一家庭集合,{父，母，儿，媳，孙 }这种成员的关系可以有多种，夫妻、上下辈份等,对于不同的两个集合，其成员之间也可能存在某种关系,例如,这个家庭集合中的成员与另一个家庭集合中的某成员是兄弟关系，两家的儿媳妇为姊妹关系等,
总之，可以将事物之间的结构联系抽象概括为集合中元素之间的关系,例如,A={a,b,c,d}表示男教师,B={x,y,z}表示女教师集合,如果 A,B的元素之间有夫妻关系，是 a和 y，
c和 z，那么
（ 1） a和 y是成对出现,c和 z是成对出现,
（ 2）根据谓词概念，这对元素具有一定顺序,
（ 3）应该给出特定的表示方法表达这种关系,
4.1.1 有序对的概念定义 4.1-1 由两个元素，比如 x和 y，按照一定顺序构成的序列称为有序对，也称序偶或二元组，记作〈 x,y〉
（也可记作（ x,y）），其中 x是它的第一元素,y是它的第二元素,且 x,y,可以相同,
例如，坐标系中点的坐标（ 3,4），（ -1,2）就是有序对,
一般说来有序对具有以下特点：
（ 1） 当 x≠y时，〈 x,y〉 ≠〈 y,x〉,即在一个有序对中，
如果两个元素不相等，那么它们是不能交换次序的,例如，
〈 0,1〉与〈 1,0〉代表不同的有序对,
（ 2） 两个有序对相等，即〈 x,y〉 =〈 u,v〉的充分必要条件是 x=u且 y=v.
4.1.1 有序对的概念定义 4.1-2 一个有序 n元组 (n≥3)是一个有序对，其中第一个元素是一个有序 n-1元组,一个有序 n元组记作
〈 x1,x2,…,x n〉，即
〈 x1,x2,…,x n〉 =〈〈 x1,…,x n-1〉,xn〉,
有序 3元组〈 x,y,z〉可以表示为〈〈 x,y〉,z〉，同样具有特点〈〈 x,y〉,z〉 =〈〈 u,v〉,w〉的充分必要条件是
〈 x,y〉 =〈 u,v〉,z=w，即 x=u,y=v,z=w.例如，空间直角坐标系中点的坐标〈 1,-1,3〉,〈 2,4.5,0〉等都是有序 3
元组,n维空间中点的坐标或 n维向量都是有序 n元组,
形式上也可以把〈 x〉看成有序 1元组，只不过这里的顺序性没有什么实际意义,以后提到有序 n元组，其中的 n
可以看成任何的正整数,
4.1.2 笛卡儿积定义 4.1-3 设 A,B为两个集合，称由
A中元素为第一个元素,B中元素为第二个元素的所有有序对组成的集合为 A与 B的笛卡儿积，记作 A× B.符号化表示为
A× B={〈 x,y〉 |x∈ A∧ y∈ B}.
4.1.2 笛卡儿积有穷集合的笛卡儿积运算满足下述性质：
（ 1）若 A,B中有一个是空集，则它们的笛卡儿积是空集，即
A× B=A× B=φ,
（ 2）当 A≠B且 A,B都不是空集时，有 A× B≠B× A.
（ 3）当 A,B,C都不是空集时，有
(A× B)× C={〈〈 a,b〉,c〉 |(〈 a,b〉 ∈ A× B)∧ (c∈ C)}，
A× (B× C)={〈 a,〈 b,c〉〉 |(a∈ A)∧ (〈 b,c〉 ∈ B× C)}，
由于〈 a,〈 b,c〉〉不是有序 3元组,(A× B)× C ≠
A× (B× C).
如果 A,B,C中有一个是空集，那么上面式子的左右两边都是空集,这条性质说明笛卡儿积运算不适合结合律,
4.1.2 笛卡儿积
（ 4）笛卡儿积运算对并和交运算满足分配律，即
A× (B∪ C)=(A× B)∪ (A× C)，
(B∪ C)× A=(B× A)∪ (C× A)，
A× (B∩C)=(A× B)∩(A× C)，
(B∩C)× A=(B× A)∩(C× A).
4.1.2 笛卡儿积定义 4.1-4 设 A1,A2,…,A n为 n个集合 (n≥2)，称集合
A1× A2× … × An={〈 x1,x2,…,x n〉 |xi∈ Ai,i=1,2,…,n}
为 n阶笛卡儿积,当 A1=A2=…=A n=A时，记 A生成的 n阶笛卡儿积为 An.
设 A1,A2,…,A n均为有限集合，并设 |Ai|=ni,i=1,2,…,n,
则 |A1× A2× … × An|=n1× n2× … × nn.
n维笛卡儿积的性质与二维笛卡儿积的性质类似，这里不再赘述,
4.2 二元关系的概念及其特性
4.2.1 二元关系的概念
4.2.2 关系的表示法
4.2.3 关系的性质
4.2.1 二元关系的概念客观事物之间的关系种类是相当繁多的,我们只能研究其抽象定义,对于具体关系只是抽象定义下的一个指派，
显然这种指派仅是笛卡儿积的一个子集,
定义 4.2-1 若集合 R中的全体元素均为有序的 n(n≥2)
元组，则称 R为 n元关系，特别地，当 n=2时，称 R为二元关系，简称为关系,
对于二元关系 R,若〈 x,y〉 ∈ R，则记为 xRy，若
〈 x,y〉? R,则记为 xRy.规定空集 φ为 n元空关系，当然也是二元空关系，简称空关系,
4.2.1 二元关系的概念定义 4.2-2 设 A,B为两个集合,A× B得任何子集 R均称为从 A到 B的二元关系，特别地，称 A× A得子集 R为 A上的二元关系,
设 A={a1,a2},B={b},A× B得子集 φ,
{〈 a1,b〉 },{〈 a2,b〉 },{〈 a1,b〉,〈 a2,b〉 },为 A到 B的全部二元关系,φ,{〈 b,a1〉 },{〈 b,a2〉 },{〈 b,a1〉,〈 b,a2〉 }为 B到
A的全部二元关系,而 B上的二元关系有两个,φ,{b,b},A上的二元关系共有 16个二元关系，这里不一一列举,
4.2.1 二元关系的概念定义 4.2-3 对任何集合 A，称 EA={〈 x,y〉 |x∈ A∧ y∈ A}=A× A为 A
上的全域关系,称 IA={〈 x,x〉 |x∈ A}为 A上的恒等关系,
若 A是实数集或其子集，还可以定义下面的各种关系：
称 DA={〈 x,y〉 |x∈ A∧ y∈ A∧ x|y}为 A上的整除关系，其中 x|y为 x
整除 y.
称 LA={〈 x,y〉 |x∈ A∧ y∈ A∧ x≤y}为 A上的小于等于关系,
4.2.2 关系的表示法前面给出的关系都是用集合表达式来定义的,对于有穷集合 A上的关系 R，还可以用关系矩阵和关系图来给出,下面给出关系矩阵和关系图的一般定义,
定义 4.2-4 设 A={x1,x2,…,x n},R是 A上的关系，令
1,若 xiRxj
rij=,(i,j=1,2,…,n)
0,若 xiRxj
r11 r12 … r1n
则 (rij)= r21 r22 … r 2n
… … … …
rn1 rn2 … r nn
是 R的关系矩阵,并记作 MR.
4.2.2 关系的表示法定义 4.2-5 设 A={x1,x2,…,x n},R A× A是 A上的关系，
以 A的元素为结点，若〈 xi,xj〉 ∈ R，则从结点 xi向 xj引一条有向边，这样得到的有向图称为 R的关系图 GR.
例如，设 A={1,2,3,4}，则 R={〈 1,1〉,〈 1,2〉,〈 2,3〉,
〈 2,4〉,〈 4,2〉 }是 A上的关系,R的关系矩阵和关系图表示为
1 1 0 0
0 0 1 1
0 0 0 0
0 1 0 0
4.2.3 关系的性质本小节涉及的主要内容是某个集合 A上的关系的性质，
有必要说明，本节内讨论的是非空集合上的二元关系的性质,
定义 4.2-6 设 R是集合 A上的二元关系，如果对于每一个 x∈ A均有 xRx，则称二元关系 R是自反的,即
R在 A (? x)(x∈ A→ 〈 x,x〉 ∈ R).
4.2.3 关系的性质定义 4.2-7 设 R是集合 A上的二元关系，如果对于每一个 x∈ A，均有〈 x,x〉? R，则称二元关系 R是反自反的,即
R在 A (? x)(x∈ A→ 〈 x,x〉? R).
例如,A={1,2,3},R={〈 2,1〉,〈 2,3〉,〈 3,2〉 }，显然 x可以取 1,2,3，〈 x,x〉? R，按定义,R是反自反的,
4.2.3 关系的性质定义 4.2-8 设 R是定义在集合 A上的一个二元关系，如果对于每一个 x,y∈ A，每当 xRy,则有 yRx，则称二元关系 R为 A上的对称关系,即
R在 A (? x)(? y)(x∈ A∧ y∈ A∧ xRy→ yRx).
定义 4.2-9 设 R是定义在集合 A上的一个二元关系,
如果对于每一个 x,y∈ A，每当 xRy且 yRx，则必有 x=y，称
R为 A上的反对称关系,即
R在 A
(? x)(? y)(x∈ A∧ y∈ A∧ xRy∧ yRx→x=y)
4.2.3 关系的性质定义 4.2-10 设 R是定义在集合 A上的二元关系：如果对于任意 x,y,z∈ A.每当 xRy且 yRz时，就有 xRz，则称 R是
A上的传递关系,即
(? x)(? y)(? z)(x∈ A∧ y∈ A∧ z∈ A∧ xRy∧ yRz→ xRz)
关于定义中的条件理解，要特别注意每当有 xRy,yRz
时，就有 xRz.换句话说，若没有 xRy,yRz,就不必去考虑
xRz.若存在一个 xRy,yRz,而没有 xRz就不是传递的,
4.3 二元关系的运算
4.3.1 定义域与值域
4.3.2 关系的基本运算
4.3.3 关系的幂运算
4.3.1 定义域与值域定义 4.3-1 设 R为二元关系,R的定义域、值域和域分别记作 domR,ranR,fldR，其中
domR={x|? y(〈 x,y〉 ∈ R)}，
ranR={y|? x(〈 x,y〉 ∈ R)}，
fldR=domR∪ ranR.
由定义不难看出，定义域 domR是 R中所有有序对的第一元素构成的集合，值域 ranR是 R中所有有序对的第二元素构成的集合，域 fldR是 R中有序对涉及的全体元素的集合,
4.3.2 关系的基本运算定义 4.3-2 设 R为二元关系,R的逆记作 R,其中
R ={〈 y,x〉 |〈 x,y〉 ∈ R}.
不难看出,R 就是把 R的每个有序对的两个元素交换以后得到的关系,如果 R是整数集 Z上的小于关系，那么 R
就是 Z上的大于关系,类似地，整除关系的逆就是倍数关系,
定义 4.3-3 设 R,S为二元关系,R与 S的合成记作 R o S,
R o S={〈 x,z〉 |? y(〈 x,y〉 ∈ R∧ 〈 y,z〉 ∈ S)}.
-1
-1
-1
-1
SR?
4.3.2 关系的基本运算定理 4.3-1 设 F是任意的关系，则
（ 1）（ F ） =F；
（ 2） domF =ranF,ranF =domF.
定理 4.3-2 设 F,G,H是任意的关系，则
（ 1）（ F o G） o H=F o (G o H)；
（ 2）（ F o G ） =G o F,
定理 4.3-3 设 R为 A上的关系，则
R o IA=IA o R=R.
定理 4.3-2 说明合成运算满足结合律，对于多个关系的合成，只要不交换它们的次序，不管谁先参与合成，最后的结果都是一样的,
-1-1
-1 -1
SR?
-1 -1 -1
4.3.3 关系的幂运算由于关系合成满足结合律，因此可以定义关系的幂运算,这里的关系指的是集合 A上的关系,
定义 4.3-4 设 R为 A上的关系,n为自然数，则 R的 n次幂定义为
（ 1） R ={〈 x,x〉 |x∈ A}=IA ；
（ 2） R =R o R.
-1
SR?
0
n+1 n
4.3.3 关系的幂运算定理 4.3-4 设 A为 n元集,R是 A上的关系，则存在自然数 s和 t，使得 R =R,
定理 4.3-5 设 R是 A上的关系,m,n∈ N,则
（ 1） R o R =R ；
（ 2）（ R ） =R,
定理 4.3-6 设 R是 A上的关系，若存在自然数 s,t(s<t)，
使得 R =R,则
（ 1）对任意 k∈ N，有 R =R ；
（ 2）对任意 k,i∈ N，有 R =R,其中 p=t-s；
（ 3）令 S={R,R,…,R },则对于任意的 q∈ N，有 R
∈ S.
s
SR?
m n m+n
t
mnm n
s t
s+k t+k
s+kp+i s+i
q0 1 t-1
4.4 关系的闭包运算设 R是集合 A上的关系，如果 R不具有某些性质，比如说对称性，那么可以通过在 R中加入最少数量的有序对来扩充 R，使得扩充后的 R′具有对称性,这种经过扩充的 R′称为 R的对称闭包,类似地也可以构造 R的自反和传递闭包,
关系的闭包运算是关系上的一元运算，是包含该关系且具有某种性质的最小关系,
SR?
4.4 关系的闭包运算定义 4.4-1 设 R是 A上的二元关系，如果有另一个关系 R′，满足：
（ 1） R′是自反的 (对称的、可传递的 )；
（ 2） R R′；
（ 3） 对于任何自反的 (对称的、可传递的 )关系 R″，都有 R′ R″，
则称关系 R′为 R的自反 (对称，传递 )闭包,R的自反、对称和传递闭包分别记为 r(R),s(R)和 t(R).
定理 4.4-1 设 R为非空集合 A上的关系，则
(1) R是自反的，当且仅当 r(R)=R；
(2) R是对称的，当且仅当 s(R)=R；
(3) R是传递的，当且仅当 t(R)=R.
SR?
4.4 关系的闭包运算定理 4.4-2 设 R为非空集合 A上的关系，则
(1) r(R)=R∪ IA；
(2) s(R)=R∪ R ；
(3) t(R)=∪ R =R ∪ R ∪ R ∪ ….
SR?
-1
∞
i=1
i 21 3
4.4 关系的闭包运算下面给出有关关系闭包的各种性质，有兴趣的读者自己证明,
定理 4.4-3 设 R1,R2是集合 A上的关系，且 R1 R2，则
（ 1） r(R1) r(R2)；
（ 2） s(R1) s(R2)；
（ 3） t(R1) t(R2).
定理 4.4-4 设 R1,R2是集合 A上的关系，则
（ 1） r(R1∪ R2)=r(R1)∪ r(R2)；
（ 2） s(R1∪ R2)=s(R1)∪ s(R2)；
（ 3） t(R1∪ R2) t(R1)∪ t(R2).
定理 4.4-5 设 R是集合 A上的关系，则
（ 1）若 R是自反的，则 s(R),t(R)也是自反的；
（ 2）若 R是对称的，则 r(R),t(R)也是对称的；
（ 3）若 R是传递的，则 r(R)也是传递的,
SR?
4.4 关系的闭包运算定义 4.4-2
（ 1）集合 A上的关系的自反对称闭包定义为 rs(R)=r(s(R))；
（ 2）集合 A上的关系的自反传递闭包定义为 rt(R)=r(t(R))；
（ 3）集合 A上的关系的对称传递闭包定义为 st(R)=s(t(R)).
同上，还可定义 sr(R),tr(R),ts(R),….
定理 4.4-6 设 R是集合 A上的关系，则
（ 1） rs(R)=sr(R)；
（ 2） rt(R)=tr(R)；
（ 3） st(R) ts(R).
上述（ 3）只能保证是单方面的包含关系，而无法证明其相等
SR?
4.5 等价关系与集合的划分
4.5.1 等价关系
4.5.2 集合的划分
4.5.1 等价关系前面讨论了关系的性质及运算，若一个关系满足不同的性质，则构成不同类型特征的关系空间,事实上，五种关系性质（自反、反自反、
对称、反对称、传递）的组合状态是较多的，我们只研究其中几种具有特别重要的二元关系,
定义 4.5-1 设 R为非空集合 A上的关系，若 R是自反的、对称的和传递的，则称 R为 A上的等价关系，简称等价关系,对任何 x,y∈ A，如果 <x,y>∈ R (R为等价关系 )，则记作 x～ y.
SR?
4.5.1 等价关系定义 4.5-2 设 R是非空集合 A上的等价关系,? x∈ A，令
［ x］ R={y|y∈ A∧ xRy},则称［ x］ R为 x的关于 R的等价类，简称为 x的等价类，在不引起混乱时，可将［ x］ R简记为［ x］,
定理 4.5-1 设 R是非空集合 A上的等价关系，对于任意的 x,y∈ A，
下面的结论成立：
(1)［ x］ R≠φ且［ x］ R A；
(2) 若 〈 x,y〉 ∈ R,则［ x］ R=［ y］ R；
(3) 若 〈 x,y〉? R,则［ x］ R∩ ［ y］ R= φ ；
(4)∪ {［ x］ R |x∈ A}=A.
定义 4.5-3 设 R是非空集合 A上的等价关系，以关于 R的全体不同的等价关系类为元素的集合称作 A关于 R的商集，简称 A的商集，记作
A/R.
SR?
4.5.2 集合的划分定义 4.5-4 设 A为非空集合，若存在 A的一个子集族 π(π P(A))满足：
（ 1） π≠ φ ；
（ 2）? x? y∈ π且 x≠y，则 x∩y= φ ；
（ 3） ∪ π=A,
则称 π是 A的一个划分，称 π中的元素为 A的划分块,
定理 4.5-2 设 A为非空集合，
(1) 设 R为 A上的任意一个等价关系，则对应 R的商集 A/R为 A的一个划分；
(2) 设 π为 A的任意一个划分，令 Rπ={〈 x,y〉 |x,y∈ A∧ x,y属于 π的同一划分块 }，则 Rπ为 A上的等价关系,
定理 4.5-3 说明在划分和等价关系之间存在着一一对应关系,即给定非空集合 A上的一个等价关系 R，由 R可以唯一产生集合 A的一个划分 π＝
A/R，反之，对非空集合 A的任一划分 π＝ {A1,A2,…,A k}，可以唯一对应集合 A上的一个等价关系：
R ＝（ A1× A1） ∪ （ A2× A2） ∪ … ∪ （ Ak× Ak）,
SR?
4.6 偏序关系
4.6.1 偏序关系
4.6.2 哈斯图
4.6.3 特殊元素
4.6.1 偏序关系集合 A上除了等价关系之外，另一种重要的关系是偏序关系，也称为为部分序关系，顾名思义就是 A上部分元素之间的顺序关系,这种关系在实际应用中广泛存在,比如，
通常的数之间的大于等于关系，集合之间的包含关系等都是偏序关系，下面给出偏序关系的定义,
定义 4.6-1 设 R是非空集合 A上的关系，若 R是自反的，
反对称和传递的，则称 R为 A上的偏序关系，简称偏序，
记作 ≤.称有序对 〈 A,R〉 为偏序集,
SR?
4.6.1 偏序关系定义 4.6-2 设〈 A,≤ 〉为偏序集，对于任意的 x,y∈ A，
如果 x ≤ y或者 y ≤ x成立，则称 x与 y是可比的；如果 x<y(即
x ≤ y∧ x≠y)，且不存在 z∈ A使得 x<z<y，则称 y盖住 x.其中
x<y读作 x“小于” y，它是指在偏序中,x排在 y的前边,
定义 4.6-3 设 〈 A,≤〉 为偏序集，若对任意的 x,y∈ A，
x和 y都可比，则称 ≤为 A上的全序关系（或线序），且称
〈 A,≤〉 为全序集，或线序集，或链,
SR?
4.6.2 哈斯图对于有穷的偏序集 〈 A,≤〉 可以用哈斯图来描述,哈斯图的画法如下：
（ 1）集合 A中的每个元素用一个结点表示,
（ 2）结点位置按它们在偏序中的次序从底向上排列,如果 y盖住 x，
则在 x和 y之间连成一条线,
实际上哈斯图就是简化的关系图,与关系图相比，哈斯图舍弃了反映关系的自反性的每个元素的环，去掉了弧线的箭头,对于 A的任意两个元素 x和 y，只要在其哈斯图中，从 x到 y有路相通，就表示其间有偏序关系，因此，其传递性已得到显示,而由下至上的方向充分表现出其反对称性,
SR?
4.6.3 特殊元素定义 4.6-4 设 〈 A,≤ 〉 为偏序集,B A.
(1)若? y∈ B，使得?x(x∈ B→y ≤ x)成立，则称 y是 B的最小元,
(2)若? y∈ B，使得?x(x∈ B→ x ≤ y)成立，则称 y是 B的最大元,
(3)若? y∈ B，使得 x(x∈ B∧ x < y)成立，则称 y是 B的极小元,
(4)若? y∈ B，使得 x(x∈ B∧ y < x)成立，则称 y是 B的极大元,
SR?
4.6.3 特殊元素定义 4.6-5 设〈 A,≤ 〉为偏序集,B A.
(1)若? y∈ A，使得?x(x∈ B→ x ≤ y)成立，则称 y是 B的上界,
(2)若? y∈ A，使得?x(x∈ B→ y ≤ x)成立，则称 y是 B的下界,
(3)令 C={y|y为 B的上界 }，则称 C的最小元为 B的最小上界或上确界,
(4)令 D={y|y为 B的下界 }，则称 D的最大元为 B的最大下界或下确界,
SR?
本章小结本章主要讨论了：
(1) 有序对（序偶）,n元组、笛卡儿积的概念及性质,
(2) 二元关系的定义与表示方法（集合表示、关系矩阵和关系图）
及关系的性质（自反性、反自反性、对称性、反对称性和传递性）,
(3) 关系定义域，值域的概念，逆关系，合成关系等的概念及性质,
(4) 关系的自反、对称和传递闭包的概念及求法,
(5) 等价关系及划分,
(6) 偏序关系及偏序集，偏序关系的关系图用哈斯图来表示,
(7) 一些特殊的二元关系：空关系、恒等关系、全域关系等,
SR?
