离散数学等价关系与偏序关系(1)

1、集合与图论精选ppt1第第9节节 等价关系与偏序关系等价关系与偏序关系主要内容：主要内容： 等价关系等价关系 偏序关系偏序关系集合与图论精选ppt2 定义定义1 集合集合X上的二元关系上的二元关系R称为称为等价关系等价关系，如果，如果R同时具有以下三个性质：同时具有以下三个性质： 例例1：集合集合X上的恒等关系是不是上的恒等关系是不是X上的等价关系？上的等价关系？1. R是自反的，即是自反的，即 x X，xRx;2. R是对称的，即如果是对称的，即如果xRy，则，则yRx;3. R是传递的，即如果是传递的，即如果xRy，yRz，则，则xRz。是是X上的等价关系。上的等价关系。1 等价关系等价关

2、系集合与图论精选ppt3等价关系实例等价关系实例例例2：考虑整数集考虑整数集Z上的模上的模n同余关系。同余关系。例例4：设设f:XY，Ker(f)=(x,y)x,y X，且，且f(x)=f(y)。Ker(f)是是X上的等价关系上的等价关系。例例3：实数集上的实数集上的“”、“”、“”、“”、“”都不都不是是R上的等价关系。上的等价关系。是等价关系。是等价关系。集合与图论精选ppt4例例5：设设 A=1, 2, , 8, 如下定义如下定义 A上的关系上的关系R： R=(x,y)| x,y Axy (mod 3)R 的关系图如下：的关系图如下：等价关系的关系图等价关系的关系图集合与图论精选ppt5

3、 定义定义2 设设R是是X上的一个等价关系，上的一个等价关系，x X，X的的子集子集Ex=yy X且且xRy称为称为x关于关于R的的等价类等价类，或简，或简记为记为x的等价类。的等价类。x的等价类常记为的等价类常记为x，即，即x=yy X且且xRy。例例5：设设 A=1, 2, , 8, 如下定义如下定义 A上的关系上的关系R： R=(x,y)| x,y Axy (mod 3)等价类的定义等价类的定义A= 1, 2, , 8 上模上模 3 等价关系的等价类：等价关系的等价类： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6集合与图论精选ppt6等价类的性质等价类的性质(3) x

4、, y X, 如果如果(x, y) R, 则则 xy=。定理定理1 设设R是非空集合是非空集合X上的等价关系上的等价关系, 则则 (1) x X, x 。(2) x, y X, 如果如果(x, y) R, 则则 x=y。 (4) ，即所有等价类的并集就是，即所有等价类的并集就是X。集合与图论精选ppt7 定义定义3 设设X为非空集合，为非空集合，X的若干个子集形成的集的若干个子集形成的集族族 称为称为X的一个的一个划分划分，如果，如果 具有性质：具有性质： 集合的划分集合的划分 如果如果 是是X的一个划分，则当的一个划分，则当 =k时，时， 被称为被称为X的的一个一个k-划分划分。(2) x,

5、y ，若，若x y，则，则xy=;(1) ；(3) 。 称称 中的元素为中的元素为X的的划分块划分块。集合与图论精选ppt8例例6：设设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 1和和 2是是A的划分，其他都不是的划分，其他都不是A的划分。的划分。实实 例例集合与图论精选ppt9 定理定理1 设设R是是X上的一个等价关系，则上的一个等价关系，则R的所有等的所有等价类的集合是价类的集合是X的一个划分。的一

6、个划分。等价关系与集合的划分等价关系与集合的划分 定理定理2 设设 是集合是集合X的一个划分，令的一个划分，令 R =(x,y) | x,y Xx与与y在在 的同一划分块中的同一划分块中则则R是是X上的一个等价关系，并且上的一个等价关系，并且 就是就是R的等价类之集。的等价类之集。注：注： 由定理由定理1、2可得：可得：X上的等价关系与上的等价关系与X的划分的划分是一一对应的，并且互相确定。是一一对应的，并且互相确定。集合与图论精选ppt10 定义定义4 设设R是是X上的等价关系，由上的等价关系，由R所确定的所确定的X的的划分也就是划分也就是R的所有等价类之集称为的所有等价类之集称为X对对R的

