CHAPT19格与布尔代数.ppt

2019/7/14,离散数学,1,第十九章 格与布尔代数,2019/7/14,离散数学,2,目录,本章介绍另外一类具有两种二元运算的代数系统格，以及特殊的格布尔代数： 格是描述集合或命题的代数系统，称为集合代数或命题代数 19.1 格的定义 19.2 格的性质 19 3 几种特殊的格 19.4 布尔代数 19.5 有限布尔代数的结构,2019/7/14,离散数学,3,19.1 格的定义,2019/7/14,离散数学,4,格的定义,定义19.1.1：设 L, 是一个偏序集。如果对任意a，bL，a，b在L中都有最大下界和最小上界，则称 L, 是一个格。 常将a，b的最大下界记为infa, b，最小上界记为supa, b。,2019/7/14,离散数学,5,复习定义2.4.5和定义2.4.6,上(下)界：设是一个偏序集,BA,若存在aA ,使得对任何xB都有x a(或a x) , 则称a为B的上(下)界。（如果存在，上(下)界可在A中，也可在B中） 上(下)确界：设是一个偏序集，BA，若a是B的一个上(下)界，且对B的任何一个上(下)界x，均有a x (或x a) , 则称a为B的上(下)确界，也可称为最小上界（或最大下界）。记为a=sup(B) (a=inf(B) )。,2019/7/14,离散数学,6,几个是格的偏序集,(a),(b),(c),图(a)中是一个全序集(链)，自然是一个格。 不难验证，图(b)和图(c)中的偏序集中任意两个元素都有最小上界和最大下界，因而都是格。,2019/7/14,离散数学,7,并非所有偏序集都是格,不是所有的偏序集都是格。 图(d), (e), (f)所表示的偏序集都不是格。不难找出它们之中存在着两个元素，或没有最小上界，或没有最大下界。,(d),(e),(f),2019/7/14,离散数学,8,子集格,例1：设S是集合，(S)是S的幂集。 于是 (S), 是一个格，称为S的子集格。 因为： 首先， (S), 是一个偏序集；,其次，对任意的A, B(S)，有 supA, B = AB； infA, B = AB。,2019/7/14,离散数学,9,整除格,例2：设Z+是所有自然数的集合。 | 是Z+上的整除关系。于是Z+, | 是一个格，称为整除格。因为 首先， Z+, | 是一个偏序集；,其次，对任意的m, nZ+，有 supm, n = m, n(最小公倍数)； infm, n = (m, n)(最大公约数)。,2019/7/14,离散数学,10,子群格,例3：设G是群，S(G)表示G的所有子群组成的集合。 于是 S(G), 是一个格，称为G的子群格。因为 首先， S(G), 是一个偏序集；,其次，对任意的H, KS(G)，有 supH, K是包含HK的最小子群； infH, K = HK。,2019/7/14,离散数学,11,子格,定义19.1.2：设 L, 是格，SL，如果 S, 也是格，则称 S, 是 L, 的子格。 偏序集的任何子集仍是偏序集。但是格 L, 中的偏序集L的子集S却不一定能够构成格 S, 。 例如，在整除格中，取S=1，2，3，则 S, | 不是格。因为按整除关系2,3=6,而6S，即sup2,3不存在。,2019/7/14,离散数学,12,整除格的子格,例4：设n是正整数，Sn = k | k0且k|n。 比如：S6 = 1, 2, 3, 6，S8 = 1, 2, 4, 8，S24 = 1, 2, 3, 4, 6, 8, 12, 24， 容易验证， Sn, | 是格，且m|n当且仅当SmSn。因此对任意的m，n，若m|n，则 Sm, | 是 Sn, | 的子格。 当然 Sn, | 的子格还有其它形式，比如 a, | 也是 Sn, | 的子格，其中aSn。,2019/7/14,离散数学,13,格中的运算,格中的inf和sup实际上是两个二元运算。 用算符和分别表示inf和sup，即 ab = infa, b，ab = supa, b。 这两种运算满足如下的性质： (1)交换律： ab= ba， ab= ba； (2)结合律： a(bc)=(ab)c, a(bc)=(ab)c (3)吸收律： a(ab) = a, a(ab) = a。,？,因为a(ab) = infa, supa, b ，所以 a(ab) a，即infa, supa, b a 又因为，aa且asupa, b，所以a是 a与supa, b的下界，即ainfa, supa, b 于是infa, supa, b ainfa, supa, b 即a(ab) = a。 同理可证a(ab) = a。,格就是具有以上性质的二元运算的代数系统。,2019/7/14,离散数学,14,从代数系统来定义格,定义19.1.3：设L是一个集合，和是L上的两个二元封闭运算，若和对a, b, cL，满足： (1)交换律： ab= ba， ab= ba； (2)结合律： a(bc) = (ab) c, a(bc) = (ab)c (3)吸收律： a(ab) = a, a(ab) = a。 则称代数系统L, , 是一个格。 L, 称为偏序格，L, , 称为代数格。,2019/7/14,离散数学,15,代数格的例子,例5：设S是集合，于是(S), , 是一个代数格。 例6：设Z+是自然数集合。定义运算和 为： mn = (m, n)(最大公约数)， mn = m, n (最小公倍数)。 则Z+, , 是一个代数格。,2019/7/14,离散数学,16,代数格和偏序格是等价的,定理19.1.1：偏序格必是代数格，反之亦然。 证明：设L, 是偏序格，对a, bL，令 ab = infa, b ab = supa, b。 显然，和是L上的封闭运算。由前面的讨论可知和满足交换律、结合律和吸收律，因此 L, , 是一个代数格。 下证代数格L, , 必是偏序格。为此，需要证明：(1)L是偏序集；(2)对a, bL，infa, b和supa, b都存在。,2019/7/14,离散数学,17,代数格和偏序格是等价的,定理19.1.1：偏序格必是代数格，反之亦然。 证明：先证代数格L, , 中L是偏序集。为此在L上定义二元关系如下：对a, bL， a b 当且仅当 a b = a。 (1)a a = a (a(aa) = a，aa。(自反的) (2)若ab, ba, 则ab=a, ba=b。而ab=ba a = b。 (反对称的) (3)若ab, bc, 则ac=(ab)c=a(bc) =ab=a， ac。(传递的) 是偏序关系，即L是偏序集。,2019/7/14,离散数学,18,注意：定义“”， ab当且仅当ab =a,定理19.1.1：偏序格必是代数格，反之亦然。 证明：下证a, bL，infa, b和supa, b存在。 由交换律和自反性有：(ab)a = a(ba)= a(ab)= (aa)b= ab； (ab)b= a(bb)= ab，于是 ab a, ab b, 从而ab是a, b的下界。 设c是a和b的任意下界，即c a，c b，则ca=c, cb=c。于是c(ab)=(ca)b=cb=c，即cab。因此ab = infa, b。 同理可证ab =supa, b。 总之，代数格必是偏序格。,由定理可知，互为等价的两个格L, 和L, , ，其运算, 可以分别是在偏序关系下，两个运算对象的最大下界和最小上界。,2019/7/14,离散数学,19,代数格的子格,定义19.1.4：若L, , 是格，SL且S对运算和封闭，则称S, 为L, 的子格。 设L, 和L, , 是等价的两个格，SL。若S, , 是L, , 的子格，则S, 也是L, 的子格。,a1,a2,a3,a4,a5,但是，若S, 是L, 的子格，而S, , 不一定是L, , 的子格。,例如，右图所示的格，其中L=a1, a2, a3, a4, a5。取S=a1, a2, a3, a5。显然S, 是L, 的子格，而 S, , 却不是L, , 的子格。因为a2a3= a4S。,这说明，偏序格的子格和代数格的子格的定义是有区别的。,2019/7/14,离散数学,20,19.2 格的性质,2019/7/14,离散数学,21,偏序关系与运算,我们知道，偏序格L, 是等价于代数格L, , ，其中对任意a, bL，a b = infa, b, a b = supa, b。从偏序格与代数格等价性的证明中可看到，L中元素的偏序关系是用运算和来定义的。即： ab当且仅当ab=a当且仅当ab=b。,定理19.2.1：设L, 是格， a, bL。于是， ab当且仅当ab=a当且仅当ab=b。,证明：若ab，由aa知，a是a, b的下界，故aab。又由的定义,aba，故ab=a。,若ab=a，则由吸收律可知： ab=(ab) b=b。,若ab=b，则由 的定义知ab=supa,b ，于是b= supa,b ，故 ab 。,2019/7/14,离散数学,22,格中的运算保偏序关系,定理19.2.2：设L, 是格， a, b, cL。于是，若bc，则 ab ac， ab ac。 证明：因bc，由定理19.2.1知bc = b。于是， (ab)(ac) = a(ba) c = a(ab) c = (aa)(b c) = ab 再由定理19.2.1知，ab ac。 同理可证 ab ac。,2019/7/14,离散数学,23,分配不等式,在环和域中，加法和乘法这两种运算是通过乘法对加法的分配律联系起来的。那么，在格中的两种运算是否也存在分配律呢？,一般来说，在格中的两种运算中分配律是不成立的，倒是存在两个分配律的不等式。,定理19.2.3：设L, 是格， a, b, cL。于是， a(bc) (ab)(ac) (ab)(ac) a(bc) 证明：因为a(ab)，a(ac)，所以 a(ab)(ac) (19.1) 又因bcb(ab)，bcc(ac)，所以 bc(ab)(ac) (19.2) 综合(19.1)和(19.2)有a(bc)(ab)(ac)。 同理可证(ab)(ac) a(bc)。,2019/7/14,离散数学,24,模不等式,定理19.2.4：设L, 是格， a, b, cL。于是， ab当且仅当a(bc) b(ac)。 证明：若ab，则由定理19.2.1知， ab=b。又由定理19.2.3知， a(bc) (ab)(ac) = b(ac)。 反之，若a(bc) b(ac)，则因为 a a(bc) b(ac) b。 所以有ab。 总之，ab当且仅当a(bc) b(ac)。,2019/7/14,离散数学,25,格的同态,定义19.2.1 设L, , 和S, ,是两个格，f是L到S的映射。若对任意a,bL,有： f(ab)=f(a)f(b) f(a b)=f(a)f(b) 则称f是L到S的格同态。特别，L到L的格同态称为格的自同态；若f是双射，则称f是格同构，并称L与S是同构的。,2019/7/14,离散数学,26,保序映射,定理19.2.5 设L, , 和S, ,是两个格，它们分别对应偏序关系L和S， f是L到S的格同态。于是，对任意a,bL,若aLb,则f(a)Sf(b)。称f是保序映射。 证明： aLb, ab=a,从而f(ab)=f(a),于是f(a)= f(ab)=f(a)f(b)，故 f(a)Sf(b)。 此定理说明，同态映射必是保序映射，但反之不然。,2019/7/14,离散数学,27,保序映射不一定是同态映射,例子：已知S12,| 和S12, 是两个格，其中“”是普通的小于等于关系。设它们分别对应代数格S12, 和S12,于是,对任意a,b S12 ab=(a,b) a b=a,b ab=mina,b ab=maxa,b 现定义恒等映射g(a)=a, a S12,则g是S12, |到S12, 的保序映射，但不是同态映射，例如：g(2 3)=g(6)=6，而g(2)g(3)=23=3,2019/7/14,离散数学,28,自同态像是代数子格,定理19.2.6 设L, , 是一个格，g是L的自同态，于是，g(L)是L的代数子格。 证明：任取a,bg(L)，则存在a,bL，使g(a)=a, g(b)=b。于是 ab= g(a)g(b)= g(ab)g(L) a b= g(a) g(b)= g(ab)g(L) 这说明g(L)在运算、下封闭，故 g(L), , 是L, , 的代数子格。,2019/7/14,离散数学,29,格同构的逆也是格同构,定理19.2.7 设L, , 和S, ,是两个格，若g是L到S的格同构，则g1是S到L的格同构。 证明：显然， g1是S到L的双射。任取a,bS，则有唯一的a,bL，使g(a)=a,g(b)=b。从而 g1(ab)= g1(g(a)g(b) = g1(g(ab)= ab= g1(a)g1(b) 同理， g1(ab)= g1(a) g1(b) 由定理19.2.5和定理19.2.7 ，我们有： 定理19.2.8 若g是格L, , 到格S, ,的格同构，则对任意a,bL, aLb当且仅当g(a)Sg(b),2019/7/14,离散数学,30,n维格,设L=0，1，规定00，01，11，于是L, 是一个格。令： Ln=| aiL，i=1,n，n2 规定 n当且仅当aibi i=1,n。于是Ln, 是一个格,称为n维格。例如:,L, ,0,1,L2, ,L3, ,令Ln, , 是与格Ln, 等价的代数格 易证，对任意， Ln,有 = = 其中，a b=infa,b, ab=supa,b,2019/7/14,离散数学,31,与n维格同构的例,例1：设S=x1,xn,于是,子集格(S), 与n维格 Ln, 同构。 证明：定义(S)到Ln的映射f如下:任取A (S)，f(A)= ,其中ai=1当且仅当xiA , i=1,n，显然，f是(S)到Ln的双射。 下证同态性：任取A,B(S),令f(A)= 。f(B)= , f(AB)= ,于是，由f的定义有： ai =1 当且仅当 xiA ， i=1,n bi =1 当且仅当 xiB ， i=1,n ci =1 当且仅当 xiAB ，i=1,n,2019/7/14,离散数学,32,与n维格同构的例, ci =1 当且仅当 xiAB ，i=1,n 从而ci =1当且仅当 xiA且xiB,当且仅当ai =1且bi =1,i=1,n.因此ci = ai bi ,i=1,n，故 = = 这说明f(AB)= f(A)f(B) 同理可证f(AB)= f(A) f(B),2019/7/14,离散数学,33,19.3 几种特殊的格,2019/7/14,离散数学,34,最小上界与最大下界的推广,命题19.3.1 设L, 是一个格，于是，L的任何非空有限子集S都有一个最小上界和最大下界。 证明：对S中元素个数作归纳证明。设|S|=n，n1。 n=1时，结论显然成立。 假设|S|=n-1时，结论成立。,2019/7/14,离散数学,35,|S|=n1时,设S=a1,an-1,an.令S=a1,an-1。由归纳假设，S有一个最小上界，设为aL,于是，a,an也有最小上界，设为a。下证a就是S的最小上界。 因为aa，ana，而a是S的上界，所以a1a, an-1a。于是a1a, an-1a, ana，从而a是S的上界。任取S的一个上界b，则有a1b, an-1b, anb，于是b是S的上界，故a b,又因为anb，所以b是a,an的上界，而a是a,an的最小上界，故a b，这说明a是S的最小上界。 同理可证S有一个最大下界。,2019/7/14,离散数学,36,格的无限子集不一定有最小上界或最大下界,通常将子集S的最小上界记为supS,最大下界记为infS。 注意：一个格的无限子集不一定有最小上界或最大下界。例如,在格Z+, 中,令所有正奇数作成的集合为D+，于是D+ Z+，但D+没有最小上界。,2019/7/14,离散数学,37,有界格,定义19.3.1 设L, 是一个格，若L有最小元素（记为0）和最大元素（记为1），则称L为有界格。 有时，将有界格L, 的等价代数格记为 L, ，0，1，其中0和1称为L的界。 设R为实数集，L=xR| 0x1，则L, 是一个有界格。,2019/7/14,离散数学,38,有限格必是有界格,由命题19.3.1知，有限格必是有界格。令L=a1,an，则L是有界格，并且： 0= a1 an 1 = a1 an 命题19.3.2 若L, 是有界格，则对任意aL，有： a 0=a， a 1=a a 1=1， a 0=0 证明：因为对任意aL，有0 a，a 1。所以a 0=a， a 1=a， a 1=1， a 0=0。,2019/7/14,离散数学,39,余元素,定义19.3.2 设L, 是有界格，a,bL,如果ab=0，a b=1，则称a和b互为余元素。 有界格中，一个元素可能没有余元素，若有也可能不止一个。例如：,a,b,1,0,a和b都无余元素,a,b,1,0,a和b互为余元素(唯一),a,b,c,0,1,a的余元素是b和c,2019/7/14,离散数学,40,有余格,命题19.3.3 在有界格L, ，0，1中，0是1的唯一余元素，1是0的唯一余元素。 证明： (证0是1的唯一余元素)由命题19.3.2知， 01=0；01=1。 所以0与1互为余元素。 设cL是1的余元素，则： 1c=0；1c=1 但因为c1，所以1c=c，因此c=0。 同理可证1是0的唯一余元素。,定义19.3.3 设L, 是有界格，若L中每个元素至少有一个余元素，则称L, 为有余格。,例2 设S=a1,an,则(S), 是有余格。其中和S是(S), 的界,A(S)的余元素为SA。,2019/7/14,离散数学,41,分配格,定义19.3.4 设L, , 是一个格，如果对任意的a,b,cL，有 a(bc)=(ab)(ac) a (bc)=(ab)(ac) 则称格L为分配格。 注意：分配格定义中的两个等式是等价的，即由一个等式可推出另一个等式。,另外，并不是所有格都是分配格。例如上述Hasse图所表示的格都不是分配格。,b(ac)=b(ba)(bc)=c 故不是分配格,a,b,c,0,1,u(vw)=u(uv)(uw)=0 故不是分配格,u,v,w,0,1,2019/7/14,离散数学,42,链都是分配格,有一类格是分配格，即： 命题19.3.4 任意一个链都是分配格。 证明：设L, 是一个链，任取a,bL，则可分以下两种情况讨论。 ba且ca,这时,bca,从而a(bc )= b c而ab=b，ac=c,于是，(ab)(ac)=bc，故 a(b c )= (ab) (a c),2019/7/14,离散数学,43,链都是分配格,ab或ac，这时abbc或者acbc，从而总有ab c,于是，a(b c)=a。 而ab=a或ac=a，故由吸收律知， (ab) (a c)= a (ac) =a，或者 (ab) (a c)= (ab) a=a，故 a(b c)= (ab) (a c) 不难验证，Ln, n， (S), , Sn, | 以及Z+, | 等都是分配格，但它们都不是链。,2019/7/14,离散数学,44,De Morgan律,定理19.3.1 设L, , 是分配格，a,bL,于是，若a,b有余元素a,b，则 (ab)=ab ； (ab)=ab 证明： （证(ab)=ab）因为 (ab)(ab)=(aba)(abb) =(1b)(a1)=11=1 ；而 (ab) (ab)=(aab) (bab) =0 0=0 所以(ab)=ab ，同理有(ab)=ab,2019/7/14,离散数学,45,模 格,定义19.3.5 设L, 是一个格，对任意a,b,cL,如果由ab可推出a(bc) =b(ac)，则称 L, 为模格。 分配格必是模格。设L, , 是分配格， 任取a,b,cL，若ab，则 a(bc) =(a b)(ac) =b(ac)。 但模格不一定是分配格。如图所示的格是模格但不是分配格。 如何判断一个格是否为模格？我们有如下定理。,2019/7/14,离散数学,46,模格的充分必要条件,定理19.3.2 格L, 为模格的充分必要条件是，对任意a,b,cL,若a b，ac=bc，ac=bc，则a=b。 证明：必要性设L, 是模格，a,b,cL，若 a b，ac=bc，ac=bc，则由吸收律和给定的条件，有： a= a(ac)=a(bc) =b(ac)=b(bc)=b 即a=b。 下证充分性。,2019/7/14,离散数学,47,模格的充分必要条件,充分性任取a,b,cL， 设ab。因为(a(bc)c= a(bc) c)= ac (19.5) 又因ab,aac,所以ab(ac ), 从而由定理19.2.2, ac(b(ac ) c (ac )c= ac， 故有 (b(ac ) c= ac (19.6) 由(19.5)和(19.6)式有 (a(bc)c=(b(a c)c (19.7),2019/7/14,离散数学,48,模格的充分必要条件,另一方面, (b(ac)c= b(ac)c)=bc (19.8) 而bca(bc)，所以由定理19.2.4有 bc=(bc)c (a(bc)c (b(ac)c = b(ac)c)= bc 故 (a(bc)c =bc (19.9) 由(19.8)和 (19.9)式有 (a(bc)c = (b(ac)c (19.10),2019/7/14,离散数学,49,模格的充分必要条件,又由格的分配不等式知，当ab时， a(bc) (ab) (ac)=b(ac) 故 a(bc) b(ac) (19.11) 最后由 (a(bc)c=(b(a c)c (19.7) (a(bc)c = (b(ac)c (19.10) a(bc) b(ac) (19.11) 三式及定理中的条件， 得 a(bc) = b(ac) 故 L, 是模格。,2019/7/14,离散数学,50,关于分配格的一个结论,定理19.3.3 设L, , 是分配格,于是,对任意a,b,cL，若ac=bc, ac=b c，则有 a=b。 证明：由假设有 a=a(ac)= a(bc)=(ab)(ac) = (ab)(bc)=b(ac)= b(bc)=b 即a=b,2019/7/14,离散数学,51,有余分配格的元素的余元素唯一。,推论19.3.1 设L, , 是有余分配格，则对任意aL，a的余元素a是唯一的。 证明：设a和a都是a的余元素。于是 a a =0， a a=1； a a=0， a a=1 从而a a= a a， a a= a a，由定理19.3.3知，a=a，故a的余元素是唯一的。,2019/7/14,离散数学,52,19.4 布尔代数,2019/7/14,离散数学,53,布尔代数的定义,定义19.4.1 有余分配格称为布尔代数。 由布尔代数及上一节所得的一些结论，可以将一个布尔代数记为B, , + , ,0,1，其中“”称为乘法运算，“+”称为加法运算，“”称为余运算，aB的余元素记为a，0，1是B的界。有时，也可将a b简记为ab。 下面根据布尔代数的定义，分类给出布尔代数的一些重要性质。,2019/7/14,离散数学,54,布尔代数的性质,设B, , + , ,0,1是一个布尔代数，于是，对任意a,b,cB，有： 因为B, , + , ,0,1是一个代数格，所以有 a a=a， a+a=a (等幂律) a b=b a， a+b=b+a (交换律) (a b) c=a (bc)， (a+b)+c=a+(b+c) (结合律) a (a+b)=a， a+ (a b) =a (吸收律) 因为B, , + , ,0,1是分配格，所以有 a (b+c) =(a b)+ (a c) ， a+(b c) =(a+b) (a+c) (分配律) (a+b) (a+c) (b+c) = (a b) + (a c) + (b c) 若a b=a c， a+b=a+c，则b=c,2019/7/14,离散数学,55,布尔代数的性质,因为B, , + , ,0,1是有界格，所以有 0a 1 a 0=0， a+1=1 a 1=1， a+0=a 因为B, , + , ,0,1是有余分配格，所以有 a a=0， a+a=1 0=1， 1=0 a b= a+b， a+b = a b,2019/7/14,离散数学,56,布尔代数的性质,因为B, 是偏序格，所以有 a b=infa, b，a+b=supa, b a b当且仅当a+b=b当且仅当a b=a a b当且仅当a b=0当且仅当b a当且仅当a+b=1 易证，一个具有上述性质的代数系统必是布尔代数。但上述性质不是独立的，即有些性质可以由其他性质推导出来，下面用相互独立的公理来重新定义布尔代数。,2019/7/14,离散数学,57,Huntington 公理,定理19.4.1 设集合B至少含两个元素，“”和“+”是定义在B上的两个代数运算。如果对任意a,b,cB，满足下面的公理： H1：a b=b a，a+b=b+a H2：a (b+c)=(a b)+(a c)；a+(b c)= (a+b) (b+c) H3：B中有元素0和1，使得对任意aB，有 a 1=a，a+0=a H4：对任意aB，有 aB，使得 a a=0, a+a=1 则B, , + , , 0, 1是一个布尔代数。,2019/7/14,离散数学,58,定理19.4.1的证明,证明：由布尔代数的定义，我们只需证明B, , + 是格，且0，1分别是B的最小元和最大元。由H4知，B是有余格，又由H2知，B是分配格，从而B是有余分配格，即布尔代数。 首先给出几个有用的公式。(证明略) 对任意aB，a+1=1，a 0=0 (19.12) 若 a+b= a+c，a+b= a+c，则b=c (19.13) 若 a b= a c， a b= a c，则b=c (19.14) 下证B, , + 是格。,2019/7/14,离散数学,59,定理19.4.1的证明,由H1知， B, , + 满足交换律。 因为 a+(a b) = (a 1)+ (a b) (由H3) =a (1+b) (由H2) =a (b+1) (由H1) =a 1 (由19.12) =a (由H3) a (a+b) = (a+0) (a+b) (由H3) = a+(0 b) (由H2) = a+(b 0) (由H1) = a+ 0 (由19.12) = a (由H3) 所以， B, , + 满足吸收律。,2019/7/14,离散数学,60,定理19.4.1的证明,令R=a (b c)，L= (a b) c，于是 a+R= a+(a (b c)=a (由吸收律) a+L=a+(a b) c)=(a+(a b) (a+c) (由H2) = a (a+c)=a (由吸收律) 因此， a+R= a+L。又因为 a+R=a+(a (b c)=( a+a) ( a+ (b c) (由H2) =1 (a+ (b c) = a+ (b c) (由H1 ,H4及H3) a+L= a+(a b) c)=( a+(a b) ( a+c) (由H2) =( a+a) ( a+b) ( a+c) (由H2) =(1 ( a+b) ( a+c) (由H1及H4) =( a+b) ( a+c) = a+(b c) (由H1 ,H3及H2) 所以a+R= a+L，故由(19.13)知，R=L。,2019/7/14,离散数学,61,定理19.4.1的证明,再令H=a+(b+c)，K= (a+b)+c，于是 a H=a (a+(b+c)= a (由吸收律) a K= a (a+b)+c)=(a (a+b)+ (a c) (由H2) =a + (a c) =a (由吸收律) 因此， a H= a K。又因为 a H=a (a+(b+c)= a a+ a (b+c) (由H2) =0+ a (b+c) = a (b+c) (由H4, H1,H2) a K= a (a+b)+c)= a (a+b)+ (a c) (由H2) = ( a a)+( a b)+ ( a c) (由H2) =(0+ ( a b) + ( a c) (由H4) = ( a b) + ( a c) =a (b+c) (由H1, H3,H2) 所以， a H= a K，由(19.14)知，H=K,2019/7/14,离散数学,62,定理19.4.1的证明,总之， B, , + 满足结合律。 综上所述， B, , + 满足交换律、吸收律和结合律，所以是格。 现定义B上的偏序关系“”如下： a b 当且仅当 a b=a 于是，由定理19.1.1知， B, 是一个格，并且， a b 当且仅当 a +b=b 最后，由H3知，对任意aB，有 a 1=a，a+0=a 故0 a 1，即0和1分别是B的最小元素和最大元素。因此， B, , + , , 0 ,1是布尔代数。,2019/7/14,离散数学,63,布尔代数的例,例1 设B=0,1，B上的运算“”、 “+”和“”定义如下： 0 1 + 0 1 x x 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 易证， B, ,+,0,1是布尔代数。这是最简单的一个布尔代数，常称为电路代数。 例2 设S是一个非空集合，则(S), ,S是一个布尔代数，对任意A(S), A=SA。称此代数为集合代数。,2019/7/14,离散数学,64,布尔代数的例,例3 设P是命题公式的集合，不难证明， P, ,F,T是一个布尔代数,称为命题代数。 例4 令Bn=|xi0,1,i=1,n，对任意a,bBn ,令a=,b=，定义Bn上的运算如下： a b= a +b= a= 其中，0=1，1=0。不难证明，Bn, ,+,0,1是一个布尔代数，其中， 0n=Bn ， 1n=Bn 。此代数称为开关代数。,2019/7/14,离散数学,65,子布尔代数,定义19.4.2 设B, ,+,0,1是一个布尔代数，SB，如果S包含元素0和1，并且对运算 ,+,是封闭的，则S, ,+,0,1称为 B, ,+,0,1的子布尔代数。 定理19.4.2 设B, ,+,0,1是布尔代数，S是B的非空子集，如果S对运算 , 或+,是封闭的，则S是B的子布尔代数。 证明：设S对运算 , 封闭，由S知，存在aS，于是aS。从而a a=0S，且0=1S。由任取a,bS，因为a+b=( a b)，所以a+bS，即S对 + 是封闭的，且包含0和1，故由定义知，S是B的子布尔代数。 同理可证，若S对+,封闭，则S是B的子布尔代数。,2019/7/14,离散数学,66,子布尔代数,由子布尔代数的定义知，子布尔代数本身构成一个布尔代数。 要注意的是，布尔代数B的子集S可以是布尔代数，但它可能不是B的子布尔代数，因为它对B中的运算可能不是封闭的。 例5 考虑如图所示的格 不难验证它是一个格。令S1=a,a,0,1，S2=a,b,0,1，S3=a,b,0,1。则S1是子布尔代数，因为它对 ，封闭； S2不是子布尔代数，因为它运算“”对不封闭；是S3布尔代数，但不是所给代数的子布尔代数，因为它对运算“”不封闭。,2019/7/14,离散数学,67,一个格的图示,图19.6,a+b,a,0,b,1,b,a,ab,2019/7/14,离散数学,68,布尔代数的同态,定义19.4.3 设B, ,+,0,1和S, ,是两个布尔代数，f是B到S的映射。如果对任意a,bB有 f(a b) = f(a)f(b) f(a +b) = f(a)f(b) f( a ) = f(a) f(0) = f(1) = 则称 f为B到S的一个布尔同态。称f(B)是布尔代数B的同态象。如果 f是双射，则称 f是布尔同构，也称B与S同构。 显然， f(B)是S的子布尔代数。,2019/7/14,离散数学,69,布尔代数的同态,定理19.4.3 设f是布尔代数B, ,+,0,1到布尔代数S, ,的一个映射，如果对任意a,bB，都有 f(a b) = f(a)f(b) f( a ) = f(a) 则 f是B到S的布尔同态。 证明：对任意a,bB，由假设有 f(a +b)=f(a +b)=f(a +b)=f( a b) = (f( a )f( b )= ( f(a) f(b)= f(a)f(b) f(0) =f(a a ) = f(a)f( a )= f(a)f(a)= f(1) = f(a +a )=f(a)f( a )=f(a)f(a)= 故有定义知， f是B到S的布尔同态。,2019/7/14,离散数学,70,布尔代数的同态,定理19.4.4 设f是布尔代数B, ,+,0,1到布尔代数S, ,的一个映射，如果对任意a,bB，都有 f(a b) = f(a)f(b) f(a +b) = f(a)f(b) 则f(B), ,f(0),f(1)是一个布尔代数，且f是B到f(B)的布尔同态，其中是关于f(0)和f(1)的余运算。,2019/7/14,离散数学,71,定理19.4.4的证明,证明：显然， f(B)S。对任意af(B)，必有aB，使得f(a)= a。因为， af(0)=f(a)f(0)=f(a0)=f(0)。所以f(0) a。又因为，af(1)=f(a)f(1)= f(a+1) =f(1) 所以af(1)。于是， f(0)af(1)。故f(0)和f(1)分别是f(B)中的最小元素和最大元素。 又任取aB，有 f(a)f(a )= f(a a )= f(0) f(a)f(a )= f(a+a ) =f(1) 于是，f( a )是f(a)的余元素，故 f(a)= f( a) 以上说明，f(B)对运算,是封闭的，故f(B)是S的子布尔代数。由又定理19.4.3知，f是B到f(B)的布尔同态。,2019/7/14,离散数学,72,19.5 有限布尔代数 的结构,2019/7/14,离散数学,73,本节提到的布尔代数，如不特别指出，都是指有限布尔代数。 前一节中，我们构造了一些布尔代数。人们可能想象有很大的自由来构造一些不同的布尔代数，实际上并非如此。本节将证明，每个有限布尔代数的阶必为2的正整数次幂，并且维数相同的有限布尔代数必同构。,2019/7/14,离散数学,74,n维布尔代数,定义19.5.1 设B, ,+,0,1是布尔代数，若存在e1,en，使得对任意aB，都可唯一地表示为 a=a1e1+,+anen 其中ai0,1，i=1,n。则称 e1,en为布尔代数B的一组基底，并称此布尔代数为n维的。 易知，ei0，i=1,n,2019/7/14,离散数学,75,极小元素,定义19.5.2 设B, ,+,0,1是布尔代数，aB，且a0。若对任意 xB，a x= 0或者a x= a，则称 a为布尔代数 B的极小元素(或原子)。 由定义知，有限布尔代数的极小元素就是其Hasse图中与最小元素0连结的那些元素，并且，若a和b是两个不同的极小元素，则必有a b=0,2019/7/14,离散数学,76,布尔代数有极小元,命题19.5.1 设B是布尔代数，aB，a0。若a不是极小元素，则必存在元素ba。 证明：因为a不是极小元素，所以存在非零元素x0B，使得a x00且a x0a。 令a x0=a1，则显然a1a(即a1a且a1 a) 若a1是极小元素，则命题得证，否则，有非零元素x1B，使得a1 x10且a1 x1a1。 令a1 x1=a2，则有a2a1a。 重复上述过程，由于B有限，故最后总可找到极小元素an，使得 anan-1 a2a1a,2019/7/14,离散数学,77,布尔代数的基底由极小元做成,定理19.5.1 有限布尔代数的基底必是此代数的所有极小元素；反之，有限布尔代数的所有极小元素必能做成此代数的基底。 证明：设e1,en是有限布尔代数B, ,+,0,1的基底，先证ei是极小元素，i=1,n。 若ei不是极小元素，则存在aB