第十三章格与布尔代数

1、第十三章 格与布尔代数13.1 13.1 格的定义与性质格的定义与性质 一、格作为偏序集的定义一、格作为偏序集的定义 定义13.1 设是偏序集,如果 x,y S,x,y都有最小上界和最大下界,则称S关于偏序 为一个格格。 由于最小上界和最大下界的唯一性,可以把求x,y的最小上界和最大下界看成x与y的二元运算和,即求xy和xy分别表示x与y的最小上界最小上界和最大下最大下界界。 本章中出现的和符号只代表格中的运算，而不再有其它的含义。例例13.1 设n是正整数,Sn是n的正因子的集合。D为整除关系,则偏序集构成格。 x,ySn,xy是lcm(x,y),即x与y的最小公倍数。 xy是gcd(x,y

2、),即x与y的最大公约数。图13.1给出了格，和.例例13.2 判断下列偏序集是否构成格,并说明理由。(1) ,其中P(B)是集合B的幂集。解解 :是格。 x,yP(B),xy就是xy,xy就是xy.由于和运算在P(B)上是封闭的,所以xy,xyP(B).称,为B的幂集格幂集格。(2) ,其中Z是整数集,为小于或等于关系。解解 :是格。x,yZ, xy = max(x,y), xy = min(x,y),它们都是整数。(3) 偏序集的哈斯图分别在图13.2中给出。 a,b没有最大下界不是格b,d有两个上界c和e,但没有最小上界不是格b,c有三个上界d,e,f,但没有最小上界。不是格不是格a,g

3、没有最大下界。例例13.3 设G是群,L(G)是G的所有子群的集合。即L(G)=H|HG，在L(G)上定义包含关系 ,则L(G)关于包含关系构成一个格,称为G的子群格子群格。 对任意的H1,H2L(G),H1H2也是G的子群,而是由H1H2生成的子群（即包含着H1H2的最小的子群）.易见在L(G)中,H1H2就是H1H2,H1H2就是. 二格的性质二格的性质 定义定义13.2 设f是含有格中元素以及符号=, , ,和的命题。令f*是将f中的 替换成 , 替换成 ,替换成,替换成所得到的命题。称f*为f的对偶命题对偶命题。 格的对偶原理格的对偶原理 设f是含有格中元素以及符号=, , ,和等的命

4、题。若f对一切格为真,则f的对偶命题f*也对一切格为真。例如,在格中令f是(ab)c c, 则f*是 (ab)c c . 例如,对一切格L都有 a,bL,ab a那么对一切格L都有a,bL,ab a许多格的性质都是互为对偶命题的。有了格的对偶原理,在证明格的性质时,只须证明其中的一个命题就可以了。2. 2. 运算性质运算性质 定理定理13.1 设是格,则运算和适合交换律交换律、 结合律结合律、幂等律幂等律和吸收律吸收律,即(1) a,b L 有 ab=ba, ab=ba a,b,cL 有(ab)c=a(bc), (ab)c=a(bc)(3) aL 有 aa=a, aa=a(4) a,bL 有a

5、(ab)=a, a(ab)=a (1)证：证： ab和ba分别是a,b和b,a的最小上界。 由于a,b=b,a,所以ab=ba. 由对偶原理,ab=ba得证。(2)证：证：由最小上界定义有 (ab)c ab a (ab)c ab b (ab)c c 由和有 (ab)c bc 由和有 (ab)c a（bc）同理可证 (ab)c a(bc)根据偏序关系的反对称性有 (ab)c=a(bc)由对偶原理， (ab)c=a(bc)得证。 （3）证：证：显然 a aa,又由 a a 可得 aa a。根据偏序关系的反对称性有 aa=a由对偶原理，aa=a得证。 （4）证：证：显然 a(ab) a 又由 a a

