地六章-格和布尔代数

第六

章格与布尔代数

数学是科学的大门钥匙，忽视数学必将伤害所有的知识，因为忽视数学的人是无法了解任何其他科学乃至世界上任何其他事物的。更为严重的是，忽视数学的人不能理解他自己这一疏忽，最终将导致无法寻求任何补救的措施。

BaconRoger环与域一、环定义：设是代数系统，为集合，为二元运算，若

(1)为阿贝尔群，

(2)为半群，

(3)乘法对加法适合分配律，则称是环。

例1.

，，都是环。是环。是模的整数环，其中表示模的加法和乘法，，。

二、域定义：环满足：

(1)至少两个元素，

(2)含有幺元，

(3)是可交换的，

(4)除加法幺元外，其余元素均有逆元，则称为域。例2.

，都是域，但不是域，因为不是除0外，其余元素都有逆元。不是域，因不是可交换的。是域，但不是域(，但不存在乘法的逆元，使)令，则为域。第六

章格与布尔代数

布尔代数是一个抽象代数系统。对于它的建立可循两个途径进行：一是从抽象代数的观点出发，把布尔代数看成是特殊的格——

布尔格，使其立于现代数学的抽象代数结构之上；二是从数理逻辑观点出发，把直观布尔代数看成是形式布尔代数的标准模型，使其立于现代数学的形式化结构之上。这样两种奠基法，无疑地将加深我们对于布尔代数的数学本质的认识。

布尔（GeorgeBool，1815~1864年，英国数学家）在戴德金（Dedekind）之前就曾引出过一种特殊的格——有余分配格，这种格被称为布尔代数。历史上最初出现的格是布尔于1854年提出的，是他在研究命题演算中发现的。大体于1935年左右形成的近代格论，正是来源于逻辑、数论、代数学与几何学领域，并与其他数学分支广泛地联系着。格是伯克霍夫（Birkhoff1884~1944年）在20世纪30年代提出的，格的提出以子集为背景。格是一种特殊的偏序集，满足一定条件的偏序集称为格，同时格又可看成是具有两个二元运算的代数系统。格和布尔代数的理论成为计算机硬件设计和通讯系统设计中的重要工具。6.1格

6.1.1格的定义定义6.1对于偏序集(L，≤)的任意两个元素a、b，恒存在上确界（记为sup{a,b}）及下确界（记为inf{a,b}）时，称该偏序集为格。格是一个抽象的代数结构(代数系统)。

显然，一个全序集是一个格，但是，不是所有偏序集都是格。对于a∈L、b∈L，a、b的上确界和下确界分别用a∨b(或a

b，或a

b)和a∧b(或a

b,a.b)来表示，依次称为a,b的并和交，这是格中的两种基本运算。在下图中，给出了格的哈斯图，（a）（b）（c）下图左侧给出了不是格的哈斯图。右侧是格的实例。

不是格的偏序集格的实例【例9.1】S是任意一个集合，

(S)是S的幂集合，于是， 偏序集(

(S),

)是一个格。对

A,B∈

(S)，

sup{A,B}＝A∪B∈

(S) inf{A,B}＝A∩B∈

(S)

（a）（b）【例6.2】设I

是是个正整数集，并用D表示I

中的“除法”关系，亦即对于任何a,b∈I

，aDb当且仅当a整除b，显然，(I

,D)是一个格。其中a和b的并是a和b的最小公倍数；a和b的交是a和b的最大公因数。

【例6.3】设I+

是个正整数集，n是一个正整数，Sn

是n的所有因数的集合。例如，S6＝{1,2,3,6}，

S24＝{1,2,3,4,6,8,12,24}。设用D表示I+

中的“除法”关系，亦即对于任何a,b∈I+来说有，aDb，当且仅当a整除b。，于是，(S6,D),(S8,D),(S24,D)和(S30,D)都是格。

【例6.4】设S是所有的命题集合，定义“

”关系如下：

A

B当且仅当B蕴涵A

则(S,

)是一个格。对

A,B∈S，

sup{A,B}＝A∧B∈Sinf{A,B}＝A∨B∈S定义6.2若格L的一个子集M≠Ф对于运算

和

