离散数学II课件：7_5布尔代数

8.5.1 布尔代数的定义及其性质布尔代数的定义及其性质 8.5.2 有限布尔代数的表示理论有限布尔代数的表示理论 8.5.3 布尔代数的同态与同构布尔代数的同态与同构 定义定义.一个有余分配格是一个布尔代数。一个有余分配格是一个布尔代数。一个布尔代数可记为（一个布尔代数可记为（B，+，0，1）。）。设（设（B B，+，0 0，1 1）是一个布尔代数，）是一个布尔代数，a a，b b，c c是集合是集合B B中任意元素中任意元素,于是于是,它有如下它有如下性质性质（一）（一）因为（因为（B B，+）是一个）是一个格格，所以有，所以有1 1）a aa=aa=a，1 1）a+a=aa+a=a。2 2）a ab=bb=ba a，2 2）a+b=b+aa+b=b+a。3 3）(a ab b)c=ac=a(b bc c)，3 3）(a+ba+b)+c=a+c=a+(b+cb+c)。4 4）a a（a+ba+b）=a,4=a,4）a+a+（a ab b）=a=a。（二）（二）因为（因为（B，+）是）是分配格分配格，所以有，所以有5)a(b+c)=(ab)+(ac)，5)a+(bc)=(a+b)(a+c)。6）(ab)+(ac)+(bc)=(a+b)(a+c)(b+c)。7）若）若ab=ac，a+b=a+c，则，则b=c。（三）（三）因为（因为（B，+，0，1）是）是有界格有界格，所以所以 8）0a1。9）a0=0，9）a+1=1。10）a1=a，10）a+0=a。（四）（四）因为（因为（B，+，0，1）是）是有余分配有余分配格格，所以有，所以有11）11）12）12）13）13）（五）（五）因为（因为（B，）是）是半序格半序格，所以有，所以有14）ab=infa，b 14）a+b=supa，b。15）ab a+b=b ab=a。16）0aa1aa10 01baba)(baba)(10baabbaba定理定理8.5.1 设设B是一个至少含有两个不同元素的是一个至少含有两个不同元素的集合，集合，+是定义在是定义在B上的两种代数运算，如上的两种代数运算，如果对任意果对任意a，b，cB，满足下面公理：，满足下面公理：H1：ab=ba，a+b=b+a.H2：a(b+c)=(ab)+(ac),a+(bc)=(a+b)(a+c)。H3：B中有元素中有元素0和元素和元素1,使得对任意使得对任意aB,有有 a1=a,a+0=a。H4：对任意对任意aB，有，有 B，使得，使得 则（则（B，+，0，1）是一个布尔代数。）是一个布尔代数。1,0aaaaa证明：只需证明证明：只需证明(B,+）是格，并且）是格，并且0，1是此格是此格的最小，最大元素。的最小，最大元素。于是，根据于是，根据H4，它就是一个，它就是一个有余格，再根据有余格，再根据H2，它又是一个分配格，故它是，它又是一个分配格，故它是布尔代数。布尔代数。首先，往证对偶原理在代数首先，往证对偶原理在代数(B,+)中成立。由于中成立。由于公理公理H1H4是对偶的，所以如果从是对偶的，所以如果从H1H4出出发能推导出结论发能推导出结论c，则，则c的对偶式的对偶式c*也可由也可由H1H4推导出来推导出来.其次，对任意其次，对任意aB，有，有 a+1=（a+1）1 （由（由H3）=1（a+1）（由（由H1）=（a+）（a+1）（由（由H4）=a+（1）（由（由H2）=a+（由（由H3）=1 （由（由H4）aaa再次，若再次，若a+b=a+c，+b=+c。则。则b=c。事实上，事实上，（a+b）（+b）=b+（a ）（由（由H2）=b+0 （由（由H4）=b （由（由H3）（a+c）（+c）=c+（a ）（由（由H2）=c+0 （由（由H4）=c （由（由H3）故故 b=c。aaaaaa 下面证明（下面证明（B，+）是一个格。）是一个格。l 由由知，此代数满足知，此代数满足交换律交换律。l 因为因为a+（ab）=（a1）+（ab）（由（由H3）=a（1+b）（由（由H2）=a1 （由上面的证明）（由上面的证明）=a （由（由H3）所以，此代数满足所以，此代数满足吸收律吸收律。l 令令L=a（bc），），M=（ab）c 于是于是 a+L=a+（a（bc）=a （由吸收律）（由吸收律）a+M=a+（ab）c）=（a+ab）（a+c）（由（由H2）=a（a+c）（由吸收律）（由吸收律）=a （由吸收律）（由吸收律）所以所以 a+L=a+M。而而 +L=+（a（bc）=（+a）（+（bc）（由（由H2）=1（+（bc）（由（由H4）=+（bc）（由（由H3）+M=+（ab）c）=（+ab）（+c）（由（由H2）=(+a)(+b)(+c)（由（由H2）=（1（+b）（+c）（由（由H4）=（+b）（+c）（由（由H3）=+（bc）（由（由H2）所以所以 +L=+M。故故L=M。即此代数满足结合律。即此代数满足结合律。由格的定义知，代数（由格的定义知，代数（B，+）是一个格。）是一个格。aaaaaaaaaaaaaaaaaaaa往证往证0，1是此格的最小，最大元素。是此格的最小，最大元素。定义定义B上的部分序关系上的部分序关系如下：如下：ab ab=a于是，由本章于是，由本章8.2的定理的定理8.2.1知，（知，（B，）是格，并且是格，并且 ab a+b=b由由H3知，对任意知，对任意aB，有，有 a1=a，a+0=a故故,0a1。即。即0，1分别是分别是B的最小的最小,最大元素最大元素.因此（因此（B，+，0，1）是布尔代数。）是布尔代数。证毕。证毕。还可以证明：公理还可以证明：公理H1H4是独立的（参看是独立的（参看“Boolean Algebra”,R.L.GoodsteinBoolean Algebra”,R.L.Goodstein）。）。v电路代数电路代数（B，+，0，1）其中其中B=0，1,B上的运算上的运算+，如下表定义：如下表定义：v集合代数集合代数（S），），S）其中其中S是一个非空集合。是一个非空集合。01000101+01001111x0110 xv 命题代数命题代数 （S，F，T）其中其中S是是命题公式的集合。命题公式的集合。v 开关代数开关代数 （Bn，+，0n，1n）其中其中Bn是由是由0，1做分量的所有做分量的所有n元向量集合。元向量集合。对任意对任意a,bBn,令令a=(a1，an)，b=(b1，bn)，定义定义Bn上的运算如下：上的运算如下：ab=（a1b1，a2b2，anbn）a+b=（a1+b1，a2+b2，an+bn）0n表示表示n个个0做成的做成的n元向量元向量(0，0)，1n表示表示n个个1做成的做成的n元向量元向量(1，1)。),(21naaaa定义定义 任给一个布尔代数任给一个布尔代数(B,+,0,1)。若若B的一个子集的一个子集S包含包含0,1,且且(S，+，0，1)仍是一个布尔代数仍是一个布尔代数,则称则称S为为B的的子代数子代数。例例.设设S=a，b，c，则，则（S）,S）是一个布尔代数。）是一个布尔代数。(1)设设S1=，a，b，c，a，b，c，则，则 （S1，S）是）是 （S），），S）的子代数。）的子代数。(2)设设S2=，a，b，a，b，a，b，c，则则S2在在，下是下是（S）的子格，但）的子格，但（S2，S）不是布尔代数，）不是布尔代数，因此不是（因此不是（S），），S）的子代）的子代数。显然，数。显然，a，b，a，b 在在S2中没有余元中没有余元素。素。(3)(3)设设S3=，a，则，则（S3，a）是布尔代数，）是布尔代数，但不是（但不是（S），），S）的子）的子代数，因为代数，因为S3不含不含（S）中的最大元素）中的最大元素S。定理定理8.5.2 设（设（B，+，0，1）是布尔代数。）是布尔代数。于是，于是，B的子集的子集S是是B的子代数的充要条件是的子代数的充要条件是S在运在运算算，+，下是封闭的。下是封闭的。证明：证明：必要性。必要性。若若S是是B的子代数，则显然的子代数，则显然S在在，+，之下是封闭的。之下是封闭的。充分性。充分性。若若S在在，+，下封闭，则任取下封闭，则任取aS，于，于是有是有 S,a+=1S,a =0S即即S包含包含0，1。又因。又因S在运算在运算，+，之下封闭，之下封闭，S中元素也是中元素也是B中元素，而中元素，而B是布尔代数，故是布尔代数，故S中中元素对于运算元素对于运算，+，满足公理满足公理H1H4，所以，所以（S，+，0，1）是布尔代数，由定义，）是布尔代数，由定义，S是是B的子代数。的子代数。aaa基基 底底定义定义.设（设（B，+，0，1）是布尔代数，）是布尔代数，e1，en是是B中有如下性质的一组元素中有如下性质的一组元素对任意对任意aB，都可唯一地表示为，都可唯一地表示为 a=1e1+2e2+nen其中其中i或为或为0，或为，或为1，（，（i=1，n）。）。则称则称e1，en为布尔代数为布尔代数B的一组的一组基底基底，并称，并称此布尔代数为此布尔代数为n维的。维的。结论结论1 设设e1，en为布尔代数为布尔代数B的一组基底，的一组基底，则对于则对于 i1,1,n,n,ei0。证明：证明：用反证法。若有用反证法。若有ei=0，则一方面，则一方面，ei=0e1+0e2+0ei+0en，另一方面，另一方面，ei=0e1+0e2+1ei+0en，而而eiB，且表示方法不唯一。这与定义中任意，且表示方法不唯一。这与定义中任意aB,都可唯一地表示为都可唯一地表示为1e1+2e2+nen矛盾。因此，矛盾。因此，ei0，i=1，n。结论结论2.设设e1，en为布尔代数为布尔代数B的一组基底，的一组基底，则对于，如果则对于，如果ij，那么，那么eiej。证明：证明：用反证法。若存在用反证法。若存在ij，而，而ei=ej，不妨设，不妨设ij，则有，则有 ei=0e1+0e2+1ei+0ej+0en，ei=ej=0e1+0e2+0ei+1ej+0en，显然与显然与ei表示方法唯一矛盾。表示方法唯一矛盾。例例.设设S30是是30的所有正因数做成的集合。的所有正因数做成的集合。对任意对任意a，bS30，规定运算，规定运算a+b 为为a、b的最小的最小公倍数，公倍数，ab 为为a、b的最大公约数。的最大公约数。则（则（S30，+，1，30）是布尔代数，）是布尔代数，1是是其最小元素，其最小元素，30是其最大元素。该布尔代数的是其最大元素。该布尔代数的基底为基底为2，3，5：1=(12)+(13)+(15)，2=(302)+(13)+(15)，3=(12)+(303)+(15)，5=(12)+(13)+(305)，6=(302)+(303)+(15),10=(302)+(13)+(305)，15=(12)+(303)+(305)，30=(302)+(303)+(305)。定义定义.设（设（B，+，0，1）是布尔代数。若）是布尔代数。若B中非零元素中非零元素a有性质：对任意有性质：对任意B，a或者或者为为0，或者为，或者为a，则称，则称a为布尔代数的极小元素。为布尔代数的极小元素。结论结论3 若若a，b为布尔代数中的两个不同的极小元为布尔代数中的两个不同的极小元素，必有素，必有ab=0。证明：证明：用反证法。若用反证法。若a，b为布尔代数中的两个不为布尔代数中的两个不同的极小元素，而同的极小元素，而ab0，则一方面由，则一方面由a为极小为极小元素知，元素知，ab=a；另一方面，另一方面，由由b为极小元素为极小元素知，知，ab=b。于是，。于是，a=b，与，与ab矛盾。矛盾。引理引理1 设设B是布尔代数，是布尔代数，a是是B中任一非零元素。中任一非零元素。若若a不是极小元素，则存在极小元素不是极小元素，则存在极小元素b，使，使ba。证明：证明：因为因为a不是极小元素，所以有非零元素不是极小元素，所以有非零元素0，使得使得ax0 0，且，且ax0 a。令令ax0=a1，显然，显然，a1a。若若a1仍不是极小元素，则有非零元素仍不是极小元素，则有非零元素1，使，使a110，且且a1x1a1。令令a1x1=a2，显然，显然，a2a1。重复上述过程，由于重复上述过程，由于B中元素有限，故最后可找中元素有限，故最后可找到极小元素到极小元素an，使得，使得 an an-1 a2 a1 a 定理定理8.5.3 有限布尔代数的基底必是此代数的所有限布尔代数的基底必是此代数的所有极小元素；反之，此代数的所有极小元素有极小元素；反之，此代数的所有极小元素必然做成此代数的基底。必然做成此代数的基底。证明：（证明：（1）设设e1，en是是B的基底。的基底。往证每个往证每个ei都是极小元素。都是极小元素。若若ei不是极小元素不是极小元素,则在则在B中可找到元素中可找到元素a,使得使得 aei=b0，且，且bei。显然，显然，bei。令令b=1e1+iei+nen。取。取c=ei，因为因为bei=b，所以，所以，b+c=bei+ei=ei。令。令 c=1e1+iei+nenbb于是有于是有 ei=b+c=（1+1）e1+（n+n）en由基底的性质，则必有由基底的性质，则必有j+j=0 （ji，j=1，n）i+i=1 亦即：亦即：j=j=0（ji，j=1，n），），i=1或者或者i=1。若若i=1，则，则b=ei，矛盾。，矛盾。若若i=1，则，则c=ei，即，即 ei=ei，所以，所以 0=（b ）ei=b（ei）=bei=b矛盾。所以矛盾。所以ei是极小元素。是极小元素。bbb往证往证B的每一个极小元素，都必是基底中某一的每一个极小元素，都必是基底中某一元素。元素。设设e*是是B的一个极小元素，令的一个极小元素，令 e*=1e1+nen因为因为e*0，故不妨设，故不妨设j0（ji），于是），于是 e*ej=ej，因为因为e*是极小元素，所以是极小元素，所以e*=ej。（2）设设e1，en是是B中所有极小元素。中所有极小元素。往证往证ei可由可由e1，en唯一线性表示唯一线性表示首先首先ei可由可由e1，en做如下线性表示：做如下线性表示：ei=0e1+1ei+0en并且此表示是唯一的。若不然，令并且此表示是唯一的。若不然，令 ei=1e1+nen其中至少有一个其中至少有一个j0（ji），于是），于是 0=eiej=jej=ej矛盾。矛盾。设设a a是是B B中任一非极小元素。令所有中任一非极小元素。令所有a a的极小元的极小元素（由引理素（由引理1 1知，这是存在的）为知，这是存在的）为 （1 1i i1 1 iik kn n）往证往证 a=a=令令 =b=b，显然，显然baba。kiiee,1kiiee1kiiee1反证。反证。若若ba，则，则 a0（否则，将推出（否则，将推出ab），），于是，由引理于是，由引理1知，必有极小元素知，必有极小元素ej a，因为，因为 aa，所以，所以eja。因此，。因此，ej必必是是 中某一个。中某一个。设设ej=（1lk）。因为）。因为ej=a，所以，所以而而 ，故，故 ，即，即 ，即即 =0，矛盾，矛盾.故故b=a，即，即a=。bbbkiiee,1lielieblliieeab)(lliiebelliiebaeb)(lliieabeb)(liekiiee1 唯一性。又设唯一性。又设a=，不妨设，不妨设 （对所有的（对所有的p=1，k）。）。于是于是 ，而，而 ，故，故 =0矛盾，所以矛盾，所以a的线性表示是唯一的。的线性表示是唯一的。证毕。证毕。推论推论1 若（若（B，+，0，1）是布尔代数，其）是布尔代数，其基底基底e1，en，则，则e1+e2+en=1。推论推论2 有限布尔代数的基底是唯一的。有限布尔代数的基底是唯一的。rjjee11jepie11jjeae0)(11kiijeee1je定义定义.设（设（B，+，0，1）和）和（S，）是两个布尔代数，）是两个布尔代数，B到到S的映射的映射，称为两个布尔代数间的同态映射，称为两个布尔代数间的同态映射，如果对任意如果对任意a，bB，有，有 （ab）=（a）（b）（a+b）=（a）（b）（）=（a）（0）=（1）=显然显然（B）是）是S的子代数。称布尔代数的子代数。称布尔代数（B）是）是布尔代数布尔代数B的同态象。如果的同态象。如果B到到S上的同态映射上的同态映射是一对一映射，则称是一对一映射，则称为同构映射，也称为同构映射，也称B与与S同同构。构。a引理引理2 设设是布尔代数（是布尔代数（B，+，0，1）到布尔代数（到布尔代数（S，）的一个）的一个映射。如果对任意映射。如果对任意a，bB，都有，都有（ab）=（a）（b）（）=（a）则则是是B到到S的同态映射。的同态映射。a引理引理3 设设是布尔代数（是布尔代数（B，+，0，1）到）到布尔代数（布尔代数（S，）的一个）的一个映射，如果对任意映射，如果对任意a，bB，都有，都有（ab）=（a）（b）（a+b）=（a）（b）则（则（B），），（0），），（1）是一个布尔代数，且是一个布尔代数，且是是B到到（B）的同态映射。）的同态映射。其中其中是关于是关于（0），），（1）的余运算。）的余运算。引理引理4 设（设（B，+，0，1）和）和（S，）是两个布尔代）是两个布尔代数。数。是是B到到S上的映射（即上的映射（即（B）=S）。）。如果对任意如果对任意a，bB，都有，都有（ab）=（a）（b）（a+b）=（a）（b）则则是是B到到S上的同态映射。上的同态映射。定理定理8.5.6 如果两个有限布尔代数的维数相同，如果两个有限布尔代数的维数相同，则这两个代数同构。则这两个代数同构。证明：证明：设布尔代数（设布尔代数（B，+，0，1）和（）和（S，）都是）都是n维的，其基底分维的，其基底分别为别为e1，en和和u1，un。作作B到到S的映射的映射如下：如下：ei ui i=1，n。其中：其中：是是a1+an的缩写；的缩写；是是b1bn的缩写；的缩写；ffniiie1)1(niifiu1)2(niia1)1(niib1)2(i=0或或1；由基底的性质，不难说明映射由基底的性质，不难说明映射是是B到到S上的一对上的一对一的映射，且一的映射，且（B）=S。对任意对任意a，bB，不妨设，不妨设 a=b=于是于是 （a）=（b）=.,11,0,niiifi当当niiie1)1(niiie1)1(niifiu1)2(niifiu1)2(所以（a+b）=（a）（b）同理可证得：（ab）=（a）（b）.由引理4知，B与S同构。)(1)1(niiiefniifiiu1)2()(niififiu1)2()(niifiniifiuu1)2(1)2()()(定理定理8.5.7 任意任意n维布尔代数维布尔代数(B,+,0,1)与开关与开关代数（代数（Bn，+，0n，1n）同构。）同构。证明：证明：因为（因为（1，0，0），（），（0，1，0，0），），（，（0，0，1）n个向量是个向量是Bn的一的一组基底，故组基底，故Bn是是n维的，由定理维的，由定理8.5.6知，知，B与与Bn同构。同构。定理定理8.5.8（Stone定理）定理）任意有限布尔代数任意有限布尔代数（B，+，0，1）与某个集合）与某个集合S的幂集合的幂集合做成的布尔代数（做成的布尔代数（(S)，S）同构。同构。证明：证明：设布尔代数设布尔代数B的基底为的基底为e1，en。令集合令集合S=e1，en.显然，布尔代数（显然，布尔代数（(S)，S）的）的基底为基底为e1，e2，en，故，故（s）是）是n维的，维的，由定理由定理8.5.6知，知，B与与（s）同构。）同构。