離散下-2010-11格單擊以文本

第十一章:格與布爾代數(shù)

第一節(jié)：格的定義與性質(zhì)第二節(jié)：分配格、有補(bǔ)格與布爾代數(shù)

第十一章:格與布爾代數(shù)

第一節(jié)：格的定義與性質(zhì)

第二節(jié)：分配格、有補(bǔ)格與布爾代數(shù)

引言格和布爾代數(shù)都是抽象的代數(shù)系統(tǒng)，與前面不同的是在于格和布爾代數(shù)中次序關(guān)系具有重要的意義格首先在偏序集合的基礎(chǔ)上進(jìn)行討論，然后施加某些限制可得到布爾代數(shù)。布爾代數(shù)是一種特殊的代數(shù)系統(tǒng)，而且是一種特殊的格格個(gè)也是一類非常重要的代數(shù)結(jié)構(gòu)11.1格的定義與性質(zhì)格：偏序集合<L,?>，滿足

每一對(duì)元素a,bL都擁有一個(gè)最小上界和最大下界符號(hào)：最大下界：∧

最小上界：∨

復(fù)習(xí)關(guān)系：集合元素間存在的某種關(guān)系二元關(guān)系：有序偶對(duì)集合的關(guān)系：AxA的子集

自反關(guān)系，對(duì)稱關(guān)系，傳遞關(guān)系偏序集的極大元素（不小于任何其他元素，不唯一）、極小元素（不唯一）、最大元素（大于每個(gè)其他元素，若存在，則唯一）、最小元素偏序集的子集A的一個(gè)上界（大于A中的所有元素）；子集A的一個(gè)下界（小于A中的所有元素）偏序集的子集A的最小上界：如果x是一個(gè)上界并且小于A的其他上屆，若存在，則唯一偏序集的子集A的最大下界：如果x是一個(gè)下界并且大于A的其他下屆，若存在，則唯一(a)(b)(c)(d)11.1格的定義與性質(zhì)(f)(g)ab(h)不是格abcd(i)11.1格的定義與性質(zhì)練習(xí)：習(xí)題十一1:（c),(f)2:（2）11.1格的定義與性質(zhì)例1:設(shè)S是一集合,P(S)是S的冪集,則<P(S),>是一個(gè)偏序集,A,B∈P(S),易證明,

A∧B=A∩B∈P(S),A∨B=A∪B∈P(S)∴<P(S),>是一個(gè)格。{a}S={a}{a,b}{a}S={a,b}{a,b,c}{b,c}{c}{a}{a,b}{a,c}S={a,b,c}11.1格的定義與性質(zhì)例：I+是正整數(shù)集合，D是整除關(guān)系，<I+，D>是偏序集，a，b∈I+，

a∧b=最大公約數(shù)，a∨b=最小公倍數(shù)證明：若c是{a，b}的下界，則c≤a，c≤b，即c能整除a，能整除b，所以c是a，b的公約數(shù)。

若c是{a，b}的最大下界，則c是a，b的最大公約數(shù)。反之，同樣可證。因此，<I+，D>是格，因?yàn)閍，b∈I+都有最大公約數(shù)和最小公倍數(shù)。11.1格的定義與性質(zhì)練習(xí)：習(xí)題十一，第5題11.1格的定義與性質(zhì)對(duì)偶式：格中元素用運(yùn)算符∧,∨連接起來(lái)的的一個(gè)表達(dá)式f

，如將f中的∧換成∨，將∨換成∧，所形成的表達(dá)式稱為f的對(duì)偶式記作f*對(duì)偶命題：兩個(gè)表達(dá)式f,g用關(guān)系符≤,≥連接成為命題，將表達(dá)式f,g用f*,g*代替，≤與≥互換，形成的命題稱為原命題的對(duì)偶命題例：f=(a∨b)∧c?c，則f*=(a∧b)∨c?c習(xí)題十一：第4題（2）11.1格的定義與性質(zhì)設(shè)f是含有格中元素以及符號(hào)＝，?，?，∨，∧等的命題。若f對(duì)一切格為真，則f的對(duì)偶命題f*也對(duì)一切格為真例：如果對(duì)一切格L，a,bL,(a∨b)∧c?c

