《离散数学》PPT课件：第4章 二元关系与函数（4.5）等价关系与偏序关系

45等价关系与偏序关系 等价关系的定义与实例 等价类及其性质 商集与集合的划分 等价关系与划分的一一对应 偏序关系 偏序集与哈斯图 ■偏序集中的特定元素

1 4.5 等价关系与偏序关系 ◼ 等价关系的定义与实例 ◼ 等价类及其性质 ◼ 商集与集合的划分 ◼ 等价关系与划分的一一对应 ◼ 偏序关系 ◼ 偏序集与哈斯图 ◼ 偏序集中的特定元素

等价关系的定义与实例 定义设R为非空集合上的关系.如果R是自反的、 对称的和传递的,则称R为A上的等价关系.设R 是一个等价关系,若≮x吵>∈R,称x等价于y,记做 实例设A={1,2,,8},如下定义A上的关系R: R={|xy∈A∧x=y(mod3)} 其中x=y(mod3)叫做x与y模3相等,即x除以3的 余数与y除以3的余数相等

2 等价关系的定义与实例 定义 设 R 为非空集合上的关系. 如果 R 是自反的、 对称的和传递的, 则称 R 为 A 上的等价关系. 设 R 是一个等价关系, 若∈R, 称 x 等价于y, 记做 x～y. 实例 设 A={1,2,…,8}, 如下定义A上的关系 R： R = { | x,y∈A∧x≡y(mod 3) } 其中 x≡y(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的 余数与 y 除以3的余数相等

等价关系的验证 验证模3相等关系R为A上的等价关系,因为 Vx∈A,有x≡x(mod3) Vx,y∈A,若x≡y(mod3),则有p≡x(md3) Vx,y,z∈A,若x≡y(md3),y≡z(mod3), 则有x=mod3) 自反性、对称性、传递性得到验证

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) 自反性、对称性、传递性得到验证

A上模3等价关系的关系图 设A={1,2,,8}, R={x>xy∈AAxy(mod3)}

4 A上模3等价关系的关系图 设 A={1,2,…,8}, R={ | x,y∈A∧x≡y(mod 3) }

等价类 定义设R为非空集合A上的等价关系,Vx∈A,令 xlk={y|y∈A∧xRy} 称xl为x关于R的等价类,简称为x的等价类,简 记为x 实例A={1,2,…,8}上模3等价关系的等价类: l=4=[7}={1,4,7 「2={5=8|={2,5,8} 阝3}=6]={3,6}

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}

等价类的性质 定理1设R是非空集合A上的等价关系,则 (1)∨x∈A,风x是A的非空子集 (2)Vx,y∈A,如果xRy,则x=p (3)x,y∈A,如果xky,则与不交 (4)∪{]x∈A}=A,即所有等价类的并集就 是A

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

实例 A={1,2,…,8}上模3等价关系的等价类: =4=[7={1,4,7}, 「2|=5]=8={2,5,8}, 阝3|=6]={3,6} 以上3类两两不交, {1,4,7}U{2,5,8}{3,6}={1,2,…,8}

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}

商集 定义设R为非空集合A上的等价关系,以R的所有 等价类作为元素的集合称为A关于R的商集,记做 A/R,AR={xlk|x∈A} 实例A={1,2,…,8},A关于模3等价关系R的商集为 A/R={{1,4,7},{2,5,8},{3,6} A关于恒等关系和全域关系的商集为: EA={{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} }

集合的划分 定义设4为非空集合,若A的子集族(mP() 满足下面条件: (1)g兀 (2)xvy(xy∈兀∧ xty-xny=) (3)∪x=A 则称是A的一个划分,称中的元素为A的划分 块

9 集合的划分 定义 设A为非空集合, 若A的子集族π(πP(A)) 满足下面条件： (1) π (2) xy (x,y∈π∧x≠y→x∩y=) (3) ∪π=A 则称π是A的一个划分, 称π中的元素为A的划分 块

例题 例1设A={a,b,c,, 给定兀 192913904956 如下 兀1={{a2b,e},{t},兀2={{a,b},{c},{t 丌3={{t,{a,b,c,母},兀←={{4,b},{} 丌s={z,{u,b},{c,母},丌6={,{t},{b,c,母} 则x1和n2是4的划分,其他都不是A的划分 为什么? 10

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 的划分. 为什么？