第七章格與布爾代數(shù)

主講人：姜慧研

東北大學(xué)軟件學(xué)院多媒體醫(yī)療信息處理研究室

E-mail:

2第七章格與布爾代數(shù)

布爾代數(shù)是計算機邏輯設(shè)計的基礎(chǔ)，它是由格引出的，格又是從偏序集引出的。所以我們先回顧一下偏序集。<A,≤>是偏序集:≤是A上自反,反對稱和傳遞關(guān)系(偏序).偏序集中的元素間的次序可以通過它的Hasse圖反映出來.

例如A={1,2,3,6,12,24,36},≤是A上整除關(guān)系其Hasse圖如圖所示，BAB≠Φ６。１。３。12。２。24。36。1.B的極小元與極大元

y是B的極小元y∈B∧x(x∈B∧x≤y)y是B的極大元y∈B∧x(x∈B∧y≤x)例如{2,3,6}的極小元:2,3極大元:632.B的最小元與最大元

y是B的最小元y∈B∧x(x∈By≤x)y是B的最大元y∈B∧x(x∈Bx≤y){2,3,6}的最小元:無最大元:6B如果有最小元(最大元),則是唯一的。3.B的下界與上界y是B的下界y∈A∧x(x∈By≤x)y是B的上界y∈A∧x(x∈Bx≤y){2,3,6}的下界:1上界:6,12,24,364.B的最大下界(下確界)與最小上界(上確界)y是B的最大下界(下確界)：B的所有下界x,有x≤y。y是B的最小上界(上確界)：B的所有上界x,有y≤x。{2,3,6}下確界:1上確界:6(B若有下(上)確界，則唯一)６。１。３。12。２。24。36。46-1格

(Lattice)一.基本概念1.格的定義<A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，則稱<A,≤>是格。右圖的三個偏序集,哪個是格？６。１。３。12。２。24。36。30。3。１。2。5。10。１5。6。<A,≤><B,≤>3。4。1。2。<C,≤><A,≤>不是格，因為{24,36}無最小上界。<B,≤>和<C,≤>是格。再看下面三個偏序集，哪個是格？5這三個偏序集，都不是格，第一個與第三個是同構(gòu)的。因為d和e無下界，也無最小上界；第二個圖：2,3無最大下界，4,5無最小上界。2.平凡格：所有全序都是格，稱之為平凡格。因為全序中任何兩個元素x,y，要么x≤y,要么y≤x。如果x≤y，則{x,y}的最大下界為x，最小上界為y。如果y≤x，則{x,y}的最大下界為y，最小上界為x。即這{x,y}的最大下界為較小元素，最小上界為較大元素.dabce123456dabce63.由格誘導(dǎo)的代數(shù)系統(tǒng)設(shè)<A,≤>是格,在A上定義二元運算∨和∧為:a,b∈Aa∨b=LUB{a,b},{a,b}的最小上界.LeastUpperBounda∧b=GLB{a,b},{a,b}的最大下界.GreatestLowerBound稱<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng).(∨-并,∧-交)例如右邊的格中a∧b=b,a∨b=a,b∧c=e

eabdcbacfe

gbacfe

gd<B,≤><A,≤>acbd<C,≤>4.子格：設(shè)<A,≤>是格,<A,∨,∧>是由<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。B是A的非空子集，如果∧和∨在B上封閉，則稱<B,≤>是<A,≤>的子格。<C,≤>是<A,≤>的子格。而<B,≤>不是.因b∧c=dB,(判定子格：看去掉的元素是否影響封閉)7二.格的對偶原理設(shè)<A,≤>是格，≤的逆關(guān)系記作≥，≥也是偏序關(guān)系。所以<A,≥>也是格，<A,≥>的Hasse圖是將<A,≤>的Hasse圖顛倒180o即可。

格的對偶原理：設(shè)P是對任何格都為真的命題，如果將P中的≤換成≥，∧換成∨，∨換成∧，就得到命題P’,

稱P’為P的對偶命題，則P’對任何格也是為真的命題。例如：P:a∧b≤aP’:a∨b≥a{a,b}的最大下界≤a{a,b}的最小上界≥a三.格的性質(zhì)<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。a,b,c,d∈A1.a≤a∨bb≤a∨ba∧b≤aa∧b≤b

此性質(zhì)由運算∨和∧的定義直接得證。82.如果a≤b，c≤d，則a∨c≤b∨d，a∧c≤b∧d。證明：如果a≤b，又b≤b∨d,由傳遞性得a≤b∨d,類似由c≤d，d≤b∨d，由傳遞性得c≤b∨d,這說明b∨d是{a,c}的上界，而a∨c是{a,c}的最小上界，所以a∨c≤b∨d。類似可證a∧c≤b∧d。推論：在一個格中，任何a,b,c∈A，如果b≤c，則

a∨b≤a∨c，a∧b≤a∧c。

此性質(zhì)稱為格的保序性。3.∨和∧都滿足交換律。即

a∨b=b∨a，a∧b=b∧a。

