离散数学课件(第6章)

1、离散数学离散数学教案教案计算机科学与技术学院计算机科学与技术学院课程学时：课程学时：64主主 讲：宋讲：宋 成成河南理工大学河南理工大学电子教案电子教案第六章：格和布尔代数第六章：格和布尔代数6.1 格的概念格的概念6.2 分配格分配格6.3 有补格有补格6.4* 布尔代数布尔代数第六章：格和布尔代数第六章：格和布尔代数教学目的及要求：教学目的及要求： 深刻理解和掌握格与布尔代数的基本概念和基本运深刻理解和掌握格与布尔代数的基本概念和基本运算算教学类容：教学类容： 格的概念、有补格，分配格、布尔代数和布尔表格的概念、有补格，分配格、布尔代数和布尔表达式。达式。教学重点：教学重点： 格、布尔代数

2、和布尔表达式。格、布尔代数和布尔表达式。教学难点：教学难点： 布尔代数和布尔表达式。布尔代数和布尔表达式。6.1 格的概念格的概念【定义【定义6.1.1】 设设 X, 是偏序集，如果是偏序集，如果 x,y X，集合，集合 x,y 都有最小上界和最大下界，则称都有最小上界和最大下界，则称 X, 是格。是格。【例【例6.1】设设S12 1,2,3,4,6,12 是是12的因子构成的集合。其的因子构成的集合。其上的整除关系上的整除关系R=x,y | x S12y S12x整除整除y ，R是是S12上上的偏序关系，的偏序关系， S12,R 是偏序集。写出是偏序集。写出S12上的盖住关系上的盖住关系CO

3、V S12，画出哈斯图，验证偏序集，画出哈斯图，验证偏序集 S12,R 是格。是格。 解：解：S12上的盖住关系上的盖住关系 COV S121,2 , 1,3 , 2,4 , 2,6 , 3,6 , 4,12 , 6,12，哈斯图如图哈斯图如图6.1所示。从哈斯图中可看出，集合所示。从哈斯图中可看出，集合S12的任意两的任意两个元素都有最小上界和最大下界，故偏序集个元素都有最小上界和最大下界，故偏序集 S12,R 是格。是格。 第六章：格和布尔代数第六章：格和布尔代数第六章：格和布尔代数第六章：格和布尔代数【例【例6.2】图图8.2中给出了一些偏序集的哈斯图，判断它们是中给出了一些偏序集的哈斯

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

5、运算；用xy表示集合表示集合 x,y 的最的最大下界，二元运算大下界，二元运算称为交运算。称为交运算。 【定义定义6.1.2】 设设 X, 是格，是格，是是X上的并运算，上的并运算，是是X上的上的交运算。则称交运算。则称 X, 是格是格 X, 导出的代数系统。导出的代数系统。 x,y P (A)，xy=xy，xy=xy。这样，格。这样，格 P (A),R 导出的代数系统导出的代数系统 P (A), 实际就是代数系统实际就是代数系统 P (A), ，所以，二元运算所以，二元运算和和的运算表如表的运算表如表6.1和表和表6.2所示。所示。 在例在例6.1中，根据图中，根据图6.1，集合，集合 4,

6、6 的最小上界为的最小上界为12，即，即46=12=4和和6的最小公倍数；它的最大下界为的最小公倍数；它的最大下界为2，即，即46=2=4和和6的最大公约数。同样，这个结果也可以推广到一的最大公约数。同样，这个结果也可以推广到一般情况。即在格般情况。即在格 S12,R 导出的代数系统导出的代数系统 S12, 中，二元中，二元运算运算是求最小公倍数；二元运算是求最小公倍数；二元运算是求最大公约数。是求最大公约数。 第六章：格和布尔代数第六章：格和布尔代数表6. 1 表6. 2aabba,baaaa,ba,ba,bbba,ba,ba,ba,ba,bba,ba,baba,baaabbba,baba,

7、b第六章：格和布尔代数第六章：格和布尔代数定义定义6.1.3 设设f是含有格中元素以及符号是含有格中元素以及符号=, , ,和和的命的命题。将题。将f中的中的 替换成替换成 ， 替换成替换成 ，替换成替换成，替换成替换成，得到一个新命题，所得的命题叫做，得到一个新命题，所得的命题叫做f的对偶命的对偶命题，记为题，记为f *。 例如，在格中，例如，在格中，f为为a(bc) a，则，则f的对偶命题的对偶命题f *为为a(bc) a 命题命题f和它的对偶命题和它的对偶命题f *遵循下列的规则，这规则叫遵循下列的规则，这规则叫做格的对偶原理。做格的对偶原理。 设设f是含有格中元素以及符号是含有格中元素

