離散數(shù)學(xué)格與布爾代數(shù)-課件

第11章格與布爾代數(shù)離散數(shù)學(xué)中國地質(zhì)大學(xué)本科生課程第11章格與布爾代數(shù)離散數(shù)學(xué)中國地質(zhì)大學(xué)本科生課程本章內(nèi)容11.1 格的定義與性質(zhì)11.2 分配格、有補(bǔ)格與布爾代數(shù)

本章總結(jié)

作業(yè)本章內(nèi)容11.1 格的定義與性質(zhì)211.1格的定義與性質(zhì)定義11.1設(shè)<S,≤>是偏序集，如果

x,y∈S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序≤作成一個格(lattice)。說明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x與y的二元運算∨和∧。

x∨y：表示x與y的最小上界

x∧y：表示x和y的最大下界。

本章出現(xiàn)的∨和∧符號只代表格中的運算，而不再有其它的含義。11.1格的定義與性質(zhì)定義11.1設(shè)<S,≤>是偏序3格的實例例11.1設(shè)n是正整數(shù)，Sn是n的正因子的集合。D為整除關(guān)系，則偏序集<Sn,D>構(gòu)成格。

x,y∈Sn， x∨y是lcm(x,y)，即x與y的最小公倍數(shù)。 x∧y是gcd(x,y)，即x與y的最大公約數(shù)。 下圖給出了格<S8,D>，<S6,D>和<S30,D>。格的實例例11.1設(shè)n是正整數(shù)，Sn是n的正因子的集合。D4例11.2例11.2判斷下列偏序集是否構(gòu)成格,并說明理由。 (1)<P(B),

>，其中P(B)是集合B的冪集。 (2)<Z,≤>，其中Z是整數(shù)集,≤為小于或等于關(guān)系。 (3)偏序集的哈斯圖分別在下圖給出。例11.2例11.2判斷下列偏序集是否構(gòu)成格,并說明理由。5例11.2解答(1)是格。

x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y。 由于∪和∩運算在P(B)上是封閉的，所以x∪y，x∩y∈P(B)。 稱<P(B),

>,為B的冪集格。(2)是格。

x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它們都是整數(shù)。(3)都不是格。 (a)中的{a,b}沒有最大下界。 (b)中的{b,d}有兩個上界c和e,但沒有最小上界。 (c)中的{b,c}有三個上界d,e,f,但沒有最小上界。 (d)中的{a,g}沒有最大下界。例11.2解答(1)是格。6例11.3例11.3設(shè)G是群，L(G)是G的所有子群的集合。即 L(G)＝{H|H≤G} 對任意的H1,H2∈L(G)，H1∩H2也是G的子群，而<H1∪H2>是由H1∪H2生成的子群（即包含著H1∪H2的最小的子群）。 在L(G)上定義包含關(guān)系

，則L(G)關(guān)于包含關(guān)系構(gòu)成一個格，稱為G的子群格。 易見在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是<H1∪H2>。例11.3例11.3設(shè)G是群，L(G)是G的所有子群的集合7對偶原理定義11.2設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。令f*是將f中的≤替換成≥，≥替換成≤，∨替換成∧，∧替換成∨所得到的命題。稱f*為f的對偶命題。例如 在格中令f是(a∨b)∧c≤c，則f*是(a∧b)∨c≥c。格的對偶原理設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。若f對一切格為真，則f的對偶命題f*也對一切格為真。例如

對一切格L都有

a,b∈L，a∧b≤a (因為a和b的交是a的一個下界) 那么對一切格L都有

a,b∈L，a∨b≥a說明 許多格的性質(zhì)都是互為對偶命題的。 有了格的對偶原理，在證明格的性質(zhì)時，

只須證明其中的一個命題即可。對偶原理定義11.2設(shè)f是含有格中元素以及符號＝、≤、≥、8格的運算性質(zhì)定理11.1設(shè)<L,≤>是格，則運算∨和∧適合交換律、結(jié)合律、冪等律和吸收律，即 (1)交換律

a,b∈L有 a∨b＝b∨a a∧b＝b∧a (2)結(jié)合律

