《离散数学-2-4-1(等价关系)[2014-10-13].ppt》由会员分享，可在线阅读，更多相关《离散数学-2-4-1(等价关系)[2014-10-13].ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学离散数学-2-4-1(等价等价关系关系)2014-10-132.4 特殊关系特殊关系o关系可能具有的性质：关系可能具有的性质：关系可能具有的性质：关系可能具有的性质：n n自反自反自反自反n n反自反反自反反自反反自反n n对称对称对称对称n n反对称反对称反对称反对称n n传递传递传递传递o特殊关系：具有上述某些性质的关系特殊关系：具有上述某些性质的关系特殊关系：具有上述某些性质的关系特殊关系：具有上述某些性质的关系n n等价关系等价关系等价关系等价关系：自反、对称、传递：自反、对称、传递：自反、对称、传递：自反、对称、传递n n偏序关系偏序关系偏序关系偏序关系：自反、反对称、传递：
2、自反、反对称、传递：自反、反对称、传递：自反、反对称、传递2.4.1 等价关系等价关系定义定义定义定义2.212.21 oo设设设设R R为非空集合为非空集合为非空集合为非空集合A A上的关系（即上的关系（即上的关系（即上的关系（即A A 并且并且并且并且R R A A A A）。）。）。）。如果如果如果如果R R是是是是自反的自反的自反的自反的、对称的对称的对称的对称的和和和和传递的传递的传递的传递的，则称则称则称则称R R为为为为A A上的上的上的上的等价关系等价关系等价关系等价关系。oo设设设设 R R 是一个等价关系。是一个等价关系。是一个等价关系。是一个等价关系。如果如果如果如果 R
3、 R,则称则称则称则称 x x与与与与y y等价等价等价等价.例例2.50判断下列关系是否判断下列关系是否判断下列关系是否判断下列关系是否为为为为等价关系等价关系等价关系等价关系 n nRR1 1:选修离散数学课程同学中的选修离散数学课程同学中的选修离散数学课程同学中的选修离散数学课程同学中的“同班同班同班同班”关系关系关系关系 n nRR2 2:幂集上的幂集上的幂集上的幂集上的“”关系关系关系关系 n nRR3 3:直线间的直线间的直线间的直线间的“平行平行平行平行”关系关系关系关系 n nR4:R4:整数集上的整数集上的整数集上的整数集上的“”关系关系关系关系 n nR5:R5:人群中的人
4、群中的人群中的人群中的“朋友朋友朋友朋友”关系关系关系关系 自反自反对称对称传递传递等价关系等价关系R1R2R3R4R5 例例2.52给定一个正整数给定一个正整数给定一个正整数给定一个正整数nn，考虑整数集合，考虑整数集合，考虑整数集合，考虑整数集合Z Z上的整除关系上的整除关系上的整除关系上的整除关系R=|xR=|x Z Z，y y Z Z，(x(x y)y)被被被被n n整除整除整除整除。证明证明证明证明R R是是是是Z Z上的等价关系。上的等价关系。上的等价关系。上的等价关系。证明证明证明证明:（1 1 1 1）因此，因此，因此，因此，R R R R是自反的。是自反的。是自反的。是自反的
5、。（2 2 2 2）因此，因此，因此，因此，R R R R是对称的。是对称的。是对称的。是对称的。（3 3 3 3）因此，因此，因此，因此，R R R R是传递的。是传递的。是传递的。是传递的。综上，关系综上，关系综上，关系综上，关系R R R R为为为为Z Z Z Z上的等价关系。证毕。上的等价关系。证毕。上的等价关系。证毕。上的等价关系。证毕。oox x y(modn)y(modn)：x-yx-y可以被可以被可以被可以被 n n整除，整除，整除，整除，“x x和和和和y y模模模模n n同余同余同余同余”。oo同余关系同余关系同余关系同余关系例例2.53设集合设集合设集合设集合A=a,b,
6、c,d,eA=a,b,c,d,e上的关系上的关系上的关系上的关系R1=,R1=,和和和和R2=,R2=,，判断判断判断判断R1R1和和和和R2R2是否为等价关系？是否为等价关系？是否为等价关系？是否为等价关系？用关系矩阵和关系图表示其中的等价关系。用关系矩阵和关系图表示其中的等价关系。用关系矩阵和关系图表示其中的等价关系。用关系矩阵和关系图表示其中的等价关系。解解解解:R1R1R1R1具有自反性、对称性和传递性，是等价关系。具有自反性、对称性和传递性，是等价关系。具有自反性、对称性和传递性，是等价关系。具有自反性、对称性和传递性，是等价关系。R2R2R2R2不是等价关系。不是等价关系。不是等价
7、关系。不是等价关系。例例2.53(续续)设集合设集合设集合设集合A=a,b,c,d,eA=a,b,c,d,e上的关系上的关系上的关系上的关系R1=,R1=,和和和和R2=,R2=,，判断判断判断判断R1R1和和和和R2R2是否为等价关系？是否为等价关系？是否为等价关系？是否为等价关系？用关系矩阵和关系图表示其中的等价关系。用关系矩阵和关系图表示其中的等价关系。用关系矩阵和关系图表示其中的等价关系。用关系矩阵和关系图表示其中的等价关系。解解解解:oo相互相互相互相互等价的元素等价的元素等价的元素等价的元素将关系矩阵分成了不同的块；将关系矩阵分成了不同的块；将关系矩阵分成了不同的块；将关系矩阵分成
8、了不同的块；oo相互等价的元素相互等价的元素相互等价的元素相互等价的元素组成了关系图中相互连通的部分。组成了关系图中相互连通的部分。组成了关系图中相互连通的部分。组成了关系图中相互连通的部分。a eb d c R1等价类等价类定义定义定义定义2.222.22设设设设RR是非空集合是非空集合是非空集合是非空集合AA上的等价关系，上的等价关系，上的等价关系，上的等价关系，对于任意对于任意对于任意对于任意x x AA，称集合，称集合，称集合，称集合 xxRR=y|y=y|y AA且且且且 RR为为为为x x关于关于关于关于RR的的的的等价类等价类等价类等价类，或称为或称为或称为或称为由由由由x x生
9、成的一个生成的一个生成的一个生成的一个RR的等价类的等价类的等价类的等价类；并称其中的并称其中的并称其中的并称其中的x x为为为为xxR R的的的的生成元生成元生成元生成元或或或或代表元代表元代表元代表元。即，即，即，即，x x R R表示由所有与表示由所有与表示由所有与表示由所有与x x关于关于关于关于R R等价的元素组成的集合。等价的元素组成的集合。等价的元素组成的集合。等价的元素组成的集合。例例2.54设设设设R R是集合是集合是集合是集合A=1,2,3,4,5,6,7,8A=1,2,3,4,5,6,7,8上的模上的模上的模上的模3 3同余关系，同余关系，同余关系，同余关系，用关系图表示
10、该关系？并求用关系图表示该关系？并求用关系图表示该关系？并求用关系图表示该关系？并求R R的所有等价类。的所有等价类。的所有等价类。的所有等价类。解解解解:集合集合集合集合A=1,2,3,4,5,6,7,8A=1,2,3,4,5,6,7,8A=1,2,3,4,5,6,7,8A=1,2,3,4,5,6,7,8上的模上的模上的模上的模3 3 3 3同余关系为同余关系为同余关系为同余关系为R=,3,R=,3,R=,3,R=,6,6,6,可以得到关系可以得到关系可以得到关系可以得到关系R R R R的关系图如图所示。的关系图如图所示。的关系图如图所示。的关系图如图所示。关于关于关于关于R R R R的
11、等价类如下的等价类如下的等价类如下的等价类如下1111R R R R=4=4=4=4R R R R=7=7=7=7R R R R=1,4,7 =1,4,7 =1,4,7 =1,4,7 2222R R R R=5=5=5=5R R R R=8=8=8=8R R R R=2,5,8 =2,5,8 =2,5,8 =2,5,8 3333R R R R=6=6=6=6R R R R=3,6=3,6=3,6=3,6 14 7 2 5 8 R 3 6等价类的性质等价类的性质定理定理定理定理2.192.19 设设设设R R为为为为非空集合非空集合非空集合非空集合A A上的等价关系，上的等价关系，上的等价关系，
12、上的等价关系，则则则则：(1)(1)对对对对于任意于任意于任意于任意x xA A，x x R R 是是是是A A的非空子集的非空子集的非空子集的非空子集.(2)(2)对对对对于任意于任意于任意于任意x x,y yA A，如果如果如果如果 R R,则则则则 x x RR=y y R R.(3)(3)对对对对于任意于任意于任意于任意x x,y yA A，如果如果如果如果 x,y R R,则则则则 x x R R y y R R=.(4)(4)x x A A x x R R=A A.商集商集定义定义定义定义2.232.23设设设设RR是非空集合是非空集合是非空集合是非空集合AA上的等价关系；上的等价
13、关系；上的等价关系；上的等价关系；将由将由将由将由RR的所有等价类构成的集合称为的所有等价类构成的集合称为的所有等价类构成的集合称为的所有等价类构成的集合称为A A关于关于关于关于R R的的的的商集商集商集商集,记记记记A/RA/R。A A/R R=x x R R|x x A A 例例例例2.25:2.25:令令令令R R是集合是集合是集合是集合A=1,2,3,4,5,6,7,8A=1,2,3,4,5,6,7,8上的模上的模上的模上的模3 3同余关系；同余关系；同余关系；同余关系；n nA A关于关于关于关于R R的商集为：的商集为：的商集为：的商集为：A/R A/R=1=1R R,2,2R
14、R,3,3R R=1,4,7,2,5,8,3,6=1,4,7,2,5,8,3,6n nA A关于恒等关系的商集为：关于恒等关系的商集为：关于恒等关系的商集为：关于恒等关系的商集为：A/IA/IA A =1,2,3,4,5,6,7,8=1,2,3,4,5,6,7,8n nA A关于全域关系的商集为：关于全域关系的商集为：关于全域关系的商集为：关于全域关系的商集为：A/EA/EA A =1,2,3,4,5,6,7,8=1,2,3,4,5,6,7,8商集的计算商集的计算 例例例例2.562.56 对于集合对于集合对于集合对于集合AA=a a,b b,c c,d d,e e 上的关系上的关系上的关系上
15、的关系RR=,，求，求，求，求AA/RR。解解解解：根据等价类的定义有：根据等价类的定义有：根据等价类的定义有：根据等价类的定义有 a a RR=b b RR =a a,b b,c c RR =c c,d d RR=e e RR =d d,e e 从而有从而有从而有从而有AA/RR=a a,b b,c c,d d,e e 划分划分定义定义定义定义2.242.24 对对对对于非空集合于非空集合于非空集合于非空集合A A，如果某个集合，如果某个集合，如果某个集合，如果某个集合S S=S=S1 1,S,S2 2,S,Smm 满满满满足足足足 S Si i AA且且且且 S Si i（i=1,2,mi
16、=1,2,m），），），），S Si i S Sj j=（ijij；i=1,2,mi=1,2,m；j=1,2,mj=1,2,m），），），），S S1 1 S S2 2 S Smm=A=A，则则则则将将将将S S称称称称为为为为A A的一个的一个的一个的一个划分划分划分划分，将将将将S S1 1,S,S2 2,S,Smm称称称称为这为这为这为这个个个个划分划分划分划分块块块块。例例2.57设集合设集合设集合设集合AA1,2,3,41,2,3,4，判断下列集合是否是，判断下列集合是否是，判断下列集合是否是，判断下列集合是否是AA的划分的划分的划分的划分 1,2,3,4 1,2,3,4 1,2,3
17、,41,2,3,41,2,3,1,4 1,2,3,1,4 ,1,2,3,4 ,1,2,3,4 1,2,3 1,2,3 1,2,3,4,1,2,3,4,例例2.58考察例考察例考察例考察例2.552.55中集合中集合中集合中集合A=1,2,3,4,5,6,7,8A=1,2,3,4,5,6,7,8。商集商集商集商集A/R=1,4,7,2,5,8,3,6A/R=1,4,7,2,5,8,3,6是否为是否为是否为是否为AA的划分？的划分？的划分？的划分？等价类与划分等价类与划分(等价类等价类-划分划分)定理定理定理定理2.20 2.20 设设设设RR是非空集合是非空集合是非空集合是非空集合AA上的等价关
18、系，则上的等价关系，则上的等价关系，则上的等价关系，则n n商集商集商集商集A/RA/R是是是是A A的一个划分的一个划分的一个划分的一个划分，将其称为，将其称为，将其称为，将其称为由等价关系由等价关系由等价关系由等价关系R R导出导出导出导出的等价划分，的等价划分，的等价划分，的等价划分，n n其中每个其中每个其中每个其中每个等价类等价类等价类等价类都是一个都是一个都是一个都是一个划分块划分块划分块划分块。例例例例2.59 2.59 对于例对于例对于例对于例2.562.56中集合中集合中集合中集合AA=a a,b b,c c,d d,e e 以及商以及商以及商以及商集集集集AA/RR=a a
19、,b b,c c,d d,e e。显然，显然，显然，显然，AA/RR是集合是集合是集合是集合AA的一个划分。的一个划分。的一个划分。的一个划分。等价类与划分等价类与划分(划分划分-等价类等价类)定理定理定理定理2.212.21设设设设S S=S S1 1,S S2 2,S Smm 是非空集合是非空集合是非空集合是非空集合AA的一个的一个的一个的一个划分划分划分划分，则由该划分确定的关系则由该划分确定的关系则由该划分确定的关系则由该划分确定的关系 RR=(=(S S1 1 S S1 1)(S S2 2 S S2 2)(S Smm S Smm)是是是是AA上的上的上的上的等价关系等价关系等价关系等
20、价关系。将上述等价关系称为将上述等价关系称为将上述等价关系称为将上述等价关系称为由划分由划分由划分由划分S S所导出的所导出的所导出的所导出的等价关系等价关系等价关系等价关系。例例2.60对于集合对于集合对于集合对于集合AA1,2,3,41,2,3,4的划分的划分的划分的划分1,2,3,41,2,3,4，试构造试构造试构造试构造AA上的等价关系。上的等价关系。上的等价关系。上的等价关系。解解解解:根据定理根据定理根据定理根据定理2.212.212.212.21，构造如下关系，构造如下关系，构造如下关系，构造如下关系R R R R=(l=(l=(l=(l l)l)l)l)(2,3(2,3(2,3
21、(2,3 2,3)2,3)2,3)2,3)(4(4(4(4 4)4)4)4)=,=,=,=,=,显然，关系显然，关系显然，关系显然，关系R R R R是自反的、对称的和传递的，是自反的、对称的和传递的，是自反的、对称的和传递的，是自反的、对称的和传递的，即，即，即，即，R R R R是是是是A A A A上的等价关系。上的等价关系。上的等价关系。上的等价关系。练习练习设设设设A=1,2,3,4,5.A=1,2,3,4,5.1)1)求求求求A A的划分的划分的划分的划分 =1,2,3,4,5=1,2,3,4,5对应的等价关系。对应的等价关系。对应的等价关系。对应的等价关系。2)2)2)2)已知关
22、系已知关系已知关系已知关系R=,R=,，求，求，求，求R R对应对应对应对应的划分。的划分。的划分。的划分。解解解解:R R R R =,=,=,=,A/R=1A/R=1R R,2,2R R，其中，其中，其中，其中11R R=1,3=1,3，22R R=2,4,5=2,4,5。思考：思考：对对非空集合非空集合A来来说说，A上的等价关系与上的等价关系与A的划分哪种更多的划分哪种更多?思考思考oo设设设设A A为含有为含有为含有为含有3 3个元素的集合。问：个元素的集合。问：个元素的集合。问：个元素的集合。问：A A上可以有多少个不同的上可以有多少个不同的上可以有多少个不同的上可以有多少个不同的等价关系？等价关系？等价关系？等价关系？（答案：（答案：（答案：（答案：5 5种）种）种）种）oo设设设设A A为含有为含有为含有为含有4 4个元素的集合。问：个元素的集合。问：个元素的集合。问：个元素的集合。问：A A上可以有多少个不同的上可以有多少个不同的上可以有多少个不同的上可以有多少个不同的等价关系？等价关系？等价关系？等价关系？（答案：（答案：（答案：（答案：1515种）种）种）种）作业作业P72o第第37题题o第第41题题o第第45题题o第第47题题谢谢观赏谢谢观赏