離散數(shù)學 第9講 格

1、1離散數(shù)學（二）離散數(shù)學（二）格和布爾代數(shù)格和布爾代數(shù) 格與布爾代數(shù)格與布爾代數(shù)：它們都是具有兩個二元運算的代數(shù)系統(tǒng)，這兩個代數(shù)系統(tǒng)與前面討論的代數(shù)系統(tǒng)之間存在著一個重要區(qū)別：在格與布爾代數(shù)中，在格與布爾代數(shù)中，偏序關系偏序關系具有重要意義具有重要意義。 為了強調(diào)偏序關系的作用，我們將分別從偏序集偏序集和代數(shù)系代數(shù)系統(tǒng)統(tǒng)兩個方面引入格的概念，給格附加一定的限制之后，格就轉化為布爾代數(shù)，即布爾代數(shù)是特殊的格布爾代數(shù)是特殊的格。格和布爾代數(shù)格和布爾代數(shù)起源與發(fā)展起源與發(fā)展: 布爾代數(shù)最初是作為對邏輯思維法則的研究出現(xiàn)的。英國哲英國哲學家布爾學家布爾(George Boole)于于1847年利用數(shù)學

2、方法研究了類與年利用數(shù)學方法研究了類與類類(集合與集合集合與集合)之間的關系法則之間的關系法則。他的研究后來發(fā)展成為一個數(shù)學分支布爾代數(shù)布爾代數(shù)。 自布爾之后，許多數(shù)學家對布爾代數(shù)一般化作了努力。在奠基工作方面，豐廷頓豐廷頓(E. V. Huntington)、雪弗爾、雪弗爾(H. M. Sheffer)和斯通和斯通(M. H. Stone)都作出了貢獻。畢克霍夫畢克霍夫(Garrett Birkhoff)和麥克朗麥克朗(Saunders Maclane)的研究進一步使布爾代數(shù)得到嚴謹?shù)奶幚怼８窈筒紶柎鷶?shù)格和布爾代數(shù) 格是一種兼有序有序和代數(shù)代數(shù)的重要結構，它和模糊數(shù)學等現(xiàn)代數(shù)學有十分緊密的聯(lián)

3、系； 格與布爾代數(shù)具體應用：格與布爾代數(shù)具體應用： 格與布爾代數(shù)在計算機科學中具有非常重要的應用。如在保密學保密學、計算機語義學計算機語義學、開關理論開關理論、計算機理論計算機理論和邏輯設計邏輯設計以及其他一些科學和工程領域中都直接應用了格與布爾代數(shù)。格和布爾代數(shù)格和布爾代數(shù)格格( (lattice) )在閃存在閃存( (flash memory) )編碼中的應用編碼中的應用: : 格的定義與基本性質(zhì)格的定義與基本性質(zhì)格的兩種定義格的兩種定義1 11 1子格和格同態(tài)子格和格同態(tài)2 2主要內(nèi)容主要內(nèi)容: :格的定義和性質(zhì)格的定義和性質(zhì)重點重點: : 重點和難點重點和難點: :格的兩種定義格的兩種

4、定義難點難點: : 一、格的兩種定義一、格的兩種定義預備知識：預備知識： 1. 若集合A上的二元關系R是自反的、反對稱的、傳遞的，則稱R為A上的偏序偏序，記為。 2 設是一偏序集合,BA (i) 若若aA，對于每一xB, 均有xa, 稱aA為為B的上界；的上界； (ii) 若若bA，對于每一xB, 均有bx, 稱bA為為B的下界；的下界； (iii) c為B的上界, 若對B的任一上界c, 均有c c, 稱c為為B的的 上確界上確界(最小上界最小上界)； (iv) d為B的下界，若對B的任一下界d, 均有d d,稱d為為 B的下確界的下確界(最大下界最大下界)。一、格的兩種定義一、格的兩種定義偏

5、序格的定義：偏序格的定義： 設是一偏序集合,若對于任意a,bL, a,b均有上確界(最小上界)和下確界(最大下界),則稱此偏序集合偏序集合為格為格。一、格的兩種定義一、格的兩種定義代數(shù)格的引入：代數(shù)格的引入： 設是一偏序集合，在L上定義兩運算*與 如下, 即對任意a,b L：a * b=a,b 的下確界=glba,b 保交保交a b=a,b 的上確界=luba,b 保聯(lián)保聯(lián) 那么是代數(shù)嗎？例例1：對任意a,bI+,有 a*b=a,b的下確界=GCDa,b (a,b的最大公約數(shù)) a b=a,b的上確界=LCMa,b (a,b的最小公倍數(shù))一、格的兩種定義一、格的兩種定義代數(shù)格的定義：代數(shù)格的定

