山東省鄒平縣實驗中學七年級地理上冊41天氣和氣候課件(新版)湘教版

2024/4/3離散數(shù)學1第二十二章

格與布爾代數(shù)2024/4/2離散數(shù)學1第二十二章

格與布爾代數(shù)2024/4/3離散數(shù)學2目錄本章介紹另外一類具有兩種二元運算的代數(shù)系統(tǒng)——格，以及特殊的格——布爾代數(shù)：格是描述集合或命題的代數(shù)系統(tǒng)，稱為集合代數(shù)或命題代數(shù)§22.1格的定義§22.2格的性質§22.3幾種特殊的格§22.4布爾代數(shù)§22.5有限布爾代數(shù)的結構2024/4/2離散數(shù)學2目錄本章介紹另外一類具有兩種二元運2024/4/3離散數(shù)學3§22.1格的定義2024/4/2離散數(shù)學3§22.1格的定義2024/4/3離散數(shù)學4格的定義定義22.1.1：設

L,≤

是一個偏序集。如果對任意a，b∈L，{a，b}在L中都有最大下界和最小上界，則稱

L,≤

是一個格。常將{a，b}的最大下界記為inf{a,b}，最小上界記為sup{a,b}。2024/4/2離散數(shù)學4格的定義定義22.1.1：設L2024/4/3離散數(shù)學5復習定義2.4.5和定義2.4.6上(下)界：設<A,

>是一個偏序集,B

A,若存在a∈A,使得對任何x∈B都有xa(或ax),則稱a為B的上(下)界。（如果存在，上(下)界可在A中，也可在B中）上(下)確界：設<A,

>是一個偏序集，B

A，若a是B的一個上(下)界，且對B的任何一個上(下)界x，均有ax(或xa),則稱a為B的上(下)確界，也可稱為最小上界（或最大下界）。記為a=sup(B)(a=inf(B))。2024/4/2離散數(shù)學5復習定義2.4.5和定義2.4.62024/4/3離散數(shù)學6幾個是格的偏序集(a)(b)(c)圖(a)中是一個全序集(鏈)，自然是一個格。不難驗證，圖(b)和圖(c)中的偏序集中任意兩個元素都有最小上界和最大下界，因而都是格。2024/4/2離散數(shù)學6幾個是格的偏序集(a)(b)(c)2024/4/3離散數(shù)學7并非所有偏序集都是格不是所有的偏序集都是格。圖(d),(e),(f)所表示的偏序集都不是格。不難找出它們之中存在著兩個元素，或沒有最小上界，或沒有最大下界。(d)(e)(f)2024/4/2離散數(shù)學7并非所有偏序集都是格不是所有的偏序2024/4/3離散數(shù)學8子集格例1：設S是集合，ρ(S)是S的冪集。于是

ρ(S),

是一個格，稱為S的子集格。因為：首先，ρ(S),

是一個偏序集；其次，對任意的A,B∈ρ(S)，有sup{A,B}=A∪B；inf{A,B}=A∩B。2024/4/2離散數(shù)學8子集格例1：設S是集合，ρ(S)是2024/4/3離散數(shù)學9整除格例2：設Z+是所有自然數(shù)的集合。|是Z+上的整除關系。于是

Z+,|是一個格，稱為整除格。因為首先，Z+,|是一個偏序集；其次，對任意的m,n∈Z+，有sup{m,n}=[m,n](最小公倍數(shù))；inf{m,n}=(m,n)(最大公約數(shù))。2024/4/2離散數(shù)學9整除格例2：設Z+是所有自然數(shù)的集2024/4/3離散數(shù)學10子群格例1：設G是群，S(G)表示G的所有子群組成的集合。于是

S(G),

是一個格，稱為G的子群格。因為首先，S(G),

是一個偏序集；其次，對任意的H,K∈S(G)，有sup{H,K}是包含H∪K的最小子群；inf{H,K}=H∩K。2024/4/2離散數(shù)學10子群格例1：設G是群，S(G)表2024/4/3離散數(shù)學11子格定義22.1.2：設

L,≤

是格，SL，如果S,≤

也是格，則稱S,≤

是L,≤

的子格。偏序集的任何子集仍是偏序集。但是格L,≤

中的偏序集L的子集S卻不一定能夠構成格S,≤

。例如，在整除格中，取S={1，2，3}，則S,|

不是格。因為按整除關系[2,3]=6,而6S，即sup{2,3}不存在。2024/4/2離散數(shù)學11子格定義22.1.2：設L,2024/4/3離散數(shù)學12整除格的子格例4：設n是正整數(shù)，Sn={k|k＞0且k|n}。比如：S6={1,2,3,6}，S8={1,2,4,8}，S24={1,2,3,4,6,8,12,24}，…容易驗證，

Sn,|

是格，且m|n當且僅當SmSn。因此對任意的m，n，若m|n，則Sm,|

是Sn,|

的子格。當然Sn,|

的子格還有其它形式，比如{a},|

也是Sn,|

的子格，其中a∈Sn。2024/4/2離散數(shù)學12整除格的子格例4：設n是正整數(shù)，2024/4/3離散數(shù)學13格中的運算格中的inf和sup實際上是兩個二元運算。用算符×和分別表示inf和sup，即a×b=inf{a,b}，ab=sup{a,b}。這兩種運算滿足如下的性質：(1)交換律：a×b=b×a，ab=ba；(2)結合律：a×(b×c)=(a×b)×c,a(bc)=(ab)c(3)吸收律：a×(ab)=a,a(a×b)=a。？

因為a×(ab)=inf{a,sup{a,b}}，所以a×(ab)≤a，即inf{a,sup{a,b}}≤a

又因為，a≤a且a≤sup{a,b}，所以a是a與sup{a,b}的下界，即a≤inf{a,sup{a,b}}

