离散数学二元关系.ppt

《离散数学二元关系.ppt》由会员分享，可在线阅读，更多相关《离散数学二元关系.ppt（107页珍藏版）》请在三一办公上搜索。

1、2023/6/23,1,第7章 二元关系,7.1 有序对与笛卡儿积7.2 二元关系7.3 关系的运算7.4 关系的性质7.5 关系的闭包7.6 等价关系和划分7.7 偏序关系,2023/6/23,2,7.1 有序对与笛卡尔积,7.1.1 有序对的定义7.1.2 集合的笛卡尔积7.1.3 有序 n 元组和 n 阶笛卡尔积,2023/6/23,3,7.1.1 有序对的定义,定义7.1：两个元素x,y组成的有序序列x,y，称为一个有序对（序偶、二元组）。例：直角坐标系中点的坐标x,y日期的表示：y,m,2023/6/23,4,7.1.1 有序对的定义,性质：当x y时，x，y y，xx，y u，v

2、xuyv例7.1：，求 x,y。解：x25,2xy 4 x3,y 2,2023/6/23,5,7.1.2 集合的笛卡尔积,定义7.2：集合A与B的笛卡儿乘积 ABx,y|xAyB例：设Aa,b，B 0，1，2，C，计算AB，BA，AC，AA。解：ABa,0,a,1,a,2,b,0,b,1,b,2BA0,a,0,b,1,a,1,b,2,a,2,bAC AA a,a,a,b,b,a,b,b（AA可记作A2）例7.2：A=1，2,求P(A)A。,2023/6/23,6,7.1.2 集合的笛卡尔积,集合的笛卡儿积的性质：性质1：若|A|m,|B|n,则|AB|mn性质2：对任意集合 A，有：AA 性质

3、3：一般地ABBA，即笛卡儿乘积不满足交换律。问题：什么情况下ABBA？（ABA B）什么情况下ABBA？（ABA B）,2023/6/23,7,7.1.2 集合的笛卡尔积,例3：设Aa，b，B1，2，3，Cp，q，计算(AB)C，A(BC)。解：(AB)C,p,q,p,q,p,q,p,q,p,q,p,q。,2023/6/23,8,7.1.2 集合的笛卡尔积,A(B C)a,a,a,a,a,a,b,b,b,b,b,b,集合的笛卡儿积的性质性质4：一般地(AB)CA(BC)，即集合的笛卡儿积不满足结合律。性质5：AC BD AB CD,2023/6/23,9,7.1.2 集合的笛卡尔积,性质6：

4、笛卡儿积对、运算满足分配律A（BC）（AB）（AC）A（BC）（AB）（AC）（AB）C（AC）（BC）（AB）C（AC）（BC）,2023/6/23,10,7.1.2 集合的笛卡尔积,证明：A（BC）（AB）（AC）证：任取x，yx，yA（BC）xAyBCxA（yB yC）（xAyB）（xA yC）（x，yAB）（x，yAC）x，y（AB）（AC）所以，A（BC）（AB）（AC）成立。,2023/6/23,11,7.1.2 集合的笛卡尔积,证明：（AB）C（AC）（BC）证：任取x，yx，y（AB）Cx（A B）yCxAxB yC（xAyC）（xB yC）（x，yAC）（x，yBC）x，y（

5、AC）（BC）所以，（AB）C（AC）（BC）成立。,2023/6/23,12,7.1.3 有序 n 元组和 n 阶笛卡尔积,定义：n个元素x1，x2，xn组成的有序序列,记做：x1,x2,xn称为n重组（n元序偶、n元组）。约定:x1，x2，,xn-1,xn=,xn性质：x1,x2,xn y1,y2,yn xi yi(i=1,2,n),2023/6/23,13,7.1.3 有序 n 元组和 n 阶笛卡尔积,定义4.4：集合A1、A2、An的笛卡儿乘积A1A2Anx1，x2，xn|xiAi i1,2,n注意：A1A2An1An（A1A2An1）An一般地：若A1A2An A时，上式简记为：An

6、,2023/6/23,14,7.2 二元关系,7.2.1 二元关系的基本定义7.2.2 二元关系的表示,2023/6/23,15,7.2.1 二元关系的基本定义,关系数的,关系;VI R;计算机程序的输入与输出联系；数据库的数据特性联系等。集合论为刻划这种联系提供了一种数学模型关系(Relation)。,7.2.1 二元关系的基本定义,定义7.3如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.例如：R,S,3,4.,2023/6/23,16,2023/6/23,17,7.2.1 二元关系的基本定义,例:(1)R|x

