离散数学--44等价关系与偏序关系

《离散数学--44等价关系与偏序关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.4等价关系与偏序关系4.4.1等价关系4.4.2等价类和商集4.4.3集合的划分4.4.4偏序关系4.4.5偏序集与哈斯图1课件等价关系的定义与实例定义4.18设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若∈R,称x等价于y,记做x～y.例1设A={1,2,…,8},如下定义A上的关系R：R={

2、x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.不难验证R为A上的等价关系,因为x∈A,有x≡x(mod3)x,y∈A,

3、若x≡y(mod3),则有y≡x(mod3)x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)2课件模3等价关系的关系图设A={1,2,…,8},R={

4、x,y∈A∧x≡y(mod3)}R的关系图如下：3课件等价类定义4.19设R为非空集合A上的等价关系,x∈A，令[x]R={y

5、y∈A∧xRy}称[x]R为x关于R的等价类,简称为x的等价类,简记为[x].实例A={1,2,…,8}上模3等价关系的等价类：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}4课

6、件等价类的性质定理4.8设R是非空集合A上的等价关系,则(1)x∈A,[x]是A的非空子集.(2)x,y∈A,如果xRy,则[x]=[y].(3)x,y∈A,如果xy,则[x]与[y]不交.(4)，即所有等价类的并集就是A.5课件性质的证明由等价类定义可知,x∈A有[x]A.由自反性有xRx，因此x∈[x],即[x]非空.任取z,则有z∈[x]∈R∈R∈R∧∈R∈R∈R从而证明了z∈[y].综上所述必有[x][y].同理可证[y][x].这就得到了[x]=[

7、y].(3)假设[x]∩[y]≠,则存在z∈[x]∩[y],从而有z∈[x]∧z∈[y],即∈R∧∈R成立.根据R的对称性和传递性必有∈R,与xy矛盾6课件性质的证明（续）(4)先证.任取y,y∈x(x∈A∧y∈[x])y∈[x]∧[x]Ay∈A从而有.再证A.任取y,y∈Ay∈[y]∧y∈Ay∈从而有A成立.综上所述得7课件商集定义4.20设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R={[x]R

8、x∈A}例2令A={1,2,…,8}，A关于模3等价关系R的商集为A

9、/R={{1,4,7},{2,5,8},{3,6}}A关于恒等关系和全域关系的商集为：A/IA={{1},{2},…,{8}}A/EA={{1,2,…,8}}8课件集合的划分定义4.21设A为非空集合,若A的子集族(P(A))满足下面条件：(1)(2)xy(x,y∈∧x≠y→x∩y=)(3)∪=A则称是A的一个划分,称中的元素为A的划分块.例3设A＝{a,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}

10、,{c}}5={,{a,b},{c,d}}，6={{a,{a}},{b,c,d}}则1和2是A的划分,其他都不是A的划分.9课件等价关系与划分的一一对应商集A/R就是A的一个划分不同的商集对应于不同的划分任给A的一个划分,如下定义A上的关系R：R={

11、x,y∈A∧x与y在的同一划分块中}则R为A上的等价关系,且该等价关系确定的商集就是.例4给出A＝{1,2,3}上所有的等价关系求解思路：先做出A的所有划分,然后根据划分写出对应的等价关系.10课件例41,2和3分别对应于等价关系R1,R2和R3.其中R1={<2,3>,<3,2>}

12、∪IAR2={<1,3>,<3,1>}∪IAR3={<1,2>,<2,1>}∪IAA上的等价关系与划分之间的对应：4对应于全域关系EA5对应于恒等关系IA11课件实例根据有序对的x+y=2,3,4,5,6,7,8将AA划分.(AA)/R={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}}例5设A={1,2,3,4}，在AA上