此性質(zhì)由運算∨和∧的定義直接得證。94.∨和∧都滿足冪等律。即a∨a=aa∧a=a證明：由性質(zhì)1得a≤a∨a(再證a∨a≤a)

又≤自反得a≤a,這說明a是{a}的上界，而a∨a是{a}的最小上界，所以a∨a≤a。最后由反對稱得a∨a=a。由對偶原理得a∧a=a5.∨和∧都滿足結(jié)合律。即

(a∨b)∨c=a∨(b∨c)，(a∧b)∧c=a∧(b∧c)。

證明：⑴先證明(a∨b)∨c≤a∨(b∨c)∵a≤a∨(b∨c)b≤b∨c≤a∨(b∨c)∴(a∨b)≤a∨(b∨c)∵c≤b∨c≤a∨(b∨c)∴(a∨b)∨c≤a∨(b∨c)

⑵同理可證a∨(b∨c)≤(a∨b)∨c

最后由反對稱得(a∨b)∨c=a∨(b∨c)

類似可證(a∧b)∧c=a∧(b∧c)。106.

∨和∧都滿足吸收律。即

a∨(a∧b)=a，a∧(a∨b)=a。證明：⑴顯然有a≤a∨(a∧b)⑵.再證a∨(a∧b)≤a∵a≤aa∧b≤a∴a∨(a∧b)≤a最后由≤反對稱得a∨(a∧b)=a，類似可證a∧(a∨b)=a。7.<A,∨,∧>是代數(shù)系統(tǒng)，如果∨和∧是滿足吸收律的二元運算，則∨和∧必滿足冪等律。證明：任取a,b∈A∵∨和∧是滿足吸收律。∴有

a∨(a∧b)=a------⑴a∧(a∨b)=a-------⑵。由于上式中的b是任意的，可以令b=a∨b并代入⑴式得

a∨(a∧(a∨b))=a由⑵式得a∨a=a同理可證a∧a=a118.

∨和∧不滿足分配律。但有分配不等式：

a∨(b∧c)≤(a∨b)∧(a∨c)，

(a∧b)∨(a∧c)≤a∧(b∨c)。我們先看右圖的例子：

d∨(b∧e)=d∨c=d(d∨b)∧(d∨e)=a∧e=ed≤e即

d∨(b∧e)≤(d∨b)∧(d∨e)證明：⑴∵a≤a∨ba≤a∨c∴a≤(a∨b)∧(a∨c)∵b∧c≤b≤a∨bb∧c≤c≤a∨c∴b∧c≤(a∨b)∧(a∨c)于是有a∨(b∧c)≤(a∨b)∧(a∨c)由對偶原理得a∧(b∨c)≥(a∧b)∨(a∧c)。

即(a∧b)∨(a∧c)≤a∧(b∨c)。cabed12*9.a≤ba∨b=ba∧b=a證明：⑴教材P239已證a≤b

a∧b=a這里從略。⑵下面證明a≤ba∨b=b

先證a≤ba∨b=b

設(shè)a≤b，又b≤b∴a∨b≤b

又∵b≤a∨b由≤反對稱得a∨b=b

再證

a∨b=b

a≤b

已知a∨b=b∵a≤a∨b∴a≤b。

最后得a≤ba∨b=b這是個很重要的定理，在以后經(jīng)常用到此結(jié)論。13四.格的同態(tài)與同構(gòu)1.定義：設(shè)<A1,≤1>和<A2,≤2>是兩個格，由它們誘導(dǎo)的代數(shù)系統(tǒng)分別是<A1,∨1,∧1>和

<A2,∨2,∧2>，如果存在映射f:A1A2使得對任何a,b∈A1,f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)則稱f是<A1,∨1,∧1>到

<A2,∨2,∧2>的同態(tài)映射。也稱<f(A1),≤2>是<A1,≤1>的同態(tài)像。如果f是雙射的，就稱f是<A1,∨1,∧1>到

<A2,∨2,∧2>，的格同構(gòu)，也稱格<A1,≤1>和<A2,≤2>同構(gòu)。14例如<A,≤>,A={1,2,3,6},≤是A上整除關(guān)系。

<P(E),>,E={a,b}它們誘導(dǎo)的代數(shù)系統(tǒng)分別是<A,∨,∧>和<P(E),∪,∩>其中∨和∧分別是求兩個數(shù)的最小公倍數(shù)和最大公約數(shù).

Φ{a}{a,b}1326f6321{a}{a,b}ΦA(chǔ)P(E)f(2∨3)=f(6)={a,b}f(2)∪f(3)={a}∪={a,b}f(2∧3)=f(1)=Φf(2)∩f(3)={a}∩=Φf(2∨6)=f(6)={a,b}f(2)∪f(6)={a}∪{a,b}={a,b}f(2∧6)=f(2)={a}f(2)∪f(6)={a}∪{a,b}={a}可見它們同構(gòu)。格同構(gòu)，它們的圖的形狀一定相同。152.格同態(tài)的保序性定理：設(shè)f是格<A1,≤1>到<A2,≤2>的同態(tài)映射，則對任何a,b∈A1,如果a≤1b,則

f(a)≤2f(b).證明：令<A1,∨1,∧1>和

