離散數(shù)學(xué)：7 格與布爾代數(shù)(簡(jiǎn)化版)

1、第七章 格與布爾代數(shù)集合代數(shù)：(S),)對(duì)A,B,C(S)，運(yùn)算，滿足：等冪律 AA = A， AA = A，交換律 AB = BA， AB = BA，結(jié)合律 A(BC)=(AB)C， A(BC)=(AB)C，分配律 A(BC)=(AB)(AC)， A(BC)=(AB)(AC)，吸收律 A(AB)=A， A(AB)=A若引進(jìn)余集的概念，有De Morgan定律:命題代數(shù)（S，）對(duì)A,B,CS，運(yùn)算，滿足：等冪律 AA = A， AA = A， ，交換律 AB = BA，AB = BA 結(jié)合律 A（BC）=（AB）C， A（BC） = （AB）C 分配律 A(BC)=(AB)(AC)， A（BC

2、） = （AB） （AC） 吸收律 A(AB)=A，A（AB）=A， 若引進(jìn)否定的概念，有De Morgan定律:(AB )= AB, (AB )= AB, 7.2 格 的 定 義 偏序（半序）格(定義A )給出一個(gè)偏序集（L,），如果對(duì)于任意a,bL，L的子集a, b在L中都有一個(gè)最大下界(記為infa, b)和一個(gè)最小上界（記為supa, b），則稱（L，）為一個(gè)格。 半序格的例例. S是任意一個(gè)集合，(S)是S的冪集合， 則，部分序集(S)，)是一個(gè)格。因?yàn)閷?duì)A, B(S)，supA, B=AB(S), infA,B=AB(S)例.設(shè)I+是所有正整數(shù)集合，D是I+中的“整除關(guān)系”，對(duì)任意

3、a，bI+，aDb當(dāng)且僅當(dāng)a整除b，于是，（I+，D）是一個(gè)格。supa,b=a，b的最小公倍I+，infa,b= a，b的最高公因I+ 。 半序格的例例. 設(shè)n是一個(gè)正整數(shù)，Sn是n的所有正因數(shù)的集合，于是，（Sn，D）是格。因?yàn)閟upa,b=a，b的最小公倍 Sn，infa,b= a，b的最高公因 Sn。例. 設(shè)S是所有的命題集合，定義“ ” 如下：A B 當(dāng)且僅當(dāng) B蘊(yùn)涵A。則（S，）是一個(gè)格。因?yàn)閟upA，B=ABS， infA，B=ABS。 半序子格定義A 設(shè)（L，）是格，S L，如果（S，）是格，則稱（S，）是格（L，）的子格。 例.（S6，D）是（S24，D）的子格。 代數(shù)格定義

4、B 設(shè)L是一個(gè)集合，是L上兩個(gè)二元代數(shù)運(yùn)算，如果這兩種運(yùn)算對(duì)于L中元素滿足： （1）交換律：ab=ba，ab=ba。 （2）結(jié)合律：a（bc）=（ab）c， a（bc）=（ab）c。 （3）吸收律：a（ab）=a， a （ab）=a。則稱此代數(shù)系統(tǒng)（L，）為一個(gè)格。 note:設(shè)(L, , )是格，則(L, )和(L, )均為交換半群。定義B中由， 滿足吸收律可推出它們一定滿足等冪律。證明：任取L中元素a，由，滿足吸收律知，a(aa)=a， a (aa)=a。故aa=a(a(aa)， aa=a(a(a a)。又由，滿足吸收律知，上面兩式的等式右端都等于a。因此， aa = a， a a = a

5、。即， 定義B中的，運(yùn)算亦滿足等冪律。代數(shù)格的例例. 設(shè)S是一個(gè)集合,(S)是S的冪集合，于是，(S),)是一個(gè)代數(shù)格。而(S)，)是半序格。易見(jiàn)對(duì)A,B(S)， A B AB = A AB = B。例. 設(shè)I+是所有正整數(shù)集合, 兩個(gè)正整數(shù)的最高公因, 最小公倍是I+上兩個(gè)代數(shù)運(yùn)算，于是, (I+, ,)是一個(gè)代數(shù)格。而（I+,D）是半序格, D是整除關(guān)系。易見(jiàn)，對(duì)任意a，bI+, a D b ab = a ab = b。例. 設(shè)n是一個(gè)正整數(shù),Sn是n的所有正因數(shù)的集合,兩個(gè)正整數(shù)的最高公因,最小公倍是Sn上兩個(gè)代數(shù)運(yùn)算,于是,(Sn,)是一個(gè)代數(shù)格。 代數(shù)格與半序格的等價(jià)性定理7.2.1

