《《离散数学课件》7偏序关系》由会员分享，可在线阅读，更多相关《《离散数学课件》7偏序关系（39页珍藏版）》请在金锄头文库上搜索。
1、等价关系等价关系等价类等价类定义定义性质性质商集、集合的划分商集、集合的划分等价关系和划分的对应等价关系和划分的对应12021/6/47.6 偏序关系和格偏序关系和格7.6.1 偏序关系、偏序集偏序关系、偏序集 7.6.2 哈斯（哈斯（Hasse）图）图 7.6.3 链、反链、全序集链、反链、全序集 7.6.4 极大元、极小元、最大元、最小元极大元、极小元、最大元、最小元 7.6.5 上界、下界、最小上界、最大下界上界、下界、最小上界、最大下界 7.6.6 格格 2一、偏序关系一、偏序关系例例 在实数集在实数集R上定义二元关系上定义二元关系S，对于任意的对于任意的x, y R， (x，y) S
2、当且仅当当且仅当 xy。R有自反性、有自反性、 反对称性、反对称性、 传递性传递性.3偏序关系、偏序集偏序关系、偏序集定义定义1 设设A是一个非空集合，是一个非空集合，R是是A上的一个二上的一个二元关系，若元关系，若R有自反性、有自反性、反反对称性、传递性，对称性、传递性，则称则称R是是A上的一个上的一个偏序关系偏序关系，记作记作 。 并称并称(A， )是一个是一个偏序集偏序集。 如果如果（x,y),则记作则记作x y,读作读作x“小于或小于或等于等于”y。例例1 A=1, 2, 3, 4 R=(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (
3、2,4) R是是A上一个偏序关系。上一个偏序关系。4例例2 (p109)设设Z+=n Zn0，即，即Z+是正整数的集合。是正整数的集合。在在Z+上定义一个二元关系上定义一个二元关系R如下如下: 对于任意的对于任意的x,y Z+， (x,y) R当且仅当当且仅当x|y。证明证明(Z+，R)是偏序集是偏序集5例例2 (p109)证明证明(Z+，R)是偏序集是偏序集（1）对于任意的）对于任意的x Z+,显然有显然有x|x,所以所以(x,x) R,即即R是是自自反反的。的。（2）对于任意的）对于任意的x,y Z+,若若(x,y) R,且且(y,x) R，则，则 x|y,即即存在存在n Z+,y=nx
4、且且 y|x,即存在即存在m Z+,x=my，所以，所以x=mnx，而，而n,m Z+，所以只有，所以只有n=m=1， 即即x=y时才有时才有(x,y) R,且且(y,x) R ，即，即R有有反对称性反对称性。（3）对于任意的）对于任意的x,y,z Z+,若若(x,y) R,且且(y,z) R；则由；则由(x,y) R,得得x|y,即即 n0 Z+，使得，使得y=xn0; 再由再由(y,x) R, 得得y|x,即即m0 Z+，使得，使得z=m0y。所以。所以z=m0n0x，即即 x|z，所以，所以(x,z) R, 即即R有有传递性传递性。综上所述综上所述, R是是Z+上偏序关系，即上偏序关系，
5、即(Z+，R)是偏序集。是偏序集。 对于任意的对于任意的x,y Z+，(x,y) R当且仅当当且仅当x|y。6例例3 设设A是任意一个集合，是任意一个集合， (A)是是A的幂集合，的幂集合，在在 (A)上建立一个二元关系上建立一个二元关系R: 对于任意的对于任意的x,y (A)， (x,y) R 当且仅当当且仅当x y。不难证明不难证明(A)，R)也是一个偏序集。也是一个偏序集。7例例在实数集在实数集R上定义二元关系上定义二元关系S， 对于任意的对于任意的x，y R， (x，y) S当且仅当当且仅当 xy。 可以证明可以证明 S是是R上的一个偏序关系。上的一个偏序关系。在实数集在实数集R上定义
6、二元关系上定义二元关系S， 对于任意的对于任意的x，y R， (x，y) S当且仅当当且仅当 xy。 可以证明可以证明 S是是R上的一个偏序关系。上的一个偏序关系。集合集合A上的恒等关系上的恒等关系IA 是是A上的偏序关系上的偏序关系.8关于记号关于记号 u 对于一个偏序关系，往往用记号对于一个偏序关系，往往用记号“ ”来表示。来表示。u 若若(a，b) ，记为，记为a b，读做，读做“ a小于等于小于等于b”。u 一个一个偏序集，通常用符号偏序集，通常用符号(A， )来表示来表示。9注意注意n偏序关系偏序关系“a小于等于小于等于b”，并不意味着平时，并不意味着平时意义上的意义上的a小于等于小
7、于等于b。n一个集合上可以定义不同的偏序关系，得到一个集合上可以定义不同的偏序关系，得到不同的偏序集。不同的偏序集。n还要说明一下，一个偏序集还要说明一下，一个偏序集(A， )，包含集，包含集合合A与集合与集合A上的偏序关系上的偏序关系 。 不允许不允许x (A， )出现，出现， 而仅有而仅有x A，（，（x，y） 。 即谈到元素是从即谈到元素是从A中取，讲到关系是在中取，讲到关系是在 中取。中取。10覆盖覆盖设设(A， )是一个偏序集，是一个偏序集， A是一个有限集，是一个有限集，|A|=n。对于任意的。对于任意的x，y A，且，且xy，假设假设(x, y) ，即，即 x y。如果对于如果对
8、于z A，由由x z，且，且 z y，一定能够推出，一定能够推出x=z或或y=z，那么我们说那么我们说 y覆盖覆盖x。设设R为非空集合为非空集合A上的偏序关系上的偏序关系,x,yA,如如果果x y且不存在且不存在z A 使得使得x z y,则称则称y 覆盖覆盖x.11 A=1, 2, 3, 4 =(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,4) 显然显然 2覆盖覆盖1 3覆盖覆盖1 4覆盖覆盖2，但，但4不覆盖不覆盖11234哈斯图哈斯图12二、哈斯图（二、哈斯图（Hasse Diagram)设设(A， )是一个偏序集，是一个偏序集，
9、 A是一个有限集，是一个有限集，|A|=n。可以用一个图形来表示偏序集（可以用一个图形来表示偏序集（A， ），），这个图形有这个图形有 n个顶点，每一个顶点表示个顶点，每一个顶点表示A中一中一个元素，个元素，两个顶点两个顶点 x与与y，若有，若有y覆盖覆盖x，则点，则点x在点在点y的的下方，且两点之间有一条直线相连结。下方，且两点之间有一条直线相连结。哈斯图哈斯图：利用偏序自反、反对称、传递性：利用偏序自反、反对称、传递性简化的关系图简化的关系图13例例A=a, b, c, d, e =(a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d)
10、, (a,e), (b,c), (b,d), (c,d), (e,d) 显然显然 b覆盖覆盖a, e覆盖覆盖a c覆盖覆盖b d覆盖覆盖c d覆盖覆盖eabcde14特点：特点：每个结点没有环，每个结点没有环，两个连通的结点之间的有序关系通过两个连通的结点之间的有序关系通过结点位置的高低表示，位置低的元素的顺结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连序在前，具有覆盖关系的两个结点之间连边。边。15哈斯图实例哈斯图实例例例162021/6/4例 试画出哈斯图试画出哈斯图设设A= 1, 2, 3, 4, 1,2, 1,5, 3,6, 4,6, 0,3,6, 1,5,8
11、, 0,3,4,6 R是是A上的一个偏序关系上的一个偏序关系: 对于任意的对于任意的x,y A，(x,y) R当且仅当当且仅当x y。121,51,2343.64,61,5,80,3,60,3,4,617A=a,b,c,d,e,f,g,hR=,IA哈斯图实例哈斯图实例例例已知偏序集已知偏序集的哈斯图如右图所示的哈斯图如右图所示,试求出集合试求出集合A和关系和关系R的表达式的表达式.182021/6/4注意事项：注意事项： 1、不出现三角形；不出现三角形； 2、不出现水平线段；不出现水平线段； 3、尽量减少交叉线。尽量减少交叉线。19可比、不可比可比、不可比设设(A， )是一个偏序集，对于任意的
12、是一个偏序集，对于任意的x, y A，若，若x y或者或者y x，则说则说 x与与y可比可比，否则说，否则说 x与与y不可比不可比。例给出如图所示的偏序集。例给出如图所示的偏序集。2与与1、2与与4等都是可比的，等都是可比的， 而而2与与3、与都是不可比的。、与都是不可比的。123420三、链三、链 、反链、反链 设设(A， )是一个偏序集，是一个偏序集， B是是A的一个的一个子集子集。(1)如果中任意两个元素都可比如果中任意两个元素都可比, 说说(B， )是一条是一条链链。(2) 如果中任意两个元素都不可比如果中任意两个元素都不可比, 说说(B， )是一条是一条反链反链。21例给出如图所示的
13、偏序集例给出如图所示的偏序集abcde( a, b, c, d , ) 链链( a, d, e , ) 链链 ( b, e , ) 反链反链 ( c, e , ) 反链反链22全序集 设设(A， )是一个偏序集，是一个偏序集，如果它本身就是一条链，如果它本身就是一条链，那么称之为那么称之为全序集全序集，并称，并称 为为全序关系全序关系。23例例A= a, b, c, d, e = (a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (c,d), (e,d) abcdeabcde, (b,e),
14、 (e,c)24四、偏序集中的特定元素四、偏序集中的特定元素设设(A， )是一个偏序集，是一个偏序集，B A,yB.u若若x (xBx y)成立成立,则称则称y 为为B的的极极小元小元.u若若x (xBy x)成立成立,则称则称y 为为B的的极极大元大元.1、极大元、极小元极大元、极小元25例给出如图所示的偏序集。例给出如图所示的偏序集。在在1，2中，中，1是极小元，是极小元， 2是极大元是极大元在在1，2，3中，中，1是极小元，是极小元， 2、3是极大元是极大元在在1，2，3，4中，中，1是极小元，是极小元， 3和和4是极大元。是极大元。123426设设(A， )是一个偏序集，是一个偏序集，
15、B A,yB.u若若 x(xBy x)成立成立,则称则称y 为为B 的的最最小元小元.u若若 x(xBx y)成立成立,则称则称y 为为B 的的最最大元大元.2、最大元、最小元最大元、最小元27一个有限的偏序集，一定有极大元和极小元，一个有限的偏序集，一定有极大元和极小元，但不一定有最大元和最小元。但不一定有最大元和最小元。例给出如图所示的偏序集。例给出如图所示的偏序集。1是最小元，也是极小元，是最小元，也是极小元，3和和4是极大元，无最大元。是极大元，无最大元。123428例例 考察如图所示偏序集最小元与最大元考察如图所示偏序集最小元与最大元u (a)无最大元无最大元u (c)表示的偏序集没
16、有最小元与最大元表示的偏序集没有最小元与最大元u (b)和和(d)表示的偏序集有最小元与最大元表示的偏序集有最小元与最大元1234abcdeabcdefghijkabcdfegh (a) (b) (c) (d)29极大、极小与最大最小元的找法：极大、极小与最大最小元的找法：1、孤立点。孤立点。 既是极大元也是极小元。既是极大元也是极小元。 若图中有孤立点，则必无最大、最小元。若图中有孤立点，则必无最大、最小元。2、除孤立点外，除孤立点外， 其他极其他极小小元是图中所有元是图中所有向下向下通路的终点；通路的终点； 其他极其他极大大元是图中所有元是图中所有向上向上通路的终点。通路的终点。3、若极小
17、元唯一则其为最小元；若极小元唯一则其为最小元； 若极大元唯一则其为最大元；若极大元唯一则其为最大元；30例例 找出极大、极小元与最大、最小元找出极大、极小元与最大、最小元极小：极小：1极大：极大：5，6，7，8，9最小：最小：1最大：无最大：无极小：极小：极大：极大：a，b，c最小：最小：最大：最大：a，b，c31设设(A， )是一个偏序集，是一个偏序集， B A,y A。u若若 x(xBx y)成立成立,则称则称y 为为B的的上界上界u若若 x(xBy x)成立成立,则称则称y 为为B的的下界下界3、上界、下界上界、下界32例给出如图所示的偏序集。例给出如图所示的偏序集。 h、i、j和和k都
18、是都是f，g的上界，的上界， c、d、a为其下界为其下界 abcdefghijk33设设(A， )是一个偏序集，是一个偏序集，B A,y A.u令令Cy |y为为B的上界的上界,则称则称C的最小元为的最小元为B的的最小上界最小上界或或上确界上确界.u令令Dy |y为为B的下界的下界,则称则称D的最大元为的最大元为B的的最大下界最大下界或或下确界下确界.4、上确界、下确界上确界、下确界34例例 给出如图所示的偏给出如图所示的偏 序集。序集。 b，d的上界是的上界是h和和f 下界是下界是a； 上确界是上确界是f，下确界是下确界是a。abcdfegh1、B中的元素向上走共同能到达的即为上界，中的元素
19、向上走共同能到达的即为上界， 上界中的最大元即为上确界；上界中的最大元即为上确界；2、B中元素向下走共同能到达的为下界，中元素向下走共同能到达的为下界， 下界中的最小元即为下确界。下界中的最小元即为下确界。35实例实例例例设偏序集设偏序集如下图所示，求如下图所示，求A 的极小元、最的极小元、最小元、极大元、最大元小元、极大元、最大元.设设Bb,c,d,求求B 的下界、的下界、上界、下确界、上确界上界、下确界、上确界.极小元：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B无下界和下确界无下界和下确界,上界有上界有d 和和f,上确界为上确界为d.362021/6/4偏序关系（自反、反对称、传递）偏序关系（自反、反对称、传递）哈斯图哈斯图画法画法从图写出关系从图写出关系特定元素特定元素极大、极小元与最大、最小元极大、极小元与最大、最小元上界、下界与上、下确界上界、下界与上、下确界372021/6/4部分资料从网络收集整理而来，供大家参考，感谢您的关注！
