06-次序关系.ppt

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

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

3、 注意：实际上,不会同时出现。,哈斯图,普通关系图当然可以表示偏序关系 哈斯图(Hasse) - 利用特定性质简化图示方法 利用自反性省略环 利用反对称性省略箭头 利用传递性省略部分连线,(a,b,c)上的包含关系,a,b,c,c,b,a,b,c,a,c,a,b,9,12,8,10,11,5,6,4,3,2,1,1,2,.,12上的整除关系,7,24,8,4,6,2,3,12,1,1,2,3,4,6,8,12,24上的整除关系,偏序集中的特殊元素 ：极大(小),定义： x是偏序集中的极大元 iff. 对任意yA,若xy, 则x=y x是偏序集中的极小元 iff. 对任意yA,若yx, 则x=y

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

5、不一定存在 上(下)界不一定唯一，但上(下)确界若存在，必唯一。注意：上(下)确界即某个偏序集的最大(小)元。,从哈斯图看特殊元素,最大/极大,极小,极小,子集S,S的上界的集合,上确界,全序,任何两个元素均可比的偏序称为“全序”，又称“线性序” 例子：实数集上的“不大于”关系、基于拉丁字母表的字典顺序 链与反链 设B是偏序集的一个子集 假设B中任何两个元素均可比，则B构成一个链 建设B中任何两个元素均不可比，则B构成一个反链 注意：所有链的集合或者所有反链的集合与集合包含关系也构成一个偏序集，因此可以讨论极大/极小、最大/最小链或反链,偏序关系与等价关系,是否有可能一个关系既是偏序，又是等价

6、关系？ 任意非空集合A上的恒等关系 IA = | aA 显然，IA满足自反性、对称性、反对称性、传递性，因此它是偏序，也是等价关系 作为等价关系，其商集是a|aA 作为偏序，它的任一链只含一个元素，而其最大反链即A本身。,有限偏序集中的链与反链,.,.,元素个数最多的反链，含k个元素,a1,a2,ai,ak,对i=1,2,k, 从ai开始可以依次构造元素尽可能多的链Li ,且Li中不含L1, Li-1中已有的元素。,必包含该偏序集中所有元素，为什么？,关于整除关系的讨论,定义N-0上的关系R：aRb 当且仅当：存在tN-0，满足：at=b (通常记为a|b) R是偏序关系 极大/极小元；最大最

7、小元？ 链的特征？ 反链的特征？ 在集合包含关系下讨论极大/极小链？,“道是无序却有序”,自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。 你能证明吗？,“道是无序却有序” 偏序模型,自然数1,2,3,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。 建立偏序集模型 集合：A= |i=1,2,n2+1, 每个vi取1,2,n2+1中一个不同的值 建立两个偏序关系： R1: R1 iff. iR2 iff. ivj 问题：证明: 一定存在A的一个至少含n+1个元素的子集，它是R1的链或者R2的链。 注意：R1的链是R2反链，反之亦然。,良序,定义：给定集合A上的偏序，若A的任一非空子集均存在最小元素，则该偏序为良序。 良序必为全序 对任意a,bA, a,b必有最小元，则a,b一定可比 实际上，“反对称性+任一非空子集存在最小元”是“自反性+传递性+任何两个元素均可比”的充分条件。 自反性：对任意aA, a也必有最小元，即aa 传递性：假设ab, bc, a, b, c的最小元素只能是a, 因此ac 任何两个元素可比