a,b,c∈L有 (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (3)冪等律

a∈L有 a∨a＝a a∧a＝a (4)吸收律

a,b∈L有 a∨(a∧b)＝a a∧(a∨b)＝a格的運算性質(zhì)定理11.1設(shè)<L,≤>是格，則運算∨和∧適合9定理11.1(1)a∨b和b∨a分別是{a,b}和{b,a}的最小上界。 由于{a,b}＝{b,a}，所以a∨b＝b∨a。 由對偶原理，a∧b＝b∧a得證。(2)由最小上界的定義有 (a∨b)∨c≥a∨b≥a (13.1) (a∨b)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)∨c≥b∨c (13.4) 再由式13.1和13.4有 (a∨b)∨c≥a∨(b∨c) 同理可證 (a∨b)∨c≤a∨(b∨c) 根據(jù)偏序關(guān)系的反對稱性有 (a∨b)∨c＝a∨(b∨c) 由對偶原理，(a∧b)∧c＝a∧(b∧c)得證。定理11.1(1)a∨b和b∨a分別是{a,b}和{b,a}10定理11.1(3)顯然a≤a∨a, 又由a≤a可得 a∨a≤a。 根據(jù)反對稱性有 a∨a＝a， 由對偶原理，a∧a＝a得證。(4)顯然 a∨(a∧b)≥a (13.5) 又由a≤a，a∧b≤a可得 a∨(a∧b)≤a (13.6) 由式13.5和13.6可得

a∨(a∧b)＝a， 根據(jù)對偶原理，a∧(a∨b)＝a得證。定理11.1(3)顯然a≤a∨a,11定理11.2定理11.2設(shè)<S,*,

>是具有兩個二元運算的代數(shù)系統(tǒng)，若對于*和

運算適合交換律、結(jié)合律、吸收律，則可以適當(dāng)定義S中的偏序≤，使得<S,≤>構(gòu)成一個格，且a,b∈S有a∧b＝a*b，a∨b＝a

b。思路

(1)證明在S中*和運算都適合冪等律。 (2)在S上定義二元關(guān)系R，并證明R為偏序關(guān)系。 (3)證明<S,≤>構(gòu)成格。說明 通過規(guī)定運算及其基本性質(zhì)可以給出格的定義。定理11.2定理11.2設(shè)<S,*,>是具有兩個二元運算12定理11.2a∈S，由吸收律得(1)證明在S中*和運算都適合冪等律。a*a＝a*(a

(a*a))＝a同理有a

a＝a。(2)在S上定義二元關(guān)系R，a,b∈S有<a,b>∈Rab＝b下面證明R在S上的偏序。根據(jù)冪等律，a∈S都有a

a＝a，即<a,a>∈R，所以R在S上是自反的。

a,b∈S有aRb且bRa

a

b＝b且b

a＝aa＝ba＝ab＝b(由于ab=ba)所以R在S上是反對稱的。定理11.2a∈S，由吸收律得(1)證明在S中*和運算都13定理11.2a,b,c∈S有 aRb且bRc ab＝b且bc＝c ac＝a(bc) ac＝(ab)c ac＝bc＝c aRc 這就證明了R在S上是傳遞的。 綜上所述，R為S上的偏序。 以下把R記作≤。定理11.2a,b,c∈S有14定理11.2(3)證明<S，≤>構(gòu)成格。即證明a∨b＝a

b，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab根據(jù)≤的定義有a≤ab和b≤ab，所以ab是{a,b}的上界。假設(shè)c為{a,b}的上界，則有ac＝c和bc＝c，從而有(ab)c＝a(bc)＝ac＝c這就證明了ab≤c，所以ab是{a,b}的最小上界，即a∨b＝ab為證a*b是{a,b}的最大下界，先證首先由ab＝b可知a*b＝a*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤的定義有a≤ba*b＝a，依照前邊的證明,類似地可證a*b是{a,b}的最大下界，即a∧b＝a*b。ab＝ba*b＝a (13.7)定理11.2(3)證明<S，≤>構(gòu)成格。即證明a∨b＝a15格的等價定義根據(jù)定理11.2，可以給出格的另一個等價定義。定義11.3設(shè)<S,*,

>是代數(shù)系統(tǒng)，*和

是二元運算，如果*和

滿足交換律，結(jié)合律和吸收律，則<S,*,

>構(gòu)成一個格(lattice)。說明 格中的冪等律可以由吸收律推出。 以后我們不再區(qū)別是偏序集定義的格，

