*

格和布爾代數

*§1格的概念1.偏序集合格《定義》格是一個偏序集合

，其中每一對元素都擁有一個最小上界和最大下界。通常用

表示a和b的最大下界，用表示a和b的最小上界。即：

——稱為元素a和b的保交運算，

——稱為元素a和b的保聯運算。*§1格的概念例：以下均為偏序集合格（D為整除關系，Sn為n的因子集合）。*§1格的概念2.代數系統格《定義》：設是一個格，如果在A上定義兩個二元運算

和

，使得對于任意的a，bA，a

b等于a和b的最小上界，a

b等于a和b的最大下界，那么就稱<L,

,

>為由格所誘導的代數系統。*§1格的概念3.格的主要性質：(1)格的對偶原理設<L,≤>是格，“≤”的逆關系“≥”與L組成的偏序集<L,≥>也是格。兩者互為對偶。前者的GLB，LUB恰好是后者的LUB，GLB。如有關于<L,≤>的有效命題，將“≤”換成“≥”，“

”換成“

”，“

”換成“

”，便能得到<L,≥>的有效命題。反之亦然。*§1格的概念(2)對格<L,≤>中任意a和b，有a≤a

b及a

b≤a。(3)<L,≤>是格。對任意a,b,c,dL，如a≤b，c≤d，則

a

c≤

b

d，a

c≤b

d**§1格的概念(4)（交換律）交和并運算是可交換的。(5)（結合律）交和并運算是可結合的。*§1格的概念(6)（冪等律）對L中每一個a，有a

a=a，a

a=a。(7)（吸收律）對L中任意a，b， 有a

(a

b)=a

a

(a

b)=a。*§2分配格

對格所定義的代數系統<L,

,

>，其運算

和

不一定滿足分配律。《定義》設<L,

,

>是由<L,≤>所誘導的代數系統。如果對任意的a,b,cL，滿足：

a

(b

c)=(a

b)

(a

c)及 a

(b

c)=(a

b)

(a

c)則稱<L,≤>是分配格。*§2分配格討論定義：(1)定義中的兩式互為對偶式。(2)如<L,≤>非為分配格，則有下面的分配不等式：

a

(b

c)≤(a

b)

(a

c)a

(b

c)≥

(a

b)

(a

c)

以及模不等式：

a≤ca

(b

c)≤(a

b)

c*§2分配格《定義》如對L中任意a，b，c有：

a≤ca

(b

c)＝(a

b)

c則稱<L,≤>為模格。例：*§2分配格《定理》如果格中交對并是分配的，那么并對交也是分配的，反之亦然。證明：已知a

(b

c)＝(a

b)

(a

c)

(a

b)

(a

c)=((a

b)

a)

((a

b)

c) =a

((a

b)

c) =a

((a

c)

(b

c)) =(a

(a

c))

(b

c) =a

(b

c)即：并對交也是分配的。*§2分配格《定理》分配格是模格。證明：由于a

(b

c)＝(a

b)

(a

c)(1)若a≤c，則a

c=c，代入上式得

a

(b

c)＝(a

b)

c(2)若a

(b

c)＝(a

b)

c，則

a≤a

(b

c)＝(a

b)

c≤c，即：a≤c

∴分配格是模格*§2分配格《定理》每個鏈均是分配格。證明：設<L,≤>是鏈。對任意a，b，cL(1)若a≤b或a≤c，則a

(b

c)＝a，

(a

b)

(a

c)＝a即：a

(b

c)＝(a

b)

(a

c)(2)若a≥b且a≥c，則

a

(b

c)＝b

c，

(a

b)

(a

c)＝b

c即：a

(b

c)＝(a

b)

(a

c)。得證。*§3有補格《定義》設<L,≤>是一個格，如果存在元素aL，對于任意的xL，都有：

a≤x

則稱a為格<L,≤>的全下界，記格的全下界為0。例：*§3有補格《定理》如果格<L,≤>有全上界（全下界），那么它是唯一的。證明：（反證法）設有兩個全上界a和b，則由定義

a≤b，且b≤a，由“≤”的反對稱性，a＝b。《定義》設<L,≤>是一個格，格中存在全上界和全下界，則稱該格為有界格。*§3有補格《定理》如果<L,≤>是有界格，全上界和全下界分別是1和0，則對任意元素aL，有：

a

1=1

a=1，a

1=1

a=a，

a

0=0

a=a，a

0=0

a=0。證明：因為1≤a

1，

又因(a

1)L且1是全上界，∴a

1≤1，

∴a

1=1。由交換律：1

a＝a

1=1。

因為a≤a，a≤1，∴a

a≤a

1，即：a≤a

1，又a

1≤a，∴a

1=a。仿此可得另兩式。*§3有補格《定義》設<L,≤>是一個有界格，對于L中的一個元素a，如果存在bL，使得a

b=1和a

b=0，則稱元素b是元素a的補元。討論定義：（1）∵