封闭，则M称作子格。例如：a是格L的一个固定元素，则使X≥a(或X≤a)的L中元素X的集合，显然是一个子格。若a≥b，则使a≥X≥b的L中元素X的集合是一个子格，这样的子格叫作一个闭区间(商)，记作M(a,b)。

还可以将格定义为一个代数系统，在这个代数系统中，可以定义一个偏序关系。这样就可以把与代数系统有关的许多概念应用于格。定义6.3设(L,

,

)是一个代数系统，其中L是一个集合，

,

是L上两个二元代数运算，如果若对于L中任意元素a、b、c，二元运算都满足下列条件时： 交换律：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。 则称此代数系统(L,

,

)为一个格。

定义中没有要求

,

运算满足等幂律，实际上由

,

满足吸收律即可推出它们一定满足等幂律。任取L中元素a，由

,

满足吸收律知

a

(a

a)＝a a

(a

a)＝a

故 a

a＝a

(a

(a

a)) a

a＝a

(a

(a

a))

又由

,

满足吸收律知，上面两式的等式右端都等于a。因此， a

a＝a a

a＝a 即定义6.3中的

,

运算亦满足等幂律。同样，

,

运算满足保序性。设(L,≤)是一个格，任取L中元素a,b,c,d，容易得出，

b≤c

a

b≤a

c，a

b≤a

c a≤c，b≤d

a

b≤c

d，a

b≤c

d可以看出，定义6.3给出了格的充分条件。【例6.5】设S是一个集合，

(S)是S的幂集合，集合的交∩，并∪是

(S)上的两个代数运算，于是，(

(S),∩,∪)是一个格。而由例9.1知(

(S),

)是半序格。易见对

A,B∈

(S)，有

A

B

A∩B＝AA∪B＝B【例6.6】设Z

是所有正整数集合，两个正整数的最大公因数

，最小公倍数

可看作是Z

上两个代数运算，于是，(Z

,

,

)是一个格。而由例6.2知(Z

,D)是半序格。易见，对任意a,b∈Z

，有

(a整除b)aDb

a

b＝a

a

b＝b

【例6.7】设n是一个正整数，Sn

是n的所有因数的集合，两个正整数的最大公因数

，最小公倍数

可看作是Sn

上两个代数运算，于是，(Sn,

,

)是一个格。定理6.1关于格的两种定义（定义6.1和定义6.3）是等价的。亦即，任意一个偏序格都可以对应一个代数格；任意一个代数格也都可以对应一个偏序格。证明：⑴若(L,≤)是一个格，则对任意a,b∈L，记 inf{a,b}为a

b；sup{a,b}为a

b。 由于对任意a,b，其inf{a,b}，sup{a,b}

是唯一的，所以，如上定义的

,

是集合L上的两种二元代数运算。不难证明，对于

,

满足交换律，结合律，吸收律。只证明吸收律：a

(a

b)＝a，其它算律的证明留给读者。因为a

(a

b)是a与(a

b)的最大下界，所以a

(a

b)≤a；

另一方面，由于a≤a，a≤a

b，所以，a是a与a

b的下界， 故a≤a

(a

b)，故a＝a

(a

b)。 因此，根据定义6.3，(L,

,

)是一个格。⑵若代数系统(L,

,

)是一个格，在集合L上定义一个关系≤如下：对任意a,b∈L，a≤b

a

b＝a

求证≤是一个偏序关系。 因为a

a＝a

(a

(a

a))＝a，所以有a≤a。 若有a≤b，b≤a，则应有a

b＝a，b

a＝b，而a

b＝b

a，所以a＝b。 若a≤b，b≤c，则有a

b＝a，b

c＝b， 故a

c＝(a

b)

c＝a

(b

c)＝a

b＝a， 亦即，有a≤c。

由此证明了关系≤具有反身性，反对称性，传递性。故≤是偏序关系。不难证明：a

b＝a

a

b＝b。若a

b＝a，则a

b＝(a

b)

b＝b。若a

b＝b，则a

b＝a

(a

b)＝a。因此，对任意a,b∈L，a≤b

a

b＝b。下面证明，对任意{a,b}⊆L，存在inf{a,b}，sup{a,b}， 就此结束定理的证明。由吸收律知

a

(a

b)＝a，b

(a

b)＝b故有a≤(a

b)，b≤(a

b)。 亦即，a

b是{a,b}的上界。若c∈L，且c是{a,b}的上界，亦即a≤c,b≤c，则有a

