二元关系4.5等价关系.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,3,4,5,找出S上的等价关系R，此关系R能够产生划分1,2,3,4,5，并画出关系图。3.设A=1,2,3,4，在AA上定义等价关系R：,R x+y=u+v，求R导出的划分.,