二元关系等价关系.ppt

二元关系等价关系
第1页，本讲稿共22页
第4章 二元关系
第2页，本讲稿共22页
二元关系
(重点)
关系的运算
关系的性质 (重点)
关系的闭包
等价关 [2] = [5] = [8] ={2,5,8},
[3]= [6] = {3,6}.
第10页，本讲稿共22页
等价类
上述两例可以看出，
1. 等价关系实际上“同类关系”，是对集合按照某种性质进行的“分类” 。
2. 这种分类的特点是，各个不同类之间无共同元素，同类元素具有相同的特性，所有类的并集是原集合。
第11页，本讲稿共22页
等价类
定理 设R是非空集合A上的等价关系, 则
(1) xA, [x] ≠ 
(2) x,yA, 如果 xRy, 则 [x] = [y]
(3) x,yA, 如果 x y, 则 [x] ∩[y]= 
(4)
等价类或者完全相同，或者完全不同，其并集恰好是A
第12页，本讲稿共22页
商集
定义 商集——等价类的集合
A/R={[x]|x∈A}
性质 商集是集合的一个划分。
第13页，本讲稿共22页
集合的划分
定义 集合的划分
把集合A分为若干非空子集A1,A2 ,… ,An ,满足：
(1) 当 i ≠ j 时，Ai∩Aj＝
(2)
则子集族 = {A1，A2，…，An} 称为A的一个划分， Ai(i=1,2, ... , n)称为划分块。
A1
A6
A5
A4
A3
A2
A
第14页，本讲稿共22页
集合的划分
例4 分别给出学生集合A={a,b,c,d,e,f}根据“性别”和
“宿舍”进行的划分1 和2 。
解： 1 = { {a,d,f} , {b,c,d} } = {A1，A2},
其中A1={a,d,f}，A2={b,d,c}
2 = { {a,d} ,{f}, {b,c,d} } = {A1，A2 ，A3},
其中A1={a,d}，A2={f} ，A3={b,d,c}
a
b
c
d
e
f
性别
女
男
男
女
男
女
宿舍
1-203
2-302
2-302
1-203
2-302
1-202
第15页，本讲稿共22页
集合的划分
例5 试给出集合A={1,2,3}的所有划分。
1
2
3
1
1
2
3
5
1
2
3
2
1
2
3
4
1
2
3
3
第16页，本讲稿共22页
集合的划分与等价关系
性质
1. 等价关系对应集合的一个划分。
等价关系 → 等价类 → 商集 → 集合的划分
，这个等价关系的商集恰好是这个划分。
第17页，本讲稿共22页
集合的划分与等价关系
例6 试给出学生集合A={a,b,c,d,e,f}关于“性别”的划分所对应的等价关系R。
解：  = { {a,d,f} , {b,c,d} } = {A1，A2},
R={<x,y>|x,y同性别}
={<x,y>|x,y  A1 ∨ x,y  A2}
={<x,y>|x,y  A1} ∨{<x,y>|x,y  A2}
= A1  A1  A2  A2
a
b
c
d
e
f
性别
女
男
男
女
男
女
= ?
第18页，本讲稿共22页
集合的划分与等价关系
性质 设 = {A1，A2，…，An} 为A的一个划分， 则 所对应的等价关系R可由如下方法得到：
R={<x,y>|x,y属于的同一划分块（具有相同的性质）}
= A1× A1  A2× A2 ......  An × An
=
第19页，本讲稿共22页
小结
等价关系是“分类关系”。
集合的划分与等价关系本质上相同，可以相互导出。
(1)等价关系导出划分：等价关系→ 商集
(2)集合的划分导出等价关系：
R={<x,y>|x,y属于的同一划分块（具有相同的性质）}
=
第20页，本讲稿共22页
集合的划分与等价关系
例7 试写出集合A={1,2,3}上的所有等价关系。
解：
1. 写出所有划分：