則f*=(a∧b)∨c?c11.1格的定義與性質(zhì)對(duì)偶原理:定理：設(shè)<L,≤>是一格，則對(duì)于所有的a,b,c∈L有：

（1）交換律：a∨b=b∨a，a∧b=b∧a

（2）結(jié)合律：(a∨b)∨c=a∨(b∨c)(a∧b)∧c=a∧(b∧c)

（3）冪等律：a∨a=a，a∧a=a

（4）吸收律：a∨(a∧b)=a，a∧(a∨b)=a

11.1格的定義與性質(zhì)證明結(jié)合律：(a∨b)∨c=a∨(b∨c)(a∨b)∨c?a∨b?a(a∨b)∨c?a∨b?b(a∨b)∨c?c∴(a∨b)∨c為b和c的上屆∴(a∨b)∨c?b∨c∴(a∨b)∨c?a∨(b∨c)同理a∨(b∨c)

?

(a∨b)∨c因?yàn)椤莸姆磳?duì)稱性，(a∨b)∨c=a∨(b∨c)11.1格的定義與性質(zhì)

定理：設(shè)<L,?>是一格，則對(duì)于所有的a,b∈L

a?ba∧b=aa∨b=b定理：設(shè)<L,?>是一格，則對(duì)于所有的a,b，c,d∈L

a?b且d?c(a∨d)?(b∨c)a?b且d?c(a∧d)?(b∧c)11.1格的定義與性質(zhì)格是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)<L,∨,∧>，運(yùn)算滿足交換律，結(jié)合律，冪等律，吸收律，能否根據(jù)運(yùn)算極其性質(zhì)來(lái)給出格的定義呢？格的另一種定義：設(shè)<L,*,>是一個(gè)代數(shù)系統(tǒng)，L是一非空集合，*和是L上的二個(gè)二元運(yùn)算。若*和滿足交換律，結(jié)合律，冪等律，吸收律，則稱此代數(shù)系統(tǒng)為格11.1格的定義與性質(zhì)為什么可以這么定義？19設(shè)<L,*,>是一個(gè)具有二元運(yùn)算的代數(shù)系統(tǒng)，且*和滿足交換律，結(jié)合律，吸收律，則在L中一定存在一個(gè)偏序關(guān)系?，使得<L,?>構(gòu)成一個(gè)格，且對(duì)任給a,b∈L，在此偏序作用下，有

a

b=a∨b，a*b=a∧b11.1格的定義與性質(zhì)對(duì)應(yīng)定理:20證明：先證*和滿足冪等律

aL，有吸收律得

a*a=a*(a(a*a))=a

同理有：

a

a=a定義二元關(guān)系?：

a，bL

a?ba

b＝b

需要證明?是L上的偏序且<L,?>為格11.1格的定義與性質(zhì)21證明?是L上的偏序（a?ba

b＝b）自反性：根據(jù)冪等律，

aL，a

a＝a，

故a?a反對(duì)稱性：

a，bLa?b且b?aa

b＝b且b

a＝aa＝b

a＝a

b＝b(適合交換律）傳遞性：

a，b，cLa?b且b?ca

b＝b且b

c＝ca

c＝a

(b

c)＝(a

b)

c

＝b

c=ca?c11.1格的定義與性質(zhì)22證明<L,?>為格（a?ba

b＝b）最小上界存在性：

a，bLa

（a

b)＝(a

a)

b＝a

bb

（a

b)＝a

(b

b)＝a

ba?a

b且b?a

b，故a

b是{a,b}的上界設(shè)c為{a,b}的上界，則a

c＝c且b

c＝c,故(a

b)

c＝a

（b

c）＝a

c＝ca

b?c，故

a

b是{a,b}的最小上界

同理可證最大上界存在性11.1格的定義與性質(zhì)子格：設(shè)<L，

∧，∨>是格，H是L的非空子集，如果H關(guān)于L中的運(yùn)算∧，∨仍構(gòu)成格，稱<H，