<A2,∨2,∧2>是格<A1,≤1>和

<A2,≤2>誘導(dǎo)的代數(shù)系統(tǒng)，任取a,b∈A1,設(shè)a≤1b,則

a∧1b=af(a∧1b)=f(a)而f(a∧1b)=f(a)∧2f(b)，所以

f(a)∧2f(b)=f(a)，所以f(a)≤2f(b).3.格同構(gòu)的保序性定理：設(shè)雙射f是格<A1,≤1>到<A2,≤2>的同構(gòu)映射，當且僅當對任何a,b∈A1,若a≤1bf(a)≤2f(b).證明：令<A1,∨1,∧1>和

<A2,∨2,∧2>是格<A1,≤1>和

<A2,≤2>誘導(dǎo)的代數(shù)系統(tǒng)，161).充分性：已知，任取a,b∈A1,若a≤1bf(a)≤2f(b).(應(yīng)證出f(a∧1b)=f(a)∧2f(b)f(a∨1b)=f(a)∨2f(b))a)

先證f(a∧1b)=f(a)∧2f(b)

令a∧1b=c∴c≤1ac≤1b由已知得f(c)≤2f(a)和f(c)≤2f(b).所以f(c)≤2f(a)∧2f(b)---------⑴

再證f(a)∧2f(b)≤2f(c)：由于f(a),f(b)∈A2,又∧2的封閉性得f(a)∧2f(b)∈A2,又由f:A1A2是滿射，必有d∈A1,使得f(d)=f(a)∧2f(b)所以f(d)≤2f(a)f(d)≤2f(b)由已知條件得：d≤1ad≤1b∴d≤1a∧1b=cd≤1cf(d)≤2f(c)即f(a)∧2f(b)≤2f(c)--------⑵由⑴⑵得f(c)=f(a)∧2f(b)即

f(a∧1b)=f(a)∧2f(b)

。b)類似可證f(a∨1b)=f(a)∨2f(b)所以f是它們的同構(gòu)映射172).必要性：已知f是格<A1,≤1>到<A2,≤2>的同構(gòu)映射，

（證出：任取a,b∈A1,若a≤1bf(a)≤2f(b)）a)

先證a≤1bf(a)≤2f(b)任取a,b∈A1,設(shè)a≤1b

，由格同態(tài)保序性得f(a)≤2f(b)

b)再證f(a)≤2f(b)a≤1b設(shè)f(a)≤2f(b)，∴f(a)=f(a)∧2f(b)=f(a∧1b)∵f是入射，∴a=a∧1b所以a≤1b由a),b)最后得a≤1bf(a)≤2f(b)。定理證畢。由格的同構(gòu)得：具有一、二、三個元素的格分別同構(gòu)于含有一、二、三個元素的鏈。aababc18具有四個元素的格分別同構(gòu)于下面兩種格形式之一：dabcda

bcecdda

bcea

bcea

bdaeb

cddabce具有五個元素的格分別同構(gòu)于下面五種格形式之一：作業(yè)P242(1)(2)(4)(7)196-2幾個特殊格一.分配格

前面我們介紹一般的格，∧和∨只滿足分配不等式。

a∨(b∧c)≤(a∨b)∧(a∨c)，

(a∧b)∨(a∧c)≤a∧(b∨c)。下面介紹的是滿足分配律的格----分配格。1.定義：<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。如果對a,b,c∈A，有

a∨(b∧c)=(a∨b)∧(a∨c)，

a∧(b∨c)=(a∧b)∨(a∧c)則稱<A,≤>是分配格。例<P(E),∪,∩>是分配格。202.二個重要的五元素非分配格：

2∧(3∨5)=2∧30=2(2∧3)∨(2∧5)=1∨1=1c∧(b∨d)=c∧a=c(c∧b)∨(c∧d)=e∨d=d可見它們都不是分配格。3.分配格的判定：見書P245

一個格是分配格的充分且必要條件是在該格中沒有任何子格與上述兩個五元素非分配格之一同構(gòu)。用此方法可以判定下面兩個格不是分配格：3130

25dea

bc416

352fga

dc

e

b214.分配格的性質(zhì)1).定理7-2.1.在格中，如果∧對∨可分配，則∨對∧也可分配。反之亦然。證明：設(shè)<A,∨,∧>是由格<A,≤>誘導(dǎo)的代數(shù)系統(tǒng)。且∧對∨可分配。任取a,b,c∈A，a∧(b∨c)=(a∧b)∨(a∧c)而(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)(分配)=a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c))(吸收、分配)=(a∨(a∧c))∨(b∧c)(結(jié)合)=a∨(b∧c)(吸收)同理可證:如果∨對∧可分配，則∧對∨也可分配.2).定理7-2.2.所有鏈均為分配格。證明：顯然任何鏈都不會含有與五元素非分配格之一同構(gòu)的子格，所以鏈必是分配格。223).

