離散數(shù)學(xué)第六章第一節(jié)

第六章格與布爾代數(shù)

格是另一類代數(shù)系統(tǒng)。格的理論形成于1935年前后，是代數(shù)學(xué)的一個分支。本章介紹格的基本知識，特殊的格：分配格、有補(bǔ)格，最后介紹布爾代數(shù)。1第六章目錄第6-1講格的概念第6-2講分配格和有補(bǔ)格第6-3講布爾代數(shù)第6-4講布爾表達(dá)式2第6-1講格的概念1.格的定義2.格的對偶原理3.格的基本性質(zhì)4.格與代數(shù)系統(tǒng)間的關(guān)系5.格同態(tài)6.

課堂練習(xí)7.第6-1講作業(yè)31、格的定義(1)

如果集合A上的關(guān)系具有自反性、反對稱性和傳遞性，稱之為偏序。<A，>稱之為偏序集。設(shè)X={1,2,3,4,6,12},Y={2,3,6,12,24,36}。集合X和Y上的整除關(guān)系“|”就構(gòu)成兩個偏序集：<X,|>，<Y,|>。它們的哈斯圖如下：雖然都是哈斯圖,但是它們有一個重要的差別：

<X,|>中每兩個元素構(gòu)成的集合都有最大下界和最小上界。但<Y,|>無此特點(diǎn)。41、格的定義(2)定義2設(shè)<A,>是格，在A上定義兩個二元運(yùn)算和，對任意a,bA，ab等于a和b的最小上界，ab等于a和b的最大下界，則稱<A,,>是格<A,>誘導(dǎo)的代數(shù)系統(tǒng)。和分別稱為并運(yùn)算和交運(yùn)算。定義1如果偏序集<A,>中任意兩個元素都有最小上界和最大下界，則稱<A,>是格。注：定義2中定義的兩個運(yùn)算是本節(jié)證明過程中反復(fù)要用的基本依據(jù)。兩個元素的集合{a,b}的上界可以屬于該集合，也可以不屬于該集合。但是，

如果ab，則ab=b，ab=a。如果a、b不可比，也應(yīng)有a,bab，aba,b。51、格的定義(3)可以證明，子格也是格。注意：若<A,>是格,BA且B，則<B,>任然是偏序集，但<B,>不一定是格。即使是格，也不一定是<A,>的子格。定義3設(shè)<A,>是格,<A,,>是<A,>誘導(dǎo)的代數(shù)系統(tǒng)。如果BA且B，若運(yùn)算和在B中封閉，則稱<B,>是<A,>的子格。例如，設(shè)S={a,b,c},<(S),

>是格，其哈斯圖如右，取A={,{a},{c},{a,c}}B={,{a},{c},{a,b},{a,c},{b,c},{a,b,c}}則<A,>是<(S),

>的子格，而<B,>雖是格，但非子格。62、格的對偶原理對偶原理設(shè)P是格<A,>的真命題，將P中的、、分別換成、、得命題P’，則P’在格<A,>中亦真。設(shè)<A,>是偏序集,用表示偏序關(guān)系的逆關(guān)系，則<A,>也是偏序集。將<A,>的哈斯圖旋轉(zhuǎn)180度，就是<A,>的哈斯圖。稱<A,>為<A,>彼此對偶的偏序集。如果<A,>是格，則<A,>也是格。由格<A,>誘導(dǎo)的代數(shù)系統(tǒng)的并(交)運(yùn)算，正好是由格<A,>誘導(dǎo)的代數(shù)系統(tǒng)的交(并)運(yùn)算。73、格的基本性質(zhì)(1)設(shè)<A,>是格,a,b,c,dA，則如下性質(zhì)成立：(1)并、交定義aab,bab

aab,bab

aba,abbaba,abb(2)保序性若ab,cd，則acbd，acbd若bc,則abac，abac(3)交換律

ab=ba，ab=ba(4)結(jié)合律a(bc)=(ab)c，a(bc)=(ab)c(5)等冪律aa=a，aa=a83、格的基本性質(zhì)(2)(6)吸收律

a(ab)=a，a(ab)=a(7)分配不等式a(bc)(ab)(ac)，a(bc)(ab)(ac)(8)abab=aab=b(9)aca(bc)(ab)c作為例子下面證明部分式子：若ab,cd，則acbd。證：已知ab,cd，由(1)，bbd，dbd，再由傳遞性可得abd，cbd。這說明bd是a和c的一個上界，但ac是a和c的最小上界，所以acbd。93、格的基本性質(zhì)(3)證(4)式：a(bc)=(ab)c。證：由(1)，aa(bc)，bbc

a(bc)，這說明a(bc)是a和b的一個上界。但ab是a和b的最小上界，所以ab

a(bc)。

同樣，cbca(bc)，與上述理由相同，應(yīng)有(ab)ca(bc)。類似的可證a(bc)(ab)cbd。因而原式得證。分析：由偏序的反對稱性，要證原式，須證下列二式：(ab)ca(bc)，

a(bc)(ab)c

證明線索如右圖所示。104、格與代數(shù)系統(tǒng)間的關(guān)系（1）證：對任意a,bA，因,滿足吸收律，所以a(ab)=a，a(ab)=a由b的任意性，在前一式中用ab取代b仍然成立，可得a(a(ab))=a再由后一式得：aa=a同理可證aa=a。引理1設(shè)<A,,>是一個代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足吸收律，那么,必滿足等冪律。114、格與代數(shù)系統(tǒng)間的關(guān)系（2）證：在A上定義二元關(guān)系：

