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

《《关系等价关系》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《关系等价关系》PPT课件.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1离散数学离散数学Discrete Mathematics 主讲：陈哲云主讲：陈哲云青岛理工大学计算机工程学院青岛理工大学计算机工程学院2013.2013.0909第第4章章 二元关系二元关系二元关系二元关系4.1二元关系基本概念二元关系基本概念 (重点重点)4.2 关系的运算关系的运算4.3 关系的性质关系的性质 (重点重点)4.4 关系的闭包关系的闭包4.5 等价关系和偏序关系等价关系和偏序关系(重点及难点重点及难点)4.6 函数的基本概念函数的基本概念等价关系等价关系 本节内容主要说明本节内容主要说明等价关系等价关系和和集合的划分集合的划分(分类分类)之间的关系：之间的关系：1.等价关系

2、等价关系 等价类等价类 商集商集 集合的划分集合的划分2.集合的划分集合的划分 等价关系等价关系等价关系等价关系定义定义 等价关系：等价关系：设设A上上的的二二元元关关系系R,如如果果R是是自自反反的的,对对称称的的，传传递递的的，则则称称R为为等价关系等价关系。若若R，称，称x与与y等价等价，记记作作xy。等价关系等价关系例例1 数学中一些常见的等价关系：数学中一些常见的等价关系：1.数理逻辑中的数理逻辑中的公式等值公式等值关系。关系。2.无向图中无向图中“点的连通点的连通”关系。关系。3.方程组的方程组的“同解同解”关系。关系。4.代数系统中的代数系统中的“同构同构”关系。关系。等价关系等

3、价关系例例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 的的等价类，其中元素属性如下表：等价类

4、，其中元素属性如下表：解：解：关于关于R1 的等价类：的等价类：关于关于R2 的等价类：的等价类：abcdef性别性别女女男男男男女女男男女女宿舍宿舍1-2032-3022-3021-2032-3021-202等价类等价类练习练习 试写出试写出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.这种分类的特点是，各个

5、不同类之间无共同元素，同这种分类的特点是，各个不同类之间无共同元素，同类元素具有相同的特性，所有类的并集是原集合。类元素具有相同的特性，所有类的并集是原集合。等价类等价类定理定理 设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1)x A,x (2)x,y A,如果如果 xRy,则则 x=y(3)x,y A,如果如果 x y,则则 x y=(4)等价类或者完全相同，或者完全不同，其并集恰好是等价类或者完全相同，或者完全不同，其并集恰好是A商集商集定定义义 商集商集等价等价类类的集合的集合 A/R=x|xA性性质质 商集是集合的一个划分。商集是集合的一个划分。集合的划分集合的划分定定

6、义义 集合的划分集合的划分把集合把集合A分分为为若干非空子集若干非空子集A1,A2,An,满满足：足：(1)当当 i j 时时，AiAj (2)则则子子集集族族 =A1，A2，An 称称为为A的的一一个个划划分分，Ai(i=1,2,.,n)称称为为划分划分块块。A1A6A5A4A3A2A集合的划分集合的划分例例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

7、=a,d，A2=f，A3=b,d,cabcdef性别性别女女男男男男女女男男女女宿舍宿舍1-2032-3022-3021-2032-3021-202集合的划分集合的划分例例5 试给出集合试给出集合A=1,2,3的所有划分。的所有划分。1 123 31 1 123 351 123 321 123 341 123 33集合的划分与等价关系集合的划分与等价关系性质性质 1.等价关系对应集合的一个划分。等价关系对应集合的一个划分。等价关系等价关系 等价类等价类 商集商集 集合的划分集合的划分2.集合的一个划分对应着一个等价关系，这个等价关系集合的一个划分对应着一个等价关系，这个等价关系的商集恰好是这个

8、划分。的商集恰好是这个划分。集合的划分与等价关系集合的划分与等价关系例例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性别性别女女男男男男女女男男女女=?集合的划分与等价关系集合的划分与等价关系性质性质 设设 =A1，A2，An 为为A的一个划分，的一个划分，则则 所所对应对应的等价关系的等价关系R可由如下方法得到：可由如下方法得到：R=|x

9、,y属于属于 的的同一划分同一划分块块（具有相同的性具有相同的性质质）=A1 A1 A2 A2 .An An =小结小结l等价关系是等价关系是“分类关系分类关系”。l集合的划分与等价关系本质上相同，可以相互导出。集合的划分与等价关系本质上相同，可以相互导出。(1)等价关系导出划分：等价关系导出划分：等价关系等价关系 商集商集(2)集合的划分导出等价关系：集合的划分导出等价关系：R=|x,y属于属于 的的同一划分同一划分块块（具有相同的性具有相同的性质质）=集合的划分与等价关系集合的划分与等价关系例例7 试写出集合试写出集合A=1,2,3上的所有等价关系。上的所有等价关系。解：解：1.写出所有划

10、分：写出所有划分：2.写出每个划分对应的每个等价关系：写出每个划分对应的每个等价关系：(略略)1 123 31 1 123 351 123 321 123 341 123 33作业作业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，在，在A A上定义等价关系上定义等价关系R：,R x+y=u+v，求求R导出的划分导出的划分.