8、以及符号=,和和的命题。的命题。 若若f对一切格为真，则对一切格为真，则f的对偶命题的对偶命题f *也对一切格为真。也对一切格为真。 格的许多性质都是互为对偶命题的。有了格的对偶原格的许多性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只需证明其中的一个就可以了。理，在证明格的性质时，只需证明其中的一个就可以了。 第六章：格和布尔代数第六章：格和布尔代数【定理定理6.1.1】 设设 X, 是格，是格， X, 是格是格 X, 导出导出的代数系统。则的代数系统。则 a,b,c X有有 ab=ba， ab=ba (交换律交换律) (ab)c=a(bc) (ab)c=a(bc) (结合律结

9、合律) aa= a， aa= a (幂等律幂等律) a(ab)=a a(ab)=a (吸收律吸收律) 证明：证明： a,b X， a,b = b,a ，所以它们的最小上界相，所以它们的最小上界相等。即等。即ab=ba，同理可证，同理可证ab=ba a和和b的最大下界一定是的最大下界一定是a、b的下界，即的下界，即ab a，同理，同理，(ab)c ab，所以，所以，(ab)c ab a 同理有同理有 (ab)c ab b 和和 (ab)c c第六章：格和布尔代数第六章：格和布尔代数由以上由以上3式得式得 (ab)c bc和和(ab)c a(bc)类似地可证类似地可证 a(bc) (ab)c根据偏

10、序关系的反对称性有根据偏序关系的反对称性有(ab)c= a(bc) 由对偶原理得由对偶原理得 (ab)c= a(bc) 显然显然a aa，又由，又由 的自反性得的自反性得a a，从而推出，从而推出aa a，根据偏序关系的反对称性有，根据偏序关系的反对称性有aa=a 由对偶原理得由对偶原理得aa=a 显然显然 a a(ab)， 又由又由a a，ab a得得a(ab) a，从而得，从而得 a(ab)=a。 由对偶原理得由对偶原理得a(ab)=a第六章：格和布尔代数第六章：格和布尔代数【定理【定理6.1.2】 设设 X, 是代数系统，其中是代数系统，其中,都是二元运算。都是二元运算。如果如果和和满足