對任意a,bA，ab當(dāng)且僅當(dāng)ab=a。

先證是偏序。由所設(shè),運(yùn)算滿足吸收律，根據(jù)引理1，對任意aA，aa=a。所以aa，從而是自反的。設(shè)ab，則ab=a。如果同時有ba,則ba=b。而運(yùn)算滿足交換律，所以ab=ba，故a=b。從而是反對稱的。設(shè)ab，bc,則ab=a,bc=b。那么ac=(ab)c=a(bc)=ab=a所以ac，說明是傳遞的。定理1設(shè)<A,,>是一個代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律、結(jié)合律和吸收律，則A上存在偏序，使<A,>是格。分析：需要做的工作是：(1)在A上構(gòu)造偏序關(guān)系；(2)證明<A,>中任意兩個元素有最小上界和最大下界。124、格與代數(shù)系統(tǒng)間的關(guān)系（3）證(續(xù))：其次證明ab是a、b的最大下界。因(ab)a=a(ab)=(aa)b=ab(ab)b=a(bb)=ab由上二式，并按的定義，可得aba，abb。說明ab是a、b的下界。設(shè)c是a、b的任一下界，則ca,cb。按的定義有ca=c,cb=c。進(jìn)而有c(ab)=(ca)b=cb=c。按的定義有cab。故ab是a、b的最大下界。定理1

設(shè)<A,,>是一個代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律、結(jié)合律和吸收律，則A上存在偏序，使<A,>是格。134、格與代數(shù)系統(tǒng)間的關(guān)系（4）證(續(xù))：第三，證明ab是a、b的最小上界。

先證ab=a與ab=b等價：若ab=a，則(ab)b=ab；另一方面，由交換律和吸收律，上式左邊(ab)b=b(ba)=b。于是ab=b。反之，若ab=b，則a(ab)=ab。

根據(jù)吸收律得a=ab,亦即ab=a。由此可見，證明開始定義的偏序關(guān)系等價于：“對任意a、bA，ab當(dāng)且僅當(dāng)ab=b。”

可以用證明“ab是a、b的最大下界”類似的方法證明“ab是a、b的最小上界”。

綜上所述，<A,>是格。定理1

設(shè)<A,,>是一個代數(shù)系統(tǒng)，其中,都是二元運(yùn)算且滿足交換律、結(jié)合律和吸收律，則A上存在偏序，使<A,>是格。145、格同態(tài)(1)定義4設(shè)<A1,1>、<A2,2>是格。它們所誘導(dǎo)的代數(shù)系統(tǒng)分別是<A1,1,1>、<A2,2,2>。如果存在映射f：A1A2，使對任意a,bA1,有f(a1b)=f(a)2f(b),f(a1b)=f(a)2f(b)則稱f是從<A1,1,1>到<A2,2,2>的格同態(tài)。稱<f(A1),2>是<A1,1>的格同態(tài)象。如果f是雙射，則稱f是從<A1,1,1>到<A2,2,2>的格同構(gòu)。也稱格<A1,1>、<A2,2>同構(gòu)。

定理1中說明，格<A,>可視為具有兩個二元運(yùn)算的代數(shù)系統(tǒng)<A,,>，其中運(yùn)算滿足交換律、結(jié)合律、吸收律和等冪律。因此，對格可引入代數(shù)系統(tǒng)中同態(tài)的概念。155、格同態(tài)(2)定理2設(shè)f是格<A1,1>到<A2,2>格同態(tài)。對任意a,bA1,如果a1b,則f(a)2f(b)。證明：因a1ba1b=a。又因f是格同態(tài)，所以f(a)=f(a1b)=f(a)2f(b)故f(a)2f(b)。

注：定理2說明，格同態(tài)是保序的。其逆不真。例如，設(shè)A={1,2,3,4,6,12}，<A,|>和<A,>都是格，其中“|”表示整除關(guān)系，“”表示數(shù)的大于小于關(guān)系。作映射f:AA,f(x)=x。顯然，如果x|y,則f(x)f(y),因而f是保序的。但f不是格同態(tài)。例如:f(416)f(4)2f(6)165、格同態(tài)(3)定理3f是格<A1,1>到<A2,2>的格同構(gòu)，當(dāng)且僅當(dāng)對任意a,bA1,a1bf(a)2f(b)。證明：設(shè)f是格<A1,1>到<A2,2>的格同構(gòu)，由定理2，對任意a,bA1,如果a1b，則f(a)2f(b)；反之，若f(a)2f(b)，則f(a)2f(b)=f(a)，因f是同構(gòu)，所以f(a)2f(b)=f(a1b)，從而f(a1b)=f(a)，注意到f是雙射，可知a1b=a，故a1b。

反之，若對任意a,bA1,a1bf(a)2f(b)，要證f是<A1,1>到<A2,2>的格同構(gòu)，即證f(a1b)=f(a)2f(b)。（轉(zhuǎn)下頁）175、格同態(tài)(3)定理3f是格<A1,1>到<A2,2>的格同構(gòu)，當(dāng)且僅當(dāng)對任意a,bA1,a1bf(a)2f(b)。

證明(續(xù))：令a1b=c,則c1a，c1b。已知a1bf(a)2f(b)，所以，f(c)2f(a),f(c)2f(b)。故f(c)2f(a)2f(b)。又令f(a)2f(b)=f(d)，則上式化為f(c)2f(d)；