6、， ab a 可得 a(ab) a 由和可得 a(ab)=a由对偶原理，a(ab)=a得证。三格作为代数系统的定义三格作为代数系统的定义 定理定理13.2 设是具有两个二元运算的代数系 统,若对于*和 运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序 ,使得构成一个格,且 a,bS有ab=a*b, ab=a b.根据定理13.2,可以给出格的另一个等价定义。 定义定义13.3 设是代数系统,*和 是二元运算,如果*和 满足交换律,结合律和吸收律,则构成一个格。格中运算满足四条算律,还有一条幂等律(见定理13.1),但幂等律可以由吸收律推出,所以定义13.3中只须满足三条算律即可。证：(

7、1) 先证在S中*和运算都适合幂等律。aS，由吸收律得a*a=a*(a(a*a)=a同理有 aa=a(2) 在S上定义二元关系R， a，bS有Rab=b下面证明R是S上的偏序。根据幂等律， aS都有aa=a，即R所以R在S上是自反的。a，bS有aRb且bRaab=b且ba=aa= ba = ab=b这就证明了R在S上是反对称的。a，b，cS有aRb且bRcab=b且bc=cac = a(b c）ac = （ab)cac = b c=c aRc这就证明了R在S上是传递的。综上所述，R为S上的偏序，记为。证明构成格。a，bS有 a(a b)=(a a)b= a bb(a b)=(a (bb)= a

8、 b这就推出a a b和b a b，所以a b是a,b的上界。假设c为a,b的上界，则有a c=c和bc=c，从而有(ab) c=a (bc)= a c=c这就证明了a b c，所以a b是a,b的最小上界，即ab=ab为证明a*b是a，b的最大下界，先证ab=b a*b=a首先由ab=b可知a*b=a*(ab)=a反之由a*b=a可知ab=(a*b) b = b (b*a)= b由 ab=b a*b=a 有 ab a*b=a类似可证明a*b是a，b的最大下界，即ab=a*b 无论是偏序集定义的格,还是代数系统定义的格,都统称为格L. 定理定理13.3 设L是格，则 a,bL有 a b ab=

9、a ab=b由于 a a 和 a b 可知 a是a,b的下界故 a ab显然 ab a 根据关系的反对称性得 ab=a 因为ab=a，所以 ab= (ab) b=b证明：先证 a b ab=a 再证 ab=a ab=b最后证 ab=b a b 因为a ab,即a b 定理定理13.4 设L是格，则 a,b,c,dL,若a b且c d,则ac bd , ac bd证明：ac a b ac c d因此ac bd同理可证ac bd例13.4 设L是格，证明 a,b,cL有 a (bc) (ab) (ac) 证明： 由 a a, bc b 得 a (bc) ab由 a a, bc c 得 a (bc)

10、 ac 所以 a (bc) (ab) (ac) 格中 、运算不一定满足分配律1.判断下述偏序集是否构成格？如果不是说明理由。 不能构成格 可以构成格 可以构成格 2. 求下述命题的对偶命题。 （1）(ab)b = b (ab)b = b （2）b(ca) (bc)a b(ca) (bc)a 3.证明： (ab)(cd) (ac)(bd) 证明： ab a ac，ab b bd， 所以 (ab) (ac)(bd)， 同理(cd) (ac)(bd) 从而得到(ab)(cd) (ac)(bd) 方法二：所以 (cd) (ac)(bd)， 所以由定理4得 (ab) (ac)(bd)， 同理由 c ac

11、 和 d bd 从而得到(ab)(cd) (ac)(bd) a ac b bd 13.2 13.2 子格与格同态子格与格同态 定义定义13.4 设是格,S是L的非空子集,若S关于L中的运算和仍构成格,则称S是L的子格子格。解：S1不是L的子格对于e和f,有ef=c,但c S1.S2是L的子格例例13.5 设格L如图13.3所示。令S1=a,e,f,g， S2=a,b,e,g问S1和S2是否是L的子格？图13.3二格同态的定义及其性质二格同态的定义及其性质 1格同态的定义定义定义13.5 设L1和L2是格,f: L1L2,若 a,bL1有 f(ab)=f(a)f(b), f(ab)=f(a)f(

12、b)成立，则称f为格L1到L2的同态映射,简称格同态格同态。例例13.6 (1)设L1=2n|nZ+， L2=2n1|nN则L1和L2关于通常数的小于或等于关系构成格。 令f: L1L2,f(x)=x-1验证f是L1到L2的同态映射 证明： 对任意的x,yL1有xymax(x,y)f(xy)=f(max(x,y)=max(x,y)-1f(x)f(y)=(x-1)(y-1)=max(x-1,y-1)=max(x,y)-1即有 f(xy)=f(x)f(y), 同理 f(xy)=f(min(x,y)=min(x,y)-1 f(x)f(y)=(x-1)(y-1)=min(x-1,y-1)=min(x,

13、y)-1即 f(xy)=f(x)f(y)所以f是L1到L2的同态映射 (2) 如图13.4中的格L1,L2和L3，若定义f1: L1L2 f1(a)=f1(b)=f1(c)=a1, f1(d)=d1f2: L1L3 f2(a)=a2,f2(b)=b2,f2(c)=c2,f2(d)=d2问f1和f2是否格同态？L1L2L3解：解：f1和和f2都不是格同态，都不是格同态，f1(bc)=f1(d)=d1f1(b)f1(c)=a1a1=a1f1(bc)f1(b)f1(c)f2(bc)=f2(d)=d2f2(b)f2(c)=b2c2=c2f2(bc)f2(b)f2(c)定理定理13.5 设f是格L1到L

14、2的映射，（1）若f是格同态映射，则f是保序映射，即 x,y L1,有 x y f(x) f(y)（2）若f是双射，则f是格同构映射，当且仅当 x,y L1有 x y f(x) f(y) （1）证明：任取x,y L1,x y由定理13.3知 xyy 又由于f是格同态映射，必有 f(y)f(xy)=f(x)f(y), 所以有 f(x) f(y)(2)证明：充分性：只需证明是L1到L2的同态映射即可。任取x,y L1,令xy=z，由x z和y z知(x) (z) , (y) (z) 从而有(x)(y) (z)= (xy) 另一方面，由(x)(y)L2和的满射性可知，必存在uL1使得(u)=(x)(

15、y) 因此有(x) (u) , (y) (u) 由已知条件可得x u和y u从而推出 xy u再由已知条件得 (x)(y) (u)= (xy) 综合上述有 (x)(y)= (xy) 同理可证(x)(y)= (xy) 必要性：由(1)的结论必有 x y (x) (y) 反之，若 (x) (y) 由于是同构映射，则(xy) = (x)(y)=(y) 由于是双射，必有xy=y从而证明了 x y例13.7 设L1, L2是格,其中S12是12 的所有正因子构成的集合，D为整除关系，为 通常数的小于等于关系，令 f: S12 S12 , f(x)=x 问f是否是L1到 L2的格同构？解：不是。因为f(2

16、)=2 f(3)=3 f(2) f(3)但是 2 并不能整除3三格的直积三格的直积 类似于半群,群和环,也可以定义格的直积。定义定义13.6 设L1和L2是格,定义L1L2上的运算,: ,L1L2 = = 称为格L1和L2的直积直积。可以证明仍是格。 ,L1L2,有 = =交换律 ()=结合律 ()=()= 同理有()= 和运算满足吸收律 同理可证运算也满足交换律和结合律、吸收律从而证明L1L2仍是格。 例如：格L=,为通常的小于或等于关系,则 是L与L的直积，是格是格LL的最小元,是最大元与是不可比的其中 LL=,画出该格对应偏序集的哈斯图。 , 所以 ,13.3 13.3 分配格与有补格分

17、配格与有补格 1分配格的定义及实例 一般说来,格中运算对满足分配不等式,即 a,b,cL,有 a(bc) (ab)(ac)但是不一定满足分配律.满足分配律的格称为分配格。定义定义13.7 设是格,若 a,b,cL,有 a(bc)=(ab)(ac) a(bc)=(ab)(ac)则称L为分配格分配格。 上面两个等式互为对偶式。在证明L为分配格时,只须证明其中的一个等式即可。例13.8 分配格分配格b(cd)=be=b(bc)(bd)=aa=a不是分配格c(bd)=ca=c(cb)(cd)=ed=d不是分配格钻石格钻石格五角格五角格分配格的判别及性质分配格的判别及性质 定理定理13.6 设L是格,则

18、L是分配格当且仅当L中不含有与不含有与钻钻 石格或五角格同构的子格石格或五角格同构的子格。推论推论 (1)小于五元的格都是分配格。 (2)任何一条链都是分配格。例例13.9 说明图13.6中的格是否为分配格,为什么？不是分配格 因为a,b,c,d,e是L1的子格,并且同构于钻石格 不是分配格 a,b,c,e,f是L2的子格,并且同构于五角格 a,c,b,e,f是L3的子格,也同构于钻石格。 不是分配格 定理定理13.7 格L是分配格当且仅当 a,b,cL, ab=ac且ab=ac b=c.证证: 必要性。 a,b,cL,有 b=b(ab) (吸收律,交换律)=b(ac) (已知条件代入)=(b

19、a)(bc) (分配律)=(ac)(bc) (已知条件代入,交换律) =(ab)c (分配律)=(ac)c (已知条件代入)=c (交换律,吸收律)充分性。（反证法） 假若 a,b,cL,有 ab=ac且ab=ac b=c成立，而L不是分配格. 根据定理13.6，L中必含有与钻石格或五角格同构的子格。 从而推出xy=xz=u, xy=xz=v 但yz,与已知矛盾。 对五角格的情况同理可证。 假设L中含有与钻石格同构的子格,且该子格为u,v,x,y,z,其中u为它的最小元,v为它的最大元。 xyzuv使用定理13.7也可以判别一个格是否为分配格。 在L1中有 bc=bd, bc=bd, 但cd在

20、L2中有 bc=be, bc=be, 但ce在L3中有 cb=cd, cb=cd, 但bd 有补格有补格 定义定义13.8 设L是格,若存在aL使得 xL有a x,则称a为L的全下界全下界；若存在bL使得 xL有x b,则称b为L的全上界全上界。 格L若存在全下界或全上界,一定是唯一的。 假若a1和a2都是格L的全下界,则有a1 a2和a2 a1. 根据偏序关系 的反对称性必有a1=a2. 由于全下界和全上界的唯一性,一般将格L的全下界记为0,全上界记为1.全上界和全下界是格中最大元和最小元。全上界和全下界是格中最大元和最小元。定义定义13.9 设L是格,若L存在全下界和全上界,则称 L为有界

21、格有界格,并将L记为.不难看出,有限格有限格L一定是有界格一定是有界格。 设L是n元格,且L=a1,a2,an,那么a1a2an是L的全下界,而a1a2an是L的全上界。 对于无限格对于无限格L来说来说,有的是有界格有的是有界格,有的不是有界格。有的不是有界格。 如集合B的幂集格,不管B是有穷集还是无穷集,它都是有界格。 它的全下界是空集 ,全上界是B. 整数集Z关于通常数的小于或等于关系构成的格不是有界格,因为不存在最小和最大的整数。因此L是有界格。定理定理13.8 设是有界格,则 aL有a0=0, a0=a， a1=a, a1=1全下界0是关于运算的零元,运算的单位元。 全上界1是关于运算

22、的零元,运算的单位元。 对于涉及到有界格的命题,如果其中含有全下界0或全上界1,在求该命题的对偶命题时,必须将0替换成1,而将1替换成0. 在有界格中,定义定义13.10 设是有界格,aL,若存在bL 使得 ab=0 和 ab=1成立,则称b是a的补元补元。a和b互为补元。 例例13.10 考虑下图中的四个格。a与c互为补元, b没有补元。L1L1是有界格,a是全下界,c是全上界a与d互为补元, b与c 也互为补元。L3中的a与e互为补元, b的补元是c和d,c的补元是b和d,d的补元是b和c. b,c,d每个元素都有两个补元。L2L3L2是有界格,a是全下界,d是全上界L3是有界格,其中a为

23、全下界,e为全上界,L4中的a与e互为补元, b的补元是c和d,c的补元是b,d的补元是b。 L4是有界格,其中a为全下界,e为全上界,在任何有界格中，全下界0与全上界1互补。 对于其他元素，可能存在补元，也可能不存在补元。如果存在，可能是惟一的，也可能是多个补元。对于有界分配格，如果它的元素存在补元，一定是唯一的。定理定理13.9 设是有界分配格有界分配格。若L中元素a存在补元，则存在唯一的补元存在唯一的补元。 证证: 假设b,c是a的补元，则有 ac=1, ac=0, 又知b是a的补元，故ab=1, ab=0 从而得到 ac=ab, ac=ab, 由于L是分配格，根据定理13.7，b=c.

24、定义定义13.11 设是有界格,若L中所有元素都 有补元存在，则称L为有补格。 例如，图13.5中: L2,L3和L4是有补格，L1不是有补格。 图13.6中L2和L3是有补格，L1不是有补格。1.判别下述格L是否为分配格。求出每个格的补元。说明它们是否为有补格。 L1 L2 不是分配格 它含有与钻石格同构的子格a,b,c,d,e。 含有与五角格同构的子格 不是分配格 a与h互为补元，其它元素没有补元。a与g互为补元； b的补元为c,d,f； c的补元为b,d,e,f; d的补元为b,c,e； e的 补元为c,d,f；f的补元为b,c,e。 是有补格 不是有补格。 L3含有与五角格同构的子格

25、a,b,g,h,d不是分配格 a与h互为补元， b的补元为d； c的补元为d； d的补元为b,c,g； g的补元为d。 是有补格 13.4 13.4 布尔代数布尔代数 1布尔代数作为格的定义及实例定义定义13.12 如果一个格是有补分配格,则称它为布尔格布尔格 或布尔代数布尔代数。根据定理13.9,在分配格中,如果一个元素存在补元,则是唯一的。 因此,在布尔代数中,每个元素都存在着唯一的补元,可以把求补元的运算看作是布尔代数中的一元运算。 从而可以把一个布尔代数标记为,其中,0,1和有界格一样,为求补运算, aB,a是a的补元。例例13.11 设S110=1,2,5,10,11,22,55,1

26、10是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问是否构成布尔代数？为什么？解解 : 容易验证 x,yS110有gcd(x,y)S110和lcm(x,y)S110.且 x,y,zS110有gcd(x,y)=gcd(y,x) lcm(x,y)=lcm(y,x)交换律结合律 gcd(gcd(x,y),z)=gcd(x,gcd(y,z) lcm(lcm(x,y),z)=lcm(x,lcm(y,z) 吸收律 gcd(x,lcm(x,y)=xlcm(x,gcd(x,y)=x因此,构成格。 先证明它是格。下面证明它是分配格。 易验证 x,y,zS110 有gcd(x,lc

27、m(y,z)=lcm(gcd(x,y),gcd(x,z)1作为S110中的全下界,110为全上界,且1和110互为补元,2和55互为补元,5和22互为补元,10和11互为补元,最后证明它是有补格。从而证明了为布尔代数。例例13.12 设B为任意集合,证明B的幂集格 构成布尔代数,称为集合代数集合代数。 证证: 因为和运算满足交换律,结合律和吸收律, 所以P(B)关于和构成格 由于和互相可分配,因此P(B)是分配格, 且全下界是空集 ,全上界是B. 根据绝对补的定义,取全集为B, xP(B),x是x的补元。 从而证明P(B)是有补分配格,即布尔代数。 所以P(B)是有补格2. 布尔代数的性质布尔

28、代数的性质 定理定理13.10 设是布尔代数,则 (1) aB, (a)=a .(2) a,bB, (ab)=ab, (ab)= ab 证证: (1) (a)是a的补元。a也是a的补元。 由补元的唯一性得(a)=a .(2) 对任意a,bB有(ab)(ab)=(aab)(bab)=(1b)( a1) = 11 = 1,(ab)(ab)=(aba)(abb)=(0b)(a0) = 00 = 0. 所以ab是ab的补元,根据补元的唯一性有(ab)=ab同理可证(ab)= ab. (1)称为双重否定律双重否定律,(2)称为德摩根律德摩根律。 3. 布尔代数作为代数系统的定义布尔代数作为代数系统的定义

29、 定义定义13.13 设是代数系统,*和 是二元运算。 若*和 运算满足：(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=a (4) 补元律,即 aB,存在a B使得 a*a=0, a a=1 则称是一个布尔代数布尔代数。 同一律就是指运算含有单位元的性质，这里的1是*运算的单位元,0是 运算的单位元。 可以证明这个定义与有补分配格的定义是等价的。 例例13.11 设S110=1,2,5,10,

30、11,22,55,110是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问是否构成布尔代数？为什么？例例13.12 设B为任意集合,证明B的幂集格 构成布尔代数,称为集合代数集合代数。 解：只需验证gcd,lcm运算是否满足：交换律、分配律、 同一律和补元律。解：只需验证,运算是否满足：交换律、分配律、 同一律和补元律。二布尔代数的子代数及实例二布尔代数的子代数及实例 定义定义13.14 设是布尔代数,S是B的非空 子集,若0,1S,且S对,和运算都是封 闭的,则称S是B的子布尔代数子布尔代数。例例13.13 设是布尔代数,a,bB,且a b. 令 S=x|xB,

31、且a x b称S为B中的区间,可简记为a,b. 证明a,b是一个布尔代数。 证明: S为B的非空子集,且a,b分别为S的全上界和全下界.对任意的x,yS,都有 a xy b 和 a xy b 这说明S关于和运算是封闭的.易见和运算在S上适合交换律和分配律.对任意的xS,都有 xa=x , xb=x ,满足同一律对任意的xS,令 y=(ax ) b a ax , a b, 故 (ax ) b所以 yS,xy=x ( (ax ) b) =x (a b )(x b) (分配律) =(x x ) (x b) (分配律) =1 (x b) (补元律) = x b (交换律,同一律) =x a(x b)

32、(由a b) =x (x b) (由a x) = b (由x b) 下面证明y是x的补元 x y=x ( (a x ) b) =(x a)(x x ) (分配律) =(x a) 0 (补元律) = a (由a x) =x (a x ) (由x b) = x a (同一律) 由定义构成一布尔代数,其全下界为a,全上界为b,对任意的xS, x关于这个全上界和全下界的补元是(ax ) b当a=0且b=1时,这时S是B的子布尔代数.但当a0或b1时, S不是B的子布尔代数.S满足补元律例例13.14 考虑110的正因子集合S110关于gcd,lcm运算构成的布尔代数。 它有以下的子布尔代数： 1,11

33、01,2,55,1101,5,22,1101,10,11,1101,2,5,10,11,22,55,110 三布尔代数的同态映射及实例三布尔代数的同态映射及实例 定义定义13.15 设和是两个布尔代数。 这里的, -泛指布尔代数B2中的求最大下界,最小上界和补元的运算。和E分别是B2的全下界和全上界。 f: B1B2.如果对于任意的a,bB1有 f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(a )=-f(a)则称f是布尔代数B1到B2的同态映射,简称布尔代数的同态布尔代数的同态。类似于其它代数系统,也可以定义布尔代数的单同态,满同态和同构。例例13.15 设和是布尔代数。f: B

34、1B2.若 a,bB1有 f(ab)=f(a)f(b) f(a )=-f(a)证明f是B1到B2的同态。证证: 只须证明 a,bB1有f(ab)=f(a)f(b) 成立即可。 f(ab) = f(ab) ) ) (双重否定律)= -f(ab) ) =-f(a b ) (德摩根律)=-(f(a )f(b )= -(-f(a)-f(b) = -(-f(a)-(-f(b) (德摩根律)= f(a)f(b) (双重否定律)根据以上例题可知,为证明f: B1B2是布尔代数B1到B2的同态映射,只须验证两个等式,即 a,bB1. f(ab)=f(a)f(b) ( 或者 f(ab)=f(a)f(b) )f(a )=-f(a) 四有限布尔代数的结构四有限布尔代数的结构 1 1有限布尔代数中的原子有限布尔代数中的原子 定义定义13.16 设L是格,0L,若 bL有有 0 b a