c＝c,b

c＝c，于是，

(a

b)

c＝(a

b)

(c

c)＝(a

c)

(b

c)＝c

c＝c故有(a

b)≤c。这就说明了(a

b)是{a,b}的最小上界，即sup{a,b}＝(a

b)。同理可证，inf{a,b}＝(a

b)。 证毕

故(L,≤)称为半序格，(L,

,

)称为代数格。由此定理知，给出一个半序格(L,≤)，就有一个与之等价的代数格(L,

,

)。反之，给出一个代数格(L,

,

)，就有一个与之等价的半序格(L,≤)。 互为等价的两个格：(L,≤)和(L,

,

)，其

,

分别是在偏序关系≤下的最大下界运算和最小上界运算。 基于上述结果，我们对偏序格和代数格不从概念上加以区分，而统一将它们称为格，当提及一个格时，既可以将其理解为偏序格，也可以将其理解为代数格。

定义6.4设(L,

,

)是一个格，S是L的一个子集，(S,

,

)称为(L,

,

)的一个子格，当且仅当在运算

,

下，S是封闭的。显然，子格是一个格。例如，(Sn,

,

)是(Z

,

,

)的子格，其中

,

分别是最大公因数和最小公倍数。从定义6.4不难说明，若(L,

,

)是一个格，S⊆L，并且(S,

,

)也是格，则(S,

,

)是(L,

,

)的子格。亦即：(S,

,

)是格(L,

,

)的子格的充要条件是：S⊆L且(S,

,

)是一个格。

最后指出一点：设(L,≤)是一个格，与其等价的代数格为(L,

,

)，S是L的一个子集。若(S,≤)是定义6.4下的(L,

,

)的子格，则显然，(S,≤)是定义6.2下的(L,≤)的子格；若(S,≤)是定义6.2下的(L,≤)的子格，则(S,

,

)不一定是定义6.4下的(L,

,

)的子格。下面给出与格相关的重要概念和事实。一个元的格是显见的。两个元的格即B＝{0,1}，三个元的格仅有一种，四个元的格有两种，五个元的格有五种，六个元的格有十五种……，它们中的部分哈斯图如下图所示：

一元格二元格三元格四元格

五元格

一元格、二元格、三元格、四元格、五元格的哈斯图

定义6.5若一个格的集合的每一个非空子集，都含有一个上确界和一个下确界，则称此种格是完全格。例如：任一集的所有子集的集合与包含关系构成的格是完全格，有理数与数的大小关系构成的格不是完全格。由定义可知，每一个完全格都必定有一个最大元素和一个最小元素。

定义6.6由有限元素所作成的格，称为有限格。在有限格的图示中，不出现以三个元素为顶点并且边上不含其他元素的三角形。显然每一个有限格必定是完全格。

6.1.2格的性质

1.对偶原理设有两个格(L,≤)和(L,≥)，

和

是其中的并与交运算，若用

取代

，用

代替

；用≥取代≤，用≤取代≥，则关于格(L,≤)和(L,≥)的任何命题，都仍归保持有效。这就是格的对偶性原理，这个对偶性原理说明：如同关系≤和≥互为对偶一样，运算

和

也互为对偶；类似地得到，格(L,≤)和(L,≥)也互为对偶。从格的定义可知，格的对偶仍是格，即格的概念是自对偶的。对有限格，互相对对偶的格的哈斯图正好上下颠倒。下面我们将对这一原理进行详细阐述。

定义6.7集合L中的偏序关系R与其逆关系R

1，称为互相对偶的两个关系。对任意x,y∈L，xR

1y

yRx。

6.1.1节例6.4中的

关系即为蕴涵关系

的逆关系。因此，对任意P,Q∈S，

(P

Q)

(Q

P)命题6.1若R是偏序关系，则R

1也是偏序关系。证明：因为对任意x∈L，xRx，因此有xR

1x。故R

1满足反身性。 若xR

1y，yR

1x，则有yRx，xRy，因此，x＝y。故R

1

满足反对称性。 若xR

1y，yR

1z，则有yRx，zRy，因此，zRx，即xR

1z。故R

1满足传递性。命题6.2(L,R)中sup{a,b}＝d

(L,R

1)

中inf{a,b}＝d(L,R)中inf{a,b}＝d

(L,R

1)