6、 定義A所定義的格和定義B所定義的格是等價(jià)的，亦即，一個(gè)半序格必是一個(gè)代數(shù)格；反之亦然。證明：i）若(L,)是一個(gè)半序格,則對(duì)a,bL，記infa,b為ab； supa, b為ab。由于對(duì)任意a，b，其infa, b，supa, b是唯一的，所以，如上定義的，是集合L上的兩種二元代數(shù)運(yùn)算。 不難證明：對(duì)于,滿足交換律、結(jié)合律、吸收律。則根據(jù)定義B，(L,)是一個(gè)代數(shù)格。 只證明吸收律中的一條： a（ab）=a其它算律的證明作為課后練習(xí)。因?yàn)閍(ab)是a與(ab)的最大下界，所以a(ab)a另一方面，由于aa，aab，所以，a是a與ab的下界，故aa(ab)所以，a=a(ab)。證明證明ii）

7、若代數(shù)系統(tǒng)（L, , ）是一個(gè)代數(shù)格，在集合L上定義一個(gè)關(guān)系如下：對(duì)任意a，bL， ab ab=a往證：是一個(gè)半序關(guān)系。反身性:因?yàn)閍a=a(a(aa)= a, 所以aa。反對(duì)稱性:若有ab,ba,則應(yīng)有ab=a，ba=b，而ab = ba，所以a=b。傳遞性:若ab，bc，則有ab=a，bc=b，故ac=(ab)c=a(bc)=ab=a，亦即，ac。往證：ab = a a b = b。若ab = a，則 ab = （ab） b = b。若ab = b，則 ab=a（ab）=a。往證:對(duì)任意a, bL, a,b在L中必有infa, b, supa, b，且就是ab和ab.由吸收律知 a（ab）

8、= a， b（ab）= b，故有a（ab），b（ab）。亦即，ab是a，b的上界。證明若cL，且c是a，b的上界，亦即有ac，bc，則應(yīng)有 ac=c，bc=c，于是，（ab）c =a（ bc） =ac =c故有（ab）c。因此，（ab）是a，b的最小上界，即supa，b=（ab）。同理可證，infa，b=（ab）。綜上，（L，）為半序格。 代數(shù)子格定義B 設(shè)(L,)是一個(gè)代數(shù)格，S L，(S,)稱為(L,)的一個(gè)代數(shù)子格，當(dāng)且僅當(dāng)在運(yùn)算,下，S是封閉的。結(jié)論：(S,)是格(L,)的子格的充要條件是：SL 且（S,）是一個(gè)格。 例.(Sn, ,)是(I+,)的代數(shù)子格，其中,分別是最高公因和最小

9、公倍運(yùn)算。代數(shù)子格與半序子格的關(guān)系設(shè)(L，)是一個(gè)半序格，與其等價(jià)的代數(shù)格為(L,)，S L。若(S,)是(L, , )的代數(shù)子格，則（S，）是（L，）的半序子格；若（S，）是（L，）的半序子格，則(S,)不一定是(L, , )的代數(shù)子格。 a3a5a1a2a4a6a7a8設(shè)L=a1,a2,a3,a4,a5,a6,a7,a8,（L,）是格。(1)取S1=a1,a2,a3,a4,則（S1，）是（L，）的半序子格，也是（L,）的代數(shù)子格。(2)取S2=a1,a2,a4,a7,則(S2 ，)是(L，)的半序子格,但(S2,)不是(L,)的代數(shù)子格。因?yàn)?a2a4=a3，而a3S2， 即，S2在下不封

10、閉。7.3 格的性質(zhì)7.3.1 格 的 性 質(zhì) 7.3.2 格的同態(tài)與同構(gòu)7.3.1 格 的 性 質(zhì)定理7.3.1 設(shè)（L，）是一個(gè)格，a，b是L中任意元素，于是 ab ab = a a b = b定理7.3.2 設(shè)（L，）是一個(gè)格，a，b，c是L中任意元素，如果bc，則有 abac, abac定理7.3.3 設(shè)（L，）是一個(gè)格，a，b，c是L中任意元素。于是有 a（bc） （ab）（ac） a（bc）（ab）（ac）Note:在一般格中，分配律不是總成立的，但上述分配不等式總是成立的。因?yàn)閍2（a1a3）= a2 （a2a1）（a2a3）=a3只有對(duì)特殊的格（分配格、模格）分配律才成立 a2

