离散数学等价关系与偏序关系.ppt

1,4.5 等价关系与偏序关系,等价关系的定义等价类及其性质商集与集合的划分等价关系与划分的一一对应相容关系偏序关系偏序集与哈斯图偏序集中的特定元素,2,4.5 等价关系和划分,定义 设R是 A上的二元关系，如果,（1）R是自反的；,（2）R是对称的；,（3）R是可传递的。,则称R是A上的等价关系。若R,称 x 等价于y,记做 xy.,等价关系是经常使用的重要的二元关系。,1、等价关系的定义,一、等价关系,3,例如，我们用a,b,c,d,e,f 分别表示6位大学生，其中a,b,c都姓张，d,e,f都姓李。,若令集合A=a,b,c,d,e,f 张 李,R是A上的同姓氏关系（同姓的大学生认为是相关的）,容易验证同姓氏关系R是A上的等价关系。,（1）因为每一个大学生都和自已是同姓的，所以满足自反性；,（2）当(a,b)R时有(b,a)R，所以满足对称性；,（3）当(a,b)R和(b,c)R时有(a,c)R，所以R是可传递的。,由此可得同姓氏关系 R是等价关系。,4,又如设集合A的情况同上所述,若令集合A=a,b,c,d,e,f 20 22,其中a,b,c,d都是20岁，e,f都是22岁。,如果年龄相同的大学生认为是相关的，那么“同年龄”关系R是等价关系。,（1）因为每一个大学生都和自已是同年龄的，所以满足自反性；,（2）当(a,b)R时有(b,a)R，所以满足对称性；,（3）当(a,b)R和(b,c)R时有(a,c)R，所以R是可传递的。,由此可得同年龄关系 R是等价关系。,5,再如设集合A的情况同上所述,若令集合A=a,b,d,c,e,f 同房间 同房间,其中a,b,d同住一个房间，c,e,f同住另一个房间。,如果同住一个房间的大学生认为是相关的，那么“同房间”关系R也是等价关系。,（1）因为每一个大学生都和自已是同房间的，所以满足自反性；,（2）当(a,b)R时有(b,a)R，所以满足对称性；,（3）当(a,b)R和(b,c)R时有(a,c)R，所以R是可传递的。,由此可得同房间关系 R是等价关系。,6,由上述3个例子可知那种同姓氏、同房间、同年龄的关系都是等价关系。,如果抽象地讨论，对集合A中的元素按照某种特性分成几个组，每个元素只属于一个组（如按年龄分组，即同年龄人在同一组内；或按姓氏分组，即同姓人在同一组内），并且定义在同一组内的元素是相关的，而不在同一组内的元素是不相关的，那么由此产生的二元关系必然是等价关系。,由此可知等价关系所具有的重要特性。,由此可见：等价关系实际上是同组关系。,7,下面将利用表格和关系矩阵来进一步了解等价关系的特征。,2、等价关系的表格表示和关系矩阵,为了方便将上述3个例子综合如下：,（1）a,b,c都姓“张”，d,e,f都姓“李”；（2）a,b,c,d都是20岁，e,f都是22岁；（3）a,b,d同住一个房间，c,e,f同住另一个房间。,下面分别画出（1）、（2）、（3）所表示的等价关系的表格和关系矩阵：,8,a b c d e f,（1）a,b,c都姓“张”，d,e,f 都姓“李”,a b c d e f,易见在描述等价关系的表格中，带有“”的格子将形成若干个正方形；而在关系矩阵中则有一些小方阵，其元素都是1，而其它元素都是0。,9,对于（2）所示的等价关系的表格表示和关系矩阵也有上述特征：,a b c d e f,a b c d e f,（2）a,b,c,d都是20岁，e,f都是22岁；,10,对于（3）所示的等价关系，如果将集合A=a,b,c,d,e,f 中的顺序改为A=a,b,d,c,e,f 也就是把相关的元素排在一起那么所画出的表格也显示上述特征：,（3）a,b,d同住一个房间，c,e,f同住另一个房间。,a b d c e f,a b d c e f,11,例1 设集合A=1，2，3，4，5，6，7，R是A上的模3 同余关系，试说明此关系是等价关系，并画出表格和关系矩阵。,解（1）相同数被3除后余数一定相同，所以R上自反的；,显然R也是对称的；,又由于A中任意元素a，可写为,a=3k+r,所以当(a,b)R 时，有a-b=3k.,因此当(a,b)R 和(b,c)R时，即有,a-b=3k1，b-c=3k2.,于是a-c=a-b+b-c=3(k1-k2),=3k,由此可得(a,c)R，所以R是可传递的，,说明此关系是等价关系。,12,在集合A中，以相关元素顺序排列，,即：A=1,4,7,2,5,3,6也就是把相关的元素排在一起那么所画出的表格表示和关系矩阵如下：,由此可见模3 同余关系也是一种分组关系，它是把A中的元素被3除后，余数为1的分为一组（1,4,7），余数为2的分为一组（2,5），余数为3的分为一组（3,6）。,1 4 7 2 5 3 6,1 4 7 2 5 3 6,13,以上的例子不仅说明集合A上的等价关系实际上是一种“同组”关系。,即当集合A确定一种“分组”形式后，也就确定了A上的一种等价关系（只要将同一组的元素认作是相关的）；,反之当确定一个A上的等价关系后，也就确定了A上的一种“分组”形式（只要将相关元素合成一组）。,为了详细地讨论这一问题，下面介绍等价类和划分这两个概念：,14,二、等价类,定义：设R是A上的等价关系，aA，由A中所有与a相关的元素组成的集合称为a关于R的等价类，记作aR.,例如 集合A=1，2，3，4，5，6，7，R是A上的模3 同余关系，显然R是A上等价关系，,A中各元素关于R的等价类分别是：,2R=2，5 5R=2，5,显然相关元素的等价类是相同的，所以不同的等价类仅有3个，它们是1R，2R，3R。,15,又如设集合A=a,b,c,d,e,f,g其中a,b,c,d,e,f,g分别表示7位大学生，且a,b都是20岁，c,d都是22岁，e,f都是24岁，g是25岁。R是A的同年龄关系，写出 A中各元素关于R的等价类。,显然aR=a,b bR=a,b,cR=c,d dR=c,d,eR=e,f fR=e,f,gR=g,定义：R是A上的等价关系，由R的所有不同的等价类作为元素构成的集合，称为A关于R的商集，记作A/R。,16,“商”和除法有关，比如把一块蛋糕平均分成四份，从两种不同的角度看这件事：从算术角度看：1用4除,每份1/4,这就是“商”,于是:1=1/4+1/4+1/4+1/4 从集合角度看：集合A用模3同余关系R划分，得到三个等价类，所以 A 1,4,7,2,5,3,6=1R,2R,3R-商集,17,思考：1.集合A=1，3，5，7，9，R是A上的模4 同余关系，求R的商集A/R。,3R=7R=3,7,1R=5R=9R=1，5，9,所以A关于R的商集A/R=1，5，9，3，7。,答案：,18,答案：有4个是不相同的等价类，它们是a,b，c,d,e,f，g，h。,2.A=a,b,c,d,e,f,g,h,A上的等价关系R如图所示：,所以A关于R的商集为A/R=a,b，c,d,e,f，g，h。,a b c d e f g h,写出A关于R的商集。,19,三、集合的划分,定义：设A是集合，A1，A2，An，是A的子集，如果A1 A2 An=A，且Ai Aj=（ij,i=1,2,n,j=1,2,n）.由以A1，A2，An作为元素构成的集合S=A1，A2，An称为A的一个划分，每一个子集Ai称为块。,例如A=a,b,c,d,e,f,A2=a,d,e，b,c,f,A1=a,b，c,d，e,f,A3=a,f，b,d,e，c,则A1,A2,A3都是A的划分；在A1中 a,b，c,d，e,f是块。,20,思考：,设Aa,b,c,d,给定1,2,3,4,5,6如下：1=a,b,c,d，2=a,b,c,d 3=a,a,b,c,d,4=a,b,c 5=,a,b,c,d,6=a,a,b,c,d 问哪些是A的划分,哪些不是 A 的划分？,答案：1和2 是A的划分,其他都不是 A 的划分.,21,由此可知，如果R是A上的等价关系，则商集A/R就是A上的一个划分，等价类就是块。,定理：集合A上的一个划分能确定一个A上的等价关系，反之确定了A上的一个等价关系也能确定A上的一个划分。,例如A=a,b,c,d,e,A=a，b,c,d,e,那么它所确定的等价关系的表格表示如图所示：,a b c d e,22,又如A=a,b,c,d,e,R为A上的等价关系，其表格表示如图所示：,则由R确定的划分为A=a,b,c,d,e。,a b c d e,由此可知，集合A上的等价关系与划分可以建立1-1对应关系。,23,例1.设A是具有5个元素的集合，问满足下列条件的等价关系有多少种？（1）等价类中至少含有2个元素；（2）至少有一个等价类含有2个元素。,解答(1)由于集合A上的等价关系与划分是1-1对应关系。所以等价类中至少有2个元素的等价关系与块中至少有2个元素的划分的个数相同。而块中至少有2个元素的划分共有两类：一类是划分中仅有1块（块中含有5个元素），这样的划分仅有1种。另一类是划分中有2块，其中1块含有2个元素，另一块含有3个元素，这样的划分有 种。,所以当 时等价类中至少含有2个元素的等价关系共有11种。,24,(2)同理至少有1个等价类含有2个元素的等价关系的个数与至少有1个块含有2个元素的划分的个数相同。而至少有1个块含有2个元素的划分可分为三类：,所以当 时至少有一个等价类含有2个元素的等价关系共有10+10+15=35种。,第一类是划分中含有2块，各块中含有的元素数分别为2，3，,第三类是划分中有4块，各块中含有的元素数分别为2，1，1，1，,第二类是划分中有3块，各块中含有的元素数分别为2，2，1，,这样的划分共有 种。,这样的划分有 种。,这样的划分有 种。,25,例2.设R是A上的自反关系,且当(a,b)R 和(a,c)R时,必有(b,c)R,证明R是等价关系.,证明:因为当(a,b)R 和(a,c)R时,必有(b,c)R.由于R是自反关系,即(a,a)R,于是有:当(a,b)R 和(a,a)R时,必有(b,a)R,因此R是对称关系;,由于R是对称关系,所以当(a,b)R,(b,c)R时,必有(b,a)R,(b,c)R,由题设可得:(a,c)R,所以R是传递关系;,因此R是等价关系.,26,思考：,1.设I是整数集合,当ab0时,(a,b)R,说明R不是等价关系.,2.设R是A上的自反关系,且当(a,b)R 和(b,c)R时,必有(c,a)R,证明R是等价关系.,3.设A是具有4个元素的集合,问在A上可以有多少种不同的 等价关系?,27,1.设I是整数集合,当ab0时,(a,b)R,说明R不是等价关系.,解:因为(-1,0)R,(0,1)R,但(-1,1)R,说明R不是传递关系,所以R不是等价关系.,解：,28,2.设R是A上的自反关系,且当(a,b)R 和(b,c)R时,必有(c,a)R,证明R是等价关系.,证明:因为当(a,b)R 和(b,c)R时,必有(c,a)R.由于R是自反关系,即(b,b)R,于是有:当(a,b)R 和(b,b)R时,必有(b,a)R,因此R是对称关系;,由于当(a,b)R 和(b,c)R时,必有(c,a)R,又由于R是对称关系,由此可得(a,c)R,所以R是传递关系;,因此R是等价关系.,29,3.设A是具有4个元素的集合,问在A上可以有多少种不同的等价关系?,解:由于A上的等价关系与A上的划分1-1对应,所以A上有多少种不同的 划分就有多少种不同的等价关系.,设A=a,b,c,d,分以下几种情况讨论:,(1)当划分中仅含有1个块时,这样的划分仅有1种:a,b,c,d,(2)当划分中含有2个块时,它们为:,a,b,c,d b,a,c,d c,a,b,d d,a,b,c,a,b,c,d a,c,b,d b,c,a,d,这样的划分应有=7种,30,(3)当划分中含有3个块时,它们为:,a,b,c,d a,c,b,d a,d,c,b b,c,a,d b,d,a,c c,d,a,b,(4)当划分中含有4个块时,这样的划分仅有1种:,a,b,c,d,综上所述,当A是具有4个元素的集合时,在A上共有1+7+6+1=15(种)不同的等价关系.,31,四、相容关系,定义：设R是 A上的二元关系，如果满足：（1）R是自反的；（2）R是对称的。则称R是A上的相容关系。,易知，等价关系是一种特殊的相容关系，即具有传递的相容关系。,在人际关系中朋友关系是相容关系，但它不是等价关系，因为它满足自反性、对称性、但它不满足可传递性。,32,设A=boy,root,cat,beer,and,R是A上的二元关系，其定义为：当两个单词至少有一个字母相同时，则认为是相关的。,显然R是自反的，对称的，所以R是A上的相容关系。但它不是等价关系，因为它不是可传递的。如(boy,root)R,(root,cat)R,而(boy,cat)R。,33,定义：设R是 A上的相容关系，B是A的子集，而且在B中任意两个元素都是相关的，则称B为由相容关系R产生的相容类。,34,例如设A=134，345，275，347，348，129，R是A上的二元关系，其定义为：a,bA;且a 和b至少有一个数码相同，则（a,b）R.显然R是相容关系。A的子集：134，347，348，275，345，134，129等都是相容类。,对于前两个相容类，都能添加新的元素组成新的相容类。如在相容类134，347，348中添加新的元素345，可组成新的相容类：134，347，348，345；在相容类275，345中添加新的元素347，可组成新的相容类：275，345，347。,而对于第三个相容类：134，129，添加任意一个新元素就不再组成相容类，称这样的相容类为最大相容类。,35,对于最大相容类还可以这样认定：R是 A上的相容关系，B是相容类，在差集AB中没有元素能和B中所有元素都是相关的，则称B为最大相容类。,利用相容关系的图形表示可以很方便地确定相容类和最大相容类。,36,如图所示中，完全多边形的顶点集合就是相容类。所谓完全多边形是指每个顶点都与其它顶点有边联结的多边形。例如三角形是完全多边形，一个四边形加上两条对角线也是完全多边形。,由于顶点134,348,347构成了一个三角形，所以134,348,347是相容类；同理275，345，347是相容类；134，347，348，345也是相容类。,如,37,由此可见，图中最大的完全多边形的顶点集合就最大相容类。这里的“最大”是这样的含义：如果一个完全多边形，在添加任何新的顶点就不再成为完全多边形，则称此完全多边形是最大的完全多边形。如由顶点134，347，348，345构成的完全多边形是最大完全多边形；由顶点345，275，347构成的完全多边形也是大完全多边形。,易见，在该图中，有四个最大相容类，它们是：192，134，129，275，345，275，347，134，345，347，348。,38,定义：A是集合，A1,A2,，An都是它的非空子集，令S=A1,A2,，An,如果A1A2An=A，则称S为A的覆盖。,例如A=1，2，3，4，5，S=1，2，2，3，4，1，3，5，则S是A的覆盖。,39,定义：S=A1,A2,，An是集合A的覆盖，且对于S中任意元素Ai,不存在S中的其它元素Aj，使得Ai是Aj的子集，则称S 为A的完全覆盖。,例如 A=a,b,c,d,e S1=a,b,b,c,d,d,e S2=a,b,a,b,c,a,d,e其中S1是A的覆盖又是完全覆盖，而S2是A的覆盖但不是完全覆盖，因为a,b是a,b,c的子集。,40,相容关系和覆盖之间的关系：,如果R是A上的相容关系，对于A中的任意元素a，集合a是一个相容类，并且可以对此集合不断地添加新的元素，直到使它成为最大相容类。因此，A中的每一个元素都将是某一个最大相容类的元素。由此可见，相容关系R产生的所有最大相容类构成的集合是A的一个覆盖；又由最大相容类的定义可知，一个最大相容类决不是另一个最大相容类的子集。所以由最大相容类构成的集合是A的一个完全覆盖。,由此可得下面的结论：R是 A上的相容关系，R能确定一个A上的完全覆盖；反之，当给定A的一个完全覆盖时，则能确定A上的相容关系R，使R产生的最大相容类构成的集合就是这个完全覆盖。,41,例.A=1，2，3，4，5，6，R为 A上的相容关系，其图形表示如图所示，求R所确定的完全覆盖。,解：由图可知，R产生的最大相容类为：1，2，6，1，4，5，3，6。所以R确定的完全覆盖S=1，2，6，1，4，5，3，6。,42,例.A=a,b,c,d,e,f,g,A的完全覆盖S=a,b,b,c,f,g,c,d,e,写出S所确定的相容关系R。,解 由S容易得到R的图形表示，如图，所以S所确定的相容关系：R=(a,a),(b,b),(a,b),(b,a),(c,c),(f,f),(g,g),(b,c),(c,b),(b,f),(f,b),(b,g),(g,b),(c,f),(f,c),(c,g),(g,c),(f,g),(g,f),(d,d),(e,e),(c,d),(d,c),(c,e),(e,c),(d,e),(e,d)。,43,思考：,1、集合A=a1,a2,a3,a4,a5,a6,R是A上的相容关系，其关系矩阵为：,求R的所有最大相容类。,2、集合A=111，122，341，456，795，893 R是A上的二元关系，当a,bA，且a 和b至少有一个数码相同，则（a,b）R.试画出R的关系图。并写出R的所有最大相容类。,44,3、集合A=a,b,c,d,e,f,g.完全覆盖S=a,b,c,d,c,d,e,d,e,f,f,g,写出S所确定的相容关系R。,