《关系等价关系》PPT课件.ppt

1,离散数学 Discrete Mathematics,主讲：陈哲云 青岛理工大学计算机工程学院 2013.09,第4章 二元关系,二元关系,4.1二元关系基本概念 (重点) 4.2 关系的运算 4.3 关系的性质 (重点) 4.4 关系的闭包 4.5 等价关系和偏序关系 (重点及难点) 4.6 函数的基本概念,等价关系,本节内容主要说明等价关系和集合的划分(分类)之间的关系：,1.等价关系, 等价类, 商集, 集合的划分,2.集合的划分, 等价关系,等价关系,定义 等价关系： 设A上的二元关系R, 如果R是自反的, 对称的，传递的，则称R为等价关系。 若R，称x与y等价，记作xy。,等价关系,例1 数学中一些常见的等价关系： 1. 数理逻辑中的公式等值关系。 2.无向图中“点的连通”关系。 3.方程组的“同解”关系。 4.代数系统中的“同构”关系。,等价关系,例2 设集合A=1,2,3,4,5,6,7,8， R是A上的模3同余关系，请画出关系图。 1 47 2 5 8 3 6,等价类,定义 等价类把具有相同性质的元素归为一类 设R是A上的等价关系，则称 xR = y | yAx y 为x关于R的等价类。,等价类,例3 设学生集合A=a,b,c,d,e,f, R1 和 R2分别是A上的“同性别”关系和“同宿舍”关系，求所有元素关于R1和R2 的等价类，其中元素属性如下表： 解：关于R1 的等价类： 关于R2 的等价类：,等价类,练习 试写出A=1,2,3,4,5,6,7,8上关于模3同余关系的等价类。 解：1 = 4= 7= 1,4,7, 2 = 5 = 8 =2,5,8, 3= 6 = 3,6.,等价类,上述两例可以看出， 1. 等价关系实际上“同类关系”，是对集合按照某种性质进行的“分类” 。 2. 这种分类的特点是，各个不同类之间无共同元素，同类元素具有相同的特性，所有类的并集是原集合。,等价类,定理 设R是非空集合A上的等价关系, 则 (1) xA, x (2) x,yA, 如果 xRy, 则 x = y (3) x,yA, 如果 x y, 则 x y= (4),等价类或者完全相同，或者完全不同，其并集恰好是A,商集,定义 商集等价类的集合 A/R=x|xA 性质 商集是集合的一个划分。,集合的划分,定义 集合的划分 把集合A分为若干非空子集A1,A2 , ,An ,满足： (1) 当 i j 时，AiAj (2) 则子集族 = A1，A2，An 称为A的一个划分， Ai(i=1,2, . , n)称为划分块。,集合的划分,例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,集合的划分,例5 试给出集合A=1,2,3的所有划分。,集合的划分与等价关系,性质 1. 等价关系对应集合的一个划分。 等价关系 等价类 商集 集合的划分 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,= ?,集合的划分与等价关系,性质 设 = A1，A2，An 为A的一个划分， 则 所对应的等价关系R可由如下方法得到： R=|x,y属于的同一划分块（具有相同的性质） = A1 A1 A2 A2 An An =,小结,等价关系是“分类关系”。 集合的划分与等价关系本质上相同，可以相互导出。 (1)等价关系导出划分：等价关系 商集 (2)集合的划分导出等价关系： R=|x,y属于的同一划分块（具有相同的性质） =,集合的划分与等价关系,例7 试写出集合A=1,2,3上的所有等价关系。 解： 1. 写出所有划分： 2.写出每个划分对应的每个等价关系：(略),作业,1.给定集合A=1, 2, 3, 4，且A中的关系R： R =, , , , , 求包含R的最小的等价关系R*（前已求）,并写出商集A/R*。 2.给定集合S= 1 , 2 ,