7、,yN,xy3,(2)C|x,yR,x2y21(3)R|x,y,zR,x2yz3(4)5元关系的实例数据库实体模型,2023/6/23,18,7.2.1 二元关系的基本定义,定义7.4 设A,B为集合,R AB，称R为A到B的二元关系；R AA，称R为A上的关系。例：若 Aa,b,B1,则：（1）写出A到B的所有二元关系。（2）写出A上的所有二元关系。,2023/6/23,19,7.2.1 二元关系的基本定义,一般地：若|A|m,|B|n|AB|mn,AB 的子集有2mn个,从A到B有2mn个不同的二元关系.R，称R为空关系；R AB，称R为全域关系 若|A|n|AA|n2,AA 的子集有2n

8、2个,A上有2n2不同的二元关系.R，称R为A上空关系R AA，称R为A上的全域关系，记做EA;R|xA，称R为A上的相等关系，记做IA;,2023/6/23,20,7.2.1 二元关系的基本定义,常见的几种特殊的二元关系|集合之间的关系：,2023/6/23,21,7.2.2 二元关系的表示,1.集合表示法2.关系矩阵(matrix of relation)设Aa1,a2,am，Bb1,b2,bn，R是A到B的一个二元关系，令：,称：MR为R的关系矩阵。,2023/6/23,22,7.2.2 二元关系的表示,例1：设Aa,b,c,B0,1,2,3,R,写出MR。,2023/6/23,23,7

9、.2.2 二元关系的表示,例2：设A 1,2,3,4,A上的关系R,4,2,写出MR。,MR,2023/6/23,24,7.2.2 二元关系的表示,例3 设A 1,2,3,4,A上的二元关系R|x y,写出MR。,MR,2023/6/23,25,7.2.2 二元关系的表示,3.关系图R为A到B的二元关系；以AB的每个元素为一个结点，对每个R，均连一条从结点x到y的有向边，得到一个有向图，称为R的关系图，记为GR。,2023/6/23,26,7.2.2 二元关系的表示,例1 设Aa,b,c,B0,1,2,3,R,画出GR。,2023/6/23,27,7.2.2 二元关系的表示,例2 设A 1,2

10、,3,4,A上的二元关系R|xy,画出GR。,2023/6/23,28,7.2.2 二元关系的表示,练习：Aa,b,c,d,R,求R的关系矩阵 MR和关系图 GR。,2023/6/23,29,7.2.2 二元关系的表示,关系的表示方法关系R的集合表达式关系矩阵MR关系图GR三者均可以唯一相互确定。,2023/6/23,30,7.3 关系的运算,7.3.1 关系的定义域、值域 和 域7.3.2 关系的逆7.3.3 关系的右复合7.3.4 关系运算的性质7.3.5 关系的幂,2023/6/23,31,7.3.1 关系的定义域、值域 和 域,定义7.6：dom（R）=x|y（xRy）ran（R）=y

11、|x（xRy）fld（R）=dom（R）ran（R）例：设Ra,1,b,2,a,3计算dom（R）,ran（R）,域fld（R）,2023/6/23,32,7.3.2 关系的逆运算,定义7.7关系R的逆关系 R-1=|xRy例：R,则：R-1,问题：已知MR，如何计算MR-1?已知GR，如何计算GR-1?,2023/6/23,33,7.3.3 关系的右复合,定义7.8关系F,G的右复合,关系复合的求解方法集合表达式图示法关系矩阵,2023/6/23,34,7.3.3 关系的右复合,例：R=,S=,法1：RS=SR=,法2：利用图示方法求合成,2023/6/23,35,7.3.3 关系的右复合,

12、法3：关系矩阵相乘的方法一般地：设:A=a1,a2,am B=b1,b2,bp C=c1,c2,cn R是A到B的一个二元关系，S是B到C的一个二元关系，RS是A到C的一个二元关系，,2023/6/23,36,7.3.3 关系的右复合,则：MR(rij)mp MS(sij)pn MR S(tij)mn,2023/6/23,37,MR,Ms,MRS,7.3.3 关系的右复合,例1：,2023/6/23,38,7.3.4 关系运算的性质,定理7.1 设F是任意的关系,则(1)(F1)1F(2)domF1ranF,ranF1domF证明：(1)任取,由逆的定义有(F 1)1 F1 F 所以有(F1)

