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

离散数学等价关系与偏序关系演示文稿1/30第1页，共28页。2/30（优选）离散数学等价关系与偏序关系第2页，共28页。等价关系实例例2：考虑整数集Z上的模n同余关系。例4：设f:X

Y，Ker(f)={(x,y)x,yX，且f(x)=f(y)}。Ker(f)是X上的等价关系。例3：实数集上的“>”、“<”、“≧”、“≦”是不是R上的等价关系？实数集上的“>”、“<”、“≧”、“≦”都不是R上的等价关系。是等价关系。第3页，共28页。例5：设A={1,2,…,8},如下定义A上的关系R：

R={(x,y)|x,y

A∧x≡y(mod3)}R的关系图如下：等价关系的关系图第4页，共28页。

定义2

设R是X上的一个等价关系，xX，X的子集Ex={yyX且xRy}称为x关于R的等价类，或简记为x的等价类。x的等价类常记为[x]，即[x]={yyX且xRy}。例5：设A={1,2,…,8},如下定义A上的关系R：

R={(x,y)|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页，共28页。等价类的性质(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页，共28页。

定义3

设X为非空集合，X的若干个子集形成的集族

称为X的一个划分，如果具有性质：集合的划分如果

是X的一个划分，则当

=k时，被称为X的一个k-划分。(2)x,y，若xy，则x∩y=;(1)

；(3)

。

称

中的元素为X的划分块。第7页，共28页。例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}},{b,c,d}}

1和

2是A的划分，其他都不是A的划分。实例第8页，共28页。

定理1

设R是X上的一个等价关系，则R的所有等价类的集合是X的一个划分。等价关系与集合的划分

定理2

设是集合X的一个划分，令

R={(x,y)|x,y

X∧x与y在

的同一划分块中}则R是X上的一个等价关系，并且就是R的等价类之集。注：由定理1、2可得：X上的等价关系与X的划分是一一对应的，并且互相确定。第9页，共28页。

定义4

设R是X上的等价关系，由R所确定的X的划分也就是R的所有等价类之集称为X对R的商集，并记X/R。

即：X/R={[x]xX，[x]是x的等价类}。

等价关系R确定的划分是R的所有等价类之集

{[x]xX}商集第10页，共28页。例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页，共28页。例8：给出A＝{1,2,3}上所有的等价关系。求解思路：先做出A的所有划分,然后根据划分写出对应的等价关系。

实例第12页，共28页。实例

1,

2和

3分别对应于等价关系R1,R2和R3，其中

R1={(2,3),(3,2)}∪IA

R2={(1,3),(3,1)}∪IA

R3={(1,2),(2,1)}∪IAA上的等价关系与划分之间的对应：

4对应于全域关系EA；

5对应于恒等关系IA；问题：设集合X为有限集，|X|=n，则X上有多少个等价关系？第13页，共28页。定理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上的等价关系，则R

S是等价关系的充要条件是R

S

S

R。等价关系的运算第14页，共28页。

定义1

集合X上的二元关系R称为偏序关系，如果R同时满足以下三个性质：当抽象地讨论X上的偏序关系时，常用符号“”表示偏序关系。如果xy，则读作“x小于或等于y”。1.R是自反的；2.R是反对称的；3.R是传递的。约定xy且xy时，就记为x<y。在偏序关系中，并不是X中所有元素都可比较;如果存在x,yX使得xy与yx中有一个成立，则称x与y可比较;如果x,yX，xy并且yx，则称x与y不可比较。2偏序关系第15页，共28页。

定义2

设是X上的一个偏序关系，则称二元组(X,)为偏序集。一个集合上可能存在多个偏序集。例1：设S是一个集合，S的子集间的包含关系是不是偏序关系？在这个偏序集中，存在着不可比较元素。例如：S={a,b,c}，则{a}与{b,c}不可比较。偏序集例如实数集上存在(R,)和(R,≥)两个偏序集。

S的子集间的包含关系是2S上的偏序关系，(2S,)是一个偏序集。第16页，共28页。例2：自然数集合N上的整除关系“

