山东省邹平县实验中学七年级地理上册41天气和气候课件(新版)湘教版

2024/4/3离散数学1第二十二章

格与布尔代数2024/4/2离散数学1第二十二章

格与布尔代数2024/4/3离散数学2目录本章介绍另外一类具有两种二元运算的代数系统——格，以及特殊的格——布尔代数：格是描述集合或命题的代数系统，称为集合代数或命题代数§22.1格的定义§22.2格的性质§22.3几种特殊的格§22.4布尔代数§22.5有限布尔代数的结构2024/4/2离散数学2目录本章介绍另外一类具有两种二元运2024/4/3离散数学3§22.1格的定义2024/4/2离散数学3§22.1格的定义2024/4/3离散数学4格的定义定义22.1.1：设

L,≤

是一个偏序集。如果对任意a，b∈L，{a，b}在L中都有最大下界和最小上界，则称

L,≤

是一个格。常将{a，b}的最大下界记为inf{a,b}，最小上界记为sup{a,b}。2024/4/2离散数学4格的定义定义22.1.1：设L2024/4/3离散数学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离散数学5复习定义2.4.5和定义2.4.62024/4/3离散数学6几个是格的偏序集(a)(b)(c)图(a)中是一个全序集(链)，自然是一个格。不难验证，图(b)和图(c)中的偏序集中任意两个元素都有最小上界和最大下界，因而都是格。2024/4/2离散数学6几个是格的偏序集(a)(b)(c)2024/4/3离散数学7并非所有偏序集都是格不是所有的偏序集都是格。图(d),(e),(f)所表示的偏序集都不是格。不难找出它们之中存在着两个元素，或没有最小上界，或没有最大下界。(d)(e)(f)2024/4/2离散数学7并非所有偏序集都是格不是所有的偏序2024/4/3离散数学8子集格例1：设S是集合，ρ(S)是S的幂集。于是

ρ(S),

是一个格，称为S的子集格。因为：首先，ρ(S),

是一个偏序集；其次，对任意的A,B∈ρ(S)，有sup{A,B}=A∪B；inf{A,B}=A∩B。2024/4/2离散数学8子集格例1：设S是集合，ρ(S)是2024/4/3离散数学9整除格例2：设Z+是所有自然数的集合。|是Z+上的整除关系。于是

Z+,|是一个格，称为整除格。因为首先，Z+,|是一个偏序集；其次，对任意的m,n∈Z+，有sup{m,n}=[m,n](最小公倍数)；inf{m,n}=(m,n)(最大公约数)。2024/4/2离散数学9整除格例2：设Z+是所有自然数的集2024/4/3离散数学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离散数学10子群格例1：设G是群，S(G)表2024/4/3离散数学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离散数学11子格定义22.1.2：设L,2024/4/3离散数学12整除格的子格例4：设n是正整数，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离散数学12整除格的子格例4：设n是正整数，2024/4/3离散数学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。格就是具有以上性质的二元运算的代数系统。2024/4/2离散数学13格中的运算格中的inf和sup实2024/4/3离散数学14从代数系统来定义格定义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。则称代数系统L,×,

是一个格。

L,≤称为偏序格，L,×,

称为代数格。2024/4/2离散数学14从代数系统来定义格定义22.1.2024/4/3离散数学15代数格的例子例5：设S是集合，于是ρ(S),∩,∪是一个代数格。例6：设Z+是自然数集合。定义运算×和

为：m×n=(m,n)(最大公约数)，mn=[m,n](最小公倍数)。则Z+,×,是一个代数格。2024/4/2离散数学15代数格的例子例5：设S是集合，于2024/4/3离散数学16代数格和偏序格是等价的定理22.1.1：偏序格必是代数格，反之亦然。证明：设

L,≤是偏序格，对a,b∈L，令a×b=inf{a,b}ab=sup{a,b}。显然，×和是L上的封闭运算。由前面的讨论可知×和满足交换律、结合律和吸收律，因此L,×,是一个代数格。下证代数格L,×,必是偏序格。为此，需要证明：(1)L是偏序集；(2)对a,b∈L，inf{a,b}和sup{a,b}都存在。2024/4/2离散数学16代数格和偏序格是等价的定理22.2024/4/3离散数学17代数格和偏序格是等价的定理22.1.1：偏序格必是代数格，反之亦然。证明：先证代数格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离散数学17代数格和偏序格是等价的定理22.2024/4/3离散数学18注意：定义“≤”，a≤b当且仅当a×b=a定理22.1.1：偏序格必是代数格，反之亦然。证明：下证

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}。总之，代数格必是偏序格。由定理可知，互为等价的两个格

