數(shù)學(xué)對(duì)象可以用不同的結(jié)構(gòu)來表示_第1頁
數(shù)學(xué)對(duì)象可以用不同的結(jié)構(gòu)來表示_第2頁
數(shù)學(xué)對(duì)象可以用不同的結(jié)構(gòu)來表示_第3頁
數(shù)學(xué)對(duì)象可以用不同的結(jié)構(gòu)來表示_第4頁
數(shù)學(xué)對(duì)象可以用不同的結(jié)構(gòu)來表示_第5頁
已閱讀5頁,還剩5頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、§5.1 格數(shù)學(xué)對(duì)象可以用不同的結(jié)構(gòu)來表示。格就是一種可以用代數(shù)或關(guān)系來表示的數(shù)學(xué)對(duì)象。我們先用代數(shù)結(jié)構(gòu)來定義格。5.1.1 定義 格 L是非空集合,Ù和Ú是L上兩個(gè)二元運(yùn)算。<L, Ù, Ú>稱為一個(gè)格(按習(xí)慣將Ù(x, y)記為xÙy,將Ú(x, y)記為xÚy,Ù稱為交,Ú稱為并),如果L滿足以下條件:(1) 冪等律 任給xÎL,都有xÙx = x,xÚx = x。(2) 結(jié)合律 任給x, y, zÎB,都有(xÙy)

2、Ùz = xÙ(yÙz),(xÚy)Úz = xÚ(yÚz)。(3) 交換律 任給x, yÎB,都有xÙy = yÙx,xÚy = yÚx。(4) 吸收律 任給x, yÎB,都有(xÙy)Úy = y,(xÚy)Ùy = y。當(dāng)Ù, Ú是已知或不必指出時(shí),簡(jiǎn)稱L是一個(gè)格。由結(jié)合律,多個(gè)元素作交或并時(shí)可以省略括號(hào)。吸收律刻畫了兩種運(yùn)算Ù和Ú的關(guān)系,由吸收律還能得到以下重要關(guān)系5.1.2 定

3、理 L是格,任給x, yÎL,都有xÙy = x當(dāng)且僅當(dāng)xÚy = y。證 如果xÙy = x,則y = (xÚy)Ùy = (xÙy)Ú(yÙy) = xÚy。如果xÚy = y,則x = (xÚy)Ùx = (xÚx)Ù(yÚx) = xÙy。以下是格的一些例子。5.1.3 例 冪集P(s)的對(duì)于Ç和È封閉的子集是格,稱為集格。5.1.4 例 在單元集a上定義Ù和Ú如下:aÙ

4、;a = a,aÚa = a,則<a, Ù, Ú>是格,稱為單元格。單元格上的Ù和Ú是唯一的。5.1.5 例 正邏輯系統(tǒng)Pm的公理是:(1) |- a®(b®a)。(2) |- (a®(b®g)®(a®b)®(a®g)。(3) |- aÙb®a。(4) |- aÙb®b。(5) |- (a®b)®(a®g)®(a®bÙg)。(6) |- a®a&

5、#218;b。(7) |- b®aÚb。(8) |-(a®g)®(b®g)®(aÚb®g)。推演規(guī)則是分離規(guī)則:從a和a®b得到b。«的定義是:a«bab =df (a®b)Ù(b®a)。令Form是Pm的所有公式的集合,因?yàn)樵赑m中有:(1) |- a®a;(2) 如果|- a«b,則|- b«a;(3) 如果|- a«b且|- b«g,則|- a«g。所以可以在Form上定義等價(jià)關(guān)系如下:ab

6、 =df |-a«b。公式a在等價(jià)關(guān)系下的等價(jià)類記為a,取L是Form在等價(jià)關(guān)系下的商集Form / 。因?yàn)樵赑m中有:如果 |-a«a¢且 |-b«b¢,則|-aÙb«a¢Ùb¢,|-aÚb«a¢Úb¢,所以可以在L上定義Ù和Ú如下:aÙb = aÙb,aÚb = aÚb<L, Ù, Ú>是格,相應(yīng)的Pm邏輯等值式如下:(1) |-aÙa