11、吸收律，则满足吸收律，则和和满足幂等律。满足幂等律。 证明证明：aa=a(a(ab)=a，同理可证，同理可证aa=a【定理定理6.1.3】 设设 X, 是代数系统，其中是代数系统，其中,都是二元运算，都是二元运算，满足交换律、结合律和吸收律，则可适当定义满足交换律、结合律和吸收律，则可适当定义X的偏序关系的偏序关系 ，使，使 X, 构成一个格。构成一个格。 证明证明：定义定义X上的一个二元关系上的一个二元关系 =a,b |a,b X且且ab=a 证明证明 是是X上的偏序关系。上的偏序关系。 由定理由定理6.1.2知知满足幂等律，即满足幂等律，即aa=a，所以，所以a a。故。故 是自反是自反的

12、。的。 设设a b且且b a，则，则ab=a且且ba=b，于是，于是a=ab=ba=b。所以所以 是反对称的。是反对称的。 设设a b且且b c，则，则ab=a且且bc=b，于是，于是ac=(ab)c=a(bc)=ab=a，即，即a c，故，故 是传递的。是传递的。 这就证明了这就证明了 是是X上的偏序关系。上的偏序关系。 第六章：格和布尔代数第六章：格和布尔代数 证明证明 a,b X，ab是集合是集合 a,b 的最大下界。因为的最大下界。因为 (ab)a=ab和和(ab)b=ab所以所以ab a且且ab b，即，即ab是是 a,b 的下界。的下界。 下证下证ab是是 a,b 的最大下界。的最

13、大下界。 设设c是是 a,b 的任一下界，即的任一下界，即c a，c b，那么有，那么有 ca=c，cb=c而而 c(ab)=(ca)b=cb=c所以所以 c ab，即，即ab是是 a,b 的最大下界。的最大下界。 证明证明ab=a的充分必要条件是的充分必要条件是ab= b 设设ab=a，由吸收率可得，由吸收率可得 ab=(ab)b=b(ba)=b，即，即ab= b 设设ab=b，由吸收率可得，由吸收率可得 ab=a(ab)=a，即，即ab=a第六章：格和布尔代数第六章：格和布尔代数 证明证明 a,b X，ab是集合是集合 a,b 的最小上界。的最小上界。 根据根据，偏序关系，偏序关系 可以等

14、价的定义为：可以等价的定义为： =a,b |a,b X且且ab=b ，用这个定义和类似于用这个定义和类似于的方法可以证明的方法可以证明ab是集合是集合 a,b 的的最小上界。最小上界。 因此，因此， X, 构成一个格。构成一个格。 根据定理根据定理6.1.3，可以给出格的另一个等价定义。，可以给出格的另一个等价定义。 【定义定义6.1.4】 设设 X,* *, 是代数系统，其中是代数系统，其中* *和和 都是二都是二元运算，如果元运算，如果* *和和 在在X上封闭且满足交换律、结合律和吸上封闭且满足交换律、结合律和吸收律，则称收律，则称 X,* *, 为格。为格。 根据定义根据定义6.1.4和

15、定理和定理6.1.1，格，格 X, 导出的代数系统导出的代数系统 X, 是格，以后不再区分偏序集定义的格和代数系统是格，以后不再区分偏序集定义的格和代数系统定义的格，统称为格。定义的格，统称为格。第六章：格和布尔代数第六章：格和布尔代数【定理【定理6.1.4】 设设 X, 是格，是格，是是X上的并运算，上的并运算，是是X上的交运算。则上的交运算。则 a,b X有有 a b当且仅当当且仅当ab=a a b当且仅当当且仅当ab=b 证明：证明： 设设a b，下证，下证ab=a 由由a a且且a b知知a是集合是集合 a,b 的下界，故有的下界，故有a ab；另一方面，由于另一方面，由于ab是是 a

16、,b 的最大下界，所以是的最大下界，所以是 a,b 的下的下界，即界，即ab a。根据偏序关系的反对称性得。根据偏序关系的反对称性得ab=a 设设ab=a，下证，下证a b a=ab b，即，即a b 可类似可类似进行证明。进行证明。第六章：格和布尔代数第六章：格和布尔代数【 定理定理6.1.5】 设设 X, 是格，是格，是是X上的并运算，上的并运算，是是X上的上的交运算。交运算。 a,b,c,d X，若，若a b且且c d，则，则ac bd，ac bd 证明证明： a b bd ，c d bd，因此，因此ac bd 类似的可以证明类似的可以证明ac bd【定理【定理6.1.6】 设设 X,

17、是格，是格，是是X上的并运算，上的并运算，是是X上的交上的交运算。则运算。则 a,b,c X有有 a(bc) (ab)(ac) (ab)(ac) a(bc) 证明证明： 根据定理根据定理8.1.5，由，由a a和和bc b得得 a(bc) ab 又由又由a a且且bc c得得 a(bc) ac 从而得到从而得到 a(bc) (ab)(ac) 利用对偶原理，即得利用对偶原理，即得。 一般地说，格中的一般地说，格中的和和并不满足分配律。并不满足分配律。 第六章：格和布尔代数第六章：格和布尔代数【定义【定义6.1.5】 设设 X, 是格，是格，B是是X的非空子集，如果的非空子集，如果B关于运算关于运

18、算和和也构成格，则称也构成格，则称 B, 是是 X, 的子的子格。格。 在例在例6.1中，令中，令B1 1,2,3,6 ，B2 2,4,6,12 ，则，则 B1, 和和 B2, 是格是格 S12, 的子格。的子格。 令令B3 1,2,3,12 ，由于，由于23=6，而，而6 B3，所以，所以 B3, 不是格不是格 S12, 的子格。的子格。 以下定义格的同态。以下定义格的同态。【定义定义6.1.6】 设设 X1,1,1 和和 X2,2,2 是格，其中是格，其中1,1,2和和2都是二元运算。都是二元运算。f是从是从X1到到X2的一个映射，对任的一个映射，对任意的意的a,b X1有有f(a1b)=

19、f(a)2 f(b)， f(a1b)=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

20、,b X1，如果，如果a 1b，必有，必有f(a) 2f(b) 证明：证明：设设a 1b，根据定理，根据定理6.1.4，a1b=a，由于，由于 f 是格是格 X1,1,1 到格到格 X2,2,2 的格同态，所以的格同态，所以 f(a)=f(a1b)=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

21、 =x,y |x P(A)y P (A)x y 是是P(A)上的偏序关系。上的偏序关系。 P(A), R 也是格。作映射也是格。作映射f：AP (A)，定义为：，定义为： x A，f(x)= y|y A且且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,b A，设，设a b， c f(a)，c a，由偏序关系，由偏序关系的传递性得的传递性得c b，所以，所以c f(b)，即即f(a) f

22、(b)，于是，于是f(a)R f(b)。故故f是保序的。是保序的。 对于对于b,d A，bd=a f(bd)=f(a)=A f(b)f (d)= b,e d,e = b,d,e f(bd)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 的

23、格同构的充分必要条件是的格同构的充分必要条件是 a,b X1，a 1bf(a) 2f(b) 证明证明：设设f是是 X1,1,1 到到 X2,2,2 的格同构，下证的格同构，下证 a,b X1，a 1bf(a) 2f(b) 由定理由定理6.1.7可知，可知， a,b X1，如果，如果a 1b，必有，必有f(a) 2f(b) 设设f(a) 2f(b)，由定理，由定理6.1.4有有f(a)=f(a)2f(b)=f(a1b)，由于，由于f是双射，故是双射，故a1b=a，所以，所以a 1b 这就证明这就证明a 1bf(a) 2f(b) 设设 a,b X1，a 1bf(a) 2f(b)，下证，下证 f 是

24、是 X1,1,1 到到 X2,2,2 的格同构。的格同构。 设设a1b=c，则，则c 1a，c 1b，f(c)=f(a1b)，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 1a1b，即，即d 1c，故，故f(d) 2f(c)，再由偏序关系的，再由偏序关系的反对称性有反对称性有f(c)=f(d)。即。

25、即f(a1b)=f(c)=f(d)=f (a)2f(b) 类似地可以证明类似地可以证明 f(a1b)=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,b1X1X2和和a2,b2X1X2，定，定义义X1X2上的二元运算上的二元运算3和和3为：为： a1,b1 3 a2,b2 = a11a2, b12b2 a1,b1 3 a2,b2 =

26、 a11a2, b12b2 代数系统代数系统 X1X2,3,3 称为格称为格 X1,1,1 到格到格 X2,2,2 的直积。的直积。 如果如果 X1,1,1 和和 X2,2,2 是格，可以证明代数系是格，可以证明代数系统统 X1X2,3,3 也是格也是格 第六章：格和布尔代数第六章：格和布尔代数 6.2 分配格分配格【定义定义6.2.1】 设设 X, 是格，是格， X, 是是 X, 导出的代导出的代数系统，如果数系统，如果 a,b,c X有有 a(bc)=(ab)(ac) (并运算对交运算可分配并运算对交运算可分配) a(bc)=(ab)(ac) (交运算对并运算可分配交运算对并运算可分配)则

27、称则称 X, 为分配格。为分配格。 因为因为a(bc)=(ab)(ac)和和 a(bc)=(ab)(ac) 互为对偶命题，根据对偶原理，定义互为对偶命题，根据对偶原理，定义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 |

28、 x P (A)y P (A)x y 是是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 导出的

29、代数系导出的代数系统统 P (A), 实际就是代数系统实际就是代数系统 P (A), ，其中，其中是集合的并运算，是集合的并运算，是集合的交运算。而集合的并、交运是集合的交运算。而集合的并、交运算满足分配律：算满足分配律：第六章：格和布尔代数第六章：格和布尔代数 P,Q,R P (A) P(QR)=(PQ)(PR) P(QR)=(PQ)(PR) 所以，所以， P (A), 分配格。分配格。第六章：格和布尔代数第六章：格和布尔代数 【例【例6.5】 A= a,b,c,d,e ， A, 是格，其哈斯图如图是格，其哈斯图如图8.3所所示，证明示，证明 A, 不是分配格。不是分配格。 证明：证明：b(

30、cd)=be=b (bc)(bd)=aa=a b(cd)(bc)(bd) 所以，所以， A, 不是分配格。不是分配格。 本例中的格叫做钻石格，钻石格不是分配格。本例中的格叫做钻石格，钻石格不是分配格。 第六章：格和布尔代数第六章：格和布尔代数【例例6.6】设设A= a,b,c,d,e ， A, 是格，其哈斯图如图是格，其哈斯图如图8.5所示，证明所示，证明 A, 不是分配格。不是分配格。 证明证明： d(bc)=de=d (db)(dc)=ac=c d(bc)(db)(dc)所以，所以， A, 不是分配格。不是分配格。 本例中的格叫做五角格，五角格本例中的格叫做五角格，五角格也不是分配格。钻石

31、格和五角格是也不是分配格。钻石格和五角格是两个很重要的格。两个很重要的格。第六章：格和布尔代数第六章：格和布尔代数【定理定理6.2.1 】一个格是分配格的充分必要条件是该格中不一个格是分配格的充分必要条件是该格中不含有与钻石格或五角格同构的子格。含有与钻石格或五角格同构的子格。 这个定理的证明已经超过了本书的范围，故略去。这个定理的证明已经超过了本书的范围，故略去。【 推论推论1】 设设 A, 是格，如果是格，如果|A|5，则，则 A, 一定是一定是分配格。分配格。【推论推论2】 设设 A, 是格，如果是格，如果 A, 是全序集，则是全序集，则 A, 一定是分配格。一定是分配格。【例例6.7】

32、图图8.6给出了两个格的哈斯图。试证明它们都不给出了两个格的哈斯图。试证明它们都不是分配格。是分配格。 证明：证明：在图在图8.6 (a)中含有与五角格同构的子格，所以中含有与五角格同构的子格，所以不是分配格；在图不是分配格；在图8.6 (b)中含有与钻石格同构的子格，所中含有与钻石格同构的子格，所以不是分配格。以不是分配格。 第六章：格和布尔代数第六章：格和布尔代数第六章：格和布尔代数第六章：格和布尔代数【定理定理6.2.2】 设设 X, 是格，是格， X, 是格是格 X, 导出的代数系导出的代数系统。统。 X, 是分配格的充分必要条件是是分配格的充分必要条件是 a,b,c X，当，当ab=

33、ac且且ab=ac时，必有时，必有b= c 证明：证明：设设 X, 是分配格，是分配格， a,b,c X， ab=ac且且ab=ac b=b(ba)=b(ab) (吸收律和交换律吸收律和交换律) =b(ac)= (ba)(bc) (已知代入和分配律已知代入和分配律) =(ac)(bc) (交换律和已知代入交换律和已知代入) =(ab)c (分配律分配律) =(ac)c (已知条件代入已知条件代入) =c (交换律和吸收律交换律和吸收律) 设设 a,b,c X，当，当ab=ac且且ab=ac时，有时，有b=c，但，但 X, 不是分配格。由定理不是分配格。由定理6.2.1知知 X, 中必含有与钻石

34、格中必含有与钻石格或五角格同构的子格。假设或五角格同构的子格。假设 X, 含有与钻石格同构的子格，且含有与钻石格同构的子格，且此子格为此子格为 S, ，其中，其中S= u,v,x,y,z ，u为它的最大元，为它的最大元，v为它的为它的最小元。从而最小元。从而xy=u=xz，xy=v=xz，但，但yz，与已知矛盾。，与已知矛盾。第六章：格和布尔代数第六章：格和布尔代数 对五角格的情况，可类似证明。对五角格的情况，可类似证明。 例如，在图例如，在图8.6 (a)中，中，bc=g=bf且且bc=a=bf，但，但cf；在图；在图8.6 (b)中，中，bc=f= be且且bc=a= be，但，但ce。根

35、据定理根据定理6.2.2它们不是分配格。它们不是分配格。 6.3 有补格有补格 【定义定义6.3.1】 设设 X, 是格，如果是格，如果 a X， x X都有都有 a x (x a)则称则称a为格为格 X, 的全下的全下(上上)界，记为界，记为0(1)。【定理定理6.3.1】 设设 X, 是格，若格是格，若格 X, 有全下界或全上有全下界或全上界，则它们一定是惟一的。界，则它们一定是惟一的。 证明证明：用反证法。用反证法。 如果有两个全下界如果有两个全下界a和和b，a,b X。因为。因为a是全下界，所是全下界，所以以a b；又因为；又因为b是全下界，所以是全下界，所以b a。再由。再由 的反对

36、称性的反对称性有有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), 是有界格，可记为是有界格，