13、1F(2)任取 xdomF1 y(F1)y(F)xranF 所以有domF1 ranF.同理可证 ranF1 domF.,2023/6/23,39,7.3.4 关系运算的性质,定理7.2 设F,G,H是任意的关系,则(1)(F。G)。H=F。(G。H),证明：任取,(FG)H t(FGH)t(s(FG)H)t s(FGH)s(Ft(GH)s(FGH)F(GH)所以(FG)H=F(GH),2023/6/23,40,7.3.4 关系运算的性质,定理7.2 设F,G,H是任意的关系,则(2)(F。G)1=G1。F1,证明：任取,(FG)1FGt(F(t,x)G)t(G1(t,y)F1)G1F1所以(

14、FG)1=G1F1,2023/6/23,41,7.3.4 关系运算的性质,定理7.3 设 R 为 A上的关系,则 RIA=IAR=R例：设A 1,2,3,4，A上的二元关系R=,，求：RIA IAR,2023/6/23,42,7.3.5 关系的幂,定义7.10：若R是A上二元关系,Rn(nN)定义如下：R0IARn+1 RnR问题：给定集合A和A上的关系R，如何计算Rn（nN）?,2023/6/23,43,7.3.5 关系的幂,例：设Aa,b,c,d,R,求Rn。方法1：按照定义求解解：R0,R1,R2,R3,R4,R2R4 R6 R3R5 R7,2023/6/23,44,7.3.5 关系的幂

15、,方法2：利用关系矩阵相乘的方法,由于：M4=M2,即R4=R2.于是：可以得到R2=R4=R6=,R3=R5=R7=,2023/6/23,45,7.3.5 关系的幂,方法3：用关系图的方法得到R0,R1,R2,R3,的关系图如下图所示,从关系图看幂Rn运算(n1)：1.从R的每个结点x出发，凡通过数n条边能到达的结点y，则有Rn。2.Rn，意味着关系图中从x到y存在长为 n的一条路径；,2023/6/23,46,7.3.5 关系的幂,幂运算的性质引：鸽笼原理（抽屉原理）若有n个鸽笼，n1只鸽子，则至少有一个鸽笼里至少有两只鸽子。（将n1个物体放入n个盒子里，则至少有一个盒子里有2个或2个以上

16、的物体。）,2023/6/23,47,7.3.5 关系的幂,定理7.6：设|A|n,R是A上二元关系，则存在s、t,使RsRt(0st2n2)。证明：R是A上的关系，则对任意k N，Rk AA。又|AA|n2|(AA)|2n2，即A上共有2n2个不同的二元关系。但：序列R0，R1，R 2n2共有2n21项，因此,存在s,t N,使Rs=Rt(0st2n2)。,2023/6/23,48,7.3.5 关系的幂,定理7.7：若R是A上二元关系，m,n N,则：Rm Rn Rmn(Rm)nRmn定理7.8：若R是A上二元关系，若存在自然数s,t(st)，使得RsRt,则：对任意k N,Rs+k Rtk

17、对任意k,i N,Rs+kp+i Rsi,其中p=ts。令S=R0,R1,Rt-1，则对任意q N,Rq S.,2023/6/23,49,7.4 关系的性质,7.4.1 自反性和反自反性7.4.2 对称性和反对称性7.4.3 传递性7.4.4 关系性质的判定,2023/6/23,50,7.4.1 自反性和反自反性,定义7.11：设R为A上的关系,(1)若x(xAR),则称R在A上是自反的.(2)若x(xAR),则称R在A上是反自反的.,例7.10：A=1,2,3,R1,R2,R3 是 A上的关系,其中 R1=,R2=,R3=,关系是自反（反自反）的关系图中每个结点均有（无）环。关系是自反（反自

18、反）的关系矩阵主对角线的元素全为1（0）自反性与反自反性是互斥的，但不互补。,2023/6/23,51,7.4.2 对称性和反对称性,定义7.12：设R为A上的关系,(1)若xy(x,yARR),则称R为A上 对称的关系.(2)若xy(x,yARRx=y),xy(x,yAR xy R),则称为A上的反对称关系.,例7.11 设A1,2,3,R1,R2,R3和R4都是A上的关系,其中 R1,，R2,R3,，R4,2023/6/23,52,7.4.2 对称和反对称性,注意：从关系图判断关系是对称的 关系图两结点若有边，则一定是双向的，即方向相反的一对有向边。关系是反对称的关系图中两结点之间若有边，

19、则一定为单向的。从关系矩阵判断关系是对称的 关系矩阵关于主对角线对称。关系是反对称的对任意的i,j,(ij),rij 1rji0。,2023/6/23,53,7.4.3 传递性,例7.12 设A1,2,3,R1,R2,R3是A上的关系,其中 R1,R2,R3,定义7.13：设R为A上的关系,若 xyz(x,y,zARRR),则称R是A上的传递关系.,关系是传递的关系图中若两结点之间至少有两条边相连，则一定存在捷径。,2023/6/23,54,7.4.4 关系性质的判定,2023/6/23,55,7.4.4 关系性质的判定,例7.14:判断下图中关系的性质,并说明理由,(3)自反，不是反自反；反

20、对称，不是对称；不传递.,(1)不自反也不反自反；对称,不反对称；不传递.,(2)不是自反；反自反；反对称,不是对称；传递.,2023/6/23,56,7.4.4 关系性质的判定,思考：设Aa,b,c，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性(要求画出R的关系图)。,2023/6/23,57,7.5 关系的闭包,7.5.1 闭包的定义7.5.2 闭包的构造方法,2023/6/23,58,7.5.1 闭包的定义,定义7.14（闭包)设R为A上的二元关系，如果A上的二元关系R，使：R R；R是自反的（对称的或传递的）；对A上的任何关系R”，如果R R”,