11、a301a17.3.1 格 的 性 質(zhì)定理7.3.4 設(shè)（L，）是一個(gè)格，a，b，c是L中任意元素，于是， ab a（bc）b（ac）7.3.1 格 的 性 質(zhì) 7.3.2 格的同態(tài)與同構(gòu)定義. 設(shè)(L,)和(S,)是兩個(gè)格，L到S內(nèi)的映射g稱為(L,)到(S,)的格同態(tài)映射，如果對(duì)任意a，bL，都有 g（ab）= g（a）g（b） g（ab）= g（a）g（b）.定義. 格L到L內(nèi)的同態(tài)映射稱為格的自同態(tài)映射。定義. 若g是L到S上的同態(tài)映射，且是一對(duì)一的，則稱g是格同構(gòu)映射，并稱格L與格S是同構(gòu)的。此時(shí)，對(duì)任意xL，任意yS ，有 g-1(g(x)=x，g(g-1(y)=y。 同態(tài)映射例例

12、. 設(shè)S=a, b,(S)=, a, b, a,b，則(S), , )是一個(gè)格。設(shè)L=0，1，規(guī)定01，分別是集合L中兩個(gè)元素在下的最大下界，最小上界運(yùn)算，則（L,）是一個(gè)格。規(guī)定映射g為：g(a) = 1， g(a, b) = 1， g(b) = 0， g() = 0。則顯然g是(S)到L上的同態(tài)映射.格的同態(tài)映射一定是保序映射定理7.3.5 設(shè)(L,)和(S,)是兩個(gè)格。集合L上對(duì)應(yīng)于運(yùn)算，的部分序?yàn)長(zhǎng)，集合S上對(duì)應(yīng)于運(yùn)算，的部分序?yàn)閟。如果g是L到S內(nèi)的同態(tài)映射，則g是保序映射，亦即，對(duì)任意a，bL，若aLb，則g（a）sg（b）。例子同態(tài)具有保序性，但其逆不一定成立，保序映射不一定是同

13、態(tài)的。下面給出3個(gè)格L1, L2, L3。定義映射1, 2和3：1：L1L2, 1(a)= 1(b)= 1(c)=a1, 1(d)=d1.2：L1L2, 2(b)= 2(c)= 2(d)=d1, 2(a)=a1.3：L1L3, 3(a)=a2, 3(b)=b2, 3(c)=c2, 3(d)=d2.c2b2a2d2L3d1a1L2cabdL1例子可以看出這3個(gè)映射都是保序的，但都不是同態(tài)的。因?yàn)?(bc)= 1(d)=d1, 1(b) 1(c)= a1 a1=a1,2(bc)= 2(a)=a1, 2(b) 2(c)= d1 d1=d1,3(bc)= 3(d)=d2, 3(b) 3(c)=b2 c

14、2=c2, 定理7.3.6 設(shè)(L,)是一個(gè)格，g是此格的自同態(tài)映射，于是g(L)是(L, , )的代數(shù)子格。證明： 任取a,bg(L),則必有a,bL, 使 a= g（a）， b= g（b）因?yàn)間是格（L，）的自同態(tài)映射，所以 ab=g(a)g(b)= g(ab)g(L)， ab= g(a)g(b)=g(ab)g(L)。即在運(yùn)算，下，g（L）是封閉的。故（g（L）， ，）是（L，）的代數(shù)子格。 定理7.3.7 設(shè)(L,), (S,)是兩個(gè)格，若g是L到S上的同構(gòu)映射，則g的逆映射g-1是S到L上的同構(gòu)映射。證明： 顯然g-1是S到L上的一對(duì)一映射。下面證明g-1是S到L上的同態(tài)映射。任取a,

