离散数学课件(第6章)

《离散数学》教案计算机科学与技术学院课程学时：64主讲：宋成河南理工大学电子教案第六章：格和布尔代数§6.1格的概念§6.2分配格§6.3

有补格§6.4*

布尔代数第六章：格和布尔代数教学目的及要求：深刻理解和掌握格与布尔代数的基本概念和基本运算教学类容：格的概念、有补格，分配格、布尔代数和布尔表达式。教学重点：格、布尔代数和布尔表达式。教学难点：布尔代数和布尔表达式。§6.1格的概念【定义6.1.1】设X,≼是偏序集，如果x,yX，集合x,y都有最小上界和最大下界，则称X,≼是格。【例6.1】设S12＝1,2,3,4,6,12是12的因子构成的集合。其上的整除关系R=x,y|xS12∧yS12∧x整除y，R是S12上的偏序关系，S12,R是偏序集。写出S12上的盖住关系COVS12，画出哈斯图，验证偏序集S12,R是格。

解：S12上的盖住关系COVS12＝1,2,1,3,2,4,2,6,3,6,4,12,6,12，哈斯图如图6.1所示。从哈斯图中可看出，集合S12的任意两个元素都有最小上界和最大下界，故偏序集S12,R是格。

第六章：格和布尔代数第六章：格和布尔代数【例6.2】图8.2中给出了一些偏序集的哈斯图，判断它们是否构成格。

解：它们都不是格。在(a)中，1,2没有下界，因而没有最大下界。在(b)中，2,4虽有两个上界，但没有最小上界。在(c)中，1,3没有下界，因而没有最大下界。在(d)中，2,3虽有三个上界，但没有最小上界。第六章：格和布尔代数设X,≼是格，x,yX，今后用x∨y表示集合x,y的最小上界，二元运算∨称为并运算；用x∧y表示集合x,y的最大下界，二元运算∧称为交运算。

【定义6.1.2】设X,≼是格，∨是X上的并运算，∧是X上的交运算。则称X,∨,∧是格X,≼导出的代数系统。

x,yP

(A)，x∨y=x∪y，x∧y=x∩y。这样，格P(A),R导出的代数系统P(A),∨,∧实际就是代数系统P(A),∪,∩，所以，二元运算∨和∧的运算表如表6.1和表6.2所示。在例6.1中，根据图6.1，集合4,6的最小上界为12，即4∨6=12=4和6的最小公倍数；它的最大下界为2，即4∧6=2=4和6的最大公约数。同样，这个结果也可以推广到一般情况。即在格S12,R导出的代数系统S12,∨,∧中，二元运算∨是求最小公倍数；二元运算∧是求最大公约数。

第六章：格和布尔代数表6.1

表6.2∨ÆaÆÆabba,baaaa,ba,ba,bbba,ba,ba,ba,ba,bba,ba,b∧Æaba,bÆÆÆÆÆaÆaÆabÆÆbba,bÆaba,b第六章：格和布尔代数定义6.1.3

设f是含有格中元素以及符号=,≼,≽,∨和∧的命题。将f中的≼替换成≽，≽替换成≼，∨替换成∧，∧替换成∨，得到一个新命题，所得的命题叫做f的对偶命题，记为f*。例如，在格中，f为a∧(b∨c)≼a，则f的对偶命题f*为a∨(b∧c)≽a命题f和它的对偶命题f*遵循下列的规则，这规则叫做格的对偶原理。设f是含有格中元素以及符号=,≼,≽,∨和∧的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真。格的许多性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只需证明其中的一个就可以了。

第六章：格和布尔代数【定理6.1.1】设X,≼是格，X,∨,∧是格X,≼导出的代数系统。则a,b,cX有⑴a∨b=b∨a，a∧b=b∧a(交换律)⑵(a∨b)∨c=a∨(b∨c) (a∧b)∧c=a∧(b∧c)(结合律)⑶a∨a=a，a∧a=a(幂等律)⑷a∨(a∧b)=a

a∧(a∨b)=a(吸收律)

证明：⑴a,bX，a,b=b,a，所以它们的最小上界相等。即a∨b=b∨a，同理可证a∧b=b∧a⑵a和b的最大下界一定是a、b的下界，即a∧b≼a，同理，(a∧b)∧c≼a∧b，所以，(a∧b)∧c≼a∧b≼a同理有(a∧b)∧c≼a∧b≼b

