(33)--3.8 等价关系离散数学离散数学.ppt

等价关系例：例：设设A=1,2,10，对于对于A上的关系上的关系 R=|(x y)/3 Z 若若 等价关系等价关系R，则记作，则记作x y。等价关系：等价关系：A上的关系上的关系R是是自反自反的、的、对称对称的和的和传递传递的，的，则称则称R为等价关系。为等价关系。由由R具有自反性具有自反性、对称性和传递性，知、对称性和传递性，知R是等价关系，是等价关系，且且1 4 7 10，2 5 8，3 6 9等价关系的概念例如例如：(1)集合上的恒等关系。集合上的恒等关系。(2)全域关系是等价关系。全域关系是等价关系。(3)三角形的全等关系，三角形的相似关系是等价关系。三角形的全等关系，三角形的相似关系是等价关系。(4)在一个班级里在一个班级里“年龄相等年龄相等”的关系是等价关系。的关系是等价关系。等价关系的概念等价类：等价类：设设R是是A上的等价关系，对任意上的等价关系，对任意x A，令令xR=y|y A xRy,则称则称xR为为x关于关于R的等价类。的等价类。简称为简称为x的等价类。简记为的等价类。简记为x于是如上例有于是如上例有 1=4=7=10=1,4,7,10,2=5=8=2,5,8,3=6=9=3,6,9等价关系的概念例例：设：设A=a,b,c,d,e,f,A上的关系上的关系 R=,IA 求出中各元素的等价类。求出中各元素的等价类。解解:是上的等价关系，是上的等价关系，a=b=f=a,b,f,c=d=c,d,e=e.等价关系的概念集合集合A的划分：的划分：设设A是非空集合，是非空集合，A1,A2,Am,(Ai,i=1,2,m)是它是它的子集，满足：的子集，满足：(1)Ai Aj=(i j)；(2)A1 A2 Am=A；则称则称 =A1,A2,Am 为为A的一个划分，的一个划分，且称且称A1,A2,Am为划分块。为划分块。等价关系与划分集合集合A在等价关系在等价关系R下的商集：下的商集：设设R是是A上的等价关系，以上的等价关系，以R的不交的等价类的不交的等价类 为元素的集合叫作为元素的集合叫作A在在R下的商集，记作下的商集，记作A R，即即A R=xR|x A 于是上例中于是上例中A R=1,4,7,10,2,5,8,3,6,9 等价关系与划分集合集合集合集合AA上的等价关系与上的等价关系与上的等价关系与上的等价关系与AA的划分是一一对应的。的划分是一一对应的。的划分是一一对应的。的划分是一一对应的。n对于对于A上给定的任意划分上给定的任意划分 ，定义，定义A上二元关系上二元关系R为：对为：对任何元素任何元素x，y A，若，若x和和y在同一划分块中，则在同一划分块中，则xRy。于是于是R是是A上的等价关系，称为由划分上的等价关系，称为由划分 所诱导的等价所诱导的等价关系，且商集关系，且商集A R就等于就等于 。nA在等价关系在等价关系R下的商集下的商集A R是是A的一个划分，的一个划分，称为：称为：由由R所诱导的划分所诱导的划分等价关系与划分例例：设：设A=1,2,3，求出，求出A上所有的等价关系。上所有的等价关系。解解：先求：先求A 的各种划分：只有的各种划分：只有1个划分块的划分个划分块的划分 1，具有具有2个划分块的划分个划分块的划分 2,3,4，具有具有3个划分块的划分个划分块的划分 5。于是于是 1=1,2,3，2=1,2,3，3=1,3,2，4=1,2,3，5=1,2,3 等价关系与划分例例：设：设A=1,2,3，求出，求出A上所有的等价关系。上所有的等价关系。R1=,设对应于划分设对应于划分 i 的等价关系为的等价关系为Ri，则有，则有R2=,R3=,R4=,R5=,THANK YOU