”是不是偏序关系?自然数集合N上的整除关系“

”是偏序关系。

(N,)是一个偏序集。设≤是X上的偏序关系，则≤的逆≤-1也是X上的偏序关系，以后用“≥”表示≤的逆关系，并读成“大于或等于”。若x≥y且xy，则简记为x>y。实例第17页，共28页。

定义3

集合X上的偏序关系叫做全序关系，如果x,yX，xy与yx至少有一个成立。全序关系也称为线性序关系。X与全序关系≤构成的二元组(X,≤)称为全序集。偏序集与全序集的主要区别在于全序集中任两个元素均可比较“大小”，而在偏序集中任意两个元素不一定都能比较大小。实数间的常用的“小于或等于”关系是不是全序关系?全序关系与全序集集合的包含关系与自然数间的整除关系是不是全序关系?是全序关系，相应的偏序集也是全序集。二者都不是全序关系。第18页，共28页。

定义4设(X,≤)是一个偏序集，称y盖住x，如果x<y且对每个zX，若x≤z≤y，则x=z或y=z。如果y盖住x，则y被称为x的后继，而x称为y的前驱。盖住的定义例3：偏序集(N,≤)中，称3盖住2，3是2的后继，2是3的先驱。

{1,2,4,6}集合上的整除关系,2覆盖1,4和6覆盖2；但4不覆盖1.第19页，共28页。哈斯(Hasse)图首先偏序关系≤是自反的，所以偏序关系的关系图中每个顶点都有一个环，因此可以省略每个顶点的环。其次由于偏序关系是传递的，那么只要在前驱与后继间联线即可。最后由于反对称性，若x<y，x

y，则点y画在x的上方，这样就不必用矢线了，按上述方法画出的图称为(X,≤)的哈斯图。

第20页，共28页。特点：

(1)每个结点没有环;(2)两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前;(3)具有覆盖关系的两个结点之间连边。

哈斯图就是利用偏序的自反、反对称、传递性简化了的关系图。哈斯(Hasse)图的特点第21页，共28页。例4：({1,2,3,4,5,6,7,8,9},R整除)(P({a,b,c}),R

)哈斯图实例第22页，共28页。

例5：已知偏序集(A,R)的哈斯图如下图所示，试求出集合A和关系R的表达式。A={a,b,c,d,e,f,g,h}

R={(b,d),(b,e),(b,f),(c,d),(c,e),(c,f),(d,f),(e,f),(g,h)}∪IA

哈斯图实例第23页，共28页。例6：设A={a1,a2,...,an}是一个全序集，则其元素(A,≤)的哈斯图象一条链子一样。所以，全序关系也叫做线性序关系，全序集又称为线性序集。可以“从小到大”排列为：

ai1<ai2<...<ain全序关系的哈斯图第24页，共28页。

定义5设(X,≤)是一个偏序集，BX。如果存在一个元素aX使得对B中每个元素x有x≤a，则称a为B的一个上界。上界与下界的定义如果存在一个元素bX，使得对B的每一个元素x有b≤x，则称b为B的一个下界。①上界与下界都不一定存在。例7：令A={2,3,6,12,24,36}，A在整除关系“”下构成一个偏序集(A,)。{24,36}不存在上界,②上界与下界可能有很多元素6,12,24,36都是子集{2,3}的上界。{2,3}不存在下界,第25页，共28页。

定义6设(X,≤)是一个偏序集，BX。如果存在一个元素aB使得对B中每个元素x有x≤a，则称a是B中的最大元素。①最大元素一定是上界，最小元素一定是下界;最大与最小元素如果存在一个元素bB，使得对B的每一个元素x有b≤x，则称b是B中的最小元素。②有上下界不一定有最大与最小元素,③最大元素与最小元素若有一定是唯一的。因为上下界不一定在子集中;第26页，共28页。

定义7

设(X,≤)是一个偏序集，BX。如果B有上界且B的一切上界之集