定理7-2.3.設(shè)<A,≤>是分配格，對任何a,b,c∈A,如果有a∧b=a∧c及a∨b=a∨c則必有b=c.證明：任取a,b,c∈A,設(shè)有a∧b=a∧c及a∨b=a∨cb=b∨(a∧b)(吸收律)=b∨(a∧c)(代換)=(b∨a)∧(b∨c)(分配)=(a∨b)∧(b∨c)(交換)=(a∨c)∧(b∨c)(代換)=(a∧b)∨c(分配)

=(a∧c)∨c(代換)=c(吸收律)23二.有界格1.格的全上界與全下界1).全上界:設(shè)<A,≤>是格，如果存在元素a∈A對任何x∈A,x≤a,則稱a是格的全上界,記作1。(即是A的最大元)定理7-2.4一個格如果有全上界，則是唯一的。(我們已證明過，最大元如果有，則是唯一的)2).全下界:設(shè)<A,≤>是格，如果存在元素a∈A對任何x∈A,a≤x,則稱a是格的全下界,記作0。(即是A的最小元)定理7-2.5一個格如果有全下界，則是唯一的。從格的圖形看：全上界1，就是圖的最上邊元素(只一個)。全下界0，就是圖的最下邊元素(只一個)。b01

ac1c0242.有界格定義：如果一個格存在全上界1與全下界0，則稱此格為有界格。設(shè)<A,≤>是有界格，則對任何a∈A,有因為a≤1,∴a∧1=aa∨1=10≤a∴a∧0=0a∨0=a由此看出：對于∧來說1是么元，0是零元。對于∨來說0是么元，1是零元。思考題：是否所有格都是有界格？所有有限個元素的格都是有界格。

而無限個元素的格可能是無界格。

例如<I,≤>就是既無全上界也無全下界。25三.有補格回顧：集合的補集，

若A∪B=EA∩B=Φ則~A=B，~B=A

如E={a,b}~E=Φ~Φ=E~{a}=,~={a}1.元素的補元：設(shè)<A,≤>是個有界格，a∈A,如果存在b∈A,使得

a∨b=1a∧b=0則稱a與b互為補元。例：右邊的格中

a的補元：c,eb的補元：

無

c的補元：a,dd的補元：ce的補元：a0的補元：11的補元：0Φ{a,b}

{a}e01

bc

d

a262.有補格的定義：一個有界格中，如果每個元素都有補元，則稱之為有補格。下述有界格中，哪些是有補格？Φ{a,b}

{a}b01

ace01

bc

d

a1c0(1)(2)(3)(4)上述有補格中，有些元素的補元不唯一，如(2)中的b,那么什么樣的有補格元素的補元唯一呢？－是有界分配格。請看下面定理：27定理7－2.6在有界分配格中，如果元素有補元，則補元是唯一的。證明：設(shè)<A,≤>是有界分配格，任取a∈A,假設(shè)a有兩個補元b和c，則

a∧b=0a∨b=1a∧c=0a∨c=1于是有，a∧b=a∧ca∨b=a∨c由分配格的定理7－2.3得b=c∴a的補元是唯一的。四.布爾格

如果一個格既是分配格又是有補格，則稱之為布爾格。布爾格中每個元素都有唯一補元，元素a的補元記作。顯然<P(E),>是布爾格。下面介紹由布爾格誘導(dǎo)的代數(shù)系統(tǒng)－－布爾代數(shù)。作業(yè)

P248(2)(5)P252(1)(3)(6)286－3布爾代數(shù)BooleanAlgebra一.定義由布爾格<B,≤>誘導(dǎo)的代數(shù)系統(tǒng)<B,∨,∧,ˉ>稱之為布爾代數(shù)。其中ˉ是“取補元”運算。如果B是有限集合，則稱它是有限布爾代數(shù)。例如：令B＝{F,T}，∧表示合取，∨表示析取，表示否定,<B,∨,∧,>就是個布爾代數(shù)。如上圖所示。

TFΦ{a,b}

{a}<P(E),∪,∩,~>也是個布爾代數(shù)。如下圖所示。29二.布爾代數(shù)的性質(zhì)設(shè)<B,∨,∧,ˉ>布爾代數(shù),任意x,y,z∈B,有⑴交換律x∨y=y∨xx∧y=y∧x⑵結(jié)合律x∨(y∨z)=(x∨y)∨zx∧(y∧z)=(x∧y)∧z

⑶冪等律x∨x=xx∧x=x

⑷吸收律x∨(x∧y)=xx∨(x∧y)=x⑸分配律x∨(y∧z)=(x∨y)∧(x∨z)

x∧(y∨z)=(x∧y)∨(x∧z)⑹同一律x∨0=xx∧1=x

⑺零律x∨1=1x∧0=0

⑻互補律x∨=1x∧=0⑼對合律⑽底－摩根定律30上述性質(zhì)都可以由格，分配格,有界格，布爾格得到。下面只證明底－摩根定律。

所以，類似可證另一個。31三.布爾代數(shù)的同構(gòu)1.定義：令<B1,∨1,∧1,ˉ>和

<B2,∨2,∧2,~>是兩個布爾代數(shù)，如果存在雙射f:B1B2,對任何a,b∈B1,有

f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)