和

是可交換的，∴補元是相互的。

（2）

，即在有界格中，1和0互為補元；

（3）由定義可知L中一個元素的補元不一定是唯一的；例：*東南大學遠程教育離散數學第五十三講主講教師：仲新宇*§3有補格《定義》在一個有界格中，如果每個元素都至少有一個補元素，則稱此格為有補格。討論定義：（1）在有補格中，每一個元素一定存在補元（不一定是一個補元）；（2）有補格一定是有界格，而有界格不一定是有補格。請看下例：*§3有補格《定義》在一個有界格中，如果每個元素都至少有一個補元素，則稱此格為有補格。討論定義：（1）在有補格中，每一個元素一定存在補元（不一定是一個補元）；（2）有補格一定是有界格，而有界格不一定是有補格。請看下例：*§3有補格《定理》在有界分配格中，若有一個元素有補元，則必是唯一的。證明：*§4布爾代數《定義》一個有補分配格稱為布爾格。《定義》一個格<L,≤>如果它既是有補格，又是分配格，則它為有補分配格。我們把有補分配格中任一元素a的唯一補元記為a。討論定義：(1)布爾格中，每個元素有唯一的補元。(2)我們可以定義L上的一個一元運算，稱為補運算，記為“-”。-*§4布爾代數《定義》由布爾格<L,≤>，可以誘導一個包括交，并和補運算的代數系統<L,

,

,->，稱此代數系統為布爾代數。例：設S是一個非空有限集，<(S),>是一個格，且是一個布爾格。由<(S),>所誘導的代數系統為

<(S),

,

,->是一個布爾代數。其中“

,

,-”分別是集合的交、并、補運算。*§4布爾代數《定理》對于布爾代數中任意兩個元素a,b，必定有*§4布爾代數證明：*§4布爾代數《定理》設<A,

,

,->是由有限布爾格<A,≤>所誘導的一個有限布爾代數，S是布爾格<A,≤>中的所有原子的集合，則<A,

,

,->和<

(S),

,

,~>同構。討論定理：(1)當布爾代數<A,

,

,->的載體A的基數|A|是有限數時,則稱之為有限布爾代數。(2)設<A,

,

,->是一個布爾代數，a∈A,如果a蓋住0，則稱元素a是該布爾代數的一個原子。

例如：*東南大學遠程教育離散數學第五十四講主講教師：仲新宇*§4布爾代數例：<

(S),

,

,~,

,S>，其中S={a,b,c}，在這個布爾代數中的元素分三種情況：（ⅰ）界：全上界S，全下界

；（ⅱ）{a},{b},{c}單個元素集合的元素；（ⅲ）二，三個元素作為集合的元素，但它們均可用單個元素的集合的元素來表述：{a,b}={a}

{b},{a,c}={a}

{c},{b,c}={b}

{c},{a,b,c}={a}

{b}

{c}。

{a,c}{a,b,c}{a,b}{b,c}{a}{c}{b}?*§4布爾代數(3)A中除0外的每個元素，都可以唯一地表示成原子的并。該定理可得以下兩個推論：a)<B,*,

,’,0,1>與<p(S),∪,∩,~,?,S>同構，|p(S)|=2|s|所以，|B|=2|s|

，故任一有限布爾代數載體的基數是2的冪。b)任一有限布爾代數和它的原子集合S構成的冪集集合代數<p(S),∪,∩,~,?,S>同構，但后者又與任一基數相同的冪集集合代數同構，故具有相同載體基數的有限布爾代數都同構。

*§4布爾代數格有界格有補格布爾代數分配格結合律吸收律交換律冪等律同一律零一律互補律分配律德·摩根律雙重否定律*§4布爾代數例：設A是一非空集合,

(A)是A的冪集,可以驗

證,<

(A),∪,∩,~,

,A>是個布爾代數,稱此為集合代數,其中運算為∪,∩,~,最小元

,最大元A。S是命題公式的全體,則<S,∨,∧,

,0,1>是一個布爾代數,稱之為命題代數。其中運算為∨,∧,

,最小元是恒假公式0,最大元是恒真公式1。*§4布爾代數因此，從邏輯觀點看，布爾代數是命題演算系統。從集合論觀點看，布爾代數是集合代數。從抽象代數的觀點看，布爾代數是一個代數系統。*第三篇小結通過本篇的學習應該達到以下基本要求：(1)給定集合與運算的解析表達式，寫出該運算的運算表。(2)給定集合和運算，判別該集合對運算是否封閉。(3)給定二元運算，說明運算是否滿足交換律、結合律、冪等律、分配律和吸收律。(4)給定集合S上的二元運算，求出該運算的幺元、零元、冪等元和所有可逆元素的逆元。(5)給定集合S和二元運算*，能判定<S,*>是否構成半群、獨異點和群。*第三篇小結(6)給定半群S和子集B，判定B是否為S的