《离散数学第七章》由会员分享，可在线阅读，更多相关《离散数学第七章（64页珍藏版）》请在金锄头文库上搜索。
1、第七章 格本章在介绍代数系统格和布尔代数。主要内容如下：7.1 偏序集； 7.4 分配格和有补格；7.2 格及其性质； 7.5 布尔代数；7.3 格是一种代数系统；*17.1 格一 偏序集1.偏序集定义7-1 集合L和定义在 L 上的偏序关系 “” 一起称为偏序集，用表示。 , , 和都是偏序集。若 是集合A上的偏序关系，则 的逆关系 也 必是上的偏序关系，证明如下：*2(1)对任意的 a，因为 自反，所以有(a,a) ,于是(a,a) ，因此 也是自反的。 (2)对任意 a ,bA ，若(a,b) 且(b,a)，则有(b,a) 且(a,b) ，必有a = b，因此是反对称的。 (3)对任意a
2、,b,c A, 若(a,b), (b,c)，则有(c,b)且(b,a)，必有(c,a), 于是(a,c) ，因此是可传递的。由上证得也是偏序关系。 *3例1 设 A=1,2,3,6，定义 A 上的整除关系：当旦仅当 a 整除 b 时，有ab。根据逆关系的定义由定义12366231的次序图如下的次序图如下*4若是一个偏序集，则对于任意元素 l1, l2, l3 L，有以下六个关系式成立：注意在偏序集中，对任意元素l1,l2 L, 若l1l2，则必有l2l1， 若l2 l1，则必有l1l2，因此,l1l2等价于l2l1 。*52最大下界和最小上界定义7-2 设l1和l2是偏序集中的两个元素, 元素
3、aL, 如果满足al1,al2 ,则称a是l1和l2的下界。如果元素a是l1和l2的下界。且对于任意aL，若a也是l1和 l2的下界，便有aa ,则称a是l1和l2的最大下界,简记作a=glb(l1,l2)。定义7-3 设l1和l2是偏序集中的两个元素, 元素bL, 如果满足l1b, l2b,则称b是l1和l2的上界。如果元素b是l1和l2的下界。且对于任意bL，若b也是l1和 l2的下界，便有bb ,则称b是l1和l2的最小上界,简记作b=lub(l1,l2)。*6例2 设A=1,2,3,6,9,12,18,27 “整除”关系是A上的偏序关系，其次序图如下，因此，它们 构成一个偏序集。132
4、12182796lub(2,3)=?，glb(12,18)=?，lub(18,27)=?有26，36；212，312；218，318。 由于612，618，66，因此，lub(2,3)=6。6 12, 6 18; 2 12, 2 18; 3 12, 3 18; 1 12, 1 18; 因1 6，2 6，3 6，所以glb(12,18)6。 *7例3 设A=1,2,3,12,18,36，整除关系是A上的偏序关系，其次序图如下 132361812试问 glb(18,12)=?, lub(2,3)=? 218，2 12；3 18，3 12，1 18，1 12 。 类似地，12，18 和 36 均是
5、2 和 3 的上界，但 lub(2,3)不存在。但glb(18,12)不存在。*8定理7-1 设l1和l2是偏序集的两个元素,如果l1和l2有glb, 则glb是唯一的，如果l1和l2有lub,则lub是唯一的。证明 设a1和a2都是l1和l2的glb， 由定义7-2, 则a2a1, a1a2, 于是a1=a2类似地可以证明, l1和l2若存在lub，则lub也一定是唯一的。*93 最小元素和最大元素定义7-4 设是一偏序集。(1) 如果存在元素aL，使得对于所有的元素lL，有a l ，则称a是的最小元素。(2) 如果存在元素bL，使得对于所有的元素lL，有lb，则称b是的最大元素。定理7-2
6、 如果偏序集有最小元素，则最小元素是唯一的。如果有最大元素，则最大元素也是唯一的。 证明 设a1和a2都是的最小元素，则有a1a2，且a2a1，得a1a2。 *10二、 格1格的定义定义7-5 设是一个偏序集，如果L中任意两个元素都存在着最大下界和最小上界，则称是格 。l1l2=glb(l1,l2), l1l2=lub(l1,l2)若是一个格，则意味着也是一个形为 的代数系统,其中和是L上的两个二元运算, 对于 任意l1,l2L, l1l2表示在偏序“”意义下l1和l2的最小上界, l1l2表示l1和l2的最大下界。*11例4 设n是一正整数，Sn是n的所有正因子的集合，设“|”是整除关系，则
7、对于任意正整数，|是Sn上的偏序关系，是格。x,ySn, xy是lcm(x,y),即x与y的最小公倍数， xy是gcd(x,y), 即x与y的最大公约数。*12例5 试判断下列次序图给出的偏序集哪些是格？eeeeeeecbdahagfdebc30161531052(a) (b) (c) (d) 解 (a)不是格， (b)不是格， (c)是一个格， (d)是一个格 *13在格L;中有如下四个关系式成立:*142格的性质定理7-3 在格中，对于任意l1, l2L, 以下三式中若任意一式成立，那么其它两式也成立.证明 设 ， *15 设 设 *16定义7-6 设是格，P是包含格的元素和符号=、，和的
8、命题，将P中的、，和分别替换成、 和所得的命题PD称为P的对偶。例如 的对偶是 对偶原理 ： 对于格上的任一真命题P，其对偶PD 亦为格上的真命题。 *17定理7-4 （交换律）设是格，则对任意的l1,l2L,有: *18定理7-5 (结合律) 设是格，则对任意的l1, l2, l3L, 有证明类似的方法可以证明ba, 于是由反对称性得a=b.*19定理7-6 (吸收律) 设L;是格,则对任意l1, l2L，有 证明 (b) 由（7-4） 另一方面，由（7-1）于是，由（7-5）由(1)、(2)和反对称性*20定理7-7 (等幂律) 设L;是格，则对任意lL，有 证明 （a）由定理7-6 ,*
9、21定理7-8 （格的保序性）设L;是格，则对于任意l1, l2, l3, l4L, 有证明 (1) 又已知 由,和因为 所以由(1)有(2 )*22例4 设 L = 1,3,4,6,12, L上的整除关系与L构成一个格，记作， 3( 6 4 ) = 3 1= 3(36)(34) = 6 12 = 6于是 3(64)(36)(34)6(34) = 612 = 6(63)(64)= 31= 3于是 6(34)(63)(64)126431*23定理7-9 设是格，则对任意l1, l2, l3L,有(分配不等式)证明 (a)由(7-4)有于是，根据定理7-8 有又由（7-4）有 *243格的另一种定
10、义方式 定理7-10 设是一个代数系统,其中和都是二元运算, 满足交换律, 结合律和吸收律, 则在L上必存在一偏序关系, 使得是一个格(并且:中的取大和取小运算与代数系统的两个运算一致)。*25可以证明关系是L上的自反，反对称和可传递的关系，因此是L上的偏序关系。在L上定义二元关系：对任意l1,l2L, 当且仅当l1l2=l1时，有l2l1。进一步还可以证明, 对任意l1, l2L，l1l2是在偏序关系意义下l1和l2的最小上界, l1l2 是l1和l2的最大下界。故是一个格。 *26格既可以看作是一个偏序集，也可以看作是一个代数系统。定义7-7 设是一个代数系统，和是 L 上的两个二元运算，
11、如果这两个运算满足交换律，结合律和吸收律，则称是格。 *27例5 在全集合 U 的幂集 2U =S|SU上的包含关系“”是2U 上的一偏序关系。 因为对任意Si2U，总有Si Si，所以是自反的 。对任意Si , Sj2U , 若SiSj ，且SjSi ，则必有Si = Sj ，所以是反对称的。 对任意Si ,Sj ,Sk2U，若SiSj ，SjSk ，则必有SiSk，所以是可传递的。因此是一偏序集。*28对于任意Si , Sj2U，有SiSiSj，Sj,SiSj， 因此SiSj是Si和Sj的上界。 若有S2U，使得 SiS ，SjS，则必有SiSj S。 因此SiSj是Si和Sj的最小上界。
12、即lub(Si, Sj)= SiSj。 类似地可以证明，对任意Si,Sj2U，glb(Si,Sj)=SiSj因此是一个格另一方面，集合的并运算和交运算和2U构成代数系统，因为运算和都满足交换律，结合律和吸收律，因此是一个格。 *29例6 设U=a,b,c, 则2U=,a,b,c,a,b,a,c,b,c,a,b,c三 子格定义7-8 设是格, 如果是的子代数, 则称是的子格。格对应的代数系统形式的格是.子格也是一个格。*30令 S1=b,a,bb,c,a,b,cS2=,a, c,a, cS3=,a,c,a,b,a,c,b,c,a,b,c是的子格。也是的子格。 S3不能与这两个运算构成的子格。a,
13、b,c a,c b,ca,b a c b *312 6112 练习12643211 设 L = 1，2，3，4，6，12，在L上定义整除关系，构成偏序集。 （1） glb(6,4)= ; lub(2,3)= ；（2） 该偏序集的最小元素是 ，最大元素是 。*323 41 10 （1） glb(6,9) = ; glb(8,12) = .；（2） glb(9,7) = ; lub(5,10) = .。2设L=1，2，3，11，12，在L上定义整除关系，构成偏序集. 128421105639711*333. 下面给出的三个次序图，其中哪些是格？在图 下方相应的括号内键入“Y”或“N”表示肯定或否定。( ) ( ) ( )NYY*34YYNN4对下图所给出的格判断以下子集是否能构成它的子格。在相应的括号内键入“Y”或“N”来回答（1）S1=e,c,b ( )（2）S2=d,b,a ( ) （3）S3=c,d,b ( )（4）S4=e,c,d,a ( )edcba*35定义7-9 设是一个格, 若对于任意的l1, l2, l3 L,有则称是分配格。72 分配格和有补格dcbaecdbadbca一、分配格 1分配格的定义*36例1 对任意