中sup{a,b}＝d

该结论的证明留给读者作为练习。 显然，对于L的任意子集A，A在偏序集(L,R)中的最小上界就是A在偏序集(L,R

1)中的最大下界，A在(L,R)中的最大下界就是A在(L,R

1)中的最小上界。因此有：

命题6.3如果偏序集(L,R)是格，则偏序集(L,R

1)也是格，反之亦然。设格(L,R)是有最小元素0，最大元素1的格。格(L,R)与格(L,R

1)称为互相对偶的两个格。定义6.8格(L,R)中的表达式是由如下规则生成的符号串：

(1)0,1及变量X是表达式，X可以是L中任意元素，0,1分别是(L,R)中最小、最大元素。

(2)若A,B是表达式，则(A

B),(A

B)是表达式，其中

,

分别是格(L,R)中的最小上界和最大下界运算。

(3)格(L,R)中所有表达式，都是有限次使用⑴、⑵生成的符号串。定义6.9设(L,R)是一个格。(L,R)中的最小上界和最大下界运算分别为

1,

1；(L,R

1)中的最小上界和最大下界运算分别为

2,

2；E是格(L,R)中一个表达式。如果将E中

1

换为

2，

1

换为

2，将所得的格(L,R

1)中的表达式记为E*，则称E*为E在其对偶格中的对偶表达式。定义6.10设(L,R)是一个格，其中最小上界和最大下界运算分别为

,

,E是格(L,R)中的表达式。如果将E中的

换为

，

换为

，0换为1（当E中有0时），1换为0（当E中有1时），所得的表达式记为E*，则称E*为E之对偶表达式。引理6.1若XRY在格(L,R)中成立，则Y*R

1X*在对偶格(L,R

1)中成立，其中X*,Y*分别是表达式X,Y的在对偶格中的对偶表达式。证明：因为对任意a,b∈L，都有

a

1b＝a

2b a

1b＝a

2b

所以，将X,Y,X*,Y*中每一变量都以L中任意元素代替，得X0,Y0,X0*,Y0*，有

X0*＝X0，Y0*＝Y0

故有X0*RY0*，即有Y0*R

1X0*。由于代入变量的元素的任意性，故有Y*R

1X*。定理6.2对偶原理1若XRY在格(L,R)中成立，则Y*RX*也在此格中成立，其中表达式X*,Y*分别是表达式X,Y的对偶表达式。证明：因为XRY在(L,R)中成立，所以X’R

1Y’

在(L,R

1)中成立，其中X’’,Y’’

分别是将X,Y中的

1

换为

2，

1

换为

2，0换为1（当X或Y中有0时），1换为0（当X或Y中有1时）所得之表达式。由引理6.1知，(Y’)*R(X’)*在(L,R)中成立，其中(Y’)*,(X’)*分别是,在其对偶格中的对偶表达式。 由X’,Y’,(X’)*,(Y’)*的定义知：

(X’)*＝X*,(Y’)*＝Y*， 其中X*,Y*分别是X,Y的对偶表达式。 故Y*RX*在(L,R)中成立。

将格看作一种代数系统，我们知道，这个代数的公理系统是对偶的。亦即，对于该系统的每一条公理，其对偶表达式组成的等式也是该系统的公理。所以，在格中利用公理推导出的一切结论都应该是对偶的。也就是说，如果从格的公理H1,H2,…,Hm

演绎出结论C，即C在格中成立，那么将此演绎的每一步中，凡是使用公理Hi(i＝1,2,…,m)的地方，都换成对偶公理Hi*(i＝1,2,…,m)，于是演绎出的结论就是C的对偶关系式C*，即C*在格中也成立。所谓C的对偶关系是指将C中的表达式换为对偶表达式，C中的关系换为对偶关系所得的关系式。例如：在格中等幂律是成立的。

a

a＝a

(a

(a

a))＝a对偶地可得：

a

a＝a

(a

(a

a))＝a

所以，如果在格L中，加入某一个条件G，而能得出一个结论C，那么将G看作是格中一条新的公理，把G的对偶关系式G*也作为新公理加到格中，于是C的对偶关系式C*，在格中，在条件G*下也应该成立。因此，下面的对偶原理是成立的。定理6.3对偶原理2在格(L,R)中，若在条件HRG下，有XRY，则在对偶条件H*R