7、71;a,|-aÚa«a。(2) |-(aÙb)Ùg«aÙ(bÙg),|-(aÚb)Úg«aÚ(bÚg)。(3) |-aÙb«bÙa,|-aÚb«bÚa。(4) |-(aÙb)Úb«b,|-(aÚb)Ùb«b。更一般地,對(duì)于Pm的任何擴(kuò)充系統(tǒng),都可以用同樣的方法定義這樣的格。5.1.6 定理 L是格,定義L上二元關(guān)系£如下:x£y =df

8、 xÙy = x,則£是L上偏序關(guān)系。證 (1) 自返性。任給xÎL,都有xÙx = x,因此x£x。(2) 反對(duì)稱性。任給x, yÎL,如果x£y且y£x,則xÙy = x且yÙx = y,因此x = xÙy = yÙx = y。(3) 傳遞性。任給x, y, zÎL,如果x£y且y£z,則xÙy = x且yÙz = y,所以xÙz = (xÙy)Ùz = xÙ(yÙz) =

9、 xÙy = x,因此x£z。由定理5.1.2,x£y 當(dāng)且僅當(dāng) xÚy = y。5.1.7 定理 L是格,£是如上定義的偏序關(guān)系。(1) 任給x, yÎL,都有xÙy£x且xÙy£y。(2) 任給x, y, zÎL,如果z£x且z£y,則z£xÙy。(3) 任給x, yÎL,都有x£xÚy且y£xÚy。(4) 任給x, y, zÎL,如果x£z且y£z,則x

10、8;y£z。證 (1) 因?yàn)?xÙy)Ùx = (yÙx)Ùx = yÙ(xÙx) = xÙy,(xÙy)Ùy = (xÙy)Ùy = xÙ(yÙy) = xÙy,。(2) 如果z£x且z£y,則zÙx = z且zÙy = z,所以zÙ(xÙy) = (zÙx)Ù(zÙy) = zÙz = z,因此z£xÙy。(3)(4) 類似

11、于(1)(2),使用x£y 當(dāng)且僅當(dāng) xÚy = y。由定理5.1.7可知,在這個(gè)偏序關(guān)系下,xÚy就是x, y的上確界,xÙy就是x, y的下確界。設(shè)L是偏序結(jié)構(gòu),如果L的任何兩個(gè)元素都有上確界和下確界,在L上定義Ù和Ú如下:xÙy = x, y的下確界,xÚy = x, y的上確界,則<L, Ú, Ù>是格。因此,也可以用任何兩個(gè)元素都有上確界和下確界的偏序結(jié)構(gòu)來定義格。詳細(xì)定義如下:<L, £>是關(guān)系結(jié)構(gòu),<L, £>稱為一個(gè)格,如果

