第 7章 格和布尔代数第 7章 格和布尔代数
7.1 格与子格
7.2 特殊格
7.3 布尔代数
7.4 例题选解习 题 七第 7章 格和布尔代数
7.1 格与子格本章将讨论另外两种代数系统 —— 格与布尔代数,
它们与群,环,域的基本不同之处是：格与布尔代数的基集都是一个有序集 。 这一序关系的建立及其与代数运算之间的关系是介绍的要点 。 格是具有两个二元运算的代数系统,它是一个特殊的偏序集,而布尔代数则是一个特殊的格 。
第 7章 格和布尔代数图 7.1.1
a b
c
d
e f
第 7章 格和布尔代数在第四章,对偏序集的任一子集可引入上确界 （ 最小上界 ） 和下确界 （ 最大下界 ） 的概念,但并非每个子集都有上确界或下确界,例如在图 7.1.1中哈斯图所示的有序集里,{a,b}没有上确界,{e,f}没有下确界 。
不过,当某子集的上,下确界存在时,这个上,下确界是唯一确定的 。
第 7章 格和布尔代数定义 7.1.1 如果偏序集 〈 L 〉 中的任何两个元素的子集都有上确界和下确界,则称偏序集 〈 L 〉 为格（ lattice）。
虽然偏序集合的任何子集的上确界,下确界并不一定都存在,但存在,则必唯一,而格定义保证了上确界,下确界的存在性 。 因此我们通常用 a∨ b表示 {a，
b}的上确界,用 a∧ b表示 {a,b}的下确界,
第 7章 格和布尔代数图 7.1.2
b
a
a b
( a ) ( b ) ( c )
( d ) ( e )
第 7章 格和布尔代数并记作 a∨ b=LUB{a,b}
（ Leastupperbound）,a∧ b=GLB{a,b}(Greatestlowerbou
nd),∨ 和 ∧ 分别称为并（ join）和交（ meet）运算。由于对任何 a,b,a∨ b及 a∧ b都是 L中确定的成员，因此
∨,∧ 均为 L上的二元运算。由定义知道，并非所有的偏序集都能构成格，我们用 Hasse图表示偏序集，图
7.1.2中哪个能构成格？
图 7.1.2中哈斯图 （ a）,（ b）,（ c） 所规定的偏序集是格,图 （ d）,（ e)及图 7.1.1所规定的偏序集不是格,因为图中 {a,b}无上确界 。
第 7章 格和布尔代数
【 例 7.1.1】
（ 1） 对任意集合 S,偏序集 〈 P（ S）,〉 为格,
其中并,交运算即为集合的并,交运算,即
B∨ C＝ B∪ C B∧ C＝ B∩C
封闭于 P(S),这里 B,C∈ P(S)。
（ 2） 设 L为命题公式集合,逻辑蕴涵关系,,为
L上的偏序关系 （ 指定逻辑等价关系,,为相等关系 ）,那么,〈 L,〉 为格,对任何命题公式 A,B，
A∨ B=A∨ B,A∧ B=A∧ B（ 等式右边的 ∨,∧ 为析取与合取逻辑运算符 ） 。
第 7章 格和布尔代数
（ 3）设 Z+表示正整数集,|表示 Z+上整除关系，那么 〈 Z+,|〉 为格，其中并、交运算即为求两正整数最小公倍数和最大公约数的运算，即
m∨ n＝ LCM（ m,n） m∧ n＝ gcd（ m,n）
另外,若将 〈 L,〉 中的小于等于关系换成大于等
,即对于 L中任何两个元素 a,b定义 a b的充分必要条件是 b a,则 〈 L,〉 也是偏序集 。 我们把偏序集 〈 L,〉 和 〈 L,〉 称为是相互对偶的 。 并且它们所对应的哈斯图是互为颠倒的 。 关于格我们有同样的性质 。
第 7章 格和布尔代数定理 7.1.1 若 〈 L,〉 是一个格,则 〈 L,〉 也是一个格,且它的并,交运算 ∨ r,∧ r对任意 a,b∈ L满足
a∨ rb=a∧ b a∧ rb=a∨ b
于是,我们有下列对偶原理 。
第 7章 格和布尔代数定理 7.1.2 如果命题 P在任意格 〈 L,〉 上成立,
则将 L中符号 ∨,∧,∧,∨,
公式 P*在任意格 〈 L,〉 上也成立,这里 P*称为 P的对偶式 。
在上述对偶原理中,,如果命题 P在任意格
〈 L,〉 上成立,的含义是指当命题 P中的变量取值于
L中,且上确界运算为 ∨,下确界运算为 ∧,则 P对于它们也成立 。 现在我们深入地讨论格的性质 。
第 7章 格和布尔代数定理 7.1.3 设 〈 L,〉 是一个格,那么对 L中任何元素 a,b,c,有
（ 1） a a∨ b,b a∨ b
a∧ b a,a∧ b b
（ 2） 若 a b,c d,则 a∨ c b∨ d,a∧ c b∧ d。
（ 3） 若 a b,则 a∨ c b∨ c,a∧ c b∧ c。
这个性质称为格的保序性 。
第 7章 格和布尔代数证明
（ 1） 因为 a∨ b是 a的一个上界,所以 a a∨ b；同理有 b a∨ b。 由对偶原理可得 a∧ b a,a∧ b b。
（ 2）由题设知 a b,c d，由（ 1）
有 b b∨ d,d b∨ d
有 a b∨ d,c b∨ d。
这说明 b∨ d是 a和 c的一个上界,而 a∨ c是 a和 c的最小上界,所以,必有
a∨ c b∨ d
将 a∧ c≤b∧ d的证明留给读者 。
（ 3） 将 （ 2） 中的 a代替 b,b代替 c,c代替 d即可得证 。
第 7章 格和布尔代数定理 7.1.4 设 〈 L,〉 是一个格,那么对 L中任意元素 a,b,c,有
（ 1） a∨ a=a,a∧ a＝ a (幂等律 )
（ 2） a∨ b=b∨ a,a∧ b=b∧ a （ 交换律 ）
（ 3） a∨ （ b∨ c） =（ a∨ b） ∨ c,a∧ （ b∧ c）
=（ a∧ b） ∧ c (结合律 )
（ 4） a∧ (a∨ b)=a,a∨ (a∧ b)=a (吸收律 )
第 7章 格和布尔代数证明
（ 1） 由自反性可得 a a,所以 a是 a的一个上界,
因为 a∨ a是 a与 a的最小上界,因此 a∨ a a。
由定理 7.1.3的 （ 1） 可知 a a∨ a。
,所以 a∨ a=a。 利用对偶原理可得 a∧ a＝ a。
（ 2）由格的并 ∨ 与交 ∧ 运算的定义知满足交换律。
第 7章 格和布尔代数
（ 3） 由下确界定义知
a∧ （ b∧ c） b∧ c b (7.1.1)
a∧ （ b∧ c） a (7.1.2)
a∧ （ b∧ c） b∧ c c (7.1.3)
由式 (7.1.1),(7.1.2)得
a∧ （ b∧ c a∧ b (7.1.4)
第 7章 格和布尔代数由式 (7.1.3),(7.1.4)得
a∧ （ b∧ c） (a∧ b)∧ c (7.1.5)
同理可证
（ a∧ b） ∧ c a∧ （ b∧ c） （ 7.1.6）
(7.1.5),(7.1.6),所以
a∧ （ b∧ c） =（ a∧ b） ∧ c。 利用对偶原理可得
a∨ （ b∨ c） =（ a∨ b） ∨ c。
第 7章 格和布尔代数
（ 4）由定理 7.1.3的（ 1）可知 a∧ （ a∨ b a；另一方面，由于 a a,a a∨ b，所以 a a∧ （ a∨ b），
因此有 a∧ (a∨ b)=a。
a∧ (a∨ b)=a的证明留给读者 。
由定理可知,格是带有两个二元运算的代数系统,
它的两个运算有上述四个性质,那么具有上述四条性质的代数系统 〈 L,∧,∨ 〉 是否是格？ 回答是肯定的 。
为了解决这个问题,我们再进一步介绍格的下述性质 。
第 7章 格和布尔代数定理 7.1.5 设 〈 L,〉 是一个格 。 那么对 L中任意元素 a,b,c,有
（ 1） a b当且仅当 a∧ b=a当且仅当 a∨ b=b。
（ 2） a∨ （ b∧ c） （ a∨ b） ∧ （ a∨ c） 。
（ 3） a c当且仅当 a∨ (b∧ c) （ a∨ b） ∧ c。
第 7章 格和布尔代数证明
（ 1）首先设 a b，因为 a a,所以 a a∧ b，而由定理 7.1.3的（ 1）可知
a∧ b a。 因此有 a∧ b=a。
再设 a=a∧ b,则 a∨ b=（ a∧ b） ∨ b=b（ 由吸收律 ）,即 a∨ b=b。
最后,设 b＝ a∨ b,则由 a a∨ b可得 a b。
因此,（ 1） 中 3个命题的等价性得证 。
第 7章 格和布尔代数
（ 2）因为 a a∨ b,a a∨ c,故
a （ a∨ b） ∧ （ a∨ c）。又因为
b∧ c b a∨ b,b∧ c c a∨ c (7.1.7)
所以有
b∧ c （ a∨ b） ∧ （ a∨ c） (7.1.8)
由式 （ 7.1.7） 和 （ 7.1.8） 可得
a∨ （ b∧ c a∨ b） ∧ （ a∨ c）
第 7章 格和布尔代数
（ 3） 设 a∨ (b∧ c) （ a∨ b） ∧ c。 由于
a a∨ （ b∧ c）,（ a∨ b） ∧ c c
因此由传递性有 a c。
反之,设 a c,则 a∨ c=c,代入本定理 （ 2） 即得
a∨ (b∧ c) （ a∨ b） ∧ c
第 7章 格和布尔代数定理 7.1.6 设 L为一非空集合,∨,∧ 为 L上的两个二元运算，如果 〈 L,∧,∨ 〉 中运算 ∧,∨ 满足交换律、
结合律和吸收律，则称 〈 L,∧,∨ 〉 为格。即在 L中可
a,b∈ L,a∧ b=GLB{a,b},a∨ b=LUB{a,b}。
证明 先证幂等性成立 。
由吸收律知 a∧ a＝ a∧ （ a∨ （ a∧ b）） ＝ a
a∨ a＝ a∨ (a∧ （ a∨ b）） ＝ a
第 7章 格和布尔代数
。
先定义 L a,b ∈ L,a b
当且仅当 a∧ b=a。
（ 1） L上偏序关系 。
① 因为 a∧ a＝ a,故 a a。 自反性得证 。
② 设 a b,b a,则 a∧ b=a,b∧ a=b 。 由于
a∧ b=b∧ a,故 a=b。 反对称性得证 。
第 7章 格和布尔代数
③ 设 a b,b c,则 a∧ b=a,b∧ c=b,于是
a∧ c=（ a∧ b） ∧ c＝ a∧ （ b∧ c） ＝ a∧ b=a
故 a c。 传递性得证 。
（ 2） 可证 a b当且仅当 a∨ b＝ b。
设 a b,那么 a∧ b=a,从而 （ a∧ b） ∨ b＝ a∨ b,
由吸收律即得 b=a∨ b。 反之,设 a∨ b＝ b,那么 a∧
（ a∨ b） ＝ a∧ b,由吸收律可知 a＝ a∧ b,即 a b。
第 7章 格和布尔代数
（ 3）下证在这个关系下，对任意 a,b∈ L,a∨ b为
{a,b}的上确界，即 a∨ b=LUB{a,b}。
由吸收律 a∧ （ a∨ b） ＝ a,所以 a a∨ b。 又因为
b∧ （ a∨ b） ＝ b,所以 b a∨ b,故 a∨ b为 {a,b}的一个上界 。
设 c为 {a,b}任一上界,即 a c,b c,那么,
a∨ c＝ c,b∨ c＝ c,于是
a∨ c∨ b∨ c＝ c∨ c
亦即 a∨ b∨ c＝ c,故 a∨ b≤c。 这表明 a∨ b为 {a,b}的上确界 。
第 7章 格和布尔代数
（ 4） 下证在这个关系下,对任意 a,b∈ L,a∧ b为
{a,b}的下确界,即 a∧ b=GLB{a,b}。
由吸收律 (a∧ b)∧ a＝ a∧ a∧ b=a∧ b,所以 a∧ b a。
又因为 (a∧ b)∧ b＝ a∧ (b∧ b)=a∧ b,所以 a∧ b b,
故 a∧ b为 {a,b}的一个下界 。
设 c为 {a,b}任一下界,即 c a且 c b，
义知 a∧ c＝ c,b∧ c＝ c,于是
c∧ （ a∧ b） ＝ (c∧ a)∧ b=c∧ b=c
所以 c a∧ b,即 a∧ b为 {a,b}的下确界 。
因此 〈 L,〉 是格 。
第 7章 格和布尔代数定义 7.1.2 设 〈 S,*,。 〉 是代数系统,*,。 是 S上的二元运算,且 *,。 满足交换律,结合律和吸收律,则
〈 S,*,。 〉 构成格 。
【 例 7.1.2】
（ 1） 〈 P(S),∩,∪ 〉 是一个代数系统,P(S)是集合 S
的幂集,因为 ∩,∪ 满足可交换,可结合并满足吸收律,
所以 〈 P(S),∩,∪ 〉 是格 。 事实上该格对应的偏序关系就是 S 。
第 7章 格和布尔代数
（ 2） 〈 Sn,*,。 〉 是一个代数系统,Sn是 n的所有因子作元素构成的集合,这里对于任意的 x,y∈ Sn,x*y={x,y}
的最大公约数,x。 y={x,y}的最小公倍数,因为 *,。 满足可交换,可结合并满足吸收律,所以 〈 Sn,*,。 〉 是格,并且该格对应的偏序关系就是整除关系 。 简单地说,子格即为格的子代数 。
第 7章 格和布尔代数定义 7.1.3 设 〈 L,∧,∨ 〉 是一个格，设非空集合 S
且 S L,若对任意的 a,b∈ S,有 a∧ b∈ S,a∨ b∈ S,则称
〈 S,∧,∨ 〉 是 〈 L,∧,∨ 〉 的子格。
显然,子格必是格 。 而格的某个子集构成格,却不一定是子格 。 这一点请读者思考 。
第 7章 格和布尔代数图 7.1.3
e
d
c
a
b
第 7章 格和布尔代数
【 例 7.1.3】 设 〈 L,是一个格，其中
L={a,b,c,d,e},7.1.3 所示。 S1={a,b,c,d}，
S2={a,b,c,e},则 〈 S1,是 〈 L,是一个子格，
〈 S2,不是 〈 L,是一个子格，因为 b∧ c=d S2，
〈 S2,不是格。类似群的同态，也可以定义格的同态。
第 7章 格和布尔代数定义 7.1.4 设 〈 L,*,〉,〈 S,∧,∨ 〉 是两个格,存在映射 f:L→ S,a,b∈ L满足 f(a*b)=f(a)∧ f(b),称 f是交同态 ;若满足 f(a b)=f(a)∨ f(b),称 f是并同态 。 若 f既是交同态又是并同态,称 f为格同态 。 若 f是双射,则称 f为格同构 。
定义 7.1.5 设 〈 L,*,〉,〈 S,∧,∨ 〉 是两个格,其
1,2分别为格 L,S上的偏序关系,存在映射 f:L→ S,
a,b∈ L,若 a 1b f(a) 2f(b),称 f是序同态 。 若 f是双射 。 则称 f是序同构 。
第 7章 格和布尔代数下面介绍格同态的定理 。
定理 7.1.7 设 f是格 〈 L,1〉 到格 〈 S,2〉 的格同态,
则 f是序同态 。 即同态是保序的 。
证明 因为 a 1b，所以
a*b=a f(a*b)=f(a) f(a)∧ f(b)=f(a)。因此,f(a) 2 f(b)。?
第 7章 格和布尔代数图 7.1.4
e
d
c
a
b g
h
( a ) ( b )
第 7章 格和布尔代数
【 例 7.1.4】 设 〈 L,,〈 S,是格，其中
L={a,b,c,d},S={e,g,h} 7.1.4(a),(b) 所示。
作映射 f:L→ S,f(b)=f(c)=g,f(a)=e,f(d)=h,显然 f满足序同态 。 f(b*c)=f(a),f(b)∧ f(c)=g≠f(a),所以不满足交同态,因此 f不是格同态 。
第 7章 格和布尔代数定理 7.1.8 映射 f是格 〈 L,1〉 到格 〈 S,2〉 的格同
a,b∈ L，有 a 1b f(a) 2f(b)。
证明 设映射 f是格 〈 L,1〉 到格 〈 S,2〉 的格同构 。
由定理 7.1.7 a,b∈ L,有 a 1b f(a) 2f(b)。 反之,
f(a) 2f(b)
f(a)∧ f(b)=f(a)
f(a*b)=f(a)
a*b=a （ f是双射 ）
a 1b
第 7章 格和布尔代数
a,b∈ L,有 a 1b f(a) 2f(b)。 设 a*b=c(要证
f(c)是 f(a),f(b)的最大下界 ),有
c 1a f(c) 2f(a)
c 1b f(c) 2f(b)
所以 f(c)是 f(a),f(b)的一个下界 。 再设 x是 f(a),f(b)
的任意下界,因为 f是满射,所以有 d∈ L,使 x=f(d)且
f(d) 2f(a) d 1a,f(d) 2f(b) d 1b
第 7章 格和布尔代数所以 d 1a*b,即 d 1c f(d) 2f(c)。因此 f(c)是
f(a),f(b) f(c)=f(a*b)=f(a)∧ f(b)
似可证 f(a b)=f(a)∨ f(b)。所以 f是 〈 L,1〉 到 〈 S,2〉
的格同构。
第 7章 格和布尔代数
【 例 7.1.5】 在同构意义下,具有 1个,2个,3个元素的格分别同构于元素个数相同的链 。
4个元素的格必同构于图 7.1.5中给出的含 4个元素的格之一； 5个元素的格必同构于图 7.1.5中的含 5个元素的格之一 。 其中图 7.1.5(g)称作五角格,图 7.1.5(h)称作钻石格,这两个格在讨论特殊格时会很有用 。
第 7章 格和布尔代数图 7.1.5
( e )( d )( c )( b )( a )
( j )( i )( h )( g )( f )
第 7章 格和布尔代数
7.2 特 殊 格本节讨论几个特殊的格 。
定义 7.2.1 如果在格 〈 L,〉 中,存在一个元素 a∈ L,
均有
a x(x a)
则称 a为格的全下界 （ 全上界 ） （ 相应于偏序集中的最小元,最大元 ）,且记全下界为 0,全上界为 1。
全下界 （ 全上界 ） 有如下性质 。
第 7章 格和布尔代数定理 7.2.1 全下 （ 上 ） 界如果存在,则必唯一 。
证明 设 1与 1′均是全上界,则因为 1是全上界,所以 1′ 1；又因为 1′是全上界,所以 1 1′。
称性,所以 1=1′。 类似可证全下界唯一 。
第 7章 格和布尔代数
【 例 7.2.1】 在格 〈 P(S),∩,∪ 〉 中,S是全上界,
是全下界 。
定义 7.2.2 如果 〈 L,∧,∨ 〉 中既有全上界 1,又有全下界 0。 称 0,1为格 L的界 （ bound）,并称格 L为有界格 （ bounded lattice） 。
不难看出,任何有限格必是有界格 。 而对于无限格,有的是有界格,有的不是有界格 。 有界格有如下性质 。
第 7章 格和布尔代数定理 7.2.2 设 〈 L,〉 是有界格,a∈ L,有
a∧ 0=0,a∧ 1=a,a∨ 0=a,a∨ 1=1。
证明留作练习 。
定义 7.2.3 如果格 〈 L,∧,∨ 〉 若满足：对任意元素 a,b,c∈ L,有
a c a∨ （ b∧ c） =（ a∨ b） ∧ c
则 L称为模格 （ modulerlattice） 。
定理 7.2.3 格 L是模格的充分必要条件是它不含有同构于五角格的子格 。
第 7章 格和布尔代数图 7.2.1
a
1
b
c
0
第 7章 格和布尔代数
【 例 7.2.2】 如图 7.2.1所示的五角格,它不是模格 。
因为 0 c b 1,而 c∨ (a∧ b)=c,(c∨ a)∧ b=b。
定理 7.2.4 格 〈 L,∧,∨ 〉 为模格的充分必要条件是：对 L中任意元素 a,b,c，
b a,a∧ c=b∧ c,a∨ c＝ b∨ c,则 a=b。
第 7章 格和布尔代数证明 先证必要性 。
设 〈 L,∧,∨ 〉 为模格,且
b a,a∧ c=b∧ c,a∨ c＝ b∨ c,那么,
a ＝ a∨ （ a∧ c）
＝ a∨ （ b∧ c）
=b∧ (a∨ c)
=b∧ (b∨ c)
=b
第 7章 格和布尔代数再证充分性 。
为证 〈 L,∧,∨ 〉 为模格,设 b a,需证
a∧ （ b∨ c） ＝ b∨ （ a∧ c） 。 首先,据定理 7.1.5之
（ 3）,由 b a可知
b∨ （ c∧ a） （ b∨ c） ∧ a (7.2.1）
由此
a∧ c ＝ （ a∧ c） ∧ c
（ b∨ （ c∧ a）） ∧ c
（ (b∨ c） ∧ a） ∧ c （ 由式 （ 7.2.1））
=（ (b∨ c） ∧ c） ∧ a=c∧ a
第 7章 格和布尔代数于是
（ b∨ （ c∧ a）） ∧ c＝（ (b∨ c） ∧ a） ∧ c=c∧ a （ 7.2.2）
（ 请读者完成 ）
（ b∨ (a∧ c）） ∨ c=(a∧ （ b∨ c）） ∨ c＝ b∨ c （ 7.2.3）
,根据题设及式 （ 7.2.1）,(7.2.2)和 （ 7.2.3） 得出
a∧ （ b∨ c） ＝ b∨ （ a∧ c）
L满足模性条件,故 〈 L,∨,∧ 〉 为模格得证 。
第 7章 格和布尔代数定义 7.2.4 格 〈 L,∧,∨ 〉 如果满足分配律,即对任意 a,b,c∈ L,有
a∧ （ b∨ c） =（ a∧ b） ∨ （ a∧ c） （ 7.2.4）
a∨ （ b∧ c） =（ a∨ b） ∧ （ a∨ c） （ 7.2.5）
则 L称为分配格 （ distributivelattice） 。
第 7章 格和布尔代数注意到,上述两个分配等式中有一个成立,则另一个必成立 。 如式 （ 7.2.4） 成立,则
（ 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）
第 7章 格和布尔代数
【 例 7.2.3】 设 S是一个集合，则 〈 P(S),∩,∪ 〉 构成格，而集合中求并 ∪ 与求交 ∩这两种运算满足分配律，
所以 〈 P(S),∩,∪ 〉 是分配格。并不是所有的格都是分配格。
图 7.2.2
a b c
1
0
第 7章 格和布尔代数
【 例 7.2.4】 如图 7.2.1和图 7.2.2所示的 Hasse图中的格均不是分配格 。 在图 7.2.2中,有
a∨ （ b∧ c） =a∨ 0=a
(a∨ b） ∧ （ a∨ c） =1∧ 1=1
所以不是分配格 。
第 7章 格和布尔代数分配格有以下性质：
定理 7.2.5 设 〈 L,∧,∨ 〉 为分配格，那么对 L中任意元素 a,b,c，若 c∧ a=c∧ b并且 c∨ a=c∨ b，则 a=b。
证明 因为
（ c∧ a） ∨ b＝ （ c∧ b） ∨ b=b (因 c∧ a=c∧ b）
（ c∧ a） ∨ b=（ c∨ b） ∧ （ a∨ b）
第 7章 格和布尔代数
=（ c∨ a） ∧ （ a∨ b） (因 c∨ a=c∨ b)
=a∨ （ c∧ b）
＝ a∨ （ c∧ a） （ 因 c∧ a=c∧ b）
=a
所以 a=b。
第 7章 格和布尔代数定理 7.2.6 若 〈 L,〉 是链,则 〈 L,〉 是分配格 。
证明 设 〈 L,〉 是链,则 〈 L,〉 是全序集,设对于该集合中任意的 a,b,c三个元素,分情况讨论：
(1)b a,c a,此时 a∧ （ b∨ c） =b∨ c，
同时 （ a∧ b） ∨ （ a∧ c） =b∨ c
(2)a b,a c,此时 a∧ （ b∨ c） =a,同时
（ a∧ b） ∨ （ a∧ c） =a因此无论任何情况,皆有 a∧
（ b∨ c） =（ a∧ b） ∨ （ a∧ c） 。 所以 〈 L,〉 是分配格 。
第 7章 格和布尔代数定理 7.2.7 设 〈 L,∧,∨ 〉 为分配格,则 〈 L,∧,∨ 〉
是模格 。
证明 对于任意的 a,b,c∈ L,若 a b,则 a∧ b=a,并有
b∧ (a∨ c)=(b∧ a)∨ (b∧ c)=a∨ (b∧ c)
因此,〈 L,∧,∨ 〉 是模格 。
下面我们讨论补格 。
定义 7.2.5 设 〈 L,∧,∨ 〉 为有界格,a为 L中任意元素,如果存在元素 b∈ L,使 a∨ b=1,a∧ b=0,则称 b
是 a的补元或补 （ complements） 。
第 7章 格和布尔代数补元有下列性质：
（ 1） 补元是相互的,即若 b是 a的补,那么 a也是 b的补 。
（ 2） 并非有界格中每个元素都有补元,而有补元也不一定唯一 。
（ 3）全下界 0与全上界 1互为补元且唯一。
第 7章 格和布尔代数
【 例 7.2.5】 考察图 7.2.3中 Hasse图所示的其格中其元素的补 。
图 7.2.3（ a） 中除 0,1之外 a,b,c均没有补元 。
图 7.2.3（ b） 中 a的补元是 b,b的补元是 a。
图 7.2.3（ c） 中元素 a,b,c两两互为补元,但不唯一 。
图 7.2.3（ d） 中除 0,1之外没有元素有补元 。 事实上,多于两个元素的链除 0,1之外没有元素有补元 。
在有界格中,显然 0是 1的唯一补元,同时 1是 0的唯一补元 。
第 7章 格和布尔代数图 7.2.3
a b
0
1
c
( a )
a b
0
1
( b )
a b
0
1
c
( c )
1
a
b
0
( d )
第 7章 格和布尔代数定义 7.2.6 如果有界格 〈 L,∨,∧ 〉 中每个元素都至少有一个补元，则称 L为补格
（ complementedlattice）。
例 7.2.5中 （ 2）,（ 3） 均是有补格,（ 1）,（ 4）
不是补格 。 多于两个元素的链都不是有补格 。
第 7章 格和布尔代数定理 7.2.8 若 〈 L,∧,∨ 〉 是有补分配格,a∈ L,
其补元是唯一的 。 因此,可用 a′来表示 a的补元 。
证明 采用反证法：若存在 a为 L中一元素,有两补元 b,c,且 b≠c,则
a∨ b＝ a∨ c＝ 1,a∧ b＝ a∧ c＝ 0
由定理 7.2.5有,b＝ c，与前面矛盾。因此 a只有唯一补元 a′。
第 7章 格和布尔代数定理 7.2.9 若 〈 L,∧,∨ 〉 a∈ L，
有 a″=（ a′） ′＝ a。
证明 a″∧ a′=0,a″∨ a′=1,由补元唯一可得 a″=a。
定理 7.2.10 德 · 摩根律,设 〈 L,∨,∧ 〉 是有补分配格,则对 L中任意元素 a,b,有
(1)（ a∧ b） ′=a′∨ b′
（ 2） （ a∨ b） ′＝ a′∧ b′
第 7章 格和布尔代数证明 (1)由于
（ a∧ b） ∧ （ a′∨ b′）
＝ ((a∧ b） ∧ a′)∨ ((a∧ b） ∧ b′)＝ 0
（ a∧ b） ∨ （ a′∨ b′） =（ a∨ a′∨ b′）
∧ （ b∨ a′∨ b′） ＝ 1
因此 a′∨ b′为 a∧ b的补元 。 由补元的唯一性得知：
(a∧ b） ′＝ a′∨ b′
同样可证 （ 2）,其证明留作练习 。
第 7章 格和布尔代数定理 7.2.11 对有补分配格的任何元素 a,b，有 a b
当且仅当 a∧ b′=0当且仅当 a′∨ b=1。
证明 若 a b，则有 a∨ b=b，所以
a∧ b′=(a∧ b′)∨ (b∧ b′)=(a∨ b)∧ b′=b∧ b′=0。
a∧ b′=0，则其对偶式 a′∨ b=1必成立。
若 a′∨ b=1，则 a∨ b=(a∨ b)∧ 1=(a∨ b)∧ (a′∨ b)
=(a∧ a′)∨ b=0∨ b=b。
第 7章 格和布尔代数
7.3 布尔代数定义 7.3.1 设 B是至少有两个元素的有补分配格,则称 B是布尔代数 （ Booleanalgebra） 。
【 例 7.3.1】 〈 {0,1},∧,∨,′〉 是一个布尔代数 。
第 7章 格和布尔代数
【 例 7.3.2】 S≠,则 〈 P(S),∩,∪,∽ 〉 是一个布尔代数。
其中 ∩表示集合的交运算,∪ 表示集合的并运算,∽ 表示集合的为一元求补集的运算（这里的全集是 S）。
布尔代数通常用序组 〈 B,∧,∨,′,0,1〉 来表示 。 其中 ′为一元求补运算 。 为此介绍布尔代数的另一个等价定义 。
第 7章 格和布尔代数定义 7.3.2 〈 B,∧,∨,′〉 是代数系统,B中至少有两个二元元素,∧,∨ 是 B上二元运算,′是一元运算，若 ∧,∨ 满足：
（ 1） 交换律 ;
（ 2） 分配律 ;
（ 3）同一律。存在 0,1∈ B,a∈ B，有
a∧ 1=a,a∨ 0=a;
（ 4） 补元律 。 对 B中每一元素 a,均存在元素 a′，
使 a∧ a′=0,a∨ a′＝ 1,则称 〈 B,∧,∨,′〉 是布尔代数 。
第 7章 格和布尔代数为证定义 7.3.1与定义 7.3.2等价,只需证 B是格,进而由 （ 2）,(3),（ 4） 可断定 B为有补分配格 。 要证 B
是格,据定义 7.1.2,只要证 B满足交换律 （ 已有 ）,结合律和吸收律 。
下证 B满足吸收律 。 a∈ B,有 a∧ 0=0。
第 7章 格和布尔代数
a∧ 0=(a∧ 0)∨ 0 (同一律 )
=（ a∧ 0） ∨ （ a∧ a′） （ 补元律 ）
=a∧ （ 0∨ a′） （ 分配律 ）
=a∧ a′ (同一律 )
=0 （ 补元律 ）
第 7章 格和布尔代数
a,b∈ B,
a∧ (a∨ b)＝ （ a∨ 0） ∧ （ a∨ b） (同一律 )
＝ a∨ （ 0∧ b） （ 分配律 ）
=a∨ 0
=a (同一律 )
类似可证 a∨ （ a∧ b） ＝ a。
因此 B满足吸收律 。 前面已证明由吸收律可推出满足幂等律 。
第 7章 格和布尔代数再证 B满足结合律 。 a,b,c∈ B,可如下证明
a∧ （ b∧ c） ＝ （ a∧ b） ∧ c，
从而对偶地可证 a∨ （ b∨ c） ＝ （ a∨ b） ∨ c。 令
X=a∧ （ b∧ c）,Y=（ a∧ b） ∧ c
那么
a∨ X＝ a∨ (a∧ （ b∧ c） )＝ a （ 吸收律 ）
a∨ Y=a∨ (（ a∧ b） ∧ c)
＝ (a∨ （ a∧ b） )∧ (a∨ （ a∧ c） )（ 分配律 ）
=a∧ a＝ a （ 幂等律 ）
第 7章 格和布尔代数故
a∨ X＝ a∨ Y （ 7.3.1）
a′∨ X=a′∨ （ a∧ （ b∧ c））
＝ (a′∨ a） ∧ （ a′∨ (b∧ c） ) (分配律 ）
=1∧ （ a′∨ (b∧ c） ) (补元律 ）
=（ a′∨ (b∧ c） ) (同一律 )
=（ a′∨ b） ∧ （ a′∨ c） (分配律 ）
a′∨ Y=a′∨ （ (a∧ b） ∧ c)
第 7章 格和布尔代数
=(a′∨ （ a∧ b） )∧ (a′∨ c) (分配律 ）
=（（ a′∨ a） ∧ （ a′∨ b）） ∧ （ a′∨ c） (分配律 ）
=（ 1∧ （ a′∨ b）） ∧ （ a′∨ c） (补元律 ）
=（ a′∨ b） ∧ （ a′∨ c） (同一律 )
故
a′∨ X=a′∨ Y （ 7.3.2）
第 7章 格和布尔代数由式 （ 7.3.1） 和 （ 7.3.2） 得
（ a∨ X） ∧ （ a′∨ X） ＝ （ a∨ Y） ∧ (a′∨ Y)
（ a∧ a′） ∨ X=(a∧ a′） ∨ Y分配律 )
0∨ X=0∨ Y(补元律 ）
X＝ Y（ 同一律 ）
故 a∧ （ b∧ c） ＝ （ a∧ b） ∧ c得证 。
第 7章 格和布尔代数
【 例 7.3.3】 〈 P,∧,∨,,0,1〉 为布尔代数。
这里 P为命题公式集,∧,∨,为合取、析取、否定的真值运算,0,1分别为假命题、真命题。
定义 7.3.3 设 〈 B,∧,∨,′,0,1〉 是布尔代数,
S(B,若 S含有 0,1,且在运算 ∧,∨,′下是封闭的,则称 S
是 B的子布尔代数,记作 〈 S,∧,∨,′,0,1〉 。
第 7章 格和布尔代数图 7.3.1
a
1
b c
f
e
d
0
第 7章 格和布尔代数
【 例 7.3.4】
(1)对任何布尔代数 〈 B,∨,∧,′,0,1〉 恒有子布尔代数 〈 B,∨,∧,′,0,1〉 和 〈 {0,1},∨,∧,′，
0,1〉,它们被称为 B的平凡子布尔代数 。
（ 2）如图 7.3.1给出的布尔代数 S1={1,a,f,0}是子布尔代数,S2={1,a,c,e}不是子布尔代数，因为 0不在 S2中。
关于子布尔代数除了定义外我们还有如下判别定理。
第 7章 格和布尔代数定理 7.3.1 设 〈 B,∧,∨,′,0,1〉 是布尔代数，
S B且 S≠,a,b∈ S,a∨ b∈ S,a′∈ S,则 S是 B的子布尔代数，记作 〈 S,∧,∨,′,0,1〉 。
证明 a,b∈ S,则 a′,b′∈ S,(a′∨ b′)′=a∧ b∈ S。
因为 S≠,所以存在 a∈ S，因此 a′∈ S,所以
a∧ a′=0∈ S和 a∨ a′=1∈ S。
第 7章 格和布尔代数定义 7.3.4 设 〈 B,∧,∨,′,0,1〉 和
〈 B*,∩,∪,∽,0,1〉 是两个布尔代数，若存在映射 f,B→ B*满足，对任何元素 a,b∈ B，有
f（ a∧ b） ＝ f（ a） ∩f（ b） （ 7.3.4）
f（ a∨ b） =f（ a） ∪ f（ b） （ 7.3.5）
f（ a′） =∽ (f(a)) （ 7.3.6）
则称 f是 〈 B,∧,∨,′,0,1〉 到 〈 B*,∩,∪,
∽,0,1〉 的布尔同态。若 f是双射，则称 f是
〈 B,∧,∨,′,0,1〉 到 〈 B*,∩,∪,∽,0,1〉
的布尔同构。
第 7章 格和布尔代数下面讨论有限布尔代数的表示定理 。
定义 7.3.5 设 B是布尔代数,如果 a是元素 0的一个覆盖,则称 a是该布尔代数的一个原子 （ atoms） 。
例如图 7.3.1中 d,e,f均是原子 。 实际上,在布尔代数中,原子是 B-{0}的极小元,因为原子与 0之间不存在其它元素 。
关于布尔代数的原子我们有以下性质 。
第 7章 格和布尔代数定理 7.3.2 设 〈 B,∧,∨,′,0,1〉 是布尔代数,
B中的元素 a是原子的充分必要条件是 a≠0且对 B中任何元素 x有
x∧ a=a 或 x∧ a=0 （ 7.3.7）
证明 先证必要性 。 设 a是原子,显然 a≠0。 另设
x∧ a≠a。 由于 x∧ a a,故 0 x∧ a,x∧ a a。 据原子的定义,有 x∧ a＝ 0。
第 7章 格和布尔代数再证充分性。设 a≠0，且对任意 x∈ B，有 x∧ a=a或
x∧ a=0成立。若 a不是原子，那么必有 b∈ B，使 0 b
a。于是,b∧ a＝ b。
因为 b≠0,b≠a,故 b∧ a＝ b与式 （ 7.3.7） 矛盾 。 因此 a只能是原子 。
第 7章 格和布尔代数定理 7.3.3 设 a,b为布尔代数
〈 B,∨,∧,′,0,1〉 中任意两个原子，则 a=b或
a∧ b=0。
证明 分两种情况来证明 。
（ 1） 若 a,b是原子且 a∧ b≠0,则
0＜ a∧ b a (因为 a是原子,所以 a=a∧ b)
0＜ a∧ b b (因为 b是原子,所以 b=a∧ b)
故 a=b。
第 7章 格和布尔代数
（ 2）若 a,b是原子且 a≠b由原子的性质可知,a∧ b≠a,a∧ b≠b(否则 a b或 b a)。用反证法，若
a∧ b≠0，则
0＜ a∧ b＜ a,0＜ a∧ b＜ b
与 a,b为原子矛盾,故 a∧ b=0。
第 7章 格和布尔代数定义 7.3.6 设 B是布尔代数,b∈ B,定义集合
A(b)={a|a∈ B,a是原子且 a b}。
例如，图 7.3.1中
A(b)={d,f},A(c)={e,f},A(0)=,A(1)={d,e,f}。
引理 1 设 〈 B,∨,∧,′,0,1〉 是一有限布尔代数，则对于 B中任一非零元素 b，恒有一原子 a∈ B,
使 a b。
第 7章 格和布尔代数证明 b∈ B且 b≠0:
若 b为原子,有 b b,则命题已得证 。
若 b不是原子,则必有 b1∈ B,0＜ b1＜ b。
若 b1不是原子,存在 b2使 0 b2 b1 b,对 b2重复上面的讨论 。
因为 B有限,这一过程必将中止,上述过程中产生
0? b2 b1 b
即存在 br,br为原子,且 0 br b,否则此序列无限长 。
引理 1得证 。
第 7章 格和布尔代数引理 2 设 〈 B,∨,∧,′,0,1〉 是一有限布尔代数,b为 B中任一非零元素，设 A(b)={a1,a2,?,am}，
则 b=a1∨ a2∨? ∨ am= a,且表达式唯一。
证明 令 c=a1∨ a2∨? ∨ am。 要证 b=c。
由于 ai b（ i=1,2,?,m）,因为 c是 A(b)中最小上界,
所以 c b。
欲证 b c。 据定理 7.2.11,只要证 b∧ c′=0。
()a A b
第 7章 格和布尔代数用反证法,设 b∧ c′≠0,从而存在原子 a使得
0 a b∧ c′,所以有 a b,a c′。
由于 a b,a是原子,因此 a为 a1,a2,?,am之一,
故 a c。
所以 a c∧ c′=0,与 a是原子矛盾 。 因此 b∧ c′=0,即
b c。 b=c=a1∨ a2∨? ∨ am得证 。
第 7章 格和布尔代数下证唯一性 。
设 b也可表示为 b= a,S={b1,b2,?,bj},b1,b2,?,bj是原子。
需证 S=A(b)。
若 q∈ S,有 q b,所以 q∈ A(b),因此 S A(b)。
若 q∈ A(b)，
有 qb,q=q∧ b=q∧ a∈ S a= a∈ S (q∧ a)。
由定理 7.3.3知,存在 a0∈ S,使 q=a0,所以 q∈ S。 故
S=A(b),引理 2得证 。
aS
aS aS
第 7章 格和布尔代数定理 7.3.4 若 a是原子,则 a b∨ c的充分必要条件是 a b或 a c。
证明 先证必要性 。
若 a是原子，且 a b∨ c,不妨设 x≤ b，因为 a是原子，
由定理 7.3.3有 a∧ b=0。
因为 a b∨ c,所以有
a=a∧ (b∨ c)=(a∧ b)∨ (a∧ c)=(a∧ c),故 a c,得证。充分性显然。
第 7章 格和布尔代数定理 7.3.5 设 〈 B,∨,∧,′,0,1〉 为有限布尔代数，令 A={a|a∈ B且 a是原子 }，则 B同构于布尔代数
〈 P(A),∪,∩,∽,,A〉 。
证明 构造映射 f,B→ P(A),使得对任意 b∈ B,f(b)=A(b)。
(1)证明 f为一单射 。 若 f(b)=f(c),有 A(b)=A(c)。 由引理 2得 b= a∈ A(b),
c= a∈ A(c) a,所以 b=c,故 f是单射 。
()a A b
()a A c
第 7章 格和布尔代数
（ 2）证明 f S∈ P(A),则 S A。
令 b= a∈ S a,由引理 2得 b= a∈ A(b) a。
由唯一性有 S=A(b)=f(b)。若
S= =A(b)=f(b),所以 f为满射得证。
aS bS
第 7章 格和布尔代数
(3)接着要证明 f保持运算，即 f满足式（ 7.3.4）、
式（ 7.3.5）和式（ 7.3.6）。
设 b,c为 B中任意两个元素且 b≠0,c≠0。 对任意的原子 x,x∈ A(b∧ c) x b∧ c x b且 x c x∈ A(b)且
x∈ A(c) x∈ A(b)∩A(c) 所以 A(b∧ c)=A(b)∩A(c),即
f(b∧ c)=f(b)∩f(c)。
第 7章 格和布尔代数对任意的原子 x,
x∈ A(b∨ c) x b∨ c x b或 x c x∈ A(b)
或 x∈ A(c) x∈ A(b)∪ A(c)
所以 A(b∨ c)=A(b)∪ A(c),即 f(b∨ c)=f(b)∪ f(c)。
b∈ B,且 b≠0,对任意的原子 x,
x∈ A(b′) x∧ b=0 x∧ b≠x x≤b x A(b) x∈∽ A(b)
所以 A(b′） =∽ A(b),即 f(b′)=∽ (f(b)),定理得证 。
第 7章 格和布尔代数本定理有如下推论：
推论 1 若有限布尔代数有 n个原子,则它有 2n个元素 。
推论 2 任何具有 2n个元素的布尔代数互相同构 。
注意 这一定理对无限布尔代数不能成立 。
根据这一定理,有限布尔代数的基数都是 2的幂 。
同时在同构的意义上对于任何 2n,n为自然数,仅存在一个 2n元的布尔代数,如图 7.3.2中的 Hasse图所示的 1
元,2元,4元,8元的布尔代数 。
第 7章 格和布尔代数图 7.3.2
第 7章 格和布尔代数
7.4 例题选解
【 例 7.4.1】 设 〈 L,≤〉 是格,a,b,c∈ L,a≤b，证明：
(a∨ b∧ c))∨ c=(b∧ (a∨ c))∨ c
证明 因为 a≤b，且 a≤a∨ c，所以 a≤b∧ (a∨ c)，故
a∨ c≤（ b∧ (a∨ c)） ∨ c。由格的吸收律、结合律知
（ a∨ b∧ c)） ∨ c=a∨ c，所以
（ a∨ (b∧ c)） ∨ c≤（ b∧ (a∨ c)） ∨ c
第 7章 格和布尔代数又由格的分配不等式知 （ b∧ (a∨ c)） ∨ c≤（ b∨ c）
∧ (a∨ c),而
（ b∨ c） ∧ (a∧ c)≤a∨ c=（ a∨ (b∧ c)） ∨ c
故
（ a∨ (b∧ c)） ∨ c=(b∧ (a∨ c))∨ c
第 7章 格和布尔代数
【 例 7.4.2】 设 〈 L,≤〉 是格,a,b,c,d∈ L,证明：
(a∧ b)∨ (c∧ d)≤（ a∨ c） ∧ (b∨ d）
证明 a,b,c,d∈ L,因为 a∧ b≤a,a∧ b≤b,c∧ d≤c，
c∧ d≤d,所以
(a∧ b)∨ (c∧ d)≤a∨ c,(a∧ b)∨ (c∧ d)≤b∨ d
因此
(a∧ b)∨ (c∧ d)≤（ a∨ c） ∧ （ b∨ d）
第 7章 格和布尔代数
【 例 7.4.3】 一个格 〈 A,≤〉 是分配格 iff a,b,c∈ A
有 (a∨ b)∧ c≤a∨ (b∧ c)。
证明 先证必要性：设 〈 A,≤〉 是分配格 。
a,b,c∈ A,由 a∧ c≤a，
b∧ c≤b∧ c,可得
（ a∧ c） ∨ （ b∧ c） ≤a∨ （ b∧ c）
而 （ a∨ b） ∧ c=（ a∧ c） ∨ （ b∧ c）
所以 （ a∨ b） ∧ c≤a∨ (b∧ c)
第 7章 格和布尔代数
a,b,c∈ A有
(a∨ b)∧ c≤a∨ (b∧ c)，则有
(a∨ b)∧ c =((a∨ b)∧ c） ∧ c≤（ a∨ (b∧ c)） ∧ c
=((b∧ c)∨ a） ∧ c≤（ b∧ c） ∨ （ a∧ c）
（ b∧ c） ∨ （ a∧ c） ≤(a∨ b)∧ c,因此有
(a∨ b)∧ c=（ b∧ c） ∨ （ a∧ c）
即 〈 A,≤〉 是分配格。
第 7章 格和布尔代数
【 例 7.4.4】 设 G是 30的因子集合,G上关系,|” 是整除关系 。
(1)画出 〈 G,|〉 的 Hasse图 。
(2)画出 〈 G,|〉 的所有元素个数大于等于 4的不同构的子格的 Hasse图 。
(3)上面各子格都是什么格？ （ 分配格,模格,有补格 ） 。
(4)上面各子格中有布尔代数吗？ 若有,指出并给出原子集合 。
第 7章 格和布尔代数图 7.4.1
30
10
3
1
15
5
6
2
第 7章 格和布尔代数解
（ 1） G={1,2,3,5,6,10,15,30},其哈斯图
7.4.1
(2)〈 G,|〉 的所有元素个数大于等于 4的不同构的子格的 Hasse图见图 7.4.2。
（ 3） 所有的子格均是分配格,模格 。 图 7.4.2
（ b）,（ f） 所示的格还是有补格 。
（ 4）图 7.4.2（ b）、（ f）所示的格是布尔代数。
其中，图（ b）的原子集合为 {15,6}，图（ f）的原子集合为 {2,3,5}。
第 7章 格和布尔代数图 7.4.2
30
10
3
1
15
5
6
2
30
3
1
15 10
5
30
1
15 6
30
1
15
5 3
30
15 6
1
1
5
15
30
( a ) ( b )
( c )
( f )( e )( d )
3
第 7章 格和布尔代数习 题 七
1,图 7.1所示的偏序集，哪一个是格？并说明理由。
第 7章 格和布尔代数图 7.1
( a ) ( b ) ( c ) ( d ) ( e ) ( f )
第 7章 格和布尔代数
2,对格 L中任意元素 a,b,c,d,证明：
（ 1） a b,a c当且仅当 a b∧ c。
（ 2） a c,b c当且仅当 a∨ b c。
（ 3） a∨ (a∧ b)=a。
（ 4） 若 a b c,d∧ c＝ a,则 d∧ b＝ a。
（ 5） 若 a b c,d∧ a＝ c,则 d∧ b＝ c。
（ 6） （ a∧ b） ∨ （ a∧ c） a∧ （ b∨ c） 。
（ 7） （（ a∧ b） ∨ （ a∧ c）） ∧ （（ a∧ b）
∨ （ b∧ c）） =a∧ b。
第 7章 格和布尔代数
（ 8）（ a∧ b） ∨ （ b∧ C） ∨ （ c∧ a a∨ b
∧ （ b∨ C） ∧ （ c∨ a）。
(9)若 a b,则有 (a∨ (b∧ c))∧ c=(b∧ (a∨ c))∧ c。
(10)a∧ b a且 a∧ b b当且仅当 a与 b是不可比较的,
即 a b,b a都不能成立 。
第 7章 格和布尔代数
3,证明：格 L的两个子格的交仍为 L的子格 。
4.设 a,b为格 L中的两个元素,证明：
S={x|x∈ L且 a x b}可构成 L的一个子格 。
5.设 f为格 L1到格 L2的同态映射,证明 f的同态像是
L2的子格 。
6,设 〈 L,∨,∧ 〉 为格,a∈ L,令 La={x|x∈ L且
x≤a},Ma={x|x∈ L 且 a≤x},则 〈 La,∨,∧ 〉,〈 Ma,
∨,∧ 〉 都是 L的子格 。
7,证明定理 7.2.2。
8.判断图 7.1所示的 Hasse图中的格各是什么格 。
（ 分配格,模格,补格,布尔格 ）
第 7章 格和布尔代数
9.证明定理 7.2.10中的 (2)。
10,证明：在有界分配格中,有补元的所有元素可以构成一个子格 。
11,设 〈 L,∧,∨ 〉 为有补分配格,a,b为 L中任意元素,证明,b′ a′当且仅当 a∧ b′=0当且仅当 a′∨ b=1。
12,设 a是布尔代数 〈 B,∧,∨,′,0,1〉 的原子,x为 B中任一元素,则 x或 a x′,但不兼而有之 。
13,设 a,b为布尔代数 B中任意元素,求证,a＝ b
当且仅当 （ a∧ b′） ∨ （ a′∧ b） ＝ 0。
第 7章 格和布尔代数
14.证明,在布尔同态的定义 （ 定义 7.3.4） 中,式
（ 7.3.4） 和式 （ 7.3.5） 两条件之一可省去 。
15.设 f为布尔代数 〈 A,∧,∨,′,0,1〉 到布尔代数 〈 B,∧,∨,′,0,1〉 的布尔同态,则
f（ 0） =0,f（ 1） =1。
16.设 〈 B,∧,∨,′,0,1〉 为布尔代数,定义
B a,b∈ B，
a b=（ a∧ b′） ∨ （ a′∧ b）
a*b=a∧ b
证明 〈 B,,*〉 ） 为一含幺交换环 。
第 7章 格和布尔代数
17,G是 12的因子集合,"|"是 G上的整除关系 。
(1)画出 〈 G,|〉 的 Hasse图 。
(2)画出 〈 G,|〉 的所有元素个数大于等于 4的子格的
Hasse图 。
(3)上述各子格都是什么格？ （ 分配格,模格,有补格 ）
(4)上述各子格中有布尔代数吗？ 若有,指出并给出原子集合 。
第 7章 格和布尔代数
18,设 G是 24的因子集合,"|"是 G上的整除关系 。
(1)画出 〈 G,|〉 的 Hasse图 。
(2)画出 〈 G,|〉 的所有 5元素子格的 Hasse图 。
(3)上述子格各是什么格？ （ 分配格,模格,有补格 ）
(4)〈 G,|〉 是布尔代数吗？ 若是,请给出原子集合 。
7.1 格与子格
7.2 特殊格
7.3 布尔代数
7.4 例题选解习 题 七第 7章 格和布尔代数
7.1 格与子格本章将讨论另外两种代数系统 —— 格与布尔代数,
它们与群,环,域的基本不同之处是：格与布尔代数的基集都是一个有序集 。 这一序关系的建立及其与代数运算之间的关系是介绍的要点 。 格是具有两个二元运算的代数系统,它是一个特殊的偏序集,而布尔代数则是一个特殊的格 。
第 7章 格和布尔代数图 7.1.1
a b
c
d
e f
第 7章 格和布尔代数在第四章,对偏序集的任一子集可引入上确界 （ 最小上界 ） 和下确界 （ 最大下界 ） 的概念,但并非每个子集都有上确界或下确界,例如在图 7.1.1中哈斯图所示的有序集里,{a,b}没有上确界,{e,f}没有下确界 。
不过,当某子集的上,下确界存在时,这个上,下确界是唯一确定的 。
第 7章 格和布尔代数定义 7.1.1 如果偏序集 〈 L 〉 中的任何两个元素的子集都有上确界和下确界,则称偏序集 〈 L 〉 为格（ lattice）。
虽然偏序集合的任何子集的上确界,下确界并不一定都存在,但存在,则必唯一,而格定义保证了上确界,下确界的存在性 。 因此我们通常用 a∨ b表示 {a，
b}的上确界,用 a∧ b表示 {a,b}的下确界,
第 7章 格和布尔代数图 7.1.2
b
a
a b
( a ) ( b ) ( c )
( d ) ( e )
第 7章 格和布尔代数并记作 a∨ b=LUB{a,b}
（ Leastupperbound）,a∧ b=GLB{a,b}(Greatestlowerbou
nd),∨ 和 ∧ 分别称为并（ join）和交（ meet）运算。由于对任何 a,b,a∨ b及 a∧ b都是 L中确定的成员，因此
∨,∧ 均为 L上的二元运算。由定义知道，并非所有的偏序集都能构成格，我们用 Hasse图表示偏序集，图
7.1.2中哪个能构成格？
图 7.1.2中哈斯图 （ a）,（ b）,（ c） 所规定的偏序集是格,图 （ d）,（ e)及图 7.1.1所规定的偏序集不是格,因为图中 {a,b}无上确界 。
第 7章 格和布尔代数
【 例 7.1.1】
（ 1） 对任意集合 S,偏序集 〈 P（ S）,〉 为格,
其中并,交运算即为集合的并,交运算,即
B∨ C＝ B∪ C B∧ C＝ B∩C
封闭于 P(S),这里 B,C∈ P(S)。
（ 2） 设 L为命题公式集合,逻辑蕴涵关系,,为
L上的偏序关系 （ 指定逻辑等价关系,,为相等关系 ）,那么,〈 L,〉 为格,对任何命题公式 A,B，
A∨ B=A∨ B,A∧ B=A∧ B（ 等式右边的 ∨,∧ 为析取与合取逻辑运算符 ） 。
第 7章 格和布尔代数
（ 3）设 Z+表示正整数集,|表示 Z+上整除关系，那么 〈 Z+,|〉 为格，其中并、交运算即为求两正整数最小公倍数和最大公约数的运算，即
m∨ n＝ LCM（ m,n） m∧ n＝ gcd（ m,n）
另外,若将 〈 L,〉 中的小于等于关系换成大于等
,即对于 L中任何两个元素 a,b定义 a b的充分必要条件是 b a,则 〈 L,〉 也是偏序集 。 我们把偏序集 〈 L,〉 和 〈 L,〉 称为是相互对偶的 。 并且它们所对应的哈斯图是互为颠倒的 。 关于格我们有同样的性质 。
第 7章 格和布尔代数定理 7.1.1 若 〈 L,〉 是一个格,则 〈 L,〉 也是一个格,且它的并,交运算 ∨ r,∧ r对任意 a,b∈ L满足
a∨ rb=a∧ b a∧ rb=a∨ b
于是,我们有下列对偶原理 。
第 7章 格和布尔代数定理 7.1.2 如果命题 P在任意格 〈 L,〉 上成立,
则将 L中符号 ∨,∧,∧,∨,
公式 P*在任意格 〈 L,〉 上也成立,这里 P*称为 P的对偶式 。
在上述对偶原理中,,如果命题 P在任意格
〈 L,〉 上成立,的含义是指当命题 P中的变量取值于
L中,且上确界运算为 ∨,下确界运算为 ∧,则 P对于它们也成立 。 现在我们深入地讨论格的性质 。
第 7章 格和布尔代数定理 7.1.3 设 〈 L,〉 是一个格,那么对 L中任何元素 a,b,c,有
（ 1） a a∨ b,b a∨ b
a∧ b a,a∧ b b
（ 2） 若 a b,c d,则 a∨ c b∨ d,a∧ c b∧ d。
（ 3） 若 a b,则 a∨ c b∨ c,a∧ c b∧ c。
这个性质称为格的保序性 。
第 7章 格和布尔代数证明
（ 1） 因为 a∨ b是 a的一个上界,所以 a a∨ b；同理有 b a∨ b。 由对偶原理可得 a∧ b a,a∧ b b。
（ 2）由题设知 a b,c d，由（ 1）
有 b b∨ d,d b∨ d
有 a b∨ d,c b∨ d。
这说明 b∨ d是 a和 c的一个上界,而 a∨ c是 a和 c的最小上界,所以,必有
a∨ c b∨ d
将 a∧ c≤b∧ d的证明留给读者 。
（ 3） 将 （ 2） 中的 a代替 b,b代替 c,c代替 d即可得证 。
第 7章 格和布尔代数定理 7.1.4 设 〈 L,〉 是一个格,那么对 L中任意元素 a,b,c,有
（ 1） a∨ a=a,a∧ a＝ a (幂等律 )
（ 2） a∨ b=b∨ a,a∧ b=b∧ a （ 交换律 ）
（ 3） a∨ （ b∨ c） =（ a∨ b） ∨ c,a∧ （ b∧ c）
=（ a∧ b） ∧ c (结合律 )
（ 4） a∧ (a∨ b)=a,a∨ (a∧ b)=a (吸收律 )
第 7章 格和布尔代数证明
（ 1） 由自反性可得 a a,所以 a是 a的一个上界,
因为 a∨ a是 a与 a的最小上界,因此 a∨ a a。
由定理 7.1.3的 （ 1） 可知 a a∨ a。
,所以 a∨ a=a。 利用对偶原理可得 a∧ a＝ a。
（ 2）由格的并 ∨ 与交 ∧ 运算的定义知满足交换律。
第 7章 格和布尔代数
（ 3） 由下确界定义知
a∧ （ b∧ c） b∧ c b (7.1.1)
a∧ （ b∧ c） a (7.1.2)
a∧ （ b∧ c） b∧ c c (7.1.3)
由式 (7.1.1),(7.1.2)得
a∧ （ b∧ c a∧ b (7.1.4)
第 7章 格和布尔代数由式 (7.1.3),(7.1.4)得
a∧ （ b∧ c） (a∧ b)∧ c (7.1.5)
同理可证
（ a∧ b） ∧ c a∧ （ b∧ c） （ 7.1.6）
(7.1.5),(7.1.6),所以
a∧ （ b∧ c） =（ a∧ b） ∧ c。 利用对偶原理可得
a∨ （ b∨ c） =（ a∨ b） ∨ c。
第 7章 格和布尔代数
（ 4）由定理 7.1.3的（ 1）可知 a∧ （ a∨ b a；另一方面，由于 a a,a a∨ b，所以 a a∧ （ a∨ b），
因此有 a∧ (a∨ b)=a。
a∧ (a∨ b)=a的证明留给读者 。
由定理可知,格是带有两个二元运算的代数系统,
它的两个运算有上述四个性质,那么具有上述四条性质的代数系统 〈 L,∧,∨ 〉 是否是格？ 回答是肯定的 。
为了解决这个问题,我们再进一步介绍格的下述性质 。
第 7章 格和布尔代数定理 7.1.5 设 〈 L,〉 是一个格 。 那么对 L中任意元素 a,b,c,有
（ 1） a b当且仅当 a∧ b=a当且仅当 a∨ b=b。
（ 2） a∨ （ b∧ c） （ a∨ b） ∧ （ a∨ c） 。
（ 3） a c当且仅当 a∨ (b∧ c) （ a∨ b） ∧ c。
第 7章 格和布尔代数证明
（ 1）首先设 a b，因为 a a,所以 a a∧ b，而由定理 7.1.3的（ 1）可知
a∧ b a。 因此有 a∧ b=a。
再设 a=a∧ b,则 a∨ b=（ a∧ b） ∨ b=b（ 由吸收律 ）,即 a∨ b=b。
最后,设 b＝ a∨ b,则由 a a∨ b可得 a b。
因此,（ 1） 中 3个命题的等价性得证 。
第 7章 格和布尔代数
（ 2）因为 a a∨ b,a a∨ c,故
a （ a∨ b） ∧ （ a∨ c）。又因为
b∧ c b a∨ b,b∧ c c a∨ c (7.1.7)
所以有
b∧ c （ a∨ b） ∧ （ a∨ c） (7.1.8)
由式 （ 7.1.7） 和 （ 7.1.8） 可得
a∨ （ b∧ c a∨ b） ∧ （ a∨ c）
第 7章 格和布尔代数
（ 3） 设 a∨ (b∧ c) （ a∨ b） ∧ c。 由于
a a∨ （ b∧ c）,（ a∨ b） ∧ c c
因此由传递性有 a c。
反之,设 a c,则 a∨ c=c,代入本定理 （ 2） 即得
a∨ (b∧ c) （ a∨ b） ∧ c
第 7章 格和布尔代数定理 7.1.6 设 L为一非空集合,∨,∧ 为 L上的两个二元运算，如果 〈 L,∧,∨ 〉 中运算 ∧,∨ 满足交换律、
结合律和吸收律，则称 〈 L,∧,∨ 〉 为格。即在 L中可
a,b∈ L,a∧ b=GLB{a,b},a∨ b=LUB{a,b}。
证明 先证幂等性成立 。
由吸收律知 a∧ a＝ a∧ （ a∨ （ a∧ b）） ＝ a
a∨ a＝ a∨ (a∧ （ a∨ b）） ＝ a
第 7章 格和布尔代数
。
先定义 L a,b ∈ L,a b
当且仅当 a∧ b=a。
（ 1） L上偏序关系 。
① 因为 a∧ a＝ a,故 a a。 自反性得证 。
② 设 a b,b a,则 a∧ b=a,b∧ a=b 。 由于
a∧ b=b∧ a,故 a=b。 反对称性得证 。
第 7章 格和布尔代数
③ 设 a b,b c,则 a∧ b=a,b∧ c=b,于是
a∧ c=（ a∧ b） ∧ c＝ a∧ （ b∧ c） ＝ a∧ b=a
故 a c。 传递性得证 。
（ 2） 可证 a b当且仅当 a∨ b＝ b。
设 a b,那么 a∧ b=a,从而 （ a∧ b） ∨ b＝ a∨ b,
由吸收律即得 b=a∨ b。 反之,设 a∨ b＝ b,那么 a∧
（ a∨ b） ＝ a∧ b,由吸收律可知 a＝ a∧ b,即 a b。
第 7章 格和布尔代数
（ 3）下证在这个关系下，对任意 a,b∈ L,a∨ b为
{a,b}的上确界，即 a∨ b=LUB{a,b}。
由吸收律 a∧ （ a∨ b） ＝ a,所以 a a∨ b。 又因为
b∧ （ a∨ b） ＝ b,所以 b a∨ b,故 a∨ b为 {a,b}的一个上界 。
设 c为 {a,b}任一上界,即 a c,b c,那么,
a∨ c＝ c,b∨ c＝ c,于是
a∨ c∨ b∨ c＝ c∨ c
亦即 a∨ b∨ c＝ c,故 a∨ b≤c。 这表明 a∨ b为 {a,b}的上确界 。
第 7章 格和布尔代数
（ 4） 下证在这个关系下,对任意 a,b∈ L,a∧ b为
{a,b}的下确界,即 a∧ b=GLB{a,b}。
由吸收律 (a∧ b)∧ a＝ a∧ a∧ b=a∧ b,所以 a∧ b a。
又因为 (a∧ b)∧ b＝ a∧ (b∧ b)=a∧ b,所以 a∧ b b,
故 a∧ b为 {a,b}的一个下界 。
设 c为 {a,b}任一下界,即 c a且 c b，
义知 a∧ c＝ c,b∧ c＝ c,于是
c∧ （ a∧ b） ＝ (c∧ a)∧ b=c∧ b=c
所以 c a∧ b,即 a∧ b为 {a,b}的下确界 。
因此 〈 L,〉 是格 。
第 7章 格和布尔代数定义 7.1.2 设 〈 S,*,。 〉 是代数系统,*,。 是 S上的二元运算,且 *,。 满足交换律,结合律和吸收律,则
〈 S,*,。 〉 构成格 。
【 例 7.1.2】
（ 1） 〈 P(S),∩,∪ 〉 是一个代数系统,P(S)是集合 S
的幂集,因为 ∩,∪ 满足可交换,可结合并满足吸收律,
所以 〈 P(S),∩,∪ 〉 是格 。 事实上该格对应的偏序关系就是 S 。
第 7章 格和布尔代数
（ 2） 〈 Sn,*,。 〉 是一个代数系统,Sn是 n的所有因子作元素构成的集合,这里对于任意的 x,y∈ Sn,x*y={x,y}
的最大公约数,x。 y={x,y}的最小公倍数,因为 *,。 满足可交换,可结合并满足吸收律,所以 〈 Sn,*,。 〉 是格,并且该格对应的偏序关系就是整除关系 。 简单地说,子格即为格的子代数 。
第 7章 格和布尔代数定义 7.1.3 设 〈 L,∧,∨ 〉 是一个格，设非空集合 S
且 S L,若对任意的 a,b∈ S,有 a∧ b∈ S,a∨ b∈ S,则称
〈 S,∧,∨ 〉 是 〈 L,∧,∨ 〉 的子格。
显然,子格必是格 。 而格的某个子集构成格,却不一定是子格 。 这一点请读者思考 。
第 7章 格和布尔代数图 7.1.3
e
d
c
a
b
第 7章 格和布尔代数
【 例 7.1.3】 设 〈 L,是一个格，其中
L={a,b,c,d,e},7.1.3 所示。 S1={a,b,c,d}，
S2={a,b,c,e},则 〈 S1,是 〈 L,是一个子格，
〈 S2,不是 〈 L,是一个子格，因为 b∧ c=d S2，
〈 S2,不是格。类似群的同态，也可以定义格的同态。
第 7章 格和布尔代数定义 7.1.4 设 〈 L,*,〉,〈 S,∧,∨ 〉 是两个格,存在映射 f:L→ S,a,b∈ L满足 f(a*b)=f(a)∧ f(b),称 f是交同态 ;若满足 f(a b)=f(a)∨ f(b),称 f是并同态 。 若 f既是交同态又是并同态,称 f为格同态 。 若 f是双射,则称 f为格同构 。
定义 7.1.5 设 〈 L,*,〉,〈 S,∧,∨ 〉 是两个格,其
1,2分别为格 L,S上的偏序关系,存在映射 f:L→ S,
a,b∈ L,若 a 1b f(a) 2f(b),称 f是序同态 。 若 f是双射 。 则称 f是序同构 。
第 7章 格和布尔代数下面介绍格同态的定理 。
定理 7.1.7 设 f是格 〈 L,1〉 到格 〈 S,2〉 的格同态,
则 f是序同态 。 即同态是保序的 。
证明 因为 a 1b，所以
a*b=a f(a*b)=f(a) f(a)∧ f(b)=f(a)。因此,f(a) 2 f(b)。?
第 7章 格和布尔代数图 7.1.4
e
d
c
a
b g
h
( a ) ( b )
第 7章 格和布尔代数
【 例 7.1.4】 设 〈 L,,〈 S,是格，其中
L={a,b,c,d},S={e,g,h} 7.1.4(a),(b) 所示。
作映射 f:L→ S,f(b)=f(c)=g,f(a)=e,f(d)=h,显然 f满足序同态 。 f(b*c)=f(a),f(b)∧ f(c)=g≠f(a),所以不满足交同态,因此 f不是格同态 。
第 7章 格和布尔代数定理 7.1.8 映射 f是格 〈 L,1〉 到格 〈 S,2〉 的格同
a,b∈ L，有 a 1b f(a) 2f(b)。
证明 设映射 f是格 〈 L,1〉 到格 〈 S,2〉 的格同构 。
由定理 7.1.7 a,b∈ L,有 a 1b f(a) 2f(b)。 反之,
f(a) 2f(b)
f(a)∧ f(b)=f(a)
f(a*b)=f(a)
a*b=a （ f是双射 ）
a 1b
第 7章 格和布尔代数
a,b∈ L,有 a 1b f(a) 2f(b)。 设 a*b=c(要证
f(c)是 f(a),f(b)的最大下界 ),有
c 1a f(c) 2f(a)
c 1b f(c) 2f(b)
所以 f(c)是 f(a),f(b)的一个下界 。 再设 x是 f(a),f(b)
的任意下界,因为 f是满射,所以有 d∈ L,使 x=f(d)且
f(d) 2f(a) d 1a,f(d) 2f(b) d 1b
第 7章 格和布尔代数所以 d 1a*b,即 d 1c f(d) 2f(c)。因此 f(c)是
f(a),f(b) f(c)=f(a*b)=f(a)∧ f(b)
似可证 f(a b)=f(a)∨ f(b)。所以 f是 〈 L,1〉 到 〈 S,2〉
的格同构。
第 7章 格和布尔代数
【 例 7.1.5】 在同构意义下,具有 1个,2个,3个元素的格分别同构于元素个数相同的链 。
4个元素的格必同构于图 7.1.5中给出的含 4个元素的格之一； 5个元素的格必同构于图 7.1.5中的含 5个元素的格之一 。 其中图 7.1.5(g)称作五角格,图 7.1.5(h)称作钻石格,这两个格在讨论特殊格时会很有用 。
第 7章 格和布尔代数图 7.1.5
( e )( d )( c )( b )( a )
( j )( i )( h )( g )( f )
第 7章 格和布尔代数
7.2 特 殊 格本节讨论几个特殊的格 。
定义 7.2.1 如果在格 〈 L,〉 中,存在一个元素 a∈ L,
均有
a x(x a)
则称 a为格的全下界 （ 全上界 ） （ 相应于偏序集中的最小元,最大元 ）,且记全下界为 0,全上界为 1。
全下界 （ 全上界 ） 有如下性质 。
第 7章 格和布尔代数定理 7.2.1 全下 （ 上 ） 界如果存在,则必唯一 。
证明 设 1与 1′均是全上界,则因为 1是全上界,所以 1′ 1；又因为 1′是全上界,所以 1 1′。
称性,所以 1=1′。 类似可证全下界唯一 。
第 7章 格和布尔代数
【 例 7.2.1】 在格 〈 P(S),∩,∪ 〉 中,S是全上界,
是全下界 。
定义 7.2.2 如果 〈 L,∧,∨ 〉 中既有全上界 1,又有全下界 0。 称 0,1为格 L的界 （ bound）,并称格 L为有界格 （ bounded lattice） 。
不难看出,任何有限格必是有界格 。 而对于无限格,有的是有界格,有的不是有界格 。 有界格有如下性质 。
第 7章 格和布尔代数定理 7.2.2 设 〈 L,〉 是有界格,a∈ L,有
a∧ 0=0,a∧ 1=a,a∨ 0=a,a∨ 1=1。
证明留作练习 。
定义 7.2.3 如果格 〈 L,∧,∨ 〉 若满足：对任意元素 a,b,c∈ L,有
a c a∨ （ b∧ c） =（ a∨ b） ∧ c
则 L称为模格 （ modulerlattice） 。
定理 7.2.3 格 L是模格的充分必要条件是它不含有同构于五角格的子格 。
第 7章 格和布尔代数图 7.2.1
a
1
b
c
0
第 7章 格和布尔代数
【 例 7.2.2】 如图 7.2.1所示的五角格,它不是模格 。
因为 0 c b 1,而 c∨ (a∧ b)=c,(c∨ a)∧ b=b。
定理 7.2.4 格 〈 L,∧,∨ 〉 为模格的充分必要条件是：对 L中任意元素 a,b,c，
b a,a∧ c=b∧ c,a∨ c＝ b∨ c,则 a=b。
第 7章 格和布尔代数证明 先证必要性 。
设 〈 L,∧,∨ 〉 为模格,且
b a,a∧ c=b∧ c,a∨ c＝ b∨ c,那么,
a ＝ a∨ （ a∧ c）
＝ a∨ （ b∧ c）
=b∧ (a∨ c)
=b∧ (b∨ c)
=b
第 7章 格和布尔代数再证充分性 。
为证 〈 L,∧,∨ 〉 为模格,设 b a,需证
a∧ （ b∨ c） ＝ b∨ （ a∧ c） 。 首先,据定理 7.1.5之
（ 3）,由 b a可知
b∨ （ c∧ a） （ b∨ c） ∧ a (7.2.1）
由此
a∧ c ＝ （ a∧ c） ∧ c
（ b∨ （ c∧ a）） ∧ c
（ (b∨ c） ∧ a） ∧ c （ 由式 （ 7.2.1））
=（ (b∨ c） ∧ c） ∧ a=c∧ a
第 7章 格和布尔代数于是
（ b∨ （ c∧ a）） ∧ c＝（ (b∨ c） ∧ a） ∧ c=c∧ a （ 7.2.2）
（ 请读者完成 ）
（ b∨ (a∧ c）） ∨ c=(a∧ （ b∨ c）） ∨ c＝ b∨ c （ 7.2.3）
,根据题设及式 （ 7.2.1）,(7.2.2)和 （ 7.2.3） 得出
a∧ （ b∨ c） ＝ b∨ （ a∧ c）
L满足模性条件,故 〈 L,∨,∧ 〉 为模格得证 。
第 7章 格和布尔代数定义 7.2.4 格 〈 L,∧,∨ 〉 如果满足分配律,即对任意 a,b,c∈ L,有
a∧ （ b∨ c） =（ a∧ b） ∨ （ a∧ c） （ 7.2.4）
a∨ （ b∧ c） =（ a∨ b） ∧ （ a∨ c） （ 7.2.5）
则 L称为分配格 （ distributivelattice） 。
第 7章 格和布尔代数注意到,上述两个分配等式中有一个成立,则另一个必成立 。 如式 （ 7.2.4） 成立,则
（ 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）
第 7章 格和布尔代数
【 例 7.2.3】 设 S是一个集合，则 〈 P(S),∩,∪ 〉 构成格，而集合中求并 ∪ 与求交 ∩这两种运算满足分配律，
所以 〈 P(S),∩,∪ 〉 是分配格。并不是所有的格都是分配格。
图 7.2.2
a b c
1
0
第 7章 格和布尔代数
【 例 7.2.4】 如图 7.2.1和图 7.2.2所示的 Hasse图中的格均不是分配格 。 在图 7.2.2中,有
a∨ （ b∧ c） =a∨ 0=a
(a∨ b） ∧ （ a∨ c） =1∧ 1=1
所以不是分配格 。
第 7章 格和布尔代数分配格有以下性质：
定理 7.2.5 设 〈 L,∧,∨ 〉 为分配格，那么对 L中任意元素 a,b,c，若 c∧ a=c∧ b并且 c∨ a=c∨ b，则 a=b。
证明 因为
（ c∧ a） ∨ b＝ （ c∧ b） ∨ b=b (因 c∧ a=c∧ b）
（ c∧ a） ∨ b=（ c∨ b） ∧ （ a∨ b）
第 7章 格和布尔代数
=（ c∨ a） ∧ （ a∨ b） (因 c∨ a=c∨ b)
=a∨ （ c∧ b）
＝ a∨ （ c∧ a） （ 因 c∧ a=c∧ b）
=a
所以 a=b。
第 7章 格和布尔代数定理 7.2.6 若 〈 L,〉 是链,则 〈 L,〉 是分配格 。
证明 设 〈 L,〉 是链,则 〈 L,〉 是全序集,设对于该集合中任意的 a,b,c三个元素,分情况讨论：
(1)b a,c a,此时 a∧ （ b∨ c） =b∨ c，
同时 （ a∧ b） ∨ （ a∧ c） =b∨ c
(2)a b,a c,此时 a∧ （ b∨ c） =a,同时
（ a∧ b） ∨ （ a∧ c） =a因此无论任何情况,皆有 a∧
（ b∨ c） =（ a∧ b） ∨ （ a∧ c） 。 所以 〈 L,〉 是分配格 。
第 7章 格和布尔代数定理 7.2.7 设 〈 L,∧,∨ 〉 为分配格,则 〈 L,∧,∨ 〉
是模格 。
证明 对于任意的 a,b,c∈ L,若 a b,则 a∧ b=a,并有
b∧ (a∨ c)=(b∧ a)∨ (b∧ c)=a∨ (b∧ c)
因此,〈 L,∧,∨ 〉 是模格 。
下面我们讨论补格 。
定义 7.2.5 设 〈 L,∧,∨ 〉 为有界格,a为 L中任意元素,如果存在元素 b∈ L,使 a∨ b=1,a∧ b=0,则称 b
是 a的补元或补 （ complements） 。
第 7章 格和布尔代数补元有下列性质：
（ 1） 补元是相互的,即若 b是 a的补,那么 a也是 b的补 。
（ 2） 并非有界格中每个元素都有补元,而有补元也不一定唯一 。
（ 3）全下界 0与全上界 1互为补元且唯一。
第 7章 格和布尔代数
【 例 7.2.5】 考察图 7.2.3中 Hasse图所示的其格中其元素的补 。
图 7.2.3（ a） 中除 0,1之外 a,b,c均没有补元 。
图 7.2.3（ b） 中 a的补元是 b,b的补元是 a。
图 7.2.3（ c） 中元素 a,b,c两两互为补元,但不唯一 。
图 7.2.3（ d） 中除 0,1之外没有元素有补元 。 事实上,多于两个元素的链除 0,1之外没有元素有补元 。
在有界格中,显然 0是 1的唯一补元,同时 1是 0的唯一补元 。
第 7章 格和布尔代数图 7.2.3
a b
0
1
c
( a )
a b
0
1
( b )
a b
0
1
c
( c )
1
a
b
0
( d )
第 7章 格和布尔代数定义 7.2.6 如果有界格 〈 L,∨,∧ 〉 中每个元素都至少有一个补元，则称 L为补格
（ complementedlattice）。
例 7.2.5中 （ 2）,（ 3） 均是有补格,（ 1）,（ 4）
不是补格 。 多于两个元素的链都不是有补格 。
第 7章 格和布尔代数定理 7.2.8 若 〈 L,∧,∨ 〉 是有补分配格,a∈ L,
其补元是唯一的 。 因此,可用 a′来表示 a的补元 。
证明 采用反证法：若存在 a为 L中一元素,有两补元 b,c,且 b≠c,则
a∨ b＝ a∨ c＝ 1,a∧ b＝ a∧ c＝ 0
由定理 7.2.5有,b＝ c，与前面矛盾。因此 a只有唯一补元 a′。
第 7章 格和布尔代数定理 7.2.9 若 〈 L,∧,∨ 〉 a∈ L，
有 a″=（ a′） ′＝ a。
证明 a″∧ a′=0,a″∨ a′=1,由补元唯一可得 a″=a。
定理 7.2.10 德 · 摩根律,设 〈 L,∨,∧ 〉 是有补分配格,则对 L中任意元素 a,b,有
(1)（ a∧ b） ′=a′∨ b′
（ 2） （ a∨ b） ′＝ a′∧ b′
第 7章 格和布尔代数证明 (1)由于
（ a∧ b） ∧ （ a′∨ b′）
＝ ((a∧ b） ∧ a′)∨ ((a∧ b） ∧ b′)＝ 0
（ a∧ b） ∨ （ a′∨ b′） =（ a∨ a′∨ b′）
∧ （ b∨ a′∨ b′） ＝ 1
因此 a′∨ b′为 a∧ b的补元 。 由补元的唯一性得知：
(a∧ b） ′＝ a′∨ b′
同样可证 （ 2）,其证明留作练习 。
第 7章 格和布尔代数定理 7.2.11 对有补分配格的任何元素 a,b，有 a b
当且仅当 a∧ b′=0当且仅当 a′∨ b=1。
证明 若 a b，则有 a∨ b=b，所以
a∧ b′=(a∧ b′)∨ (b∧ b′)=(a∨ b)∧ b′=b∧ b′=0。
a∧ b′=0，则其对偶式 a′∨ b=1必成立。
若 a′∨ b=1，则 a∨ b=(a∨ b)∧ 1=(a∨ b)∧ (a′∨ b)
=(a∧ a′)∨ b=0∨ b=b。
第 7章 格和布尔代数
7.3 布尔代数定义 7.3.1 设 B是至少有两个元素的有补分配格,则称 B是布尔代数 （ Booleanalgebra） 。
【 例 7.3.1】 〈 {0,1},∧,∨,′〉 是一个布尔代数 。
第 7章 格和布尔代数
【 例 7.3.2】 S≠,则 〈 P(S),∩,∪,∽ 〉 是一个布尔代数。
其中 ∩表示集合的交运算,∪ 表示集合的并运算,∽ 表示集合的为一元求补集的运算（这里的全集是 S）。
布尔代数通常用序组 〈 B,∧,∨,′,0,1〉 来表示 。 其中 ′为一元求补运算 。 为此介绍布尔代数的另一个等价定义 。
第 7章 格和布尔代数定义 7.3.2 〈 B,∧,∨,′〉 是代数系统,B中至少有两个二元元素,∧,∨ 是 B上二元运算,′是一元运算，若 ∧,∨ 满足：
（ 1） 交换律 ;
（ 2） 分配律 ;
（ 3）同一律。存在 0,1∈ B,a∈ B，有
a∧ 1=a,a∨ 0=a;
（ 4） 补元律 。 对 B中每一元素 a,均存在元素 a′，
使 a∧ a′=0,a∨ a′＝ 1,则称 〈 B,∧,∨,′〉 是布尔代数 。
第 7章 格和布尔代数为证定义 7.3.1与定义 7.3.2等价,只需证 B是格,进而由 （ 2）,(3),（ 4） 可断定 B为有补分配格 。 要证 B
是格,据定义 7.1.2,只要证 B满足交换律 （ 已有 ）,结合律和吸收律 。
下证 B满足吸收律 。 a∈ B,有 a∧ 0=0。
第 7章 格和布尔代数
a∧ 0=(a∧ 0)∨ 0 (同一律 )
=（ a∧ 0） ∨ （ a∧ a′） （ 补元律 ）
=a∧ （ 0∨ a′） （ 分配律 ）
=a∧ a′ (同一律 )
=0 （ 补元律 ）
第 7章 格和布尔代数
a,b∈ B,
a∧ (a∨ b)＝ （ a∨ 0） ∧ （ a∨ b） (同一律 )
＝ a∨ （ 0∧ b） （ 分配律 ）
=a∨ 0
=a (同一律 )
类似可证 a∨ （ a∧ b） ＝ a。
因此 B满足吸收律 。 前面已证明由吸收律可推出满足幂等律 。
第 7章 格和布尔代数再证 B满足结合律 。 a,b,c∈ B,可如下证明
a∧ （ b∧ c） ＝ （ a∧ b） ∧ c，
从而对偶地可证 a∨ （ b∨ c） ＝ （ a∨ b） ∨ c。 令
X=a∧ （ b∧ c）,Y=（ a∧ b） ∧ c
那么
a∨ X＝ a∨ (a∧ （ b∧ c） )＝ a （ 吸收律 ）
a∨ Y=a∨ (（ a∧ b） ∧ c)
＝ (a∨ （ a∧ b） )∧ (a∨ （ a∧ c） )（ 分配律 ）
=a∧ a＝ a （ 幂等律 ）
第 7章 格和布尔代数故
a∨ X＝ a∨ Y （ 7.3.1）
a′∨ X=a′∨ （ a∧ （ b∧ c））
＝ (a′∨ a） ∧ （ a′∨ (b∧ c） ) (分配律 ）
=1∧ （ a′∨ (b∧ c） ) (补元律 ）
=（ a′∨ (b∧ c） ) (同一律 )
=（ a′∨ b） ∧ （ a′∨ c） (分配律 ）
a′∨ Y=a′∨ （ (a∧ b） ∧ c)
第 7章 格和布尔代数
=(a′∨ （ a∧ b） )∧ (a′∨ c) (分配律 ）
=（（ a′∨ a） ∧ （ a′∨ b）） ∧ （ a′∨ c） (分配律 ）
=（ 1∧ （ a′∨ b）） ∧ （ a′∨ c） (补元律 ）
=（ a′∨ b） ∧ （ a′∨ c） (同一律 )
故
a′∨ X=a′∨ Y （ 7.3.2）
第 7章 格和布尔代数由式 （ 7.3.1） 和 （ 7.3.2） 得
（ a∨ X） ∧ （ a′∨ X） ＝ （ a∨ Y） ∧ (a′∨ Y)
（ a∧ a′） ∨ X=(a∧ a′） ∨ Y分配律 )
0∨ X=0∨ Y(补元律 ）
X＝ Y（ 同一律 ）
故 a∧ （ b∧ c） ＝ （ a∧ b） ∧ c得证 。
第 7章 格和布尔代数
【 例 7.3.3】 〈 P,∧,∨,,0,1〉 为布尔代数。
这里 P为命题公式集,∧,∨,为合取、析取、否定的真值运算,0,1分别为假命题、真命题。
定义 7.3.3 设 〈 B,∧,∨,′,0,1〉 是布尔代数,
S(B,若 S含有 0,1,且在运算 ∧,∨,′下是封闭的,则称 S
是 B的子布尔代数,记作 〈 S,∧,∨,′,0,1〉 。
第 7章 格和布尔代数图 7.3.1
a
1
b c
f
e
d
0
第 7章 格和布尔代数
【 例 7.3.4】
(1)对任何布尔代数 〈 B,∨,∧,′,0,1〉 恒有子布尔代数 〈 B,∨,∧,′,0,1〉 和 〈 {0,1},∨,∧,′，
0,1〉,它们被称为 B的平凡子布尔代数 。
（ 2）如图 7.3.1给出的布尔代数 S1={1,a,f,0}是子布尔代数,S2={1,a,c,e}不是子布尔代数，因为 0不在 S2中。
关于子布尔代数除了定义外我们还有如下判别定理。
第 7章 格和布尔代数定理 7.3.1 设 〈 B,∧,∨,′,0,1〉 是布尔代数，
S B且 S≠,a,b∈ S,a∨ b∈ S,a′∈ S,则 S是 B的子布尔代数，记作 〈 S,∧,∨,′,0,1〉 。
证明 a,b∈ S,则 a′,b′∈ S,(a′∨ b′)′=a∧ b∈ S。
因为 S≠,所以存在 a∈ S，因此 a′∈ S,所以
a∧ a′=0∈ S和 a∨ a′=1∈ S。
第 7章 格和布尔代数定义 7.3.4 设 〈 B,∧,∨,′,0,1〉 和
〈 B*,∩,∪,∽,0,1〉 是两个布尔代数，若存在映射 f,B→ B*满足，对任何元素 a,b∈ B，有
f（ a∧ b） ＝ f（ a） ∩f（ b） （ 7.3.4）
f（ a∨ b） =f（ a） ∪ f（ b） （ 7.3.5）
f（ a′） =∽ (f(a)) （ 7.3.6）
则称 f是 〈 B,∧,∨,′,0,1〉 到 〈 B*,∩,∪,
∽,0,1〉 的布尔同态。若 f是双射，则称 f是
〈 B,∧,∨,′,0,1〉 到 〈 B*,∩,∪,∽,0,1〉
的布尔同构。
第 7章 格和布尔代数下面讨论有限布尔代数的表示定理 。
定义 7.3.5 设 B是布尔代数,如果 a是元素 0的一个覆盖,则称 a是该布尔代数的一个原子 （ atoms） 。
例如图 7.3.1中 d,e,f均是原子 。 实际上,在布尔代数中,原子是 B-{0}的极小元,因为原子与 0之间不存在其它元素 。
关于布尔代数的原子我们有以下性质 。
第 7章 格和布尔代数定理 7.3.2 设 〈 B,∧,∨,′,0,1〉 是布尔代数,
B中的元素 a是原子的充分必要条件是 a≠0且对 B中任何元素 x有
x∧ a=a 或 x∧ a=0 （ 7.3.7）
证明 先证必要性 。 设 a是原子,显然 a≠0。 另设
x∧ a≠a。 由于 x∧ a a,故 0 x∧ a,x∧ a a。 据原子的定义,有 x∧ a＝ 0。
第 7章 格和布尔代数再证充分性。设 a≠0，且对任意 x∈ B，有 x∧ a=a或
x∧ a=0成立。若 a不是原子，那么必有 b∈ B，使 0 b
a。于是,b∧ a＝ b。
因为 b≠0,b≠a,故 b∧ a＝ b与式 （ 7.3.7） 矛盾 。 因此 a只能是原子 。
第 7章 格和布尔代数定理 7.3.3 设 a,b为布尔代数
〈 B,∨,∧,′,0,1〉 中任意两个原子，则 a=b或
a∧ b=0。
证明 分两种情况来证明 。
（ 1） 若 a,b是原子且 a∧ b≠0,则
0＜ a∧ b a (因为 a是原子,所以 a=a∧ b)
0＜ a∧ b b (因为 b是原子,所以 b=a∧ b)
故 a=b。
第 7章 格和布尔代数
（ 2）若 a,b是原子且 a≠b由原子的性质可知,a∧ b≠a,a∧ b≠b(否则 a b或 b a)。用反证法，若
a∧ b≠0，则
0＜ a∧ b＜ a,0＜ a∧ b＜ b
与 a,b为原子矛盾,故 a∧ b=0。
第 7章 格和布尔代数定义 7.3.6 设 B是布尔代数,b∈ B,定义集合
A(b)={a|a∈ B,a是原子且 a b}。
例如，图 7.3.1中
A(b)={d,f},A(c)={e,f},A(0)=,A(1)={d,e,f}。
引理 1 设 〈 B,∨,∧,′,0,1〉 是一有限布尔代数，则对于 B中任一非零元素 b，恒有一原子 a∈ B,
使 a b。
第 7章 格和布尔代数证明 b∈ B且 b≠0:
若 b为原子,有 b b,则命题已得证 。
若 b不是原子,则必有 b1∈ B,0＜ b1＜ b。
若 b1不是原子,存在 b2使 0 b2 b1 b,对 b2重复上面的讨论 。
因为 B有限,这一过程必将中止,上述过程中产生
0? b2 b1 b
即存在 br,br为原子,且 0 br b,否则此序列无限长 。
引理 1得证 。
第 7章 格和布尔代数引理 2 设 〈 B,∨,∧,′,0,1〉 是一有限布尔代数,b为 B中任一非零元素，设 A(b)={a1,a2,?,am}，
则 b=a1∨ a2∨? ∨ am= a,且表达式唯一。
证明 令 c=a1∨ a2∨? ∨ am。 要证 b=c。
由于 ai b（ i=1,2,?,m）,因为 c是 A(b)中最小上界,
所以 c b。
欲证 b c。 据定理 7.2.11,只要证 b∧ c′=0。
()a A b
第 7章 格和布尔代数用反证法,设 b∧ c′≠0,从而存在原子 a使得
0 a b∧ c′,所以有 a b,a c′。
由于 a b,a是原子,因此 a为 a1,a2,?,am之一,
故 a c。
所以 a c∧ c′=0,与 a是原子矛盾 。 因此 b∧ c′=0,即
b c。 b=c=a1∨ a2∨? ∨ am得证 。
第 7章 格和布尔代数下证唯一性 。
设 b也可表示为 b= a,S={b1,b2,?,bj},b1,b2,?,bj是原子。
需证 S=A(b)。
若 q∈ S,有 q b,所以 q∈ A(b),因此 S A(b)。
若 q∈ A(b)，
有 qb,q=q∧ b=q∧ a∈ S a= a∈ S (q∧ a)。
由定理 7.3.3知,存在 a0∈ S,使 q=a0,所以 q∈ S。 故
S=A(b),引理 2得证 。
aS
aS aS
第 7章 格和布尔代数定理 7.3.4 若 a是原子,则 a b∨ c的充分必要条件是 a b或 a c。
证明 先证必要性 。
若 a是原子，且 a b∨ c,不妨设 x≤ b，因为 a是原子，
由定理 7.3.3有 a∧ b=0。
因为 a b∨ c,所以有
a=a∧ (b∨ c)=(a∧ b)∨ (a∧ c)=(a∧ c),故 a c,得证。充分性显然。
第 7章 格和布尔代数定理 7.3.5 设 〈 B,∨,∧,′,0,1〉 为有限布尔代数，令 A={a|a∈ B且 a是原子 }，则 B同构于布尔代数
〈 P(A),∪,∩,∽,,A〉 。
证明 构造映射 f,B→ P(A),使得对任意 b∈ B,f(b)=A(b)。
(1)证明 f为一单射 。 若 f(b)=f(c),有 A(b)=A(c)。 由引理 2得 b= a∈ A(b),
c= a∈ A(c) a,所以 b=c,故 f是单射 。
()a A b
()a A c
第 7章 格和布尔代数
（ 2）证明 f S∈ P(A),则 S A。
令 b= a∈ S a,由引理 2得 b= a∈ A(b) a。
由唯一性有 S=A(b)=f(b)。若
S= =A(b)=f(b),所以 f为满射得证。
aS bS
第 7章 格和布尔代数
(3)接着要证明 f保持运算，即 f满足式（ 7.3.4）、
式（ 7.3.5）和式（ 7.3.6）。
设 b,c为 B中任意两个元素且 b≠0,c≠0。 对任意的原子 x,x∈ A(b∧ c) x b∧ c x b且 x c x∈ A(b)且
x∈ A(c) x∈ A(b)∩A(c) 所以 A(b∧ c)=A(b)∩A(c),即
f(b∧ c)=f(b)∩f(c)。
第 7章 格和布尔代数对任意的原子 x,
x∈ A(b∨ c) x b∨ c x b或 x c x∈ A(b)
或 x∈ A(c) x∈ A(b)∪ A(c)
所以 A(b∨ c)=A(b)∪ A(c),即 f(b∨ c)=f(b)∪ f(c)。
b∈ B,且 b≠0,对任意的原子 x,
x∈ A(b′) x∧ b=0 x∧ b≠x x≤b x A(b) x∈∽ A(b)
所以 A(b′） =∽ A(b),即 f(b′)=∽ (f(b)),定理得证 。
第 7章 格和布尔代数本定理有如下推论：
推论 1 若有限布尔代数有 n个原子,则它有 2n个元素 。
推论 2 任何具有 2n个元素的布尔代数互相同构 。
注意 这一定理对无限布尔代数不能成立 。
根据这一定理,有限布尔代数的基数都是 2的幂 。
同时在同构的意义上对于任何 2n,n为自然数,仅存在一个 2n元的布尔代数,如图 7.3.2中的 Hasse图所示的 1
元,2元,4元,8元的布尔代数 。
第 7章 格和布尔代数图 7.3.2
第 7章 格和布尔代数
7.4 例题选解
【 例 7.4.1】 设 〈 L,≤〉 是格,a,b,c∈ L,a≤b，证明：
(a∨ b∧ c))∨ c=(b∧ (a∨ c))∨ c
证明 因为 a≤b，且 a≤a∨ c，所以 a≤b∧ (a∨ c)，故
a∨ c≤（ b∧ (a∨ c)） ∨ c。由格的吸收律、结合律知
（ a∨ b∧ c)） ∨ c=a∨ c，所以
（ a∨ (b∧ c)） ∨ c≤（ b∧ (a∨ c)） ∨ c
第 7章 格和布尔代数又由格的分配不等式知 （ b∧ (a∨ c)） ∨ c≤（ b∨ c）
∧ (a∨ c),而
（ b∨ c） ∧ (a∧ c)≤a∨ c=（ a∨ (b∧ c)） ∨ c
故
（ a∨ (b∧ c)） ∨ c=(b∧ (a∨ c))∨ c
第 7章 格和布尔代数
【 例 7.4.2】 设 〈 L,≤〉 是格,a,b,c,d∈ L,证明：
(a∧ b)∨ (c∧ d)≤（ a∨ c） ∧ (b∨ d）
证明 a,b,c,d∈ L,因为 a∧ b≤a,a∧ b≤b,c∧ d≤c，
c∧ d≤d,所以
(a∧ b)∨ (c∧ d)≤a∨ c,(a∧ b)∨ (c∧ d)≤b∨ d
因此
(a∧ b)∨ (c∧ d)≤（ a∨ c） ∧ （ b∨ d）
第 7章 格和布尔代数
【 例 7.4.3】 一个格 〈 A,≤〉 是分配格 iff a,b,c∈ A
有 (a∨ b)∧ c≤a∨ (b∧ c)。
证明 先证必要性：设 〈 A,≤〉 是分配格 。
a,b,c∈ A,由 a∧ c≤a，
b∧ c≤b∧ c,可得
（ a∧ c） ∨ （ b∧ c） ≤a∨ （ b∧ c）
而 （ a∨ b） ∧ c=（ a∧ c） ∨ （ b∧ c）
所以 （ a∨ b） ∧ c≤a∨ (b∧ c)
第 7章 格和布尔代数
a,b,c∈ A有
(a∨ b)∧ c≤a∨ (b∧ c)，则有
(a∨ b)∧ c =((a∨ b)∧ c） ∧ c≤（ a∨ (b∧ c)） ∧ c
=((b∧ c)∨ a） ∧ c≤（ b∧ c） ∨ （ a∧ c）
（ b∧ c） ∨ （ a∧ c） ≤(a∨ b)∧ c,因此有
(a∨ b)∧ c=（ b∧ c） ∨ （ a∧ c）
即 〈 A,≤〉 是分配格。
第 7章 格和布尔代数
【 例 7.4.4】 设 G是 30的因子集合,G上关系,|” 是整除关系 。
(1)画出 〈 G,|〉 的 Hasse图 。
(2)画出 〈 G,|〉 的所有元素个数大于等于 4的不同构的子格的 Hasse图 。
(3)上面各子格都是什么格？ （ 分配格,模格,有补格 ） 。
(4)上面各子格中有布尔代数吗？ 若有,指出并给出原子集合 。
第 7章 格和布尔代数图 7.4.1
30
10
3
1
15
5
6
2
第 7章 格和布尔代数解
（ 1） G={1,2,3,5,6,10,15,30},其哈斯图
7.4.1
(2)〈 G,|〉 的所有元素个数大于等于 4的不同构的子格的 Hasse图见图 7.4.2。
（ 3） 所有的子格均是分配格,模格 。 图 7.4.2
（ b）,（ f） 所示的格还是有补格 。
（ 4）图 7.4.2（ b）、（ f）所示的格是布尔代数。
其中，图（ b）的原子集合为 {15,6}，图（ f）的原子集合为 {2,3,5}。
第 7章 格和布尔代数图 7.4.2
30
10
3
1
15
5
6
2
30
3
1
15 10
5
30
1
15 6
30
1
15
5 3
30
15 6
1
1
5
15
30
( a ) ( b )
( c )
( f )( e )( d )
3
第 7章 格和布尔代数习 题 七
1,图 7.1所示的偏序集，哪一个是格？并说明理由。
第 7章 格和布尔代数图 7.1
( a ) ( b ) ( c ) ( d ) ( e ) ( f )
第 7章 格和布尔代数
2,对格 L中任意元素 a,b,c,d,证明：
（ 1） a b,a c当且仅当 a b∧ c。
（ 2） a c,b c当且仅当 a∨ b c。
（ 3） a∨ (a∧ b)=a。
（ 4） 若 a b c,d∧ c＝ a,则 d∧ b＝ a。
（ 5） 若 a b c,d∧ a＝ c,则 d∧ b＝ c。
（ 6） （ a∧ b） ∨ （ a∧ c） a∧ （ b∨ c） 。
（ 7） （（ a∧ b） ∨ （ a∧ c）） ∧ （（ a∧ b）
∨ （ b∧ c）） =a∧ b。
第 7章 格和布尔代数
（ 8）（ a∧ b） ∨ （ b∧ C） ∨ （ c∧ a a∨ b
∧ （ b∨ C） ∧ （ c∨ a）。
(9)若 a b,则有 (a∨ (b∧ c))∧ c=(b∧ (a∨ c))∧ c。
(10)a∧ b a且 a∧ b b当且仅当 a与 b是不可比较的,
即 a b,b a都不能成立 。
第 7章 格和布尔代数
3,证明：格 L的两个子格的交仍为 L的子格 。
4.设 a,b为格 L中的两个元素,证明：
S={x|x∈ L且 a x b}可构成 L的一个子格 。
5.设 f为格 L1到格 L2的同态映射,证明 f的同态像是
L2的子格 。
6,设 〈 L,∨,∧ 〉 为格,a∈ L,令 La={x|x∈ L且
x≤a},Ma={x|x∈ L 且 a≤x},则 〈 La,∨,∧ 〉,〈 Ma,
∨,∧ 〉 都是 L的子格 。
7,证明定理 7.2.2。
8.判断图 7.1所示的 Hasse图中的格各是什么格 。
（ 分配格,模格,补格,布尔格 ）
第 7章 格和布尔代数
9.证明定理 7.2.10中的 (2)。
10,证明：在有界分配格中,有补元的所有元素可以构成一个子格 。
11,设 〈 L,∧,∨ 〉 为有补分配格,a,b为 L中任意元素,证明,b′ a′当且仅当 a∧ b′=0当且仅当 a′∨ b=1。
12,设 a是布尔代数 〈 B,∧,∨,′,0,1〉 的原子,x为 B中任一元素,则 x或 a x′,但不兼而有之 。
13,设 a,b为布尔代数 B中任意元素,求证,a＝ b
当且仅当 （ a∧ b′） ∨ （ a′∧ b） ＝ 0。
第 7章 格和布尔代数
14.证明,在布尔同态的定义 （ 定义 7.3.4） 中,式
（ 7.3.4） 和式 （ 7.3.5） 两条件之一可省去 。
15.设 f为布尔代数 〈 A,∧,∨,′,0,1〉 到布尔代数 〈 B,∧,∨,′,0,1〉 的布尔同态,则
f（ 0） =0,f（ 1） =1。
16.设 〈 B,∧,∨,′,0,1〉 为布尔代数,定义
B a,b∈ B，
a b=（ a∧ b′） ∨ （ a′∧ b）
a*b=a∧ b
证明 〈 B,,*〉 ） 为一含幺交换环 。
第 7章 格和布尔代数
17,G是 12的因子集合,"|"是 G上的整除关系 。
(1)画出 〈 G,|〉 的 Hasse图 。
(2)画出 〈 G,|〉 的所有元素个数大于等于 4的子格的
Hasse图 。
(3)上述各子格都是什么格？ （ 分配格,模格,有补格 ）
(4)上述各子格中有布尔代数吗？ 若有,指出并给出原子集合 。
第 7章 格和布尔代数
18,设 G是 24的因子集合,"|"是 G上的整除关系 。
(1)画出 〈 G,|〉 的 Hasse图 。
(2)画出 〈 G,|〉 的所有 5元素子格的 Hasse图 。
(3)上述子格各是什么格？ （ 分配格,模格,有补格 ）
(4)〈 G,|〉 是布尔代数吗？ 若是,请给出原子集合 。
