1、引言7.1格7.2分配格7.3有補格7.4布爾代數7.5布爾表達式第七章 格與布爾代數對于計算機科學來說，格與布爾代數是兩個重要的代數系統。在開關理論計算機的邏輯設計，及其它一些科學領域中，都直接應用了格與布爾代數。引 言引 言格的結構是基于偏序關系。偏序：自反、反對稱、傳遞。布爾代數是特殊的格。命題代數和集合代數都是布爾代數的特例。此兩個系統有一個重要特點：強調次序關系。7.1格一、格的定義1、概念2、對偶原理3、基本性質二、格是代數系統1、作為代數系統的格的定義2、偏序集合的格、代數集合的格的關系三、子格 1、子格2、格同態一、格的定義(1)若集合A上的二元關系滿足自反性、反對稱性、傳遞性

2、，稱A為偏序集合。aRb記為ab, 它可用哈斯圖表示。1、偏序集合的一些概念(2) 設A,是偏序集合，B是A的子集。 若bB，ba，則a是子集B的上界。 若a也是B的上界，有aa，稱a是子集B的最小上界，記為lub (B); 若 bB，ab，則a是子集B的下界。 若a也是B的下界，有aa，稱a是子集B的最大下界，記為glb(B)。(3)最大下界、最小上界若存在，則唯一。 設A,是偏序集，若a,bA，都有最大下界、最小上界；則稱A,是個格，且記 glb(a,b)=ab， lub(a,b)=ab, 并稱它們為交和并。注1：由于最大下界、最小上界若存在則唯一，所以交、并是二元運算；注2：稱為由格所誘

3、導的代數系統。 一、格的定義例1：設n是正整數，Sn是n的正因子的集合。D為整除關系，則偏序集構成格。x, ySn，xy是lcm(x,y)，即x與y的最小公倍數。xy是gcd(x,y)，即x與y的最大公約數。1、格的實例例2：判斷下列偏序集是否構成格，并說明理由。(1) ，其中(B)是集合B的冪集。(2) ，其中Z是整數集，為小于或等于關系。(3) 偏序集的哈斯圖分別在圖中給出。1、格的實例解： (1) 是格。x,y (B)，xy就是xy，xy就是xy。由于和運算在(B)上是封閉的，所以xy，xy (B)。稱，為B的冪集格。(2) 是格。 x,yZ,xymax(x,y)，xymin(x,y)，

4、它們都是整數。(3) 都不是格。(a) 中的a,b沒有最大下界。(b) 中的b,d有兩個上界c和e，但沒有最小上界。(c) 中的b,c有三個上界d,e,f，但沒有最小上界。(d) 中的a,g沒有最大下界。 集合S的偏序關系的逆關系也是偏序關系，若AS, 其中 的glb(A) 對應于 的lub(A), 的lub(A) 對應于 的glb(A), 所以，若是格，則也是格， 稱這兩個格互為對偶。2、格的對偶原理 因為的交是的并， 的并是的交， 所以，關于格的一般性質的任意命題， 如用替換，用替換，用替換， 格的一般性質的任意命題仍成立，這稱為格的對偶原理。2、格的對偶原理1）自反性 aa 對偶：aa2

5、）反對稱性 ab ba a=b 對偶：ab ba a=b3）傳遞性 ab bc ac 對偶：ab bc ac 3、格的基本性質4）最大下界描述之一 aba 對偶：aba abb 對偶：abb5）最大下界描述之二 ca,cb cab 對偶：ca,cb cab3、格的基本性質6）結合律 a(bc)=(ab)c 對偶：a(bc)=(ab)c證：令R=a(bc)，R=(ab)c 則由4） Ra, Rbc Ra, Rb, Rc Rab, Rc R(ab)c RR 同理可證：RR 所以 R=R注：格的證明思路總是利用反對稱性。3、格的基本性質7）等冪律 aa=a 對偶： aa=a8）吸收律 a(ab)=a

6、 對偶： a(ab)=a證：因為 aab, aa 所以 aa(ab) 又 aa(ab) 所以 a = a(ab)3、格的基本性質證：） ab aa, ab aab 又 aab a=ab ） ab=a 若ba且ba, 則與ab=a 矛盾 若a,b不可比較，則與ab=a 矛盾 ab9)ab ab=a ab ab=b3、格的基本性質證： aba, ac abc abb, bd abd abcd同理可證： ac, bd abcd10) ac,bd abcd abcd3、格的基本性質證：因為aa, bc 由性質10) 知 abac #同理可證： abac11）保序性 bc abac abac3、格的基本