還是代數(shù)系統(tǒng)定義的格，而統(tǒng)稱為格L。格的等價定義根據(jù)定理11.2，可以給出格的另一個等價定義。16格的性質(zhì)定理11.3

設(shè)L是格，則

a,b∈L有 a≤b

a∧b＝a

a∨b＝b證明

先證a≤b

a∧b＝a 由a≤a和a≤b可知，a是{a,b}的下界， 故a≤a∧b。顯然又有a∧b≤a。 由反對稱性得a∧b＝a。

再證a∧b＝a

a∨b＝b。 根據(jù)吸收律有b＝b∨(b∧a) 由a∧b＝a得b＝b∨a,即a∨b＝b。

最后證a∨b＝b

a≤b。 由a≤a∨b得a≤a∨b＝b。格的性質(zhì)定理11.3設(shè)L是格，則a,b∈L有17格的性質(zhì)定理11.4設(shè)L是格，

a,b,c,d∈L，若a≤b且c≤d，則 a∧c≤b∧d， a∨c≤b∨d證明 a∧c≤a≤b a∧c≤c≤d 因此，a∧c≤b∧d。 同理可證a∨c≤b∨d。格的性質(zhì)定理11.4設(shè)L是格，a,b,c,d∈L，若a≤18例11.5

例11.5設(shè)L是格，證明

a,b,c∈L有 a∨(b∧c)≤(a∨b)∧(a∨c)證明 由a≤a，b∧c≤b得 a∨(b∧c)≤a∨b 由a≤a，b∧c≤c得 a∨(b∧c)≤a∨c 從而得到a∨(b∧c)≤(a∨b)∧(a∨c)說明 在格中分配不等式成立。 一般說來，格中的∨和∧運算并不是滿足分配律的。例11.5

例11.5設(shè)L是格，證明a,b,c∈L有19本節(jié)小結(jié)偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上界。

格的實例：正整數(shù)的因子格，冪集格，子群格。格的性質(zhì)：對偶原理，格中算律（交換、結(jié)合、冪等、吸收），保序性，分配不等式。

格作為代數(shù)系統(tǒng)的定義。格的證明方法本節(jié)小結(jié)偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上20子格定義11.4設(shè)<L,∧,∨>是格，S是L的非空子集，若S關(guān)于L中的運算∧和∨仍構(gòu)成格，則稱S是L的子格。例11.6設(shè)格L如右圖所示。令S1＝{a,e,f,g}S2＝{a,b,e,g}則S1不是L的子格，S2是L的子格。因為對于e和f,有e∧f＝c，但c

S1。子格定義11.4設(shè)<L,∧,∨>是格，S是L的非空子集，若2111.2分配格、有補(bǔ)格與布爾代數(shù)一般說來，格中運算∨對∧滿足分配不等式， 即

a,b,c∈L，有 a∨(b∧c)≤(a∨b)∧(a∨c) 但是不一定滿足分配律。滿足分配律的格稱為分配格。定義11.5設(shè)<L,∧,∨>是格，若

a,b,c∈L，有 a∧(b∨c)＝(a∧b)∨(a∧c) a∨(b∧c)＝(a∨b)∧(a∨c) 則稱L為分配格。說明 上面兩個等式互為對偶式。 在證明L為分配格時，只須證明其中的一個等式即可。11.2分配格、有補(bǔ)格與布爾代數(shù)一般說來，格中運算∨對∧滿22例11.7L1和L2是分配格，L3和L4不是分配格。在L3中， b∧(c∨d)＝b∧e＝b(b∧c)∨(b∧d)＝a∨a＝a在L4中, c∨(b∧d)＝c∨a＝c(c∨b)∧(c∨d)＝e∧d＝d鉆石格五角格例11.7L1和L2是分配格，L3和L4不是分配格。在L3中23分配格的判別定理11.5設(shè)L是格，則L是分配格當(dāng)且僅當(dāng)L中不含有與鉆石格或五角格同構(gòu)的子格。證明 略。推論 (1)小于五元的格都是分配格。 (2)任何一條鏈都是分配格。分配格的判別定理11.5設(shè)L是格，則L是分配格當(dāng)且僅當(dāng)L中24例11.8說明下圖中的格是否為分配格，為什么？L1,L2和L3都不是分配格。{a,b,c,d,e}是L1的子格，并且同構(gòu)于鉆石格。{a,b,c,e,f}是L2的子格，并且同構(gòu)于五角格。{a,c,b,e,f}是L3的子格，也同構(gòu)于鉆石格。