12、滿足以下條件:(1) ("xÎL)(x£x)。(2) ("x, yÎL)(x£yÙy£x®x = y)。(3) ("x, y, zÎL)(x£yÙy£z®x£z)。(4) ("x, yÎL)($aÎL)(x£aÙy£aÙ("zÎL)(x£zÙy£z®a£z)。(5) ("x, yÎ

13、;L)($bÎL)(b£xÙb£yÙ("zÎL)(z£xÙz£y®z£b)。(1)(2)(3)是說<L, £>是偏序結(jié)構(gòu),(4)是說任何兩個(gè)元素都有上確界,(5)是說任何兩個(gè)元素都有下確界。可以證明:(4)中a和(5)中b都是唯一的,所以可以在這樣定義的格中引進(jìn)兩個(gè)二元運(yùn)算:Ù:L×L®L Ù(x, y) = a (由(4)確定的唯一的a),Ú:L×L®L Ú(x, y) =

14、 a (由(5)確定的唯一的b),則<L, Ù, Ú>就是用代數(shù)定義的格。以下討論中仍用格的代數(shù)定義,但同時(shí)使用偏序關(guān)系。5.1.8 例 全序集的任何兩個(gè)元素都有上確界和下確界,所以任何非空全序集都可以形成格。5.1.9 例 G是群,L = H | H是G的子群, L在集合的包含關(guān)系下是一個(gè)偏序集,兩個(gè)子群H和K的下確界是HÇK,上確界是HÈK生成的子群,所以如果在L上定義Ù和Ú如下:HÙK = HÇK,HÚK = HÈK生成的子群,則<L, Ù, Ú>

15、;是格。5.1.10 定義 子格 <L, Ù, Ú>是一個(gè)格,S Í L,如果<S, Ù, Ú>是一個(gè)格,則稱S是L的子格。S Í L,S是L的子格的充要條件是:任給x, yÎS,都有xÙyÎS且xÚyÎS。5.1.11 例 L是L的子格,不等于L的子格稱為真子格。5.1.12 例 L是格,a, bÎL,a£b,令a, b = x | a£x£b,因?yàn)槿谓ox, yÎa, b,都有a£x£b且a

16、£y£b,由定理5.1.7得a£xÙy£b且a£xÚy£b,所以xÙy, xÚyÎa, b。因此a, b是L的子格,稱為由a和b確定的閉子格。a, a就是單元格a。類似地可定義由a確定的上開子格a)= x | a£x和由b確定的下開子格。(b = x | x£b,5.1.13 定理 L是格,G是L的子格的集合,即任給SÎG,S都是L的子格,則:(1) ÇG是L的子格。(2) 如果G單調(diào)的,則ÈG是L的子格。由定理5.1.13(1),可定

17、義由X所生成的子格ÇG,其中G = S | X Í S且S是L的子格。格的同態(tài)和同構(gòu)就是一般代數(shù)結(jié)構(gòu)的同態(tài)和同構(gòu),格的同態(tài)基本定理就是一般代數(shù)結(jié)構(gòu)的同態(tài)基本定理,簡(jiǎn)單重述如下:5.1.14 定理 同態(tài)基本定理 <L1, Ù1, Ú1>、<L2, Ù2, Ú2>是兩個(gè)格,s是<L1, Ù1, Ú1>到<L2, Ù2, Ú2>的滿同態(tài)。取等價(jià)關(guān)系如下:ab 當(dāng)且僅當(dāng) s(a) = s(b),則是正規(guī)的等價(jià)關(guān)系,因此可以構(gòu)造商格<L1/, 

18、7;, Ú>(Ù和Ú是商集L1/上的二元運(yùn)算),使得<L1/, Ù, Ú><L2, Ù2, Ú2>。成立分配律的格稱為分配格。分配律是指:任給x, y, zÎL,都有xÙ(yÚz) = (xÙy)Ú(xÙz),xÚ(yÙz) = (xÚy)Ù(xÚz)。5.1.15 例 分配格的子格是分配格5.1.16 例 全序集形成的格是分配格。5.1.17 定理 L是分配格,x, yÎL。

19、如果存在aÎL,使得aÙx = aÙy,aÚx = aÚy,則x = y。證 x = xÚ(aÙx) = xÚ(aÙy) = (xÚa)Ú(xÙy)= (yÚa)Ú(xÙy) = yÚ(aÙx) = yÚ(aÙy) = y。集格都是分配格。在同構(gòu)的意義上,分配格都是集格。5.1.18 定義 濾 L是格,F(xiàn)是L的非空子集。如果F滿足:(1) 任給x, yÎL,如果xÎF且yÎF,

20、則xÙyÎF;(2) 任給x, yÎL,如果xÎF且x£y,則yÎF。則稱F是L的濾。5.1.19 定理 L是格,G是L的濾的集合,即任給FÎG,F(xiàn)都是L的濾,則:(1) ÇG是L的濾。(2) 如果G單調(diào)的,則ÈG是L的濾。如果X¹Æ,則由定理5.1.19的(1),可以定義由X所生成的濾ÇG,其中G = F | Í F且F是L的濾,可以證明由X所生成的濾是y | 存在x1, xnÎX,使得x1ÙÙxn£y。aÎL,由

21、a生成的濾就是上開子格a)。F是L的濾,aÎL,由FÈa生成的濾是x | 存在uÎI,使得uÙa£x。5.1.20 定義 素濾 L是格,P是L的真濾。如果任給x, yÎL,都能從xÚyÎF推出xÎF或yÎF,則稱F是素濾。素濾有以下基本性質(zhì)。5.1.21 定理 L是格,P是L的素濾,則:(1) 任給x, yÎL,都有xÙyÎP當(dāng)且僅當(dāng)xÎP且yÎP。(2) 任給x, yÎL,都有xÚyÎP當(dāng)且僅當(dāng)xÎP或y

22、ÎP。證 (1) 如果xÎP且yÎP,則xÙyÎP。如果xÙyÎP,則由xÙy£x得xÎP,由xÙy£y得yÎP。(2) 如果xÚyÎP,則xÎP或yÎP。如果xÎP或yÎP,則由x£xÚy和y£xÚy得xÚyÎP。5.1.22 定理 L是分配格,F(xiàn)是濾,bÏF,xÚyÎF。令F1是由FÈx生成的濾,F(xiàn)2是由

23、FÈy生成的濾,則bÏF1或bÏF2。證 反證法。設(shè)bÎF1且bÎF2,則存在uÎF,vÎF,使得uÙx£b且vÙy£b,所以u(píng)ÙvÙx£b且uÙvÙy£b,uÙvÎF所以(uÙvÙx)Ú(uÙvÙy)£b,由分配律得(uÙv)Ù(xÚy)£b,因此bÎF,矛盾。5.1.23 定理 素濾存在定理 L

24、是一個(gè)分配格,任給a, bÎL,如果b<a,則存在素濾P,使得aÎP且bÏP。證 令G = F | F是濾,aÎF且bÏF,由a生成的濾a)ÎG,所以G非空,任給S Í G是單調(diào)的,則F = ÈS是濾,并有aÎF且bÏF,所以FÎG。由Zorn引理,G有極大元P,證明P是素濾。任給xÚyÎP,令F1是由PÈx生成的濾,F(xiàn)2是由PÈy生成的濾,則由定理5.1.22得bÏF1或bÏF2,所以F1ÎG或F2Î

25、;G,由P是極大元得F1 = P或F2 = P,因此xÎP或yÎP。5.1.24 定理 L是格,令s = P | P是L的素濾,任給xÎL,令x* = P | PÎs且xÎP,則:(1) 任給x, yÎL,都有(xÙy)* = x*Çy*。(2) 任給x, yÎL,都有(xÚy)* = x*Èy*。證 首先由x*的定義得PÎx*當(dāng)且僅當(dāng)xÎP。(1) PÎ(xÙy)* 當(dāng)且僅當(dāng) xÙyÎP當(dāng)且僅當(dāng) (xÎP且yÎP)當(dāng)且僅當(dāng) (PÎx*且PÎy*)當(dāng)且僅當(dāng)PÎx*Çy*。所以(xÙy)* = x*Çy*。(2) PÎ(xÚy)* 當(dāng)且僅當(dāng) xÚyÎP當(dāng)且僅當(dāng) (xÎP或yÎP)當(dāng)且僅當(dāng) (PÎx*或PÎy*)當(dāng)且僅當(dāng)PÎx*Èy*。所以(xÚy)* = x*Èy*。

溫馨提示

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

評(píng)論

0/150

提交評(píng)論