1G*下，有X*R

1Y*。其中H*,G*,X*,Y*分别是H,G,X,Y的对偶表达式。 证明略。2.格的其它性质定理6.4设(L,≤)是一个格，a,b是L中任意元素，于是 a≤b

a

b＝a

a

b＝b证明：若a≤b，因为a≤a，所以a是{a,b}的下界， 故a≤a

b。 而a

b是{a,b}的最大下界，所以a

b≤a。 故a

b＝a。 若a

b＝a，由吸收律知a

b＝(a

b)

b＝b， 若a

b＝b，由a

b的定义知，b是{a,b}的最小上界，当然有a≤b。定理6.5设(L,≤)是一个格，a,b,c是L中任意元素，如果b≤c，则有

a

b≤a

c a

b≤a

c证明：因为b≤c，所以由定理6.4知b

c＝b，又因为

(a

b)

(a

c)＝(a

a)

(b

c)＝a

(b

c)＝a

b

再由定理9.3知：a

b≤a

c。 同理可证得第二个不等式。定理6.6设(L,≤)是一个格，a,b,c是L中任意元素。于是有a

(b

c)≤(a

b)

(a

c) a

(b

c)≥(a

b)

(a

c)

其中关系“≥”是关系“≤”的对偶关系。证明：因为a≤a

b，a≤a

c，所以，由

的定义知

a≤(a

b)

(a

c)(6.1)

又因为b

c≤b≤a

b,b

c≤c≤a

c

所以，再由

的定义知

b

c≤(a

b)

(a

c)(6.2)

由

的定义及(9.1),(9.2)式知

a

(b

c)≤(a

b)

(a

c)

对偶地可证得另一不等式。注意，在一般格中，分配律不是总成立的，但上述分配不等式总是成立的。定理6.7设(L,≤)是一个格，a,b,c是L中任意元素，于是，a≤b

a

(b

c)≤b

(a

c)证明：若a≤b，则由定理6.4知：a

b＝b。由定理6.6知

a

(b

c)≤(a

b)

(a

c)＝b

(a

c)

若a

(b

c)≤b

(a

c)，则由

的定义知

a

(b

c)≥a

由

的定义知

b

(a

c)≤b

故a≤b。6.1.3格的同态与同构定义6.11设(L,

,

)和(S,∧,∨)是两个格，L到S内的映射g称为(L,

,

)到(S,∧,∨)的格同态映射，如果对任意a,b∈L，都有

g(a

b)＝g(a)∧g(b) g(a

b)＝g(a)∨g(b)

格L到L内的同态映射称为格的自同态映射。若g是L到S上的同态映射，且是一对一的，则称g是格同构映射，并称格L与格S是同构的。显然，若g是格L到格S上的同构映射，则必定存在S到L上的g的逆映射g

1，并且对L中任意元素х，S中任意元素y，都有

g

1(g(х))＝х,g(g

1(y))＝y【例6.8】设S＝{a,b}，

(S)＝{Φ,{a},{b},{a,b}}是S的幂集合，则(

(S),∩,∪)是一个格。证明：设L＝{0,1}，规定0≤1，∧,∨分别是集合L中两个元素在≤下的最大下界，最小上界运算，则(L,∧,∨)是一个格。规定映射g为：

g({a})＝1,g({a,b})＝1,g({b})＝0,g(Φ)＝0

则显然g是

(S)到L上的映射，求证g是同态映射。 首先证对任意A,B∈

(S)，g(A∩B)＝g(A)∧g(B)

（1）若a∈A∩B，则a∈A，a∈B，故

g(A∩B)＝1,g(A)∧g(B)＝1∧1＝1 （2）若a

A∩B，则 g(A∩B)＝0,1∧0＝0a∈A,a

B g(A)∧g(B)＝0∧1＝0 a

A,a∈B 0∧0＝0a

A,a

B

综上，g(A∩B)＝g(A)∧g(B)。再证对任意A,B∈

(S)，g(A∪B)＝g(A)∨g(B)

（1）若a∈A∪B，则g(A∪B)＝1,1∨0＝1a∈A,a

Bg(A)∨g(B)＝0∨1＝1a

A,a∈B1∨1＝1a∈A,a∈B

（2）若a

A∪B，则a

A，a

B，故