于是inf{a,sup{a,b}}≤a≤inf{a,sup{a,b}}即a×(ab)=a。同理可證a(a×b)=a。格就是具有以上性質的二元運算的代數(shù)系統(tǒng)。2024/4/2離散數(shù)學13格中的運算格中的inf和sup實2024/4/3離散數(shù)學14從代數(shù)系統(tǒng)來定義格定義22.1.3：設L是一個集合，×和是L上的兩個二元封閉運算，若×和對a,b,c∈L，滿足：(1)交換律：a×b=b×a，ab=ba；(2)結合律：a×(b×c)=(a×b)

×c,

a(bc)=(ab)c(3)吸收律：a×(ab)=a,a(a×b)=a。則稱代數(shù)系統(tǒng)L,×,

是一個格。

L,≤稱為偏序格，L,×,

稱為代數(shù)格。2024/4/2離散數(shù)學14從代數(shù)系統(tǒng)來定義格定義22.1.2024/4/3離散數(shù)學15代數(shù)格的例子例5：設S是集合，于是ρ(S),∩,∪是一個代數(shù)格。例6：設Z+是自然數(shù)集合。定義運算×和

為：m×n=(m,n)(最大公約數(shù))，mn=[m,n](最小公倍數(shù))。則Z+,×,是一個代數(shù)格。2024/4/2離散數(shù)學15代數(shù)格的例子例5：設S是集合，于2024/4/3離散數(shù)學16代數(shù)格和偏序格是等價的定理22.1.1：偏序格必是代數(shù)格，反之亦然。證明：設

L,≤是偏序格，對a,b∈L，令a×b=inf{a,b}ab=sup{a,b}。顯然，×和是L上的封閉運算。由前面的討論可知×和滿足交換律、結合律和吸收律，因此L,×,是一個代數(shù)格。下證代數(shù)格L,×,必是偏序格。為此，需要證明：(1)L是偏序集；(2)對a,b∈L，inf{a,b}和sup{a,b}都存在。2024/4/2離散數(shù)學16代數(shù)格和偏序格是等價的定理22.2024/4/3離散數(shù)學17代數(shù)格和偏序格是等價的定理22.1.1：偏序格必是代數(shù)格，反之亦然。證明：先證代數(shù)格L,×,中L是偏序集。為此在L上定義二元關系≤如下：對a,b∈L，a≤b當且僅當a×b=a。(1)a×a=a×(a(a×a))=a，∴a≤a。(自反的)(2)若a≤b,b≤a,則a×b=a,b×a=b。而a×b=b×a∴a=b。(反對稱的)(3)若a≤b,b≤c,則a×c=(a×b)×c=a×(b×c)=a×b=a，∴a≤c。(傳遞的)∴≤是偏序關系，即L是偏序集。2024/4/2離散數(shù)學17代數(shù)格和偏序格是等價的定理22.2024/4/3離散數(shù)學18注意：定義“≤”，a≤b當且僅當a×b=a定理22.1.1：偏序格必是代數(shù)格，反之亦然。證明：下證

a,bL，inf{a,b}和sup{a,b}存在。由交換律、結合律和自反性有：(a×b)×a=a×(b×a)=a×(a×b)=(a×a)×b=a×b；

(a×b)×b=a×(b×b)=a×b，于是

a×b≤a,a×b≤b,從而a×b是a,b的下界。設c是a和b的任意下界，即c≤a，c≤b，則c×a=c,c×b=c。于是c×(a×b)=(c×a)×b=c×b=c，即c≤a×b。因此a×b=inf{a,b}。同理可證ab=sup{a,b}?？傊?，代數(shù)格必是偏序格。由定理可知，互為等價的兩個格

L,≤和L,×,，其運算×,可以分別是在偏序關系≤下，兩個運算對象的最大下界和最小上界。2024/4/2離散數(shù)學18注意：定義“≤”，a≤b當且僅2024/4/3離散數(shù)學19代數(shù)格的子格定義22.1.4：若

L,×,是格，SL且S對運算×和封閉，則稱S,×,為L,×,的子格。設L,≤和L,×,是等價的兩個格，SL。若S,×,是L,×,的子格，則S,≤也是L,≤的子格。a1a2a3a4a5但是，若S,≤是L,≤的子格，而S,×,不一定是L,×,的子格。例如，右圖所示的格，其中L={a1,a2,a3,a4,a5}。取S={a1,a2,a3,a5}。顯然

S,≤是L,≤的子格，則S,×,卻不是L,×,的子格。因為a2×a3=a4S。這說明，偏序格的子格和代數(shù)格的子格的定義是有區(qū)別的。2024/4/2離散數(shù)學19代數(shù)格的子格定義22.1.4：若2024/4/3離散數(shù)學20§22.2格的性質2024/4/2離散數(shù)學20§22.2格的性質2024/4/3離散數(shù)學21偏序關系與運算我們知道，偏序格

L,≤是等價于代數(shù)格L,×,，其中對任意a,b∈L，a×b=inf{a,b},ab=sup{a,b}。從偏序格與代數(shù)格等價性的證明中可看到，L中元素的偏序關系是用運算×和來定義的。即：

a≤b當且僅當a×b=a當且僅當ab=b。定理22.2.1：設

L,≤是格，a,b∈L。于是，a≤b當且僅當a×b=a當且僅當ab=b。證明：若a≤b，由a≤a知，a是{a,b}的下界，故a≤a×b。又由×的定義,a×b≤a，故a×b=a。

若a×b=a，則由吸收律可知：ab=(a×b)b=b。

若ab=b，則由的定義知ab=sup{a,b}，于是b=sup{a,b}，故a≤b。2024/4/2離散數(shù)學21偏序關系與運算我們知道，偏序格2024/4/3離散數(shù)學22格中的運算保偏序關系定理22.2.2：設

