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

上节课内容等价关系等价关系等价类定义性质商集、集合的划分等价关系和划分的对应12/497.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,y∊R，(x，y)∊S当且仅当x≤y。R有自反性、反对称性、传递性.4/49偏序关系、偏序集定义1设A是一个非空集合，R是A上的一个二元关系，若R有自反性、反对称性、传递性，则称R是A上的一个偏序关系，记作≼。并称(A，≼)是一个偏序集。如果（x,y)∈≼,则记作x≼y,读作x“小于或等于”y。例1A={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+={n∊Z│n0}，即Z+是正整数的集合。在Z+上定义一个二元关系R如下:对于任意的x,y∊Z+，(x,y)∊R当且仅当x|y。证明(Z+，R)是偏序集6/49例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且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+上偏序关系，即(Z+，R)是偏序集。对于任意的x,y∊Z+，(x,y)∊R当且仅当x|y。7/49例3设A是任意一个集合，ρ(A)是A的幂集合，在ρ(A)上建立一个二元关系R:对于任意的x,y∊ρ(A)，(x,y)∊R当且仅当x⊆y。不难证明(ρ(A)，R)也是一个偏序集。8/49例在实数集R上定义二元关系S，对于任意的x，y∊R，(x，y)∊S当且仅当x≤y。可以证明S是R上的一个偏序关系。在实数集R上定义二元关系S’，对于任意的x，y∊R，(x，y)∊S’当且仅当x≥y。可以证明S’是R上的一个偏序关系。集合A上的恒等关系IA是A上的偏序关系.9/49关于记号≺对于一个偏序关系，往往用记号“≺”来表示。若(a，b)∊≺，记为a≺b，读做“a小于等于b”。一个偏序集，通常用符号(A，≺)来表示。10/49注意偏序关系“a小于等于b”，并不意味着平时意义上的a小于等于b。一个集合上可以定义不同的偏序关系，得到不同的偏序集。还要说明一下，一个偏序集(A，≺)，包含集合A与集合A上的偏序关系≺。不允许x∊(A，≺)出现，而仅有x∊A，（x，y）∊≺。即谈到元素是从A中取，讲到关系是在≺中取。11/49覆盖设(A，≺)是一个偏序集，A是一个有限集，|A|=n。对于任意的x，y∊A，且x≠y，假设(x,y)∊≺，即x≺y。如果对于∀z∊A，由x≺z，且z≺y，一定能够推出x=z或y=z，那么我们说y覆盖x。设R为非空集合A上的偏序关系,x,y∈A,如果x≺y且不存在zA使得x≺z≺y,则称y覆盖x.12/49A={1,2,3,4}≺={(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(1,4),(2,4)}显然2覆盖13覆盖14覆盖2，但4不覆盖11234哈斯图13/49二、哈斯图（HasseDiagram)设(A，≺)是一个偏序集，A是一个有限集，|A|=n。可以用一个图形来表示偏序集（A，≺），这个图形有n个顶点，每一个顶点表示A中一个元素，两个顶点x与y，若有y覆盖x，则点x在点y的下方，且两点之间有一条直线相连结。哈斯图：利用偏序自反、反对称、传递性简化的关系图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覆盖ac覆盖bd覆盖cd覆盖eabcde特点：每个结点没有环，两个连通的结点之间的有序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边。16哈斯图实例例{1,2,3,4,5,6,7,8,9},R整除P({a,b,c}),R17/49例试画出哈斯图设A={{1},{2},{3},{4},{1,2},{1,5},{3,6},{4,6},{0,3,6},{1,5,8},{0,3,4,6}}R是A上的一个偏序关系:对于任意的x,y∊A，(x,y)∊R当且仅当x⊆y。{1}{2}{1,5}{1,2}{3}{4}{3.6}{4,6}{1,5,8}{0,3,6}{0,3,4,6}18A={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哈斯图实例例已知偏序集A,R的哈斯图如右图所示,试求出集合A和关系R的表达式.19注意事项：1、不出现三角形；2、不出现水平线段；3、尽量减少交叉线。20/49可比、不可比设(A，≺)是一个偏序集，对于任意的x,y∊A，若x≺y或者y≺x，则说x与y可比，否则说x与y不可比。例给出如图所示的偏序集。2与1、2与4等都是可比的，而2与3、３与４都是不可比的。123421/49三、链、反链设(A，≺)是一个偏序集，B是A的一个子集。(1)如果Ｂ中任意两个元素都可比,说(B，≺)是一条链。(2)如果Ｂ中任意两个元素都不可比,说(B，≺)是一条反链。22/49例给出如图所示的偏序集abcde({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,c),(a,d),(a,e),(b,c),(b,d),(c,d),(e,d)}abcdeabcde,(b,e),(e,c)25/49四、偏序集中的特定元素设(A，≺)是一个偏序集，BA,y∈B.若x(x∈B∧x≺y)成立,则称y为B的极小元.若x(x∈B∧y≺x)成立,则称y为B的极大元.1、极大元、极小元26/49例给出如图所示的偏序集。在{1，2}中，1是极小元，2是极大元在{1，2，3}中，1是极小元，2、3是极大元在{1，2，3，4}中，1是极小元，3和4是极大元。123427/49设(A，≺)是一个偏序集，BA,y∈B.若x(x∈B→y≼x)成立,则称y为B的最小元.若x(x∈B→x≼y)成立,则称y为B的最大元.2、最大元、最小元28/49一个有限的偏序集，一定有极大元和极小元，但不一定有最大元和最小元。例给出如图所示的偏序集。1是最小元，也是极小元，3和4是极大元，无最大元。123429/49例考察如图所示偏序集最小元与最大元(a)无最大元(c)表示的偏序集没有最小元与最大元(b)和(d)表示的偏序集有最小元与最大元1234abcdeabcdefghijkabcdfegh(a)(b)(c)(d)极大、极小与最大最小元的找法：1、孤立点。既是极大元也是极小元。若图中有孤立点，则必无最大、最小元。2、除孤立点外，其他极小元是图中所有向下通路的终点；其他极大元是图中所有向上通路的终点。3、若极小元唯一则其为最小元；若极大元唯一则其为最大元；例找出极大、极小元与最大、最小元极小：1极大：5，6，7，8，9最小：1最大：无极小：φ极大：{a，b，c}最小：φ最大：{a，b，c}32/49设(A，≺)是一个偏序集，BA,yA。若x(x∈B→x≼y)成立,则称y为B的上界若x(x∈B→y≼x)成立,则称y为B的下界3、上界、下界33/49例给出如图所示的偏序集。h、i、j和k都是{f，g}的上界，c、d、a为其下界abcdefghijk34/49设(A，≺)是一个偏序集，BA,yA.令C＝{y|y为B的上界},则称C的最小元为B的最小上界或上确界.令D＝{y|y为B的下界},则称D的最大元为B的最大下界或下确界.4、上确界、下确界35/49例给出如图所示的偏序集。◆{b，d}的上界是h和f下界是a；上确界是f，下确界是a。abcdfegh1、B中的元素向上走共同能到达的即为上界，上界中的最大元即为上确界；2、B中元素向下走共同能到达的为下界，下界中的最小元即为下确界。36实例例设偏序集A,≼如下图所示，求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、下确界、上确界.极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B无下界和下确界,上界有d和f,上确界为d.小结偏序关系偏序关系（自反、反对称、传递）哈斯图画法从图写出关系特定元素极大、极小元与最大、最小元上界、下界与上、下确界37