例11.8說明下圖中的格是否為分配格，為什么？L1,L2和25格的全下界和全上界定義11.6設(shè)L是格， 若存在a∈L使得

x∈L有a≤x，則稱a為L的全下界； 若存在b∈L使得

x∈L有x≤b，則稱b為L的全上界。命題 格L若存在全下界或全上界，一定是唯一的。證明 以全下界為例，假若a1和a2都是格L的全下界, 則有a1≤a2和a2≤a1。 根據(jù)偏序關(guān)系的反對稱性必有a1＝a2。記法 將格L的全下界記為0，全上界記為1。格的全下界和全上界定義11.6設(shè)L是格，26有界格定義11.7設(shè)L是格，若L存在全下界和全上界，則稱L為有界格，并將L記為<L,∧,∨,0,1>。說明 有限格L一定是有界格。舉例設(shè)L是n元格，且L＝{a1,a2,…,an}，那么a1∧a2∧…∧an是L的全下界，而a1∨a2∨…∨an是L的全上界。因此L是有界格。對于無限格L來說，有的是有界格，有的不是有界格。如集合B的冪集格<P(B),∩,∪>，不管B是有窮集還是無窮集，它都是有界格。它的全下界是空集，全上界是B。整數(shù)集Z關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，因為不存在最小和最大的整數(shù)。有界格定義11.7設(shè)L是格，若L存在全下界和全上界，則稱L27有界格的性質(zhì)定理（補(bǔ)充）設(shè)<L,∧,∨,0,1>是有界格，則

a∈L有 a∧0＝0 a∨0＝a a∧1＝a a∨1＝1證明 由a∧0≤0和0≤a∧0可知a∧0＝0。說明 在有界格中， 全下界0是關(guān)于∧運算的零元，∨運算的單位元。 全上界1是關(guān)于∨運算的零元，∧運算的單位元。對偶原理對于涉及到有界格的命題，如果其中含有全下界0或全上界1，在求該命題的對偶命題時，必須將0替換成1，而將1替換成0。例如 a∧0＝0和a∨1＝1互為對偶命題， a∨0＝a和a∧1＝a互為對偶命題。有界格的性質(zhì)定理（補(bǔ)充）設(shè)<L,∧,∨,0,1>是有界格，28有界格中的補(bǔ)元定義11.8設(shè)<L,∧,∨,0,1>是有界格，a∈L， 若存在b∈L使得

a∧b＝0和a∨b＝1 成立，則稱b是a的補(bǔ)元。說明 若b是a的補(bǔ)元，那么a也是b的補(bǔ)元。 換句話說，a和b互為補(bǔ)元。有界格中的補(bǔ)元定義11.8設(shè)<L,∧,∨,0,1>是有界格29例11.9考慮下圖中的四個格。L1中的a與c互為補(bǔ)元，其中a為全下界，c為全上界，b沒有補(bǔ)元。L2中的a與d互為補(bǔ)元，其中a為全下界，d為全上界，b與c也互為補(bǔ)元。L3中的a與e互為補(bǔ)元，其中a為全下界，e為全上界，b的補(bǔ)元是c和d，c的補(bǔ)元是b和d，d的補(bǔ)元是b和c。b,c,d每個元素都有兩個補(bǔ)元。L4中的a與e互為補(bǔ)元。其中a為全下界。e為全上界。b的補(bǔ)元是c和d，c的補(bǔ)元是b，d的補(bǔ)元是b。例11.9考慮下圖中的四個格。L1中的a與c互為補(bǔ)元，其中a30有界格中補(bǔ)元的說明在任何有界格中，全下界0與全上界1互補(bǔ)。對于其他元素，可能存在補(bǔ)元，也可能不存在補(bǔ)元。如果存在，可能是唯一的，也可能是多個補(bǔ)元。對于有界分配格，如果它的元素存在補(bǔ)元，一定是唯一的。有界格中補(bǔ)元的說明在任何有界格中，31有界分配格中補(bǔ)元的唯一性定理11.6設(shè)<L,∧,∨,0,1>是有界分配格。 若a∈L，且對于a存在補(bǔ)元b，則b是a的唯一補(bǔ)元。證明 假設(shè)c∈L也是a的補(bǔ)元，則有 a∨c＝1，a∧c＝0 又知b是a的補(bǔ)元，故 a∨b＝1，a∧b＝0 從而得到 a∨c＝a∨b，a∧c＝a∧b 由于L是分配格，根據(jù)定理13.7，b＝c。有界分配格中補(bǔ)元的唯一性定理11.6設(shè)<L,∧,∨,0,32有補(bǔ)格的定義定義11.9設(shè)<L,∧,∨,0,1>是有界格，若L中所有元素都有補(bǔ)元存在，則稱L為有補(bǔ)格。L2,L3和L4是有補(bǔ)格，L1不是有補(bǔ)格。L2和L3是有補(bǔ)格，L1不是有補(bǔ)格。有補(bǔ)格的定義定義11.9設(shè)<L,∧,∨,0,1>是有界格，33本節(jié)小結(jié)如果格中一個運算對另一個運算是可分配的，稱這個格是分配格。

