第09章格与布尔代数优秀课件.ppt

《第09章格与布尔代数优秀课件.ppt》由会员分享，可在线阅读，更多相关《第09章格与布尔代数优秀课件.ppt（70页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第09章格与布尔代数章格与布尔代数第1页，本讲稿共70页9.1 格格1格作为偏序集定定定定义义义义9.1.19.1.1 设设设设是是是是一一一一个个个个偏偏偏偏序序序序集集集集，若若若若对对对对任任任任意意意意a,b,a,b,L L，存存存存在在在在glba,bglba,b和和和和luba,bluba,b，则则则则称称称称为为为为格格格格，并并并并记记记记为为为为a*b=glba,ba*b=glba,b，a a b=luba,bb=luba,b，称称称称 和和和和 分分分分别别别别为为为为L L上上上上的的的的交交交交（或或或或积积积积）和和和和并并并并（或或或或和和和和）运运运运算算算算。

2、称称称称L,*为为为为所所所所诱诱诱诱导导导导的的的的代代代代数数数数结结结结构构构构的的的的格格格格。若若若若L L是有限集合，称是有限集合，称是有限集合，称是有限集合，称为有限格。为有限格。为有限格。为有限格。第2页，本讲稿共70页格的对偶性原理是成立的：格的对偶性原理是成立的：格的对偶性原理是成立的：格的对偶性原理是成立的：令令令令是偏序集，且是偏序集，且是偏序集，且是偏序集，且是其对偶的偏是其对偶的偏是其对偶的偏是其对偶的偏序集。若序集。若序集。若序集。若是格，则是格，则是格，则是格，则也是格，反之亦也是格，反之亦也是格，反之亦也是格，反之亦然。这是因为，对于然。这是因为，对于然。这是

3、因为，对于然。这是因为，对于L L中任意中任意中任意中任意a a和和和和b b，中中中中luba,bluba,b等同于等同于等同于等同于中中中中glb a,bglb a,b，中中中中glba,bglba,b等同于等同于等同于等同于中的中的中的中的luba,bluba,b。若。若。若。若L L是有限是有限是有限是有限集，这些性质易从偏序集及其对偶的哈斯图得集，这些性质易从偏序集及其对偶的哈斯图得集，这些性质易从偏序集及其对偶的哈斯图得集，这些性质易从偏序集及其对偶的哈斯图得到验证。到验证。到验证。到验证。第3页，本讲稿共70页从上讨论中，可知两格互为对偶。互为对从上讨论中，可知两格互为对偶。互为

4、对从上讨论中，可知两格互为对偶。互为对从上讨论中，可知两格互为对偶。互为对偶的两个偶的两个偶的两个偶的两个和和和和有着密切关系，即格有着密切关系，即格有着密切关系，即格有着密切关系，即格中交运算中交运算中交运算中交运算 正是格正是格正是格正是格中的并运算中的并运算中的并运算中的并运算 ，而，而，而，而格格格格中的并运算中的并运算中的并运算中的并运算 正是格正是格正是格正是格中的交运算中的交运算中的交运算中的交运算 。因此，给出关于格一般性质的任何有效命题，因此，给出关于格一般性质的任何有效命题，因此，给出关于格一般性质的任何有效命题，因此，给出关于格一般性质的任何有效命题，把关系把关系把关系把

5、关系 换成换成换成换成（或者（或者（或者（或者 换成换成换成换成），交换成并，并），交换成并，并），交换成并，并），交换成并，并换成交，可得到另一个有效命题，这就是关于换成交，可得到另一个有效命题，这就是关于换成交，可得到另一个有效命题，这就是关于换成交，可得到另一个有效命题，这就是关于格的对偶性原理。格的对偶性原理。格的对偶性原理。格的对偶性原理。定义定义定义定义9.1.29.1.2 设设设设是格，且是格，且是格，且是格，且S S L L。若对任。若对任。若对任。若对任意意意意a,ba,b S S，有，有，有，有a*ba*b S S和和和和a a b b S S，则称，则称，则称，则称是是是

6、是格格格格的子格。的子格。的子格。的子格。第4页，本讲稿共70页2格的基本性质在在在在证证证证明明明明格格格格的的的的性性性性质质质质前前前前，回回回回忆忆忆忆一一一一下下下下a*ba*b和和和和a a b b的的的的真正含义是有好处的。真正含义是有好处的。真正含义是有好处的。真正含义是有好处的。a*baa*ba和和和和a a bbbb，则则则则表表表表明明明明a*ba*b是是是是a a和和和和b b的的的的下下下下界。界。界。界。若若若若caca和和和和cbcb，则则则则ca*bca*b，这这这这表表表表明明明明a*ba*b是是是是a a和和和和b b的最大下界。的最大下界。的最大下界。的最

