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

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

1、第9节等价关系与偏序关系主要内容：等价关系偏序关系1定义1集合X上的二元关系R称为等价关系，如果R同时具有以下三个性质：例1：集合X上的恒等关系是不是X上的等价关系？1.R是自反的，即xX，xRx;2.R是对称的，即如果xRy，则yRx;3.R是传递的，即如果xRy，yRz，则xRz。是X上的等价关系。1等价关系2等价关系实例例2：考虑整数集Z上的模n同余关系。例4：设f:XY，Ker(f)={(x,y)x,yX，且f(x)=f(y)}。Ker(f)是X上的等价关系。例3：实数集上的“>

2、”、“<”、“≧”、“≦”是不是R上的等价关系？实数集上的“>”、“<”、“≧”、“≦”都不是R上的等价关系。是等价关系。3例5：设A={1,2,…,8},如下定义A上的关系R：R={(x,y)

3、x,yA∧x≡y(mod3)}R的关系图如下：等价关系的关系图4定义2设R是X上的一个等价关系，xX，X的子集Ex={yyX且xRy}称为x关于R的等价类，或简记为x的等价类。x的等价类常记为[x]，即[x]={yyX且xRy}。例5：设A={1,2,…,8},如下定义A上的关系R：

4、R={(x,y)

5、x,yA∧x≡y(mod3)}等价类的定义A={1,2,…,8}上模3等价关系的等价类：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}5等价类的性质(3)x,yX,如果(x,y)R,则[x]∩[y]=。定理1设R是非空集合X上的等价关系,则(1)xX,[x]≠。(2)x,yX,如果(x,y)R,则[x]=[y]。(4)，即所有等价类的并集就是X。6定义3设X为非空集合，X的若干个子集形成的

6、集族称为X的一个划分，如果具有性质：集合的划分如果是X的一个划分，则当=k时，被称为X的一个k-划分。(2)x,y，若xy，则x∩y=;(1)；(3)。称中的元素为X的划分块。7例6：设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},{c}}5={,{a,b},{c,d}}，6={{a,{a}},{

7、b,c,d}}1和2是A的划分，其他都不是A的划分。实例8定理1设R是X上的一个等价关系，则R的所有等价类的集合是X的一个划分。等价关系与集合的划分定理2设是集合X的一个划分，令R={(x,y)

8、x,yX∧x与y在的同一划分块中}则R是X上的一个等价关系，并且就是R的等价类之集。注：由定理1、2可得：X上的等价关系与X的划分是一一对应的，并且互相确定。9定义4设R是X上的等价关系，由R所确定的X的划分也就是R的所有等价类之集称为X对R的商集，并记X/R。即：X/R={[x]xX，[

9、x]是x的等价类}。等价关系R确定的划分是R的所有等价类之集{[x]xX}商集10例7：令A={1,2,…,8}。A关于模3等价关系R的商集为：A/R={{1,4,7},{2,5,8},{3,6}}A关于恒等关系和全域关系的商集为：A/IA={{1},{2},…,{8}}A/EA={{1,2,…,8}}实例11例8：给出A＝{1,2,3}上所有的等价关系。求解思路：先做出A的所有划分,然后根据划分写出对应的等价关系。实例12实例1,2和3分别对应于等价关系R1,R2和R3，其中R1={(

10、2,3),(3,2)}∪IAR2={(1,3),(3,1)}∪IAR3={(1,2),(2,1)}∪IAA上的等价关系与划分之间的对应：4对应于全域关系EA；5对应于恒等关系IA；问题：设集合X为有限集，

11、X

12、=n，则X上有多少个等价关系？13定理4设R为X上的一个二元关系，则e(R)=(R∪R-1)*。R的等价闭包(R的自反对称传递闭包)，记为e(R),e(R)是X上包含R的那些等价关系的交集。定理5设R,S是X上的等价关系，则RS是等价关系的充要条件是RS=SR。推论设R,S是X上

13、的等价关系，则RS是等价关系的充要条件是RSSR。等价关系的运算14定义1集合X上的二元关系R称为偏序关系，如果R同时满足以下三个性质：当抽象地讨论X上的偏序关系时，常用符号“”表示偏序关系。如果xy，则读作“x小于或等于y”。1.R是自反的；2.R是反对称的；3.R是传递的。约定xy且xy时，就记为x