~f(a)f()=則稱f是<B1,∨1,∧1,ˉ

>到

<B2,∨2,∧2,~

>的同構(gòu)映射。

與格同構(gòu)比較，多了一個關(guān)于補運算的同構(gòu)關(guān)系等式。

為了引出有限布爾代數(shù)的元素個數(shù)的定理，下面介紹原子的概念。322.原子

定義1:設(shè)<B,∨,∧,ˉ>是布爾代數(shù),元素a∈B,a≠0,對任何元素x∈B,有x∧a=a,或x∧a=0,則稱a是原子。

定義2:<A,≤>是布爾格,在<A,≤>的哈斯圖中稱蓋住全下界0的元素為原子。例如：1。e。0。d。f。b。c。a。0。1。01a

b33定理7-3.8(Stone鉆石定理)設(shè)<B,∨,∧,ˉ>是有限布爾代數(shù)，M是B中所有原子構(gòu)成的集合，則<B,∨,∧,ˉ>與<P(M),∪,∩,~>同構(gòu)。證明:構(gòu)造映射f:BP(M)對于x∈B

f(x)={Φx=0{a|a∈M,a≤x}x≠030。3。1。2。5。10。15。6。12356101530Φ{2}{3}{5}{2,3}{2,5}{3,5}{2,3,5}BP(M)f先通過下邊例子了解映射f的形式:341).先證明f是雙射.

a).證明f是入射:只有x=0時,才有f(0)=Φ.

任取x1,x2∈B,x1≠0

x2≠0且x1≠x2,由定理7-3.6得,x1,x2可以寫成如下形式:x1=a1∨a2∨…∨ak

其中ai≤x1(1≤i≤k)x2=b1∨b2∨…∨bm

其中bj≤x2(1≤j≤m)因為每個非0元素寫成上述表達式的形式是唯一的,又因為x1≠x2,所以

{a1,a2,...,ak}≠{b1,b2,…,bm}.

由f定義得f(x1)={a1,a2,...,ak}f(x2)={b1,b2,…,bm}故f(x1)≠f(x2)f入射.

b).

證明f滿射:任取M1∈P(M)如果M1為Φ,則f(0)=M1

,如果M1≠Φ,令M1={a1,a2,...,ak},由∨的封閉性得,必存在x∈B,使得a1∨a2∨…∨ak=x,顯然每個ai≤x(1≤i≤k),故f(x)=M1,所以f是滿射的.最后由a)b)得f是雙射的.352).證明f滿足三個同構(gòu)關(guān)系式.任取x1,x2∈B,因為f是雙射,必有M1,M2∈P(M),使得

f(x1)=M1,f(x2)=M2,a).證明f(x1∧x2)=f(x1)∩f(x2)=M1∩M2,

令f(x1∧x2)=M3,即證明M3=M1∩M2

先證M3M1∩M2

如果M3=Φ顯然有M3M1∩M2

如果M3≠Φ,任取a∈M3,即a∈f(x1∧x2)由f定義得a≤x1∧x2,又因為x1∧x2≤x1,

x1∧x2≤x2,所以a≤x1a≤x2由f定義得a∈f(x1)a∈f(x2)即a∈M1a∈M2,故a∈M1∩M2,所以M3M1∩M236再證M1∩M2M3

如果M1∩M2=Φ顯然有M1∩M2M3

如果M1∩M2≠Φ,任取a∈M1∩M2a∈M1a∈M2即a∈f(x1),a∈f(x2)，所以a是滿足a≤x1與a≤x2的原子,所以a≤x1∧x2，由f定義得,a∈f(x1∧x2),即a∈M3所以M1∩M2M3

所以

M3=M1∩M2

即f(x1∧

x2)=f(x1)∩f(x2)

37b).證明f(x1∨

x2)=f(x1)∪f(x2)=M1∪M2,

令f(x1∨x2)=M4,即證明M4=M1∪M2先證M4M1∪M2

如果M4=Φ顯然有M4M1∪M2

如果M4≠Φ,任取a∈M4,a∈f(x1∨x2)由f定義得a≤x1∨x2,則必有a≤x1,或者a≤x2,

(因為如果a≤x1與a≤x2都不成立,由定理7-3.7得必有

與a是原子矛盾,所以有

a≤x1

或a≤x2)由f定義得a∈f(x1)即a∈M1

或a∈f(x2)即a∈M2所以a∈M1∪

M2,所以M4M1∪M238再證M1∪M2

M4

如果M1∪M2

=Φ顯然有M1∪M2

M4

如果M1∪M2≠Φ,任取a∈M1∪M2a∈M1或者a∈M2如果a∈M1

則a≤x1a≤x1≤x1∨x2∴a∈f(x1∨x2),a∈M4如果a∈M2

則a≤x2a≤x2≤x1∨x2∴a∈f(x1∨x2),a∈M4所以M1∪M2

M4

最后得M4=M1∪M2即f(x1∨

x2)=f(x1)∪f(x2)39c).證明于是有x1∨x2=1x1∧x2=0f(x1∨x2)=Mf(x1∧x2)=Φf(x1∨x2)=f(x1)∪f(x2)=M1∪M2=Mf(x1∧x2)=f(x1)∩f(x2)=M1∩M2=Φ所以M2=~M1即綜上所述