g(A∪B)＝0,g(A)∨g(B)＝0∨0＝0。 综上，g(A∪B)＝g(A)∨g(B)。 因此，g是

(S)到L上的同态映射。【例6.9】设S＝{a,b}，

(S)＝{Φ,{a},{b},{a,b}}是S的幂集合，则(

(S),∩,∪)是一个格。证明：规定映射g为：

g(Φ)＝g({a})＝Φ，g({b})＝g({a,b})＝{b}

显然，g为

(S)到

(S)内的映射。求证g是同态映射。 不难验证对任意A,B∈

(S)，有： 若b∈A∪B，则g(A∪B)＝g(A)∪g(B)＝{b}； 若b

A∪B，则g(A∪B)＝g(A)∪g(B)＝Φ。 若b∈A∩B，则g(A∩B)＝g(A)∩g(B)＝{b}； 若b

A∩B，则g(A∩B)＝g(A)∩g(B)＝Φ。 因此，g(A∪B)＝g(A)∪g(B)，

g(A∩B)＝g(A)∩g(B)。g为此格的自同态映射。【例6.10】设S＝{a,b,c}，则

(S)＝{Φ,{a},{b},{c},{a,b},{b,c},{a,b,c}}是S的幂集合，则(

(S),∩,∪)是一个格。证明：设S30是30的所有正因数的集合，

,

分别是求两个正整数的最大公因数、最小公倍数，则(S30,

,

)是一个格。规定映射g为：

Φ

1,{a}

2,{b}

3,{c}

5,{a,b}

6, {a,c}

10,{b,c}

15,{a,b,c}

30

则显然g为

(S)到S30上的1－1映射。不难验证对任意A,B∈

(S)，有：

g(A∪B)＝g(A)

g(B),g(A∩B)＝g(A)

g(B)

因此，g为

(S)到S30上的同构映射。且g

1是S30到

(S)上的同构映射，有：

g

1(g(х))＝х,x∈

(S)g(g

1(y))＝y,y∈S30定理6.8设(L,

,

)和(S,∧,∨)是两个格。集合L上对应于运算

,

的偏序为≤L，集合S上对应于运算∧,∨的偏序为≤S。如果g是L到S内的同态映射，则g是保序映射，亦即，对任意a,b∈L，若a≤Lb，则g(a)≤Sg(b)。证明：因为a≤b

a

b＝a，所以g(a

b)＝g(a)，而

g(a

b)＝g(a)∧g(b)＝g(a)

故g(a)≤Sg(b)。定理6.9设(L,

,

)是一个格，g是此格的自同态映射，于是g(L)是(L,

,

)的子格（定义6.2）。证明：任取g(L)中两个元素a’,b’

。于是a’,b’

一定是L中某两个元素a,b在g下的映像。亦即，

a’＝g(a),b’＝g(b)

因为g是格(L,

,

)的自同态映射，所以

a’b’＝g(a)

g(b)＝g(a

b)∈g(L) a’b’＝g(a)

g(b)＝g(a

b)∈g(L)

即在运算

,

下，g(L)是封闭的。 故(g(L),

,

)是(L,

,

)的子格。定理6.10设(L,

,

)，(S,∧,∨)是两个格，若g是L到S上的同构映射，则g的逆映射g

1是S到L上的同构映射。 证明：显然g

1是S到L上的一对一映射。 下面证明g

1是S到L上的同态映射。 任取a’,b’∈S，令g

1(a’)＝a,g

1(b’)＝b。于是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(g(a)∨g(b))

＝g

1(g(a

b))

＝a

b＝g

1(a’)

g

1(b’)

故g

1是S到L上的同构映射。推论6.1若格(L,

,

)和格(S,∧,∨)同构，g是其同构映射，则对L中任意两个元素a,b，有

a≤Lb

g(a)≤Sg(b)

其中≤L,≤S分别是集合L,S上对应于运算

,∧的偏序关系。 此推论的证明留给读者。

取L＝{0,1}，规定0≤1。于是，不难看出(L,≤)是一个格，并且令(L,∧,∨)是与之等价的代数格，则∧,∨分别是集合L中两个元素的最大下界，最小上界运算。令Ln＝{(a1,a2,…,an)∣ai∈L,i＝1,2,…,n}

规定：(a1,a2,…,an)≤n(b1,b2,…,bn)

