第5篇ch15格与布尔代数

1、 第第1515章章 格格 与与 布布 尔尔 代代 数数15-1 15-1 格的概念格的概念 定义定义15-1.1 设设是一个偏序集，如果是一个偏序集，如果A中任意中任意两个元素都有最小上界和最大下界，则称两个元素都有最小上界和最大下界，则称为为格格（lattice）。）。 图图6-1.2所示的偏序集都是格。所示的偏序集都是格。 例例1 是格。是格。 例例2 是格。是格。 定义定义15-1.2 设设是一个格是一个格,如果在上定义两个二如果在上定义两个二元运算元运算和和 ,使得对于任意的使得对于任意的a,b A ， ab等于等于 a和和b的最小上界的最小上界, ab等于等于a和和b的最大下界的最大

2、下界,那么那么,就称就称为由格为由格所诱导的代数系统。二元运所诱导的代数系统。二元运算算和和分别称为分别称为并运算并运算和和交运算交运算。 通常用通常用ab 表示表示a,b的上确界的上确界,用用ab 表示表示a，b的下确界的下确界,和和分别称为分别称为保联保联(join)和和保交保交(meet)运算。由于对任何运算。由于对任何a，b，ab及及ab都是都是A 中确定中确定的成员，因此的成员，因此 ,均为均为A上的运算。上的运算。 定义定义15-1.3 设设是一个格是一个格, 由格由格所诱导所诱导的代数系统为的代数系统为 。设。设B A 且且B ，如果如果A中的两个运算中的两个运算和和 关于关于B

3、是封闭的，则称是封闭的，则称 是是的子格。的子格。 例例3 设设S=a,b ， (S) =, a,b,a,b由格由格诱导的代数系统为诱导的代数系统为 。其中其中为为集合的并运算和集合的并运算和为为集合的交运算。集合的交运算。 格对偶原理：格对偶原理：设设是一个偏序集是一个偏序集,在在A上定义一上定义一 个二元关系个二元关系 R,使得对于使得对于A中任意两个元素中任意两个元素a,b都有关系都有关系a Rb当且仅当当且仅当b a,于是于是也是一个偏序集。把也是一个偏序集。把和和称为相互对偶的称为相互对偶的(哈斯图相互颠倒哈斯图相互颠倒)。 可以证明，若可以证明，若是格，则是格，则也是格。也是格。

4、称称 R是是 的逆关系。记为的逆关系。记为 。 格对偶原理可以叙述为：设格对偶原理可以叙述为：设P是对任意格都真的命题，是对任意格都真的命题，如果在命题如果在命题P中把中把 换成换成 ，换成换成，换成换成，就，就得到另一个命题得到另一个命题P，我们把，我们把P称为称为P的对偶命题，则的对偶命题，则P对任意格也是真的命题。对任意格也是真的命题。 定理定理15-1.1 在一个格在一个格中，对任意两个元素中，对任意两个元素a,b A都有都有 a ab b ab ab a ab b 证明思路：证明思路： 因为因为a和和b的并是的并是a的一个上界，所以的一个上界，所以 a ab 同理同理 b ab 有对

5、偶原理，即得有对偶原理，即得 ab a ab b 定理定理15-1.2 在一个格在一个格中，对于任意元素中，对于任意元素a,b,c,d A,如果如果 a b 和和 c d则则 ac bd ac bd 推论推论 在一个格在一个格中，对于任意元素中，对于任意元素a,b,c A,如如果果b c,则则 ab ac, ab ac(保序性保序性)。 证明思路：证明思路：因为因为b bd和和d bd，所以由传递性，所以由传递性 a bd和和 c bd即即 bd是是a和和c的一个上界，而的一个上界，而ac是是a和和c的最小上界，的最小上界，所以，必有所以，必有 ac bd类似地证明类似地证明 ac bd 定理

6、定理15-1.3 在一个格在一个格中中,由格由格所诱导的代所诱导的代数系统为数系统为,则对于任意元素则对于任意元素a,b,c,d A,有有 (1) ab= ba ab= ba (2) a(bc)=(ab)c a(bc)=(ab)c (3) aa=a aa=a (4) a(ab)=a a(ab)=a（交换律）（交换律）（结合律）（结合律）（幂等律）（幂等律）（吸收律）（吸收律） 证明思路：证明思路：因（因（1）根据格的定义，）根据格的定义， a，b 。 （2）第一式：先证）第一式：先证(ab)c a(bc)根据定理根据定理1（x xy,y xy） b bc a(bc ) , a a(bc ) 根