和(a∧b)∧c≼c第六章：格和布尔代数由以上3式得(a∧b)∧c≼b∧c和(a∧b)∧c≼a∧(b∧c)类似地可证a∧(b∧c)≼(a∧b)∧c根据偏序关系的反对称性有(a∧b)∧c=a∧(b∧c)由对偶原理得(a∨b)∨c=a∨(b∨c)⑶显然a≼a∨a，又由≼的自反性得a≼a，从而推出a∨a≼a，根据偏序关系的反对称性有a∨a=a由对偶原理得a∧a=a⑷显然a≼a∨(a∧b)，又由a≼a，a∧b≼a得a∨(a∧b)≼a，从而得a∨(a∧b)=a。由对偶原理得a∧(a∨b)=a第六章：格和布尔代数【定理6.1.2】

设X,∨,∧是代数系统，其中∨,∧都是二元运算。如果∨和∧满足吸收律，则∨和∧满足幂等律。

证明：a∨a=a∨(a∧(a∨b))=a，同理可证a∧a=a【定理6.1.3】设X,∨,∧是代数系统，其中∨,∧都是二元运算，满足交换律、结合律和吸收律，则可适当定义X的偏序关系≼，使X,≼构成一个格。

证明：定义X上的一个二元关系

≼=a,b|a,bX且a∧b=a⑴证明≼是X上的偏序关系。由定理6.1.2知∧满足幂等律，即a∧a=a，所以a≼a。故≼是自反的。设a≼b且b≼a，则a∧b=a且b∧a=b，于是a=a∧b=b∧a=b。所以≼是反对称的。设a≼b且b≼c，则a∧b=a且b∧c=b，于是a∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a，即a≼c，故≼是传递的。这就证明了≼是X上的偏序关系。

第六章：格和布尔代数⑵证明a,bX，a∧b是集合a,b的最大下界。因为(a∧b)∧a=a∧b和(a∧b)∧b=a∧b所以a∧b≼a且a∧b≼b，即a∧b是a,b的下界。下证a∧b是a,b的最大下界。设c是a,b的任一下界，即c≼a，c≼b，那么有c∧a=c，c∧b=c而

c∧(a∧b)=(c∧a)∧b=c∧b=c所以

c≼a∧b，即a∧b是a,b的最大下界。⑶

证明a∧b=a的充分必要条件是a∨b=b设a∧b=a，由吸收率可得

a∨b=(a∧b)∨b=b∨(b∧a)=b，即a∨b=b设a∨b=b，由吸收率可得

a∧b=a∧(a∨b)=a，即a∧b=a第六章：格和布尔代数⑷

证明a,bX，a∨b是集合a,b的最小上界。根据⑶，偏序关系≼可以等价的定义为：

≼=a,b|a,bX且a∨b=b，用这个定义和类似于⑵的方法可以证明a∨b是集合a,b的最小上界。因此，X,≼构成一个格。根据定理6.1.3，可以给出格的另一个等价定义。【定义6.1.4】

设X,*,∘是代数系统，其中*和∘都是二元运算，如果*和∘在X上封闭且满足交换律、结合律和吸收律，则称X,*,∘为格。根据定义6.1.4和定理6.1.1，格X,≼导出的代数系统X,∨,∧是格，以后不再区分偏序集定义的格和代数系统定义的格，统称为格。第六章：格和布尔代数【定理6.1.4】

设X,≼是格，∨是X上的并运算，∧是X上的交运算。则a,bX有⑴a≼b当且仅当a∧b=a⑵a≼b当且仅当a∨b=b证明：⑴设a≼b，下证a∧b=a由a≼a且a≼b知a是集合a,b的下界，故有a≼a∧b；另一方面，由于a∧b是a,b的最大下界，所以是a,b的下界，即a∧b≼a。根据偏序关系的反对称性得a∧b=a设a∧b=a，下证a≼ba=a∧b≼b，即a≼b⑵可类似⑴进行证明。第六章：格和布尔代数【定理6.1.5】设X,≼是格，∨是X上的并运算，∧是X上的交运算。a,b,c,dX，若a≼b且c≼d，则a∨c≼b∨d，a∧c≼b∧d

证明：

a≼b≼b∨d，c≼d≼b∨d，因此a∨c≼b∨d类似的可以证明a∧c≼b∧d【定理6.1.6】设X,≼是格，∨是X上的并运算，∧是X上的交运算。则a,b,cX有⑴a∨(b∧c)≼(a∨b)∧(a∨c)⑵(a∧b)∨(a∧c)≼

a∧(b∨c)

证明：⑴根据定理8.1.5，由a≼a和b∧c≼b得a∨(b∧c)≼a∨b又由a≼a且b∧c≼c得a∨(b∧c)≼a∨c

