離散數(shù)學(xué)II課件:7_4幾種特殊的格_第1頁
離散數(shù)學(xué)II課件:7_4幾種特殊的格_第2頁
離散數(shù)學(xué)II課件:7_4幾種特殊的格_第3頁
離散數(shù)學(xué)II課件:7_4幾種特殊的格_第4頁
離散數(shù)學(xué)II課件:7_4幾種特殊的格_第5頁
已閱讀5頁,還剩20頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、7.4 幾種特殊的格,7.4.1 有 界 格 7.4.2 有 余 格 7.4.3 分 配 格 7.4.4 模 格,7.4.1 有 界 格,引理1 設(shè)(L,)是一個格。若S是L的任意一個有限非空子集,則S有一個最大下界和一個最小上界。 記集合S的最大下界為inf S; 集合S的最小上界為sup S。 Note: 對于格的一個無窮子集,引理1的結(jié)論不 成立。 例.在格(I+,)中,所有正偶數(shù)組成的集合 記為E+,顯然,E+ I+,但E+沒有最小上界。,定義. 格(L,)稱為有界格,如果它有一個最大元素(記為1)和一個最小元素(記為0),亦即,對任意aL,都有 0a1 0,1稱為格(L,)的界。 結(jié)

2、論:有限格必是有界格 令L=a1,an , 0 = a1a2an, 1 = a1a2an 引理2. 若(L,0,1)是有界格,則對任意aL,恒有 a 0 = a, a1 = a, a 1 = 1, a0 = 0。,定義. 在有界格(L,0,1)中,一個元素bL,稱為元素aL的余元素,如果 ab = 0, ab = 1。 1 1 1 a b a b a b c 0 0 0 (a,b都無余)(a有唯一余)(a有b,c兩個余) 1 a b c 0,引理3 在有界格(L,0,1)中,1是0的唯一一個余元素,反之亦然。 證明:由引理2,01 = 0, 01 = 1, 所以,0,1互為余元素。 若cL,且

3、c1,c是0的余元素, 0c = 0, 0c = 1。 但是,由引理2知,0c = c 故,c = 1,矛盾。,7.4.2 有 余 格,定義. 稱有界格(L,0,1)是一個 有余格,如果對L中每一個元素,都至少有一 個余元素。 例. n維格(Ln,n)是一個有余格,其中 1n=(1,1,1), 0n=(0,0,0)是界。 對任意Ln中元素(a1,an), 元素(b1,bn)是其 余元素,其中,例. 設(shè)S是有n個元素的集合,(S)是S的冪 集合,于是,(S),)是有余格。 其中, 和S是此格的界. 對(S)中任意元素A,(S)中的元 素S-A是其余元素。,7.4.3 分 配 格,定義7.4.4

4、格(L,)稱為分配格,如果對任意a,b,cL,恒有 a(bc)=(ab)(ac) a(bc)=(ab)(ac) Note: (1)分配格定義中的兩個等式是等價的 (2) n維格(Ln,n),格(S),), 格(I+,D),格(Sn,D)都是分配格。 但不是所有的格都是分配格 (3)分配格的任意子格仍是分配格。,例子,d d e e c b c b c d d b b a a c a a L1 L2 L3 L4 圖中L1和L2是分配格,但L3,L4不是。因為在L3中 b(cd)=b e=b和(b c) (b d)=a a=a; 在L4中d(bc)=d e=d和(d b) (d c)=a c=c。

5、 L3稱為鉆石格, L4稱為五角格。,引理4 任意一個鏈都是一個分配格。 證明:設(shè)格(L,)是一個鏈,任取a,b,c L, 1)若ab且ac,于是abc,故 a(bc)= bc 而ab = b,ac = c,所以 (ab)(ac)= bc 故a(bc)=(ab)(ac)。 2)若ab或者ac,于是a(bc), 故a(b c)= a。而 (ab)(ac)= a 所以a(bc)=(ab)(ac)。,De Morgan定律,定理7.4.1 設(shè)(L,)是一個分配格,對任意a,bL,若a,b有余元素a,b,則 (ab)= ab (ab)= ab 證明: (ab)(ab)=(aba)(abb) =(1b)

6、(a1)= 11 = 1 而(ab)(ab)=(aab)(bab) =(0b)(0a)= 00 = 0 故由余元素定義知, (ab)= ab 同理可證另一等式。,定理7.4.2 設(shè)格(L,)是分配格,對 任意a,b,cL,如果 ac = bc, ac = bc, 則有a = b。 證明:若(L,)是分配格,且ac=bc,ac=bc, 則 a = a(ac)= a(bc) =(ab)(ac) =(ab)(bc)= b(ac) = b(bc)= b,推論 設(shè)格(L,)是一個有余分配格, 則對任意aL,a的余元素a是唯一的。 證明: 因(L,)是有余格,設(shè)a和a都是a的余元素,即 aa= 0, aa