L,≤和L,×,，其运算×,可以分别是在偏序关系≤下，两个运算对象的最大下界和最小上界。2024/4/2离散数学18注意：定义“≤”，a≤b当且仅2024/4/3离散数学19代数格的子格定义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。这说明，偏序格的子格和代数格的子格的定义是有区别的。2024/4/2离散数学19代数格的子格定义22.1.4：若2024/4/3离散数学20§22.2格的性质2024/4/2离散数学20§22.2格的性质2024/4/3离散数学21偏序关系与运算我们知道，偏序格

L,≤是等价于代数格L,×,，其中对任意a,b∈L，a×b=inf{a,b},ab=sup{a,b}。从偏序格与代数格等价性的证明中可看到，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离散数学21偏序关系与运算我们知道，偏序格2024/4/3离散数学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离散数学22格中的运算保偏序关系定理22.22024/4/3离散数学23分配不等式在环和域中，加法和乘法这两种运算是通过乘法对加法的分配律联系起来的。那么，在格中的两种运算是否也存在分配律呢？一般来说，在格中的两种运算中分配律是不成立的，倒是存在两个分配律的不等式。定理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离散数学23分配不等式在环和域中，加法和乘法2024/4/3离散数学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离散数学24模不等式定理22.2.4：设L2024/4/3离散数学25格的同态定义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的格同态。特别，L到L的格同态称为格的自同态；若f是双射，则称f是格同构，并称L与S是同构的。2024/4/2离散数学25格的同态定义22.2.1设L2024/4/3离散数学26

保序映射定理22.2.5设

L,×,和S,∧,∨是两个格，它们分别对应偏序关系≤L和≤S，f是L到S的格同态。于是，对任意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)。此定理说明，同态映射必是保序映射，但反之不然。2024/4/2离散数学262024/4/3离散数学27

保序映射不一定是同态映射例子：已知

S12,|

和S12,≤

是两个格，其中“≤”是普通的小于等于关系。设它们分别对应代数格S12,×,

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

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

现定义恒等映射g(a)=a,a∈S12,则g是

S12,|

到S12,≤

的保序映射，但不是同态映射，例如：g(23)=g(6)=6，而g(2)∨g(3)=2∨3=32024/4/2离散数学27保序映射不一定是同态映射例子2024/4/3离散数学28

自同态像是代数子格定理22.2.6设

L,×,是一个格，g是L的自同态，于是，g(L)是L的代数子格。证明：任取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,×,的代数子格。2024/4/2离散数学28自同态像是代数子2024/4/3离散数学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离散数学29格同构的逆也是格2024/4/3离散数学30n维格设L={0，1}，规定0≤0，0≤1，1≤1，于是〈L,≤〉是一个格。令：

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