从而得到a∨(b∧c)≼(a∨b)∧(a∨c)利用对偶原理，即得⑵。一般地说，格中的∨和∧并不满足分配律。

第六章：格和布尔代数【定义6.1.5】

设X,∨,∧是格，B是X的非空子集，如果B关于运算∨和∧也构成格，则称B,∨,∧是X,∨,∧的子格。在例6.1中，令B1＝1,2,3,6，B2＝2,4,6,12，则B1,∨,∧和B2,∨,∧是格S12,∨,∧的子格。令B3＝1,2,3,12，由于2∨3=6，而6B3，所以B3,∨,∧不是格S12,∨,∧的子格。以下定义格的同态。【定义6.1.6】设X1,∨1,∧1和X2,∨2,∧2是格，其中∨1,∧1,∨2和∧2都是二元运算。f是从X1到X2的一个映射，对任意的a,bX1有f(a∨1b)=f(a)∨2f(b)，f(a∧1b)=f(a)∧2f(b)则称f是格X1,∨1,∧1到格X2,∨2,∧2的格同态。如果f是单射、满射和双射，分别称f是格单同态、格满同态和格同构。称f(X1),∨2,∧2是X1,∨1,∧1的格同态像。第六章：格和布尔代数【定理6.1.7】设X1,≼1和X2,≼2是格，X1,∨1,∧1和X2,∨2,∧2是它们导出的代数系统。f是格X1,∨1,∧1到格X2,∨2,∧2的格同态，则a,bX1，如果a≼1b，必有f(a)≼2f(b)证明：设a≼1b，根据定理6.1.4，a∧1b=a，由于f是格X1,∨1,∧1到格X2,∨2,∧2的格同态，所以f(a)=f(a∧1b)=f(a)∧2f(b)，再由定理6.1.4，f(a)≼2f(b)。定理6.1.7说明格同态是保序的。一般地说，定理6.1.7的逆并不成立。【例6.3】设A=a,b,c,d,e，A,≼是格，其哈斯图如图8.3所示，P(A)是A的幂集合，R=x,y|xP(A)∧yP

(A)∧xy是P(A)上的偏序关系。P(A),R也是格。作映射f：A→P(A)，定义为：xA，f(x)=y|yA且y≼x，即：f(a)=a,b,c,d,e=A，f(b)=b,e，f(c)=c,e，f(d)=d,e，f(e)=e。证明f是保序的，但不是格同态。第六章：格和布尔代数证明：a,bA，设a≼b，cf(a)，c≼a，由偏序关系的传递性得c≼b，所以cf(b)，即f(a)f(b)，于是f(a)Rf(b)。故f是保序的。对于b,dA，b∨d=af(b∨d)=f(a)=Af(b)∪f(d)=b,e∪d,e=b,d,e

f(b∨d)≠f(b)∪f(d)f不是格同态。但是，当f是格同构时，定理6.1.7的逆成立。

第六章：格和布尔代数【定理6.1.8】设X1,≼1和X2,≼2是格，X1,∨1,∧1和X2,∨2,∧2是它们导出的代数系统。f是X1到X2的双射，则f是X1,∨1,∧1到X2,∨2,∧2的格同构的充分必要条件是a,bX1，a≼1bf(a)≼2f(b)

证明：设f是X1,∨1,∧1到X2,∨2,∧2的格同构，下证a,bX1，a≼1bf(a)≼2f(b)由定理6.1.7可知，a,bX1，如果a≼1b，必有f(a)≼2f(b)设f(a)≼2f(b)，由定理6.1.4有f(a)=f(a)∧2f(b)=f(a∧1b)，由于f是双射，故a∧1b=a，所以a≼1b这就证明a≼1bf(a)≼2f(b)设a,bX1，a≼1bf(a)≼2f(b)，下证f是X1,∨1,∧1到X2,∨2,∧2的格同构。设a∧1b=c，则c≼1a，c≼1b，f(c)=f(a∧1b)，f(c)≼2f(a)，f(c)≼2f(b)，故f(c)≼2f(a)∧2f(b)。设f(a)∧2f(b)=f(d)，则有f(c)≼2f(a)∧2f(b)=f(d)，即f(c)≼2f(d)；还有f(d)≼2f(a)和f(d)≼2f(b)。所以有d≼1a和d≼1b，

第六章：格和布尔代数于是d≼1a∧1b，即d≼1c，故f(d)≼2f(c)，再由偏序关系的反对称性有f(c)=f(d)。即f(a∧1b)=f(c)=f(d)=f(a)∧2f(b)类似地可以证明f(a∨1b)=f(a)∨2f(b)这就证明了f是X1,∨1,∧1到X2,∨2,∧2的格同构。【定义6.1.7】