37、可记为 P (A),A 。在例。在例6.6中，从哈斯图中，从哈斯图(图图8.5)中可以看出，中可以看出，a是全上界，是全上界，而而e是全下界，所以是全下界，所以 A, 是有界格。是有界格。【定理定理6.3.2】 设设 X,0,1 为有界格，则为有界格，则 a X有有 a0=0，a0=a； a1=a，a1=1 证明证明：因为因为0是全下界且是全下界且a0 X，所以，所以0 a0，又因为，又因为a0 0，由，由 的反对称性有的反对称性有a0=0 显然显然a a，由于，由于1是全上界，所以有是全上界，所以有a 1，从而推出，从而推出 a a1，又因为又因为a1 a，再由，再由 的反对称性有的反对称性

38、有a1=a a0=a 和和a1=1可以类似地证明。可以类似地证明。第六章：格和布尔代数第六章：格和布尔代数 设设 X,0,1 为有界格，为有界格，a X有有a0=0，因为格满足，因为格满足交换律，所以交换律，所以0a=0，这说明，这说明0是交运算的零元；同样的道是交运算的零元；同样的道理，理，0是并运算的幺元，而是并运算的幺元，而1是交运算的幺元和并运算的零元。是交运算的幺元和并运算的零元。 【定义定义6.3.3】 设设 X,0,1 为有界格，如果对于为有界格，如果对于 a X， b X，使得，使得ab=1且且ab=0，则称，则称b是是a的补元。的补元。 如果如果b是是a的补元，从定义的补元，