15、bS,令g-1(a)=a,g-1(b)=b。于是g（a）= a， g（b）= b。g-1(ab)=g-1(g(a)g(b)=g-1(g(ab) = ab =g-1(a)g-1(b)。g-1(ab)= g-1(g(a)g(b)=g-1(g(ab) = ab= g-1（a）g-1（b）。故g-1是S到L上的同構(gòu)映射。 推論 若格(L,)和格(S, ,)同構(gòu)，g是其同構(gòu)映射，則對(duì)L中任意兩個(gè)元素a，b，有aLb g（a）sg（b）其中L，S分別是集合L，S上對(duì)應(yīng)于運(yùn)算，的部分序關(guān)系。 a,b,ca,ba,cb,cab維格 設(shè)L=0, 1，規(guī)定01。于是，(L, )是格。令(

16、L, ,)是與之等價(jià)的代數(shù)格。令 Ln=(a1，an)aiL，i=1，n規(guī)定：(a1,an )n ( b1,bn ) aibi (i=1,n)不難證明：(Ln，n)是一個(gè)格，通常稱為n維格。令與(Ln，n)等價(jià)的代數(shù)格為(Ln,)，對(duì)Ln中任意兩個(gè)元素(a1,an)，(b1,bn)，顯然有(a1,an)(b1,bn)=(a1b1,anbn)(a1,an)(b1,bn)=(a1b1,anbn)。 7.4.1 有 界 格 7.4.2 有 余 格 7.4.3 分 配 格 7.4.4 模 格7.4 幾種特殊的格7.4.1 有 界 格 引理1 設(shè)(L，)是一個(gè)格。若S是L的任意一個(gè)有限非空子集，則S有一

17、個(gè)最大下界和一個(gè)最小上界。記集合S的最大下界為inf S； 集合S的最小上界為sup S。 Note: 對(duì)于格的一個(gè)無(wú)窮子集，引理1的結(jié)論不成立。 例.在格（I+，）中，所有正偶數(shù)組成的集合記為E+，顯然，E+ I+，但E+沒(méi)有最小上界。定義. 格（L，）稱為有界格，如果它有一個(gè)最大元素（記為1）和一個(gè)最小元素（記為0），亦即，對(duì)任意aL，都有 0a1 0，1稱為格（L，）的界。 結(jié)論：有限格必是有界格 令L=a1，an , 0 = a1a2an, 1 = a1a2an 引理2. 若（L, 0, 1）是有界格，則對(duì)任意aL，恒有 a 0 = a， a1 = a， a 1 = 1， a0 = 0

18、。 7.4.1 有 界 格 定義. 在有界格（L，0，1）中，一個(gè)元素bL，稱為元素aL的余元素，如果 ab = 0， ab = 1。ab10ab10ac10ba,b均無(wú)余a有唯一余bc有兩個(gè)余a,b在有界格（L, 0, 1)中，1是0的唯一一個(gè)余元素，反之亦然。7.4.2 有 余 格 定義. 稱有界格（L，0，1）是一個(gè)有余格，如果對(duì)L中每一個(gè)元素，都至少有一個(gè)余元素。例. 設(shè)S是有n個(gè)元素的集合，(S)是S的冪集合，于是，（S），）是有余格。其中， 和S是此格的界.對(duì)（S）中任意元素A，（S）中的元素S-A是其余元素。a,b,ca,ba,cb,cabc7.4.3 分 配 格 定義7.4.4

19、 格（L,）稱為分配格，如果對(duì)任意a，b，cL，恒有a(bc)=(ab)(ac)a(bc)=(ab)(ac)Note: (1)分配格定義中的兩個(gè)等式是等價(jià)的(ab)(ac)(aa)(ac)(ba)(bc)a(ac)(ab)(bc)a(a(cb) )(bc)a(bc)7.4.3 分 配 格 Note: (2) n維格(Ln, n)，格(S), )，(I+, D)，(Sn, D)都是分配格。 但不是所有的格都是分配格 (3)分配格的任意子格仍是分配格。 證明：設(shè)格（L，）是一個(gè)鏈，任取a, b, c L, 1）若ab且ac，于是abc，故 a(bc)= bc而ab = b，ac = c，所以 (a

20、b)(ac)= bc故a(bc)=(ab)(ac)。2）若ab或者ac，于是a(bc)，故a(b c)= a。而 (ab)(ac)= a所以a(bc)=(ab)(ac)。 引理4 任意一個(gè)鏈都是一個(gè)分配格De Morgan定律定理7.4.1 設(shè)（L,）是一個(gè)分配格，對(duì)任意a,bL，若a，b有余元素a,b，則 (ab)= ab (ab)= ab證明： (ab)(ab)=(aba)(abb) =(1b)(a1)= 11 = 1而(ab)(ab)=(aab)(bab) =(0b)(0a)= 00 = 0故由余元素定義知， (ab)= ab同理可證另一等式。例子圖中L1和L2是分配格，但L3, L4不

21、是。因?yàn)樵贚3中 b(cd)=b e=b和(b c) (b d)=a a=a；在L4中d(bc)=d e=d和(d b) (d c)=a c=c。L3稱為鉆石格， L4稱為五角格。cbadL1cbadcbadcbadeeL3L2L4定理7.4.2 設(shè)格（L,）是分配格，對(duì)任意a,b,cL，如果 ac = bc， ac = bc，則a = b。證明：若（L,）是分配格，且ac=bc，ac=bc，則a = a(ac)= a(bc) =(ab)(ac) =(ab)(bc)= b(ac) = b(bc)= b 定理7.4.2 設(shè)格（L,）是一個(gè)有余分配格，則對(duì)任意aL，a的余元素a是唯一的。證明： 因

22、（L,）是有余格，設(shè)a和a都是a的余元素，即 aa= 0， aa= 1 aa= 0， aa= 1故aa= aa，aa= aa。由定理8.4.2知，a= a。 推論 7.4.4 模 格 定義7.4.5 設(shè)(L,)是一個(gè)格，對(duì)任意a, b, cL，如果ab，都有a(bc)= b(ac)則稱（L，）為模格。例子與結(jié)論格L1、L2和L3都是模格，但L4不是。因?yàn)閏 d, 但c (bd)=c,(cb) d=d 一個(gè)格L是模格當(dāng)且僅當(dāng)L不含與五角格同構(gòu)的子格。一個(gè)模格是分配格當(dāng)且僅當(dāng)L不含與鉆石格同構(gòu)的子格cbadL1cbadcbadcbadeeL3L2L4Note:(1)任意一個(gè)分配格都是模格， 由ab