21、且R”自反（对称或传递）,必有R R”；则称R为R的自反（对称或传递）闭包。记做：r(R)（s(R)或 t(R)）,2023/6/23,59,7.5.1 闭包的定义,例：Aa,b,c,d,R,求r(R),s(R),t(R)。,2023/6/23,60,7.5.2 闭包的构造方法,1.集合表达式定理7.10 设R为A上的二元关系，则：(1)r（R）RR0（R0 IA）(2)s（R）RR-1(3)t（R）RR2R3,2023/6/23,61,7.5.2 闭包的构造方法,（1）r（R）RIA证明：令R RIA显然 R R；对任意xA，有 IA,当然 RIA R，故R自反；设另有关系R”也是自反的，且

22、R R”，R”自反 IA R”，又R R”故：RIA R”，即R R”。所以说：r（R）RIA。,2023/6/23,62,(2)s（R）RR-1证明：令R R R-1显然 R R；对任意 R R R R 1 R 1 R R R 1 R 故R对称；,7.5.2 闭包的构造方法,2023/6/23,63,设另有关系R也是对称的，且R R，则对任意 RR R 1若R,由于R R 知R若R1,则R,由于R R,故有R,而R对称,于是 R。R R所以说：s（R）RR-1。,7.5.2 闭包的构造方法,2023/6/23,64,(3)t（R）RR2R3 证明：令R RR2R3 显然 R R；对任意，R,

23、必 k,j（k,j1,使 Rk,Rj,于是 Rk Rj Rk+j R,即 R故R传递；,7.5.2 闭包的构造方法,2023/6/23,65,设另有关系R也是传递的，且R R，则对任意 R,必 k(k1),使 Rk,显然存在序列：xc0,c1,c2,cky,使：,R R由已知：R传递，故 R R R 因此t（R）RR2R3 成立。,7.5.2 闭包的构造方法,2023/6/23,66,7.5.2 闭包的构造方法,2.关系矩阵表示设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和 Mt,则Mr=M+E Ms=M+MT Mt=M+M2+M3+3.关系图表示,2023/6/23,

24、67,7.5.2 闭包的构造方法,例7.15 设A=a,b,c,d,R=,R和 r(R),s(R),t(R)的关系图如下图所示.,2023/6/23,68,7.6 等价关系和划分,7.6.1 等价关系的定义7.6.2 等价类和商集7.6.3 集合的划分7.6.4 等价关系与划分的关系,2023/6/23,69,7.6.1 等价关系的定义,定义7.15 非空集合A上的二元关系R，如果R是(1)自反的(2)对称的(3)传递的称R为等价关系Equivalence Relations。若R为一个等价关系，xRy，称为x等价于y,记作：xy。,2023/6/23,70,7.6.1 等价关系的定义,例7.