7、大下界。aaaa b b和和和和baba b b，则则则则表表表表明明明明a a b b是是是是a a和和和和b b的的的的上界。上界。上界。上界。若若若若acac，且且且且bcbc，则则则则a a bcbc，这这这这表表表表明明明明a a b b是是是是a a和和和和b b的最小上界。的最小上界。的最小上界。的最小上界。第5页，本讲稿共70页定理定理定理定理9.1.19.1.1 设设设设是格，对任意是格，对任意是格，对任意是格，对任意a,ba,b L L，有有有有 a a b=bb=babab a*b=a a*b=aabab a*b=a a*b=aa a b=bb=b亦即亦即亦即亦即 aba

8、ba a b=bb=ba*b=aa*b=a第6页，本讲稿共70页定定定定理理理理9.1.29.1.2 设设设设是是是是格格格格，对对对对任任任任意意意意a,ba,b L L，有有有有 a*b=a,aa*b=a,a a=aa=a。（幂等律）（幂等律）（幂等律）（幂等律）a*b=b*a,aa*b=b*a,a b=bb=b a a。（交换律）（交换律）（交换律）（交换律）a*(b*c)=(a*b)*ca*(b*c)=(a*b)*ca a (b(b c)=(ac)=(a b)b)c c （结合律）（结合律）（结合律）（结合律）a*(aa*(a b)=ab)=aa a (a*b)=a (a*b)=a （

9、吸收律）（吸收律）（吸收律）（吸收律）第7页，本讲稿共70页定定定定理理理理9.1.39.1.3 设设设设是是是是格格格格，对对对对任任任任意意意意a,b,ca,b,c L L，有，有，有，有若若若若abab和和和和cdcd，则，则，则，则a*cb*da*cb*d，a a cbcb d d。若若若若abab，则，则，则，则a*cb*ca*cb*c，a a cbcb c c。caca和和和和cb ca*bcb ca*bacac和和和和bc abc a bcbc第8页，本讲稿共70页定定定定 理理理理 9.1.49.1.4 设设设设 是是是是 格格格格，对对对对 任任任任 意意意意 的的的的a,b

10、,ca,b,c L L，有，有，有，有a a (b*c)(a(b*c)(a b)*(ab)*(a c)c)(a*b)(a*b)(a*c)a*(b(a*c)a*(b c)c)通常称上二式为格中分配不等式。通常称上二式为格中分配不等式。通常称上二式为格中分配不等式。通常称上二式为格中分配不等式。第9页，本讲稿共70页定定定定 理理理理 9.1.59.1.5 设设设设 是是是是 格格格格，对对对对 任任任任 意意意意 的的的的a,b,ca,b,c L L，有，有，有，有acaca a (b*c)(a(b*c)(a b)*cb)*c推推推推论论论论：在在在在格格格格中中中中，对对对对任任任任意意意意的