设X1,≼1和X2,≼2是格，X1,∨1,∧1和X2,∨2,∧2是它们导出的代数系统。其中∨1,∧1,∨2和∧2都是二元运算。a1,b1X1×X2和a2,b2X1×X2，定义X1×X2上的二元运算∨3和∧3为：a1,b1∨3a2,b2=a1∨1a2,b1∨2b2a1,b1∧3a2,b2=a1∧1a2,b1∧2b2代数系统

X1×X2,∨3,∧3称为格X1,∨1,∧1到格X2,∨2,∧2的直积。如果X1,∨1,∧1和X2,∨2,∧2是格，可以证明代数系统X1×X2,∨3,∧3也是格第六章：格和布尔代数

§6.2分配格【定义6.2.1】

设X,≼是格，X,∨,∧是X,≼导出的代数系统，如果a,b,cX有a∨(b∧c)=(a∨b)∧(a∨c)(并运算对交运算可分配)a∧(b∨c)=(a∧b)∨(a∧c)(交运算对并运算可分配)则称X,∨,∧为分配格。因为a∨(b∧c)=(a∨b)∧(a∨c)和a∧(b∨c)=(a∧b)∨(a∧c)互为对偶命题，根据对偶原理，定义6.2.1还可以改写为：一个格如果交运算对并运算可分配或并运算对交运算可分配，则称该格为分配格。第六章：格和布尔代数【例6.4】设A=a,b,c，P(A)=Æ,a,b,c,a,b,a,c,b,c,a,b,c是A的幂集合，P(A)上的包含关系R=x,y|xP

(A)∧yP

(A)∧xy是P

(A)上的偏序关系。P

(A),R是偏序集，P(A)上的盖住关系COVP(A)=Æ,a,Æ,b,Æ,c,a,a,b,b,a,b,a,a,c,c,a,c,b,b,c,c,b,c,a,b,a,b,c,a,c,a,b,c,b,c,a,b,c其哈斯图如图8.4所示。P

(A),∨,∧是P(A),R导出的代数系统，证明P(A),∨,∧是分配格。

证明：前面已经证明了格P(A),R导出的代数系统P

(A),∨,∧实际就是代数系统P(A),∪,∩，其中∪是集合的并运算，∩是集合的交运算。而集合的并、交运算满足分配律：第六章：格和布尔代数P,Q,RP

(A)

P∪(Q∩R)=(P∪Q)∩(P∪R)P∩(Q∪R)=(P∩Q)∪(P∩R)所以，P

(A),∨,∧分配格。第六章：格和布尔代数

【例6.5】

A=a,b,c,d,e，A,≼是格，其哈斯图如图8.3所示，证明A,≼不是分配格。

证明：

b∨(c∧d)=b∨e=b

(b∨c)∧(b∨d)=a∧a=a b∨(c∧d)≠(b∨c)∧(b∨d)

所以，A,≼不是分配格。

本例中的格叫做钻石格，钻石格不是分配格。

第六章：格和布尔代数【例6.6】设A=a,b,c,d,e，A,≼是格，其哈斯图如图8.5所示，证明A,≼不是分配格。证明：

d∨(b∧c)=d∨e=d(d∨b)∧(d∨c)=a∧c=cd∨(b∧c)≠(d∨b)∧(d∨c)所以，A,≼不是分配格。本例中的格叫做五角格，五角格也不是分配格。钻石格和五角格是两个很重要的格。第六章：格和布尔代数【定理6.2.1】一个格是分配格的充分必要条件是该格中不含有与钻石格或五角格同构的子格。这个定理的证明已经超过了本书的范围，故略去。【推论1】设A,≼是格，如果|A|＜5，则A,≼一定是分配格。【推论2】设A,≼是格，如果A,≼是全序集，则A,≼一定是分配格。【例6.7】图8.6给出了两个格的哈斯图。试证明它们都不是分配格。证明：在图8.6

(a)中含有与五角格同构的子格，所以不是分配格；在图8.6

(b)中含有与钻石格同构的子格，所以不是分配格。

第六章：格和布尔代数第六章：格和布尔代数【定理6.2.2】

设X,≼是格，X,∨,∧是格X,≼导出的代数系统。X,≼是分配格的充分必要条件是a,b,cX，当a∧b=a∧c且a∨b=a∨c时，必有b=c证明：设X,≼是分配格，a,b,cX，a∧b=a∧c且a∨b=a∨cb=b∨(b∧a)=b∨(a∧b)