7、性質證： aab, aac a(ab)(ac) bab, cac bc(ab)(ac)（性質10） a(bc)(ab)(ac) 12）分配不等式 a(bc)(ab)(ac) 對偶：a(bc)(ab)(ac)3、格的基本性質證：）若ac 則ac=c 代入分配不等式 a(bc)(ab)(ac)=(ab)c ）若a(bc)(ab)c 因為aa(bc)(ab)c c 所以ac13）模不等式 ac a(bc)(ab)c3、格的基本性質（可用代數系統的有關概念應用于格）1、作為代數系統的格的定義 設是個代數系統，, 是L上二個二元運算，若二元運算,均滿足結合律、交換律、吸收律(a(ab)=a，a(ab)=

8、a)、等冪律(aa=a，aa=a)，稱是格。注：定義中的等冪律可以消除，因它可由吸收律推得。 aa= a( a( aa)=a二、格是代數系統定理4：若是一個格（作為代數系統），那么，L中存在一偏序關系，使a,bL，有： ab=lub(a,b), ab=glb(a,b)。2、偏序集合的格、代數系統的格二者定義是等價的。二、格是代數系統分三步： 1) 證明是L上的偏序關系 2）證明 a,bL, a,b的下確界存在， 且 ab = glb(a,b)。 3）a,bL, a,b的上確界存在，且 lub(a,b) ab 具體證法見后面偏序集合的格、代數系統的格二者定義是等價的證明證：在集合L上定義的二元關

9、系如下： a,bL，若ab ab = a1) 證明是L上的偏序關系 自反性：aL 由等冪律 aa=a, aa 反對稱性：a,bL, 若ab, ba 則 ab=a, ba=b a = ab = ba = b 傳遞性：a,b,cL, 若 ab,bc 則ab=a, bc=b ac=(ab)c = a(bc)= ab=a ac 2）證明 a,bL, a,b的下確界存在， 且 ab=glb(a,b)。b) 設c 是a,b 的任一下界， 即cb, ca 則cab 因為 c(ab)= (ca)b=cb=c cab ab 是a,b的下界。a) 因為(ab)a =(aa)b=ab aba 同理abb ab 是a

10、,b的下界。3) 同理可證：a,bL, a,b的上確界存在， 且lub(a,b)=ab由1）2）3）知：是一個格。 以后可根據需要，隨意使用這二種定義和記法。1、子格定義： 是個格，SL，若S對運算和封閉，則稱是的子格。子格是個格，因結合律、交換律、吸收律是繼承的。 三、子格、格同態例：設格L如圖所示。令S1=a，e，f，g，S2=a，b，e，g則S1不是L的子格，S2是L的子格。因為對于e和f，有ef=c，但cS12、格同態定義： ，是二個格，f：SL 且a,bS 有f(a*b)=f(a)f(b) f(ab)=f(a)f(b) 稱f是到的格同態；若f是雙射則稱和是同構的。三、子格、格同態例：