23、， ab=b, 故 a(bc)=(ab)(ac) = b(ac)(2)模格不一定是分配格。如圖所示L=0, 1, a, b, c。則格(L,)是模格，但不是分配格，因?yàn)?a(bc)= a(ab)(ac)= 0。 ba0c1cb0d1不是模格也不是分配格是模格不是分配格定理7.4.3定理7.4.3 格(L，)是模格的充要條件是：對(duì)任意a，b，cL，如果ab，ac=bc，ac=bc則必有a=b。證明：必要性。若格（L，）是模格，則對(duì)任意a，b，cL，如果ab，ac=bc，a c=b c，則a = a （ac）= a （bc） = b（ac）= b（bc）= b充分性。任取a，b，cL，且ab。因?yàn)?/p>

24、(a(bc) c = a (bc)c)=ac 又因?yàn)閍b，所以ab(ac)，故a c(b(ac)c (a c) c = ac所以，(b(a c) c = a c。因此(a(bc)c =(b(ac)c (1)亦即，在格（L，）中，若ab，則有（1）式。 定理7.4.37.5 布 爾 代 數(shù)7.5.1 布爾代數(shù)的定義及其性質(zhì) 7.5.2 有限布爾代數(shù)的表示理論7.5.3 布爾代數(shù)的同態(tài)與同構(gòu)7.5.1 布爾代數(shù)的定義及其性質(zhì)定義. 一個(gè)有余分配格是一個(gè)布爾代數(shù)。記為（B，+，0，1）。a，b，c是集合B中任意元素，有如下性質(zhì):（一）因?yàn)椋˙，+）是一個(gè)格，有1）aa= a， 1）a+a = a。2

25、）ab=ba， 2）a+b = b+a。3）(ab)c=a(bc)， 3）(a+b)+c=a+(b+c)。4）a（a+b）= a, 4）a+（ab）= a。 （二） 因?yàn)椋˙，+）是分配格，所以有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。 （三）因?yàn)椋˙，+，0，1）是有界格，所以 有 8）0a1。 9） a0 = 0， 9）a+1 = 1。 10）a1 = a， 10）a+0 = a。布爾代數(shù)的性質(zhì)（四） 因?yàn)椋˙，+，0，1）是有余分配

