06-次序关系.ppt

《06-次序关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、合

4、>,N是自然数集，“

5、”是整除关系拟序“小于”关系不是偏序，不满足自反性拟序的定义：反自反、传递拟序满足反对称性。注意：实际上,不会同时出现。哈斯图普通关系图当然可以表示偏序关系哈斯图(Hasse)-利用特定性质简化图示方法利用自反性省略环利用反对称性省略箭头利用传递性省略部分连线({a,b,c})上的包含关系{a,b,c}{c}{b}{a}{b,c}{a,c}{a,b}91281011564321{1,2,...,12}上的整除关系72484623121{1,2,3,4,6,8,12,24}上的

6、整除关系偏序集中的特殊元素：极大(小)定义：x是偏序集中的极大元iff.对任意y∈A,若x≼y,则x=yx是偏序集中的极小元iff.对任意y∈A,若y≼x,则x=y有关极大元与极小元的讨论有穷集合一定有极大(小)元不一定唯一一个元素可能兼为极大(小)元没比它更小(大)的了！偏序集中的特殊元素：最大(小)定义：x是偏序集中的最大元iff.对任意y∈A,y≼xx是偏序集中的最小元iff.对任意y∈A,x≼y有关最大元与最小元的讨论最大(小)元最多只有一个可能不存在。它比谁都要小(大)！偏序集中的

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

8、的一个子集假设B中任何两个元素均可比，则B构成一个链建设B中任何两个元素均不可比，则B构成一个反链注意：所有链的集合或者所有反链的集合与集合包含关系也构成一个偏序集，因此可以讨论极大/极小、最大/最小链或反链偏序关系与等价关系是否有可能一个关系既是偏序，又是等价关系？任意非空集合A上的恒等关系IA={

9、aA}显然，IA满足自反性、对称性、反对称性、传递性，因此它是偏序，也是等价关系作为等价关系，其商集是{{a}

10、aA}作为偏序，它的任一链只含一个元素，而其最大反链即A本身。有限偏序集中的链与反链….….元素

11、个数最多的反链，含k个元素a1a2aiak对i=1,2,…,k,从ai开始可以依次构造元素尽可能多的链Li,且Li中不含L1,…,Li-1中已有的元素。必包含该偏序集中所有元素，为什么？关于整除关系的讨论定义N-{0}上的关系R：aRb当且仅当：存在tN-{0}，满足：at=b(通常记为a

12、b)R是偏序关系极大/极小元；最大最小元？链的特征？反链的特征？在集合包含关系下讨论极大/极小链？“道是无序却有序”自然数1,2,3,…,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。你能证明吗？提示：建立n

13、n的方阵，在[i,j]单元中放入自然数1,2,3,…n2+1中的某一个，条件是在给顶排列中以该数为起点的严格递增链长度是i,而严格递减链长度是j。证明不可能有两个不同的数落在同一单元中。“道是无序却有序”–偏序模型自然数1,2,3,…,n2+1的任