11、 (1)設L1=2n|nZ+， L2=2n+1|nN 則L1和L2關于通常數的小于或等于關系構成格。 令 f：L1L2，f(x)=x-1 不難驗證f是L1到L2的同態映射，因為對x, yL1有： f(xy)=f(max(x, y)=max(x, y)-1 f(x)f(y)=(x-1) (y-1)=max(x-1, y-1)=max(x, y)-1 f(xy)=f(min(x, y)=min(x, y)-1 f(x)f(y)=(x-1)(y-1)=min(x-1, y-1)=min(x, y)-1即： f(xy) = f(x)f(y)， f(xy) = f(x)f(y) 成立。 定理：若a,bL

12、，ab 則f(a)f(b)證： ab a*b=a f(a)f(b)=f(a*b)=f(a) f(a)f(b)注1：保序的函數不一定是同態的。 格同態是保序的三、子格、格同態 S12，整除* S12，小于等于 f: S12 S12，f(x)=x， 則f是保序的。 即ab f(a)f(b) 但f不是同態映射: f(3*2) f(3)f(2) ( f(3*2)=f(1)=1 ，f(3)f(2)=2 )例1：12421 6 31264231三、子格、格同態證：）f是格同構 由“格同態是保序的”知：ab f(a)f(b) 反之，設f(a)f(b) 則：f(a)=f(a)*f(b)=f(ab)因為f是雙射

13、, a= ab ab例2：設f是雙射，則f是到的格同構，當且僅當a,bA1，ab f(a)f(b) ）已知a,bA1, ab f(a)f(b)需證f是同構, 即證：f(ab)= f(a)*f(b)證：令 c= ab 則 ca f(c)f(a) cb f(c)f(b) f(c)f(a)*f(b) 令 f(a)*f(b)=f(d) 則 f(d)f(a) da f(d)f(b) db dab=c f(d)f(c) f(c)=f(d) f(ab)=f(a)*f(b)證畢由此看出，同構的二個格，其哈斯圖相同。 三、子格、格同態 因為，三個元素的偏序集合（同構意義下）僅有： 例3：具有一、二、三個元素的格

14、，分別同構于一、二、三元素的鏈。 四個元素的偏序集合（同構意義下） 僅有： 三、子格、格同態三、子格、格同態同理，五個元素的格僅為：7.2分配格一、定義二、性質7.2分配格一般格只滿足分配不等式： a(bc)(ab)(ac)設是格，若a,b,cL，有：(1) a(bc)=(ab)(ac), (2) a(bc)=(ab)(ac),則稱 為分配格。注：(1)(2)是互相等價的，由對偶原理，從一式可推得另一式。一、定義例：L1和L2是分配格，L3和L4不是分配格。在L3中：b(cd)=be=b， (bc)(bd)=aa=a在L4中：c(bd)=ca=c， (cb)(cd)=ed=d稱L3為鉆石格，L

15、4為五角格。7.2分配格二、性質1、設L是格，則L是分配格當且僅當L中不含有與鉆石格或五角格同構的子格。 由于該定理的證明比較繁且已超出本課程的范圍，故此略去，只要掌握它的應用就行了。 小于五元的格都是分配格。2、任何一條鏈是分配格。證：設是一個鏈，a,b,cL (1) ab 或ac 則：a(bc)=a, (ab)(ac)=a (2) ba 且 ca bc a 則有：a(bc)=bc 和 (ab)(ac)=bc即：a(bc)=(ab)(ac) 是分配格。7.2分配格7.2分配格證：(ab)c=(ac)c=c (ac)(bc)=(ab)(bc) =(ba)(bc) =b(ac) =b(ab) =

16、b3、設是分配格，則 a,b,cL (ab=ac)(ab=ac) b=c(稱為分配格的可約性)交換律分配律代換7.3有補格1、全上（全下界）定義2、有界格3、補元4、有補格5、有補分配格7.3有補格1、全上界（全下界）定義 給定格，若存在aL，使bL,有ba (ab)，稱 a為的全上界（全下界）。證：若存在兩個全上界a,b，則有： a是全上界， ab， 又 b是全上界， ba 所以 b=a注：可以證明，一個格的全上界（全下界）是唯一的。7.3有補格2、有界格定義： 存在全上界和全下界的格，稱為有界格；全上界記為1，全下界記為0，并稱它們為格的界。記為：注：由定義知，0是的幺元，1是的幺元。不難

17、看出，有限格L一定是有界格。設L是n元格，且L=a1，a2，an，那么a1a2an是L的全下界，而a1a2an是L的全上界。因此L是有界格。對于無限格L來說，有的是有界格，有的不是有界格。如：集合B的冪集格，不管B是有窮集還是無窮集，它都是有界格。它的全下界是空集 ，全上界是B。而整數集Z關于通常數的小于或等于關系構成的格不是有界格，因為不存在最小和最大的整數。7.3有補格3、補元定義： 設是有界格，aL，若存在bL，有：ab=0，ab=1，稱b為a的補元，記為a。注： 若a是b的補元，則b也是a的補元; 補元可以不存在，可以不唯一。例：a) a的補元是b,c b的補元是a,c, c的補元是a

18、,b b) a,b,c 均不存在補元 c) 有界格中，0，1互為補元證：因為01=0，01=1 所以0, 1互為補元。c1b0a1bc0 a7.3有補格例：考慮下圖中的四個格。L1中的a與c互為補元，其中a為全下界，c為全上界，b沒有補元。L2中的a與d互為補元，其中a為全下界，d為全上界，b與c 也互為補元。L3中的a與e互為補元，其中a為全下界，e為全上界，b的補元是c和d，c的補元是b和d，d的補元是b和c。b，c，d每個元素都有兩個補元。L4中的a與e互為補元，其中a為全下界，e為全上界，b的補元是c和d，c的補元是b，d的補元是b。7.3有補格4、有補格定義： 若在一個有界格中，每個

