《离散数学课件》7偏序关系.ppt

1、上节课内容 等价关系,等价关系 等价类 定义 性质 商集、集合的划分 等价关系和划分的对应,1,2/49,7.6 偏序关系和格,7.6.1 偏序关系、偏序集 7.6.2 哈斯（Hasse）图 7.6.3 链、反链、全序集 7.6.4 极大元、极小元、最大元、最小元 7.6.5 上界、下界、最小上界、最大下界 7.6.6 格,3/49,一、偏序关系,例 在实数集R上定义二元关系S， 对于任意的x, yR， (x，y) S当且仅当 xy。,R有自反性、 反对称性、 传递性.,4/49,偏序关系、偏序集,定义1 设A是一个非空集合，R是A上的一个二 元关系，若R有自反性、反对称性、传递性， 则称R是

2、A上的一个偏序关系，记作。 并称(A， )是一个偏序集。 如果（x, y), 则记作 xy, 读作 x“小于或 等于”y。,例1 A=1, 2, 3, 4 R=(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,4) R是A上一个偏序关系。,5/49,例2 (p109),设Z+=nZn0，即Z+是正整数的集合。 在Z+上定义一个二元关系R如下: 对于任意的x,yZ+， (x,y)R当且仅当x|y。 证明(Z+，R)是偏序集,6/49,例2 (p109)证明(Z+，R)是偏序集,（1）对于任意的xZ+,显然有x|x,所以(x,x)R,即R是自反

3、的。 （2）对于任意的x,yZ+,若(x,y)R,且(y,x)R，则 x|y,即存在nZ+,y=nx 且 y|x,即存在mZ+,x=my，所以x=mnx，而n,mZ+，所以只有n=m=1， 即x=y时才有(x,y)R,且(y,x)R ，即R有反对称性。 （3）对于任意的x,y,zZ+,若(x,y)R,且(y,z)R；则由(x,y)R,得x|y,即n0Z+，使得y=xn0; 再由(y,x)R, 得y|x,即m0Z+，使得z=m0y。所以z=m0n0 x，即 x|z，所以(x,z) R, 即R有传递性。 综上所述, R是Z+上偏序关系，即(Z+，R)是偏序集。,对于任意的x,yZ+，(x,y)R当

4、且仅当x|y。,7/49,例3 设A是任意一个集合， (A)是A的幂集合， 在 (A)上建立一个二元关系R: 对于任意的x,y (A)， (x,y) R 当且仅当xy。 不难证明(A)，R)也是一个偏序集。,8/49,例,在实数集R上定义二元关系S， 对于任意的x，yR， (x，y) S当且仅当 xy。 可以证明 S是R上的一个偏序关系。,在实数集R上定义二元关系S， 对于任意的x，yR， (x，y) S当且仅当 xy。 可以证明 S是R上的一个偏序关系。,集合A上的恒等关系 IA 是A上的偏序关系.,9/49,关于记号 ,对于一个偏序关系，往往用记号“”来表示。 若(a，b) ，记为a b，

5、读做“ a小于等于b”。 一个偏序集，通常用符号(A，)来表示。,10/49,注意,偏序关系“a小于等于b”，并不意味着平时意义上的a小于等于b。 一个集合上可以定义不同的偏序关系，得到不同的偏序集。 还要说明一下，一个偏序集(A， )，包含集合A与集合A上的偏序关系。 不允许x(A，)出现， 而仅有xA，（x，y）。 即谈到元素是从A中取，讲到关系是在 中取。,11/49,覆盖,设(A， )是一个偏序集， A是一个有限集，|A|=n。对于任意的x，yA，且xy， 假设(x, y) ，即 x y。 如果对于zA， 由x z，且 z y，一定能够推出x=z或y=z， 那么我们说 y覆盖x。,设R

6、为非空集合A上的偏序关系, x, yA, 如果 x y且不存在 zA 使得 x z y, 则称 y 覆盖x.,12/49,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不覆盖1,1,2,3,4,哈斯图,13/49,二、哈斯图（Hasse Diagram),设(A， )是一个偏序集， A是一个有限集，|A|=n。 可以用一个图形来表示偏序集（A，）， 这个图形有 n个顶点，每一个顶点表示A中一个元素， 两个顶点 x与y，若有y覆盖x，则点x在点y的下方，且两点之间有