11、的的的a,b,ca,b,c L L，有有有有(a*b)(a*b)(a*c)a*(b(a*c)a*(b (a*c)(a*c)a a (b*(a(b*(a c)(ac)(a b)*(ab)*(a c)c)第10页，本讲稿共70页3特殊的格定定定定义义义义9.1.39.1.3 设设设设是是是是格格格格，若若若若L L中中中中有有有有最最最最大大大大元元元元和和和和最最最最小小小小元元元元，则则则则称称称称为为为为有有有有界界界界格格格格。一一一一般般般般把把把把格格格格中中中中最最最最大元记为大元记为大元记为大元记为1 1，最小元记为，最小元记为，最小元记为，最小元记为0 0。由定义可知，对任意由定

12、义可知，对任意由定义可知，对任意由定义可知，对任意a a L L，有，有，有，有0a10a1a*0=0,aa*0=0,a 0=a0=aa*1=a,aa*1=a,a 1=11=1第11页，本讲稿共70页定理定理9.1.6 设设设设是有限格，其中是有限格，其中是有限格，其中是有限格，其中L=a1 1,a,a2,an ，则，则是有界格。是有界格。第12页，本讲稿共70页定义定义定义定义9.1.49.1.4 设设设设是有界格，对于是有界格，对于是有界格，对于是有界格，对于a a L L，存在存在存在存在b b L L，使得，使得，使得，使得a*b=0a*b=0，a a b=1b=1称称称称b b为为为

13、为a a的补元，记为的补元，记为的补元，记为的补元，记为aa。由定义可知，若由定义可知，若由定义可知，若由定义可知，若b b是是是是a a的补元，则的补元，则的补元，则的补元，则a a也是也是也是也是b b的的的的补元，即补元，即补元，即补元，即a a与与与与b b互为补元。互为补元。互为补元。互为补元。显然，显然，显然，显然，0=10=1和和和和1=01=0，且易证补元是唯一的。，且易证补元是唯一的。，且易证补元是唯一的。，且易证补元是唯一的。一般说来，一个元素可以有其补元，未必一般说来，一个元素可以有其补元，未必一般说来，一个元素可以有其补元，未必一般说来，一个元素可以有其补元，未必唯一，

14、也可能无补元。唯一，也可能无补元。唯一，也可能无补元。唯一，也可能无补元。第13页，本讲稿共70页定定定定 义义义义 9.1.59.1.5 设设设设 是是是是 格格格格，对对对对 任任任任 意意意意 的的的的a,b,ca,b,c L L，有，有，有，有 a*(ba*(b c)=(a*b)c)=(a*b)(a*c)(a*c)a a (b*c)=(a(b*c)=(a b)*(ab)*(a c)c)则则则则称称称称为为为为分分分分配配配配格格格格，称称称称和和和和为为为为格格格格中中中中分分分分配配配配律。律。律。律。第14页，本讲稿共70页定义定义定义定义9.1.69.1.6 设设设设是格，对任意

15、的是格，对任意的是格，对任意的是格，对任意的a,b,ca,b,c L L，有，有，有，有acaca a (b*c)=(a(b*c)=(a b)*cb)*c称称称称为模格。为模格。为模格。为模格。定理定理定理定理9.1.79.1.7 分配格是模格分配格是模格分配格是模格分配格是模格定理定理定理定理9.1.89.1.8 每个链都是分配格。每个链都是分配格。每个链都是分配格。每个链都是分配格。第15页，本讲稿共70页定定定定理理理理9.1.99.1.9 一一一一个个个个格格格格为为为为分分分分配配配配格格格格，当当当当且且且且仅仅仅仅当当当当它它它它不不不不含有任何子格与这两个五元素格中任一个同构。

16、含有任何子格与这两个五元素格中任一个同构。含有任何子格与这两个五元素格中任一个同构。含有任何子格与这两个五元素格中任一个同构。定定定定理理理理9.1.109.1.10 设设设设是是是是分分分分配配配配格格格格，对对对对任任任任意意意意a,b,ca,b,c L L，有，有，有，有(a*b=a*c)(a*b=a*c)且且且且(a(a b=ab=a c)c)b=cb=c定定定定理理理理9.1.119.1.11 设设设设是是是是有有有有界界界界分分分分配配配配格格格格，若若若若a a L L，且补元存在，则其补元是唯一的。，且补元存在，则其补元是唯一的。，且补元存在，则其补元是唯一的。，且补元存在，则

17、其补元是唯一的。第16页，本讲稿共70页定定定定义义义义9.1.79.1.7 设设设设是是是是格格格格，若若若若L L中中中中每每每每个个个个元元元元素素素素至少有一补元，则称至少有一补元，则称至少有一补元，则称至少有一补元，则称为有补格。为有补格。为有补格。为有补格。由由由由于于于于补补补补元元元元的的的的定定定定义义义义是是是是在在在在有有有有界界界界格格格格中中中中给给给给出出出出的的的的，可可可可知，有补格一定是有界格。知，有补格一定是有界格。知，有补格一定是有界格。知，有补格一定是有界格。定定定定义义义义9.1.89.1.8 若若若若一一一一格格格格既既既既是是是是有有有有补补补补又

18、又又又是是是是分分分分配配配配的的的的，则则则则称该格为有补分配格，或布尔格，或布尔代数。称该格为有补分配格，或布尔格，或布尔代数。称该格为有补分配格，或布尔格，或布尔代数。称该格为有补分配格，或布尔格，或布尔代数。第17页，本讲稿共70页定定定定理理理理9.1.129.1.12 设设设设是是是是有有有有补补补补分分分分配配配配格格格格，若若若若任任任任意意意意元素元素元素元素a a L L，则，则，则，则a a的补元的补元的补元的补元aa是唯一的。是唯一的。是唯一的。是唯一的。该该该该定定定定理理理理9.1.119.1.11的的的的直直直直接接接接推推推推论论论论，因因因因为为为为有有有有补

19、补补补分分分分配配配配格格格格当然是有界分配格。当然是有界分配格。当然是有界分配格。当然是有界分配格。由由由由于于于于有有有有补补补补分分分分配配配配格格格格中中中中，每每每每个个个个元元元元素素素素a a都都都都有有有有唯唯唯唯一一一一的的的的补补补补元元元元aa，因因因因此此此此可可可可在在在在L L上上上上定定定定义义义义一一一一个个个个一一一一元元元元运运运运算算算算补补补补运运运运算算算算“”“”。这这这这样样样样，有有有有补补补补分分分分配配配配格格格格可可可可看看看看作作作作具具具具有有有有两两两两个个个个二二二二元元元元运运运运算算算算和和和和一一一一个个个个一一一一元元元元运

20、运运运算算算算的的的的代代代代数数数数结结结结构构构构，习习习习惯惯惯惯上上上上称它为布尔代数，记为称它为布尔代数，记为称它为布尔代数，记为称它为布尔代数，记为B,*,0,1，其中，其中，其中，其中B=LB=L。第18页，本讲稿共70页定理定理定理定理9.1.139.1.13 设设设设是有补分配格，对任意是有补分配格，对任意是有补分配格，对任意是有补分配格，对任意a,ba,b L L，则，则，则，则 (a)=a(a)=a(a*b)=a(a*b)=a bb(a(a b)=a*bb)=a*b后两式称为格中德后两式称为格中德后两式称为格中德后两式称为格中德 摩根律。摩根律。摩根律。摩根律。第19页，

21、本讲稿共70页定定定定理理理理9.1.149.1.14 设设设设是是是是有有有有补补补补分分分分配配配配格格格格，对对对对任任任任意意意意a,ba,b L L，有，有，有，有ababa*b=0a*b=0aa b=1b=1格格格格同同同同态态态态，格格格格直直直直积积积积等等等等概概概概念念念念可可可可以以以以接接接接下下下下来来来来定定定定义义义义和和和和研研研研究究究究，但但但但这这这这里里里里不不不不打打打打算算算算这这这这样样样样做做做做，因因因因为为为为如如如如此此此此进进进进行行行行会会会会相相相相对对对对较较较较繁繁繁繁，而而而而是是是是将将将将格格格格作作作作为为为为一一一一个个

22、个个代代代代数数数数结结结结构构构构而而而而引引引引入入入入它们。它们。它们。它们。第20页，本讲稿共70页4格是代数结构能能能能自自自自然然然然地地地地把把把把代代代代数数数数结结结结构构构构中中中中有有有有关关关关子子子子代代代代数数数数、同同同同态态态态、积代数等概念，引入到格中。积代数等概念，引入到格中。积代数等概念，引入到格中。积代数等概念，引入到格中。定定定定义义义义9.1.99.1.9 设设设设L,*是是是是一一一一代代代代数数数数结结结结构构构构，其其其其中中中中 和和和和*是是是是L L上上上上满满满满足足足足交交交交换换换换律律律律、结结结结合合合合律律律律和和和和吸吸吸吸

23、收收收收律律律律的的的的二二二二元运算，且对任意元运算，且对任意元运算，且对任意元运算，且对任意a,ba,b L L，定义关系，定义关系，定义关系，定义关系 如下：如下：如下：如下：ababa*b=aa*b=a则则则则 是是是是 格格格格，称称称称 为为为为 代代代代 数数数数 系系系系 统统统统L,*所诱导的偏序集确立的格。所诱导的偏序集确立的格。所诱导的偏序集确立的格。所诱导的偏序集确立的格。第21页，本讲稿共70页定定定定 义义义义 9.1.109.1.10 设设设设 L,*和和和和 S,是是是是 格格格格。存在函数存在函数存在函数存在函数f:Lf:LS S，若对任意，若对任意，若对任意

24、，若对任意a,ba,b L L，有，有，有，有f(af(a b)=f(a)b)=f(a)f(b)f(b)，f(a*b)=f(a)f(a*b)=f(a)f(b)f(b)则称则称则称则称f f是从是从是从是从L,*到到到到S,的格同态。的格同态。的格同态。的格同态。下述定理说明格同态是保序的。下述定理说明格同态是保序的。下述定理说明格同态是保序的。下述定理说明格同态是保序的。定定定定理理理理9.1.159.1.15 设设设设L,*和和和和S,是是是是格格格格，而而而而L,和和和和分分分分别别别别是是是是给给给给定定定定两两两两个个个个格格格格所所所所诱诱诱诱导导导导的的的的偏偏偏偏序序序序集集集集

25、确确确确立立立立的的的的格格格格。若若若若f:Lf:LS S是是是是格格格格同同同同态态态态，则则则则对对对对任任任任意意意意a,ba,b L L，且，且，且，且abab，必有，必有，必有，必有f(a)f(b)f(a)f(b)。第22页，本讲稿共70页在在在在定定定定义义义义9.1.109.1.10中中中中，若若若若f f是是是是双双双双射射射射函函函函数数数数，则则则则称称称称f f是是是是格格格格同同同同构构构构。或或或或称称称称L,*和和和和S,两两两两个个个个格格格格同同同同构构构构。由由由由于于于于同同同同构构构构是是是是相相相相互互互互的的的的，又又又又是是是是保保保保序序序序的的

26、的的，故故故故对对对对任任任任意意意意a,ba,b L L，有，有，有，有ababf(a)f(b)f(a)f(b)和和和和f(a)f(b)f(a)f(b)abab这这这这表表表表明明明明同同同同构构构构的的的的两两两两个个个个格格格格的的的的哈哈哈哈斯斯斯斯图图图图是是是是一一一一样样样样的的的的，只是各结点的标记不同而已。只是各结点的标记不同而已。只是各结点的标记不同而已。只是各结点的标记不同而已。第23页，本讲稿共70页定定定定义义义义9.1.119.1.11 设设设设L,*和和和和S,是是是是格格格格，定定定定义一个代数结构义一个代数结构义一个代数结构义一个代数结构LS,+,o如下：如下

27、：如下：如下：对任意对任意对任意对任意a，a L L S S，有，有，有，有a+=aoo=称称称称LS,+,o是是是是格格格格L,*和和和和S,的的的的直直直直积。积。积。积。第24页，本讲稿共70页两个格的直积也是格。这是因为在两个格的直积也是格。这是因为在两个格的直积也是格。这是因为在两个格的直积也是格。这是因为在L L S S上，上，上，上，运算运算运算运算o o和和和和+是封闭的，且满足交换律、结合律和是封闭的，且满足交换律、结合律和是封闭的，且满足交换律、结合律和是封闭的，且满足交换律、结合律和吸收律。吸收律。吸收律。吸收律。格积的阶等于两个格的阶乘积。由于格积的阶等于两个格的阶乘积

28、。由于格积的阶等于两个格的阶乘积。由于格积的阶等于两个格的阶乘积。由于LS,o,+是一个格，故又可以与另一个格作直是一个格，故又可以与另一个格作直是一个格，故又可以与另一个格作直是一个格，故又可以与另一个格作直积，这样，利用格的直积可用较小阶的格构造积，这样，利用格的直积可用较小阶的格构造积，这样，利用格的直积可用较小阶的格构造积，这样，利用格的直积可用较小阶的格构造出阶越来越大的格。但反之，较大阶的格，并出阶越来越大的格。但反之，较大阶的格，并出阶越来越大的格。但反之，较大阶的格，并出阶越来越大的格。但反之，较大阶的格，并不都能表示成较小阶的格直积。不都能表示成较小阶的格直积。不都能表示成较

29、小阶的格直积。不都能表示成较小阶的格直积。第25页，本讲稿共70页9.2 布尔代数布尔代数前前前前已已已已指指指指出出出出，布布布布尔尔尔尔代代代代数数数数是是是是有有有有补补补补分分分分配配配配格格格格，常常常常记记记记为为为为B,。对任意。对任意a,b,ca,b,c B B，有，有第26页，本讲稿共70页 B,*是格，且是格，且是格，且是格，且 为为为为B B上由上由上由上由 或或或或*所定所定所定所定义的偏序关系，满足义的偏序关系，满足义的偏序关系，满足义的偏序关系，满足(L-1)a(L-1)a b=luba,bb=luba,b，a*b=glba,ba*b=glba,b(L-2)ab(L

30、-2)aba a b=bb=ba*b=aa*b=a(L-3)a(L-3)a a=aa=a，a*a=a a*a=a （等幂律）（等幂律）（等幂律）（等幂律）(L-4)a(L-4)a b=bb=b a a，a*b=b*a a*b=b*a （交换律）（交换律）（交换律）（交换律）(L-5)(a(L-5)(a b)b)c=ac=a (b(b c)c)，(a*b)*c=a*(b*c)(a*b)*c=a*(b*c)（结合律）（结合律）（结合律）（结合律）(L-6)a(L-6)a (a*b)=a(a*b)=a，a*(aa*(a b)=a b)=a （吸收律）（吸收律）（吸收律）（吸收律）第27页，本讲稿共7

31、0页 B,*是分配格，满足是分配格，满足是分配格，满足是分配格，满足(D-1)a(D-1)a (b*c)=(a(b*c)=(a b)*(ab)*(a c)c)，a*(ba*(b c)=(a*b)c)=(a*b)(a*c)(a*c)（分配律）（分配律）（分配律）（分配律）(D-2)(a(D-2)(a b=ab=a c)c)(a*b=a*c)(a*b=a*c)b=cb=c(D-3)(a(D-3)(a b)*(bb)*(b c)*(cc)*(c a)=(a*b)a)=(a*b)(b*c)(b*c)(c*a)(c*a)第28页，本讲稿共70页 B,*,0,1是有界格，满足是有界格，满足是有界格，满足是

32、有界格，满足(B-1)0a1(B-1)0a1(B-2)a(B-2)a 0=a0=a，a*a=a a*a=a （幺律）（幺律）（幺律）（幺律）(B-3)a(B-3)a 1=11=1，a*0=0 a*0=0 （零律）（零律）（零律）（零律）B,*,0,1是有补格，满足是有补格，满足是有补格，满足是有补格，满足(C-1)a(C-1)a a=1a=1，a*a=0 a*a=0 （互补律）（互补律）（互补律）（互补律）(C-2)1=0(C-2)1=0，0=10=1第29页，本讲稿共70页 B,*,0,1是有补分配格，满足是有补分配格，满足是有补分配格，满足是有补分配格，满足(CD-1)(a(CD-1)(a

33、 b)=a*ab)=a*a，(a*b)=a(a*b)=a b b （德（德（德（德 摩根律）摩根律）摩根律）摩根律）(CD-2)ab(CD-2)abaa b=1b=1a*b=0a*b=0baba注意，上述公式并非都是独立的，可从中注意，上述公式并非都是独立的，可从中注意，上述公式并非都是独立的，可从中注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余选出一些公式作为基本公式，用它们推出其余选出一些公式作为基本公式，用它们推出其余选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。的公式，而且可以用基本公式定义布尔代数。的公式，而且可以用基本

34、公式定义布尔代数。的公式，而且可以用基本公式定义布尔代数。第30页，本讲稿共70页定义定义定义定义9.2.19.2.1 设设设设B,*,是一代数结构，其是一代数结构，其是一代数结构，其是一代数结构，其中中中中 和和和和*是是是是B B上的二元运算，上的二元运算，上的二元运算，上的二元运算，是是是是B B上的一元运算。上的一元运算。上的一元运算。上的一元运算。0,10,1 B B。若对任意。若对任意。若对任意。若对任意a,ba,b B B，有，有，有，有 a a b=bb=b a a，a*b=b*a a*b=b*a （交换律）（交换律）（交换律）（交换律）a a (b*c)=(a(b*c)=(a

35、 b)*(ab)*(a c)c)，a*(ba*(b c)=(a*b)c)=(a*b)(a*c)(a*c)（分配律）（分配律）（分配律）（分配律）a a 0=a0=a，a*1=a a*1=a （幺律）（幺律）（幺律）（幺律）a a a=1a=1，a*a=0 a*a=0 （互补律）（互补律）（互补律）（互补律）第31页，本讲稿共70页则称则称则称则称B,*,是布尔代数，称是布尔代数，称是布尔代数，称是布尔代数，称 、*和和和和 分别是分别是分别是分别是B B上的并、交和补运算，上的并、交和补运算，上的并、交和补运算，上的并、交和补运算，0 0和和和和1 1分别称为分别称为分别称为分别称为 和和和和

36、*的零元和幺元。的零元和幺元。的零元和幺元。的零元和幺元。代代代代数数数数结结结结构构构构B,0,1满满满满足足足足定定定定义义义义9.2.19.2.1的的的的条条条条件件件件，所所所所以以以以它它它它是是是是布布布布尔尔尔尔代代代代数数数数，它它它它是是是是二二二二元元元元布布布布尔尔尔尔代代代代数数数数。二元布尔代数其哈斯图是链的唯一布尔代数。二元布尔代数其哈斯图是链的唯一布尔代数。二元布尔代数其哈斯图是链的唯一布尔代数。二元布尔代数其哈斯图是链的唯一布尔代数。第32页，本讲稿共70页9.3 子布尔代数、积布尔代数和子布尔代数、积布尔代数和布尔代数同态布尔代数同态把把子子代代数数、积积代代

37、数数和和同同态态的的概概念念应应用用到到布布尔尔代代数数上上，便便得得到到了了相相应应论论题题，本本节节不准备详尽叙述它，仅就其特点讨论之。不准备详尽叙述它，仅就其特点讨论之。第33页，本讲稿共70页定义定义定义定义9.3.19.3.1 给定布尔代数给定布尔代数给定布尔代数给定布尔代数B1，T T B B，若，若，若，若T T对所有运算封闭，且对所有运算封闭，且对所有运算封闭，且对所有运算封闭，且0 0，1 1T T，则称，则称，则称，则称T 是子布尔代数。是子布尔代数。是子布尔代数。是子布尔代数。显然，显然，显然，显然，B1和和和和01是子布尔代数。是子布尔代数。是子布尔代数。是子布尔代数。

38、第34页，本讲稿共70页应该指出，没有必要对所有三个运算应该指出，没有必要对所有三个运算应该指出，没有必要对所有三个运算应该指出，没有必要对所有三个运算 ，和和和和 都要检查封闭性，也没有必要验证都要检查封闭性，也没有必要验证都要检查封闭性，也没有必要验证都要检查封闭性，也没有必要验证0 0与与与与1 1是是是是否在否在否在否在T T中，只要对运算集合中，只要对运算集合中，只要对运算集合中，只要对运算集合 ，或或或或 ，检查其封闭性即可。这可从布尔代数中这两个检查其封闭性即可。这可从布尔代数中这两个检查其封闭性即可。这可从布尔代数中这两个检查其封闭性即可。这可从布尔代数中这两个运算集合是全功能

39、集得出。因为对任意运算集合是全功能集得出。因为对任意运算集合是全功能集得出。因为对任意运算集合是全功能集得出。因为对任意x x，y yS S，有，有，有，有x x y=(xy=(x y)y)，0=(x0=(x x)x)，1=x1=x xx，故对，故对，故对，故对于于于于 和和和和 的封闭便保证了的封闭便保证了的封闭便保证了的封闭便保证了 的封闭以及的封闭以及的封闭以及的封闭以及0 0，1 1T T。第35页，本讲稿共70页对于对于对于对于 ，可用同样论证。可用同样论证。可用同样论证。可用同样论证。显然，每个子布尔代数都是布尔代数。显然，每个子布尔代数都是布尔代数。显然，每个子布尔代数都是布尔代

40、数。显然，每个子布尔代数都是布尔代数。布尔代数的子集可以是个布尔代数，但也布尔代数的子集可以是个布尔代数，但也布尔代数的子集可以是个布尔代数，但也布尔代数的子集可以是个布尔代数，但也可能不是布尔代数，因为这可从它对运算是否可能不是布尔代数，因为这可从它对运算是否可能不是布尔代数，因为这可从它对运算是否可能不是布尔代数，因为这可从它对运算是否封闭而定。封闭而定。封闭而定。封闭而定。第36页，本讲稿共70页定义定义定义定义9.3.29.3.2 给定两个布尔代数给定两个布尔代数给定两个布尔代数给定两个布尔代数B 和和和和B，则两个布尔代数的积也是布尔代数，称为积，则两个布尔代数的积也是布尔代数，称为

41、积，则两个布尔代数的积也是布尔代数，称为积，则两个布尔代数的积也是布尔代数，称为积布尔代数，记作布尔代数，记作布尔代数，记作布尔代数，记作B，其中对任意，其中对任意，其中对任意，其中对任意b，b B B1 1BB2 2，有，有，有，有第37页，本讲稿共70页b 3 3b=b 3 3b=b=0 03 3=0=，1 13 3=1=可见，积布尔代数能够生成新的布尔代数。可见，积布尔代数能够生成新的布尔代数。可见，积布尔代数能够生成新的布尔代数。可见，积布尔代数能够生成新的布尔代数。第38页，本讲稿共70页定义定义定义定义9.3.39.3.3 给定两个布尔代数给定两个布尔代数给定两个布尔代数给定两个布

42、尔代数B1和和和和T，则，则，则，则B1 T：=(=(f)(ff)(fT TB B(x)(x)(y)(xy)(x，y yS(f(x+y)=f(x)S(f(x+y)=f(x)f(y)f(y)f(xy)=f(x)f(xy)=f(x)f(y)f(y)f(x)=f(x)=f(0)=f(0)=f(1)=)f(1)=)并称并称并称并称f f为从为从为从为从B1到到到到T的布尔同态映射。的布尔同态映射。的布尔同态映射。的布尔同态映射。第39页，本讲稿共70页如前所述，同态的定义仍可简化成：若保如前所述，同态的定义仍可简化成：若保如前所述，同态的定义仍可简化成：若保如前所述，同态的定义仍可简化成：若保持运算持

43、运算持运算持运算 ，或或或或 ，则则则则f fT TB B为布尔同态为布尔同态为布尔同态为布尔同态映射。又若映射。又若映射。又若映射。又若f f为双射，则为双射，则为双射，则为双射，则f f为布尔同构映射。为布尔同构映射。为布尔同构映射。为布尔同构映射。定理定理定理定理9.3.19.3.1 若若若若f f为从为从为从为从B1到到到到T的布尔同态映射，且的布尔同态映射，且的布尔同态映射，且的布尔同态映射，且|f(B)|2|f(B)|2，其中，其中，其中，其中f(B)=y|f(x)=yf(B)=y|f(x)=yT Tx xBB，则，则，则，则f(B)f(1)是布尔代数。是布尔代数。是布尔代数。是布

44、尔代数。第40页，本讲稿共70页9.4 布尔代数的原子表示布尔代数的原子表示在在在在布布布布尔尔尔尔集集集集合合合合代代代代数数数数中中中中，每每每每个个个个子子子子集集集集可可可可表表表表成成成成单单单单元元元元集集集集的的的的并并并并，而而而而且且且且这这这这种种种种表表表表示示示示在在在在不不不不计计计计项项项项的的的的次次次次序序序序情情情情况况况况下下下下是是是是唯唯唯唯一一一一的的的的。对对对对于于于于任任任任何何何何有有有有限限限限布布布布尔尔尔尔代代代代数数数数，也也也也将将将将有有有有同同同同样样样样的的的的结结结结果果果果，这这这这里里里里起起起起着着着着单单单单元元元元集

45、集集集作作作作用用用用的的的的那那那那些些些些元元元元素素素素，称它们是原子。称它们是原子。称它们是原子。称它们是原子。第41页，本讲稿共70页定义定义定义定义9.4.19.4.1 给定布尔代数给定布尔代数给定布尔代数给定布尔代数 1且且且且00a aB B，则，则，则，则a a为原子：为原子：为原子：为原子：=(=(x x)()(x xB Ba a x x=a aa a x x=0)=0)因为因为因为因为a a x x=a aa a x x，所以上述定义又可表为，所以上述定义又可表为，所以上述定义又可表为，所以上述定义又可表为a a为原子：为原子：为原子：为原子：=(=(x x)()(x x

46、S Sa a x xa a x x=0)=0)若若若若a a为原子且为原子且为原子且为原子且x x a a，则，则，则，则x x=0=0或或或或x x=a a。这表明原。这表明原。这表明原。这表明原子在偏序图中是那些紧位于零元之上的元素。子在偏序图中是那些紧位于零元之上的元素。子在偏序图中是那些紧位于零元之上的元素。子在偏序图中是那些紧位于零元之上的元素。第42页，本讲稿共70页定理定理定理定理9.4.19.4.1 若若若若a a1 1和和和和a a2 2为布尔代数为布尔代数为布尔代数为布尔代数 的原子，且的原子，且的原子，且的原子，且a a1 1 a a2 200，则，则，则，则a a1 1

47、=a a2 2。定定定定理理理理9.4.29.4.2 若若若若x x是是是是有有有有限限限限布布布布尔尔尔尔代代代代数数数数 的非零元，则存在原子的非零元，则存在原子的非零元，则存在原子的非零元，则存在原子a aS S，使得，使得，使得，使得a a x x。定定定定理理理理9.4.39.4.3 若若若若a a，a a1 1，a a2 2，a an n为为为为有有有有限限限限布布布布尔尔尔尔代数代数代数代数 1的原子，则的原子，则的原子，则的原子，则a a a a1 1 a a2 2 a an n(i i)()(i i 1 1，2 2，n n a a=a ai i)第43页，本讲稿共70页定定定

48、定理理理理9.4.4 设设有有限限布布尔尔代代数数的的所所有有原原子子是是a1 1，a2，a an，且且yB，则，则y=0=0(i)(i 1 1，2 2，n y ai i=0)第44页，本讲稿共70页定理定理9.4.5(9.4.5(原子表示定理原子表示定理)给给定定布布尔尔代代数数，00 xB B以及以及i i=1，2，n，ai x x，则，则x=ai，且不计原子的次序表示式是唯一的。，且不计原子的次序表示式是唯一的。，且不计原子的次序表示式是唯一的。，且不计原子的次序表示式是唯一的。第45页，本讲稿共70页定理定理定理定理9.4.6(9.4.6(斯通斯通斯通斯通(Stone)(Stone)定

49、理定理定理定理)设设设设 1是是是是有有有有限限限限布布布布尔尔尔尔代代代代数数数数，且且且且A A表表表表示示示示该该该该代代代代数数数数中中中中的的的的所所所所有有有有原原原原子子子子的的的的集集集集合合合合，则则则则 1同同同同构构构构于于于于幂幂幂幂集集集集代代代代数数数数 。本本本本定定定定理理理理说说说说明明明明了了了了，能能能能够够够够用用用用布布布布尔尔尔尔代代代代数数数数的的的的各各各各原原原原子子子子，完完完完全全全全确确确确定定定定该该该该布布布布尔尔尔尔代代代代数数数数，并并并并且且且且可可可可用用用用布布布布尔尔尔尔集集集集合合合合代代代代数数数数 表示这一布尔代数。

50、表示这一布尔代数。表示这一布尔代数。表示这一布尔代数。第46页，本讲稿共70页由本定理可直接得到下面推论：由本定理可直接得到下面推论：由本定理可直接得到下面推论：由本定理可直接得到下面推论：|B B|=2|=2|A A|由此又可推出，若两个有限布尔代数中的由此又可推出，若两个有限布尔代数中的由此又可推出，若两个有限布尔代数中的由此又可推出，若两个有限布尔代数中的集合有相同的基数，则它们的原子集合也有相集合有相同的基数，则它们的原子集合也有相集合有相同的基数，则它们的原子集合也有相集合有相同的基数，则它们的原子集合也有相同的基数。于是该二个布尔代数是同构的。因同的基数。于是该二个布尔代数是同构的