1、1第十一章第十一章 格与布尔代数格与布尔代数主要内容主要内容l 格的定义及性质格的定义及性质 l 子格子格l 分配格、有补格分配格、有补格l 布尔代数布尔代数211.1 格的定义与性质格的定义与性质 定义定义11.1 设设是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上都有最小上界和最大下界，则称界和最大下界，则称S关于偏序关于偏序 作成一个作成一个格格.求求x,y 最小上界和最大下界看成最小上界和最大下界看成 x 与与 y 的二元运算的二元运算和和，例例1 设设n是正整数，是正整数，Sn是是n的正因子的集合的正因子的集合.D为整除关系，则为整除关系，则偏序集偏序集构成格构成格.x,
2、ySn，xy是是lcm(x,y)，即，即x与与y的的最小公倍数最小公倍数.xy是是gcd(x,y)，即，即x与与y的最大公约数的最大公约数.3图2例例2 判断下列偏序集是否构成格，并说明理由判断下列偏序集是否构成格，并说明理由.(1)，其中，其中P(B)是集合是集合B的幂集的幂集.(2)，其中，其中Z是整数集，是整数集，为小于或等于关系为小于或等于关系.(3)偏序集的哈斯图分别在下图给出偏序集的哈斯图分别在下图给出.实例实例(1)幂集格幂集格.x,yP(B)，xy就是就是xy，xy就是就是xy.(2)是格是格.x,yZ，xy=max(x,y)，xy=min(x,y)，(3)都不是格都不是格.可
3、以找到两个结点缺少最大下界或最小上界可以找到两个结点缺少最大下界或最小上界4实例：子群格实例：子群格例例3 设设G是群，是群，L(G)是是G 的所有子群的集合的所有子群的集合.即即L(G)=H|HG，对任意的对任意的H1,H2L(G)，H1H2是是G 的子群，的子群，是由是由H1H2生成的子群（即包含着生成的子群（即包含着H1H2的最小子群）的最小子群）.在在L(G)上定义包含关系上定义包含关系，则，则L(G)关于包含关系构成一个关于包含关系构成一个格，称为格，称为G的子群格的子群格.在在 L(G)中，中，H1H2 就是就是 H1H2 H1H2 就是就是 5格的性质：对偶原理格的性质：对偶原理
4、定义定义11.2 设设 f 是含有格中元素以及符号是含有格中元素以及符号=,和和的命的命题题.令令 f*是将是将 f 中的中的 替换成替换成 ,替换成替换成 ,替换成替换成,替换替换成成所得到的命题所得到的命题.称称 f*为为 f 的的对偶命题对偶命题.例如例如,在格中令在格中令 f 是是(ab)c c,f*是是(ab)c c.格的格的对偶原理对偶原理 设设 f 是含有格中元素以及符号是含有格中元素以及符号=,和和等的命题等的命题.若若 f 对对一切格为真一切格为真,则则 f 的对偶命题的对偶命题 f*也对一切格为真也对一切格为真.例如例如,如果对一切格如果对一切格L都有都有 a,bL,ab
5、a，那么对一切格那么对一切格L都有都有 a,bL,ab a l 注意：对偶是相互的，即注意：对偶是相互的，即(f*)*=f6格的性质：算律格的性质：算律定理定理11.1 设设是格是格,则运算则运算和和适合交换律、结合律、适合交换律、结合律、幂等律和吸收律幂等律和吸收律,即即(1)a,bL 有有 ab=ba,ab=ba(2)a,b,cL 有有(ab)c=a(bc),(ab)c=a(bc)(3)aL 有有 aa=a,aa=a(4)a,bL 有有 a(ab)=a,a(ab)=a 7证明证明(1)ab是是 a,b 的最小上界的最小上界,ba是是 b,a 的最小上界的最小上界.由于由于 a,b =b,a
6、,所以所以 ab=ba.由对偶原理由对偶原理,ab=ba.(2)由最小上界的定义有由最小上界的定义有 (ab)c ab a (1)(ab)c ab b (2)(ab)c c (3)由式由式(2)和和(3)有有 (ab)c bc (4)由式由式(1)和和(4)有有 (ab)c a(bc)同理可证同理可证 (ab)c a(bc)根据反对称性根据反对称性 (ab)c=a(bc)由对偶原理由对偶原理,(ab)c=a(bc)8证明证明(3)显然显然 a aa,又由又由 a a 可得可得 aa a.根据反对称性根据反对称性有有aa=a.由对偶原理由对偶原理,aa=a 得证得证.(4)显然显然 a(ab)a
7、 (5)由由 a a,ab a 可得可得 a(ab)a (6)由式由式(5)和和(6)可得可得 a(ab)=a,根据对偶原理根据对偶原理,a(ab)=a 9格的性质：序与运算的关系格的性质：序与运算的关系定理定理11.2 设设L是格是格,则则 a,bL有有a b ab=a ab=b证证 (1)先证先证 a b ab=a由由 a a 和和 a b 可知可知 a 是是 a,b 的下界的下界,故故 a ab.显然有显然有ab a.由反对称性得由反对称性得 ab=a.(2)再证再证 ab=a ab=b根据吸收律有根据吸收律有 b=b(ba)由由 ab=a 和上面的等式得和上面的等式得 b=ba,即即
8、ab=b.(3)最后证最后证 ab=b a b由由 a ab 得得 a ab=b 10格的性质：保序格的性质：保序定理定理11.3 设设L是格是格,a,b,c,dL，若若a b 且且 c d,则则 ac bd,ac bd例例4 设设L是格是格,证明证明 a,b,cL有有 a(bc)(ab)(ac).证证 ac a b,ac c d 因此因此 ac bd.同理可证同理可证 ac bd 证证 由由 a a,bc b 得得 a(bc)ab由由 a a,bc c 得得 a(bc)ac从而得到从而得到a(bc)(ab)(ac)注意：一般说来注意：一般说来,格中的格中的和和运算不满足分配律运算不满足分配律
9、.11格作为代数系统的定义格作为代数系统的定义定理定理11.4 设设是具有两个二元运算的代数系统是具有两个二元运算的代数系统,若对若对于于 和和 运算适合交换律、结合律、吸收律运算适合交换律、结合律、吸收律,则可以适当定义则可以适当定义S中中的偏序的偏序 ,使得使得 构成格构成格,且且 a,bS 有有 ab=a b,ab=a b.证明省略证明省略.根据定理根据定理11.4,可以给出格的另一个等价定义可以给出格的另一个等价定义.定义定义11.3 设设是代数系统是代数系统,和和 是二元运算是二元运算,如如果果 和和 满足交换律、结合律和吸收律满足交换律、结合律和吸收律,则则构成格构成格.12子格及
10、其判别法子格及其判别法定义定义11.4 设设是格是格,S是是L的非空子集的非空子集,若若S关于关于L中中的运算的运算和和仍构成格仍构成格,则称则称S是是L的的子格子格.例例5 设格设格L如图所示如图所示.令令 S1=a,e,f,g,S2=a,b,e,gS1不是不是L的子格的子格,因为因为e,f S1 但但 ef=c S1.S2是是L的子格的子格.1311.2 分配格、有补格与布尔代数分配格、有补格与布尔代数 定义定义11.5 设设是格是格,若若 a,b,cL,有有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称则称L为为分配格分配格.l 注意：可以证明以上两个条件互为充分必要条件
11、注意：可以证明以上两个条件互为充分必要条件L1 和和 L2 是分配格是分配格,L3 和和 L4不是分配格不是分配格.称称 L3为为钻石格钻石格,L4为为五角格五角格.实例实例14分配格的判别及性质分配格的判别及性质定理定理11.5 设设L是格是格,则则L是分配格当且仅当是分配格当且仅当L不含有与钻石格不含有与钻石格或五角格同构的子格或五角格同构的子格.证明省略证明省略.推论推论 (1)小于五元的格都是分配格小于五元的格都是分配格.(2)任何一条链都是分配格任何一条链都是分配格.例例6 说明图中的格是否为分配格说明图中的格是否为分配格,为什么？为什么？解解 都不是分配格都不是分配格.a,b,c,
12、d,e 是是L1的子格的子格,同构于钻石格同构于钻石格 a,b,c,e,f 是是L2的子格的子格,同构于五角格；同构于五角格；a,c,b,e,f 是是L3的子格的子格 同构于钻石格同构于钻石格.15有界格的定义有界格的定义定义定义11.6 设设L是格是格,(1)若存在若存在aL使得使得 xL有有 a x,则称则称a为为L的的全下界全下界(2)若存在若存在bL使得使得 xL有有 x b,则称则称b为为L的的全上界全上界 说明：说明：l 格格L若存在全下界或全上界若存在全下界或全上界,一定是惟一的一定是惟一的.l 一般将格一般将格L的全下界记为的全下界记为0,全上界记为全上界记为1.定义定义11.
13、7 设设L是格是格,若若L存在全下界和全上界存在全下界和全上界,则称则称L 为为有界有界格格,一般将有界格一般将有界格L记为记为.16 定理定理11.6 设设是有界格是有界格,则则 aL有有a0=0,a0=a,a1=a,a1=1注意：注意：l 有限格有限格L=a1,a2,an是有界格是有界格,a1a2an是是L的全下的全下界界,a1a2an是是L的全上界的全上界.l 0是关于是关于运算的零元运算的零元,运算的单位元；运算的单位元；1是关于是关于运算的运算的零元零元,运算的单位元运算的单位元.l 对于涉及到有界格的命题对于涉及到有界格的命题,如果其中含有全下界如果其中含有全下界0或全上界或全上界
14、1,在求该命题的对偶命题时在求该命题的对偶命题时,必须将必须将0替换成替换成1,而将而将1替换替换成成0.有界格的性质有界格的性质17有界格中的补元及实例有界格中的补元及实例定义定义11.8 设设是有界格是有界格,aL,若存在若存在bL 使得使得 ab=0 和和 ab=1 成立成立,则称则称b是是a的的补元补元.l 注意：若注意：若b是是a的补元的补元,那么那么a也是也是b的补元的补元.a和和b互为补元互为补元.例例7 考虑下图中的格考虑下图中的格.针对不同的元素，求出所有的补元针对不同的元素，求出所有的补元.18解答解答(1)L1中中 a 与与 c 互为补元互为补元,其中其中 a 为全下界为
15、全下界,c为全上界为全上界,b 没有没有 补元补元.(2)L2中中 a 与与 d 互为补元互为补元,其中其中 a 为全下界为全下界,d 为全上界为全上界,b与与 c 也互为补元也互为补元.(3)L3中中a 与与 e 互为补元互为补元,其中其中 a 为全下界为全下界,e 为全上界为全上界,b 的补的补 元是元是 c 和和 d;c 的补元是的补元是 b 和和 d;d 的补元是的补元是 b 和和 c;b,c,d 每个元素都有两个补元每个元素都有两个补元.(4)L4中中 a 与与 e 互为补元互为补元,其中其中 a 为全下界为全下界,e 为全上界为全上界,b 的补的补 元是元是 c 和和 d;c 的补
16、元是的补元是 b;d 的补元是的补元是 b.19有界分配格的补元惟一性有界分配格的补元惟一性定理定理11.7 设设是有界分配格是有界分配格.若若L中元素中元素 a 存在存在补元补元,则存在惟一的补元则存在惟一的补元.证证 假设假设 c 是是 a 的补元的补元,则有则有 ac=1,ac=0,又知又知 b 是是 a 的补元的补元,故故 ab=1,ab=0 从而得到从而得到 ac=ab,ac=ab,由于由于L是分配格是分配格,b=c.注意：注意：l 在任何有界格中在任何有界格中,全下界全下界0与全上界与全上界1互补互补.l 对于一般元素对于一般元素,可能存在补元可能存在补元,也可能不存在补元也可能不
17、存在补元.如果如果存在补元存在补元,可能是惟一的可能是惟一的,也可能是多个补元也可能是多个补元.对于有界对于有界分配格分配格,如果元素存在补元如果元素存在补元,一定是惟一的一定是惟一的.20图9有补格的定义有补格的定义定义定义11.9 设设是有界格是有界格,若若L中所有元素都有补中所有元素都有补元存在元存在,则称则称L为为有补格有补格.例如例如,图中的图中的L2,L3和和L4是有补格是有补格,L1不是有补格不是有补格.21布尔代数的定义与实例布尔代数的定义与实例定义定义11.10 如果一个格是有补分配格如果一个格是有补分配格,则称它为布尔格或布则称它为布尔格或布尔代数尔代数.布尔代数标记为布尔
18、代数标记为,为求补运算为求补运算.例例8 设设 S110=1,2,5,10,11,22,55,110是是110的正因子集合，的正因子集合，gcd表示求最大公约数的运算，表示求最大公约数的运算，lcm表示求最小公倍数的运表示求最小公倍数的运算，问算，问是否构成布尔代数？为什么？是否构成布尔代数？为什么？解解 (1)不难验证不难验证S110关于关于gcd 和和 lcm 运算构成格运算构成格.(略略)(2)验证分配律验证分配律 x,y,zS110 有有 gcd(x,lcm(y,z)=lcm(gcd(x,y),gcd(x,z)(3)验证它是有补格验证它是有补格,1作为作为S110中的全下界中的全下界,
19、110为全上界为全上界,1和和110互为补元互为补元,2和和55互为补元互为补元,5和和22互为补元互为补元,10和和 11互为补元互为补元,从而证明了从而证明了为布尔代数为布尔代数.22实例实例例例9 设设B为任意集合为任意集合,证明证明B的幂集格的幂集格构成布尔代数构成布尔代数,称为集合代数称为集合代数.证证 (1)P(B)关于关于和和构成格构成格,因为因为和和运算满足交换律运算满足交换律,结合律和吸收律结合律和吸收律.(2)由于由于和和互相可分配互相可分配,因此因此P(B)是分配格是分配格.(3)全下界是空集全下界是空集,全上界是全上界是B.(4)根据绝对补的定义根据绝对补的定义,取全集
20、为取全集为B,xP(B),x是是x的补元的补元.从而证明从而证明P(B)是有补分配格是有补分配格,即布尔代数即布尔代数.23布尔代数的性质布尔代数的性质定理定理11.8 设设是布尔代数是布尔代数,则则(1)aB,(a)=a.(2)a,bB,(ab)=a b,(ab)=a b （德摩根律）（德摩根律）证证(1)(a)是是a 的补元的补元,a也是也是a 的补元的补元.由补元惟一性得由补元惟一性得(a)=a.(2)对任意对任意a,bB有有 (ab)(a b)=(aa b)(ba b)=(1b)(a 1)=11=1,(ab)(a b)=(aba)(abb)=(0b)(a0)=00=0a b 是是ab的
21、补元的补元,根据补元惟一性有根据补元惟一性有(ab)=a b,同理同理可证可证(ab)=a b.l 注意：德摩根律对有限个元素也是正确的注意：德摩根律对有限个元素也是正确的.24布尔代数作为代数系统的定义布尔代数作为代数系统的定义定义定义11.11 设设是代数系统是代数系统,和和 是二元运算是二元运算.若若 和和 运运算满足：算满足：(1)交换律交换律,即即 a,bB有有a b=b a,a b=b a(2)分配律分配律,即即 a,b,cB有有 a (b c)=(a b)(a c),a (b c)=(a b)(a c)(3)同一律同一律,即存在即存在0,1B,使得使得 aB有有a 1=a,a 0
22、=a(4)补元律补元律,即即 aB,存在存在 a B 使得使得 a a =0,a a =1 则称则称 是一个布尔代数是一个布尔代数.可以证明，布尔代数的两种定义是等价的可以证明，布尔代数的两种定义是等价的.25有限布尔代数的结构有限布尔代数的结构定义定义11.12 设设 L 是格是格,0L,若若 bL有有 0 b a b=a,则则称称 a 是是 L 中的中的原子原子.实例：实例：(1)L是正整数是正整数 n 的全体正因子关于整除关系构成的的全体正因子关于整除关系构成的格格,则则L的原子恰为的原子恰为n的全体素因子的全体素因子.(2)若若L是是B的幂集的幂集,则则L的原子就是的原子就是B中元素构
23、成的单元集中元素构成的单元集(3)图中图中L1的原子是的原子是a,L2的原子是的原子是a,b,c,L3的原子是的原子是a 和和 b10cab10abca10bL1L2L326有限布尔代数的表示定理有限布尔代数的表示定理定理定理11.9(有限布尔代数的表示定理有限布尔代数的表示定理)设设B是有限布尔代数是有限布尔代数,A是是B的全体原子构成的集合的全体原子构成的集合,则则B同构同构于于A的幂集代数的幂集代数P(A).实例实例:(1)S110关于关于gcd,lcm运算构成的布尔代数运算构成的布尔代数.它的原子是它的原子是2,5和和11,因此原子的集合因此原子的集合A=2,5,11.幂集幂集 P(A
24、)=,2,5,11,2,5,2,11,5,11,2,5,11.幂集代数是幂集代数是.只要令只要令 f:S110P(A),f(1)=,f(2)=2,f(5)=5,f(11)=11,f(10)=2,5,f(22)=2,11,f(55)=5,11,f(110)=A,那么那么 f 就是从就是从S110到幂集到幂集P(A)的同构映射的同构映射.27推论推论推论推论1 任何有限布尔代数的基数为任何有限布尔代数的基数为2n,nN.证证 设设B是有限布尔代数是有限布尔代数,A是是B的所有原子构成的集合的所有原子构成的集合,且且|A|=n,nN.由定理得由定理得 B P(A),而而|P(A)|=2n,所以所以|
25、B|=2n.推论推论2 任何等势的有限布尔代数都是同构的任何等势的有限布尔代数都是同构的.(证明省略证明省略)结论结论：l 有限布尔代数的基数都是有限布尔代数的基数都是2的幂的幂,l 对于任何自然数对于任何自然数n,仅存在一个仅存在一个2n元的布尔代数元的布尔代数.28图11实例实例下图给出了下图给出了 1 元元,2 元元,4 元和元和 8 元的布尔代数元的布尔代数.29第十一章第十一章 习题课习题课主要内容主要内容l 格的两个等价定义格的两个等价定义l 格的性质格的性质l 子格子格l 特殊格：分配格、有界格、有补格、布尔代数特殊格：分配格、有界格、有补格、布尔代数基本要求基本要求l 能够判别
26、给定偏序集或者代数系统是否构成格能够判别给定偏序集或者代数系统是否构成格l 能够确定一个命题的对偶命题能够确定一个命题的对偶命题l 能够证明格中的等式和不等式能够证明格中的等式和不等式l 能判别格能判别格L的子集的子集S是否构成子格是否构成子格l 能够判别给定的格是否为分配格、有补格能够判别给定的格是否为分配格、有补格l 能够判别布尔代数并证明布尔代数中的等式能够判别布尔代数并证明布尔代数中的等式 30练习练习11(1)证明格中的命题证明格中的命题,即即(ab)b=b(2)证明证明(ab)(cd)(ac)(bd)(1)(ab)b是是ab与与b的最小上界的最小上界,根据最小上界的定义根据最小上界
27、的定义有有(ab)b b.b是是ab与与b的上界的上界,故有故有(ab)b b.由由于于偏序的反对称性偏序的反对称性,等式得证等式得证.(2)ab a ac,ab b bd,所以所以(ab)(ac)(bd),同理同理(cd)(ac)(bd).从而得到从而得到 (ab)(cd)(ac)(bd)31解2求图中格的所有子格求图中格的所有子格.1元子格：元子格：a,b,c,d,e；2元子格：元子格：a,b,a,c,a,d,a,e,b,c,b,d,b,e,c,e,d,e；3元子格：元子格：a,b,c,a,b,d,a,b,e,a,c,e,a,d,e,b,c,e,b,d,e；4元子格：元子格：a,b,c,e
28、,a,b,d,e,b,c,d,e；5元子格：元子格：a,b,c,d,e 练习练习2eabcd32图133判别下述格判别下述格L是否为分配格是否为分配格.L1不是分配格不是分配格,因为它含有与钻石格同构的子格因为它含有与钻石格同构的子格.L2和和L3不是分配格不是分配格,因为它们含有与五角格同构的子格因为它们含有与五角格同构的子格.L1 L2 L3练习练习333L1 L2 L3图124针对下图，求出每个格的补元并说明它们是否为有补格针对下图，求出每个格的补元并说明它们是否为有补格L1中中,a与与h互为补元互为补元,其他元素没补元其他元素没补元.L2中中,a与与g互为补元互为补元.b的补元为的补元
29、为c,d,f；c的补元为的补元为b,d,e,f；d的补元为的补元为b,c,e；e的补元为的补元为c,d,f；f的补元为的补元为b,c,e.L3中中,a与与h互为补元互为补元,b的补元为的补元为d；c的补元为的补元为d；d的补元为的补元为b,c,g；g的补元为的补元为d.L2与与L3是有补格是有补格.练习练习4345对于以下各题给定的集合和运算判断它们是哪一类代数对于以下各题给定的集合和运算判断它们是哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）系统（半群、独异点、群、环、域、格、布尔代数）,并说并说明理由明理由.(1)S1=1,1/2,2,1/3,3,1/4,4,为普通乘法为普通乘法
30、.(2)S2=a1,a2,.,an,ai,ajS2,ai aj=ai,这里的这里的 n 为给定为给定 正整数正整数,n1.(3)S3=0,1,为普通乘法为普通乘法.(4)S4=1,2,3,6,x,yS4,x y与与x y分别表示分别表示 x 与与 y 的的最小公倍数和最大公约数最小公倍数和最大公约数.(5)S5=0,1,为模为模2加法加法,为模为模2乘法乘法.练习练习535解：解答解答(1)不是代数系统不是代数系统,因为乘法不封闭因为乘法不封闭,例如例如4 4=16.(2)是半群但不是独异点是半群但不是独异点,因为因为 运算满足结合律运算满足结合律,但是没有但是没有单单 位元位元.(3)是独异
31、点但不是群是独异点但不是群.因为因为 运算满足结合律运算满足结合律,单位元是单位元是1,可可 是是0没有乘法逆元没有乘法逆元.(4)是格是格,也是布尔代数也是布尔代数.因为这两个运算满足交换律和分配因为这两个运算满足交换律和分配 律；求最小公倍数运算的单位元是律；求最小公倍数运算的单位元是1,求最大公约数运算求最大公约数运算 的单位元是的单位元是6,满足同一律；两个运算满足补元律满足同一律；两个运算满足补元律.(5)是域是域.对于模对于模 n 的环的环Zn,当当n为素数时构成域为素数时构成域.36证证(2)由由 反之也对反之也对.下面证下面证明它们都等价于明它们都等价于ab.由由 得得即即 a
32、b,又由又由 ab 得得 bababa 10)2(6设设是布尔代数是布尔代数,证明对于证明对于B中任意元素中任意元素 a,bbabaa )()1(练习练习6;1,10 bababa即即得得00)()(abbabbababababaaabaa )(1)()()()1(1 babababaaabaaaa )(0)()()(137练习练习77.判断下述代数系统是否为格？是不是布尔代数？判断下述代数系统是否为格？是不是布尔代数？(1)S=1,3,4,12;任给任给 x,yS,x y=lcm(x,y),x y=gcd(x,y),其中其中 lcm 是求最小公倍数是求最小公倍数,gcd 是求最大公约数是求最大公约数.(2)S=0,1,2;是模是模3加法加法,是模是模3乘法乘法(3)S=0,.,n,其中其中n2;任给任给 x,yS,x y=max(x,y),x y=min(x,y)(1)是布尔代数是布尔代数.(2)不是格不是格.(3)是格是格,但不是布尔代数但不是布尔代数.