7、一条直线相连结。,哈斯图：利用偏序自反、反对称、传递性简化的关系图,14/49,例,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) 显然 b覆盖a, e覆盖a c覆盖b d覆盖c d覆盖e,a,b,c,d,e,特点： 每个结点没有环， 两个连通的结点之间的有序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边。,16,哈斯图实例,例 ,17/49,例 试画出哈斯图,设A= 1, 2, 3, 4, 1

8、,2, 1,5, 3,6, 4,6, 0,3,6, 1,5,8, 0,3,4,6 ,R是A上的一个偏序关系: 对于任意的x,yA，(x,y) R当且仅当xy。,18,A=a, b, c, d, e, f, g, h R=, ,IA,哈斯图实例,例 已知偏序集 的哈斯图如右图所示, 试求出集合A和关系 R的表达式.,19,注意事项： 1、不出现三角形； 2、不出现水平线段； 3、尽量减少交叉线。,20/49,可比、不可比,设(A，)是一个偏序集，对于任意的x, yA，若xy或者yx， 则说 x与y可比，否则说 x与y不可比。,例给出如图所示的偏序集。 2与1、2与4等都是可比的， 而2与3、与都

9、是不可比的。,21/49,三、链 、反链,设(A，)是一个偏序集， B是A的一个子集。 如果中任意两个元素都可比, 说(B，)是一条链。 (2) 如果中任意两个元素都不可比, 说(B，)是一条反链。,22/49,例给出如图所示的偏序集,( a, b, c, d , ) 链 ( a, d, e , ) 链 ( b, e , ) 反链 ( c, e , ) 反链,23/49,全序集,设(A，)是一个偏序集， 如果它本身就是一条链， 那么称之为全序集，并称 为全序关系。,例A= a, b, c, d, e = (a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,

10、c), (a,d), (a,e), (b,c), (b,d), (c,d), (e,d) , (b,e), (e,c),25/49,四、偏序集中的特定元素,设(A，)是一个偏序集，BA, yB. 若x (xBx y) 成立, 则称 y 为B的极小元. 若x (xBy x) 成立, 则称 y 为B的极大元.,1、极大元、极小元,26/49,例给出如图所示的偏序集。 在1，2中，1是极小元， 2是极大元 在1，2，3中，1是极小元， 2、3是极大元 在1，2，3，4中，1是极小元， 3和4是极大元。,27/49,设(A，)是一个偏序集，BA, yB. 若x(xByx) 成立, 则称 y 为 B 的

11、最小元. 若x(xBxy) 成立, 则称 y 为 B 的最大元.,2、最大元、最小元,28/49,一个有限的偏序集，一定有极大元和极小元，但不一定有最大元和最小元。,例给出如图所示的偏序集。 1是最小元，也是极小元， 3和4是极大元，无最大元。,29/49,例 考察如图所示偏序集最小元与最大元,(a)无最大元 (c)表示的偏序集没有最小元与最大元 (b)和(d)表示的偏序集有最小元与最大元,(a) (b) (c) (d),极大、极小与最大最小元的找法： 1、孤立点。 既是极大元也是极小元。 若图中有孤立点，则必无最大、最小元。 2、除孤立点外， 其他极小元是图中所有向下通路的终点； 其他极大元

12、是图中所有向上通路的终点。 3、若极小元唯一则其为最小元； 若极大元唯一则其为最大元；,例 找出极大、极小元与最大、最小元,极小：1 极大：5，6，7，8，9 最小：1 最大：无,极小： 极大：a，b，c 最小： 最大：a，b，c,32/49,设(A，)是一个偏序集， BA, yA。 若x(xBxy) 成立, 则称 y 为B的上界 若x(xByx) 成立, 则称 y 为B的下界,3、上界、下界,33/49,例给出如图所示的偏序集。 h、i、j和k都是f，g的上界， c、d、a为其下界,34/49,设(A，)是一个偏序集，BA, yA. 令Cy | y为B的上界, 则称C的最小元为B的最小上界 或 上确界. 令Dy | y为B的下界, 则称D的最大元为B的最大下界 或 下确界.,4、上确界、下确界,35/49,例 给出如图所示的偏 序集。 b，d的上界是h和f 下界是a； 上确界是f，下确界是a。,1、B中的元素向上走共同能到达的即为上界， 上界中的最大元即为上确界； 2、B中元素向下走共同能到达的为下界， 下界中的最小元即为下确界。,36,实例,例 设偏序