7、= 1 aa= 0, aa= 1 故aa= aa,aa= aa。 由定理8.4.2知,a= a。,7.4.4 模 格,定義7.4.5 設(shè)(L,)是一個格,對任意a, b,cL,如果ab,都有 a(bc)= b(ac) 則稱(L,)為模格。 Note: (1)任意一個分配格都是模格, 由ab, ab=b,故 a(bc)= (ab)( a c) = b(ac) (2)模格不一定是分配格。,例.如圖所示,L=0,1,b1,b2,b3。則, 格(L,)不是分配格: b1(b2b3)= b1 (b1b2)(b1b3)= 0。 格(L,)是模格: (1)當a=1時,若ab,則b也一定是1。故 a(bc)=

8、1(1c) = 1 b(ac)=1(1c)= 11 = 1。 (2)當a=0時,若ab,則b可能為0,b1,b2,b3,1。故 a(bc)= 0(bc)=bc b(ac)=b(0c)= bc。,(3)當a= b1,b2,b3之一時, 若ab,則b是1或a。 若b = 1,則 a(bc)= a(1c)=ac b(ac)=1(ac)=ac 。 若b = a,則 a(bc)= a(ac) = a b(ac)= a(ac)= a。 綜上,對任意a,b,cL,如果ab,都有a(bc)= b(ac) 。,例子與結(jié)論,前面描述的格L1、L2和L3都是模格,但L4不是。因為cd,但c (bd)=c,(cb)

9、d=d 一個格L是模格當且僅當L不含與五角格同構(gòu)的子格。 一個模格是分配格當且僅當L不含與鉆石格同構(gòu)的子格,模格的例,群G中的所有正規(guī)子群做成一個模格。 證明:設(shè)群G的所有正規(guī)子群做成的集合為S, 規(guī)定S中兩種運算: , ,對任意AS,BS, A與B的交集記為AB。 A與B的乘積(記為AB)為如下集合: AB = y(A)(yB) (1)往證(S,, )是格 往證, 是S上的二元代數(shù)運算。 因為正規(guī)子群的交仍為正規(guī)子群,故運算 對S封閉。,對任意AS,BS,對任意gG,任取ug(AB),于是, u = gab 其中aA,bB。因為A,B是正規(guī)子群,所以 gab = a1gb = a1b1g 其

10、中a1A,b1B。故u=gab(AB)g,故 g(AB)(AB)g 同理可證:(AB)g g(AB)。故 g(AB)=(AB)g 即,AB是正規(guī)子群. 所以,乘運算對S也是封閉的。,往證, 適合交換律、結(jié)合律、吸收律 結(jié)合律 , 滿足結(jié)合律是顯然的。 交換律 滿足交換律是顯然的 對于乘運算 :任取uAB,即 u=ab(aA,bB)。 由于B是正規(guī)子群,所以, u = ab = b1a(b1B) 故uBA,即AB BA。 同理可證:BA AB,故AB=BA。 即乘運算滿足交換律。,吸收律 任取uA(AB),于是,u=ac,其中cAB,故u = acA,即A(AB)A。 任取uA,因為A,B都是子

11、群,故單位元素1在A中,也在B中,故1AB,故 u = u1A(AB),即A A(AB)。 故 A(AB)=A. 同理可證:A(AB)=A。 亦即:運算和滿足吸收律。 因此,(S,)是一個格。 由于此格中的運算就是集合的交運算,故與 (S,)等價的半序格的部份序就是集合之 間的包含關(guān)系。,(2)往證(S,, )是 模格 對任意AS,BS,CS,如果AB, 任取uA(CB),于是,u=ad,其中dCB,aA,而AAC,故u=ad(AC)B,即 A(CB)(AC)B。 任取u(AC)B,于是,uB,uAC。令 u = ad(其中aA,dC),于是,d = a-1u。因為a-1AB,uB,故a-1u

12、B,即dB。故dCB。因此, u = adA(CB),即 (AC)BA(CB), 所以有 A(CB)=(AC)B 由定義知,(S,)是模格。,定理7.4.3 格(L,)是模格的充要條件是: 對任意a,b,cL,如果 ab,ac=bc,ac=bc 則必有a=b。 證明:必要性。若格(L,)是模格,則對 任意a,b,cL,如果 ab,ac=bc,a c=b c, 則 a = a (ac)= a (bc) = b(ac)= b(bc)= b,充分性。任取a,b,cL,且ab。 因為(a(bc) c = a (bc)c)=ac 又因為ab,所以ab(ac),故 a c(b(ac)c (a c) c = ac 所以,(b(a c) c = a c。 因此(a(bc)c =(

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論