《离散数学课件》6等价关系

1、二元关系的性质与闭包（7.3-7.4）,性质 自反性、反自反性 对称性、反对称性 传递性 闭包 自反闭包r(R) 对称闭包s(R) 传递闭包t(R),1,2/49,特 点,3/55,7.5.1 等价关系与等价类 7.5.2 商集合 7.5.3 集合的划分,7.5 等价关系和集合的划分,4/55,例 试画出关系图,A=1,2,3,4,5,6,7,8 R=(x,y) x,y A, xy(mod 3) 其中xy(mod 3)的含义就是x-y可以被3整除.,5/55,等价关系,定义1 A是一个非空集, R是A上的一个二元关系， 若R有自反性、 对称性、 传递性， 则说R是A上的等价关系。,设 R 是一

2、个等价关系, 若R, 称 x 等价于y, 记做 xy.,6/55,例（1）人类集合中的“同龄”、 “同乡”关系都是 等价关系。 （2） 三角形集合的相似关系、 全等关系都是 等价关系。 （3） 住校学生的同寝室关系是等价关系。 （4）命题公式间的逻辑等价关系是等价关系。 （5） 对任意集合A， A上的恒等关系IA和全域关 系EA是等价关系。,7/55,例3 (p106) Z是整数集，在Z上定义一个二元关系R：对于任意的 x,yZ, (x,y) R当且仅当x与y被5除余数相同。R是Z上的等价关系。,显然, x与y被5除同余的充要条件是5|(x-y), 这里符号a|b表示a整除b，a与b是两个整数

3、。 对于 xZ，有5|(x-x), 即(x,x) R，亦即R有自反性。 对于 x,yZ，若(x,y) R, 即5|(x-y)， 也即5|(y-x), 所以(y,x) R， 亦即R有对称性。 对于 x,y,zZ，若(x,y) R, 且(y,z) R， 即5|(x-y)，且5|(z-y)，则 5|(x-y)+(y-z)， 亦即5|(x-z)，所以(x,z) R，亦即R有传递性。 故R是A上的等价关系。,8/55,例设A=1,2,3,并设是AA上的关系，其定义为：若ad=bc， 则(a,b) (c,d)。证明 是一个等价关系。,证： (1) 自反性 对于(a,b)AA, 因为ab=ba， 则有(a,

4、b) (a,b) 。 (2) 对称性 如果(a,b) (c,d)，即有 ad=bc， 即有 cb=da， 故有(c,d) (a,b)。 (3) 传递性 如果(a,b) (c,d)，(c,d) (e,f)， 即有 ad=bc, cf=de, 于是有 adcf=bcde 即 af=be, 故有 (a,b)(e,f),9/55,等价类、代表元,若R是A上的等价关系， a是A中任意一个元素， 集合 xA(x,a) R 称为集合A关于关系R的一个等价类，记 aR= xA(x,a) R, 简记a 其中a叫代表元。,10/55,例1,A=1,2,3, R=(1,1), (2,2), (3,3), (1,2)

5、, (2,1) 则R是A上一个等价关系。,显然 1R1,2 2R1,2 3R3,1 2 3,11/55,例2 A= 1, 2, , 8 上模 3 等价关系的等价类：,1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,12/55,定理1(p107) 等价类的性质,A是一个非空集合，R是A上的一个等价关系，则有 (1) xR=A， (2) 对于任意的x,yA， 若xRyR，则xR=yR。,xA,13/55,定理1 证明 若xRyR，则xR=yR,证明(2): 对于任意的x,y A，若xRyR， 则存在axRyR。 由axR，得(a,x)R； 再由R的对称性，有(x,a) R。 由ay

6、R, 有(a,y) R。 利用R的传递性，得(x,y)R。 下面开始证明xR=yR。 对于任意的z xR，有(z,x) R, 又因为刚才已得到(x,y) R， 由R的传递性，得到(z,y) R, 所以有z yR。从而证得 xRyR。 同理可证yRxR。 所以最后得到xR=yR。,14/55,定理1,A是一个非空集合，R是A上的一个等价关系，则有 (1) xR=A， (2) 对于任意的x,yA，若xRyR， 则xR=yR。 (3) xR, 且xRA. (4) 若xRy, 则xR=yR. (5) 若xRy, 则xRyR=,xA,15/55,商集合,定义2 A是一个非空集合，R是A上的一个等价关系，

7、集合xRxA 叫集合A的商集合，记为 A/R= xRxA,16/55,例 Z是整数集，在Z上定义一个二元关系R： 对于任意的 x,yZ, (x,y) R 当且仅当x与y被5除余数相同。 则 Z/R= 0R, 1R, 2R, 3R, 4R,0R=xZnZ, x=5n 1R=xZnZ, x=5n+1 2R=xZnZ, x=5n+2 3R=xZnZ, x=5n+3 4R=xZnZ, x=5n+4,17/55,例 A=1,2,3,4,5,6,7,8 R=(x,y) x,y A, xy(mod 3),A/R=1R, 2R, 3R,= 1,4,7, 2,5,8, 3,6 ,A关于恒等关系和全域关系的商集为

8、： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 ,18/55,集合的划分,B,定义3 设A为非空集合, 若A的子集族(P(A) 满足下面条件： (1) (2) xy (x,yxyxy=) (3) =A 则称是A的一个划分, 称中的元素为A的划分块.,19/55,例1 设Aa, 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 的划分.,(1) (2)

9、 xy (x,yxyxy=)(3) =A,20/55,集合的划分等价关系,若给定集合A上的一个划分， 可以在A上定义一个二元关系R， 使得R成为A上的一个等价关系，且有 A/R ,21/55,解: R=(a,a), (b,b), (c,c), (b,c),(c,b),(d,d) 求其等价类 a=a, b=c=b,c, d=d 商集A/R=a,b,c =a,b,c,d,例：考虑集合A=a,b,c,d的一个划分: a, b,c, d 求该划分所对应的等价关系.,例：给出A1,2,3上所有的等价关系,22,1 对应等价关系 R1 =,IA 2 对应等价关系 R2=,IA3 对应等价关系 R3=,IA,4 对应于全域关系 EA，5 对应于恒等关系 IA,实例,23,例3 设 A=1, 2, 3, 4，在 AA上定义二元关系R： ,R x+y = u+v， 求 R 导出的划分.,解 AA=, , , ,