39、从定义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的

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

41、章：格和布尔代数第六章：格和布尔代数【定理定理6.3.3】设设 X,0,1 为有界分配格，如果对于为有界分配格，如果对于a X，a存在补元存在补元b，则，则b是是a的惟一补元。的惟一补元。 证明证明：因为因为b是是a的补元，所以有的补元，所以有 ab=1，ab=0 设设c X，c是是a的另一个补元，同样也有的另一个补元，同样也有ac=1，ac=0 从而有从而有 ab= ac，ab= ac 由于由于 X,0,1 为分配格，根据定理为分配格，根据定理6.6.6必有必有b=c，即即a的补元惟一。的补元惟一。【定义定义6.3.4】设设 X,0,1 为有界格，如果为有界格，如果 a X，在，在X中都有中

42、都有a的补元存在，则称的补元存在，则称 X,0,1 为有补格为有补格 例如，图例如，图8.8是三个有界格的哈斯图，由于每一个元是三个有界格的哈斯图，由于每一个元素至少有一个补元，所以它们都是有补格。素至少有一个补元，所以它们都是有补格。 第六章：格和布尔代数第六章：格和布尔代数第六章：格和布尔代数第六章：格和布尔代数6.4 布尔代数布尔代数 【定义定义6.4.1】 有补分配格称为布尔格。有补分配格称为布尔格。 在布尔格中每一个元素都有补元。因为有补格一定是有界在布尔格中每一个元素都有补元。因为有补格一定是有界格，所以布尔格一定是有界分配格，根据定理格，所以布尔格一定是有界分配格，根据定理6.3