ai≤bi

(i＝1,2,…,n)

指出一点，对于格的一个无穷子集，引理6.2的结论不成立。例如，在格(Z

,≤)中，所有正偶数组成的集合记为E

，显然，E

⊆Z

，但E

没有最小上界。于是，不难证明：(Ln,≤n)是一个格，通常称为n维格。令与(Ln,≤n)等价的代数格为(Ln,

,

)，对Ln中任意两个元素(a1,a2,…,an),(b1,b2,…,bn)，显然有

(a1,a2,…,an)

(b1,b2,…,bn)＝(a1∧b1,a2∧b2,…,an∧bn)(a1,a2,…,an)

(b1,b2,…,bn)＝(a1∨b1,a2∨b2,…,an∨bn)【例6.11】设S是含n个元素的集合，

(S)是S的幂集合，于是，格(

(S),⊆)与格(Ln,≤n)同构。证明：令S＝{s1,s2,…,sn}。令g是

(S)到Ln上的映射如下：任取A∈

(S)，

g(A)＝(a1,a2,…,an)

其中ai＝1

si∈A，i＝1,2,…,n。显然，g是

(S)到Ln上的一对一映射。任取A,B∈

(S)，令g(A)＝(a1,a2,…,an)，

g(B)＝(b1,b2,…,bn)，

g(A∩B)＝(c1,c2,…,cn)，于是由g的定义知：

ai＝1

si∈A，i＝1,2,…,n bi＝1

si∈B，i＝1,2,…,n ci＝1

si∈A∩B，i＝1,2,…,n于是，不难看出：

ci＝1

ai＝1同时bi＝1，i＝1,2,…,n因此，ci＝ai∧bi，故

(c1,c2,…,cn)＝(a1∧b1,a2∧b2,…,an∧bn)

＝(a1,a2,…,an)

(b1,b2,…,bn)

即，g(A∩B)＝g(A)

g(B)。同理可证得：g(A∪B)＝g(A)

(B)。故(

(S),∩,∪)与(Ln,

,

)同构。1.有界格在一个格里，任意一对元素都有一个最大下界和一个最小上界，推广这个事实。引理6.2设(L,≤)是一个格。若S是L的任意一个有限非空子集，则S有一个最大下界和一个最小上界。 证明留给读者。记集合S的最大下界为infS；集合S的最小上界为supS。6.1.4几种特殊的格定义6.12在格(L,≤)中，若存在最大元素和最小元素，通常称之为格的域界或界，并分别记作1和0。若一个格有域界1和0，则称此种格为有界格。设：(L,

,

,0,1)是一个有界格，根据依定义6.12，对于所有的a∈L有a≤1和a≥0。显然得到有界格的如下性质：引理6.3在有界格(L,

,

,0,1)中，对于所有的a∈L，都有如下恒等式成立：

a

0＝a，a

1＝a a

1＝1，a

0＝0

另外，在一个有界格中，1和0是互为对偶的，因此根据对偶性原理也可以交换1和0。定义6.13在有界格(L,

,

,0,1)中，若元素a、b∈L，且有

a

b＝0，a

b＝1

则称元素a和元素b互为余元素或余。A的余元素通常用a’

或来表示。任意元素a可以有余元素，也可以没有余元素；如果有余元素，则可以有一个或一个以上的余元素。由引理6.3可知0和1互为余元素。引理6.4在有界格(L,

,

,0,1)中，1是0的唯一余元素，0也是1的唯一余元素。证明：因为由引理6.3知，

0

1＝0，0

1＝1

所以，0,1互为余元素。 若c∈L，且c≠1，c是0的余元素，

0

c＝0，0

c＝1

但是，由引理6.3知，

0

c＝c

故c＝1。因而由c≠1导至一个矛盾，故1是0的唯一余元素。 同理可证0也是1的唯一余元素。2.有余格定义6.14对于有界格(L,

,

,0,1)，若L中每一个元素，都至少有一个余元素，则称(L,

,

,0,1)是一个有余格。【例6.12】n维格(Ln,≤n)是一个有余格，其中1n＝(1,1,…,1)，0n＝(0,0,…,0)是界。对任意Ln中元素(a1,a2,…,an)，元素(b1,b2,…,bn)是其余元素，其中

bi＝0

ai＝1i＝1,2,…,nbi＝1

