二元关系4.5等价关系.ppt
《二元关系4.5等价关系.ppt》由会员分享,可在线阅读,更多相关《二元关系4.5等价关系.ppt(22页珍藏版)》请在装配图网上搜索。
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等价,记作xy。,等价关系,例1数学中一些常见的等价关系:1.数理逻辑中的公式等值关系。2.无向图中“点的连通”关系。3.方程组的“同解”关系。4.代数系统中的“同构”关系。,等价关系,例2设集合A=1,2,3,4,5,6,7,8,R是A上的模3同余关系,请画出关系图。14725836,等价类,定义等价类把具有相同性质的元素归为一类设R是A上的等价关系,则称xR=y|yAxy为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,如果xy,则xy=(4),等价类或者完全相同,或者完全不同,其并集恰好是A,商集,定义商集等价类的集合A/R=x|xA性质商集是集合的一个划分。,集合的划分,定义集合的划分把集合A分为若干非空子集A1,A2,An,满足:(1)当ij时,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,c2=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,yA1x,yA2=|x,yA1|x,yA2=A1A1A2A2,=?,集合的划分与等价关系,性质设=A1,A2,An为A的一个划分,则所对应的等价关系R可由如下方法得到:R=|x,y属于的同一划分块(具有相同的性质)=A1A1A2A2.AnAn=,小结,等价关系是“分类关系”。集合的划分与等价关系本质上相同,可以相互导出。(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:,Rx+y=u+v,求R导出的划分.,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二元关系 4.5 等价 关系
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文