二元关系等价关系PPT讲稿.ppt

二元关系等价关系二元关系等价关系第1页，共22页，编辑于2022年，星期四第第4章章 二元关系二元关系第2页，共22页，编辑于2022年，星期四二元关系二元关系l4.1二元关系基本概念二元关系基本概念 (重点重点)l4.2 关系的运算关系的运算l4.3 关系的性质关系的性质 (重点重点)l4.4 关系的闭包关系的闭包l4.5 等价关系和偏序关系等价关系和偏序关系(重点及难点重点及难点)l4.6 函数的基本概念函数的基本概念第3页，共22页，编辑于2022年，星期四等价关系等价关系 本节内容主要说明本节内容主要说明等价关系等价关系和和集合的划分集合的划分(分类分类)之间之间的关系：的关系：1.等价关系等价关系 等价类等价类 商集商集 集合的划分集合的划分2.集合的划分集合的划分 等价关系等价关系第4页，共22页，编辑于2022年，星期四等价关系等价关系定义定义 等价关系：等价关系：设设A上上的的二二元元关关系系R,如如果果R是是自自反反的的,对对称称的的，传传递递的的，则则称称R为为等价关系等价关系。若若R，称，称x与与y等价等价，记记作作xy。第5页，共22页，编辑于2022年，星期四等价关系等价关系例例1 数学中一些常见的等价关系：数学中一些常见的等价关系：1.数理逻辑中的数理逻辑中的公式等值公式等值关系。关系。2.无向图中无向图中“点的连通点的连通”关系。关系。3.方程组的方程组的“同解同解”关系。关系。4.代数系统中的代数系统中的“同构同构”关系。关系。第6页，共22页，编辑于2022年，星期四等价关系等价关系例例2 设集合设集合A=1,2,3,4,5,6,7,8，R是是A上的上的模模3同余同余关系，请关系，请画出关系图。画出关系图。1 47 2 5 8 3 6第7页，共22页，编辑于2022年，星期四等价类等价类定定义义 等价等价类类把具有相同性把具有相同性质质的元素的元素归为归为一一类类设设R是是A上的等价关系，则称上的等价关系，则称 xR=y|yAx y 为为x关于关于R的等价类。的等价类。第8页，共22页，编辑于2022年，星期四等价类等价类例例3 设学生集合设学生集合A=a,b,c,d,e,f,R1 和和 R2分别是分别是A上的上的“同性别同性别”关关系和系和“同宿舍同宿舍”关系，求所有元素关于关系，求所有元素关于R1和和R2 的等价类，其中的等价类，其中元素属性如下表：元素属性如下表：解：解：关于关于R1 的等价类：的等价类：关于关于R2 的等价类：的等价类：abcdef性别女男男女男女宿舍1-2032-302 2-302 1-2032-3021-202第9页，共22页，编辑于2022年，星期四等价类等价类练习练习 试写出试写出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.第10页，共22页，编辑于2022年，星期四等价类等价类上述两例可以看出，上述两例可以看出，1.等价关系实际上等价关系实际上“同类关系同类关系”，是对集合按照某种性质进行，是对集合按照某种性质进行的的“分类分类”。2.这种分类的特点是，各个不同类之间无共同元素，同类元素这种分类的特点是，各个不同类之间无共同元素，同类元素具有相同的特性，所有类的并集是原集合。具有相同的特性，所有类的并集是原集合。第11页，共22页，编辑于2022年，星期四等价类等价类定理定理 设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1)x A,x (2)x,y A,如果如果 xRy,则则 x=y(3)x,y A,如果如果 x y,则则 x y=(4)等价类或者完全相同，或者完全不同，其并集恰好是等价类或者完全相同，或者完全不同，其并集恰好是A第12页，共22页，编辑于2022年，星期四商集商集定定义义 商集商集等价等价类类的集合的集合 A/R=x|xA性性质质 商集是集合的一个划分。商集是集合的一个划分。第13页，共22页，编辑于2022年，星期四集合的划分集合的划分定定义义 集合的划分集合的划分把集合把集合A分分为为若干非空子集若干非空子集A1,A2,An,满满足：足：(1)当当 i j 时时，AiAj (2)则则子子集集族族 =A1，A2，An 称称为为A的的一一个个划划分分，Ai(i=1,2,.,n)称称为为划分划分块块。A1A6A5A4A3A2A第14页，共22页，编辑于2022年，星期四集合的划分集合的划分例例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,cabcdef性别女男男女男女宿舍1-2032-302 2-302 1-2032-3021-202第15页，共22页，编辑于2022年，星期四集合的划分集合的划分例例5 试给出集合试给出集合A=1,2,3的所有划分。的所有划分。1 123 31 1 123 351 123 321 123 341 123 33第16页，共22页，编辑于2022年，星期四集合的划分与等价关系集合的划分与等价关系性质性质 1.等价关系对应集合的一个划分。等价关系对应集合的一个划分。等价关系等价关系 等价类等价类 商集商集 集合的划分集合的划分2.集合的一个划分对应着一个等价关系，这个等价关系的商集集合的一个划分对应着一个等价关系，这个等价关系的商集恰好是这个划分。恰好是这个划分。第17页，共22页，编辑于2022年，星期四集合的划分与等价关系集合的划分与等价关系例例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性别女男男女男女=?第18页，共22页，编辑于2022年，星期四集合的划分与等价关系集合的划分与等价关系性质性质 设设 =A1，A2，An 为为A的一个划分，的一个划分，则则 所所对应对应的等价关系的等价关系R可由如下方法得到：可由如下方法得到：R=|x,y属于属于 的的同一划分同一划分块块（具有相同的性具有相同的性质质）=A1 A1 A2 A2 .An An =第19页，共22页，编辑于2022年，星期四小结小结l等价关系是等价关系是“分类关系分类关系”。l集合的划分与等价关系本质上相同，可以相互导出。集合的划分与等价关系本质上相同，可以相互导出。(1)等价关系导出划分：等价关系导出划分：等价关系等价关系 商集商集(2)集合的划分导出等价关系：集合的划分导出等价关系：R=|x,y属于属于 的的同一划分同一划分块块（具有相同的性具有相同的性质质）=第20页，共22页，编辑于2022年，星期四集合的划分与等价关系集合的划分与等价关系例例7 试写出集合试写出集合A=1,2,3上的所有等价关系。上的所有等价关系。解：解：1.写出所有划分：写出所有划分：2.写出每个划分对应的每个等价关系：写出每个划分对应的每个等价关系：(略略)1 123 31 1 123 351 123 321 123 341 123 33第21页，共22页，编辑于2022年，星期四作业作业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导出的划分导出的划分.第22页，共22页，编辑于2022年，星期四