43、.3，布尔格中，布尔格中的每一个元素的补元存在且惟一。于是可以将求补元的运算看的每一个元素的补元存在且惟一。于是可以将求补元的运算看作一元运算且把作一元运算且把a的补元记为的补元记为a。【定义定义6.4.2】 设设 X, 是布尔格，是布尔格， X, 是格是格 X, 导出导出的代数系统。称代数系统的代数系统。称代数系统 X, 为布尔代数。为布尔代数。 在在6.1节中证明了节中证明了 P (A), R 是格，其中是格，其中 A= a,b 。 P (A), 是是 P (A), R 导出的代数系统，其中导出的代数系统，其中和和是集合是集合并运算和交运算。以后又进一步说明了并运算和交运算。以后又进一步说

44、明了 P (A), 是分配格和有界格，是分配格和有界格，是全下界、是全下界、A是全上界。从而是全上界。从而 P(A), 是有界分配格。令是有界分配格。令A为全集，为全集， T P (A)，T的补集的补集T=AT P (A)，满足，满足TT= A和和TT=，所以，所以T的补元的补元T=T。根据定义。根据定义6.4.2， P (A), 是布尔代数。是布尔代数。 第六章：格和布尔代数第六章：格和布尔代数 可以证明，当可以证明，当A为任意集合时，为任意集合时， P (A), 也是布尔也是布尔代数。称为集合代数。集合代数是布尔代数的一个具体模型。代数。称为集合代数。集合代数是布尔代数的一个具体模型。 布

