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

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

2、，记作。 并称(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,例2 (p109),设Z+=nZn0，即Z+是正整数的集合。 在Z+上定义一个二元关系R如下: 对于任意的x,yZ+， (x,y)R当且仅当x|y。 证明(Z+，R)是偏序集,6,例2 (p109)证明(Z+，R)是偏序集,（1）对于任意的xZ+,显然有x|x,所以(x,x)R,即R是自反的。 （2）对于任意的x,yZ

3、+,若(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当且仅当x|y。,7,例3 设A

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

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

6、在 zA 使得 x z y, 则称 y 覆盖x.,12,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,二、哈斯图（Hasse Diagram),设(A， )是一个偏序集， A是一个有限集，|A|=n。 可以用一个图形来表示偏序集（A，）， 这个图形有 n个顶点，每一个顶点表示A中一个元素， 两个顶点 x与y，若有y覆盖x，则点x在点y的下方，且两点之间有一条直线相连结。,哈斯图：利用偏序自反、反对称、传递性简化的关系图,14

7、,例,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,例 试画出哈斯图,设A= 1, 2, 3, 4, 1,2, 1,5, 3,6, 4,6, 0,3,6, 1,5,8, 0,3,4,6 ,

8、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,可比、不可比,设(A，)是一个偏序集，对于任意的x, yA，若xy或者yx， 则说 x与y可比，否则说 x与y不可比。,例 给出如图所示的偏序集。 2与1、2与4等都是可比的， 而2与3、与都是不可比的。,21,三、链 、反链,设(A，)是一个偏序集， B是A的一个子集。 如果中

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

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

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

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