L,≤是格，a,b,c∈L。于是，若b≤c，則a×b≤a×c，ab≤ac。證明：因b≤c，由定理22.2.1知b×c=b。于是，(a×b)×(a×c)=a×(b×a)×c=a×(a×b)×c=(a×a)×(b×c)=a×b再由定理22.2.1知，a×b≤a×c。同理可證ab≤ac。2024/4/2離散數(shù)學22格中的運算保偏序關系定理22.22024/4/3離散數(shù)學23分配不等式在環(huán)和域中，加法和乘法這兩種運算是通過乘法對加法的分配律聯(lián)系起來的。那么，在格中的兩種運算是否也存在分配律呢？一般來說，在格中的兩種運算中分配律是不成立的，倒是存在兩個分配律的不等式。定理22.2.3：設

L,≤是格，a,b,c∈L。于是，a(b×c)≤(ab)×(ac)(a×b)(a×c)≤a×(bc)證明：因為a≤(ab)，a≤(ac)(a是{(ab),(ac)}的下界)

，所以a≤(ab)×(ac)(=inf{ab,ac})

(22.1)又因b×c≤b≤(ab)，b×c≤c≤(ac)，所以b×c≤(ab)×(ac)(22.2)綜合(22.1)和(22.2)有a(b×c)≤(ab)×(ac)。同理可證(a×b)(a×c)≤a×(bc)。2024/4/2離散數(shù)學23分配不等式在環(huán)和域中，加法和乘法2024/4/3離散數(shù)學24模不等式定理22.2.4：設

L,≤是格，a,b,c∈L。于是，a≤b當且僅當a(b×c)≤b×(ac)。證明：若a≤b，則由定理22.2.1知，ab=b。又由定理22.2.3知，a(b×c)≤(ab)×(ac)=b×(ac)。反之，若a(b×c)≤b×(ac)，則因為a≤a(b×c)≤b×(ac)≤b。所以有a≤b?？傊?，a≤b當且僅當a(b×c)≤b×(ac)。2024/4/2離散數(shù)學24模不等式定理22.2.4：設L2024/4/3離散數(shù)學25格的同態(tài)定義22.2.1設

L,×,和S,∧,∨是兩個格，f是L到S的映射。若對任意a,b∈L,有：

f(a×b)=f(a)∧f(b)f(ab)=f(a)∨f(b)

則稱f是L到S的格同態(tài)。特別，L到L的格同態(tài)稱為格的自同態(tài)；若f是雙射，則稱f是格同構，并稱L與S是同構的。2024/4/2離散數(shù)學25格的同態(tài)定義22.2.1設L2024/4/3離散數(shù)學26

保序映射定理22.2.5設

L,×,和S,∧,∨是兩個格，它們分別對應偏序關系≤L和≤S，f是L到S的格同態(tài)。于是，對任意a,b∈L,若a≤Lb,則f(a)≤Sf(b)。稱f是保序映射。證明：∵a≤Lb,∴a×b=a,從而f(a×b)=f(a),于是f(a)=f(a×b)=f(a)∧f(b)，故f(a)≤Sf(b)。此定理說明，同態(tài)映射必是保序映射，但反之不然。2024/4/2離散數(shù)學262024/4/3離散數(shù)學27

保序映射不一定是同態(tài)映射例子：已知

S12,|

和S12,≤

是兩個格，其中“≤”是普通的小于等于關系。設它們分別對應代數(shù)格S12,×,

和S12,∧,∨,于是,對任意a,b∈S12

a×b=(a,b)ab=[a,b]a∧b=min{a,b}a∨b=max{a,b}

現(xiàn)定義恒等映射g(a)=a,a∈S12,則g是

S12,|

到S12,≤

的保序映射，但不是同態(tài)映射，例如：g(23)=g(6)=6，而g(2)∨g(3)=2∨3=32024/4/2離散數(shù)學27保序映射不一定是同態(tài)映射例子2024/4/3離散數(shù)學28

自同態(tài)像是代數(shù)子格定理22.2.6設

L,×,是一個格，g是L的自同態(tài)，于是，g(L)是L的代數(shù)子格。證明：任取a’,b’∈g(L)，則存在a,b∈L，使g(a)=a’,g(b)=b’。于是

a’×b’=g(a)×g(b)=g(a×b)∈g(L)a’b’=g(a)g(b)=g(ab)∈g(L)

這說明g(L)在運算×、下封閉，故g(L),×,是L,×,的代數(shù)子格。2024/4/2離散數(shù)學28自同態(tài)像是代數(shù)子2024/4/3離散數(shù)學29

格同構的逆也是格同構定理22.2.7設

L,×,和S,∧,∨是兩個格，若g是L到S的格同構，則g－1是S到L的格同構。證明：顯然，g－1是S到L的雙射。任取a’,b’∈S，則有唯一的a,b∈L，使g(a)=a’,g(b)=b’。從而

g－1(a’∧b’)=g－1(g(a)∧g(b))=g－1(g(a×b))=a×b=g－1(a’)×g－1(b’)

同理，g－1(a’∨b’)=g－1(a’)g－1(b’)由定理22.2.5和定理22.2.7，我們有：定理22.2.8若g是格

L,×,到格S,∧,∨的格同構，則對任意a,b∈L,a≤Lb當且僅當g(a)≤Sg(b)2024/4/2離散數(shù)學29格同構的逆也是格2024/4/3離散數(shù)學30n維格設L={0，1}，規(guī)定0≤0，0≤1，1≤1，于是〈L,≤〉是一個格。令：

Ln={<a1,…,an>|ai∈L，i=1,…,n，n≥2}

規(guī)定<a1,…,an>≤n<b1,…,bn>當且僅當ai≤bii=1,…,n。于是〈Ln,≤〉是一個格,稱為n維格。例如:〈L,≤〉01〈L2,≤〉<0,0><1,1><1,0><0,1>〈L3,≤〉<1,0,0><0,0,1><0,0,0><0,1,1><1,1,0><1,1,1><1,0,1><0,1,0>令〈Ln,×,〉是與格〈Ln,≤〉等價的代數(shù)格易證，對任意<a1,…,an>，<b1,…,bn>∈Ln,有<a1,…,an>×<b1,…,bn>=<a1∧b1,…,an∧bn><a1,…,an>