25、16A1,2,3,4,5,6,7,8上的关系RR|x,yAxy(mod 3)为A上的一个等价关系。,2023/6/23,71,7.6.1 等价关系的定义,模m相等（同余）关系设x，yA（A Z），m Z+，如果xym k(kZ)，那么x与y是模m相等，记为：x y(mod m)（或称x和y模m同余）。一般地非空集合A 上的模m 同余关系 R|x,yAxy(mod m)是一个等价关系。,2023/6/23,72,7.6.2 等价类和商集,定义7.16：等价类设R为非空集合A上的等价关系,xA，令 xR y|yAxRy 称 xR 为x关于R 的等价类,简称为 x 的等价类,简记为x.定义7.17:

26、商集 ARxR|xA,2023/6/23,73,7.6.2 等价类和商集,例：写出A1,2,3,4,5,6,7,8上的模3等价关系的等价类和商集。,则:1471,4,7 2582,5,8 363,6 AR 1,4,7,2,5,8,3,6,2023/6/23,74,例2Aa,b,c,d,e,f，A上的等价关系R的关系图如下：,则：abca,b,cded,effAR a,d,f,7.6.2 等价类和商集,2023/6/23,75,7.6.2 等价类和商集,例3R是Z上的模4等价关系，则：0,8,4,0,4,8,1,7,3,1,5,9,2,6,2,2,6,10,3,5,1,3，7,11,ZR 0,1