7、据定理根据定理2（x1 x2且且y1 y2 x1y1 x2y2） ab a(bc ) 又因为又因为 c (bc ) a(bc ) 再根据定理再根据定理2 (ab)c a(bc ) 再证再证a(bc) (ab)c b ab, c c bc (ab)c a (ab) a(bc ) a(bc) a(bc ) 例例4 设设是一个偏序集，定义是一个偏序集，定义 ab =maxa,b （取大运算）取大运算） ab =min a,b （取小运算）取小运算）则则是一个格。由此格诱导的代数系统为是一个格。由此格诱导的代数系统为可以证明，该代数系统的两个运算满足可以证明，该代数系统的两个运算满足定理定理15-1.

8、3的的4个个运算律运算律。 引理引理15-1.1 设设是一个代数系统是一个代数系统,其中其中,都是二元运算且满足吸收律，则都是二元运算且满足吸收律，则和和都满足幂都满足幂等律。等律。 证明思路：证明思路： 由吸收律：由吸收律： a(ab)=a (1) a(ab) =a (2) 将将(1)中的中的b取为取为(ab) ，得得 a(a(ab)=a再由得再由得 aa=a 同理可证同理可证 aa=a 定理定理15-1.4 设设是一个代数系统是一个代数系统,其中其中,都是二元运算且满足交换律、结合律和吸收律，则都是二元运算且满足交换律、结合律和吸收律，则A上存在偏序关系上存在偏序关系 ，使，使是一个格。是

9、一个格。 证明思路：证明思路：分四部分内容来证明：分四部分内容来证明： (1) 定义二元关系定义二元关系 ： a b当且仅当当且仅当 (ab)=a (2) 证明是偏序关系（证：自反、反对称和传递）证明是偏序关系（证：自反、反对称和传递） ； (3)证明证明ab是是a和和b的最大下界（下确界）；的最大下界（下确界）； (4)证明证明、满足满足交换律和吸收律。交换律和吸收律。 第第1式证明思路：式证明思路：由定理由定理15-1.1 a ab, a ac,再由定理再由定理15-1.2和幂等律得和幂等律得 a=aa (ab)(ac) (1)另外另外,由于由于 bc b ab 和和 bc c ac所以所

10、以 bc=bcbc (ab)(ac) (2)再对再对(1)式和式和(2)式应用定理式应用定理15-1.2得得 a(bc) (ab)(ac) 第第2式证明由对偶原理从上式直接可得。式证明由对偶原理从上式直接可得。 定理定理15-1.5 在一个格在一个格中中,对于任意的对于任意的a,b,c A, 都有：都有： a(bc) (ab)(ac) (ab)(ac) a(bc) 定理定理15-1.6 设设是一个格是一个格,那么，对于任意的那么，对于任意的a,b A, 都有：都有： a b(ab)=a(ab)=b a b(ab)证明思路：证明思路： (1)先证先证 a b (ab)=a 由由a b和和a a

11、，根据定理，根据定理15-1.2得得 a ab 又根据又根据ab的定义，的定义， 有有 ab a 由二元关系由二元关系 的反对称性得的反对称性得 ： ab = a (2) 再证再证 (ab)=a a b 设设ab=a，则，则a =ab b ，这就证明了，这就证明了 (ab)=a a b 综合综合(1)和和(2)得：得： a b(ab) 定理定理15-1.7 设设是一个格是一个格,那么，对于任意的那么，对于任意的a,b,c A, 都有：都有： a ca(bc) (ab)c 证明思路：证明思路： (1)先证先证 a c a(bc) (ab)c 根据定理根据定理15-1.6有有 a c (ac)=c

12、 根据定理根据定理15-1.5有有a(bc) (ab)(ac) a(bc) (ab)c (2) 再证再证 a(bc) (ab)c a c 若若 a(bc) (ab)c 则则 a a(bc) (ab)c c 即即 a c 综合综合(1)和和(2)得：得：a ca(bc) (ab)c 推论推论 设设是一个格是一个格,那么，对于任意的那么，对于任意的a,b,c A, 都有：都有： (ab)(ac) a(b (ac) a(b (ac) ) (ab) (ac) 证明思路：第证明思路：第1式是式是 a(bc) (ab) (ac) 式的对偶。式的对偶。 第第2式是第式是第1式的对偶。式的对偶。 定义定义15

13、-1.4 设设和和是两个格是两个格,那那么么,由他们分别诱导的代数系统为由他们分别诱导的代数系统为和和 ，如果存在着一个从，如果存在着一个从A1到到A2的映射的映射f，使得对于任意的使得对于任意的a,b A1 ，有，有 f(a1 b)= f(a)2 f(b) f(a 1 b)= f(a)2 f(b)则称则称 f为从为从 到到 的格同态，的格同态，亦可称亦可称 是是 的的 格同态象。此外，格同态象。此外，当当 f是双射时，则称是双射时，则称 f为从为从 到到 的格同构，亦可称的格同构，亦可称 和和 两个格是同构的两个格是同构的 。 证明思路：证明思路：因为因为x 1y ，所以所以x1y=x f(

14、x1y) = f(x) f(x)2f(y) = f(x) 故故 f(x) 2f(y) 定理定理15-1.8 设设f是格是格和和是的格同态是的格同态,则对于任意的则对于任意的x,y A1, 若若x 1y,必有必有:f(x) 2f(y) 。 例例7： f:S (S), x y=f(x)=y| y S, y x 定理定理15-1.9 设设和和是是两两个格个格, f是从是从A1到到A2的双射，则的双射，则f是从是从到到的格同构，当且的格同构，当且仅当对任意的仅当对任意的a,b A1, 都有：都有：a 1b f(a) 2f(b) 证明证明: (1) 先证先证f是是到到的格同构的格同构 a 1bf(a)

15、2f(b) 由定理由定理15-1.8， 若若 a 1b, 必有必有: f(a) 2f(b) () 反之，设反之，设 f(a) 2f(b) ， () 则则(格同构大条件格同构大条件) f(a)2f(b)= f(a1b)= f(a) 由于由于f是双射，所以是双射，所以 a1b=a 故故 ： a 1b (2) 再证再证 a 1bf(a) 2f(b) f是是到到的格同构的格同构 设对任意的设对任意的a,b A1, a 1bf(a) 2f(b) 设设 a1b=c，则，则 c 1a, c 1b ， 于是于是 f(a1b)=f (c) ,f(c) 2f(a) , f(c) 2f(b) 故有故有 f(c) 2

16、f(a)2f(b) 令令 f(a)2f(b)=f(d) 则则 f(c) 2f(d) , f(d) 2f(a) , f(d) 2f(b) 故有故有 d 1a ，d 1b，于是，于是 d 1a1b ，即，即 d 1c， 所以所以 f(d) 2f(c) 因此因此 f(d)=f(c) 即即 f(a1b)=f(a)2f(b) 类似地可证：类似地可证： f(a1b)=f(a)2 f(b) 格同构证毕。格同构证毕。 定义定义15-2.1 设设 是由格是由格是所诱是所诱导的代数系统。如果对任意的导的代数系统。如果对任意的a,b,c A，满足：，满足： a(bc)= (ab)(ac) a(bc)= (ab)(a

17、c) 则称则称 是分配格是分配格 。15-2 分配格分配格 例例1： 集合：集合：S=a,b,c 格：格： 代数系统：代数系统： 结论：结论： 是一个分配格。是一个分配格。 例例2：不是分配格的例子。：不是分配格的例子。 例例3：利用两个：利用两个“特殊五元素非分配格特殊五元素非分配格”的结论。的结论。 定理定理15-2.1 如果在一个分配格中交运算对于并运算可如果在一个分配格中交运算对于并运算可分配，则并运算对于交运算也一定是可分配的。反之亦然。分配，则并运算对于交运算也一定是可分配的。反之亦然。 证明证明定理的前半部分：定理的前半部分： 分配格中交对并可分配分配格中交对并可分配 并对交也一

18、定可分配并对交也一定可分配设对任意的设对任意的a,b,c A，若若 a(bc)= (ab)(ac) (交对并可分配交对并可分配a)则则 (ab)(ac) =(ab)a)(ab)c) (交对并可分配交对并可分配(ab) =a(ab)c) (吸收律吸收律) =a(ac)(bc) (交对并可分配交对并可分配c) =(a (ac) )(bc) (结合律结合律) =a(bc) (吸收律吸收律) （并对交可分配）（并对交可分配） 定理定理15-2.2 每个链是分配格。每个链是分配格。 证明证明 是链是链 是分配格是分配格 设设是一个链，所以，是一个链，所以， 一定是格。一定是格。对任意的对任意的a,b,c

