格和布爾代數(shù)課件1VIP

*

格和布爾代數(shù)

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

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

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

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

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

和

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

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

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

,

>為由格所誘導(dǎo)的代數(shù)系統(tǒng)。*§1格的概念3.格的主要性質(zhì)：(1)格的對偶原理設(shè)<L,≤>是格，“≤”的逆關(guān)系“≥”與L組成的偏序集<L,≥>也是格。兩者互為對偶。前者的GLB，LUB恰好是后者的LUB，GLB。如有關(guān)于<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)（結(jié)合律）交和并運算是可結(jié)合的。*§1格的概念(6)（冪等律）對L中每一個a，有a

a=a，a

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

(a

b)=a

a

(a

b)=a。*§2分配格

對格所定義的代數(shù)系統(tǒng)<L,

,

>，其運算

和

不一定滿足分配律?！抖x》設(shè)<L,

,

>是由<L,≤>所誘導(dǎo)的代數(shù)系統(tǒng)。如果對任意的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分配格《定理》每個鏈均是分配格。證明：設(shè)<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有補格《定義》設(shè)<L,≤>是一個格，如果存在元素aL，對于任意的xL，都有：

a≤x

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

a≤b，且b≤a，由“≤”的反對稱性，a＝b?！抖x》設(shè)<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有補格《定義》設(shè)<L,≤>是一個有界格，對于L中的一個元素a，如果存在bL，使得a

b=1和a

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

和

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

（2）

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

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

,

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

<(S),

,

,->是一個布爾代數(shù)。其中“

,

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

,

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

,

,->和<

(S),

,

,~>同構(gòu)。討論定理：(1)當(dāng)布爾代數(shù)<A,

,

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

,

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

例如：*東南大學(xué)遠(yuǎn)程教育離散數(shù)學(xué)第五十四講主講教師：仲新宇*§4布爾代數(shù)例：<

(S),

,

,~,

,S>，其中S={a,b,c}，在這個布爾代數(shù)中的元素分三種情況：（?。┙纾喝辖鏢，全下界

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

,{a,c}={a}

{c},{b,c}=

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



{c}。

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

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

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

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

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

證,<

(A),∪,∩,~,

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

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

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

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