《离散数学课件：3-11 序关系》由会员分享，可在线阅读，更多相关《离散数学课件：3-11 序关系（35页珍藏版）》请在金锄头文库上搜索。
1、 十一、序十一、序 关关 系系 序序(order)，指一类定义在非空集合，指一类定义在非空集合A上，以满足传递性为基上，以满足传递性为基本条件的二元关系，它是通常的实数之间本条件的二元关系，它是通常的实数之间大小次序大小次序概念的推广概念的推广. 在实数系中，两个实数之间的在实数系中，两个实数之间的“小于或等于小于或等于”关系（记为关系（记为 ）是一种序，它满足：）是一种序，它满足：(1) 自反性：自反性：a a.(2) 反对称性：若反对称性：若a b且且b a ，则，则a = = b.(3) 传递性：若传递性：若a b且且b c ，则，则a c.(4) 强连结性：任給强连结性：任給a, b,
2、 则则a b和和b a中至少有一个成立中至少有一个成立.F一般说来，如果任何集合一般说来，如果任何集合A上存在二元关系（记为上存在二元关系（记为 ），），能满足上述能满足上述(1)(4)，则称，则称A上有一上有一全序全序(线序线序)关系关系，称，称为为全全序（线序）集序（线序）集;只能满足只能满足(1),(2),(3)，称为，称为偏序关系偏序关系.F此外还有此外还有良序关系良序关系、拟序关系拟序关系等不同的序关系。等不同的序关系。 若集合若集合A上的二元关系上的二元关系R是是自反的自反的、反对称反对称的的和和传递的传递的，则称，则称R是是A上的上的偏序关系偏序关系（或偏序）（或偏序），序偶，序
3、偶称为称为偏序集偏序集.&偏序，又称偏序，又称半序半序(semi-ordering).&若若R是偏序关系，是偏序关系， 常记为常记为 ，“ ”是序关系符号，读作是序关系符号，读作“小于或者等于小于或者等于”.&R是偏序时，是偏序时，aRb就记为就记为a b.(一一) 偏序偏序(partial-ordering)十一、序关系十一、序关系例例例例3.11.13.11.1 判断以下关系是否是偏序关系判断以下关系是否是偏序关系.(2)集合集合A的幂集的幂集P(A)上的包含关系上的包含关系“ ”;(3)在正整数集上的整除关系在正整数集上的整除关系;(5) 若若R是是A上的偏序关系，则上的偏序关系，则Rc
4、(4)在一群人的集合上的朋友关系在一群人的集合上的朋友关系. 对称，且可能不传递对称，且可能不传递(1)在任意实数集在任意实数集A上的大小关系上的大小关系“ ”; F若用若用 表示表示R，则可用，则可用 表示表示Rc.十一、序关系十一、序关系例例例例3.11.23.11.2 令令A N+，对任意，对任意m, n A, m|n表示表示m整除整除n的的关系（即关系（即n为为m的整数倍：存在整数的整数倍：存在整数k满足满足n=km），），试证试证是偏序集是偏序集.证：证：即要证整除关系是自反、反对称和传递的即要证整除关系是自反、反对称和传递的. (1) ( m)(m A(2) ( m)( n)(m
5、A) (n A) (m|n) (n|m) m|m);(m=n);(3) ( m)( n)( k)(m A) (n A) (k A) (m|n) (n|k)(m|k).所以，所以，是偏序集是偏序集.十一、序关系十一、序关系例例例例3.11.33.11.3 画出偏序集画出偏序集的关系图的关系图.12461246关系图关系图关系图关系图1246哈斯图哈斯图十一、序关系十一、序关系(二二) 哈斯哈斯 (Hasse)图图 利用偏序关系是自反、反对称和传递的，可以简利用偏序关系是自反、反对称和传递的，可以简化一个偏序关系的关系图，得到偏序集的化一个偏序关系的关系图，得到偏序集的哈斯图哈斯图. 为了说明哈斯
6、图的画法，首先定义偏序集中为了说明哈斯图的画法，首先定义偏序集中顶点顶点的盖住关系的盖住关系. 设设为偏序集，为偏序集， x, y A, 若若x y, x y, 且且不存在不存在z A使得使得x z y, 则称则称y盖住盖住x，并且记，并且记COVA=|x, y A, y盖住盖住x.F 通俗地讲，序关系通俗地讲，序关系“ ”是指集合中元素间的顺序性是指集合中元素间的顺序性.l“x y”的含义是：依照这个顺序，的含义是：依照这个顺序，“x排在排在y的前面的前面”或或“x就是就是y, 是同一个元素是同一个元素”.l“y盖住盖住x”的含义是：的含义是：“x紧排在紧排在y的前面的前面”.十一、序关系十
7、一、序关系顶点的顶点的“盖住盖住”关系关系例例例例3.11.43.11.4 在偏序集在偏序集中，有中，有& 2盖住盖住1；& 4和和6盖住盖住2；& 但但4不盖住不盖住1，因为，因为1 2 4；& 但但6也不盖住也不盖住4，因为，因为4 6不成立不成立.从而从而COVA= , , .4与与6不不可比可比十一、序关系十一、序关系F 设设(A, )是一个偏序集，对任意是一个偏序集，对任意x, y A，若，若x y，或或y x，称，称x与与y可比可比 ；否则，称；否则，称x与与y不可比不可比。偏序集的哈斯图表示偏序集的哈斯图表示哈斯图的画法：哈斯图的画法： 设有偏序集设有偏序集， x, y A(x
8、y)，适当排列适当排列结点的顺序使得：结点的顺序使得：(1)若若x y，则将，则将x画在画在y的下方的下方.(2)若若y盖住盖住x，则用一条直线连接，则用一条直线连接x和和y.F哈斯图中：无环；不使用箭头，更无双边；无第三哈斯图中：无环；不使用箭头，更无双边；无第三边；（与关系图的区别）；无水平边（同层次元素边；（与关系图的区别）；无水平边（同层次元素不不可比可比）.十一、序关系十一、序关系例例例例3.11.53.11.5 画出偏序集画出偏序集的哈斯图的哈斯图.解：解：其哈斯图如下：其哈斯图如下： 1令令A= 1, 2, 3, 4, 5, 6, 7, 8, 9, 则则COVA= , , , ,
9、 , , , , .53724698十一、序关系十一、序关系例例例例3.11.63.11.6 已知已知偏序集偏序集的哈斯图如下图所示，试求的哈斯图如下图所示，试求出集合出集合A和关系和关系R的表达式的表达式.解：解：a, b, c, d, e, f, g, h.cbgadehfA=R= , , , , , , , IA.十一、序关系十一、序关系(三三) 链链 设设为偏序集，为偏序集，&在在A的一个子集中，如果每两个元素都是有关系（的一个子集中，如果每两个元素都是有关系（可可比比）的，则称这个子集为）的，则称这个子集为链链(chain).&在在A的一个子集中，如果每两个元素都是无关（的一个子集中
10、，如果每两个元素都是无关（不可不可比比）的，则称这个子集为）的，则称这个子集为反链反链.F约定：若约定：若A的子集只有单个元素，则这个子集既是的子集只有单个元素，则这个子集既是链又是反链链又是反链.十一、序关系十一、序关系例例例例3.11.7 3.11.7 判断在如下哈斯图表示的偏序集的一些判断在如下哈斯图表示的偏序集的一些子集中，哪些是链，哪些是反链子集中，哪些是链，哪些是反链.1324612子集子集链链反链反链1, 2, 4, 121, 3, 6, 121, 2, 6, 121, 2, 42, 62, 33, 41, 2, 3, 6YNYYYYNNNNNYYNNNF在哈斯图中，链中在哈斯图
11、中，链中的元素分布在沿盖住的元素分布在沿盖住方向的一条线上方向的一条线上.十一、序关系十一、序关系(四四) 偏序集合的子集的特殊元素偏序集合的子集的特殊元素设设为偏序集，为偏序集，B A，对，对b B，(1)若若B中不存在元素中不存在元素x,使使b x且且b x，则称，则称b为为 B的的极大元极大元(maximal element)；(2)若若B中不存在元素中不存在元素x,使使b x且且x b，则称，则称b为为B的的极小元极小元(minimal element).Fb为为B的的极大元极大元：若：若B中不存在任何大于中不存在任何大于b的元的元素，即素，即b大于大于B中任何异于中任何异于b且与且与
12、b可比较的元素可比较的元素. 用符号表达如下：用符号表达如下：( x B)(x b x=b).Fb为为B的的极小元极小元，用符号表达如下：，用符号表达如下：( x B)(b x x=b).十一、序关系十一、序关系例例例例3.11.8 3.11.8 设设A=2, 3, 5, 7, 14, 15, 21，偏序集为，偏序集为. 求求B=2, 3, 7, 14, 21的极大元和极小元的极大元和极小元.解：解：的哈斯图如下：的哈斯图如下：2135271415B的极小元集合是的极小元集合是2, 3, 7, B的极大元集合是的极大元集合是14, 21. F极大元是哈斯图中最顶端的元素；极大元是哈斯图中最顶端
13、的元素； 极小元是哈斯图中最底层的元素；极小元是哈斯图中最底层的元素； 不同的极大元（极小元）之间是无关的，是不不同的极大元（极小元）之间是无关的，是不可比的可比的.十一、序关系十一、序关系B例例例例3.11.9 3.11.9 设偏序集为设偏序集为，求，求B=2i| i Z的极大元的极大元和极小元和极小元.解：解：B的极大元和极小元均不存在的极大元和极小元均不存在. 由以上两例可见：由以上两例可见：F极大（小）元极大（小）元不一定不一定存在，对于非空有限集，存在，对于非空有限集，极大（小）元极大（小）元一定一定存在；存在；F极大（小）元若存在，不一定唯一极大（小）元若存在，不一定唯一.十一、序
14、关系十一、序关系偏序集合的子集的特殊元素偏序集合的子集的特殊元素设设为偏序集，为偏序集，B A，对，对b B，(1)若若B中任意元素中任意元素x,有有x b，则称，则称b为为B的的最最大元大元(largest element, greatest element)；(2)若若B中任意元素中任意元素x,有有b x，则称，则称b为为B的的最最小元小元(least element, smallest element)； 或用符号表达如下：或用符号表达如下：Fb为为B的的最大元最大元：( x)(x B x b).Fb为为B的的最小元最小元：( x)(x B b x).十一、序关系十一、序关系例例例例3.
15、11.10 3.11.10 考虑偏序集考虑偏序集，其哈斯图为：，其哈斯图为：求子集求子集a, , a, b的最大（小）元的最大（小）元.a, ba b子集子集最大元最大元最小元最小元a, a, ba不存在不存在不存在不存在解：解：十一、序关系十一、序关系定理定理 设设为偏序集，为偏序集，B A，若，若B有最大（最有最大（最小）元，则必是唯一的小）元，则必是唯一的.假设假设a和和b都是都是B的最大元，的最大元，证：证：则则a b且且b a.a=b.由由 的反对称性得，的反对称性得，所以所以B的最大元是唯一的的最大元是唯一的.同理可证，同理可证，B的最小元也是唯一的的最小元也是唯一的. 由以上例子
16、和定理可见：由以上例子和定理可见：F最大（小）元最大（小）元不一定不一定存在，对于非空有限集，存在，对于非空有限集，最大（小）元也最大（小）元也不一定不一定存在；存在；F最大（小）元若存在，一定唯一最大（小）元若存在，一定唯一.十一、序关系十一、序关系偏序集合的子集的特殊元素偏序集合的子集的特殊元素最大元与极大元的比较：最大元与极大元的比较：&最大元是最大元是B中最大的元素，它与中最大的元素，它与B中其它元素都可中其它元素都可比；而极大元不一定与比；而极大元不一定与B中所有元素都可比，只要没中所有元素都可比，只要没有比它大的元素，它就是极大元有比它大的元素，它就是极大元.&最大元与极大元都不一
17、定存在，但对于非空有限最大元与极大元都不一定存在，但对于非空有限集集B, 极大元一定存在，但最大元不一定存在极大元一定存在，但最大元不一定存在;&最大元若存在一定唯一，但极大元可能有多个最大元若存在一定唯一，但极大元可能有多个.&若若B中只有一个极大元，则它一定是中只有一个极大元，则它一定是B的最大元；的最大元；若若B中有最大元，则它一定是中有最大元，则它一定是B的唯一的极大元的唯一的极大元.F最小元与极小元也有类似的区别和联系最小元与极小元也有类似的区别和联系.十一、序关系十一、序关系例例例例3.11.11 3.11.11 考虑偏序集考虑偏序集，其哈斯图为：，其哈斯图为：cbgadehf求求
18、A的极大元、极小元、最大元、最小元的极大元、极小元、最大元、最小元.解：解：由该偏序集的哈斯图可知：由该偏序集的哈斯图可知：极小元：极小元：a, b, c, g;极大元：极大元：a, f, h;没有最大元与最小元没有最大元与最小元.F由此例可知，哈斯图中的孤立点既是极大元也是由此例可知，哈斯图中的孤立点既是极大元也是极小元极小元.十一、序关系十一、序关系偏序集合的子集的特殊元素偏序集合的子集的特殊元素设设为偏序集，为偏序集，B A，对，对a A，(1)若若( x)(x B x a)成立，则称成立，则称a为为B的的上界上界(upper bound);(2)若若( x)(x B a x)成立，则称
19、成立，则称a为为B的的下界下界(lower bound).F注意这里注意这里a A, 即即B的上（下）界的上（下）界不一定不一定是是B中的元素中的元素.十一、序关系十一、序关系偏序集合的子集的特殊元素偏序集合的子集的特殊元素设设为偏序集，为偏序集，B A，(1)设设a是是B的一个上界，若对的一个上界，若对B的所有上界的所有上界y均有均有a y, 则称则称a为为B的的最小上界最小上界(least upper bound)或或上确界上确界(supremum), 记为记为LUBB或或supB;(2)设设b是是B的一个下界，若对的一个下界，若对B的所有下界的所有下界z均有均有z b, 则称则称b为为B
20、的的最大下界最大下界(greatest lower bound)或或下确界下确界(infimum), 记为记为GLBB或或infB.F或者：或者：(1)令令C=a|a为为B的上界的上界，则称，则称C的最小元为的最小元为B的最小的最小上界（上确界）；上界（上确界）；(2)令令D=b|b为为B的下界的下界，则称，则称D的最大元为的最大元为B的最大的最大下界（下确界）下界（下确界）.十一、序关系十一、序关系例例例例3.11.12 3.11.12 考虑偏序集考虑偏序集，其哈斯图为：，其哈斯图为：cbgadehf令子集令子集B=b, c, d，求，求B的上界、上确界、下界和的上界、上确界、下界和下确界下
21、确界.解：解：由该偏序集的哈斯图可知：由该偏序集的哈斯图可知：上界：上界： d, f;上确界：上确界：d;下界和下确界都不存在下界和下确界都不存在.十一、序关系十一、序关系B求求B1=a, b, c, d, e, f, g, B2=h, i, j, k, B3=f, g, h, i, j的上界、上确界、下界和下确界的上界、上确界、下界和下确界.例例例例3.11.13 3.11.13 考虑偏序集考虑偏序集，其哈斯图为：，其哈斯图为：dcebfgahijkB1B2十一、序关系十一、序关系dcebfgahijkB1B2子集子集上界上界上确界上确界下界下界下确界下确界a, b, c, d, e, f,
22、 g,h, i, j, kf, g, h, i, j解：解：h, i, j, ka, b, c, d, e, f, gaa无无无无无无无无无无无无无无无无十一、序关系十一、序关系偏序集合的子集的特殊元素偏序集合的子集的特殊元素F上确界与最大元的比较：上确界与最大元的比较：lB的最大元一定是的最大元一定是B的上确界；但的上确界；但B的上确界不的上确界不一定是一定是B的最大元，因为它可能不是的最大元，因为它可能不是B中的元素中的元素;l下确界与最小元也有类似的区别和联系下确界与最小元也有类似的区别和联系.F由以上两例可见：由以上两例可见：l上界、上确界、下界、下确界都不一定存在；上界、上确界、下界
23、、下确界都不一定存在；l上确界、下确界若存在一定唯一，但上界、下上确界、下确界若存在一定唯一，但上界、下界可能有多个界可能有多个.十一、序关系十一、序关系偏序集合的子集的特殊元素偏序集合的子集的特殊元素F若若是是一一个个偏偏序序集集，则则也也是是一一个偏序集个偏序集.F偏偏序序集集中中的的极极大大元元、最最大大元元、上上界界、上上确确界界分分别别是是中中的的极极小小元元、最最小小元元、下下界、下确界界、下确界. 反之亦然反之亦然.十一、序关系十一、序关系例例例例3.11.14 3.11.14 考虑偏序集考虑偏序集的子集的子集B1=x|0x1, B2=x|0 x+ ，分别求它们的上界、上确界、最
24、，分别求它们的上界、上确界、最大元、下界、下确界和最小元大元、下界、下确界和最小元.解：解：关于关于B1, 有有上界：上界：上确界：上确界：最大元：最大元：下界：下界：下确界：下确界：最小元：最小元：x|x 11无无x|x 00无无关于关于B2, 有有上界：上界：上确界：上确界：最大元：最大元：下界：下界：下确界：下确界：最小元：最小元：无无无无无无x|x 000十一、序关系十一、序关系(五五) 其它序关系其它序关系F所谓所谓“全序全序”，就是在自反、反对称、传，就是在自反、反对称、传递的基础上，添加了可比性（强连结性），递的基础上，添加了可比性（强连结性），即即( a) ( b)(a, b
25、A) (a b) (b a) 自然数集自然数集N，整数集，整数集Z，有理数集，有理数集Q，实，实数集数集R上的上的 关系，就是全序概念的起源关系，就是全序概念的起源. 在偏序集在偏序集中，若中，若A是一个链，则是一个链，则&称称为为全序集合全序集合(totally ordered set)或或线线序集合序集合(linearly ordered set)；&二元关系二元关系 称为称为A上的上的全序关系全序关系（或（或线序关系线序关系）.十一、序关系十一、序关系例例例例3.11.15 3.11.15 给定给定A= , a, a, b, a, b, c上的包上的包含关系含关系 ，证明，证明是全序集合
26、是全序集合.解：解： 包含关系包含关系 显然是自反，反对称和传递的，显然是自反，反对称和传递的，所以所以是偏序集是偏序集.而而A中任意两个元素都可比：中任意两个元素都可比： a a, b a, b, c.所以所以是全序集合是全序集合.a, ba a, b, ca, ba a, b, c(a) 哈斯图哈斯图(b) 关系图关系图十一、序关系十一、序关系良序集合良序集合 在偏序集在偏序集中，若中，若A的每一非空子集总含的每一非空子集总含有最小元，则有最小元，则&称称为为良序集合良序集合(well-ordered set)；&二元关系二元关系 称为称为A上的上的良序良序(well-ordering).
27、例例例例3.11.16 3.11.16 判断下列偏序集是否是良序集判断下列偏序集是否是良序集.子集子集良序集良序集YYNNN十一、序关系十一、序关系良序集合良序集合定理定理定理定理 每一良序集合，一定是全序集合每一良序集合，一定是全序集合.证：证：对对 a, b A, 可构成子集可构成子集a, b,设设为一良序集合，为一良序集合，则则已经是偏序集已经是偏序集.要进一步证要进一步证为全序集，只需要证为全序集，只需要证成立成立.( a) ( b)(a, b A) (a b) (b a)因因为良序集，则为良序集，则a, b必存在最小元：必存在最小元：a或或b.从而从而(a b) (b a), 所以所
28、以是全序集是全序集.十一、序关系十一、序关系良序集合良序集合定理定理定理定理 每一有限的全序集合，一定是良序集合每一有限的全序集合，一定是良序集合.证：证：设设A=a1, a2, ,an，令，令为一全序集为一全序集. 由于由于B是一个有限集合，故一定可以找出两是一个有限集合，故一定可以找出两个元素个元素x与与y是无关是无关(不可比不可比)的的. 则必存在一个非则必存在一个非空子集空子集B A，在，在B中不存在最小元中不存在最小元. 假设假设不是良序集，不是良序集， 由于由于是全序集，是全序集，x,yA，故故必是良序集必是良序集. 所以所以x, y必必有关系（可比），得出矛盾有关系（可比），得出
29、矛盾. F上述结论对无限的全序集合不一定成立上述结论对无限的全序集合不一定成立. 例如例如, , 是全序集合，是全序集合，但不是良序集合但不是良序集合.十一、序关系十一、序关系良序集合良序集合F总的来说，偏序（半序）、全序（线序）、总的来说，偏序（半序）、全序（线序）、良序依次加强，它们的关系可用下图来表示良序依次加强，它们的关系可用下图来表示.偏序偏序全序全序良序良序十一、序关系十一、序关系拟序集合拟序集合(见见3-12习题习题(2) 若集合若集合A上的二元关系上的二元关系R是是传递的传递的和和反自反反自反的的，则称，则称R是是A上的上的拟序关系拟序关系.定理定理 设设R是集合是集合A上的二元关系，上的二元关系，(1) 若若R是一拟序关系，则是一拟序关系，则r(R)=RIA是偏序关系；是偏序关系；(2) 若若R是一偏序关系，则是一偏序关系，则R-IA是一拟序关系是一拟序关系.HW: 3-12习题习题 (1);(2);(6);(7)十一、序关系十一、序关系
