[1]R=[4]R=[7]R={1,4,7} [2]R=[5]R=[8]R={2,5,8} [3]R=[6]R={3,6}
精选ppt
15
定义3:集合A上的等价关系R，其等价类集 合{[a]R|a ∈ A}称作A关于R的商集
(quotient set) 。记作A/R
精选ppt
16
二、性质
(1) a ∈[a]R
(2)定理1:设给定集合A上的等价关系R， 对于a,b∈A，若<a,b>∈R,iff [a]R=[b]R。
精选ppt
17
(3)设R为集合A上的等价关系，则任意
a,b ∈ A,若<a,b> R,则
aR bR
4 a A aA R
精选ppt
18
三 商集与集合的划分
定理2：集合A上的等价关系R，决定了A的一
精选ppt
3
传递性（ transitive ）
定义:设R为定义在集合A上的二元关系， 如果对于任意x，y，z∈A， 每当<x,y> ∈ R且<y,z> ∈R，就有 <x,z> ∈ R，称关系R在A上是传递的。
精选ppt
4
R 1 { a,a , a, b , b,a , c,c }
1 1 0 MR 1 1 0 0
3-10 等价关系与等价类
离散数学
精选ppt
1
复习
自反性（ reflexive ）
定义：设R为定义在集合A上的二元关系，如果 对于每个x∈A，都有<x,x>∈R,即xRx，则称
二元关系R是自反的。
精选ppt
2
对称性（ symmetric ）
定义：设R为定义在集合A上的二元关系，如果 对于每个x，y∈A，每当<x,y>∈R，就有 <y,x>∈R，则称集合A上关系R是对称的。
精选ppt
11
例2 设A = { 1, 2, …, 8 }, 如下定义A 上的关系R:
R = { <x, y> | x, yA且x≡y（mod3) }
证明R为A上的等价关系。
证明:
xA , 因为x-x=0=0×3,所以
<x,x>∈R;
x,yA, 若x-y=3t(t为整数）, 则有:
y-x=-3t,即 <y,x>∈R;
所以A/R是A上对应于R的一个划精分选p。pt
19
定理3 集合A的一个划分确定A的元素间 的一个等价关系。
证明：
设集合A的一个划分S＝｛S1,S2…Sm｝，现定义一个关系： aRb当且仅当a,b在同一个分块中。则R是一个等价关系。
①、a与a在同一个分块中，则有aRa ，即自反性
②、 a与b在同一个分块中，则b与a在同一个分块中，即若aRb， 有bRa，故R是对称的。
③、 a与b在同一个分块中， b与c在同一个分块中，而由划分的 定义b只能属于且属于一个分块，故a与c必在同一分块中，即若 有aRb,bRc则必有aRc，即传递性成立。
所以R是一个等价关系。S＝A/R
精选ppt
20
说明
等价关系—— 等价类 —— 商集 —— 划分
A上的等价关系与A的划分是一一对应的。
R＝｛＜1，1＞，＜1，4＞，＜4，1＞， ＜4，4＞，＜2，2＞，＜2，3＞， ＜3，2＞，＜3，3＞｝。
验证R是集合T上的等价关系。
精选ppt
10
1001 0110 MR 0 1 1 0 1001
10011001 1001 01100110 0110 MR2 0 1 1 0 0 1 1 0 0 1 1 0 10011001 1001
精选ppt
21
例3 A={a,b,c,d,e}， S＝{{a,b},{c},{d,e}}，求由S确定的R。
R1＝{a,b}x{a,b}={<a,a><b,b><a,b><b,a>} R2={c} x{c}={<c,c>} R3= {d,e}x{d,e}={<d,d><e,e><d,e><e,d>} R=R1∪R2∪R3
0 0 1
a cb
R1
R1 是对称的。
精选ppt
5
R 2 { a, a , a, b , b, a , b, b , c, c }
1 1 0
a
MR 2 1 1 0
0 0 1
cb
R2
R2 是自反的、对称的、传递的。
精选ppt
6
主要内容
1
等价关系与等价类的基本概念
2
等价关系的基本性质
3
商集与集合的划分
精选ppt
22
例4设A={a,b,c,d,e},R={〈a,a〉,〈a,b〉, 〈a,c〉,〈b,b〉,〈b,a〉,〈b,c〉,〈c,c〉,〈c,a〉, 〈c,b〉,〈d,d〉,〈d,e〉,〈e,e〉,〈e,d〉},其有 向图如图所示,
则R诱导的划分 S={{a,b,c},{d,e}}.反之,若 A的划分S={{a,b,c},{d,e}}, 则所诱导的等价关系 R={a,b,c}×{a,b,c}∪{d,e }×{d,e}={〈a,a〉, 〈a,b〉,〈a,c〉,〈b,b〉, 〈b,a〉,〈b,c〉,〈c,c〉, 〈c,a〉,〈c,b〉,〈d,d〉, 〈d,e〉,〈e,e〉,〈e,d〉}
精选ppt
7
一、定义
定义1:设R为定义在集合A上的一个关系，若 R是自反的，对称的和传递的，则称R为集 合A上的等价关系。
精选ppt
8
例如
平面上三角形集合中，三角形的相似关 系；
同学集合A={a,b,c,d,e,f,g},A中的关系 R：住在同一宿舍；
3，4｝，
精选ppt
23
定理4：设R1和R2为非空集合A上的等价 关系，则R1=R2当且仅当A/R1=A/R2。
x,y,zA, 若x-y=3t, y-z=3s, 则有:
x-z=3(t+s),即<x,z> ∈R.
精选ppt
12
关系图如下图所示.
精选ppt
13
等价类
定义2：设R为集合A上的等价关系，对任意a∈A， 集合 [a]R={x|x ∈ A,<a,x>∈R} 称为元素a关于R的等价类。
精选ppt
14
例2可求出三个不同的等价类
个划分，该划分就是商集A/R。
证明 设集合A上的一个等价关系R，则[a]R是A的一个子集， 则所有这样的子集可做成商集A/R
1、A/R={[a]R|a ∈A}中, ∪[a]R=A
2、 对任意a ∈A，都有aRa，即a∈[a]R，即A中的每一个 元素都属于一个分块。
3、A的每个元素只能属于一个分块
反证设a∈[b]R ，a∈[c]R,且[b]R ≠ [c]R，则bRa,cRa成立， 所以有aRc,所以bRc，即[b]R ＝ [c]R