1
4.5 等价关系与偏序关系
? 等价关系的定义与实例
? 等价类及其性质
? 商集与集合的划分
? 等价关系与划分的一一对应
? 偏序关系
? 偏序集与哈斯图
? 偏序集中的特定元素
2
等价关系的定义与实例
定义 设 R 为非空集合上的关系, 如果 R 是自反的、
对称的和传递的,则称 R 为 A 上的 等价关系, 设 R
是一个等价关系,若 <x,y>∈ R,称 x 等价于 y,记做
x～ y,
实例 设 A={1,2,…,8},如下定义 A上的关系 R,
R = { <x,y> | x,y∈ A∧ x≡y(mod 3) }
其中 x≡y(mod 3) 叫做 x 与 y 模 3相等,即 x 除以 3的
余数与 y 除以 3的余数相等,
3
等价关系的验证
验证模 3 相等关系 R 为 A上的等价关系,因为
?x∈ A,有 x ≡ x(mod 3)
?x,y∈ A,若 x ≡ y(mod 3),则有 y ≡ x(mod 3)
?x,y,z∈ A,若 x ≡ y(mod 3),y ≡ z(mod 3),
则有 x≡z(mod 3)
自反性、对称性、传递性得到验证
4
A上模 3等价关系的关系图
设 A={1,2,…,8},
R={ <x,y>| x,y∈ A∧ x≡y(mod 3) }
5
等价类
定义 设 R为非空集合 A上的等价关系,?x∈ A，令
[x]R = { y | y∈ A∧ xRy }
称 [x]R 为 x 关于 R 的 等价类,简称为 x 的等价类,简
记为 [x],
实例 A={ 1,2,…,8 } 上模 3 等价关系的等价类,
[1]=[4]=[7]={1,4,7}
[2]=[5]=[8]={2,5,8}
[3]=[6]={3,6}
6
等价类的性质
定理 1 设 R是非空集合 A上的等价关系,则
(1) ?x∈ A,[x] 是 A的非空子集,
(2) ?x,y∈ A,如果 x R y,则 [x]=[y],
(3) ?x,y∈ A,如果 x y,则 [x]与 [y]不交,
(4) ∪ { [x] | x∈ A}=A,即所有等价类的并集就
是 A,
7
实例
A={ 1,2,…,8 } 上模 3 等价关系的等价类,
[1]=[4]=[7]={1,4,7},
[2]=[5]=[8]={2,5,8},
[3]=[6]={3,6}
以上 3 类两两不交,
{1,4,7}?{2,5,8}?{3,6} = {1,2,…,8}
8
商集
定义 设 R为非空集合 A上的等价关系,以 R的所有
等价类作为元素的集合称为 A关于 R的 商集,记做
A/R,A/R = { [x]R | x∈ A }
实例 A={1,2,…,8}, A关于模 3等价关系 R的商集为
A/R = { {1,4,7},{2,5,8},{3,6} }
A关于恒等关系和全域关系的商集为,
A/IA = { {1},{2},…,{8}}
A/EA = { {1,2,…,8} }
9
集合的划分
定义 设 A为非空集合,若 A的子集族 π(π?P(A))
满足下面条件,
(1) ??π
(2) ?x?y (x,y∈ π∧ x≠y→ x∩y=?)
(3) ∪ π=A
则称 π是 A的一个 划分,称 π中的元素为 A的 划分
块,
10
例题
例 1 设 A＝ {a,b,c,d},
给定 π1,π2,π3,π4,π5,π6如下,
π1= { {a,b,c},{d} },π2= { {a,b},{c},{d} }
π3= { {a},{a,b,c,d} },π4= { {a,b},{c} }
π5= { ?,{a,b},{c,d} },π6= { {a,{a}},{b,c,d} }
则 π1和 π2 是 A的划分,其他都不是 A 的划分,
为什么？
11
等价关系与划分的一一对应
商集 A/R 就是 A 的一个划分
不同的商集对应于不同的划分
任给 A 的一个划分 π,如下定义 A 上的关系 R,
R = {<x,y> | x,y∈ A∧ x 与 y 在 π的同一划分块中 }
则 R 为 A上的等价关系,且该等价关系确定的商集
就是 π,
例 2 给出 A＝ {1,2,3}上所有的等价关系
求解思路：先做出 A的所有划分,然后根据划分写
出对应的等价关系,
12
等价关系与划分之间的对应
π1,π2和 π3分别对应等价关系 R1,R2 和 R3,
R1={<2,3>,<3,2>}∪ IA,R2={<1,3>,<3,1>}∪ IA
R3={<1,2>,<2,1>}∪ IA
π4 对应于全域关系 EA,π5 对应于恒等关系 IA
13
实例
例 3 设 A={1,2,3,4}，在 A?A上定义二元关系 R,
<<x,y>,<u,v>>?R ? x+y = u+v,
求 R 导出的划分,
解 A?A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,
<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,
<4,2>,<4,3>,<4,4>}
14
实例（续）
根据 <x,y> 的 x + y = 2,3,4,5,6,7,8 将 A?A划分成 7个
等价类,
(A?A)/R={ {<1,1>},{<1,2>,<2,1>},
{<1,3>,<2,2>,<3,1>},
{<1,4>,<2,3>,<3,2>,<4,1>},
{<2,4>,<3,3>,<4,2>},
{<3,4>,<4,3>},{<4,4>} }
15
偏序关系
定义 非空集合 A上的自反、反对称和传递的关系，
称为 A上的 偏序关系,记作 ?,设 ?为偏序关系,如
果 <x,y>∈ ?,则记作 x?y,读作 x“小于或等于” y,
实例
集合 A上的恒等关系 IA 是 A上的偏序关系,
小于或等于关系,整除关系和包含关系也是相应
集合上的偏序关系,
16
相关概念
x与 y 可比,设 R为非空集合 A上的偏序关系,
x,y?A,x与 y可比 ? x?y ∨ y?x,
结论：任取两个元素 x和 y,可能有下述情况,
x?y (或 y?x),x＝ y,x与 y不是可比的,
全序关系,
R为非空集合 A上的偏序,?x,y?A,x与 y 都是可比的，
则称 R 为 全序 （或 线序 ）
实例：数集上的小于或等于关系是全序关系
整除关系不是正整数集合上的全序关系
17
覆盖,设 R为非空集合 A上的偏序关系,x,y∈ A,如
果 x ? y且不存在 z?A 使得 x ? z ? y,则称 y 覆盖
x,
实例,{ 1,2,4,6 }集合上的整除关系,
2 覆盖 1,
4 和 6 覆盖 2,
4 不覆盖 1,
相关概念（续）
18
偏序集与哈斯图
定义 集合 A和 A上的偏序关系 ?一起叫做 偏序集,记
作 <A,?>,
实例：整数集和小于等于关系构成偏序集 <Z,≤>，幂
集 P(A)和包含关系构成偏序集 <P(A),R?>,
哈斯图,利用偏序自反、反对称、传递性简化的关
系图
特点：每个结点没有环，两个连通的结点之间的序
关系通过结点位置的高低表示，位置低的元素的顺
序在前，具有覆盖关系的两个结点之间连边
19
哈斯图实例
例 4 <{ 1,2,3,4,5,6,7,8,9 },R整除 >
<P({a,b,c}),R?>
20
A={a,b,c,d,e,f,g,h}
R={<b,d>,<b,e>,<b,f>,<c,d>,
<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪ IA
哈斯图实例（续）
例 5
已知偏序集 <A,R>
的哈斯图如右图所示,
试求出集合 A和关系
R的表达式,
21
偏序集的特定元素
定义 设 <A,?>为偏序集,B?A,y∈ B,
(1) 若 ?x(x∈ B→ y?x) 成立,则称 y 为 B 的 最小元,
(2) 若 ?x(x∈ B→ x?y) 成立,则称 y 为 B 的 最大元,
(3) 若 ??x (x∈ B∧ x ? y) 成立,则称 y 为 B的 极小元,
(4) 若 ??x (x∈ B∧ y ? x) 成立,则称 y 为 B的 极大元,
22
特殊元素的性质
? 对于有穷集，极小元和极大元必存在，可能存在
多个,
? 最小元和最大元不一定存在，如果存在一定惟一,
? 最小元一定是极小元；最大元一定是极大元,
? 孤立结点既是极小元，也是极大元,
23
定义 设 <A,?>为偏序集,B?A,y?A,
(1) 若 ?x(x∈ B→ x?y) 成立,则称 y 为 B的 上界,
(2) 若 ?x(x∈ B→ y?x) 成立,则称 y 为 B的 下界,
(3) 令 C＝ {y | y为 B的上界 },则称 C的最小元为 B的
最小上界 或 上确界,
(4) 令 D＝ {y | y为 B的下界 },则称 D的最大元为 B的
最大下界 或 下确界,
偏序集的特定元素 (续 )
24
? 下界、上界、下确界、上确界不一定存在
? 下界、上界存在不一定惟一
? 下确界、上确界如果存在，则惟一
? 集合的最小元就是它的下确界，最大元就是它的
上确界；反之不对,
特殊元素的性质
25
实例
例 6 设偏序集 <A,?>如下图所示，求 A 的极小元、
最小元、极大元、最大元, 设 B＝ {b,c,d},求 B 的下
界、上界、下确界、上确界,
极小元,a,b,c,g；
极大元,a,f,h；
没有最小元与最大元,
B的下界和最大下界都
不存在,上界有 d 和 f,
最小上界为 d,
4.5 等价关系与偏序关系
? 等价关系的定义与实例
? 等价类及其性质
? 商集与集合的划分
? 等价关系与划分的一一对应
? 偏序关系
? 偏序集与哈斯图
? 偏序集中的特定元素
2
等价关系的定义与实例
定义 设 R 为非空集合上的关系, 如果 R 是自反的、
对称的和传递的,则称 R 为 A 上的 等价关系, 设 R
是一个等价关系,若 <x,y>∈ R,称 x 等价于 y,记做
x～ y,
实例 设 A={1,2,…,8},如下定义 A上的关系 R,
R = { <x,y> | x,y∈ A∧ x≡y(mod 3) }
其中 x≡y(mod 3) 叫做 x 与 y 模 3相等,即 x 除以 3的
余数与 y 除以 3的余数相等,
3
等价关系的验证
验证模 3 相等关系 R 为 A上的等价关系,因为
?x∈ A,有 x ≡ x(mod 3)
?x,y∈ A,若 x ≡ y(mod 3),则有 y ≡ x(mod 3)
?x,y,z∈ A,若 x ≡ y(mod 3),y ≡ z(mod 3),
则有 x≡z(mod 3)
自反性、对称性、传递性得到验证
4
A上模 3等价关系的关系图
设 A={1,2,…,8},
R={ <x,y>| x,y∈ A∧ x≡y(mod 3) }
5
等价类
定义 设 R为非空集合 A上的等价关系,?x∈ A，令
[x]R = { y | y∈ A∧ xRy }
称 [x]R 为 x 关于 R 的 等价类,简称为 x 的等价类,简
记为 [x],
实例 A={ 1,2,…,8 } 上模 3 等价关系的等价类,
[1]=[4]=[7]={1,4,7}
[2]=[5]=[8]={2,5,8}
[3]=[6]={3,6}
6
等价类的性质
定理 1 设 R是非空集合 A上的等价关系,则
(1) ?x∈ A,[x] 是 A的非空子集,
(2) ?x,y∈ A,如果 x R y,则 [x]=[y],
(3) ?x,y∈ A,如果 x y,则 [x]与 [y]不交,
(4) ∪ { [x] | x∈ A}=A,即所有等价类的并集就
是 A,
7
实例
A={ 1,2,…,8 } 上模 3 等价关系的等价类,
[1]=[4]=[7]={1,4,7},
[2]=[5]=[8]={2,5,8},
[3]=[6]={3,6}
以上 3 类两两不交,
{1,4,7}?{2,5,8}?{3,6} = {1,2,…,8}
8
商集
定义 设 R为非空集合 A上的等价关系,以 R的所有
等价类作为元素的集合称为 A关于 R的 商集,记做
A/R,A/R = { [x]R | x∈ A }
实例 A={1,2,…,8}, A关于模 3等价关系 R的商集为
A/R = { {1,4,7},{2,5,8},{3,6} }
A关于恒等关系和全域关系的商集为,
A/IA = { {1},{2},…,{8}}
A/EA = { {1,2,…,8} }
9
集合的划分
定义 设 A为非空集合,若 A的子集族 π(π?P(A))
满足下面条件,
(1) ??π
(2) ?x?y (x,y∈ π∧ x≠y→ x∩y=?)
(3) ∪ π=A
则称 π是 A的一个 划分,称 π中的元素为 A的 划分
块,
10
例题
例 1 设 A＝ {a,b,c,d},
给定 π1,π2,π3,π4,π5,π6如下,
π1= { {a,b,c},{d} },π2= { {a,b},{c},{d} }
π3= { {a},{a,b,c,d} },π4= { {a,b},{c} }
π5= { ?,{a,b},{c,d} },π6= { {a,{a}},{b,c,d} }
则 π1和 π2 是 A的划分,其他都不是 A 的划分,
为什么？
11
等价关系与划分的一一对应
商集 A/R 就是 A 的一个划分
不同的商集对应于不同的划分
任给 A 的一个划分 π,如下定义 A 上的关系 R,
R = {<x,y> | x,y∈ A∧ x 与 y 在 π的同一划分块中 }
则 R 为 A上的等价关系,且该等价关系确定的商集
就是 π,
例 2 给出 A＝ {1,2,3}上所有的等价关系
求解思路：先做出 A的所有划分,然后根据划分写
出对应的等价关系,
12
等价关系与划分之间的对应
π1,π2和 π3分别对应等价关系 R1,R2 和 R3,
R1={<2,3>,<3,2>}∪ IA,R2={<1,3>,<3,1>}∪ IA
R3={<1,2>,<2,1>}∪ IA
π4 对应于全域关系 EA,π5 对应于恒等关系 IA
13
实例
例 3 设 A={1,2,3,4}，在 A?A上定义二元关系 R,
<<x,y>,<u,v>>?R ? x+y = u+v,
求 R 导出的划分,
解 A?A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,
<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,
<4,2>,<4,3>,<4,4>}
14
实例（续）
根据 <x,y> 的 x + y = 2,3,4,5,6,7,8 将 A?A划分成 7个
等价类,
(A?A)/R={ {<1,1>},{<1,2>,<2,1>},
{<1,3>,<2,2>,<3,1>},
{<1,4>,<2,3>,<3,2>,<4,1>},
{<2,4>,<3,3>,<4,2>},
{<3,4>,<4,3>},{<4,4>} }
15
偏序关系
定义 非空集合 A上的自反、反对称和传递的关系，
称为 A上的 偏序关系,记作 ?,设 ?为偏序关系,如
果 <x,y>∈ ?,则记作 x?y,读作 x“小于或等于” y,
实例
集合 A上的恒等关系 IA 是 A上的偏序关系,
小于或等于关系,整除关系和包含关系也是相应
集合上的偏序关系,
16
相关概念
x与 y 可比,设 R为非空集合 A上的偏序关系,
x,y?A,x与 y可比 ? x?y ∨ y?x,
结论：任取两个元素 x和 y,可能有下述情况,
x?y (或 y?x),x＝ y,x与 y不是可比的,
全序关系,
R为非空集合 A上的偏序,?x,y?A,x与 y 都是可比的，
则称 R 为 全序 （或 线序 ）
实例：数集上的小于或等于关系是全序关系
整除关系不是正整数集合上的全序关系
17
覆盖,设 R为非空集合 A上的偏序关系,x,y∈ A,如
果 x ? y且不存在 z?A 使得 x ? z ? y,则称 y 覆盖
x,
实例,{ 1,2,4,6 }集合上的整除关系,
2 覆盖 1,
4 和 6 覆盖 2,
4 不覆盖 1,
相关概念（续）
18
偏序集与哈斯图
定义 集合 A和 A上的偏序关系 ?一起叫做 偏序集,记
作 <A,?>,
实例：整数集和小于等于关系构成偏序集 <Z,≤>，幂
集 P(A)和包含关系构成偏序集 <P(A),R?>,
哈斯图,利用偏序自反、反对称、传递性简化的关
系图
特点：每个结点没有环，两个连通的结点之间的序
关系通过结点位置的高低表示，位置低的元素的顺
序在前，具有覆盖关系的两个结点之间连边
19
哈斯图实例
例 4 <{ 1,2,3,4,5,6,7,8,9 },R整除 >
<P({a,b,c}),R?>
20
A={a,b,c,d,e,f,g,h}
R={<b,d>,<b,e>,<b,f>,<c,d>,
<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪ IA
哈斯图实例（续）
例 5
已知偏序集 <A,R>
的哈斯图如右图所示,
试求出集合 A和关系
R的表达式,
21
偏序集的特定元素
定义 设 <A,?>为偏序集,B?A,y∈ B,
(1) 若 ?x(x∈ B→ y?x) 成立,则称 y 为 B 的 最小元,
(2) 若 ?x(x∈ B→ x?y) 成立,则称 y 为 B 的 最大元,
(3) 若 ??x (x∈ B∧ x ? y) 成立,则称 y 为 B的 极小元,
(4) 若 ??x (x∈ B∧ y ? x) 成立,则称 y 为 B的 极大元,
22
特殊元素的性质
? 对于有穷集，极小元和极大元必存在，可能存在
多个,
? 最小元和最大元不一定存在，如果存在一定惟一,
? 最小元一定是极小元；最大元一定是极大元,
? 孤立结点既是极小元，也是极大元,
23
定义 设 <A,?>为偏序集,B?A,y?A,
(1) 若 ?x(x∈ B→ x?y) 成立,则称 y 为 B的 上界,
(2) 若 ?x(x∈ B→ y?x) 成立,则称 y 为 B的 下界,
(3) 令 C＝ {y | y为 B的上界 },则称 C的最小元为 B的
最小上界 或 上确界,
(4) 令 D＝ {y | y为 B的下界 },则称 D的最大元为 B的
最大下界 或 下确界,
偏序集的特定元素 (续 )
24
? 下界、上界、下确界、上确界不一定存在
? 下界、上界存在不一定惟一
? 下确界、上确界如果存在，则惟一
? 集合的最小元就是它的下确界，最大元就是它的
上确界；反之不对,
特殊元素的性质
25
实例
例 6 设偏序集 <A,?>如下图所示，求 A 的极小元、
最小元、极大元、最大元, 设 B＝ {b,c,d},求 B 的下
界、上界、下确界、上确界,
极小元,a,b,c,g；
极大元,a,f,h；
没有最小元与最大元,
B的下界和最大下界都
不存在,上界有 d 和 f,
最小上界为 d,