(吸收律和交换律)=b∨(a∧c)=(b∨a)∧(b∨c)(已知代入和分配律)=(a∨c)∧(b∨c)(交换律和已知代入)=(a∧b)∨c(分配律)=(a∧c)∨c(已知条件代入)=c(交换律和吸收律) 设a,b,cX，当a∧b=a∧c且a∨b=a∨c时，有b=c，但X,∨,∧不是分配格。由定理6.2.1知X,∨,∧中必含有与钻石格或五角格同构的子格。假设X,∨,∧含有与钻石格同构的子格，且此子格为S,∨,∧，其中S=u,v,x,y,z，u为它的最大元，v为它的最小元。从而x∨y=u=x∨z，x∧y=v=x∧z，但y≠z，与已知矛盾。第六章：格和布尔代数对五角格的情况，可类似证明。例如，在图8.6(a)中，b∧c=g=b∧f且b∨c=a=b∨f，但c≠f；在图8.6(b)中，b∧c=f=b∧e且b∨c=a=b∨e，但c≠e。根据定理6.2.2它们不是分配格。

§6.3有补格

【定义6.3.1】

设X,≼是格，如果aX，xX都有a≼x(x≼a)则称a为格X,≼的全下(上)界，记为0(1)。【定理6.3.1】设X,≼是格，若格X,≼有全下界或全上界，则它们一定是惟一的。

证明：用反证法。如果有两个全下界a和b，a,bX。因为a是全下界，所以a≼b；又因为b是全下界，所以b≼a。再由≼的反对称性有a=b类似地可证明全上界的惟一性。第六章：格和布尔代数【定义6.3.2】设X,≼是格，X,∨,∧是格X,≼导出的代数系统。若格X,∨,∧存在全下界0和全上界1，则称X,∨,∧为有界格，记为X,∨,∧,0,1。在例8.4中，P(A),R是格。P

(A),∨,∧是P(A),R导出的代数系统。空集Æ是格的全下界，而集合A是格的全上界。因而P

(A),∨,∧是有界格，可记为P(A)∨,∧,Æ,A。在例6.6中，从哈斯图(图8.5)中可以看出，a是全上界，而e是全下界，所以A,≼是有界格。【定理6.3.2】设X,∨,∧,0,1为有界格，则aX有

a∧0=0，a∨0=a；a∧1=a，a∨1=1

证明：因为0是全下界且a∧0X，所以0≼a∧0，又因为a∧0≼0，由≼的反对称性有a∧0=0显然a≼a，由于1是全上界，所以有a≼1，从而推出a≼a∧1，又因为a∧1≼a，再由≼的反对称性有a∧1=aa∨0=a和a∨1=1可以类似地证明。第六章：格和布尔代数设X,∨,∧,0,1为有界格，aX有a∧0=0，因为格满足交换律，所以0∧a=0，这说明0是交运算的零元；同样的道理，0是并运算的幺元，而1是交运算的幺元和并运算的零元。

【定义6.3.3】设X,∨,∧,0,1为有界格，如果对于aX，bX，使得a∨b=1且a∧b=0，则称b是a的补元。如果b是a的补元，从定义6.3.3可以看出，a也是b的补元。因此，可以说a和b是互补的，或者说a和b互为补元。例如，在例6.6中，从哈斯图(图8.5)中可以看出，b和c互为补元，b和d也互为补元，b有两个补元c和d。所以格中元素的补元并不惟一。第六章：格和布尔代数【例6.8】图8.7是一个有界格的哈斯图。找出a,b,c,d,e的补元。

解：从图8.7中可以看出，a的补元是e；b没有补元；c的补元是d；d的补元是c和e，e的补元是a和d，0和1互为补元。显然，在有界格中，全上界1的惟一补元是全下界0，而全下界0的惟一补元是全上界1。除了1和0，其它元素有的有补元，有的没有补元。如果某个元素的补元存在，补元可能有一个，也可能有多个。但在有界分配格中，如果元素的补元存在，则一定惟一。

第六章：格和布尔代数【定理6.3.3】设X,∨,∧,0,1为有界分配格，如果对于aX，a存在补元b，则b是a的惟一补元。

证明：因为b是a的补元，所以有a∨b=1，a∧b=0设cX，c是a的另一个补元，同样也有a∨c=1，a∧c=0从而有a∨b=a∨c，a∧b=a∧c由于X,∨,∧,0,1为分配格，根据定理6.6.6必有b=c，即a的补元惟一。【定义6.3.4】设X,∨,∧,0,1为有界格，如果aX，在X中都有a的补元存在，则称X,∨,∧,0,1为有补格例如，图8.8是三个有界格的哈斯图，由于每一个元素至少有一个补元，所以它们都是有补格。