19、 A，只要讨论以下两种情况：，只要讨论以下两种情况： （1） a b 或或 a c （2） b a 且且 c a 对于情况（对于情况（1），无论是），无论是b c还是还是c b ，都有，都有 a(bc)= a 和和 (ab)(ac)=a （a小）小） 对于情况（对于情况（2），总有），总有 bc a 所以所以 a(bc) = bc （a大）大）而由而由b a和和c a ，应有，应有(ab)(ac)=bc 故故a(bc)=(ab)(ac)成立。成立。 定理定理15-2.3 设设是分配，那么，对任意的是分配，那么，对任意的a,b,c A,如果满足如果满足:ab=ac和和ab=ac成立成立, 则必有

20、则必有 b=c 。 证明证明：因为：因为 (ab)c= (ac)c=c (吸收律吸收律) 而而 (ab)c=(ac)(bc)=(ab)(bc) = b(ac) (并对交可分配并对交可分配b) = b(ab) (ab=ac条件条件) =b (吸收律吸收律) b = c成立。成立。 定义定义15-2.2 设设 是由格是由格是所诱是所诱导的代数系统。如果对任意的导的代数系统。如果对任意的a,b,c A，当，当b a时，时，有：有： a(bc)= b(ac) 则称则称 是模格是模格 。 定理定理15-2.4 设设是模格，当且仅当在中不含是模格，当且仅当在中不含有适合下述条件的元素有适合下述条件的元素

