第09章格与布尔代数精选文档.ppt

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

1、第第09章格与布尔代数章格与布尔代数本讲稿第一页，共七十页9.1 格格1格作为偏序集定定义义9.1.1 设设是是一一个个偏偏序序集集，若若对对任任意意a,b,L，存存在在glba,b和和luba,b，则则称称为为格格，并并记记为为a*b=glba,b，a b=luba,b，称称 和和 分分别别为为L上上的的交交（或或积积）和和并并（或或和和）运运算算。称称为为所所诱诱导导的的代代数数结结构构的的格格。若若L是有限集合，称是有限集合，称为有限格。为有限格。本讲稿第二页，共七十页格的对偶性原理是成立的：格的对偶性原理是成立的：令令是偏序集，且是偏序集，且是其对偶的偏是其对偶的偏序集。若序集。若是格

2、，则是格，则也是格，反之亦也是格，反之亦然。这是因为，对于然。这是因为，对于L中任意中任意a和和b，中中luba,b等同于等同于中中glb a,b，中中glba,b等同于等同于中的中的luba,b。若。若L是有限是有限集，这些性质易从偏序集及其对偶的哈斯图得集，这些性质易从偏序集及其对偶的哈斯图得到验证。到验证。本讲稿第三页，共七十页从上讨论中，可知两格互为对偶。互为对从上讨论中，可知两格互为对偶。互为对偶的两个偶的两个和和有着密切关系，即格有着密切关系，即格中交运算中交运算 正是格正是格中的并运算中的并运算，而，而格格中的并运算中的并运算 正是格正是格中的交运算中的交运算。因此，给出关于格一

3、般性质的任何有效命题，因此，给出关于格一般性质的任何有效命题，把关系把关系换成换成（或者（或者换成换成），交换成并，并），交换成并，并换成交，可得到另一个有效命题，这就是关于换成交，可得到另一个有效命题，这就是关于格的对偶性原理。格的对偶性原理。定义定义9.1.2 设设是格，且是格，且S L。若对任。若对任意意a,b S，有，有a*b S和和a b S，则称，则称是是格格的子格。的子格。本讲稿第四页，共七十页2格的基本性质在在证证明明格格的的性性质质前前，回回忆忆一一下下a*b和和a b的的真正含义是有好处的。真正含义是有好处的。a*ba和和a bb，则则表表明明a*b是是a和和b的的下下界。

4、界。若若ca和和cb，则则ca*b，这这表表明明a*b是是a和和b的最大下界。的最大下界。aa b和和ba b，则则表表明明a b是是a和和b的的上界。上界。若若ac，且且bc，则则a bc，这这表表明明a b是是a和和b的最小上界。的最小上界。本讲稿第五页，共七十页定理定理9.1.1 设设是格，对任意是格，对任意a,b L，有有 a b=bab a*b=aab a*b=aa b=b亦即亦即 aba b=ba*b=a本讲稿第六页，共七十页定定理理9.1.2 设设是是格格，对对任任意意a,b L，有有 a*b=a,a a=a。（幂等律）（幂等律）a*b=b*a,a b=b a。（交换律）（交换律

5、）a*(b*c)=(a*b)*ca(b c)=(a b)c （结合律）（结合律）a*(a b)=aa(a*b)=a （吸收律）（吸收律）本讲稿第七页，共七十页定定理理9.1.3 设设是是格格，对对任任意意a,b,c L，有，有若若ab和和cd，则，则a*cb*d，a cb d。若若ab，则，则a*cb*c，a cb c。ca和和cb ca*bac和和bc a bc本讲稿第八页，共七十页定定 理理 9.1.4 设设 是是 格格，对对 任任 意意 的的a,b,c L，有，有a(b*c)(a b)*(a c)(a*b)(a*c)a*(b c)通常称上二式为格中分配不等式。通常称上二式为格中分配不等式