第六章：格和布尔代数第六章：格和布尔代数§6.4布尔代数【定义6.4.1】

有补分配格称为布尔格。在布尔格中每一个元素都有补元。因为有补格一定是有界格，所以布尔格一定是有界分配格，根据定理6.3.3，布尔格中的每一个元素的补元存在且惟一。于是可以将求补元的运算看作一元运算且把a的补元记为a′。【定义6.4.2】设X,≼是布尔格，X,∨,∧,′是格X,≼导出的代数系统。称代数系统X,∨,∧,′为布尔代数。在6.1节中证明了P

(A),R是格，其中A=a,b。P

(A),∪,∩是P

(A),R导出的代数系统，其中∪和∩是集合并运算和交运算。以后又进一步说明了P

(A),∪,∩是分配格和有界格，Æ是全下界、A是全上界。从而P(A),∪,∩是有界分配格。令A为全集，TP

(A)，T的补集~T=A–TP

(A)，满足T∪~T=A和T∩~T=Æ，所以T的补元T′=~T。根据定义6.4.2，P(A),∪,∩,~是布尔代数。

第六章：格和布尔代数

可以证明，当A为任意集合时，P(A),∪,∩,~也是布尔代数。称为集合代数。集合代数是布尔代数的一个具体模型。布尔代数一定是格。根据定理8.1.1，布尔代数中的两个二元运算满足交换律、结合律、幂等律和吸收律。此外，布尔代数还有下面的性质：【定理6.4.1】

设X,∨,∧,′为布尔代数，a,bX，必有⑴(a′)′=a⑵(a∨b)′=a′∧b′⑶(a∧b)′=a′∨b′证明：⑴a′是a的补元，a也是a′的补元，由布尔代数中补元的惟一性有(a′)′=a第六章：格和布尔代数⑵(a∨b)∨(a′∧b′)=((a∨b)∨a′)∧((a∨b)∨b′)=(b∨(a∨a′))∧(a∨(b∨b′))=(b∨1)∧(a∨1)=1∧1=1(a∨b)∧(a′∧b′)=(a∧(a′∧b′))∨(b∧(a′∧b′))=((a∧a′)∧b′)∨((b∧b′)∧a′)=(0∧b′)∨(0∧a′)=0∨0=0所以(a∨b)′=a′∧b′⑶同理可证(a∧b)′=a′∨b′定理6.4.1中的⑴称为双重否定律，⑵和⑶称为德摩根律。布尔代数满足双重否定律和德摩根律。第六章：格和布尔代数【定理6.4.2】

设X,*,∘,′是代数系统，其中*和∘都是二元运算，′是一元运算。X,*,∘,′是布尔代数的充分必要条件是：⑴*和∘在X上封闭且满足交换律。⑵*和∘满足分配律(满足*对∘的分配律和∘对*的分配律)。⑶X中存在运算*的幺元和运算∘的幺元。设运算*的幺元为0，运算∘的幺元为1。即aX，有a*0=a，a∘1=a⑷

aX，a′X，使得a*a′=1，a∘a′=0由于篇幅的限制，证明从略。定理6.4.2给出的四个条件可以作为布尔代数的等价定义。布尔代数X,*,∘,′也可以表示成为X,*,∘,′,0,1，其中0是运算*的幺元，1是运算∘的幺元。第六章：格和布尔代数【例6.9】设P是所有命题构成的集合，∨,∧和¬分别是命题的析取、合取和否定联结词。证明代数系统P,∨,∧,¬是布尔代数。

证明：根据第1章的内容，∨和∧在P上封闭且满足交换律、分配律。命题常元0(假)和1(真)是集合P的元素，满足qP，q∨0=q，q∧1=q。

qP，¬qP，满足q∨¬q=1，q∧¬q=0。根据定理6.4.2，P,∨,∧,¬是布尔代数。例6.9中的布尔代数P,∧,∨,¬叫做命题代数，它是布尔代数的又一个模型。【定义6.4.3】

设X,∨,∧,′,0,1是布尔代数，B是X的非空子集，若0,1B且B,∨,∧,′,0,1也是布尔代数。则称B,∨,∧,′,0,1是X,∨,∧,′,0,1子布尔代数。第六章：格和布尔代数【定理6.4.3】设X,∨,∧,′,0,1是布尔代数，B是X的非空子集，若0,1B且运算∨,∧,′在B上封闭，则B,∨,∧,′,0,1是X,∨,∧,′,0,1子布尔代数