27、,2,3,2023/6/23,76,7.6.2 等价类和商集,等价类的性质定理7.14：设R为非空集合A上的等价关系，则,2023/6/23,77,7.6.3 集合的划分,定义7.18：设A为非空集合,若A的子集族(P(A)满足下面条件：(1)(2)xy(x,yxyxy)(3)A 称是A的一个划分,称 中的元素为A的划分块.,2023/6/23,78,7.6.3 集合的划分,问题1：设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的划分,其他都不是

28、A的划分.,2023/6/23,79,7.6.3 集合的划分,问题2A1,2,3，则集合A的划分有几个？分别是什么？,11,2,3 22,1,3 33,1,2 41,2,3 51,2,3,2023/6/23,80,7.6.4 等价关系与划分的关系,等价关系与划分是一一对应的关系一方面：集合A上的一个等价关系R确定A的一个划分,即AR。另一方面：集合A的一个划分，确定A上的一个等价关系R。任给A 的一个划分,如下定义A 上的关系 R：R|x,yAx 与 y 在的同一划分块中 R 为A上的等价关系，且该等价关系确定的商集就是.,2023/6/23,81,7.6.4 等价关系与划分的关系,例：若 A

29、a,b,c,d,e,f,A上的一个划分 a，b，c，d，e，f，则：确定A上的一个等价关系。R,2023/6/23,82,7.6.4 等价关系与划分的关系,一般地：若A上的划分A1,A2,Am。则确定A上的一个等价关系R,2023/6/23,83,7.6.4 等价关系与划分的关系,问题3：设A1，2，3（1）A上共有多少个不同的二元关系；（2）给出A上所有的等价关系。分析：,1 5分别对应于等价关系 R1R5.其中:R1=,IAR2=,IAR3=,IAR4=EAR5=IA,2023/6/23,84,7.6.4 等价关系与划分的关系,思考练习A1，2共有多少个二元关系，其中有几个是等价关系，请写

30、出来。A1，2，3，4共有多少个二元关系，其中有几个是等价关系，请写出来。A1，2，3，4，5共有多少个二元关系，其中有几个是等价关系，请写出来。,2023/6/23,85,7.7 偏序关系,7.7.1 偏序关系及相关定义7.7.2 哈斯图7.7.3 偏序集中的特殊元素7.7.4 调度问题,2023/6/23,86,偏序关系及相关定义,定义7.19：R是非空集合A上的二元关系，如果R是：(1)自反的(2)反对称的(3)传递的则称R是A上偏序关系(半序关系部分序关系),记作。设为偏序关系,如果,则记作 xy,读作 x“小于或等于”y.,2023/6/23,87,偏序关系及相关定义,实例:集合A上

31、的恒等关系 IA 是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.定义7.22：集合A连同A上的偏序关系R一起称为一个偏序集，记为（或：）。,2023/6/23,88,偏序关系及相关定义,定义7.20：设R为非空集合A上的偏序关系,定义：x,yA，xy xy xy x,yA,x与y 可比 xy yx.定义7.21：全序 R为非空集合A上的偏序,x,yA,x与y 都可比，则称R为全序（线序）关系。如：,2023/6/23,89,偏序关系及相关定义,定义7.23：覆盖设R为非空集合A上的偏序关系,x,yA,如果xy且不存在 zA使得 xzy,则称 y覆盖x。如：,20

32、23/6/23,90,7.7.2 哈斯图,偏序关系的表示方法1.关系矩阵不能明显看出二元关系的特征。2.关系图 比较烦琐3.简化的关系图哈斯图（Hasse图）,2023/6/23,91,7.7.2 哈斯图,例1：A 2，4，6，8，A上的二元关系：Ra，b a|b，a,bA,2023/6/23,92,7.7.2 哈斯图,关系图哈斯图：自反性：每个顶点都有自回路，省去。反对称性：两个顶点间只可能有一个箭头,从下上的方向从小到大安置顶点，可省略箭头。传递性：若y覆盖x，则在x和y之间连一条线,2023/6/23,93,7.7.2 哈斯图,例2：画出1,2,9，R 的哈斯图。,全序关系线序关系,20

33、23/6/23,94,7.7.2 哈斯图,例3：画出 1,2,3,4,5,6,7,8,9,R整除，P(a,b,c),R 的哈斯图。,练习1：已知偏序集的哈斯图如下图所示,试求出集合A和关系R的表达式.,2023/6/23,95,7.7.2 哈斯图,A=a,b,c,d,e,f,g,h R=,IA,2023/6/23,96,课堂练习,练习2：已知偏序集,的关系图如下，试将关系图改画成哈斯图。,2023/6/23,97,课堂练习,练习3图示为偏序集的哈斯图，试画出其关系图。,2023/6/23,98,课堂练习,问题设A=1,2，求A上的所有的偏序关系。设A=1,2,3，求A上的所有的偏序关系。,20

34、23/6/23,99,7.7.3 偏序集中的特殊元素,定义7.24：设A,是偏序集,BA,bB：若x(x B x b)成立，则称b为B的最大元。若x(x B b x)成立，则称b为B的最小元。例1：对偏序集合2,4,6,8，R整除分别写出如下集合的最大元和最小元：2，4，6，82，4，82，4，64，6，8,2023/6/23,100,例2：对偏序集合 1,2,3,4,5,6,7,8,9,R整除分别写出如下集合的最大元和最小元：1,3,5,91,2,3,6 1,3,5,7 2,3,4,6,8,7.7.3 偏序集中的特殊元素,2023/6/23,101,7.7.3 偏序集中的特殊元素,定义7.2

35、4：设A,是偏序集,BA,b B：x（xB b x），则称b为B的极大元。x（xB x b），则称b为B的极小元。例1：对偏序集合2,4,6,8，R整除分别写出如下集合的极大元和极小元：2，4，6，82，4，82，4，64，6，8,2023/6/23,102,例2：对偏序集合 1,2,3,4,5,6,7,8,9,R整除分别写出如下集合的极大元和极小元：1,3,5,91,2,3,6 1,3,5,7 2,3,4,6,8,7.7.3 偏序集中的特殊元素,2023/6/23,103,7.7.3 偏序集中的特殊元素,性质对于有穷集，极小元和极大元必存在，可能存在多个.最小元和最大元不一定存在，如果存在一

36、定惟一.最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元.,2023/6/23,104,7.7.3 偏序集中的特殊元素,定义7.25:设为偏序集,BA,aA.（1）若x(xBx a)成立,则称a为B 的上界.（2）若x(xB a x)成立,则称 a 为B 的下界.（3）令Cy|y为B的上界,则称C的最小元为B 的最小上界 或上确界.（4）令Dy|y为B的下界,则称D的最大元为B 的最大下界 或下确界.,例：对偏序集合2,3,6,12,24,36,R整除,求如下集合的上界、最小上界、下界、最大下界。2，3，612，24，362，324，366，12,2023/6/23,105,7.7.3 偏序集中的特殊元素,2023/6/23,106,7.7.3 偏序集中的特殊元素,例7.21：设偏序集如下图所示求A 的极小元、最小元、极大元、最大元.设B b,c,d,求B 的下界、上界、下确界、上确界.,解：极小元：a,b,c,g；极大元：a,f,h；最小元：无最大元：无B的下界和最大下界都不存在,B的上界有d 和 f,最小上界为 d.,2023/6/23,107,7.7.3 偏序集中的特殊元素,性质：下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下确界、上确界如果存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确界；反之不对.,