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

《《关系等价关系》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1离散数学DiscreteMathematics主讲：陈哲云青岛理工大学计算机工程学院2013.09第4章二元关系二元关系4.1二元关系基本概念(重点)4.2关系的运算4.3关系的性质(重点)4.4关系的闭包4.5等价关系和偏序关系(重点及难点)4.6函数的基本概念等价关系本节内容主要说明等价关系和集合的划分(分类)之间的关系：1.等价关系→等价类→商集→集合的划分2.集合的划分→等价关系等价关系定义等价关系：设A上的二元关系R,如果R是自反的,对称的，传递的，则称R为等价关系。若∈R，称x与y等价，记作x～

2、y。等价关系例1数学中一些常见的等价关系：1.数理逻辑中的公式等值关系。2.无向图中“点的连通”关系。3.方程组的“同解”关系。4.代数系统中的“同构”关系。等价关系例2设集合A={1,2,3,4,5,6,7,8}，R是A上的模3同余关系，请画出关系图。1～4～72～5～83～6等价类定义等价类——把具有相同性质的元素归为一类设R是A上的等价关系，则称[x]R={y

3、y∈A∧x～y}为x关于R的等价类。等价类例3设学生集合A={a,b,c,d,e,f},R1和R2分别是A上的“同性别”关系和“同宿舍”关系，求所有元素关

4、于R1和R2的等价类，其中元素属性如下表：解：关于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,如果xy,则[x]∩[y]=(4)等价类或者完全相同，或者完全不同，其并集恰好是A商集定义商集——等价类的集合A/R={[x]

6、x∈A}性质商集是集合的一个划分。集合的划分定义集合的划分把集合A分为若干非空子集A1,A2,…,An,满足：(1)当i≠j时，Ai∩Aj＝(2)则子集族={A1，A2，…，An}称为A的一个划分，Ai(i=1,2,...,

7、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={a,d}，A2={f}，A3={b,d,c}abcdef性别女男男女男女宿舍1-2032-3022-3021-2032-3021-202集合的划分例5试给出集合A={1,2,3}的所有划分。

8、12311235123212341233集合的划分与等价关系性质1.等价关系对应集合的一个划分。等价关系→等价类→商集→集合的划分2.集合的一个划分对应着一个等价关系，这个等价关系的商集恰好是这个划分。集合的划分与等价关系例6试给出学生集合A={a,b,c,d,e,f}关于“性别”的划分所对应的等价关系R。解：={{a,d,f},{b,c,d}}={A1，A2},R={

9、x,y同性别}={

10、x,yA1∨x,yA2}={

11、x,yA1}∨{

12、x,yA2}=A1A

13、1A2A2abcdef性别女男男女男女=?集合的划分与等价关系性质设={A1，A2，…，An}为A的一个划分，则所对应的等价关系R可由如下方法得到：R={

14、x,y属于的同一划分块（具有相同的性质）}=A1×A1A2×A2......An×An=小结等价关系是“分类关系”。集合的划分与等价关系本质上相同，可以相互导出。(1)等价关系导出划分：等价关系→商集(2)集合的划分导出等价关系：R={

15、x,y属于的同一划分块（具有相同的性质）}=集合的划分与等价关系例7试写出集合A={1,

16、2,3}上的所有等价关系。解：1.写出所有划分：2.写出每个划分对应的每个等价关系：(略)12311235123212341233作业1.给定集合A={1,2,3,4}，且A中的关系R：R={<1,1>,<1,3>,<2,2>,<3,4>,<4,1>,<4,4>}求包含R的最小的等价关系R*（前已求）,并写出商集A/R*