∧，∨>是<L，

∧，∨>的子格

思考:圖11.7,L2的所有子格

11.1格的定義與性質(zhì)格同構(gòu)：設(shè)<L，

∧，∨>和<S，*，>是二個(gè)格，定義一函數(shù)f:L→S。若對(duì)任何的a,b∈L有

f(a∧b)=f(a)*f(b)，f(a∨b)=f(a)f(b)則稱f是從<L,*,>到<S,∧,∨>的格同態(tài)若f為滿射函數(shù)，則稱為滿同態(tài)若f為雙射函數(shù)，則稱為格同構(gòu)11.1格的定義與性質(zhì)例：（1）具有一個(gè)，二個(gè)，三個(gè)元素的格分別同構(gòu)于一，二，三個(gè)元素的鏈；（2）具有四個(gè)元素的格分別同構(gòu)于下面二個(gè)格；（3）具有五個(gè)元素的格則一定同構(gòu)于下頁(yè)五個(gè)格之一；11.1格的定義與性質(zhì)11.1格的定義與性質(zhì)第十一章:格與布爾代數(shù)

第一節(jié)：格的定義與性質(zhì)第二節(jié)：分配格、有補(bǔ)格與布爾代數(shù)

11.2分配格、有補(bǔ)格分配格：設(shè)<L，

∧，∨>是格,且a,b,c∈La∧(b∨c)=(a∧b)∨(a∧c),a∨(b∧c)=(a∨b)∧(a∨c)例:格<P(S),>是分配格，例:格<I+,D>是分配格。例:如圖兩個(gè)格均不是分配格cbdbaeacde

鉆石格如b*(cd)和(b*c)(b*d)

五角格如c(e*b)和(ce)*(cb)11.2分配格、有補(bǔ)格分配格的充分必要條件定理I：設(shè)L是格，則L是分配格當(dāng)且僅當(dāng)L中不含與鉆石格或五角格同構(gòu)的子格推論小于五元的格都分配格任何一條鏈都是分配格充分必要條件定理II：設(shè)格<L，

∧，∨>，

L為分配格當(dāng)且僅當(dāng)a,b,c∈L,a*c=b*c且ac=bc,推出a=b11.2分配格、有補(bǔ)格31全上（下）界a：給定格<L,?>，若存在a,對(duì)于任何元素b，都有b?a(a?b)一個(gè)格，若存在全下界（全上界），則是唯一的分別記為0（1）證明：若a1a2都是格的全下界，則a1≤a2

a2≤a1

反對(duì)稱性a1=a211.2分配格、有補(bǔ)格32有界格<L,?>：<L,?>為格，若L存在全下界（最大元）和全上屆（最小元）記作<L，

∧，∨，1，0>

若L是有限集，則<L,?>一定是有界格例:<P(S),∩,∪>，P(S)是集合S的冪集最大元是全集S,最小元是例:<I+,D>不是有界格,因其不存在最大元,(最小元是存在的,是整數(shù)1)11.2分配格、有補(bǔ)格有界格的性質(zhì):在有界格中成立,a∈L同一律：a0=a,a*1=a零一律：a*0=0,a1=1證明:因0是最小元,a∈L,0≤a

a*0=0a0=a1是最大元,a∈L，a≤1

a*1=a,a1=111.2分配格、有補(bǔ)格補(bǔ)元:設(shè)<L，

∧，∨，0，1>是有界格,a∈L,如果存在元素b∈L使得

a∧b=0，a∨b=1則稱b為元素a的補(bǔ)元素(或稱為余元素)，記為a