由1).2).3)得

f(x1∧x2)=f(x1)∩f(x2)f(x1∨x2)=f(x1)∪f(x2)所以<B,∨,∧,ˉ>與<P(M),∪,∩,~>同構(gòu)。40推論1.任何有限布爾代數(shù)的元素個數(shù)為2n(n=1,2,3,…)

因為|P(M)|=2n推論2.兩個有限布爾代數(shù)同構(gòu)的充分且必要條件是元素個數(shù)相同。1。e。0。d。f。b。c。a。0。1。01a

b41Φ{c}1r1l15x{a}{a,c,d}{a,b,d}{b,c,d}{a,b,c}{b,c}{a,d}{b,d}{a,c}{a,b,c,d}{c,d}{a,b}本節(jié)重點掌握布爾代數(shù)的性質(zhì)，同構(gòu)概念，Stone定理及其推論。作業(yè)P260（2）426-4.布爾表達式

此內(nèi)容在開關(guān)理論，邏輯設(shè)計中有著廣泛的應(yīng)用。一.布爾表達式概念1.定義：設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，其上的布爾表達式遞歸定義如下：1)B中任何元素是個布爾表達式。2)任何變元x是個布爾表達式.E1ˉ3)如果E1,E2是個布爾表達式,則

,(E1∧E2),(E1∨E2)也是布爾表達式。

4)有限次地應(yīng)用規(guī)則1)--3),得到的符號串都是布爾表達式.bˉ(x1∨)———例如令B={0,1,a,b}(a∨),((x∧y)∨),*表達式的最外層括號可以省略.432.對布爾表達式賦值：設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，含有變元x1,x2…xn

的布爾表達式記作E(x1,x2,…xn),對變元x1,x2,…,xn分別用B中元素代替的過程，稱之為對布爾表達式賦值。例如B={0,1,a,b}

01a

b(x1∨)———(a∨)———a∨a____aˉE(x1,x2)=E(a,b)====b一個的布爾表達式E(x1,x2,…xn),經(jīng)過賦值以后，就得到一個值(即是B中一個元素)。3.兩個布爾表達式相等:設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，含有變元x1,x2,…xn

的兩個布爾表達式E1(x1,x2,…xn)和E2(x1,x2,…xn),如果不論對變元x1,x2…xn分別用B中任何元素賦值,都使得E1和E2的值相同,則稱這兩個表達式相等,記作

E1(x1,x2,…,xn)=E2(x1,x2,…,xn)44我們可以通過布爾代數(shù)的性質(zhì)(10個)得到很多等式.

如,E1(x,y)=x∨(y∧)E2(x,y)=x∨yE1(x,y)=x∨(y∧)=(x∨y)∧(x∨)=(x∨y)∧1=x∨y=E2(x,y)二.布爾函數(shù)設(shè)<B,∨,∧,ˉ>是布爾代數(shù)，含有變元x1,x2,…,xn

的布爾表達式記作E(x1,x2,…xn),也可以看成是一個函數(shù)f:BnB,稱之為布爾函數(shù).布爾函數(shù)有兩種表示方法:1.代數(shù)法:例如B={0,1}<B,∨,∧,ˉ>是布爾代數(shù)，即是表達式表示法.2.真值表法:見下面:45的真值表如下:x1x2x3f(x1,

x2,

x3)0010010101101000101011000001111146三.布爾表達式的范式

1.有兩個元素的布爾代數(shù)的布爾表達式的范式:

<{0,1},∨,∧,ˉ>是兩個元素的布爾代數(shù)

1).析取范式(相當于命題公式的主析取范式)

(1).小項:含有n個變元的小項形式為:其中例如都是小項.(2).布爾表達式的析取范式:含有變元x1,x2,…,xn

的布爾表達式E(x1,x2,…xn),如果寫成如下形式:A1∨A2∨...∨Am(m≥1)其中每個Ai(1≤i≤m)都是有n個變元的小項.則稱此式是E(x1,x2,…xn)的析取范式.例如:47

2).合取范式(相當于命題公式的主合取范式)

(1).大項:含有n個變元的大項形式為:

其中例如都是大項.(2).布爾表達式的合取范式:含有變元x1,x2,…,xn

的布爾表達式E(x1,x2,…xn),如果寫成如下形式:A1∧A2∧...∧Am(m≥1)其中每個Ai(1≤i≤m)都是有n個變元的大項.則稱此式是E(x1,x2,…xn)的合取范式.例如:3).析取范式與合取范式的寫法:

方法1:列真值表

方法2:表達式的等價變換.48001000010100100010110001方法1.用真值表求析取范式:

先介紹小項的性質(zhì),以兩個變元x1,x2為例每一組賦值,有且僅有一個小項為1.根據(jù)一組賦值,求值為1的小項:如果變元x,被賦值為0,則在此小項中,x以形式出現(xiàn);如果變元x,被賦值為1,則在此小項中,x以原形x形式出現(xiàn).求E(x1,x2,…xn)的析取范式:先列出它的真值表,找出表中每個1對應(yīng)的小項,然后用∨連接上述小項.49例如,求布爾代數(shù)<{0,1},∨,∧,ˉ>上的布爾表達式