ai＝0i＝1,2,…,n

【例6.13】设S是一个集合，

(S)是它的幂集。只要S有n个元素，(

(S),

)就是有余格。它的域界是Φ和S。其中S的任何子集A的余是集合S

A。显然，构成有余格的必要条件是此格是个有界格，但这条件并不是充分的。在下图所示的一些格，格中的某些元素的余元如下：（a）（b）（c）

有余格

图(a)所示的元素a1

的余元是a2；图(b)所示的b1

的余元是b2

和b3，

b2

的余元是b1

和b3，b3

的余元是b1

和b2；图(c)所示的格中a1

的余元是a2

和a3，等等。111000a1a2a1a2a3b1b2b33.分配格分配格是另一种特殊的格。由6.1节中定理6.6知，对于任意格，其格中元素都满足分配不等式，下面我们引进一种满足分配恒等式的特殊格。定义6.15设(L,

,

)是一个格，若对于任意a,b,c∈L，恒有

a

(b

c)＝(a

b)

(a

c) a

(b

c)＝(a

b)

(a

c)

则称(L,

,

)是一个分配格。

不是所有的格都是分配格，例如，图9.4中的一元格、二元格、三元格是分配格，四元格、五元格不是分配格。应当指出：在分配格定义中的两个等式是互为等价的。因此，对于格的各元素的所有可能组合，证明这两个恒等式之一就够了。下面给出构成分配格的定理及其基本性质。引理6.5任意一个链都是一个分配格。证明：设格(L,≤)是一个链，任取L中三个元素a,b,c，试考察下列两种情况：

(1)a≥b，a≥c，于是a≥b

c， 故

a

(b

c)＝b

c

而 a

b＝b，a

c＝c，所以

(a

b)

(a

c)＝b

c

故 a

(b

c)＝(a

b)

(a

c)。

(2)a≤b或者a≤c，于是a≤(b

c)， 故 a

b(b

c)＝a。 而 (a

b)

(a

c)＝a

所以 a

(b

c)＝(a

b)

(a

c)。

也有很多不是链的格是分配格。例如，n维格(Ln,≤n)，格(

(S),)，格(Z

,D)，格(Sn,D)都是分配格。 注意，分配格的任何子格也是分配格，而且对于所有分配格而言对偶性原理全都有效。定理6.11德·摩根（DeMorgan）定律设(L,

,

)是一个分配格，对任意元素a,b，若a,b有余元素a’,b’

，则(ab)’

＝a’

b’(ab)＝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)

＝(0

b)

(0

a)

＝0

0＝0

故由余元素定义知，(ab)’＝a’

b’

同理可证另一等式。定理6.12设格(L,,)是分配格，对任意a,b,c∈L，如果

a

c＝b

c，a

c＝b

c

则有 a＝b。证明：若(L,,)是分配格， 且a

c＝b

c，a

c＝b

c，则

a＝a(a

c)＝a(b

c)

＝(a

b)(a

c)

＝(a

b)(b

c)＝b(a

c)

＝b(b

c)＝b

推论6.2设格(L,

,

)是一个有余分配格，则对任意a∈L，a的余元素是唯一的。证明：因(L,

,

)是有余格，设和都是a的余元素，即

aa’＝0，aa’＝1 aa’’＝0，aa’’＝1

故aa’＝aa’’，aa’＝aa’’。 由定理9.5知，a’＝a’’。6.2布尔代数6.2.1布尔代数的定义定义6.17一个有余分配格是一个布尔代数。 有余格仅保证了余的普遍性(即每一个元素皆至少有一个余元)，但不保证余的唯一性(即对于同一个元素可能有多个余元)；而分配格仅保证了余的唯一性，但不保证余的普遍性；只是在有余分配格中，才吸取了以上两者的特点，既保证了余元的普遍性又保证了它的唯一性。

布尔代数首先是一个格，是个特殊的格(布尔格)，其特殊性表现在三个方面，即有界性，有余性和可分配性。另外显见，在集合B中存在一个偏序关系≤，同时因布尔代数是个有余分配格，故前述的关于有余格、分配格的性质在其中皆成立，亦即为布尔代数的一般性质。 因为布尔代数是一个格，今后将布尔代数中的运算

简记为•，称为乘法。运算

简记为

，称为加法。因为布尔代数是有