证明：⑴a,bB，因为BX，所以a,bX。又因为X,∨,∧,′,0,1是布尔代数，故a∨b=b∨a，a∧b=b∧a⑵类似⑴可以证明*和∘满足分配律。⑶

已知0,1B，aBX，aX，有a∨0=a和a∧1=a⑷aB，由′在B上封闭知有a′B，使得a∨a′=1，a∧a′=0根据定理6.4.2，B,∨,∧,′,0,1是布尔代数，它是X,∨,∧,′,0,1的子布尔代数。为了方便，以下将x≼y且x≠y记为x≺y。

第六章：格和布尔代数【例4.10】设X,∨,∧,′,0,1是布尔代数，a,bX，a≺b，令S=x|xX，a≼x且x≼b试证明S,∨,∧,′,0,1是X,∨,∧,′,0,1的子布尔代数。

证明：由于a≼a且a≼b，所以aS，S是X的非空子集，由S的定义知a是S的全下界，b是S的全上界。x,yS，a≼x且x≼b，a≼y且y≼ba≼x∨y且x∨y≼b，a≼x∧y且x∧y≼b从而x∨yS且x∧yS，即运算∨和∧在S上封闭。xS，令y=(a∨x′)∧b由于a≼a∨x′，a≼b，故a≼(a∨x′)∧b；又由于(a∨x′)∧b≼b，所以y=(a∨x′)∧bS，又x∨y=x∨((a∨x′)∧b)=x∨((a∧b)∨(x′∧b))(分配律)=x∨(a∨(x′∧b))(a≼ba∧b=a)=(x∨a)∨(x′∧b)(结合律)第六章：格和布尔代数=x∨(x′∧b)(a≼xa∨x=x)=(x∨x′)∧(x∨b)(分配律)=1∧(x∨b)(x′是x的补元)=x∨b (1是∧的幺元)=b(x≼b

x∨b=b)x∧y=x∧((a∨x′)∧b)=(x∧b)∧(a∨x′)(交换律和结合律)=x∧(a∨x′)(由定理8.1.4，x≼bx∧b=x)=(x∧a)∨(x∧x′)(分配律)=(x∧a)∨0(x′是x的补元)=(x∧a)(0是∨的幺元)=a(由定理8.1.4，a≼xa∧x=a)所以x′=yS，一元运算′在S上封闭。

根据定理6.4.3，S,∨,∧,′,0,1是X,∨,∧,′,0,1的子布尔代数。第六章：格和布尔代数【定义6.4.4】

设X1,∨1,∧1,′,0,1和X2,∨2,∧2,",,E是两个布尔代数，其中∨1,∧1,∨2和∧2都是二元运算，′和"是一元运算，0和1是X1的全下界和全上界，,E是X2的全下界和全上界。f是从X1到X2的一个映射，对任意的a,bX1有f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2

f(b)f(a′)=(f(a))"则称f是布尔代数X1,∨1,∧1,′,0,1到X2,∨2,∧2,",,E

的同态，简称布尔代数同态。如果f是单射、满射和双射，分别称f是布尔代数单同态、布尔代数满同态和布尔代数同构。称f(X1),∨2,∧2,",,E

是X1,∨1,∧1,′,0,1的布尔代数同态像。第六章：格和布尔代数【定义8.2.5】设X,≼是格，具有全下界0，若X中的元素a盖住了0，则称元素a为原子。根据盖住的定义，a盖住了0可以描述为：0≺a且bX，如果有0≺b≼a，则a=b。图8.10是三个格的哈斯图，在(a)中，a是原子；在(b)中，a,b,c是原子；在(c)中，a,b是原子。【定理6.4.4】设X,≼是格，具有全下界0，a和b是原子，如果a≠b，则a∧b=0。

证明：设a∧b≠0，0≺a∧b≼a且0≺a∧b≼b，因为a是原子，所以a∧b=a。同样的道理a∧b=b。于是，a=a∧b=b。与假设矛盾。在图8.10的(b)中，a∧b=0，a∧c＝0，b∧c=0；在图8.10的(c)中，a∧b=0。设X,≼是格，如果集合X是有限集，则称X,≼是有限格。【定理6.4.5】

设X,≼是有限格，具有全下界0，则bX且b≠0，至少存在一个原子a，使得a≼b。

证明：如果b是一个原子，则b≼b。定理得证。如果b不是原子，必有b1使得0≺b1≺b。如果b1是一个原子，定理得证。否则，必有b2使得0≺b2≺b1≺b。……

第六章：格和布尔代数由于X,≼是有限格，通过有限步总可找到一个原子bi，使得

