资源描述：
《离散数学等价关系与偏序关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、4.5等价关系与偏序关系等价关系的定义等价类及其性质商集与集合的划分等价关系与划分的一一对应相容关系偏序关系偏序集与哈斯图偏序集中的特定元素14.5等价关系和划分定义设R是A上的二元关系，如果（1）R是自反的；（2）R是对称的；（3）R是可传递的。则称R是A上的等价关系。若∈R,称x等价于y,记做x～y.等价关系是经常使用的重要的二元关系。1、等价关系的定义一、等价关系2例如，我们用a,b,c,d,e,f分别表示6位大学生，其中a,b,c都姓张，d,e,f都姓李。若令集合A={a,b,c,d,e,f}张李R是A上的同姓氏关系（同姓的大学
2、生认为是相关的）容易验证同姓氏关系R是A上的等价关系。（1）因为每一个大学生都和自已是同姓的，所以满足自反性；（2）当(a,b)∈R时有(b,a)∈R，所以满足对称性；（3）当(a,b)∈R和(b,c)∈R时有(a,c)∈R，所以R是可传递的。由此可得同姓氏关系R是等价关系。3又如设集合A的情况同上所述若令集合A={a,b,c,d,e,f}2022其中a,b,c,d都是20岁，e,f都是22岁。如果年龄相同的大学生认为是相关的，那么“同年龄”关系R是等价关系。（1）因为每一个大学生都和自已是同年龄的，所以满足自反性；（2）当(a,b)∈R时有(b
3、,a)∈R，所以满足对称性；（3）当(a,b)∈R和(b,c)∈R时有(a,c)∈R，所以R是可传递的。由此可得同年龄关系R是等价关系。4再如设集合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
4、是等价关系。5由上述3个例子可知那种同姓氏、同房间、同年龄的关系都是等价关系。如果抽象地讨论，对集合A中的元素按照某种特性分成几个组，每个元素只属于一个组（如按年龄分组，即同年龄人在同一组内；或按姓氏分组，即同姓人在同一组内），并且定义在同一组内的元素是相关的，而不在同一组内的元素是不相关的，那么由此产生的二元关系必然是等价关系。由此可知等价关系所具有的重要特性。由此可见：等价关系实际上是同组关系。6下面将利用表格和关系矩阵来进一步了解等价关系的特征。2、等价关系的表格表示和关系矩阵为了方便将上述3个例子综合如下：（1）a,b,c都姓“张”，d,
5、e,f都姓“李”；（2）a,b,c,d都是20岁，e,f都是22岁；（3）a,b,d同住一个房间，c,e,f同住另一个房间。下面分别画出（1）、（2）、（3）所表示的等价关系的表格和关系矩阵：7abcdefecbafd√√√√√√√√√√√√√√√√√√（1）a,b,c都姓“张”，d,e,f都姓“李”abcdefecbafd易见在描述等价关系的表格中，带有“√”的格子将形成若干个正方形；而在关系矩阵中则有一些小方阵，其元素都是1，而其它元素都是0。8对于（2）所示的等价关系的表格表示和关系矩阵也有上述特征：abcdefecbafd√√√√abcd
6、efecbafd（2）a,b,c,d都是20岁，e,f都是22岁；√√√√√√√√√√√√√√√√9对于（3）所示的等价关系，如果将集合A={a,b,c,d,e,f}中的顺序改为A={a,b,d,c,e,f}也就是把相关的元素排在一起那么所画出的表格也显示上述特征：（3）a,b,d同住一个房间，c,e,f同住另一个房间。abdcefedbafc√√√√√√√√√√√√√√√√√√abdcefedbafc10例1设集合A={1，2，3，4，5，6，7}，R是A上的模3同余关系，试说明此关系是等价关系，并画出表格和关系矩阵。解（1）相同数被3除后余数
7、一定相同，所以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是可传递的，说明此关系是等价关系。11在集合A中，以相关元素顺序排列，即：A={1,4,7,2,5,3,6}也就是把相关的元素排在一起那么所画出的表格表示和关系矩阵如下：由此可见模3同余关系也是一种分组关系，它是把A中的元素被3除后，余数为1的分为一组（1,4,7），余数
8、为2的分为一组（2,5），余数为3的分为一组（3,6）。1472536374165214725363741652√√√√√√√√√√√√
