序关系和结构OrderRelationsandStructures.docVIP

序关系和结构Order Relations and Structures §6.1 偏序集Partial Orsered Sets 偏序关系Partial Order 1.自反 Reflexive (a(A, (a,a)(R 2．反对称antisymmetric (a,b)∈R ∧ (b,a)∈R ( a=b 3．传递Transitive (a,b)∈R ∧ (b,c)∈R ( (a,c)∈R. 大于等于，小于等于，恒等，整除关系都是偏序关系。 树是偏序。（A, (）(是集合偏序。不是偏序。 例4． R，S都是A上等价关系， R(S(xRy→xSy R：A上全体等价关系， （R ，(）构成偏序。 对偶偏序集：如果R是A上偏序，则R－1也是A上偏序。（A，R－1）称为（A，R）的对偶偏序集。 （A，≥）是（A，≤）的对偶偏序。 全序关系，线性序关系linear order偏序1.2.3.＋4． (a,b(A,(a,b)(R∨(b,a)∈R. 大于等于，小于等于是全序，整除，（A, (）不是。’,b’) (a≤a’,b≤b’ 设（A，≤）是偏序， 令ab(a≤b，a≠b， 称（A，）大于，小于都是严格线性序。 (a,b)(a’,b’)(aa’or a=a’,bb’ 是字典序lexicograpjic （A，≤）是偏序， An＝A×A×……×A (a1,a2,……,an)(b1,b2,……,bn) ( a1b1∨a1＝b1∧a2b2∨……∨a1＝b1∧……∧anbn 定理2. 偏序集的有向图中没有长度大于1的圈。 哈斯图Hasse Diagram 例11．A＝{1,2,3,4,12}, 偏序集(A, | )的哈斯图： 例12．S＝{a,b,c}, A=P(S). (A, ()的哈斯图: A={(,{a},{b},{c},{a,b} {a,c},{b,c},{a,b,c}} 拓扑排序 （A，≤）是偏序集，构造一个线性序（A，?）使 a≤b(a?b， 算法原理： 1. 选择一个没有前驱的顶点输出， 2. 去掉这个顶点以及从这点出发的所有边。 重复1.2.直到所有顶点都输出完毕 同构Isomorphic f：（A，≤）→（A’,≤’） f是A→A’的一一对应， a≤b iff f(a)≤’f(b)。 例15． f：（Z，≤）→（2Z，≤）是同构。 f(a)=2a a≤b iff 2a≤2b 定理3. 设f：(A,≤) ((A’,≤’)。则A, A’对应的性质都相同。 如果f是同构，则A的哈斯图中所有标记a换成对应的标记f(a), 得到A’的哈斯图。 如果A的哈斯图中所有标记a换成对应的标记f(a), 得到A’的哈斯图，则f是同构。 例17．A＝{1,2,3,6}, A’=P({a,b})={ (,{a},{b},{c},{a,b}}, (A, |)((A’, () Homework P200－201 5，6，14，16，24，28，35，36 §6.2偏序集的极大极小元 Extremal elements of Partial Orsered Sets 极大元maximal element： a 是A的极大元， a∈A，没有b∈A，ab. 极小元minimal element： a 是A的极小元， a∈A，没有b∈A，ba. 定理1. 有限偏序集A中，至少有一个极大元，至少有一个极小元。 最大元greatest element： a 是A的最大元， a∈A，任意b∈A，ba. 最小元least element： a 是A的最小元， a∈A，任意b∈A，ab. 定理2. 偏序集A中，至多有一个最大元，至多有一个最小元。 偏序集A中，如果有最大元，称之为单位元1，如果有最小元，称之为零元0。 上界 upper bound 偏序集A中，B(A，a∈A，(b∈B，ba. 下界lower bound 偏序集A中，B(A，a∈A，(b∈B，ab. 上确界LUB least upper bound 偏序集A中，B(A，a是B的最小上界，即a是B的上界，对B的任意上界a’，aa’. 下确界GLB greatest lower bound 偏序集A中，B(A，a是B的最大下界，即a是B的下界，对B的任意下界a’，aa’. 定理3. 偏序集A中，B(A，B至多一个上确界，至多一个下确界。 定理4. 设f：（A，≤）→（A’,≤’） 是偏序同构， a是A的极大（极小）元，则f(a)是A’的极大（极小）元。 a是A的最大（最小）元，则f(a)是A’的最大（最小）元。 B(A，a是B的上（下）界，则f(a)是f(B)的上（下）界 B(A，a是B的上确（下）界，则f(a)是f(B)的上（下）确界 Homewo