《序关系和结构OrderRelationsandStructures.doc》由会员分享，可在线阅读，更多相关《序关系和结构OrderRelationsandStructures.doc（22页珍藏版）》请在金锄头文库上搜索。
1、序关系和结构Order Relations and Structures6.1 偏序集Partial Orsered Sets偏序关系Partial Order1.自反 Reflexive aA, (a,a)R2反对称antisymmetric(a,b)R (b,a)R a=b3传递Transitive(a,b)R (b,c)R (a,c)R.大于等于，小于等于，恒等，整除关系都是偏序关系。树是偏序。偏序的图中没有长度大于1的回路。偏序集Poset Partial ordered set(A，R), R是A上偏序。（A, ）偏序集，是集合A上偏序。 Z是偏序集，是Z上偏序。 不是偏序。例4 R
2、，S都是A上等价关系， RSxRyxSyR：A上全体等价关系，（R ，）构成偏序。对偶偏序集：如果R是A上偏序，则R1也是A上偏序。（A，R1）称为（A，R）的对偶偏序集。（A，）是（A，）的对偶偏序。全序关系，线性序关系linear order，链chain偏序1.2.3.44 a,bA,(a,b)R(b,a)R.大于等于，小于等于是全序，整除，（A, ）不是。定理1.如果(A,)，(B,)是偏序，则(AB，)是乘积偏序product partial order，其中定义为： (a,b)(a,b) aa,bb设（A，）是偏序，令abab，ab，称（A，）严格线性序大于，小于都是严格线性序。乘
3、积偏序(AB，)中，令(a,b)(a,b)aaor a=a,bb是字典序lexicograpjic（A，）是偏序，AnAAA(a1,a2,an)(b1,b2,bn) a1b1a1b1a2b2a1b1anbn 12定理2. 偏序集的有向图中没有长度大于1的圈。43哈斯图Hasse Diagram21例11A1,2,3,4,12, 偏序集(A, | )的哈斯图：0例12Sa,b,c, A=P(S).1a,cb,ca,b(A, )的哈斯图:bcaA=,a,b,c,a,ba,c,b,c,a,b,c拓扑排序（A，）是偏序集，构造一个线性序（A，）使abab，算法原理： 1. 选择一个没有前驱的顶点输出，
4、 2. 去掉这个顶点以及从这点出发的所有边。 重复1.2.直到所有顶点都输出完毕同构Isomorphic f：（A，）（A,）f是AA的一一对应，ab iff f(a)f(b)。例15f：（Z，）（2Z，）是同构。f(a)=2aab iff 2a2b定理3. 设f：(A,) (A,)。则A, A对应的性质都相同。1 如果f是同构，则A的哈斯图中所有标记a换成对应的标记f(a), 得到A的哈斯图。2 如果A的哈斯图中所有标记a换成对应的标记f(a), 得到A的哈斯图，则f是同构。 例17A1,2,3,6, A=P(a,b)= ,a,b,c,a,b,(A, |)(A, )Homework P200
5、2015，6，14，16，24，28，35，366.2偏序集的极大极小元 Extremal elements of Partial Orsered Sets极大元maximal element：a 是A的极大元，aA，没有bA，ab.极小元minimal element：a 是A的极小元，aA，没有bA，ba.定理1. 有限偏序集A中，至少有一个极大元，至少有一个极小元。最大元greatest element：a 是A的最大元，aA，任意bA，ba.最小元least element：a 是A的最小元，aA，任意bA，ab.定理2. 偏序集A中，至多有一个最大元，至多有一个最小元。偏序集A中，如
6、果有最大元，称之为单位元1，如果有最小元，称之为零元0。上界 upper bound偏序集A中，BA，aA，bB，ba.下界lower bound偏序集A中，BA，aA，bB，ab.上确界LUB least upper bound偏序集A中，BA，a是B的最小上界，即a是B的上界，对B的任意上界a，aa.定理3. 偏序集A中，BA，B至多一个上确界，至多一个下确界。定理4. 设f：（A，）（A,）是偏序同构，（a） a是A的极大（极小）元，则f(a)是A的极大（极小）元。（b） a是A的最大（最小）元，则f(a)是A的最大（最小）元。（c） BA，a是B的上（下）界，则f(a)是f(B)的上（
7、下）界（d） BA，a是B的上确（下）界，则f(a)是f(B)的上（下）确界Homework P20620716，26，336.3 格 Lattices定义 格是一个偏序集（L，），任意a，bL，a，b有上下确界。令abLUB(a,b), abGLB(a,b).格 (L,，)例1（P(S), ）是格，ABAB，ABAB。记做（P(S), ,）例2（Z，| ）是格，abLCM(a,b),abGCD(a,b).例3令Dn是n的所有正因子的集合，（Dn，|）是格。D201,2,4,5,10,20, D30=1,2,3,5,6,10,15,20线性序是格例4 Hasse图是否格的判断。设（L，, ，）
8、是格，则对偶（L，）也是格。例6. （P(S),，）是格，ABAB，ABAB。 例5 R：A上全体等价关系，偏序（R ，）是格。 RSRS RS(RS)定理1. 设（L1,），（L2,）都是格。则（L1L2，,）也是格。(a,b)(c,d)=(ac, bd)(a,b)(c,d)=(ac, bd)子格sublattice设（L，）是格，SL，S对，封闭，即a，bSab，abS。记做(S，,) (L，,)或 格S L。(Dn，|, LCM, GCD) (Z+, |, LCM,GCD)例9 PP209210 图6.42格的同构Isomorphic Latticesf：(L1,)(L1,)，f是L1到
9、L2的序同构，则f保持，运算，f(ab)=f(a)f(b)f(ab)=f(a)f(b)格同构也记做L1L2。D6P(a,b).R见 练习33格的性质Properties of Lattices定理2 设L是格，则ab abb aba.定理3.设L是格，则L具有如下性质：幂等律 aaa， aaa交换律 abba，abba结合律 a(bc)=(ab)c, a (bc)=(ab)c吸收律 a(ab)=a, a(ab)=a定理3. 设集合L上有运算，（L,）满足幂等律，交换律，结合律，吸收律，则L是格。证明.先证明 abb iff aba。 aba(ab)=a. aba(ab)=a.定义L上关系：ab
10、 iff abb iff aba。是L上偏序： 1）自反性：由aaa，得aa 2）反对称性： 设ab，ba， aabbab， 3）传递性 设ab，bc， aca(bc)(ab)c bcc ac还要证明ab，ab分别是上下确界，这里仅证ab是上确界，将ab是下确界留给同学：上界：a(ab)=a, aabb(ab)=b, bab上确界设ac，bc，(ab)c=a(bc)=accabcab是a，b的最小上界。定理4. 设L是格，如果ab，则（a）acbc（b）acbcac，bc iff abcca，cb iff cab如果ab，cd则 acbdacbd特殊格有界格Bounded lattice：有最
11、大元1，最小元0的格叫有界格。L是有界格，则对任意aL，有0，1律成立。 0a1a0a，a00a11，a1a定理5. L是有限格，则L有界。分配格Distributive Lattice：满足分配律的格：1. a(bc)abac2. a(bc)(ab)(ac)120例16格(P(S),)是分配格。11例18不分配的格，含有如下子格：bcaabc0定理6格L不是分配格当且仅当L含有例18中的子格。可补格Complement Lattice.有界格L是可补格，如果任意aL，有aL，使 aa=1，aa=0.称a为a的补元。0例19格(P(S),)是可补格。例21D20，D30都是可补格。定理7. 设L是有界格，aL，如果a有补元，则其补元唯一。证明. 设a,a”都是a的补元。则a=a0a(aa”) (aa)(aa”) = aa” a”=a”0a”(aa) (a”a)(a”a) = aa”因此 a=a”.Homework P21621712，14，18，21，23，24，27，31，336.4 有限布尔代数Finite Boolean Algeblas6.5 线路设计Circuit Designs