在有界格中，有的元素存在補(bǔ)元素,也可能有的元素不存在補(bǔ)元素也可能有的元素存在兩個(gè)或兩個(gè)以上元素11.2分配格、有補(bǔ)格1x1x30x2x1的補(bǔ)元有兩個(gè)x2,x3,而,x3的補(bǔ)元只有一個(gè)是x1,0和1是互為補(bǔ)元。8126312424在<S24,D>中,最大元為24,最小元為1,1和24互為補(bǔ)元,3和8互為補(bǔ)元，因3*8=1,3+8=24,2,4,6,12的補(bǔ)元是什么？11.2分配格、有補(bǔ)格在圖中的有界格中，0和1互為補(bǔ)元，x1x2x3的補(bǔ)元是什么？1x1x3x2011.2分配格、有補(bǔ)格補(bǔ)元唯一性定理:在有界分配格中，如果元素a∈L有一個(gè)補(bǔ)元，則此補(bǔ)元是唯一的

證明：假定b和c都是a的補(bǔ)元，則

a*b=0=a*cab=1=ac

由于L是分配格，從而有

b=b*(ba)=b*(ca)=(b*c)(b*a)=(b*c)(c*a)=(ba)*c=(ca)*c=c有補(bǔ)格:如果在一個(gè)有界格中，每個(gè)元素都至少有一個(gè)補(bǔ)元素，則稱此格為有補(bǔ)格。11.2分配格、有補(bǔ)格第十一章:格與布爾代數(shù)

第一節(jié)：格的定義與性質(zhì)第二節(jié)：分配格、有補(bǔ)格與布爾代數(shù)

布爾代數(shù)簡(jiǎn)介

1854年由GeorgeBoole在他的著作:TheLawsofThought中提出是捕獲了集合運(yùn)算和邏輯運(yùn)算二者的根本性質(zhì)的一個(gè)代數(shù)結(jié)構(gòu)在電子工程和計(jì)算機(jī)科學(xué)中有很多實(shí)踐應(yīng)用電子工程領(lǐng)域?qū)ｉT(mén)化了的布爾代數(shù)也叫做邏輯代數(shù)計(jì)算機(jī)科學(xué)領(lǐng)域?qū)ｉT(mén)化了布爾代數(shù)也叫做布爾邏輯