6、。本讲稿第九页，共七十页定定 理理 9.1.5 设设 是是 格格，对对 任任 意意 的的a,b,c L，有，有aca(b*c)(a b)*c推推论论：在在格格中中，对对任任意意的的a,b,c L，有有(a*b)(a*c)a*(b(a*c)a(b*(a c)(a b)*(a c)本讲稿第十页，共七十页3特殊的格定定义义9.1.3 设设是是格格，若若L中中有有最最大大元元和和最最小小元元，则则称称为为有有界界格格。一一般般把把格格中中最最大元记为大元记为1，最小元记为，最小元记为0。由定义可知，对任意由定义可知，对任意a L，有，有0a1a*0=0,a 0=aa*1=a,a 1=1本讲稿第十一页，

7、共七十页定理定理9.1.6 设设是有限格，其中是有限格，其中L=a1,a2,an，则，则是有界格。是有界格。本讲稿第十二页，共七十页定义定义9.1.4 设设是有界格，对于是有界格，对于a L，存在存在b L，使得，使得a*b=0，a b=1称称b为为a的补元，记为的补元，记为a。由定义可知，若由定义可知，若b是是a的补元，则的补元，则a也是也是b的的补元，即补元，即a与与b互为补元。互为补元。显然，显然，0=1和和1=0，且易证补元是唯一的。，且易证补元是唯一的。一般说来，一个元素可以有其补元，未必一般说来，一个元素可以有其补元，未必唯一，也可能无补元。唯一，也可能无补元。本讲稿第十三页，共七

8、十页定定 义义 9.1.5 设设 是是 格格，对对 任任 意意 的的a,b,c L，有，有 a*(b c)=(a*b)(a*c)a(b*c)=(a b)*(a c)则则称称为为分分配配格格，称称和和为为格格中中分分配配律。律。本讲稿第十四页，共七十页定义定义9.1.6 设设是格，对任意的是格，对任意的a,b,c L，有，有aca(b*c)=(a b)*c称称为模格。为模格。定理定理9.1.7 分配格是模格分配格是模格定理定理9.1.8 每个链都是分配格。每个链都是分配格。本讲稿第十五页，共七十页定定理理9.1.9 一一个个格格为为分分配配格格，当当且且仅仅当当它它不不含有任何子格与这两个五元素

9、格中任一个同构。含有任何子格与这两个五元素格中任一个同构。定定理理9.1.10 设设是是分分配配格格，对对任任意意a,b,c L，有，有(a*b=a*c)且且(a b=a c)b=c定定理理9.1.11 设设是是有有界界分分配配格格，若若a L，且补元存在，则其补元是唯一的。，且补元存在，则其补元是唯一的。本讲稿第十六页，共七十页定定义义9.1.7 设设是是格格，若若L中中每每个个元元素素至少有一补元，则称至少有一补元，则称为有补格。为有补格。由由于于补补元元的的定定义义是是在在有有界界格格中中给给出出的的，可可知，有补格一定是有界格。知，有补格一定是有界格。定定义义9.1.8 若若一一格格既

10、既是是有有补补又又是是分分配配的的，则则称该格为有补分配格，或布尔格，或布尔代数。称该格为有补分配格，或布尔格，或布尔代数。本讲稿第十七页，共七十页定定理理9.1.12 设设是是有有补补分分配配格格，若若任任意意元素元素a L，则，则a的补元的补元a是唯一的。是唯一的。该该定定理理9.1.11的的直直接接推推论论，因因为为有有补补分分配配格格当然是有界分配格。当然是有界分配格。由由于于有有补补分分配配格格中中，每每个个元元素素a都都有有唯唯一一的的补补元元a，因因此此可可在在L上上定定义义一一个个一一元元运运算算补补运运算算“”。这这样样，有有补补分分配配格格可可看看作作具具有有两两个个二二元

11、元运运算算和和一一个个一一元元运运算算的的代代数数结结构构，习习惯惯上上称它为布尔代数，记为称它为布尔代数，记为，其中，其中B=L。本讲稿第十八页，共七十页定理定理9.1.13 设设是有补分配格，对任意是有补分配格，对任意a,b L，则，则(a)=a(a*b)=a b(a b)=a*b后两式称为格中德后两式称为格中德摩根律。摩根律。本讲稿第十九页，共七十页定定理理9.1.14 设设是是有有补补分分配配格格，对对任任意意a,b L，有，有aba*b=0a b=1格格同同态态，格格直直积积等等概概念念可可以以接接下下来来定定义义和和研研究究，但但这这里里不不打打算算这这样样做做，因因为为如如此此进

12、进行行会会相相对对较较繁繁，而而是是将将格格作作为为一一个个代代数数结结构构而而引引入入它们。它们。本讲稿第二十页，共七十页4格是代数结构能能自自然然地地把把代代数数结结构构中中有有关关子子代代数数、同同态态、积代数等概念，引入到格中。积代数等概念，引入到格中。定定义义9.1.9 设设是是一一代代数数结结构构，其其中中 和和*是是L上上满满足足交交换换律律、结结合合律律和和吸吸收收律律的的二二元运算，且对任意元运算，且对任意a,b L，定义关系，定义关系如下：如下：aba*b=a则则 是是 格格，称称 为为 代代 数数 系系 统统所诱导的偏序集确立的格。所诱导的偏序集确立的格。本讲稿第二十一页

13、，共七十页定定义义9.1.10 设设和和是是格格。存存在函数在函数f:LS，若对任意，若对任意a,b L，有，有f(a b)=f(a)f(b)，f(a*b)=f(a)f(b)则称则称f是从是从到到的格同态。的格同态。下述定理说明格同态是保序的。下述定理说明格同态是保序的。定定理理9.1.15 设设和和是是格格，而而和和分分别别是是给给定定两两个个格格所所诱诱导导的的偏偏序序集集确确立立的的格格。若若f:LS是是格格同同态态，则则对对任任意意a,b L，且，且ab，必有，必有f(a)f(b)。本讲稿第二十二页，共七十页在在定定义义9.1.10中中，若若f是是双双射射函函数数，则则称称f是是格格同

14、同构构。或或称称和和两两个个格格同同构构。由由于于同同构构是是相相互互的的，又又是是保保序序的的，故故对对任任意意a,b L，有，有abf(a)f(b)和和f(a)f(b)ab这这表表明明同同构构的的两两个个格格的的哈哈斯斯图图是是一一样样的的，只是各结点的标记不同而已。只是各结点的标记不同而已。本讲稿第二十三页，共七十页定定义义9.1.11 设设和和是是格格，定定义一个代数结构义一个代数结构如下：如下：对任意对任意，L S，有，有+=o=称称是是格格和和的的直直积。积。本讲稿第二十四页，共七十页两个格的直积也是格。这是因为在两个格的直积也是格。这是因为在L S上，上，运算运算o和和+是封闭的

15、，且满足交换律、结合律和是封闭的，且满足交换律、结合律和吸收律。吸收律。格积的阶等于两个格的阶乘积。由于格积的阶等于两个格的阶乘积。由于是一个格，故又可以与另一个格作直是一个格，故又可以与另一个格作直积，这样，利用格的直积可用较小阶的格构造积，这样，利用格的直积可用较小阶的格构造出阶越来越大的格。但反之，较大阶的格，并出阶越来越大的格。但反之，较大阶的格，并不都能表示成较小阶的格直积。不都能表示成较小阶的格直积。本讲稿第二十五页，共七十页9.2 布尔代数布尔代数前前已已指指出出，布布尔尔代代数数是是有有补补分分配配格格，常常记为记为。对任意。对任意a,b,c B，有，有本讲稿第二十六页，共七十

16、页 是格，且是格，且为为B上由上由 或或*所定义所定义的偏序关系，满足的偏序关系，满足(L-1)a b=luba,b，a*b=glba,b(L-2)aba b=ba*b=a(L-3)a a=a，a*a=a （等幂律）（等幂律）(L-4)a b=b a，a*b=b*a （交换律）（交换律）(L-5)(a b)c=a(b c)，(a*b)*c=a*(b*c)（结合律）（结合律）(L-6)a(a*b)=a，a*(a b)=a （吸收律）（吸收律）本讲稿第二十七页，共七十页 是分配格，满足是分配格，满足(D-1)a(b*c)=(a b)*(a c)，a*(b c)=(a*b)(a*c)（分配律）（分配

17、律）(D-2)(a b=a c)(a*b=a*c)b=c(D-3)(a b)*(b c)*(c a)=(a*b)(b*c)(c*a)本讲稿第二十八页，共七十页 是有界格，满足是有界格，满足(B-1)0a1(B-2)a 0=a，a*a=a （幺律）（幺律）(B-3)a 1=1，a*0=0 （零律）（零律）是有补格，满足是有补格，满足(C-1)a a=1，a*a=0 （互补律）（互补律）(C-2)1=0，0=1本讲稿第二十九页，共七十页 是有补分配格，满足是有补分配格，满足(CD-1)(a b)=a*a，(a*b)=a b （德（德摩根律）摩根律）(CD-2)aba b=1a*b=0ba注意，上述

18、公式并非都是独立的，可从中注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。的公式，而且可以用基本公式定义布尔代数。本讲稿第三十页，共七十页定义定义9.2.1 设设是一代数结构，其是一代数结构，其中中 和和*是是B上的二元运算，上的二元运算，是是B上的一元运算。上的一元运算。0,1 B。若对任意。若对任意a,b B，有，有 a b=b a，a*b=b*a （交换律）（交换律）a(b*c)=(a b)*(a c)，a*(b c)=(a*b)(a*c)（分配律）（分配律）a 0=a，a*1=a

19、 （幺律）（幺律）a a=1，a*a=0 （互补律）（互补律）本讲稿第三十一页，共七十页则称则称是布尔代数，称是布尔代数，称、*和和分别是分别是B上的并、交和补运算，上的并、交和补运算，0和和1分别称为分别称为 和和*的零元和幺元。的零元和幺元。代代数数结结构构满满足足定定义义9.2.1的的条条件件，所所以以它它是是布布尔尔代代数数，它它是是二二元元布布尔尔代代数数。二元布尔代数其哈斯图是链的唯一布尔代数。二元布尔代数其哈斯图是链的唯一布尔代数。本讲稿第三十二页，共七十页9.3 子布尔代数、积布尔代数和布子布尔代数、积布尔代数和布尔代数同态尔代数同态把把子子代代数数、积积代代数数和和同同态态的

20、的概概念念应应用用到到布布尔尔代代数数上上，便便得得到到了了相相应应论论题题，本本节节不不准准备详尽叙述它，仅就其特点讨论之。备详尽叙述它，仅就其特点讨论之。本讲稿第三十三页，共七十页定义定义9.3.1 给定布尔代数给定布尔代数，T B，若，若T对所有运算封闭，且对所有运算封闭，且0，1T，则称，则称是子布尔代数。是子布尔代数。显然，显然，和和是子布尔代数。是子布尔代数。本讲稿第三十四页，共七十页应该指出，没有必要对所有三个运算应该指出，没有必要对所有三个运算，和和都要检查封闭性，也没有必要验证都要检查封闭性，也没有必要验证0与与1是是否在否在T中，只要对运算集合中，只要对运算集合 ，或或 ，

21、检查其封闭性即可。这可从布尔代数中这两个检查其封闭性即可。这可从布尔代数中这两个运算集合是全功能集得出。因为对任意运算集合是全功能集得出。因为对任意x，yS，有，有x y=(x y)，0=(x x)，1=x x，故对，故对于于 和和的封闭便保证了的封闭便保证了 的封闭以及的封闭以及0，1T。本讲稿第三十五页，共七十页对于对于 ，可用同样论证。可用同样论证。显然，每个子布尔代数都是布尔代数。显然，每个子布尔代数都是布尔代数。布尔代数的子集可以是个布尔代数，但也布尔代数的子集可以是个布尔代数，但也可能不是布尔代数，因为这可从它对运算是否可能不是布尔代数，因为这可从它对运算是否封闭而定。封闭而定。本

22、讲稿第三十六页，共七十页定义定义9.3.2 给定两个布尔代数给定两个布尔代数和和，则两个布尔代数的积也是布尔代数，称为积布则两个布尔代数的积也是布尔代数，称为积布尔代数，记作尔代数，记作，其中对任意，其中对任意，B1B2，有，有本讲稿第三十七页，共七十页 3=3=03=，13=可见，积布尔代数能够生成新的布尔代数。可见，积布尔代数能够生成新的布尔代数。本讲稿第三十八页，共七十页定义定义9.3.3 给定两个布尔代数给定两个布尔代数和和，则，则：=(f)(fTB(x)(y)(x，yS(f(x+y)=f(x)f(y)f(xy)=f(x)f(y)f(x)=f(0)=f(1)=)并称并称f为从为从到到的

23、布尔同态映射。的布尔同态映射。本讲稿第三十九页，共七十页如前所述，同态的定义仍可简化成：若保如前所述，同态的定义仍可简化成：若保持运算持运算 ，或或 ，则则fTB为布尔同态为布尔同态映射。又若映射。又若f为双射，则为双射，则f为布尔同构映射。为布尔同构映射。定理定理9.3.1 若若f为从为从到到的布尔同态映射，且的布尔同态映射，且|f(B)|2，其中，其中f(B)=y|f(x)=yTxB，则，则是布尔代数。是布尔代数。本讲稿第四十页，共七十页9.4 布尔代数的原子表示布尔代数的原子表示在在布布尔尔集集合合代代数数中中，每每个个子子集集可可表表成成单单元元集集的的并并，而而且且这这种种表表示示在

24、在不不计计项项的的次次序序情情况况下下是是唯唯一一的的。对对于于任任何何有有限限布布尔尔代代数数，也也将将有有同同样样的的结结果果，这这里里起起着着单单元元集集作作用用的的那那些些元元素素，称它们是原子。称它们是原子。本讲稿第四十一页，共七十页定义定义9.4.1 给定布尔代数给定布尔代数且且0aB，则，则a为原子：为原子：=(x)(xBa x=aa x=0)因为因为a x=aa x，所以上述定义又可表为，所以上述定义又可表为a为原子：为原子：=(x)(xSa xa x=0)若若a为原子且为原子且x a，则，则x=0或或x=a。这表明原。这表明原子在偏序图中是那些紧位于零元之上的元素。子在偏序图

25、中是那些紧位于零元之上的元素。本讲稿第四十二页，共七十页定理定理9.4.1 若若a1和和a2为布尔代数为布尔代数的原子，且的原子，且a1 a20，则，则a1=a2。定定理理9.4.2 若若x是是有有限限布布尔尔代代数数的非零元，则存在原子的非零元，则存在原子aS，使得，使得a x。定定理理9.4.3 若若a，a1，a2，an为为有有限限布布尔尔代数代数的原子，则的原子，则a a1 a2 an(i)(i 1，2，n a=ai)本讲稿第四十三页，共七十页定定理理9.4.4 设设有有限限布布尔尔代代数数的的所所有有原原子子是是a1，a2，an，且且yB，则，则y=0(i)(i 1，2，n y ai=

26、0)本讲稿第四十四页，共七十页定理定理9.4.5(原子表示定理原子表示定理)给给定定布布尔尔代代数数，0 xB以及以及i=1，2，n，ai x，则，则x=ai，且不计原子的次序表示式是唯一的。，且不计原子的次序表示式是唯一的。本讲稿第四十五页，共七十页定理定理9.4.6(斯通斯通(Stone)定理定理)设设是是有有限限布布尔尔代代数数，且且A表表示示该该代代数数中中的的所所有有原原子子的的集集合合，则则同同构构于于幂幂集集代代数数。本本定定理理说说明明了了，能能够够用用布布尔尔代代数数的的各各原原子子，完完全全确确定定该该布布尔尔代代数数，并并且且可可用用布布尔尔集集合合代代数数表示这一布尔代

27、数。表示这一布尔代数。本讲稿第四十六页，共七十页由本定理可直接得到下面推论：由本定理可直接得到下面推论：|B|=2|A|由此又可推出，若两个有限布尔代数中的由此又可推出，若两个有限布尔代数中的集合有相同的基数，则它们的原子集合也有相集合有相同的基数，则它们的原子集合也有相同的基数。于是该二个布尔代数是同构的。因同的基数。于是该二个布尔代数是同构的。因此可得到如下定理：此可得到如下定理：定理定理9.4.7 每个有限布尔代数的集合基数均每个有限布尔代数的集合基数均为为2的方幂，具有同样集合基数的布尔代数都是的方幂，具有同样集合基数的布尔代数都是同构的。同构的。本讲稿第四十七页，共七十页9.5 布尔

28、代数布尔代数Br2为为了了书书写写方方便便，用用Bn表表示示具具有有n个个元元素素的的布布尔尔代代数数，即即Bn=。根根据据定定理理9.4.7可可知知，n必必为为2的的方方幂幂。因因此此，“最最小小”的的布布尔尔代代数数即即是是二二元元布布尔尔代代数数B2=，其其中中B2=0，1。B2的的运运算算表表如如表表9.1.1所所示示。下下面面再再给给出出“次次最最小小”的的布布尔尔代代数数B4=的的运运算算表表9.5.1，其其中中B4=0，1。本讲稿第四十八页，共七十页本讲稿第四十九页，共七十页特特 别别 令令 人人 感感 兴兴 趣趣 的的 代代 数数 结结 构构 是是B2B2B2(r个个)，即即r

29、个个相相同同的的布布尔尔代代数数B2的的直直积积。该该系系统统记记作作Br2，且且其其运运算算符符号号仍仍与与B2中中的的，和和相相同同，即即Br2=。对对任任意意和和Br2，其其中中i，j 0，1，i，j=1，2，n。本讲稿第五十页，共七十页=0=和和1=本讲稿第五十一页，共七十页由积代数的理论可知，由积代数的理论可知，Br2保持保持B2中重要性中重要性质，于是断言，质，于是断言，Br2是布尔代数，并且由定理是布尔代数，并且由定理9.4.7能得到下面定理：能得到下面定理：定理定理9.5.1 布尔代数布尔代数与与是同构的，并且每个布尔是同构的，并且每个布尔代数同构于某布尔代数代数同构于某布尔代

30、数Bk2=。综综上上所所述述可可知知，每每个个布布尔尔代代数数同同构构于于某某布布尔集合代数。尔集合代数。本讲稿第五十二页，共七十页9.6 布尔表达式及其范式定理布尔表达式及其范式定理本本节节中中先先给给出出布布尔尔表表达达式式或或布布尔尔函函数数的的定定义，后讨论布尔表达式的范式定理。义，后讨论布尔表达式的范式定理。定定义义9.6.1 给给定定布布尔尔代代数数及及n个个变变元元x1，x2，xn，则则在在上上由由n个个变变元元产产生生的的布布尔尔表表达达式式可可归纳定义如下：归纳定义如下：本讲稿第五十三页，共七十页(1)(基础基础)。B中的任何元素和变元中的任何元素和变元xi(i=1，2，n)

31、都是一个布尔表达式。都是一个布尔表达式。(2)(归纳步归纳步)。若。若e1和和e2是布尔表达式，那么是布尔表达式，那么e1，(e1)(e2)和和(e1)(e2)也是布尔表达式。也是布尔表达式。注意，当约定注意，当约定 先于先于 运算时，可适当省略运算时，可适当省略表达式中的园括号。表达式中的园括号。本讲稿第五十四页，共七十页如如果果限限定定n个个变变元元x1，x2，xn都都取取值值于于B中中的的元元素素，那那么么在在布布尔尔代代数数上上由由变变元元x1，x2，xn所所产产生生的的布布尔尔表表达达式式的的值值便便表表示示B中中的的元元素素。因因此此，这这些些表表达达式式便便是是一一个个函函数数f

32、Bn，这这里里f(x1，x2，xn)对对任任意意变变元元x1，x2，xn可可由由布布尔尔代代数数中中关关于于，的的运运算算来来确确定定。因因此此，有有时时将将在在上上由由变变元元x1，x2，xn产产生生的的布布尔尔表表达达式式称称为为在在上上的的n元元布布尔尔函函数数(以以下下简简称称布布尔函数尔函数)。本讲稿第五十五页，共七十页定义定义9.6.2 形如形如 的的布布尔尔表表达达式式称称为为由由变变元元x1，x2，xn产产生生的的小小项项，其其中中i 0，1，用用x1i表表示示xi，x0i表表示示xi，i 1，2，n，并用，并用 表示该小项。表示该小项。形如形如 的的布布尔尔表表达达式式称称为

33、为由由变变元元x1，x2，xn产产生生的的大大项项，其其中中i 0，1，x1i表表示示xi，x0i表表示示xi，i 1，2，n，并用，并用 表示该大项。表示该大项。本讲稿第五十六页，共七十页为书写方便，将二进制数为书写方便，将二进制数12n和和12n分别化为十进制数分别化为十进制数i和和j作为作为m和和M的下的下标，即标，即mi和和Mj。关于小项和大项有下列关系：关于小项和大项有下列关系：mi mj=0 (ij)Mi Mj=1 (ij)本讲稿第五十七页，共七十页这是显然的，因为对于两个不同的小项这是显然的，因为对于两个不同的小项(大大项项)，必有一个变元，必有一个变元xk，使得这两个小项，使得

34、这两个小项(大项大项)之之一含有一含有xk，而另一个含有，而另一个含有xk。于是，。于是，xk xk=0，xk xk=1。因此上列关系成立。因此上列关系成立。使用归纳法不难证明下列关系：使用归纳法不难证明下列关系：mi=1Mi=0本讲稿第五十八页，共七十页定理定理9.6.1(范式定理范式定理)在布尔代数在布尔代数上由变元上由变元x1，x2，xn产生的每产生的每个布尔表达式个布尔表达式f(x1，x2，xn)均可表成：均可表成：f(x1，x2，xn)=(ck mk)(1)f(x1，x2，xn)=(Cl Ml)(2)本讲稿第五十九页，共七十页这里，这里，k和和l分别取遍分别取遍2n个所有可能的组态个

35、所有可能的组态12n和和12n，并且，并且=f(1，2，n)=f(1，2，n)(3)本讲稿第六十页，共七十页由由本本定定理理可可知知，布布尔尔代代数数上上的的由由变变元元x1，x2，xn产产生生的的每每个个布布尔尔表表达达式式均均可可表表为为所所有有小小项项的的带带“权权”的的并并，或或者者所所有有大大项项的的带带“权权”的的交交，其其中中这这些些“权权”(即即c12n或或C12n)是是B中中的的元元素素，它它可可用用布布尔尔表表达达式式用用公公式式(3)计计算算得得到到。由由于于这这些些权权是是唯唯一一的的，故故上上述述公公式式(1)和和(2)便便是是唯唯一一的的，并并称称(1)为为小小项项

36、范范式式或或析析取取范范式式，称称(2)为为大大项项范范式式或或合取范式。合取范式。本讲稿第六十一页，共七十页布布尔尔表表达达式式的的范范式式也也可可由由下下面面算算法法9.6.1（或（或9.6.2）得到。）得到。算法算法9.6.1（或（或9.6.2）本本算算法法可可求求出出上上的的布布尔尔表表达式达式f(x1，x2，xn)范式，其具体步骤是：范式，其具体步骤是：本讲稿第六十二页，共七十页(1)使用定律和定理把使用定律和定理把f(x1，x2，xn)表表示成形如示成形如c （或（或C ）的不同交）的不同交（或并）的并（或交），其中（或并）的并（或交），其中c,C B且且i1i2ik。本讲稿第六十

37、三页，共七十页(2)若若每每个个交交（或或并并）是是形形如如c m（或或C M），其其中中c B（或或C B），m是是小小项项（或或M是是大大项项），则则增增加加项项本讲稿第六十四页，共七十页(3)从最后得到的表达式中，选取形如从最后得到的表达式中，选取形如c （或（或C ）的交（或并），其中）的交（或并），其中kn和和对某个对某个h,（或（或 ）不出现，则用）不出现，则用本讲稿第六十五页，共七十页本讲稿第六十六页，共七十页再在新的交（或并）中按下标增加次序重再在新的交（或并）中按下标增加次序重新排列新排列 （或（或 ），于是使用），于是使用(c1 c2)m(或或(C1 C2)M代替代替c1

38、m,c2 m,（或（或C1 M,C2 M,）的交（或并）的交（或并）。转到。转到(2)。本讲稿第六十七页，共七十页因因为为在在上上的的布布尔尔表表达达式式f(x1，x2，xn)是是由由2n个个权权唯唯一一确确定定，又又因因为为每每个个权权是是B中中的的元元素素，所所以以在在上共有上共有 个不同布尔表达式。个不同布尔表达式。本讲稿第六十八页，共七十页另一方面，形如另一方面，形如f 的不同函数共有的不同函数共有 个个 。可见，当。可见，当|B|2时，形如时，形如f 的函数的函数中确有那些函数，它不是布尔函数。而且可以中确有那些函数，它不是布尔函数。而且可以精确计算精确计算 -个函数不是布尔函数。个函数不是布尔函数。本讲稿第六十九页，共七十页例如对于例如对于S=0,1，函数，函数f 的的定义中有定义中有f(0,0)=0，f(0,1)=1，f(1,0)=f(1,1)=，f(0,)=则则f不是布尔函数，为什么？读者从上面的不是布尔函数，为什么？读者从上面的说明中是不难给出正确地回答。说明中是不难给出正确地回答。本讲稿第七十页，共七十页