规定<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,≤〉等价的代数格易证，对任意<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离散数学302024/4/3离散数学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的双射。下证同态性：任取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离散数学31与n维格同构的例例1：设S={x2024/4/3离散数学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离散数学32与n维格同构的例…2024/4/3离散数学33§22.3几种特殊的格2024/4/2离散数学33§22.3几种特殊的格2024/4/3离散数学34

最小上界与最大下界的推广命题22.3.1设

L,≤是一个格，于是，L的任何非空有限子集S都有一个最小上界和最大下界。证明：对S中元素个数作归纳证明。设|S|=n，n≧1。

n=1时，结论显然成立。假设|S|=n-1时，结论成立。

2024/4/2离散数学34最小上界与最大下界的推广命2024/4/3离散数学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离散数学35|S|=n＞1时,设S={a1,2024/4/3离散数学36

格的无限子集不一定有最小上界或最大下界通常将子集S的最小上界记为supS,最大下界记为infS。注意：一个格的无限子集不一定有最小上界或最大下界。例如,在格〈Z+,≤〉中,令所有正奇数作成的集合为D+，于是D+Z+，但D+没有最小上界。2024/4/2离散数学36格的无限子集不一2024/4/3离散数学37

有界格定义22.3.1设

L,≤是一个格，若L有最小元素（记为0）和最大元素（记为1），则称L为有界格。有时，将有界格L,≤的等价代数格记为L,×，，0，1，其中0和1称为L的界。设R为实数集，L={x∈R|0≤x≤1}，则L,≤是一个有界格。2024/4/2离散数学372024/4/3离散数学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离散数学38有限格必是有界格2024/4/3离散数学39

余元素定义22.3.2设

L,≤是有界格，a,b∈L,如果a×b=0，ab=1，则称a和b互为余元素。有界格中，一个元素可能没有余元素，若有也可能不止一个。例如：ab10a和b都无余元素ab10a和b互为余元素(唯一)abc01a的余元素是b和c2024/4/2离散数学392024/4/3离散数学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离散数学402024/4/3离散数学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离散数学412024/4/3离散数学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离散数学422024/4/3离散数学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离散数学43链都是分配格a≤b或a≤c，这时2024/4/3离散数学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离散数学442024/4/3离散数学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离散数学452024/4/3离散数学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离散数学46模格的充分必要2024/4/3离散数学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离散数学47模格的充分必要2024/4/3离散数学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离散数学48模格的充分必要条件另2024/4/3离散数学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离散数学49模格的充分必要条件又由格的分配不2024/4/3离散数学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离散数学50关于分配格的一个结论定理22.32024/4/3离散数学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离散数学51有余分配格的元素的余元素唯一。推2024/4/3离散数学52§22.4布尔代数2024/4/2离散数学52§22.4布尔代数2024/4/3离散数学53

布尔代数的定义定义22.4.1有余分配格称为布尔代数。由布尔代数的定义及上一节所得的一些结论，可以将一个布尔代数记为

B,·,+,－,0,1，其中“·”称为乘法运算，“+”称为加法运算，“－”称为余运算，a∈B的余元素记为a，0，1是B的界。有时，也可将a·b简记为ab。下面根据布尔代数的定义，分类给出布尔代数的一些重要性质。2024/4/2离散数学532024/4/3离散数学54

布尔代数的性质设

B,·,+,－,0,1是一个布尔代数，于是，对任意a,b,c∈B，有：因为B,·,+是一个代数格，所以有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离散数学542024/4/3离散数学55

布尔代数的性质因为

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离散数学552024/4/3离散数学56

布尔代数的性质因为

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易证，一个具有上述性质的代数系统必是布尔代数。但上述性质不是独立的，即有些性质可以由其他性质推导出来，下面用相互独立的公理来重新定义布尔代数。2024/4/2离散数学562024/4/3离散数学57Huntington公理定理22.4.1设集合B至少含两个元素，“·”和“+”是定义在B上的两个代数运算。如果对任意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是一个布尔代数。由H1知运算有交换律，由H2知运算有分配律，由H4知B的任何元素有余元素。2024/4/2离散数学57Hunti2024/4/3离散数学58定理22.4.1的证明证明：由布尔代数的定义，我们只需证明

B,·,+是格，且0，1分别是B的最小元和最大元。由H4知，B是有余格，又由H2知，B是分配格，从而B是有余分配格，即布尔代数。首先给出几个有用的公式。(证明略)对任意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离散数学58定理22.4.1的证明证明：由布2024/4/3离散数学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离散数学59定理22.4.1的证明由H1知，2024/4/3离散数学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离散数学60定理22.4.1的证明令R=a2024/4/3离散数学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离散数学61定理22.4.1的证明再令H=a2024/4/3离散数学62定理22.4.1的证明总之，

B,·,+满足结合律。综上所述，B,·,+满足交换律、吸收律和结合律，所以是格。现定义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是布尔代数。2024/4/2离散数学62定理22.4.1的证明总之，2024/4/3离散数学63布尔代数的例例1设B={0,1}，B上的运算“·”、“+”和“－”定义如下：

·01+01xx0000010110111110

易证，

B,·

,+,－,0,1是布尔代数。这是最简单的一个布尔代数，常称为电路代数。例2设S是一个非空集合，则(S),∩,∪,－,,S是一个布尔代数，对任意A∈(S),A=S－A。称此代数为集合代数。2024/4/2离散数学63布尔代数的例例1设B={0,2024/4/3离散数学64布尔代数的例例3设P是命题公式的集合，不难证明，

P,∧,∨,,F,T是一个布尔代数,称为命题代数。例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是一个布尔代数，其中，0n=<0,…,0>∈Bn

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

。此代数称为开关代数。2024/4/2离散数学64布尔代数的例例3设P是命题公2024/4/3离散数学65子布尔代数定义22.4.2设

B,·

,+,－,0,1是一个布尔代数，SB，如果S包含元素0和1，并且对运算·

,+,－是封闭的，则S,·

,+,－,0,1称为B,·

,+,－,0,1的子布尔代数。定理22.4.2设

B,·,+,－,0,1是布尔代数，S是B的非空子集，如果S对运算{·,－}或{+,－}是封闭的，则S是B的子布尔代数。证明：设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的子布尔代数。同理可证，若S对{+,－}封闭，则S是B的子布尔代数。2024/4/2离散数学65子布尔代数定义22.4.22024/4/3离散数学66子布尔代数由子布尔代数的定义知，子布尔代数本身构成一个布尔代数。要注意的是，布尔代数B的子集S可以是布尔代数，但它可能不是B的子布尔代数，因为它对B中的运算可能不是封闭的。例5考虑如图所示的格不难验证它是一个格。令S1={a,a,0,1}，S2={a,b,0,1}，S3={a,b,0,1}。则S1是子布尔代数，因为它对{·，－}封闭；S2不是子布尔代数，因为它对运算“－”不封闭；S3是布尔代数，但不是所给代数的子布尔代数，因为它对运算“－”不封闭。2024/4/2离散数学66子布尔代数由子布尔代数的定义知，2024/4/3离散数学67一个格的图示图22.6a+ba0b1baa·b2024/4/2离散数学67一个格的图示图22.6a+ba02024/4/3离散数学68布尔代数的同态定义22.4.3设

B,·,+,－,0,1和S,∧,∨,,,是两个布尔代数，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的一个布尔同态。称f(B)是布尔代数B的同态象。如果f是双射，则称f是布尔同构，也称B与S同构。显然，f(B)是S的子布尔代数。2024/4/2离散数学68布尔代数的同态定义22.4.32024/4/3离散数学69布尔代数的同态定理22.4.3设f是布尔代数

B,·,+,－,0,1到布尔代数S,∧,∨,,,的一个映射，如果对任意a,b∈B，都有

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

则f是B到S的布尔同态。证明：对任意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的布尔同态。2024/4/2离散数学69布尔代数的同态定理22.4.32024/4/3离散数学70布尔代数的同态定理22.4.4设f是布尔代数

B,·,+,－,0,1到布尔代数S,∧,∨,,,的一个映射，如果对任意a,b∈B，都有

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

则f(B),∧,∨,,f(0),f(1)是一个布尔代数，且f是B到f(B)的布尔同态，其中是关于f(0)和f(1)的余运算。2024/4/2离散数学70布尔代数的同态定理22.4.42024/4/3离散数学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的子布尔代数。由又定理22.4.3知，f是B到f(B)的布尔同态。2024/4/2离散数学71定理22.4.4的证明证明：显然2024/4/3离散数学72§22.5有限布尔代数

的结构2024/4/2离散数学72§22.5有限布尔代数

2024/4/3离散数学73本节提到的布尔代数，如不特别指出，都是指有限布尔代数。前一节中，我们构造了一些布尔代数。人们可能想象有很大的自由来构造一些不同的布尔代数，实际上并非如此。本节将证明，每个有限布尔代数的阶必为2的正整数次幂，并且维数相同的有限布尔代数必同构。2024/4/2离散数学73本节提到的布尔代数，如不特别指出2024/4/3离散数学74n维布尔代数定义22.5.1设

B,·,+,－,0,1是布尔代数，若存在e1,…,en∈B，使得对任意a∈B，都可唯一地表示为

a=a1e1+,…,+anen

其中ai∈{0,1}，i=1,…,n。则称e1,…,en为布尔代数B的一组基底，并称此布尔代数为n维的。易知，ei≠0，i=1,…,n2024/4/2离散数学74n维布尔代数定义22.5.12024/4/3离散数学75极小元素定义22.5.2设

B,·,+,－,0,1是布尔代数，a∈B，且a≠0。若对任意x∈B，a·x=0或者a·x=a，则称a为布尔代数B的极小元素(或原子)。由定义知，有限布尔代数的极小元素就是其Hasse图中与最小元素0连结的那些元素，并且，若a和b是两个不同的极小元素，则必有a·b=02024/4/2离散数学75极小元素定义22.5.22024/4/3离散数学76布尔代数有极小元命题22.5.1设B是布尔代数，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离散数学76布尔代数有极小元命题22.5.12024/4/3离散数学77布尔代数的基底由极小元做成定理22.5.1有限布尔代数的基底必是此代数的所有极小元素；反之，有限布尔代数的所有极小元素必能做成此代数的基底。证明：设e1,…,en是有限布尔代数

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离散数学77布尔代数的基底由极小元做成定理22024/4/3离散数学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=