布爾代數(shù):又稱有補(bǔ)(有界)分配格。由于是有補(bǔ)格,每個(gè)元素均存在補(bǔ)元,由于是有補(bǔ)分配格,每個(gè)元素均存在且有唯一的補(bǔ)元,因而求補(bǔ)元可以看作是一個(gè)運(yùn)算,可以‘把a(bǔ)的補(bǔ)元記為a’,今后用<B，∧，∨，，0，1>來(lái)表示一個(gè)布爾代數(shù)。11.2布爾代數(shù)41格有界格有補(bǔ)格布爾代數(shù)分配格結(jié)合律吸收律交換律冪等律同一律零一律互補(bǔ)律分配律德·摩根律雙重否定律11.2布爾代數(shù)常見(jiàn)的布爾代數(shù)：<P(A),∪,∩,~,,A>是個(gè)布爾代數(shù),稱此為集合代數(shù),其中,補(bǔ)運(yùn)算~,最小元,最大元AS是命題公式的全體,則<S,∨,∧,?,0,1>是一個(gè)布爾代數(shù),稱之為命題代數(shù)數(shù)字電路中的邏輯代數(shù)為布爾代數(shù)11.2布爾代數(shù)定理：給定布爾代數(shù)<B，∧，∨，，0，1>對(duì)于每一個(gè)a∈B，都有(a)=a對(duì)任意元素a,bB,a和b有補(bǔ)元素a',b',則(a∧b)'=a'∨b',(a∨b)'=a'∧b'證明：①顯然成立，證明②(a∧b)∨(a'∨b')=(a∨a'∨b)∧(b∨a'∨b')=1類似可以證明：(a∧b)∧(a'∨b')=0

所以(a∧b)'=a'∨b'

同理可以證(a∨b)'=a'∧b'11.2布爾代數(shù)等價(jià)定義：設(shè)<B,*,>是代數(shù)系統(tǒng),如果a,b,c∈B,滿足如下：H1:a*b=b*a,ab=ba(交換律)H2:a*(bc)=a*ba*c,a(b*c)=(ab)*(ac)(分配律)H3:B中有元素0和1,對(duì)a∈B,a*1=a,a0=a(同一律)H4:a∈B,有一a∈B,使

aa=1,a*a=0(互補(bǔ)律)則<B,*,

,,0,1>是布爾代數(shù)(有補(bǔ)分配格)11.2布爾代數(shù)例：設(shè)S110={1,2,5,10,11,22,55,110}是110的所有因數(shù)的集合,令glb,lub是最大公約數(shù)和最小公倍數(shù)運(yùn)算。下面簡(jiǎn)記為glb—*,lub—證明<S110,*,>是一個(gè)布爾代數(shù)。證明:110=1×2×5×11質(zhì)因子分解式中因子是不重復(fù)的。記(x)為x分解的質(zhì)因數(shù)的集合,例(55)={1,5,11}。容易驗(yàn)證,交換律顯然成立。

11.2布爾代數(shù)x,y,z∈S110,x*(yz)=(x)∩((y)∪(z))=((x)∩(y))∪((x)∩(z))=(x*y)(x*z)同理x(y*z)＝(xy)*(xz)分配律成立。顯然1是S110的最小元,110是S110的最大元。x*110=x,x1=x,同一律成立。11.2布爾代數(shù)記﹁x=110/x,因110中質(zhì)因數(shù)分解中質(zhì)因數(shù)不重復(fù)。故﹁x與x的質(zhì)因數(shù)沒(méi)有重復(fù)的。∴﹁x*x=1,﹁xx=(﹁x)∪(x)=110互補(bǔ)律是成立,∴<S110,*,,﹁,1,110>是布爾代數(shù)。11.2布爾代數(shù)定理：設(shè)<B，∧，∨，，0，1>是布爾代數(shù),則成立如下運(yùn)算律(1)交換律

a∧b=b∧a,a∨b=b∨a(2)結(jié)合律

(a∧b)∧c=a∧(b∧c),

(a∨b)∨c=a∨(b∨c)(3)冪等律

a∧a=a,a∨a=a(4)吸收律

a∧(a∨b)=a,a∨(a∧b)=a(5)分配律

a∨(b∧c)=(a∨b)∧(a∨c)a∧(b∨c)=(a∧b)∨(a∧c)11.2布爾代數(shù)定理：設(shè)<B，∧，∨，，0，1>是布爾代數(shù),則成立如下運(yùn)算律(6)同一律

a∨0=a,a∧1=a(7)零一律

a∨1=1,a∧0=0(8)互補(bǔ)律a∨a=1,a∧a=0(9)雙重否定律a=a(10)德·摩律(a∨b)=a∧b

(a∧b)=a∨b

11.2布爾代數(shù)子布爾代數(shù)H：設(shè)<B，∧，∨，，0，1>是一個(gè)布爾代數(shù)H是B的一個(gè)子集H包含0和1，H對(duì)∧，∨，運(yùn)算封閉

子布爾代數(shù)也是布爾代數(shù)11.2布爾代數(shù)例：考察下圖所示的布爾代數(shù)（1）S={a,a,0,l},則<S

，∧，∨，，0，1>是子布爾代數(shù)，當(dāng)然也是布爾代數(shù)；（2）S={b,c,a,0}，則<S,*,,,0,c>是布爾代數(shù)，但不是子布爾代數(shù)；a1ccba0b11.2布爾代數(shù)同態(tài)映射f：設(shè)<B，∧，∨，，0，1>和<B,,,－,α,β>是兩個(gè)布爾代數(shù),f是從B到B的映射,且滿足f(a+b)=f(a)f(b)f(a·b)=f(a)f(b)f(a)=f(0)=α;f(1)=β若f是單射,稱f是單同態(tài)；如f是滿射,稱f是滿同態(tài)。若f是雙射,稱f是同構(gòu)映射。11.2布爾代數(shù)元素a覆蓋元素b：b≤a且b≠a，即b<a，并且在此格中再?zèng)]有別的元素c，使得b<c和c<a原子：設(shè)<B，∧，∨，，0，1>是一個(gè)布爾代數(shù)，a∈B,如果a覆蓋0，則稱元素a是該布爾代數(shù)的一個(gè)原子11.2布爾代數(shù)定理：元素a是布爾代數(shù)<B，∧，∨，，0，1>的原子，當(dāng)且僅當(dāng)a≠0時(shí)，對(duì)任意元素x∈B，有

