次序关系课件

《次序关系课件》由会员分享，可在线阅读，更多相关《次序关系课件（24页珍藏版）》请在装配图网上搜索。

1、次序关系偏序关系偏序关系离散数学：第6讲次序关系上一讲内容的回顾上一讲内容的回顾l等价关系的定义l等价关系的关系图的特征l等价类定义非空集合A上等价关系R的等价类的性质商集l集合的划分l等价关系与集合划分的对应次序关系偏序关系偏序关系l偏序关系与偏序集l拟序l哈斯图l偏序集中的特殊元素极大元与极小元最大元与最小元上(下)界与上(下)确界l全序l良序次序关系偏序关系的定义偏序关系的定义 l非空集合A上的自反、反对称、传递关系称为一个偏序关系“不大于”关系的推广l符号： l如果对a,bA，a b和b a中总有一个成立，则a,b可比。l例子：集合包含关系；注意：并非每对元素都“可比”, 例如a和b。

2、l例子：正整数集合上的“整除”关系次序关系“字典顺序字典顺序”l假设 是集合A上的偏序关系，定义AA上的关系R如下： R iff. x1x2且x1 x2, 或者x1= x2且y1 y2易证R是AA上的偏序关系l给定有限字符集合，只要在上定义一个偏序关系，类似上述办法，就可以对任意正整数k,定义k(由中字符构成的长度为k的串的集合)上的偏序关系。加以适当的技术处理，则容易定义+(由中字符构成的长度为任意正整数的串的集合)上的偏序关系：字典关系注意：在通常的字典关系中，任何两个元素均可比。次序关系偏序集偏序集l定义了偏序的集合l表示：l例子：, 其中A是集合, N是自然数集，“|”是整除关系次序关

3、系拟序拟序l“小于”关系不是偏序，不满足自反性l拟序的定义：反自反、传递l拟序满足反对称性。注意：实际上,不会同时出现。次序关系哈斯图哈斯图 l普通关系图当然可以表示偏序关系l哈斯图(Hasse) - 利用特定性质简化图示方法利用特定性质简化图示方法利用自反性省略环利用反对称性省略箭头利用传递性省略部分连线次序关系(a,b,c)上的包含关系a,b,ccbab,ca,ca,b次序关系912810115643211,2,.,12上的整除关系7次序关系24846231211,2,3,4,6,8,12,24上的整除关系次序关系偏序集中的特殊元素偏序集中的特殊元素 ：极大：极大(小小)l定义：x是偏序集

4、中的极大元 iff. 对任意yA,若x y, 则x=yx是偏序集中的极小元 iff. 对任意yA,若y x, 则x=yl有关极大元与极小元的讨论有穷集合一定有极大(小)元不一定唯一一个元素可能兼为极大(小)元没比它更小(大)的了！次序关系偏序集中的特殊元素偏序集中的特殊元素 ：最大：最大(小小)l定义：x是偏序集中的最大元 iff. 对任意yA,y xx是偏序集中的最小元 iff. 对任意yA, x yl有关最大元与最小元的讨论最大(小)元最多只有一个可能不存在。 它比谁都要小(大)！次序关系偏序集中的特殊元素偏序集中的特殊元素 ：上：上(下下)确界确界l定义上界：对于偏序集和A的子集B，若存

5、在y,对B中任意元素x,均有x y,则y是B的上界。上确界：如果B的上界构成的偏序集有最小元，则该最小元为B的上确界。类似地可以定义下下( (确确) )界界。l有关上(下)界的讨论不一定存在上(下)界不一定唯一，但上(下)确界若存在，必唯一。注意：上(下)确界即某个偏序集的最大(小)元。次序关系从哈斯图看特殊元素从哈斯图看特殊元素最大/极大极小极小子集SS的上界的集合上确界次序关系全序全序l任何两个元素均可比的偏序称为“全序”，又称“线性序”例子：实数集上的“不大于”关系、基于拉丁字母表的字典顺序l链与反链设B是偏序集的一个子集假设B中任何两个元素均可比，则B构成一个链建设B中任何两个元素均不

6、可比，则B构成一个反链l注意：所有链的集合或者所有反链的集合与集合包含关系也构成一个偏序集，因此可以讨论极大/极小、最大/最小链或反链次序关系偏序关系与等价关系偏序关系与等价关系l是否有可能一个关系既是偏序，又是等价关系？l任意非空集合A上的恒等关系IA = | aAl显然，IA满足自反性、对称性、反对称性、传递性，因此它是偏序，也是等价关系作为等价关系，其商集是a|aA作为偏序，它的任一链只含一个元素，而其最大反链即A本身。次序关系有限偏序集中的链与反链有限偏序集中的链与反链.元素个数最多的反链，含k个元素a1a2aiak对i=1,2,k, 从ai开始可以依次构造元素尽可能多的链Li ,且L

7、i中不含L1, Li-1中已有的元素。kiiL1必包含该偏序集中所有元素，为什么？次序关系关于整除关系的讨论关于整除关系的讨论l定义N-0上的关系R：aRb 当且仅当：存在tN-0，满足：at=b (通常记为a|b)lR是偏序关系l极大/极小元；最大最小元？l链的特征？l反链的特征？l在集合包含关系下讨论极大/极小链？次序关系“道是无序却有序道是无序却有序”l自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。l你能证明吗？提示：建立nn的方阵，在i,j单元中放入自然数1,2,3,n2+1中的某一个，条件是在给顶排列中以该数为起点的严格递增链长度是i

8、, 而严格递减链长度是j。证明不可能有两个不同的数落在同一单元中。次序关系“道是无序却有序道是无序却有序” 偏序模型偏序模型l自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。l建立偏序集模型集合：A= |i=1,2,n2+1, 每个vi取1,2,n2+1中一个不同的值建立两个偏序关系：lR1: R1 iff. ij并且vivj lR2: R2 iff. ivj l问题：证明: 一定存在A的一个至少含n+1个元素的子集，它是R1的链或者R2的链。注意：R1的链是R2反链，反之亦然。次序关系良序良序l定义：给定集合A上的偏序 ，若A的任一非空子集均存

9、任一非空子集均存在最小元素在最小元素，则该偏序为良序。l良序必为全序对任意a,bA, a,b必有最小元，则a,b一定可比l实际上，“反对称性+任一非空子集存在最小元”是“自反性+传递性+任何两个元素均可比”的充分条件。自反性：对任意aA, a也必有最小元，即a a传递性：假设a b, b c, a, b, c的最小元素只能是a, 因此a c任何两个元素可比上面已证明。次序关系关于次序关系的进一步讨论关于次序关系的进一步讨论l全序是否一定是良序？l当A是无穷集合时，全序不一定是良序例如：, 任何开区间上没有最小元素l偏序、全序、良序的逆关系是否仍为偏序、全序和良序？l良序不一定保持例如次序关系作业作业lpp.140-45-50