7、的商集商集，并记并记X/R。 即：即：X/R=x x X，x是是x的等价类的等价类。 等价关系等价关系R确定的划分是确定的划分是R的所有等价类之集的所有等价类之集 xx X商商 集集集合与图论精选ppt11例例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 实实 例例集合与图论精选ppt12例例8：给出给出A1,2,3上所有的等价关系。上所有的等价关系。求解思路：先

8、做出求解思路：先做出A的所有划分的所有划分, 然后根据划分写出然后根据划分写出 对应的等价关系。对应的等价关系。 实实 例例集合与图论精选ppt13实实 例例 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上有多少个上有多少个等价关系？等价关系？集合与图

9、论精选ppt14定理定理4 设设R为为X上的一个二元关系，则上的一个二元关系，则 e(R)=(RR-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。等价关系的运算等价关系的运算集合与图论精选ppt15 定义定义1 集合集合X上

10、的二元关系上的二元关系R称为称为偏序关系偏序关系，如，如果果R同时满足以下三个性质：同时满足以下三个性质： 当抽象地讨论当抽象地讨论X上的偏序关系时，常用符号上的偏序关系时，常用符号“ ”表示偏序关系。如果表示偏序关系。如果x y，则读作，则读作“x小于或等于小于或等于y”。1. R是自反的；是自反的；2. R是反对称的；是反对称的；3. R是传递的。是传递的。约定约定x y且且x y时，就记为时，就记为xy。实实 例例集合与图论精选ppt18 定义定义3 集合集合X上的偏序关系上的偏序关系 叫做叫做全序关系全序关系，如果，如果 x,y X，x y与与y x至少有一个成立。全序关系也称为至少有

11、一个成立。全序关系也称为线性序关系线性序关系。X与全序关系与全序关系构成的二元组构成的二元组(X,)称为称为全全序集序集。 偏序集与全序集的主要区别在于全序集中任两个偏序集与全序集的主要区别在于全序集中任两个元素均可比较元素均可比较“大小大小”，而在偏序集中任意两个元素，而在偏序集中任意两个元素不一定都能比较大小。不一定都能比较大小。实数间的常用的实数间的常用的“小于或等于小于或等于”关系是不是全序关关系是不是全序关系系?全序关系与全序集全序关系与全序集 集合的包含关系与自然数间的整除关系是不是全集合的包含关系与自然数间的整除关系是不是全序关系序关系?是全序关系，相应的偏序集也是全序集。是全序

12、关系，相应的偏序集也是全序集。二者都不是全序关系。二者都不是全序关系。集合与图论精选ppt19 定义定义4 设设(X,)是一个偏序集，称是一个偏序集，称y盖住盖住x，如果，如果xy且对每个且对每个z X，若，若xzy，则，则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.集合与图论精选ppt2

13、0哈斯哈斯(Hasse)图图 首先偏序关系首先偏序关系是自反的，所以偏序关系的关系图是自反的，所以偏序关系的关系图中每个顶点都有一个环，因此可以省略每个顶点的环。中每个顶点都有一个环，因此可以省略每个顶点的环。 其次由于偏序关系是传递的，那么只要在前驱与其次由于偏序关系是传递的，那么只要在前驱与后继间联线即可。后继间联线即可。 最后由于反对称性，若最后由于反对称性，若xy，x y，则点，则点y画在画在x的上方，这样就不必用矢线了，按上述方法画出的图的上方，这样就不必用矢线了，按上述方法画出的图称为称为(X,)的的哈斯图哈斯图。 集合与图论精选ppt21特点：特点： (1)每个结点没有环每个结点

14、没有环; (2)两个连通的结点之间的序关系通过结点两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前位置的高低表示，位置低的元素的顺序在前; (3)具有覆盖关系的两个结点之间连边。具有覆盖关系的两个结点之间连边。 哈斯图哈斯图就是利用偏序的自反、反对称、传就是利用偏序的自反、反对称、传递性简化了的关系图。递性简化了的关系图。哈斯哈斯(Hasse)图的特点图的特点集合与图论精选ppt22例例4：( 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整除整除) (P(a, b, c), R )哈斯图实例哈斯图实例集合与图论精选ppt23 例例5：已知偏序集已知偏序集(

15、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 哈斯图实例哈斯图实例集合与图论精选ppt24例例6：设设A=a1,a2,.,an是一个全序集，是一个全序集，则其元素则其元素(A,)的哈斯图象一条链子一样。的哈斯图象一条链子一样。所以，全序关系也叫做线性序关系，所以，全序关系也叫做线性序关系，全序集又称为线性序集。全序集又称为线性序集。可以可以“从小到大从小到大”排列为：

16、排列为： ai1ai2.ain全序关系的哈斯图全序关系的哈斯图集合与图论精选ppt25 定义定义5 设设(X,)是一个偏序集，是一个偏序集，B X。如果存在一。如果存在一个元素个元素a X使得对使得对B中每个元素中每个元素x有有xa，则称，则称a为为B的一的一个个上界上界。上界与下界的定义上界与下界的定义 如果存在一个元素如果存在一个元素b X，使得对，使得对B的每一个元素的每一个元素x有有bx，则称，则称b为为B的一个的一个下界下界。上界与下界都不一定存在。上界与下界都不一定存在。例例7：令令A=2,3,6,12,24,36，A在整除关系在整除关系“ ”下构成下构成一个偏序集一个偏序集(A,

17、)。24,36不存在上界不存在上界,上界与下界可能有很多元素上界与下界可能有很多元素6,12,24,36都是子集都是子集2,3的上界。的上界。2,3不存在下界不存在下界,集合与图论精选ppt26 定义定义6 设设(X,)是一个偏序集，是一个偏序集，B X。如果存在一个。如果存在一个元素元素a B使得对使得对B中每个元素中每个元素x有有xa，则称，则称a是是B中的中的最最大元素大元素。最大元素一定是上界，最小元素一定是下界最大元素一定是上界，最小元素一定是下界;最大与最小元素最大与最小元素 如果存在一个元素如果存在一个元素b B，使得对，使得对B的每一个元素的每一个元素x有有bx，则称，则称b是

18、是B中的中的最小元素最小元素。 有上下界不一定有最大与最小元素有上下界不一定有最大与最小元素,最大元素与最小元素若有一定是唯一的。最大元素与最小元素若有一定是唯一的。因为上下界不一定在子集中因为上下界不一定在子集中;集合与图论精选ppt27 定义定义7 设设(X,)是一个偏序集，是一个偏序集，B X。如果。如果B有上有上界且界且B的一切上界之集有最小元素，则这个最小上界的一切上界之集有最小元素，则这个最小上界称为称为B的的上确界上确界，记为，记为supB。上确界与下确界的定义上确界与下确界的定义 如果如果B有下界且有下界且B的一切下界之集有最大元素，的一切下界之集有最大元素，则这个最大下界称为

19、则这个最大下界称为B的的下确界下确界，记为，记为infB。例例8：令令A=2,3,6,12,24,36，A在整除关系在整除关系“ ”下构成下构成一个偏序集一个偏序集(A,)。6,12,24,36都是子集都是子集2,3的上界。的上界。6是子集是子集2,3的上确界。的上确界。2,3,6,12都是子集都是子集24,36的下界。的下界。12是子集是子集24,36的下确界。的下确界。集合与图论精选ppt28A中有最大元素和最小元素吗？中有最大元素和最小元素吗？实实 例例例例9：令令A=2,3,6,12,24,36,A在整除关系在整除关系“ ”下构成一下构成一个偏序集个偏序集(A,)。 A中没有最大元素也没有最小元素。中没有最大元素也没有最小元素。 因为因为24与与36不可比，不可比，2与与3也不可比。也不可比。 但是但是A中没有比中没有比24和和36更大的元素，也没有比更大的元素，也没有比2与与3更小的元素。更小的元素。 称称24和和36都是极大元素都是极大元素,2与与3都是极小元素。都是极小元素。集合与图论精选ppt29 定义定义8 设设(X,)是一个偏序集，是一个偏序集，A X，A中元素中元素s称为称为A的的极大元素极大元素，如果，如果A中