x*a=a(a<x)或x*a=0(不可比較)必要性證明：因?yàn)閤*a≤a，而a是原子，所以

x*a=a或x*a=0充分性證明：若a≠0不是原子，則存在一個(gè)元素x∈B，使a>x>0，于是有x*a=x，這與假設(shè)時(shí)“a≠0時(shí)，對(duì)任意元素x∈B，有x*a=a或x*a=0”相矛盾。所以，a是原子。11.2布爾代數(shù)推論：a是布爾代數(shù)<B，∧，∨，，0，1>的原子，x是B的任意元素，則或者a≤x，或者a≤x，但不能同時(shí)成立。

證明:x*a=aa≤x,x*a=0a≤x

a*(x

∨x)=a(a*x)∨(a*x)=a(a*x)∨0=aa*x=a根據(jù)前面的定理，如果a是原子，x是B的任意元素a≤x或a≤x若兩者同時(shí)成立，則a≤x*x=0，這與a>0矛盾。11.2布爾代數(shù)圖中{a},,{c}是原子，虛線表示原子{c}將B的元素分為兩類。{c}{b,c}{a,c}{a,b,c}?{a}{a,b}11.2布爾代數(shù)定理：設(shè)<B，∧，∨，，0，1>是一個(gè)有限布爾代數(shù)，則對(duì)于每一個(gè)非零元素x∈B，至少存在一個(gè)原子a，使x*a=a(即a≤x)。證明：若x是原子，則x*x=x，此x就是所求的原子a。若x不是原子，因?yàn)閤≥0，所以，從x下降到0有一條路徑，又由于B是有限的，此路徑所經(jīng)過(guò)的結(jié)點(diǎn)是有限的，不妨設(shè)為

x≥a1≥a2≥…≥ak≥0則ak覆蓋0，而x*ak=ak，此ak就是所求的原子a。11.2布爾代數(shù)引理1：a1和a2是布爾代數(shù)<B，∧，∨，，0，1>中的兩個(gè)原子，若a1≠a2，則a1*a2＝0引理2：設(shè)<B，∧，∨，，0，1>是有限布爾代數(shù)，x是B中任意非0元素，a1,a2,…ak是滿足ai≤x的所有原子(i=1,2,…,k),則

x=a1∨a2∨…∨ak11.2布爾代數(shù)證明：記y=a1a2…ak因?yàn)閍i≤x(i=1,2,…,k)，所以，y≤x。下面證明x≤y。只需證明x*y=0就可以了。反證法：設(shè)x*y≠0，于是必有一個(gè)原子a，使a≤x*y，又因x*y≤x和x*y≤y，由傳遞性

a≤x和a≤y因?yàn)閍是一個(gè)原子，且滿足a≤x，所以a必是a1,a2,…,ak中的一個(gè)，因此a≤y。但這與a≤y矛盾。故x*y’=0，即x≤y。11.2布爾代數(shù)

設(shè)<B，∧，∨，，0，1>是一個(gè)有限布爾代數(shù)，S是此代數(shù)中的所有原子的集合，則<B，∧，∨，，0，1>同構(gòu)于冪集代數(shù)<P(S)，∩，∪，，?，S>

。證明：作一映射f:B→P(S)

f(x)=?x=0{a|a∈S∧a≤x}x≠0我們首先證明f是雙射函數(shù)11.2布爾代數(shù)有限布爾代數(shù)表示定理：

1）由于B對(duì)運(yùn)算∨封閉，對(duì)S的任一子集S1={a1,a2,…,ak}都存在a1∨a2∨…∨ak=x∈B，使f(x)=S1,所以，f是滿射的。2）設(shè)x和y是B的任意兩元素，x≠y，則要么x≤y或者y≤x要么x*y=0假設(shè)A：x*y=0，于是x*y≠0，存