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

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

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

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

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

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

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

每一對元素a,bL都擁有一個最小上界和最大下界符號：最大下界：∧

最小上界：∨

復習關系：集合元素間存在的某種關系二元關系：有序偶對集合的關系：AxA的子集

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

A∧B=A∩B∈P(S),A∨B=A∪B∈P(S)∴<P(S),>是一個格。{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格的定義與性質例：I+是正整數(shù)集合，D是整除關系，<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>是格，因為a，b∈I+都有最大公約數(shù)和最小公倍數(shù)。11.1格的定義與性質練習：習題十一，第5題11.1格的定義與性質對偶式：格中元素用運算符∧,∨連接起來的的一個表達式f

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

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

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

（2）結合律：(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格的定義與性質證明結合律：(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因為≥的反對稱性，(a∨b)∨c=a∨(b∨c)11.1格的定義與性質

定理：設<L,?>是一格，則對于所有的a,b∈L

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

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

a

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

aL，有吸收律得

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

同理有：

a

a=a定義二元關系?：

a，bL

a?ba

b＝b

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

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

aL，a

a＝a，

故a?a反對稱性：

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格的定義與性質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}的上界設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格的定義與性質子格：設<L，

∧，∨>是格，H是L的非空子集，如果H關于L中的運算∧，∨仍構成格，稱<H，

∧，∨>是<L，

∧，∨>的子格

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

11.1格的定義與性質格同構：設<L，

∧，∨>和<S，*，>是二個格，定義一函數(shù)f:L→S。若對任何的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ù)，則稱為格同構11.1格的定義與性質例：（1）具有一個，二個，三個元素的格分別同構于一，二，三個元素的鏈；（2）具有四個元素的格分別同構于下面二個格；（3）具有五個元素的格則一定同構于下頁五個格之一；11.1格的定義與性質11.1格的定義與性質第十一章:格與布爾代數(shù)

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

11.2分配格、有補格分配格：設<L，

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

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

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

∧，∨>，

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

a2≤a1

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

∧，∨，1，0>

若L是有限集，則<L,?>一定是有界格例:<P(S),∩,∪>，P(S)是集合S的冪集最大元是全集S,最小元是例:<I+,D>不是有界格,因其不存在最大元,(最小元是存在的,是整數(shù)1)11.2分配格、有補格有界格的性質:在有界格中成立,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分配格、有補格補元:設<L，

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

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

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

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

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有補格:如果在一個有界格中，每個元素都至少有一個補元素，則稱此格為有補格。11.2分配格、有補格第十一章:格與布爾代數(shù)

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

布爾代數(shù)簡介

1854年由GeorgeBoole在他的著作:TheLawsofThought中提出是捕獲了集合運算和邏輯運算二者的根本性質的一個代數(shù)結構在電子工程和計算機科學中有很多實踐應用電子工程領域專門化了的布爾代數(shù)也叫做邏輯代數(shù)計算機科學領域專門化了布爾代數(shù)也叫做布爾邏輯

布爾代數(shù):又稱有補(有界)分配格。由于是有補格,每個元素均存在補元,由于是有補分配格,每個元素均存在且有唯一的補元,因而求補元可以看作是一個運算,可以‘把a的補元記為a’,今后用<B，∧，∨，，0，1>來表示一個布爾代數(shù)。11.2布爾代數(shù)41格有界格有補格布爾代數(shù)分配格結合律吸收律交換律冪等律同一律零一律互補律分配律德·摩根律雙重否定律11.2布爾代數(shù)常見的布爾代數(shù)：<P(A),∪,∩,~,,A>是個布爾代數(shù),稱此為集合代數(shù),其中,補運算~,最小元,最大元AS是命題公式的全體,則<S,∨,∧,?,0,1>是一個布爾代數(shù),稱之為命題代數(shù)數(shù)字電路中的邏輯代數(shù)為布爾代數(shù)11.2布爾代數(shù)定理：給定布爾代數(shù)<B，∧，∨，，0，1>對于每一個a∈B，都有(a)=a對任意元素a,bB,a和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ù)等價定義：設<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,對a∈B,a*1=a,a0=a(同一律)H4:a∈B,有一a∈B,使

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

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

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中質因數(shù)分解中質因數(shù)不重復。故﹁x與x的質因數(shù)沒有重復的?！唳鑨*x=1,﹁xx=(﹁x)∪(x)=110互補律是成立,∴<S110,*,,﹁,1,110>是布爾代數(shù)。11.2布爾代數(shù)定理：設<B，∧，∨，，0，1>是布爾代數(shù),則成立如下運算律(1)交換律

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

(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ù)定理：設<B，∧，∨，，0，1>是布爾代數(shù),則成立如下運算律(6)同一律

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

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

(a∧b)=a∨b

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

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

，∧，∨，，0，1>是子布爾代數(shù)，當然也是布爾代數(shù)；（2）S={b,c,a,0}，則<S,*,,,0,c>是布爾代數(shù)，但不是子布爾代數(shù)；a1ccba0b11.2布爾代數(shù)同態(tài)映射f：設<B，∧，∨，，0，1>和<B,,,－,α,β>是兩個布爾代數(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是同構映射。11.2布爾代數(shù)元素a覆蓋元素b：b≤a且b≠a，即b<a，并且在此格中再沒有別的元素c，使得b<c和c<a原子：設<B，∧，∨，，0，1>是一個布爾代數(shù)，a∈B,如果a覆蓋0，則稱元素a是該布爾代數(shù)的一個原子11.2布爾代數(shù)定理：元素a是布爾代數(shù)<B，∧，∨，，0，1>的原子，當且僅當a≠0時，對任意元素x∈B，有

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

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

證明: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若兩者同時成立，則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ù)定理：設<B，∧，∨，，0，1>是一個有限布爾代數(shù)，則對于每一個非零元素x∈B，至少存在一個原子a，使x*a=a(即a≤x)。證明：若x是原子，則x*x=x，此x就是所求的原子a。若x不是原子，因為x≥0，所以，從x下降到0有一條路徑，又由于B是有限的，此路徑所經(jīng)過的結點是有限的，不妨設為

x≥a1≥a2≥…≥ak≥0則ak覆蓋0，而x*ak=ak，此ak就是所求的原子a。11.2布爾代數(shù)引理1：a1和a2是布爾代數(shù)<B，∧，∨，，0，1>中的兩個原子，若a1≠a2，則a1*a2＝0引理2：設<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因為ai≤x(i=1,2,…,k)，所以，y≤x。下面證明x≤y。只需證明x*y=0就可以了。反證法：設x*y≠0，于是必有一個原子a，使a≤x*y，又因x*y≤x和x*y≤y，由傳遞性

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

設<B，∧，∨，，0，1>是一個有限布爾代數(shù)，S是此代數(shù)中的所有原子的集合，則<B，∧，∨，，0，1>同構于冪集代數(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對運算∨封閉，對S的任一子集S1={a1,a2,…,ak}都存在a1∨a2∨…∨ak=x∈B，使f(x)=S1,所以，f是滿射的。2）設x和y是B的任意兩元素，x≠y，則要么x≤y或者y≤x要么x*y=0假設A：x*y=0，于是x*y≠0，存