6、義： 設是代數(shù)系統(tǒng),*和 是載體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 * b)=a a * (a b)=a 則稱是代數(shù)格是代數(shù)格。 事實上代數(shù)格也滿足等冪律等冪律，a a=a, a*a=a, 由吸收律可推出 等冪律, 因為a*a=a*(a (a*a)=a。類似地可證a a=a。例例3 (1) S=a,b,c, 為代數(shù)格； (2) 定義X:由命題變元p1,p2,pn, , 構成的合式公式集。則為代數(shù)格。一、格的兩種定義一、格

7、的兩種定義定理定理1 1：如果是偏序格,定義L上兩運算*與 如下:a*b=glba,b, a b=luba,b ,則是代數(shù)格。證明證明: (1)可交換可交換：由*與 的定義可知*與 是可交換的。(2)可結合：可結合：證明 a,b,cL有a (b c)=(a b) c成立 即要證明 a (b c)(a b) c (a b) ca (b c) 下面證明，類似可證。 由ba b(a b) c和c(a b) c可得，(b c)(a b) c 又aa b(a b) c，所以a (b c)(a b) c。(3)吸收律：吸收律：證明對a,bL，a (a*b)=a。 由aa, a*ba可得a (a*b)a,又

8、aa (a*b),所以a (a*b)=a。 同理可證a * (a b)=a。定理得證。定理得證。一、格的兩種定義一、格的兩種定義定理定理2 2：如果是代數(shù)格，定義L上一個二元關系如下,即對a,bL, aba*b=aa b=b,則是偏序格。證明證明: (1) 是偏序關系是偏序關系： 自反自反 因aL, aa a*a = a。 反對稱反對稱 設ab,ba, 則有a*b=a, b*a=b,又a*b=b*a,所以a=b。 傳遞性傳遞性 設ab, bc,則有a*b=a, b*c=b,則有a*c=(a*b)*c=a*(b*c)=a*b=a, 則有 a c。 一、格的兩種定義一、格的兩種定義定理定理2 2：

9、如果是代數(shù)格，定義L上一個二元關系如下,即對a,bL, aba*b=aa b=b,則是偏序格。證明證明: (2) 對任意對任意a,bL,a,b均有上確界和下確界均有上確界和下確界,下面只證下面只證有下確界有下確界 a*b即為a,b的下確界: 先證下界先證下界 (a*b)*a = a*(b*a)= a*(a*b) = (a*a)*b = a*b,即(a*b)*a = a*b,則a*b a; 同理可得(a*b)*b = a*b,則a*bb. 證明對證明對a,b的任一下界的任一下界c,有有c a*b,即即c*(a*b) = c.設c是a,b的任意下界，即有ca且cb,則有c*a=c且c*b=c.而c

10、*(a*b)=(c*a)*b=c*b=c,即c*(a*b)=c,所以有ca*b。一、格的兩種定義一、格的兩種定義例例3(1)：S=a,b,c, 為代數(shù)格,A,B(S)，AB AB=A A包含于B 所以誘導的偏序格是 .例例3(2)：X=A|A是由變元p1,p2,pn, ,構成的合式公式集。P,QX,PQ PQ=PPQ 誘導的偏序格是 。一、格的兩種定義一、格的兩種定義定理定理3 3：設是偏序格，(或)是誘導的代數(shù)格，a,b,cL 有以下式子成立: (1)自反性 a a (2)反對稱性 (ab) 且 (ba) a = b (3)傳遞性 (ab) 且 (bc) ac (4) aba, abb aa

11、b, bab (5) (ca)且(cb) c(ab), (bc)且(ac) c (ab) (6)交換律 ab=ba ab= ba (7)結合律 (ab)c=a(bc), (ab)c=a(bc)一、格的兩種定義一、格的兩種定義定理定理3( 3(續(xù)續(xù)) )：(8)等冪律 aa=a, aa=a (9)吸收律 a(ab)= a, a(ab)=a(10) ab ab=a ab=b(11) ab 且d c ad bc ab 且d c a d bc(12)保序性 bc abac, bc a bac(13)分配不等式 a(bc) (ab)(ac) a(bc) (ab)(ac)(14)模不等式 a c a(bc

12、)(ab)c一、格的兩種定義一、格的兩種定義定理定理3 3證明：證明：證明(10)： ab ab=a ab=b 先證 由 ab, aa, 可得aab;又由定義知ab a;所以ab=a 再證 已知a=ab, abb,可得ab，同理可證abab=b證明(11)： ab且d c adbc ada, add,由傳遞性得adb, adc;又由公式(5)可得adbc一、格的兩種定義一、格的兩種定義定理定理3 3證明：證明：證明(13)：a(bc) (ab)(ac)由aab, aac,可得a(ab)(ac);又bab, cac,可得bc(ab)(ac)。所以， a(bc) (ab)(ac)。 二、子格和格同

13、態(tài)二、子格和格同態(tài)子格的定義：子格的定義： 設是偏序格，是由所誘導的代數(shù)格, SL且S ,若S關于和是封閉的，則稱是的子格子格?！纠}例題】圖圖(a)、(b)中所示的格中所示的格分別是格分別是格的子格嗎？的子格嗎？(a)abecdffacdea abdcedeab(b)一個格中的部分元素在原偏序關系上構成一個格中的部分元素在原偏序關系上構成一個格，不能說明它就是原格的子格一個格，不能說明它就是原格的子格。主主要看該子集上的任意兩個元素在原運算保要看該子集上的任意兩個元素在原運算保交和保聯(lián)下的結果是否也在該子集中。交和保聯(lián)下的結果是否也在該子集中。二、子格和格同態(tài)二、子格和格同態(tài)格同態(tài)的定義：格

14、同態(tài)的定義： 設和是兩個代數(shù)格，存在函數(shù)f: LS, 如果對于任何a,bL,有f(a*b)=f (a)f (b), f(a b)=f (a)f (b) 則稱f是從到的格同態(tài)格同態(tài)。若f是雙射函數(shù)，則稱f是格同構格同構。二、子格和格同態(tài)二、子格和格同態(tài) 定理定理4：設和是兩個格，在集合L和S中，對應于保交和保聯(lián)運算的偏序關系分別是和，如果f: LS是格同態(tài)，則對任意a,bL,當ab時,必有f (a)f (b)。 證明證明：因為ab a*b=a, 所以f(a*b)=f(a), 根據(jù)格同態(tài)定義有，f(a*b)= f(a)f(b)，所以f(a)f(b)=f(a),于是可得f(a)f(b)。 Note: f是是格同態(tài)格同態(tài), 則則f保序的保序的; 反之反之,當當f保序時保序時, f不一定是不一定是格同態(tài)。格同態(tài)。 二、子格和格同態(tài)二、子格和格