26、格，所以有11） 11）12） 12）13） 13） （五） 因?yàn)椋˙，）是半序格，所以有14）ab = infa，b 14）a+b = supa，b。15）ab a+b = b ab = a。16）布爾代數(shù)的性質(zhì)Huntington公理 定理7.5.1 設(shè)B是一個(gè)至少含有兩個(gè)不同元素的集合，+是定義在B上的兩種代數(shù)運(yùn)算，如果對(duì)任意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,使得對(duì)任意aB,有 a1 = a, a+0 = a。 H4： 對(duì)任意aB，有 B，使得 則

27、（B，+，0，1）是一個(gè)布爾代數(shù)。 布爾代數(shù)的例電路代數(shù) （B，+，0，1） 其中B=0，1, B上的運(yùn)算+，如下表定義：集合代數(shù) （S），S） 其中S是一個(gè)非空集合。01000101+01001111x0110 命題代數(shù)（S，F(xiàn)，T）其中S是命題公式的集合。 開(kāi)關(guān)代數(shù) （Bn，+，0n，1n）其中Bn是由0，1做分量的所有n元向量集合。對(duì)任意a,bBn,令a=(a1，an)，b=(b1，bn)，定義Bn上的運(yùn)算如下：ab=（a1b1，a2b2，anbn）a+b =（a1+b1，a2+b2，an+bn）0n表示n個(gè)0做成的n元向量(0，0)，1n表示n個(gè)1做成的n元向量(1，1) 。 子代數(shù)定

28、義 任給一個(gè)布爾代數(shù) (B, , +, , 0, 1)。若B的一個(gè)子集S包含0和1, 且(S，+，0，1)仍是一個(gè)布爾代數(shù),則稱S為B的子代數(shù)。例. 設(shè)S = a，b，c，則(S), , S)是一個(gè)布爾代數(shù)。(1)設(shè)S1=,a,b,c,a,b,c，則(S1, , S)是(S), , S)的子代數(shù)。定理7.5.2 設(shè)（B，+，0，1）是布爾代數(shù)。于是，B的子集S是B的子代數(shù)的充要條件是S在運(yùn)算 ，+，下是封閉的。7.5.2有限布爾代數(shù)的表示理論 基 底設(shè)（B，+，0，1）是布爾代數(shù)，e1，en是B中有如下性質(zhì)的一組元素, 對(duì)任意aB，都可唯一地表示為 a =1e1+2e2+nen其中i或?yàn)?，或

29、為1，（i = 1，n）。則稱e1，en為布爾代數(shù)B的一組基底，并稱此布爾代數(shù)為n維的。 結(jié)論1 設(shè)e1，en為布爾代數(shù)B的一組基底，則對(duì)于 i1,n, ei0。證明： 用反證法。若有ei = 0，則一方面，ei = 0e1 + 0e2 + +0ei + + 0en，另一方面，ei = 0e1 + 0e2 + +1ei + + 0en，而eiB，且表示方法不唯一。這與定義中任意aB,都可唯一地表示為1e1+2e2+ +nen矛盾。因此，ei0，i=1，n。 結(jié)論2. 設(shè)e1，en為布爾代數(shù)B的一組基底，則對(duì)于，如果ij，那么eiej。證明： 用反證法。若存在ij，而ei=ej，不妨設(shè)ij，則有

30、 ei = 0e1 + 0e2 + +1ei + 0ej + + 0en， ei = ej= 0e1 + 0e2 + +0ei + 1ej + + 0en， 顯然與ei表示方法唯一矛盾。 例. 設(shè)S30是30的所有正因數(shù)做成的集合。對(duì)任意a，bS30，規(guī)定運(yùn)算a + b 為a、b的最小公倍數(shù)，ab 為a、b的最大公約數(shù)。則（S30，+，1，30）是布爾代數(shù)，1是其最小元素，30是其最大元素。該布爾代數(shù)的基底為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)。 極小元定義. 設(shè)（B，+，0，1）是布爾代數(shù)。若B中非零元素a有性質(zhì)：對(duì)任意B，a或者為0，或者為a，則稱a為布爾代數(shù)的極小元素。結(jié)論3 若a，b為布爾代數(shù)中的兩個(gè)不同的極小元素，必有ab=0。證明：用反證法。若a，b為布爾代數(shù)中的兩個(gè)不同的極小元素，而ab0，則一方面由a為極小元素知，ab = a； 另一方面， 由b為極小元素知，ab = b。于是，a=b，與ab矛盾。 引理1 設(shè)B是布爾代數(shù)，a是B中任一非零元素。若a不是