0≺bi≺…≺b2≺b1≺b由≼的传递性，bi≺b定理6.4.5中的原子a不一定惟一，图8.10的(c)是有限格，元素c有惟一的原子b，使得b≼c。图8.10的(b)也是有限格，元素d却有三个原子a,b,c，使得a≼d,b≼d,c≼d。

【引理6.4.1】设X,≼是布尔格，0是全下界，a,bX，则a∧b′=0当且仅当a≼b。

证明：设a∧b′=0，由0∨b=b，有b=0∨b=(a∧b′)∨b=(a∨b)∧(b′∨b)=(a∨b)∧1=a∨b由前面的定理知，a≼b。设a≼b，由于b′≼b′，因有a∧b′≼b∧b′，而b∧b′=0，所以a∧b′≼0。又因为0≼a且0≼b′，故有0≼a∧b′。由≼的反对称性知a∧b′=0。

第六章：格和布尔代数【引理6.4.2】设X,∨,∧,′是有限布尔代数，0是全下界，如果bX且b≠0，a1,a2,…,ak是X中满足aj≼b(j=1,…,k)的所有原子，则b=a1∨a2∨…∨ak

证明：因为aj≼b(j=1,…,k)，所以a1∨a2∨…∨ak≼b再证b≼a1∨a2∨…∨ak，根据引理8.2.1，只需证明b∧(a1∨a2∨…∨ak)′=0。用反证法。设b∧(a1∨a2∨…∨ak)′≠0由定理6.4.5，至少存在一个原子a，使得a≼b∧(a1∨a2∨…∨ak)′又因为b∧(a1∨a2∨…∨ak)′≼b和

b∧(a1∨a2∨…∨ak)′≼(a1∨a2∨…∨ak)′由≼的传递性可得a≼b和a≼(a1∨a2∨…∨ak)′因为a是原子且满足a≼b，所以a必是原子a1,a2,…,ak中的一个，因此第六章：格和布尔代数a≼a1∨a2∨…∨ak于是有a≼(a1∨a2∨…∨ak)∧(a1∨a2∨…∨ak)′=0即a≼0这与a是原子相矛盾。所以b∧(a1∨a2∨…∨ak)′＝0，根据引理8.2.1有b≼a1∨a2∨…∨ak由≼的反对称性知b＝a1∨a2∨…∨ak

【引理6.4.3】

设X,∨,∧,′是有限布尔代数，如果bX且b≠0，a1,a2,…,ak是X中满足aj≼b(j=1,…,k)的所有原子。则b=a1∨a2∨…∨ak是将b表示为原子的惟一形式。第六章：格和布尔代数

证明：设有b的另外一种表示形式b=∨∨…∨且是X中的原子。因为b是的最小上界，所以必有≼b(i=1,…,t)，而a1,a2,…,ak是X中满足aj≼b(j=1,…,k)的所有不同的原子。所以，必有t≤k。当t＜k时，a1,a2,…,ak中必有使得≠，i=1,…,t于是，∧=(∧a1)∨(∧a2)∨…∨(∧)∨…∨(∧ak)=∧(a1∨a2∨…∨ak)=∧(∨∨…∨)=(∧)∨(∧)∨…∨(∧)=0∨0∨…∨0=0第六章：格和布尔代数从而=0，与是原子矛盾。所以只能有t=k【定理6.4.6】(有限布尔代数表示定理)设X,∨,∧,′是由有限布尔格X,≼导出的有限布尔代数，S是布尔格X,≼中所有原子的集合，则X,∨,∧,′和P

(S),∪,∩,~同构。

证明：xX，令T(x)=a|aS且a≼x，显然T(x)S。定义函数f：X→P(S)，f(x)=T(x)，xX⑴证明f是X到P

(S)的双射函数。设f(x)=f(y)，令f(x)=f(y)=a1,a2,…,an，由引理6.4.3知x＝a1∨a2∨…∨an＝y。于是f是单射。设b1,b2,…,bnP(S)，令x=b1∨b2∨…∨bn，由运算∨的封闭性得xX且bi≼x，i=1,…,n，f(x)=T(x)=b1,b2,…,bn，所以f是满射。故f是X到P(S)的双射函数。第六章：格和布尔代数⑵证明f是X,∨,∧,′和P(S),∪,∩,~同构。x,yX，对于任意的bbT(x∧y)

bS且b≼x∧y(bS且b≼x)且(bS且b≼y)bT(x)且bT(y)bT(x)∩T(y)从而有T(x∧y)=T(x)∩T(y)，因此f(x∧y)=T(x∧y)=T(x)∩T(y)=f(x)∩f(y)x,yX，令T(x)=a|aS且a≼x=a1,a2,…,an