45、尔代数一定是格。根据定理布尔代数一定是格。根据定理8.1.1，布尔代数中的两个，布尔代数中的两个二元运算满足交换律、结合律、幂等律和吸收律。此外，布二元运算满足交换律、结合律、幂等律和吸收律。此外，布尔代数还有下面的性质：尔代数还有下面的性质：【定理定理6.4.1】 设设 X, 为布尔代数，为布尔代数， a,b X，必有，必有 (a)=a (ab)= ab (ab)= ab 证明：证明： a是是a的补元，的补元，a也是也是a的补元，由布尔代数中的补元，由布尔代数中补元的惟一性有补元的惟一性有(a)=a第六章：格和布尔代数第六章：格和布尔代数 (ab)(ab)=(ab)a)(ab)b) =(b(

46、aa)(a(bb) =(b1)(a1)=11=1 (ab)(ab)=(a(ab)(b(ab) =(aa)b)(bb)a) =(0b)(0a)=00=0所以所以 (ab)= ab 同理可证同理可证 (ab)= ab 定理定理6.4.1中的中的称为双重否定律，称为双重否定律，和和称为德摩根称为德摩根律。布尔代数满足双重否定律和德摩根律。律。布尔代数满足双重否定律和德摩根律。第六章：格和布尔代数第六章：格和布尔代数【定理定理6.4.2】 设设 X,* *, , 是代数系统，其中是代数系统，其中* *和和 都是二都是二元运算，元运算，是一元运算。是一元运算。 X,* *, , 是布尔代数的充分必要是布

47、尔代数的充分必要条件是：条件是：* *和和 在在X上封闭且满足交换律。上封闭且满足交换律。 * *和和 满足分配律满足分配律(满足满足* *对对 的分配律和的分配律和 对对* *的分的分配律配律)。 X中存在运算中存在运算* *的幺元和运算的幺元和运算 的幺元。设运算的幺元。设运算* *的的幺元为幺元为0，运算，运算 的幺元为的幺元为1。即。即 a X，有，有a* *0=a，a 1=a a X， a X，使得，使得a* *a=1，a a=0 由于篇幅的限制，证明从略。由于篇幅的限制，证明从略。 定理定理6.4.2给出的四个条件可以作为布尔代数的等价定给出的四个条件可以作为布尔代数的等价定义。义

48、。 布尔代数布尔代数 X,* *, , 也可以表示成为也可以表示成为 X,* *, ,0,1 ，其中其中0是运算是运算* *的幺元，的幺元，1是运算是运算 的幺元。的幺元。第六章：格和布尔代数第六章：格和布尔代数【例【例6.9】设设P是所有命题构成的集合，是所有命题构成的集合，,和和分别是命题分别是命题的析取、合取和否定联结词。证明代数系统的析取、合取和否定联结词。证明代数系统 P, 是是布尔代数。布尔代数。 证明证明：根据第根据第1章的内容，章的内容，和和在在P上封闭且满足交上封闭且满足交换律、分配律。命题常元换律、分配律。命题常元0(假假)和和1(真真)是集合是集合P的元素，满足的元素，满

49、足 q P，q0=q，q1=q。 q P，q P，满足，满足qq=1，qq=0。 根据定理根据定理6.4.2， P, 是布尔代数。是布尔代数。 例例6.9中的布尔代数中的布尔代数 P, 叫做命题代数，它是布叫做命题代数，它是布尔代数的又一个模型。尔代数的又一个模型。 【定义定义6.4.3 】 设设 X, 0,1 是布尔代数，是布尔代数，B 是是X的非的非空子集，若空子集，若0,1 B且且 B, 0,1 也是布尔代数。则称也是布尔代数。则称 B, 0,1 是是 X, , 0,1 子布尔代数。子布尔代数。 第六章：格和布尔代数第六章：格和布尔代数【定理定理6.4.3】 设设 X,0,1 是布尔代数

50、，是布尔代数，B是是X的非空的非空子集，若子集，若0,1 B且运算且运算,在在B上封闭，则上封闭，则 B, 0,1 是是 X, 0,1 子布尔代数子布尔代数 证明证明： a,b B，因为，因为 B X，所以，所以 a,b X。又因为。又因为 X,0,1 是布尔代数，故是布尔代数，故 ab=ba，ab=ba 类似类似可以证明可以证明* *和和 满足分配律。满足分配律。 已知已知0,1 B， a B X，a X，有，有a0=a和和a1=a a B，由，由在在B上封闭知有上封闭知有a B，使得，使得aa=1，aa=0 根据定理根据定理 6.4.2， B, 0,1 是布尔代数，它是是布尔代数，它是 X

51、,0,1 的子布尔代数。的子布尔代数。 为了方便，以下将为了方便，以下将x y且且xy记为记为x y。 第六章：格和布尔代数第六章：格和布尔代数【例例4.10】设设 X, 0,1 是布尔代数，是布尔代数，a,b X，a b，令令S= x| x X，a x且且x b 试证明试证明 S,0,1 是是 X,0,1 的子布尔代数。的子布尔代数。 证明证明：由于由于a a且且a b，所以，所以a S，S是是X的非空子集，的非空子集，由由S的定义知的定义知 a是是S的全下界，的全下界，b是是S的全上界。的全上界。 x, y S， a x且且x b，a y且且y b a xy且且xy b，a xy且且xy

52、b从而从而xy S且且xy S，即运算，即运算和和在在S上封闭。上封闭。 x S，令，令y=(ax)b 由于由于a ax，a b，故，故a (ax)b； 又由于又由于(ax)b b，所以，所以y=(ax)b S，又，又 xy=x(ax)b) =x(ab)(xb) (分配律分配律) =x(a(xb) (a bab=a) = (xa)(xb) (结合律结合律)第六章：格和布尔代数第六章：格和布尔代数 = x(xb) (a xax=x) =(xx)(xb) (分配律分配律) =1(xb) (x是是x的补元的补元) =xb (1是是的幺元的幺元) =b (x b xb=b) xy=x(ax)b) =(

53、xb)(ax) (交换律和结合律交换律和结合律) =x(ax) (由定理由定理8.1.4，x bxb=x) =(xa)(xx) (分配律分配律) =(xa)0 (x是是x的补元的补元) =(xa) (0是是的幺元的幺元) =a (由定理由定理8.1.4，a xax=a)所以所以x=y S，一元运算，一元运算在在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和

54、和2都是二元运算，都是二元运算，和和是一元运算，是一元运算， 0和和1 是是X1的全下界和全上界，的全下界和全上界， ,E是是X2的全的全下界和全上界。下界和全上界。f是从是从X1到到X2的一个映射，对任意的的一个映射，对任意的a,b X1有有 f (a1b)=f (a)2f (b) f (a1b)=f (a)2 f (b) f (a)=(f (a)则称则称f是布尔代数是布尔代数 X1,1,1,0,1 到到 X2,2,2, ,E 的的同态，简称布尔代数同态。如果同态，简称布尔代数同态。如果f是单射、满射和双射，是单射、满射和双射，分别称分别称f是布尔代数单同态、布尔代数满同态和布尔代数是布尔代

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

56、子；在在(c)中，中，a,b是原子是原子。【定理定理6.4.4】 设设 X, 是格，具有全下界是格，具有全下界0，a和和b是原子，是原子，如果如果ab，则，则ab=0。 证明证明：设设ab0，0 ab a且且0 ab b，因为，因为a是是原子，所以原子，所以ab=a。同样的道理。同样的道理ab=b。于是，。于是，a=ab=b。与假设矛盾。与假设矛盾。 在图在图8.10的的(b)中，中，ab=0，ac0，bc=0；在图；在图8.10的的(c)中，中，ab=0。 设设 X, 是格，如果集合是格，如果集合X是有限集，则称是有限集，则称 X, 是有是有限格。限格。 【定理定理6.4.5】 设设 X,

57、是有限格，具有全下界是有限格，具有全下界0，则，则 b X且且b0，至少存在一个原子，至少存在一个原子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

58、.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,b X，则，则ab=0当且仅当当且仅当a b。 证明：证明：设设ab=0，由，由0b=b，有，有 b=0b=(ab)b=(ab)(bb)=(ab)1=ab由前面的定理知，由前面的定理知，a b。 设设a b，由于，由于b b， 因有因有

59、ab bb，而，而bb=0，所以，所以ab 0。又因为。又因为0 a且且0 b，故有，故有0 ab。由由 的反对称性知的反对称性知ab=0。 第六章：格和布尔代数第六章：格和布尔代数【引理引理6.4.2】设设 X, 是有限布尔代数，是有限布尔代数，0是全下界，是全下界，如果如果 b X且且b0，a1,a2,ak是是X中满足中满足aj b(j=1,k)的所的所有原子，则有原子，则b=a1a2ak 证明证明：因为：因为aj b(j=1,k)，所以，所以a1a2ak b 再证再证b a1a2ak，根据引理，根据引理8.2.1，只需证明，只需证明 b(a1a2ak)=0。 用反证法。设用反证法。设b(

60、a1a2ak)0 由定理由定理6.4.5，至少存在一个原子，至少存在一个原子a，使得，使得 a b(a1a2ak)又因为又因为b(a1a2ak) b和和 b(a1a2ak) (a1a2ak) 由由 的传递性可得的传递性可得a b和和a (a1a2ak) 因为因为a是原子且满足是原子且满足a b，所以，所以a必是原子必是原子a1,a2, ak中中的一个，因此的一个，因此第六章：格和布尔代数第六章：格和布尔代数 a a1a2ak于是有于是有 a (a1a2ak)(a1a2ak)=0即即 a 0 这与这与a是原子相矛盾。所以是原子相矛盾。所以b(a1a2ak)0，根据引理根据引理8.2.1有有 b