19、元素至少有一個補元，則稱此格為有補格。例：右圖中的L2，L3和L4是有補格，L1不是有補格。右圖中的L2和L3是有補格，L1不是有補格。7.3有補格5、有補分配格定義： 若一個格既是有補格，又是分配格，則此格稱為有補分配格，又稱布爾代數。 例：集合運算，命題運算，開關代數為布爾代數,(因為滿足結合律、交換律、吸收律、分配律、存在補元及0，1）1）有補分配格中，任何元素的補元是唯一的。證明：設b，c都是a的補元，則 1）ab=0=ac，ab=1=ac 由分配格的可約性， b=c7.3有補格2）有補分配格滿足德摩根定律，即（1）(ab)=ab （2）(ab)=ab證：(ab)(ab)=(aab)(

20、bab) =00=0 (ab)(ab)=(aba)(abb) =11=1 由有補分配格的補元唯一性，(ab)=ab 由對偶原理 (ab)=ab7.3有補格7.4 布爾代數一、布爾代數的定義二、布爾代數的子代數三、布爾代數的同態映射四、有限布爾代數的結構一、布爾代數的定義1、布爾代數作為的格的定義2、布爾代數的性質3、布爾代數作為代數系統的定義7.4 布爾代數7.4 布爾代數一、布爾代數的定義1、布爾代數作為格的定義如果一個格是有補分配格，則稱它為布爾格或布爾代數。7.4 布爾代數例：設S110=1，2，5，10，11，22，55，110是110的正因子集合。令gcd，lcm分別表示求最大公約數

21、和最小公倍數的運算。 問是否構成布爾代數？為什么？ 解：容易驗證x, yS110，有：gcd(x, y)S110和lcm(x, y)S110。且x,y,zS110有：gcd(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) = x(吸收律)lcm(x, gcd(x, y) = x因此，構成格。下面證明它是分配格。易驗證x，y，zS110 有：gcd(x, lcm(y,

22、z)=lcm(gcd(x, y), gcd(x, z)1作為S110中的全下界，110為全上界，且：1和110互為補元，2和55互為補元，5和22互為補元，10和11互為補元，從而證明了為布爾代數。 例：設B為任意集合，證明B的冪集格構成布爾代數，稱為集合代數。證：(B)關于和構成格，因為：和運算滿足交換律、結合律、吸收律。由于和互相可分配，因此(B)是分配格，且全下界是空集，全上界是B。根據絕對補的定義，取全集為B，x(B)，xBx 是 x 的補元。從而證明(B)是有補分配格，即布爾代數。 2、布爾代數的性質【定理】設是布爾代數，則(1) aB，(a)=a 。(2) a，bB， (ab)=a

23、b， (ab)= ab【證】(1) (a)是a的補元。a也是a的補元。由補元的唯一性得(a)=a。雙重否定律德摩根律(2) 對 a，bB有：(ab)(ab)=(aab)(bab) = (1b)( a1) = 11 = 1，(ab)(ab)=(aba)(abb) = (0b)(a0) = 00 = 0，所以ab是ab的補元，根據補元的唯一性有：(ab)=ab同理可證：(ab)= ab。定義：設是代數系統，*和是二元運算。若*和運算滿足：(1) 交換律，即a，bB有：a*b=b*a， ab=ba (2) 分配律，即a，b，cB有： a*(bc)=(a*b) (a*c)， a (b*c)=(ab)*

24、(ac) (3) 同一律，即存在0，1B，使得aB有：a*1=a， a0=a (4) 補元律，即aB，存在aB使得a*a=0， aa=1 則稱是一個布爾代數。3、布爾代數作為代數系統的定義 二、布爾代數的子代數定義：設是布爾代數，S是B的非空子集，若0, 1S，且S對, 和 運算都是封閉的，則稱S是B的子布爾代數。二、布爾代數的子代數例1：設是布爾代數，a,bB，且ab。令Sx|xB，且axb稱S為B中的區間，可簡記為a,b?？梢宰C明a,b是一個布爾代數。顯然S是B的非空子集，且a和b分別為S的全下界和全上界對任意的x,yS都有 axb，ayb從而有 axyb, axybS關于和運算是封閉的。

25、易見和運算在S上適合交換律和分配律。對任意的 xS，令 y(ax)b (下面證明y為x得補元。)由于 aax，ab，故 a(ax)b。同時(ax)bb，因此 yS。又xy x(ax)b) x(ab)(xb)(分配律) xa(xb) (ab) x(xb) (ax) (xx)(xb) (分配律) 1(xb) (補元律) xb (交換律，同一律) b(xb) xy x(ax)b) x(ax) (xb,交換律) (xa)(xx) (分配律) (xa)0 (補元律) xa (同一律) a (ax) 根據定義(布爾代數作為代數系統的定義)，構成布爾代數。其全上界是a，全下界是b。 xa,b，x關于這個全上

26、界和全下界的補元是(ax)b。當a0且b1時，a,b是B的子布爾代數。但當a0或b1時，a,b不是B的子布爾代數。 二、布爾代數的子代數例2：考慮110的正因子集合：S110 = 1, 2, 5, 10, 11, 22, 55, 110S110關于gcd，lcm運算構成的布爾代數。它有以下的子布爾代數：1, 1101, 2, 55, 1101, 5, 22, 1101, 10, 11,1 101, 2, 5, 10, 11, 22, 55, 110 三、布爾代數的同態映射定義：設和是兩個布爾代數。這里的，泛指布爾代數B2中的求最大下界，最小上界和補元的運算。和E分別是B2的全下界和全上界。f: B1B2。如果對于任意的a，bB1有：f(ab) = f(a)f(b)f(ab) = f(a)f(b)f(a) = f(a)則稱 f是布爾代數B1到B2的同