分配格的兩種判別法： 不存在與鉆石格或五角格同構(gòu)的子格； 對于任意元素a,b,c,有a∧b＝a∧c且a∨b＝a∨c

b＝c。

有界格的定義及其實例。

格中元素的補(bǔ)元及其性質(zhì)（分配格中補(bǔ)元的唯一性）。

有補(bǔ)格的定義。本節(jié)小結(jié)如果格中一個運算對另一個運算是可分配的，稱這個格是分34布爾代數(shù)定義11.10如果一個格是有補(bǔ)分配格，則稱它為布爾格或布爾代數(shù)。說明 在布爾代數(shù)中，每個元素都存在著唯一的補(bǔ)元。 可以把求補(bǔ)元的運算看作是布爾代數(shù)中的一元運算。 可以把一個布爾代數(shù)標(biāo)記為<B,∧,∨,＇,0,1>，

＇為求補(bǔ)運算,

a∈B，a＇是a的補(bǔ)元。布爾代數(shù)定義11.10如果一個格是有補(bǔ)分配格，則稱它為布爾35例11.10例11.10

設(shè)S110＝{1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分別表示求最大公約數(shù)和最小公倍數(shù)的運算。問<S110,gcd,lcm>是否構(gòu)成布爾代數(shù)？為什么？解答

證明<S110,gcd,lcm>構(gòu)成格。容易驗證

x,y,z∈S110，有g(shù)cd(x,y)∈S110 lcm(x,y)∈S110gcd(x,y)＝gcd(y,x)lcm(x,y)＝lcm(y,x)gcd(gcd(x,y),z)＝gcd(x,gcd(y,z))lcm(lcm(x,y),z)＝lcm(x,lcm(y,z))gcd(x,lcm(x,y))＝xlcm(x,gcd(x,y))＝x二元運算交換律結(jié)合律吸收律例11.10例11.10

設(shè)S110＝{1,2,5,10,36例11.10證明<S110,gcd,lcm>是分配格。 易驗證

x,y,z∈S110有 gcd(x,lcm(y,z))＝lcm(gcd(x,y),gcd(x,z))證明<S110,gcd,lcm>是有補(bǔ)格。 1為S110中的全下界 110為S110中的全上界 1和110互為補(bǔ)元，2和55互為補(bǔ)元， 5和22互為補(bǔ)元，10和11互為補(bǔ)元。綜上所述，<S110,gcd,lcm>為布爾代數(shù)。例11.10證明<S110,gcd,lcm>是分配格。37例11.10（2）例11.10（2）設(shè)B為任意集合,證明B的冪集格<P(B),∩,∪,～,

,B>構(gòu)成布爾代數(shù)，稱為集合代數(shù)。證明 P(B)關(guān)于∩和∪構(gòu)成格，因為 ∩和∪運算滿足交換律、結(jié)合律和吸收律。 由于∩和∪互相可分配，因此P(B)是分配格， 且全下界是空集

,全上界是B。 根據(jù)絕對補(bǔ)的定義，取全集為B，

x∈P(B)，～x是x的補(bǔ)元。 從而證明P(B)是有補(bǔ)分配格，即布爾代數(shù)。例11.10（2）例11.10（2）設(shè)B為任意集合,證明B38布爾代數(shù)的性質(zhì)定理11.7設(shè)<B,∧,∨,′,0,1>是布爾代數(shù)，則(1)

a∈B，(a＇)＇＝a(2)

a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇說明 (1)稱為雙重否定律。 (2)稱為德摩根律。 命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實際上

是這個定理的特例。 可以證明德摩根律對有限個元素也是正確的。證明 (1)(a′)′是a′的補(bǔ)元，a也是a′的補(bǔ)元。 由補(bǔ)元的唯一性得(a′)′＝a。布爾代數(shù)的性質(zhì)定理11.7設(shè)<B,∧,∨,′,0,1>是布39定理11.7(2)的證明(2)

a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇ (a∧b)∨(a＇∨b＇) ＝(a∨a＇∨b＇)∧(b∨a＇∨b＇) ＝(1∨b＇)∧(a＇∨1) ＝1∧1 ＝1

(a∧b)∧(a＇∨b＇) ＝(a∧b∧a＇)∨(a∧b∧b＇) ＝(0∧b)∨(a∧0) ＝0∨0＝0 所以a＇∨b＇是a∧b的補(bǔ)元，根據(jù)補(bǔ)元的唯一性有 (a∧b)＇＝a＇∨b＇ 同理可證(a∨b)＇=a＇∧b＇。定理11.7(2)的證明(2)a,b∈B，(a∧b)＇＝40布爾代數(shù)作為代數(shù)系統(tǒng)的定義定義11.11設(shè)<B,*,

>是代數(shù)系統(tǒng)，*和

是二元運算。 若*和°運算滿足： (1) 交換律，即

a,b∈B有 a*b＝b*a， a

b＝b

a (2) 分配律，即

a,b,c∈B有 a*(b

c)＝(a*b)

(a*c) a

(b*c)＝(a

b)*(a

c)

(3) 同一律，即存在0,1∈B，使得

a∈B有 a*1＝a， a

0＝a (4) 補(bǔ)元律，即

a∈B,存在a′∈B，使得 a*a′＝0， a

a′＝1則稱<B,*,

>是一個布爾代數(shù)。

布爾代數(shù)作為代數(shù)系統(tǒng)的定義定義11.11設(shè)<B,*,>是41關(guān)于布爾代數(shù)定義的說明所謂同一律就是指運算含有單位元的性質(zhì)，這里的1是*運算的單位元，0是運算

的單位元?？梢宰C明1和0分別也是

和*運算的零元。

a∈B有 a1 ＝(a1)*1 （同一律） ＝1*(a1) （交換律） ＝(a

a′)*(a

1) （補(bǔ)元律） ＝a(a′*1) （分配律） ＝a

a′ （同一律） ＝1（補(bǔ)元律）同理可證a*0＝0。關(guān)于布爾代數(shù)定義的說明所謂同一律就是指運算含有單位元的性質(zhì)，42關(guān)于布爾代數(shù)定義的說明為證明以上定義的<B,*,°>是布爾代數(shù)，只需證明它是一個格，即證明*和°運算滿足結(jié)合律和吸收律。證明吸收律，

a,b∈B有

a(a*b) ＝(a*1)(a*b) （同一律） ＝a*(1b) （分配律） ＝a*1 （1是運算的零元) ＝a （同一律）同理有a*(ab)＝a。關(guān)于布爾代數(shù)定義的說明為證明以上定義的<B,*,°>是布爾代43關(guān)于布爾代數(shù)定義的說明為證結(jié)合律，先證以下命題：

a,b,c∈B，ab＝ac且ab＝acb＝c由ab＝ac且ab＝ac可得 (ab)*(ab)＝(ac)*(ac)由分配律和交換律得 (a*a)b＝(a*a)c由補(bǔ)元律得 0b＝0c由同一律和交換律得 b＝c關(guān)于布爾代數(shù)定義的說明為證結(jié)合律，先證以下命題：44關(guān)于布爾代數(shù)定義的說明使用這個命題，為證明(a*b)*c＝a*(b*c)，只需證明以下兩個等式：(1)a((a*b)*c)＝a(a*(b*c))(2)a((a*b)*c)＝a(a*(b*c))先證明第一個等式，由吸收律有 a(a*(b*c))＝a a((a*b)*c) ＝(a(a*b))*(ac) (分配律) ＝a*(ac) (吸收律) ＝a所以(1)式成立。關(guān)于布爾代數(shù)定義的說明使用這個命題，為證明(a*b)*c＝45關(guān)于布爾代數(shù)定義的說明下面證明(2)式：a((a*b)*c)＝a(a*(b*c))

a(a*(b*c)) ＝(aa)*(a(b*c)) (分配律) ＝1*(a(b*c)) (交換律,補(bǔ)元律) ＝a(b*c) (交換律,同一律)

a((a*b)*c) ＝(a(a*b))*(ac)(分配律) ＝((aa)*(ab))*(ac) (分配律) ＝(1*(ab))*(ac) (交換律,補(bǔ)元律) ＝(ab)*(ac)(交換律,同一律) ＝a(b*c) (分配律)所以（2）式成立。關(guān)于布爾代數(shù)定義的說明下面證明(2)式：a((a*b)46有限布爾代數(shù)的結(jié)構(gòu)定義11.12設(shè)L是格，0∈L，a∈L，若

b∈L有 0＜b≤a

b＝a 則稱a是L中的原子?？紤]右圖中的幾個格。L1的原子是a。L2的原子是a,b,c。L3的原子是a和b。若L是正整數(shù)n的全體正因子關(guān)于整除關(guān)系構(gòu)成的格，則L的原子恰為n的全體質(zhì)因子。若L是集合B的冪集合，則L的原子就是由B中元素構(gòu)成的單元集。有限布爾代數(shù)的結(jié)構(gòu)定義11.12設(shè)L是格，0∈L，a∈L，47有限布爾代數(shù)的表示定理定理11.8(有限布爾代數(shù)的表示定理)設(shè)B是有限布爾代數(shù)，A是B的全體原子構(gòu)成的集合，則B同構(gòu)于A的冪集代數(shù)P(A)。證明 任取x∈B，令T(x)＝{a|a∈B,a是原子且a≤x} 則T(x)A，定義函數(shù) ：B→P(A)，

(x)＝T(x)，

x∈B 下面證明

是B到P(A)的同構(gòu)映射。 任取x,y∈B，b有 b∈T(x∧y)

b∈A且b≤x∧y (b∈A且b≤x)且(b∈A且b≤y) b∈T(x)且b∈T(y) b∈T(x)∩T(y) 從而有T(x∧y)＝T(x)∩T(y)， 即

x,y

B有

(x∧y)＝

(x)∩

(y)。有限布爾代數(shù)的表示定理定理11.8(有限布爾代數(shù)的表示定理48定理11.8證明任取x,y∈B，設(shè) x＝a1∨a2∨…∨an， y＝b1∨b2∨…∨bm是x,y的原子表示，則 x∨y＝a1∨a2∨…∨an∨b1∨b2∨…∨bm由引理2可知 T(x∨y)＝{a1,a2,…,an,b1,b2,…,bm}又由于 T(x)＝{a1,a2,…,an}， T(y)＝{b1,b2,…,bm}所以 T(x∨y)＝T(x)∪T(y)即

(x∨y)＝

(x)∪

(y)定理11.8證明任取x,y∈B，設(shè)49定理11.8證明任取x∈B，存在x

∈B使得 x∨x＝1，x∧x＝0因此有

(x)∪

(x

)＝

(x∨x

)＝

(1)＝A

(x)∩

(x

)＝

(x∧x

)＝

(0)＝

而和A分別為P(A)的全下界和全上界，因此

(x

)是

(x)在P(A)中的補(bǔ)元，即

(x

)＝?

(x)綜上所述，

是B到P(A)的同態(tài)映射。定理11.8證明任取x∈B，存在x∈B使得50定理11.8證明下面證明

為雙射。假設(shè)

(x)＝

(y)，則有 T(x)＝T(y)＝{a1,a2,…,an}由引理2可知x＝a1∨a2∨…∨an＝y(tǒng)于是

為單射。任取{b1,b2,…,bm}∈P(A)，令x＝b1∨b2∨…∨bm，則

(x)＝T(x)＝{b1,b2,…,bm}于是

為滿射。定理得證。定理11.8證明下面證明為雙射。51例子考慮110的正因子的集合S110關(guān)于gcd,lcm運算構(gòu)成的布爾代數(shù)。它的原子是2、5和11，因此原子的集合A＝{2,5,11}。冪集P(A)＝{

,{2},{5},{11},{2,5