21、， ， 满足：满足： 且且 = 和和 = 证明证明：(1)先证：先证： 是模格是模格 有有 , , , ,使使 且且 = 和和 = (反设反设) 若存在上述若存在上述 , , , , 因为因为 , , 且且 ( ) )= ( ) )= (吸收律吸收律) ( ) ) =( ) ) = (吸收律吸收律) 比较上两式，得比较上两式，得 ( ) ) ( ) ) (根据根据 ) 所以所以 不是模格。不是模格。 (出现矛盾出现矛盾) (2) 再证：有再证：有 , , , ,使使 且且 = 和和 = 是模格是模格 (反设反设) 若若不不是模格，则有是模格，则有a,b,c满足：满足： b b a 且且 b(c

22、a) (bc)a 令令 = =b(ca) = (bc)a = =c有有 = =(bc)ac= a(bc)c) = =ac= acc 因此因此 (ac b(ca)= ) 另外另外, ,由于由于(条件条件) , ,故有故有 ,所以所以: = 同理可证同理可证 = 。 (3)综合综合(1)和和 (2)得到结论。得到结论。 定理定理15-2.5 对于模格对于模格，若有三个元素，若有三个元素a,b,c，使得以下三式中的任意一式中把使得以下三式中的任意一式中把“ ”换为换为“=”成立，则成立，则另外两个式子中把另外两个式子中把“ ”换为换为“=”也成立。也成立。 a(bc) (ab )(ac) (1) (

23、ab)(ac) a(bc) (2) (ab)(bc)(ca) (ab)(bc)(ca) (3) 证明证明：设：设(1)成立，根据对偶律成立，根据对偶律(2)也成立。也成立。 只需先证明：只需先证明： (1)成立且成立且(2)成立成立 (3)也成立也成立 (3)式右端式右端= (ab)(bc)(ca)=(ac)b) (ca) =(ca) b)(ac) ( (分配分配(ca) ) = (ab)(bc)(ca) = (3)式左端式左端 ( (分配分配b) ) 再证明：再证明： (3)也成立也成立 (1)成立且成立且(2)成立成立 (1)左端左端= a(bc)=利用利用(3)式推导式推导= (1)右端

24、右端。 定理定理15-2.6 对于分配格必定是模格。对于分配格必定是模格。 证明证明：设：设是一个分配格，对于是一个分配格，对于A的任意元素的任意元素a,b,c，如果，如果 b a 则则 ab= b 。 因此因此 a(bc)= (ab)(bc) = b(ac) 6-3 有补格有补格 定义定义15-3.1 设设是一个格，如果存在元素是一个格，如果存在元素a A ,对对于任意的于任意的x A,都有都有a x,则为格的全下界则为格的全下界,记为记为“0”。 定理定理15-3.1 格格若有全下界若有全下界,则全下界是唯一的。则全下界是唯一的。 证明证明：用反证法：用反证法 如果有两个不相等的全下界如果

25、有两个不相等的全下界a和和b，a,b A 且且ba 因为因为 a 是全下界，是全下界， b A ，所以，所以 a b 又因为又因为 b 是全下界，是全下界， a A ，所以，所以 b a 由此得由此得 a=b 与有两个不相等的全下界与有两个不相等的全下界a和和b 矛盾。矛盾。 定义定义15-3.2 设设是一个格，如果存在元素是一个格，如果存在元素b A,对对于任意的于任意的x A,都有都有x b,则为格的全上界则为格的全上界,记为记为“1”。 证明证明：用反证法：用反证法 如果有两个不相等的全上界如果有两个不相等的全上界a和和b ，a,b A 且且ba 因为因为 a 是全上界，是全上界， b

26、A ，所以，所以 b a 又因为又因为 b 是全上界，是全上界， a A ，所以，所以 a b 由此得由此得 a=b 与有两个不相等的全上界与有两个不相等的全上界a和和b 矛盾。矛盾。 定理定理15-3.2 格格若有全上界若有全上界,则全下界是唯一的。则全下界是唯一的。 定义定义15-3.3 设设是一个格，如果存在全下界和全是一个格，如果存在全下界和全上界，则称该格为有界格。上界，则称该格为有界格。 定理定理15-3.3 设设是一个有界格，则对于任意的是一个有界格，则对于任意的a A,都有都有 a1=1 a1=a (1是是运算的零元运算的零元,运算的幺元运算的幺元) a0=a a0=0 (0是

27、是运算的幺元运算的幺元,运算的零元运算的零元) 证明证明：(1) 证证 a1=1 因为因为 a1 A且且1是全上界，所以是全上界，所以 a1 1 又因为又因为 1 a1，所以，所以 a1=1 (2) 证证 a1=a 因为因为 a a， a 1, 所以所以 a a1 又因为又因为 a1 a， 所以所以 a1=a (3) 证证a0=a (略略) (4) 证证a0=0 (略略) 定义定义15-3.4 设设是一个有界格，对于是一个有界格，对于A中任意的中任意的a,如果存在如果存在b A ，使得，使得ab=1和和ab=0 ，则称元素，则称元素b是是元素元素a的的补元补元。此时称。此时称a和和b是是互补的

28、互补的。 定义定义15-3.5 在一个有界格中，如果每个元素都至少有在一个有界格中，如果每个元素都至少有一个补元素，则称此格为一个补元素，则称此格为有补格有补格。 定理定理15-3.4 在一个有界分配格中，如果有一个元素在一个有界分配格中，如果有一个元素有补元素，则必是唯一的。有补元素，则必是唯一的。 证明证明：设：设 a有两个补元素有两个补元素b和和c，即有，即有 ab=1 和和 ab=0 ac=1 和和 ac=0 由定理由定理15-2.3即得即得 b=c 定义定义15-3.6 一个格如果如果它即是有补格，又是分配一个格如果如果它即是有补格，又是分配格，则称此格为格，则称此格为有补分配格有补

29、分配格。一般把任一元素。一般把任一元素a的唯的唯一补元记为一补元记为 a (或或a- )。 15-4 15-4 布尔代数布尔代数 定义定义15-4.1 代一个有补分配格称为代一个有补分配格称为布尔格布尔格。 求一个元素的补元素可以看作一元运算，称为补运算。求一个元素的补元素可以看作一元运算，称为补运算。 定义定义15-4.2 设设 是由布尔格是由布尔格是所诱导的代数系统。称这个代数系统为是所诱导的代数系统。称这个代数系统为布尔代数布尔代数。 例例1 设设是由布尔格是由布尔格是所诱导的代数系统。这个代数系统为是所诱导的代数系统。这个代数系统为布尔代数布尔代数。 定理定理15-4.1 在一个有界分

30、配格中，对于布尔代数中在一个有界分配格中，对于布尔代数中的任意两个元素的任意两个元素a，b，必定有，必定有 ( a )=a ab= ab ab= ab 证明证明：只证第：只证第(2)个等式个等式 先证互补的两个式子先证互补的两个式子相并相并等于全上界等于全上界“1”。 (ab)(ab)= (ab)a)(ab)b) =(b(aa)(a(bb) =(b1)(a1) =1 再证互补的两个式子再证互补的两个式子相交相交等于全下界等于全下界“0”。 (ab)(ab)= 0 定义定义15-4.3 具有有限个元素的布尔代数称为具有有限个元素的布尔代数称为有限有限布尔代数布尔代数。 定义定义15-4.4 设设

31、和和是两是两个布尔代数个布尔代数,如果存在着如果存在着A到到B的双射的双射f,对于任意的对于任意的a,b A,都有都有 f(ab)=f(a)f(b) f(ab)=f(a)f(b) f(a)=f(a)则称则称和和同构同构。 可以证明可以证明,对于每一正整数对于每一正整数n,必存在着必存在着2n个元素的布个元素的布尔代数尔代数;反之反之,任一有限布尔代数任一有限布尔代数,它的元素个数必为它的元素个数必为2的幂的幂次。次。 定义定义15-4.5 设设 是一个格，且具有全下界是一个格，且具有全下界0，如果有元素如果有元素a盖住盖住0，则称元素，则称元素a为原子。为原子。 原子：与原子：与0相邻且比相邻

32、且比0“大大” 定理定理15-4.2 设设 是一个具有全下界是一个具有全下界0的有限的有限格，则对于任何一个非零元素格，则对于任何一个非零元素b（即不等于全下界（即不等于全下界0的元的元素）至少存在一个原子素）至少存在一个原子a ，使得，使得a b 。 证明证明：若：若b是原子，则有是原子，则有b b ，若，若b不是原子，则必不是原子，则必有有b1存在，使得存在，使得0 b1 b 若若b1是原子，则定理得证，否则，必存在是原子，则定理得证，否则，必存在b2使得使得 0 b2 b1 b 由于是一个有下界的有限格，所以通过有限不骤总可由于是一个有下界的有限格，所以通过有限不骤总可以找到一个原子以找

33、到一个原子bi ，使得，使得0 bi . b2 b1 b 引理引理15-4.1 设在一个布尔格中设在一个布尔格中,bc=0当且仅当当且仅当b c。 证明证明：(1)先证先证 bc=0 b c 若若 bc=0， 因为因为 0c=c ， 则则 (bc)c=c 根据分配性，就有根据分配性，就有 (bc) (cc) =c 即即 (bc) 1 =c 所以所以 bc =c 又因为又因为 b bc 所以所以 b c (2)再证再证 b c bc=0 若若b c, ,则则bc cc, ,即即bc 0 0，所以所以bc=0 引理引理15-4.2 设设是一个有限布尔代数是一个有限布尔代数,若若b是是A中中 任意非

34、零元素，任意非零元素， a1, a2, , ak是是A中满足中满足aj b 的所有原子（的所有原子（j=1,2,k） ,则则 b = a1a2ak 证明证明：(1)先证先证 a1a2ak b 记记a1a2ak =c,因为因为aj b,所以所以c b。 (2)再证再证 b a1a2ak 由引理由引理6-4.1知知,要证要证b c若是原子若是原子,只需证只需证bc=0, 反设反设bc0,于是必有一个原子于是必有一个原子a,使得使得a bc。 又因又因bc b,和和 bc c, 所以所以 a b 和和 a c , 因为因为a是原子是原子,且且a b,所以所以a必是必是a1, a2, , ak中的一中

35、的一 个个,因此因此 a c,已有已有a c,得得a cc,即即a 0, 与与a是原子矛是原子矛盾。盾。 bc0假设不成立假设不成立 。综合。综合(1)和和(2)定理得证。定理得证。 引理引理15-4.3 设设是一个有限布尔代数是一个有限布尔代数,若若b是是A中中 任意非零元素，任意非零元素， a1, a2, ,ak是是A中满足中满足aj b的的所有原子（所有原子（j=1,2,k） ,则则b = a1a2ak是将是将b表示表示为原子之并的唯一形式。为原子之并的唯一形式。 证明证明:设有另一种表示形式为设有另一种表示形式为b=aj1aj1ajt 其中其中aj1,aj1,ajt是原子。因为是原子。

36、因为b是是aj1,aj1,ajt的最小上的最小上界界,所以必有所以必有aj1 b, aj2 b,., ajt b。而。而a1, a2, , ak是是A中中所有满足所有满足ai b （i=1,2,k）的不同原子。）的不同原子。 所以必有所以必有 tk 反设反设t k,那么在那么在a1, a2, , ak中必有中必有aj0且且aj0ajl 于是于是,由由aj0(aj1aj1ajt)= aj0(a1a2ak)即即 (aj0aj1) (aj0aj2) (aj0 ajt) = (aj0a1) (aj0a2) (aj0 ak)导致的导致的0= aj0矛盾。矛盾。t k假设不成立假设不成立 。 T= =k定

37、理得证。定理得证。 引理引理15-4.4 在一个布尔格在一个布尔格中中,对对A中中 任意一任意一个原子个原子a和另一个非零元素和另一个非零元素b，a b 和和a b两式中有且两式中有且仅有一式成立。仅有一式成立。 证明证明：(1)先证先证a b 和和a b两式两式不可能同时成立不可能同时成立 反设反设a b 和和a b同时成立，就有同时成立，就有a bb=0，这，这与与a是原子相矛盾，即是原子相矛盾，即a b 和和a b同时成立。同时成立。 (2)再证再证a b 和和a b两式中两式中必有一式成立必有一式成立 因为因为ab a, a是原子是原子,所以只能是所以只能是 ab=0 或或 ab=a

38、若若ab=0，则，则 a(b) =0 ，由引理，由引理6-4.1得得 a b； 若若ab=a,由引理由引理6-1.6得得a b。 定理定理15-4.3(Stone 表示定理表示定理) 设设 是由是由有限布尔格有限布尔格所诱导的一个有限布尔代数，所诱导的一个有限布尔代数， S是布是布尔格中的所有原子的集合，则尔格中的所有原子的集合，则和和同构。同构。 证明证明：本定理的证明过程分三部分：本定理的证明过程分三部分 (1)构造一个映射，并证明它是双射（既是入射又是满构造一个映射，并证明它是双射（既是入射又是满射）；射）； (2)描述代数系统描述代数系统和和同构并证明之；同构并证明之； (3)总结概括

39、结论。总结概括结论。 第第(1)部分部分证明：证明：对于任意对于任意a A,必有的唯一表示：必有的唯一表示： a=a1a2 ak （引理（引理15-4.2a的原子表示）的原子表示）其中其中ai a （i=1,2,k）,作映射作映射 f(a)=S1那么，这个映射是那么，这个映射是 一个从一个从A到到 (S)的一个双射。的一个双射。 第第1 1部分部分双射证明：双射证明： . . 对于全下界对于全下界0 A，规定，规定 f(0)= 。 . .如果如果 S1 =a1,a2 , ak (S)，而有，而有a,b A,使得使得 f(a)= f(a)=S1 ，则则a=a1a2 ak = b， 所以所以 f是

40、一个从是一个从A到到 (S)的一个入射。的一个入射。 . .对于任一个对于任一个S1 (S)，若，若S1 =a1,a2 , ak，则由，则由于运算于运算的封闭性，所以的封闭性，所以 a1a2ak = a A这就说明这就说明 (S)中任一元素，必是中任一元素，必是A中某个元素的象，所以中某个元素的象，所以是一个从是一个从A到到 (S)的一个满射。的一个满射。 第第1 1部分部分双射证明完毕。双射证明完毕。 第第(2)部分部分证明：证明：和和同构同构 第第2 2部分部分同构性格证明：同构性格证明： . . 设设 f(ab)=S3,若若x S3,则则x必是满足必是满足x ab的原的原子，因为子，因为

41、ab a和和ab b，所以，所以x a且且x b，推得，推得x S1且且x S2，即，即x S1S2 ，这就证得，这就证得S3 S1S2 。 反之反之,若若x S1S2,则则x S1且且x S2,所以所以x必是满足必是满足x a和和x b的原子的原子,推得推得x必是满足必是满足x ab的原子的原子,所以所以x S3,这这就证明了就证明了 S1S2 S3 。 综上所述，就有综上所述，就有S3 = = S1S2 ，即，即 f(ab)= f(a)f(b) . . 设设 f(ab)=S3,若若x S3,则则x是满足是满足x ab的原的原子，所以必有子，所以必有x a或或x b，这是因为：，这是因为：

42、若若x a且且x b,则由引理则由引理6-4.4可知必有可知必有 x a且且x b,所所以以x ab= ab 。再由条件。再由条件x ab,便得便得 x (ab)(ab)=0这与这与x是原子相矛盾。是原子相矛盾。因此，若因此，若x a则则x S1或者若或者若x b则则x S2 ，所以，所以 x S1S2 这就证明了这就证明了S3 S1S2 。 反之反之,若若x S1S2, 则则x S1或或x S2,若若x S1，则，则 x a ab所以所以x S3,同理，若同理，若x S2，则，则 x b ab所以所以x S3,这就证明了这就证明了 S1S2 S3 。 综上所述，就有综上所述，就有S3 = =

43、 S1S2 ，即，即 f(ab)= f(a)f(b) . .最后证明同构性的最后证明同构性的f(a)= f(a)式：式： 将将S看作全集看作全集, ,另另f(a)=S1, ,则则f(a)=S-S1=S-f(a), ,可以证可以证明明x f(a)当且仅当当且仅当x a, ,这是因为这是因为, ,若若x f(a), ,必有必有x a, ,则则由引理由引理6-4.4可知必有可知必有 x a, ,反之反之, ,若原子若原子x满足满足x a, ,则必则必有有x a, ,所以所以x f(a) 。 还可以证明还可以证明, ,对于原子对于原子x, ,x a当且仅当当且仅当x f(a), ,这是这是因为因为,

44、,若若x a而而x f(a), ,将导致将导致x a的矛盾的矛盾, ,所以所以x f(a), ,反反之之, ,若若x f(a)而而x a, ,也将导致也将导致x f(a)的矛盾的矛盾, ,所以所以x a 。 另外还可以证明另外还可以证明, , x f(a)当且仅当当且仅当x f(a), ,所以所以, ,对于对于原子原子x, , x f(a)当且仅当当且仅当x f(a), ,因此因此, , f(a)=f(a) 第第2 2部分部分同构性证明完毕。同构性证明完毕。 (3)总结概括结论总结概括结论:和和同构。同构。 推论推论15-4.1 有限布尔格的元素个数必定等于有限布尔格的元素个数必定等于2n，其

45、中，其中n是该布尔格中所有原子的个数。是该布尔格中所有原子的个数。 推论推论15-4.2 任何一个具有任何一个具有2n个元素的有限布尔代数个元素的有限布尔代数都是同构的。都是同构的。15-5 布尔表达式布尔表达式 定义定义15-5.115-5.1 设设A, 为布尔代数为布尔代数, ,如下递归如下递归地定义地定义A A上上布尔表达式布尔表达式( (Boolean expressionsBoolean expressions) )：布尔常元布尔常元( (取值于取值于A A的常元的常元) )是布尔表达式是布尔表达式, ,布尔布尔常元常用常元常用a a, ,b b，c c等符号表示。等符号表示。布尔变

46、元布尔变元( (取值于取值于A A的变元的变元) )是布尔表达式，布是布尔表达式，布尔变元常用尔变元常用x x，y y，z z等符号表示。等符号表示。如果如果e e1 1, ,e e2 2为布尔表达式，那么为布尔表达式，那么( (e e1 1),(),(e e1 1ee2 2) ,() ,(e e1 1ee2 2) ) 也是布尔表达式。也是布尔表达式。除有限次使用条款（除有限次使用条款（2 2），（），（3 3）生成的表达式）生成的表达式是布尔表达式外，没有别的是布尔表达式。是布尔表达式外，没有别的是布尔表达式。 例例1 1 给出了两个布尔函数的例子给出了两个布尔函数的例子. . 例例2 2

47、给出了布尔表达式的例子给出了布尔表达式的例子。 定义定义15-5.2 15-5.2 一个含有一个含有n n个相异变元的布尔表达式，个相异变元的布尔表达式，称为含有称为含有n n元的布尔表达式，记为元的布尔表达式，记为E(xE(x1 1,x,x2 2,x,xn n) )，其中其中x x1 1,x,x2 2,x,xn n为为变元。变元。 定义定义15-5.3 15-5.3 布尔代数布尔代数A, 上的一个含有上的一个含有n n元的布尔表达式元的布尔表达式E(xE(x1 1,x,x2 2,x,xn n) )的值是指：将的值是指：将A A中的中的元素作为变元元素作为变元x xi i(i=1,2,n)(i

48、=1,2,n)的值来代替表达式中的值来代替表达式中相应的变元（即对变元赋值）相应的变元（即对变元赋值）, ,从而计算出表达式的值。从而计算出表达式的值。 定义定义15-5.4 15-5.4 布尔代数布尔代数A, 上两个上两个n n元的元的布尔表达式为布尔表达式为E E1 1(x(x1 1,x,x2 2,x,xn n) )和和E E2 2(x(x1 1,x,x2 2,x,xn n) ), ,如果对于个变元的任意赋值如果对于个变元的任意赋值x xi i=x=xi i, ,x xi i A时均有时均有 E E1 1(x(x1 1,x,x2 2,x,xn n)=E)=E2 2(x(x1 1,x,x2

49、2,x,xn n) ) 则称这两个则称这两个布尔表达式布尔表达式是等价的。是等价的。 例例3 布尔代数布尔代数0,1, 上两个上两个3 3元的布尔表达元的布尔表达式为式为 E E1 1(x(x1 1,x,x2 2,x,x3 3)=(x)=(x1 1xx2 2)(x)(x1 1xx3 3) ) 和和 E E2 2(x(x1 1,x,x2 2,x,x3 3)=x)=x1 1(x(x2 2xx3 3) ) 验证这两个布尔表达式是等价的。验证这两个布尔表达式是等价的。 E E1 1(0,1,1)=(01)(00)=0(0,1,1)=(01)(00)=0 E E2 2(0,1,1)=0(10)=0(0,1,1)=0(10)=0 E E1 1(1,1,1)=(11)(10)=1(1,1,1)=(11)(10)=1 E E2 2(1,1,1)=1(10)=1(1,1,1)=1(10)=1 E E1 1(0,0,0)=(00)(01)=0(0,0,0)=(00)(01)=0 E