二元关系等价关系

1、二元关系等价关系第1页，共22页，2022年，5月20日，8点2分，星期日第4章 二元关系第2页，共22页，2022年，5月20日，8点2分，星期日二元关系4.1二元关系基本概念 (重点)4.2 关系的运算4.3 关系的性质 (重点)4.4 关系的闭包4.5 等价关系和偏序关系 (重点及难点)4.6 函数的基本概念第3页，共22页，2022年，5月20日，8点2分，星期日等价关系 本节内容主要说明等价关系和集合的划分(分类)之间的关系：1.等价关系 等价类 商集 集合的划分2.集合的划分 等价关系第4页，共22页，2022年，5月20日，8点2分，星期日等价关系定义 等价关系：设A上的二元关系

2、R, 如果R是自反的, 对称的，传递的，则称R为等价关系。若R，称x与y等价，记作xy。第5页，共22页，2022年，5月20日，8点2分，星期日等价关系例1 数学中一些常见的等价关系：1. 数理逻辑中的公式等值关系。2.无向图中“点的连通”关系。3.方程组的“同解”关系。4.代数系统中的“同构”关系。第6页，共22页，2022年，5月20日，8点2分，星期日等价关系例2 设集合A=1,2,3,4,5,6,7,8， R是A上的模3同余关系，请画出关系图。 1 47 2 5 8 3 6第7页，共22页，2022年，5月20日，8点2分，星期日等价类定义 等价类把具有相同性质的元素归为一类设R是A

3、上的等价关系，则称 xR = y | yAx y 为x关于R的等价类。 第8页，共22页，2022年，5月20日，8点2分，星期日等价类例3 设学生集合A=a,b,c,d,e,f, R1 和 R2分别是A上的“同性别”关系和“同宿舍”关系，求所有元素关于R1和R2 的等价类，其中元素属性如下表：解：关于R1 的等价类： 关于R2 的等价类：abcdef性别女男男女男女宿舍1-2032-3022-3021-2032-3021-202第9页，共22页，2022年，5月20日，8点2分，星期日等价类练习 试写出A=1,2,3,4,5,6,7,8上关于模3同余关系的等价类。解：1 = 4= 7= 1,

4、4,7, 2 = 5 = 8 =2,5,8, 3= 6 = 3,6.第10页，共22页，2022年，5月20日，8点2分，星期日等价类上述两例可以看出，1. 等价关系实际上“同类关系”，是对集合按照某种性质进行的“分类” 。2. 这种分类的特点是，各个不同类之间无共同元素，同类元素具有相同的特性，所有类的并集是原集合。第11页，共22页，2022年，5月20日，8点2分，星期日等价类定理 设R是非空集合A上的等价关系, 则(1) xA, x (2) x,yA, 如果 xRy, 则 x = y(3) x,yA, 如果 x y, 则 x y= (4)等价类或者完全相同，或者完全不同，其并集恰好是A

5、第12页，共22页，2022年，5月20日，8点2分，星期日商集定义 商集等价类的集合 A/R=x|xA性质 商集是集合的一个划分。第13页，共22页，2022年，5月20日，8点2分，星期日集合的划分定义 集合的划分把集合A分为若干非空子集A1,A2 , ,An ,满足： (1) 当 i j 时，AiAj (2) 则子集族 = A1，A2，An 称为A的一个划分， Ai(i=1,2, . , n)称为划分块。A1A6A5A4A3A2A第14页，共22页，2022年，5月20日，8点2分，星期日集合的划分例4 分别给出学生集合A=a,b,c,d,e,f根据“性别”和“宿舍”进行的划分1 和2

6、。解： 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,cabcdef性别女男男女男女宿舍1-2032-3022-3021-2032-3021-202第15页，共22页，2022年，5月20日，8点2分，星期日集合的划分例5 试给出集合A=1,2,3的所有划分。1231 1235123212341233第16页，共22页，2022年，5月20日，8点2分，星期日集合的划分与等价关系性质 1. 等价关系对应集合的一个划分。 等价关系 等价类 商集

7、 集合的划分2.集合的一个划分对应着一个等价关系，这个等价关系的商集恰好是这个划分。第17页，共22页，2022年，5月20日，8点2分，星期日集合的划分与等价关系例6 试给出学生集合A=a,b,c,d,e,f关于“性别”的划分所对应的等价关系R。解： = a,d,f , b,c,d = A1，A2, R=|x,y同性别 =|x,y A1 x,y A2 =|x,y A1 |x,y A2 = A1 A1 A2 A2 abcdef性别女男男女男女 = ?第18页，共22页，2022年，5月20日，8点2分，星期日集合的划分与等价关系性质 设 = A1，A2，An 为A的一个划分， 则 所对应的等价

8、关系R可由如下方法得到：R=|x,y属于的同一划分块（具有相同的性质） = A1 A1 A2 A2 . An An = 第19页，共22页，2022年，5月20日，8点2分，星期日小结等价关系是“分类关系”。集合的划分与等价关系本质上相同，可以相互导出。(1)等价关系导出划分：等价关系 商集(2)集合的划分导出等价关系： R=|x,y属于的同一划分块（具有相同的性质） = 第20页，共22页，2022年，5月20日，8点2分，星期日集合的划分与等价关系例7 试写出集合A=1,2,3上的所有等价关系。解： 1. 写出所有划分：2.写出每个划分对应的每个等价关系：(略)1231 1235123212341233第21页，共22页，2022年，5月20日，8点2分，星期日作业1.给定集合A=1, 2, 3, 4，且A中的关系R：R =, , , , , 求包含R的最小的等价关系R*（前已求）,并写出商集A/R*。2.给定集合S= 1