x1x2x3E(x1,

x2,

x3)00100100011010011010110100001111x3ˉE(x1,x2,x3)=x1∧(x2∨)的析取范式.x3ˉx3ˉx2ˉE(x1,x2,x3)=(x1∧∧)∨(x1∧x2∧)∨(x1∧x2∧x3)50方法1.用真值表求合取范式:

先介紹大項的性質(zhì),以兩個變元x1,x2為例000111011011101101111110每一組賦值,有且僅有一個大項為0.根據(jù)一組賦值,求值為0的大項:如果變元x,被賦值為1,則在此大項中,x以形式出現(xiàn);如果變元x,被賦值為0,則在此大項中,x以原形x形式出現(xiàn).求E(x1,x2,…xn)的合取范式:先列出它的真值表,找出表中每個0對應(yīng)的大項,然后用∧連接上述大項.51例如,求布爾代數(shù)<{0,1},∨,∧,ˉ>上的布爾表達式

x1x2x3E(x1,

x2,

x3)00100100011010011010110100001111x3ˉE(x1,x2,x3)=x1∧(x2∨)的合取范式.x3ˉx2ˉx3ˉx1ˉx2ˉx3ˉE(x1,x2,x3)=(x1∨x2∨x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(∨x2∨)52方法2.用表達式的等價變換求析取范式:x3ˉx3ˉE(x1,x2,x3)=x1∧(x2∨)=(x1∧x2)∨(x1∧)x2ˉx3ˉx3ˉ=(x1∧x2∧(x3∨))∨(x1∧(x2∨)∧)x2ˉx3ˉx3ˉx3ˉ=(x1∧x2∧x3)∨(x1∧x2∧)∨(x1∧x2∧

)∨(x1∧∧)x3ˉx3ˉx2ˉ=(x1∧x2∧x3)∨(x1∧x2∧)∨(x1∧∧)結(jié)果與前相同.用表達式的等價變換求合取范式:x3ˉE(x1,x2,x3)=x1∧(x2∨)x3ˉx2ˉx1ˉx3ˉ=(x1∨(x2∧)∨(x3∧))∧((x1∧)∨x2∨)x3ˉx2ˉx3ˉx2ˉ=(x1∨x2∨

x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)x1ˉx3ˉx3ˉ∧(x1∨x2∨)∧(∨x2∨)x3ˉx2ˉx1ˉx3ˉx3ˉx2ˉ=(x1∨x2∨

x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(∨x2∨)534).應(yīng)用：在樓梯處安裝一個電燈，在樓下(樓上)有開關(guān)X(Y)，都可以控制此燈，使得有人上摟(或下?lián)?按動開關(guān)X(Y)燈就亮，上樓(或下樓)完畢按動Y(X)開關(guān)后燈就滅。請設(shè)計控制此燈的電路。解：令L為燈，X和Y為開關(guān)，這是雙

XYL110101011000。。。。。。XYXˉYˉL開關(guān)邏輯∧、∨定義為：

X∧YX∨YXˉYˉL=(X∧)∨(∧Y)開關(guān)的控制過程如下:Xˉ位開關(guān)，即一端是X端，另一端是,

假設(shè)開始時開關(guān)X合到X端，開關(guān)Y合到Y(jié)端，此時L是滅的。列出真值表：54。。。。。。XYXˉYˉLXY。。。。。。XYXˉYˉLYX。。。。。。XYXˉYˉLYXX。。。。。。XYXˉYˉLY552.一般的布爾代數(shù)的布爾表達式的范式:

<B,∨,∧,ˉ>是布爾代數(shù),含有變元x1,x2,…,xn

的布爾表達式E(x1,x2,…xn),1).小項:是由n個變元和B中元素構(gòu)成的如下形式,稱為小項.

其中Cδ1δ2...δn為B中元素,我們稱之為小項的系數(shù).

例如B={0,1,a,b},下面就是E(x1,x2,x3)中的小項:2).布爾表達式E(x1,x2,...xn)的析取范式:含有變元x1,x2,…,xn

的布爾表達式E(x1,x2,…xn),如果寫成如下形式:A1∨A2∨...∨Am(m≥1)其中每個Ai(1≤i≤m)都是有n個變元的小項.則稱此式是E(x1,x2,…xn)的析取范式.

56定理7-4.1.設(shè)<B,∨,∧,ˉ>是布爾代數(shù),含有變元x1,x2,…,xn

的布爾表達式E(x1,x2,…xn),則可以寫成析取范式形式.證明:令E(xi=a)=E(x1,x2,..,xi-1,a,xi+1,…,xn)

先通過對|E|歸納證明如下結(jié)論成立:xiˉE(x1,x2,…xn)=(∧E(xi=0))∨(xi∧E(xi=1))先用下面例子理解上邊式子的含義。并驗證結(jié)論成立.