<b1,…,bn>=<a1∨b1,…,an∨bn>其中，a∧b=inf{a,b},a∨b=sup{a,b}2024/4/2離散數(shù)學302024/4/3離散數(shù)學31與n維格同構的例例1：設S={x1,…,xn},于是,子集格

ρ(S),

與n維格

Ln,≤

同構。證明：定義ρ(S)到Ln的映射f如下:任取A∈ρ(S)，f(A)=<a1,…,an>,其中ai=1當且僅當xi∈A,i=1,…,n，顯然，f是ρ(S)到Ln的雙射。下證同態(tài)性：任取A,B∈ρ(S),令f(A)=<a1,…,an>。f(B)=<b1,…,bn>,f(A∩B)=<c1,…,cn>,于是，由f的定義有：

ai=1當且僅當xi∈A，i=1,…,nbi=1當且僅當xi∈B，i=1,…,nci=1當且僅當xi∈A∩B，i=1,…,n2024/4/2離散數(shù)學31與n維格同構的例例1：設S={x2024/4/3離散數(shù)學32與n維格同構的例…ci=1當且僅當xi∈A∩B，i=1,…,n

從而ci=1當且僅當xi∈A且xi∈B,當且僅當ai=1且bi=1,i=1,…,n.因此ci=ai∧bi,i=1,…,n，故

<c1,…,cn>=<a1∧b1,…,an∧bn>=<a1,…,an>×<b1,…,bn>

這說明f(A∩B)=f(A)×f(B)

同理可證f(A∪B)=f(A)

f(B)2024/4/2離散數(shù)學32與n維格同構的例…2024/4/3離散數(shù)學33§22.3幾種特殊的格2024/4/2離散數(shù)學33§22.3幾種特殊的格2024/4/3離散數(shù)學34

最小上界與最大下界的推廣命題22.3.1設

L,≤是一個格，于是，L的任何非空有限子集S都有一個最小上界和最大下界。證明：對S中元素個數(shù)作歸納證明。設|S|=n，n≧1。

n=1時，結論顯然成立。假設|S|=n-1時，結論成立。

2024/4/2離散數(shù)學34最小上界與最大下界的推廣命2024/4/3離散數(shù)學35|S|=n＞1時,設S={a1,…,an-1,an}.令S’={a1,…,an-1}。由歸納假設，S’有一個最小上界，設為a’∈L,于是，{a’,an}也有最小上界，設為a。下證a就是S的最小上界。因為a’≤a，an≤a，而a’是S’的上界，所以a1≤a’,…,an-1≤a’。于是a1≤a,…,an-1≤a,an≤a，從而a是S的上界。任取S的一個上界b，則有a1≤b,…,an-1≤b,an≤b，于是b是S’的上界，故a’≤b,又因為an≤b，所以b是{a’,an}的上界，而a是{a’,an}的最小上界，故a≤b，這說明a是S的最小上界。同理可證S有一個最大下界。2024/4/2離散數(shù)學35|S|=n＞1時,設S={a1,2024/4/3離散數(shù)學36

格的無限子集不一定有最小上界或最大下界通常將子集S的最小上界記為supS,最大下界記為infS。注意：一個格的無限子集不一定有最小上界或最大下界。例如,在格〈Z+,≤〉中,令所有正奇數(shù)作成的集合為D+，于是D+Z+，但D+沒有最小上界。2024/4/2離散數(shù)學36格的無限子集不一2024/4/3離散數(shù)學37

有界格定義22.3.1設

L,≤是一個格，若L有最小元素（記為0）和最大元素（記為1），則稱L為有界格。有時，將有界格L,≤的等價代數(shù)格記為L,×，，0，1，其中0和1稱為L的界。設R為實數(shù)集，L={x∈R|0≤x≤1}，則L,≤是一個有界格。2024/4/2離散數(shù)學372024/4/3離散數(shù)學38

有限格必是有界格由命題22.3.1知，有限格必是有界格。令L={a1,…,an}，則L是有界格，并且：

0=a1

×…

×an1=a1…

an命題22.3.2若

L,≤是有界格，則對任意a∈L，有：

a0=a，a×1=aa1=1，a×0=0證明：因為對任意a∈L，有0≤a，a≤1。所以a0=a，a×1=a，a1=1，a×0=0。2024/4/2離散數(shù)學38有限格必是有界格2024/4/3離散數(shù)學39

余元素定義22.3.2設

L,≤是有界格，a,b∈L,如果a×b=0，ab=1，則稱a和b互為余元素。有界格中，一個元素可能沒有余元素，若有也可能不止一個。例如：ab10a和b都無余元素ab10a和b互為余元素(唯一)abc01a的余元素是b和c2024/4/2離散數(shù)學392024/4/3離散數(shù)學40

有余格命題22.3.3在有界格

L,×，，0，1中，0是1的唯一余元素，1是0的唯一余元素。證明：(證0是1的唯一余元素)由命題22.3.2知，

0×1=0；01=1。所以0與1互為余元素。設c∈L是1的余元素，則：1×c=0；1c=1

但因為c≦1，所以1×c=c，因此c=0。同理可證1是0的唯一余元素。定義22.3.3設

L,≤是有界格，若L中每個元素至少有一個余元素，則稱L,≤為有余格。例2設S={a1,…,an},則(S),

是有余格。其中和S是(S),

的界,A∈(S)的余元素為S－A。2024/4/2離散數(shù)學402024/4/3離散數(shù)學41

分配格定義22.3.4設

L,×,是一個格，如果對任意的a,b,c∈L，有

a×(bc)=(a×b)(a×c)a(b×c)=(ab)×(ac)

則稱格L為分配格。注意：分配格定義中的兩個等式是等價的，即由一個等式可推出另一個等式。另外，并不是所有格都是分配格。例如上述Hasse圖所表示的格都不是分配格。b×(ac)=b≠(b×a)(b×c)=c故不是分配格abc01u×(vw)=u≠(u×v)(u×w)=0故不是分配格uvw012024/4/2離散數(shù)學412024/4/3離散數(shù)學42

鏈都是分配格有一類格是分配格，即：命題22.3.4任意一個鏈都是分配格。證明：設

L,≤是一個鏈，任取a,b,c∈L，則可分以下兩種情況討論。b≤a且c≤a,這時,bc≤a,從而a×(bc)=bc

而a×b=b，a×c=c,

于是，(a×b)(a×c)=bc，故a×(bc)=(a×b)(a×c)2024/4/2離散數(shù)學422024/4/3離散數(shù)學43鏈都是分配格a≤b或a≤c，這時a≤b≤bc或者a≤c≤bc，從而總有a≤bc,

于是，a×(bc)=a。而a×b=a或a×c=a，故由吸收律知，

(a×b)(a×c)=a(a×c)=a，或者(a×b)(a×c)=(a×b)a=a，故a×(bc)=(a×b)(a×c)不難驗證，Ln,≤n

，ρ(S),,Sn,|

以及Z+,|等都是分配格，但它們都不是鏈。2024/4/2離散數(shù)學43鏈都是分配格a≤b或a≤c，這時2024/4/3離散數(shù)學44DeMorgan律定理22.3.1設

L,×,是分配格，a,b∈L,于是，若a,b有余元素a’,b’，則(a×b)’=a’b’；(ab)’=a’×b’證明：（證(a×b)’=a’b’）因為(a’b’)(a×b)=(a’b’a)×(a’b’b)=(1b’)×(a’1)=1×1=1；而

(a’b’)×(a×b)=(a’×a×b)(b’×a×b)=00=0所以(a×b)’=a’b’，同理有(ab)’=a’×b’2024/4/2離散數(shù)學442024/4/3離散數(shù)學45

模格定義22.3.5設

L,≤是一個格，對任意a,b,c∈L,如果由a≤b可推出a(b×c)=b×(ac)，則稱L,≤為模格。分配格必是模格。設L,×,是分配格，任取a,b,c∈L，若a≤b，則a(b×c)=(ab)×(ac)=b×(ac)。但模格不一定是分配格。如圖所示的格是模格但不是分配格。如何判斷一個格是否為模格？我們有如下定理。2024/4/2離散數(shù)學452024/4/3離散數(shù)學46

模格的充分必要條件定理22.3.2格

L,≤為模格的充分必要條件是，對任意a,b,c∈L,若a≤b，a×c=b×c，ac=bc，則a=b。證明：[必要性]設L,≤是模格，a,b,c∈L，若a≤b，a×c=b×c，ac=bc，則由吸收律和給定的條件，有：

a=a(a×c)=a(b×c)=b×(ac)=b×(bc)=b

即a=b。下證充分性。2024/4/2離散數(shù)學46模格的充分必要2024/4/3離散數(shù)學47

模格的充分必要條件[充分性]任取a,b,c∈L，設a≤b。因為(a(b×c))c=a((b×c)c)=ac(22.5)

又因a≤b,a≤ac,所以a≤b×(ac),

從而由定理22.2.2(格運算保偏序關系),ac≤(b×(ac))c≤(ac)c=ac，故有(b×(ac))c=ac(22.6)

由(22.5)和(22.6)式有

(a(b×c))c=(b×(ac))c(22.7)

2024/4/2離散數(shù)學47模格的充分必要2024/4/3離散數(shù)學48

模格的充分必要條件另一方面,(b×(ac))×c=b×((ac)×c)=b×c(22.8)

而b×c≤a(b×c)，所以由定理22.2.4有b×c=(b×c)×c≤(a(b×c))×c≤(b×(ac))×c=b×((ac)×c)=b×c故(a(b×c))×c=b×c(22.9)由(22.8)和

(22.9)式有

(a(b×c))×c=(b×(ac))×c(22.10)2024/4/2離散數(shù)學48模格的充分必要條件另2024/4/3離散數(shù)學49模格的充分必要條件又由格的分配不等式知，當a≤b時，

a(b×c)≤(ab)×(ac)=b×(ac)故a(b×c)≤b×(ac)(22.11)最后由

a(b×c)≤b×(ac)

(22.11)

(a(b×c))×c=(b×(ac))×c(22.10)(a(b×c))c=(b×(ac))c(22.7)三式及定理中的條件，得a(b×c)=b×(ac)(*)

故L,≤是模格。2024/4/2離散數(shù)學49模格的充分必要條件又由格的分配不2024/4/3離散數(shù)學50關于分配格的一個結論定理22.3.3設

L,×,是分配格,于是,對任意a,b,c∈L，若a×c=b×c,ac=bc，則有a=b。證明：由假設有

a=a×(ac)=a×(bc)=(a×b)(a×c)=(a×b)(b×c)=b×(ac)=b×(bc)=b即a=b2024/4/2離散數(shù)學50關于分配格的一個結論定理22.32024/4/3離散數(shù)學51有余分配格的元素的余元素唯一。推論22.3.1設

L,×,是有余分配格，則對任意a∈L，a的余元素a’是唯一的。證明：設a’和a’’都是a的余元素。于是

a×a’=0，aa’=1；

a×a’’=0，aa’’=1

從而a×a’=a×a’’，aa’=aa’’，由定理22.3.3知，a’=a’’，故a的余元素是唯一的。2024/4/2離散數(shù)學51有余分配格的元素的余元素唯一。推2024/4/3離散數(shù)學52§22.4布爾代數(shù)2024/4/2離散數(shù)學52§22.4布爾代數(shù)2024/4/3離散數(shù)學53

布爾代數(shù)的定義定義22.4.1有余分配格稱為布爾代數(shù)。由布爾代數(shù)的定義及上一節(jié)所得的一些結論，可以將一個布爾代數(shù)記為

B,·,+,－,0,1，其中“·”稱為乘法運算，“+”稱為加法運算，“－”稱為余運算，a∈B的余元素記為a，0，1是B的界。有時，也可將a·b簡記為ab。下面根據(jù)布爾代數(shù)的定義，分類給出布爾代數(shù)的一些重要性質。2024/4/2離散數(shù)學532024/4/3離散數(shù)學54

布爾代數(shù)的性質設

B,·,+,－,0,1是一個布爾代數(shù)，于是，對任意a,b,c∈B，有：因為B,·,+是一個代數(shù)格，所以有a·a=a，a+a=a(等冪律)a·b=b

·a，a+b=b+a(交換律)(a·b)·c=a·(b·c)，(a+b)+c=a+(b+c)(結合律)a·(a+b)=a，a+(a·b)=a(吸收律)因為

B,·,+是分配格，所以有a·(b+c)=(a·b)+(a·c)，a+(b·c)=(a+b)·(a+c)(分配律)(a+b)·(a+c)·(b+c)=(a·b)+(a·c)+(b·c)若a·b=a

·c，a+b=a+c，則b=c2024/4/2離散數(shù)學542024/4/3離散數(shù)學55

布爾代數(shù)的性質因為

B,·,+,－,0,1是有界格，所以有0≤a≤1a·0=0，a+1=1a·1=a，a+0=a因為

B,·,+,－,0,1是有余分配格，所以有a·a=0，a+a=10=1，1=0a·b=a+b，a+b=a·b2024/4/2離散數(shù)學552024/4/3離散數(shù)學56

布爾代數(shù)的性質因為

B,≤

是偏序格，所以有a·b=inf{a,b}，a+b=sup{a,b}a≤b當且僅當a+b=b當且僅當a·b=aa≤b當且僅當a·b=0當且僅當b≤a當且僅當a+b=1易證，一個具有上述性質的代數(shù)系統(tǒng)必是布爾代數(shù)。但上述性質不是獨立的，即有些性質可以由其他性質推導出來，下面用相互獨立的公理來重新定義布爾代數(shù)。2024/4/2離散數(shù)學562024/4/3離散數(shù)學57Huntington公理定理22.4.1設集合B至少含兩個元素，“·”和“+”是定義在B上的兩個代數(shù)運算。如果對任意a,b,c∈B，滿足下面的公理：H1：a·b=b·a；a+b=b+aH2：a·(b+c)=(a·b)+(a·c)；a+(b·c)=(a+b)·(b+c)H3：B中有元素0和1，使得對任意a∈B，有a·1=a，a+0=aH4：對任意a∈B，有a∈B，使得a·a=0,a+a=1則B,·,+,－,0,1是一個布爾代數(shù)。由H1知運算有交換律，由H2知運算有分配律，由H4知B的任何元素有余元素。2024/4/2離散數(shù)學57Hunti2024/4/3離散數(shù)學58定理22.4.1的證明證明：由布爾代數(shù)的定義，我們只需證明

B,·,+是格，且0，1分別是B的最小元和最大元。由H4知，B是有余格，又由H2知，B是分配格，從而B是有余分配格，即布爾代數(shù)。首先給出幾個有用的公式。(證明略)對任意a∈B，a+1=1，a·0=0(22.12)若a+b=a+c，a+b=a+c，則b=c(22.13)若a·b=a·c，a·b=a·c，則b=c(22.14)

下證B,·,+是格。2024/4/2離散數(shù)學58定理22.4.1的證明證明：由布2024/4/3離散數(shù)學59定理22.4.1的證明由H1知，B,·,+滿足交換律。因為a+(a·b)=(a·1)+(a·b)(由H3)=a·(1+b)(由H2)=a·(b+1)(由H1)=a·1(由22.12)=a(由H3)a·(a+b)=(a+0)·(a+b)(由H3)

=a+(0·b)(由H2)

=a+(b·0)(由H1)

=a+0(由22.12)

=a(由H3)

所以，

B,·,+滿足吸收律。2024/4/2離散數(shù)學59定理22.4.1的證明由H1知，2024/4/3離散數(shù)學60定理22.4.1的證明令R=a·(b·c)，L=(a·b)·c，于是

a+R=a+(a·(b·c))=a(由吸收律)a+L=a+((a·b)·c)=(a+(a·b))·(a+c)(由H2)

=a·(a+c)=a(由吸收律)

因此，a+R=

a+L。又因為

a+R=a+(a·(b·c))=(a+a)·(a+(b·c))(由H2)=1·(a+(b·c))=a+(b·c)(由H1,H4及H3)a+L=a+((a·b)·c)=(a+(a·b))·(a+c)(由H2)=((a+a)·(a+b))·(a+c)(由H2)=((1·(a+b))·(a+c)(由H1及H4)

=(a+b)·(a+c)=a+(b·c)(由H1,H3及H2)所以a+R=a+L，故由(22.13)知，R=L。2024/4/2離散數(shù)學60定理22.4.1的證明令R=a2024/4/3離散數(shù)學61定理22.4.1的證明再令H=a+(b+c)，K=(a+b)+c，于是

a·H=a·(a+(b+c))=a(由吸收律)a·K=a·((a+b)+c)=(a·(a+b))+(a·c)(由H2)=a+(a·c)=a(由吸收律)因此，a·H=a·K。又因為

a·H=a·(a+(b+c))=a·a+a·(b+c)(由H2)=0+a·(b+c)=a·(b+c)(由H4,H1,H2)

a·K=a·((a+b)+c)=a·(a+b)+(a·c)(由H2)=((a·a)+(a·b))+(a·c)(由H2)=(0+(a·b))+(a·c)(由H4)=(a·b)+(a·c)=a·(b+c)(由H1,H3,H2)所以，a·H=a·K，由(22.14)知，H=K2024/4/2離散數(shù)學61定理22.4.1的證明再令H=a2024/4/3離散數(shù)學62定理22.4.1的證明總之，

B,·,+滿足結合律。綜上所述，B,·,+滿足交換律、吸收律和結合律，所以是格?，F(xiàn)定義B上的偏序關系“≤”如下：

a≤b當且僅當a·b=a

于是，由定理22.1.1知，

B,≤是一個格，并且，a≤b當且僅當a+b=b

最后，由H3知，對任意a∈B，有

a·1=a，a+0=a

故0≤a≤1，即0和1分別是B的最小元素和最大元素。因此，B,·,+,－,0,1是布爾代數(shù)。2024/4/2離散數(shù)學62定理22.4.1的證明總之，2024/4/3離散數(shù)學63布爾代數(shù)的例例1設B={0,1}，B上的運算“·”、“+”和“－”定義如下：

·01+01xx0000010110111110

易證，

B,·

,+,－,0,1是布爾代數(shù)。這是最簡單的一個布爾代數(shù)，常稱為電路代數(shù)。例2設S是一個非空集合，則(S),∩,∪,－,,S是一個布爾代數(shù)，對任意A∈(S),A=S－A。稱此代數(shù)為集合代數(shù)。2024/4/2離散數(shù)學63布爾代數(shù)的例例1設B={0,2024/4/3離散數(shù)學64布爾代數(shù)的例例3設P是命題公式的集合，不難證明，

P,∧,∨,,F,T是一個布爾代數(shù),稱為命題代數(shù)。例4令Bn={<x1,…,xn>|xi∈{0,1},i=1,…,n}，對任意a,b∈Bn,令a=<a1,…,an>,b=<b1,…,bn>，定義Bn上的運算如下：

a·b=<a1·b1,…,an·bn>a+b=<a1+b1,…,an+bn>a=<a1,…,an>

其中，0=1，1=0。不難證明，Bn,·,+,－,0,1是一個布爾代數(shù)，其中，0n=<0,…,0>∈Bn

，1n=<1,…,1>∈Bn

。此代數(shù)稱為開關代數(shù)。2024/4/2離散數(shù)學64布爾代數(shù)的例例3設P是命題公2024/4/3離散數(shù)學65子布爾代數(shù)定義22.4.2設

B,·

,+,－,0,1是一個布爾代數(shù)，SB，如果S包含元素0和1，并且對運算·

,+,－是封閉的，則S,·

,+,－,0,1稱為B,·

,+,－,0,1的子布爾代數(shù)。定理22.4.2設

B,·,+,－,0,1是布爾代數(shù)，S是B的非空子集，如果S對運算{·,－}或{+,－}是封閉的，則S是B的子布爾代數(shù)。證明：設S對運算{·,－}封閉，由S≠知，存在a∈S，于是a∈S。從而a·a=0∈S，且0=1∈S。又任取a,b∈S，因為a+b=(a·b)，所以a+b∈S，即S對+是封閉的，且包含0和1，故由定義知，S是B的子布爾代數(shù)。同理可證，若S對{+,－}封閉，則S是B的子布爾代數(shù)。2024/4/2離散數(shù)學65子布爾代數(shù)定義22.4.22024/4/3離散數(shù)學66子布爾代數(shù)由子布爾代數(shù)的定義知，子布爾代數(shù)本身構成一個布爾代數(shù)。要注意的是，布爾代數(shù)B的子集S可以是布爾代數(shù)，但它可能不是B的子布爾代數(shù)，因為它對B中的運算可能不是封閉的。例5考慮如圖所示的格不難驗證它是一個格。令S1={a,a,0,1}，S2={a,b,0,1}，S3={a,b,0,1}。則S1是子布爾代數(shù)，因為它對{·，－}封閉；S2不是子布爾代數(shù)，因為它對運算“－”不封閉；S3是布爾代數(shù)，但不是所給代數(shù)的子布爾代數(shù)，因為它對運算“－”不封閉。2024/4/2離散數(shù)學66子布爾代數(shù)由子布爾代數(shù)的定義知，2024/4/3離散數(shù)學67一個格的圖示圖22.6a+ba0b1baa·b2024/4/2離散數(shù)學67一個格的圖示圖22.6a+ba02024/4/3離散數(shù)學68布爾代數(shù)的同態(tài)定義22.4.3設

B,·,+,－,0,1和S,∧,∨,,,是兩個布爾代數(shù)，f是B到S的映射。如果對任意a,b∈B有

f(a·b)=f(a)∧f(b)

f(a+b)=f(a)∨f(b)

f(a)=f(a)

f(0)=f(1)=

則稱f為B到S的一個布爾同態(tài)。稱f(B)是布爾代數(shù)B的同態(tài)象。如果f是雙射，則稱f是布爾同構，也稱B與S同構。顯然，f(B)是S的子布爾代數(shù)。2024/4/2離散數(shù)學68布爾代數(shù)的同態(tài)定義22.4.32024/4/3離散數(shù)學69布爾代數(shù)的同態(tài)定理22.4.3設f是布爾代數(shù)

B,·,+,－,0,1到布爾代數(shù)S,∧,∨,,,的一個映射，如果對任意a,b∈B，都有

f(a·b)=f(a)∧f(b)f(a)=f(a)

則f是B到S的布爾同態(tài)。證明：對任意a,b∈B，由假設有

f(a+b)=f(a+b)=f(a+b)=f(a·b)=(f(a)∧f(b))=(f(a)∧

f(b))=f(a)∨f(b)

f(0)=f(a·a)=f(a)∧f(a)=f(a)∧

f(a)=

f(1)=f(a+a)=f(a)∨f(a)=f(a)∨f(a)=

故由定義知，f是B到S的布爾同態(tài)。2024/4/2離散數(shù)學69布爾代數(shù)的同態(tài)定理22.4.32024/4/3離散數(shù)學70布爾代數(shù)的同態(tài)定理22.4.4設f是布爾代數(shù)

B,·,+,－,0,1到布爾代數(shù)S,∧,∨,,,的一個映射，如果對任意a,b∈B，都有

f(a·b)=f(a)∧f(b)f(a+b)=f(a)∨f(b)

則f(B),∧,∨,,f(0),f(1)是一個布爾代數(shù)，且f是B到f(B)的布爾同態(tài)，其中是關于f(0)和f(1)的余運算。2024/4/2離散數(shù)學70布爾代數(shù)的同態(tài)定理22.4.42024/4/3離散數(shù)學71定理22.4.4的證明證明：顯然，f(B)S。對任意a’∈f(B)，必有a∈B，使得f(a)=a’。因為，

a’∧f(0)=f(a)∧f(0)=f(a·0)=f(0)。所以f(0)≤a’。又因為，a’∨f(1)=f(a)∨f(1)=f(a+1)=f(1)

所以a’≤f(1)。于是，f(0)≤a’≤f(1)。故f(0)和f(1)分別是f(B)中的最小元素和最大元素。又任取a∈B，有f(a)∧f(a)=f(a·a)=f(0)f(a)∨f(a)=f(a+a)=f(1)

于是，f(a)是f(a)的余元素，故f(a)=f(a)

以上說明，f(B)對運算∧,∨,是封閉的，故f(B)是S的子布爾代數(shù)。由又定理22.4.3知，f是B到f(B)的布爾同態(tài)。2024/4/2離散數(shù)學71定理22.4.4的證明證明：顯然2024/4/3離散數(shù)學72§22.5有限布爾代數(shù)

的結構2024/4/2離散數(shù)學72§22.5有限布爾代數(shù)

2024/4/3離散數(shù)學73本節(jié)提到的布爾代數(shù)，如不特別指出，都是指有限布爾代數(shù)。前一節(jié)中，我們構造了一些布爾代數(shù)。人們可能想象有很大的自由來構造一些不同的布爾代數(shù)，實際上并非如此。本節(jié)將證明，每個有限布爾代數(shù)的階必為2的正整數(shù)次冪，并且維數(shù)相同的有限布爾代數(shù)必同構。2024/4/2離散數(shù)學73本節(jié)提到的布爾代數(shù)，如不特別指出2024/4/3離散數(shù)學74n維布爾代數(shù)定義22.5.1設

B,·,+,－,0,1是布爾代數(shù)，若存在e1,…,en∈B，使得對任意a∈B，都可唯一地表示為

a=a1e1+,…,+anen

其中ai∈{0,1}，i=1,…,n。則稱e1,…,en為布爾代數(shù)B的一組基底，并稱此布爾代數(shù)為n維的。易知，ei≠0，i=1,…,n2024/4/2離散數(shù)學74n維布爾代數(shù)定義22.5.12024/4/3離散數(shù)學75極小元素定義22.5.2設

B,·,+,－,0,1是布爾代數(shù)，a∈B，且a≠0。若對任意x∈B，a·x=0或者a·x=a，則稱a為布爾代數(shù)B的極小元素(或原子)。由定義知，有限布爾代數(shù)的極小元素就是其Hasse圖中與最小元素0連結的那些元素，并且，若a和b是兩個不同的極小元素，則必有a·b=02024/4/2離散數(shù)學75極小元素定義22.5.22024/4/3離散數(shù)學76布爾代數(shù)有極小元命題22.5.1設B是布爾代數(shù)，a∈B，a≠0。若a不是極小元素，則必存在元素b＜a。證明：因為a不是極小元素，所以存在非零元素x0∈B，使得a·x0≠0且a·x0≠a。令a·x0=a1，則顯然a1＜a(即a1≤a且a1≠a)

若a1是極小元素，則命題得證，否則，有非零元素x1∈B，使得a1·x1≠0且a1·x1≠a1。令a1·x1=a2，則有a2＜a1＜a。重復上述過程，由于B有限，故最后總可找到極小元素an，使得

an＜an-1

…＜a2＜a1＜a2024/4/2離散數(shù)學76布爾代數(shù)有極小元命題22.5.12024/4/3離散數(shù)學77布爾代數(shù)的基底由極小元做成定理22.5.1有限布爾代數(shù)的基底必是此代數(shù)的所有極小元素；反之，有限布爾代數(shù)的所有極小元素必能做成此代數(shù)的基底。證明：設e1,…,en是有限布爾代數(shù)

B,·,+,－,0,1的基底，先證ei是極小元素，i=1,…,n。若ei不是極小元素，則存在a∈B，使得

a·ei≠0且a·ei≠ei

設a·ei=b，則b＜ei

。令

b=

1e1

+…+nen，bei=c

由b＜ei知，bei=b,從而，b+c=bei+bei=ei

，令

c=1e1

+…+nen

，于是有

ei=b+c=(

1+

1)e1

+,…,+(

n+

n)en2024/4/2離散數(shù)學77布爾代數(shù)的基底由極小元做成定理22024/4/3離散數(shù)學78定理22.5.1的證明由基底的性質，有

j+

j=0(j≠i，j=1,…,n)；i+

i=1

也即i=1或i=1，j=

j=0,j≠i，j=1,…,n

若i=1，則b=ei，矛盾，若i=1，則c=ei，即bei=ei，于是

0=(bb)ei=b(bei)=bei=b

此與b≠0矛盾。故ei是極小元素，i=1,…,n再證e1,…,en是B的所有極小元素。設e*是B的一個極小元素。令e*=

1e1

+…+nen

因e*≠0，故不妨設

i≠0，于是e*ei=