這里|E|為E(x1,x2,…xn)的長度,即其中所含有的B中元素個數(shù)、運算符號個數(shù)、變元個數(shù)的總和(含重復(fù)計數(shù)).例如57(1).如果|E|=1則E=a(a∈B),或者E=xj,(xj是個變量)如果E=a則E(xi=0)=E(xi=1)=a所以|E|=1時,結(jié)論成立.58(2).假設(shè)|E|≤n時,結(jié)論成立.即

(3).當|E|=n+1時,分下面三種情況討論:①如果E=E1∨E2

則|E1|≤n,|E2|≤n,由(2)假設(shè)得,59②如果E=E1∧E2

則|E1|≤n,|E2|≤n,由(2)假設(shè)得,

60③如果61定理得證.通過反復(fù)應(yīng)用此定理,就可以將E(x1,x2,…xn)寫析取范式形式.62xnˉx1ˉx2ˉxnˉx1ˉx2ˉxn-1ˉ類似地,E(x1,x2,…xn)的合取范式為:E(x1,x2,…xn)=(x1∨x2∨...∨xn∨E(0,0,…,0))∧(x1∨x2∨...∨xn-1∨∨E(0,0,…0,1))∧...∧(∨∨...∨∨xn∨E(1,1,…,1,0))∧(∨∨...∨∨E(1,1,…,1))其中E(0,0…,0),E(0,0,…0,1),…,E(1,1,…1,0)和E(1,1,…,1)就是所謂的“系數(shù)”.實際上,求E(x1,x2,…xn)的析取或者合取范式時,就是求這些“系數(shù)”.下面看一個例子.63例.已知<B,∨,∧,ˉ>是布爾代數(shù),

其中B={0,a,b,1}分別求出下面布爾表達式的析取范式和合取范式.01a

b解.先求四個系數(shù):析取范式為:64合取范式為:本節(jié)重點掌握內(nèi)容：布爾表達式定義、析取范式和合取范式的寫法。作業(yè)：P269(1)65本章內(nèi)容小結(jié)：1.格的概念、格的性質(zhì).格的同構(gòu).2.分配格的性質(zhì)、判斷.有界格有補格布爾格概念性質(zhì).3.布爾代數(shù)的性質(zhì),Stone定理的應(yīng)用.4.布爾表達式定義,范式的寫法.66習(xí)題課P242(1).(a)不是格因為d和e沒有下確界,也沒有上確界.(d)不是格5和6沒有下確界,7和8既沒下確界,也沒上確界.進一步問,如果是格,哪些是分配格?哪些是有補格?(b)不是分配格,因去掉結(jié)點i后的子格如圖所示但它是有補格.(c)不是分配格(去m,p),不是有補格.1dabcefghijk5246lmnoqrp387(a)(b)(c)(d)jkf

gh67(2).設(shè)≤是L上的整除關(guān)系,下面偏序集中,哪些是格?a)L={1,2,3,4,6,12},b).L={1,2,3,4,6,8,12,14}c)L={1,2,3,4,5,6,7,8,9,10,11,12}可見只有(a)是格.12462318412531678142111092124613(a)(b)(c)68(4).設(shè)<A,≤>是一個格,任取a,b∈A,a<b(即a≤b∧a≠b),構(gòu)造集合:B={x|x∈A且a≤x≤b},則<B,≤>也是格.證明:顯然B是A的非空子集(因為a≤a≤b,a≤b≤b,所以a,b∈B),只要證明∧和∨在B上封閉即可.任取x,y∈B,由B的構(gòu)成得a≤x≤b,a≤y≤b,于是由格的性質(zhì)得,a≤x∨y≤ba≤x∧y≤b,于是有x∨y∈Bx∧y∈B,說明∨和∧在B上封閉,所以<B,≤>也是格.69(7).設(shè)a,b是格<A,≤>中的兩個元素,證明:a).a∧b=b當且僅當a∨b=a.b).a∧b<b和a∧b<a,當且僅當a與b是不可比較的.證明:a)充分性:已知a∨b=ab=b∧(b∨a)=b∧(a∨b)=b∧a=a∧b

必要性:已知a∧b=b,a=a∨(a∧b)=a∨bb)充分性:已知a與b是不可比較的.因a∧b≤b,a∧b≤a,如果a∧b=b,則有b≤a,如果a∧b=a,則有a≤b,都與a與b是不可比較的矛盾.所以有:

a∧b≤b∧a∧b≠b,于是有a∧b<ba∧b≤a∧a∧b≠a,于是有a∧b<a

必要性:已知a∧b<b和a∧b<a,假設(shè)a與b是可比較的.則要么a≤b,要么b≤a.

于是要么a∧b=a要么a∧b=b.這與a∧b<b和a∧b<a矛盾.所以a與b是不可比較的.70(9).證明格中成立:

a)(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)b)(a∧b)∨(b∧c)∨(c∧a)≤(a∨b)∧(b∨c)∧(c∨a)證明:a)∵(a∧b)≤a≤(a∨c)∴(a∧b)≤(a∨c)∵(c∧d)≤c≤(a∨c)∴(c∧d