格与分配格离 散 数 学哈尔滨理工大学本科生课程计算机系第六章 格与布尔代数这一章将介绍另一类代数系统，这就是格。
格论大体上是在 1935年左右形成的，它不仅是代数学的一个分支，而且在近代解析几何，半序空间等方面也都有重要的作用。我们在这里只介绍格的一些基本知识以及几个具有特别性质的格 —— 分配格、有补格。
学习,格与布尔代数,
这一章的要求一、学习目的与要求本章在已经学过的群、环和域几个代数系统的基础上，进一步学习格这个新的代数系统，并且学习在计算机科学中有重要应用的布尔代数。
通过本章的学习，使学生进一步了解格的基本概念，掌握布尔代数的运算规律，为学习数字逻辑、计算机硬件设计等课程打下数学基础。
二、知识点
1,格的概念,偏序集上的并运算,
偏序集上的交运算 。
2,分配格,有补格；
3,布尔代数,Stone表示定理及其推论,布尔表达式,布尔函数,开关代数的概念 。
三、要求
1,识记根据哈斯图识别是否是格,分配格,有补格,
模格,布尔格,布尔代数 。
2,领会格同构的概念,分配格与模格的关系,格的全上界的唯一性证明,Stone表示定理,布尔表达式,析取范式和合取范式 。
3,简单应用开关代数 。
复习
1.偏序集定义 3-12.1：设 A是一个集合，如果 A上的一个关系 R满足自反性、反对称性和传递性，则称 R是 A上的一个偏序关系，记作 ≤ 。 <A,≤ >称作偏序集。
2,最大元、最小元定义 3-12.6：设 <A,≤>是一个偏序集，且 B是 A的子集，
若有某个元素 b?B，对于 B中的每一个元素 x，有 x≤b，则称 b为 <B,≤>的最大元；同理，若有某个元素 b?B，对于 B
中的每一个元素 x，有 b≤x，则称 b为 <B,≤>的最小元。
3.哈斯图定义 3-12.2：在偏序集 <A,≤>中，如果 x,y∈ A,x≤y，
x≠y，且没有其他元素 z，使 x≤z,z≤y，则称元素 y盖住元素 x。记 COVA={<x,y>|x,y∈ A,y盖住 x}。
对于给定偏序集 <A,≤>，它的盖住关系是唯一的，
所以可用盖住的性质画出偏序集合图，或称哈斯图，其作图规则为：
(1)小圆圈代表元素。
(2)如果 x≤y且 x≠y，将代表 y的小圆圈画在代表 x的小圆圈之上。
(3)如果 <x,y>∈ COVA，则在 x与 y之间用直线连结。
4,上界、下界定义 3-12.7：设 <A,≤>是一偏序集，对于 B?A，如有 a∈ A，
且对任意元素 x∈ B，都有 x≤a，则称 a为 B的上界。同理，对任意元素 x∈ B，都有 a≤x，则称 a为 B的下界。
5,上确界、下确界定义 3-12.8：设 <A,≤>是一偏序集且 B?A,a是 B的任一上界，若对 B的所有上界 y均有 a≤y，则称 a是 B的最小上界 (上确界 )，记作 LUBB。同理,b是 B的任一下界，若对 B的所有下界 z均有 z≤b，则称 b是 B的最大下界 (下确界 )，记作 GLBB。
6-1 格的概念在第三章中，我们介绍了偏序集的概念，偏序集就是由一个集合 A以及 A上的一个偏序关系,≤”所组成的一个代数系统 <A,≤>。我们知道，对于偏序集来说，它的任一个子集不是必定存在最小上界或最大下界的。
例如，在由图 6-1.1所示的偏序集中,{a,b}的最小上界是 c，但没有最大下界； {e,f}的最大下界是 d，但没有最小上界。
今后，我们把 {a,b}的最小上界（最大下界）
称为元素 a,b的最小上界（最大下界）。
由图 6-1.2所示的偏序集都有这样一个共同的特性，那就是在这些偏序集中，任何两个元素都有最小上界和最大下界。我们把具有这种性质的偏序集称作格。
一、格的定义称为正整数格练习 242页（ 1）
定义 6-1.1 设 <A,≤>是一个偏序集，如果 A中任意两个元素都有最小上界和最大下界，则称 <A,≤>为 格 （ lattice）。
例 1 设 I+是所有正整数的结合，在 I+上定义一个二元关系 |，
对于 a,b?I+,a|b当且仅当 a整除 b。容易验证 |是 I+上的一个偏序关系，故 < I+,|>是偏序集。由于该偏序集中任意两个元素的最小公倍数、最大公约数就是这两个元素的最小上界和最大下界，且?I+，因此 < I+,|>是格。
例 2 设?(S)是给定集合 S的幂集,<?(S),?>是一个偏序集。由于?(S)中的任意两个元素 S1,S2，它们的最大下界为 S1∩ S2,最小上界为 S1∪ S2,且(S),所以 <?(S)，
>是格。
例 3 给定 S={a,b},?(S)={?,{a},{b},{a,b}}，那么，格
<?(S),?>如图 6-1.3所示。
二、由格 <A,≤>所诱导的代数系统定义 6-1.2 设 <A,≤>是一个格,如果在上定义两个二元运算 ∨ 和 ∧,使得对于任意的 a,b? A,a∨ b等于 a和 b的最小上界,a∧ b等于 a和 b的最大下界,那么,就称 <A,∨,∧ >为由格
<A,≤>所诱导的代数系统。二元运算 ∨ 和 ∧ 分别称为 并运算 和交运算 。
通常用 a∨ b表示 {a,b}的上确界,用 a∧ b 表示 {a,b}的下确界,∨ 和 ∧ 分别称为 保联 (join)和 保交 (meet)运算。由于对任何 a,b,因为在格中,a∨ b及 a∧ b都是 A中确定的成员，因此 ∨,∧ 均为 A上的运算。
设 S={a,b},?(S) ={?,{a},{b},{a,b}}由格 <?(S),? >
诱导的代数系统为 <?(S),∨,∧ >。其中 ∨ 为 集合的并运算和
∧ 为 集合的交运算。如表 6-1.1所示。
三、子格定义 6-1.3 设 <A,≤>是一个格,由格 <A,≤>所诱导的代数系统为 <A,∨,∧ >。设 B?A且 B≠?，如果 A中的两个运算 ∨ 和 ∧ 关于 B是封闭的，则称 <B,≤>是
<A,≤>的子格。
例 4 例 1给出了一个具体的格 < I+,|>,由它诱导的代数系统为 < I+,∨,∧ >,其中 a∨ b就是 a,b的最小公倍数,a∧ b就是 a,b的最大公约数。因为任何两个偶数的最大公约数和最小公倍数都是偶数，所以，
如果取 E+是正偶整数的全体，那么 ∨ 和 ∧ 关于 E+是封闭的，因此称 < E+,|>是 < I+,|>的子格。
必须指出，对于格 <A,≤>，设 B是 A的非空子集，尽管 <B,≤>必定是一个偏序集，然而 <B,≤>不一定是格，而且即使 <B,?>是格，也不一定是 <A,≤>的子格。
例题 1 设 <S,≤>是一个格，任取 a?S，构造 S的子集
T为：
T={x|x?S且 x≤a}
则 <T,≤>是 <S,≤>的一个子格。
解 对于任意的 x,y?T，必有 x≤a 和 y≤a，
所以 x∨ y≤a,x∧ y≤a
而 x∨ y?S,x∧ y?S
故 x∨ y?T,x∧ y?T
因此 <T,≤>是 <S,≤>的一个子格。
同样地，可以证明，如果取 Q={x|x?S且 a≤x}，
则 <Q,≤>也是 <S,≤>的一个子格。
四、格所诱导的代数系统的一些性质
1,对偶原理在讨论格以及格所诱导的代数系统的一些性质之前，先介绍格的对偶原理。
对偶这个概念在日常生活中也是屡见不鲜的，
譬如，在不同国家的交通规则可能不同，但基本上是两种，一种是以左为准，另一种是以右为准，那么，在以左为准的交通规则中，如果将左换成右，
右换成左就可得到另一种以右为准的交通规则，这里，左和右就是一种对偶的概念。
格对偶原理,设 <A,≤>是一个偏序集,在 A上定义一 个二元关系 ≤R,使得对于 A中任意两个元素 a,b都有关系 a ≤Rb当且仅当 b ≤ a,于是 <A,≤R>也是一个偏序集。把 <A,≤>和 <A,≤R>称为相互对偶的 (哈斯图相互颠倒 )。
可以证明，若 <A,≤>是格，则 <A,≤R>也是格。
称 ≤R是 ≤的逆关系。记为 ≥。
格对偶原理可以叙述为：设 P是对任意格都真的命题，如果在命题 P中把 ≤换成 ≥,∨ 换成 ∧,∧ 换成
∨,就得到另一个命题 P’，我们把 P’称为 P的对偶命题，则 P’对任意格也是真的命题。
定理 6-1.1 在一个格 <A,≤>中，对任意两个元素
a,b?A都有
a ≤ a∨ b b ≤ a∨ b
a∧ b ≤ a a∧ b ≤ b
证明思路,因为 a和 b的并是 a的一个上界，所以
a ≤ a∨ b
同理 b ≤ a∨ b
由对偶原理，即得 a∧ b ≤ a
a∧ b ≤ b?
2,格所诱导的代数系统的一些性质定理 6-1.2 在一个格 <A,≤>中，对于任意元素 a,b,c,d?A,
如果 a ≤ b 和 c ≤ d
则 a∨ c ≤ b∨ d
a∧ c ≤ b∧ d
证明 因为 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
推论 在一个格 <A,≤>中，对于任意元素 a,b,c?A,如果 b ≤
c,则 a∨ b ≤ a∨ c,a∧ b ≤ a∧ c(保序性 )。
证明 只要在定理 6-1.2中将 a代替 b,b代替 c,c代替 d，即可得证。
定理 6-1.3 在一个格 <A,≤>中,由格 <A,≤>所诱导的代数系统为 <A,∨,∧ >,则对于任意元素 a,b,c,d?A,有
(1) a∨ b= b∨ a
a∧ b= b∧ a
(2) a∨ (b∨ c)=(a∨ b)∨ c
a∧ (b∧ c)=(a∧ b)∧ c
(3) a∨ a=a
a∧ a=a
(4) a∨ (a∧ b)=a
a∧ (a∨ b)=a
（交换律）
（结合律）
（幂等律）
（吸收律）
（ 2）第一式：先证 [(a∨ b)∨ c] ≤[a∨ (b∨ c)]
根据定理 1（ x ≤ x∨ y,y ≤ x∨ y）
b ≤ b∨ c ≤ a∨ (b∨ c ),a ≤ a∨ (b∨ c )
根据定理 2（ x1 ≤ x2且 y1 ≤ y2?x1∨ y1 ≤ x2∨ y2）
a∨ b ≤ a∨ (b∨ c )
又因为
c ≤(b∨ c ) ≤ a∨ (b∨ c )
再根据定理 2
(a∨ b)∨ c ≤ a∨ (b∨ c )
再证 [a∨ (b∨ c)] ≤[(a∨ b)∨ c]
b ≤ a∨ b,c ≤ c? b∨ c ≤ (a∨ b)∨ c
a ≤ (a∨ b) ≤ a∨ (b∨ c )
a∨ (b∨ c) ≤ a∨ (b∨ c )?
证明思路,（ 1）格中任何两个元素 a,b的最小上界
（最大下界）当然等于 b,a的最小上界（最大下界），
故 a∨ b=b∨ a（ a∧ b=b∧ a）
（ 3）由定理 6-1.1可得 a ≤ a ∨ a
由自反性可知 a ≤ a
由此可得 a∨ a ≤ a
因此 a∨ a= a
利用对偶原理，即得 a∧ a=a
（ 4）由定理 6-1.1可得
a ≤ a ∨ （ a∧ b）
因为 a ≤ a和 a∧ b ≤ a
所以 a ∨ （ a∧ b） ≤ a
因此 a∨ (a∧ b)=a
利用对偶原理，即得 a∧ (a∨ b)=a
练习 242页（ 3）
例 6 设 <N,≤>是一个偏序集，这里 N是自然数集,≤是普通的数与数之间的,小于等于,关系，定义
a∨ b =max{a,b} （ 取大运算）
a∧ b =min {a,b} （ 取小运算）
则 <N,≤>是一个格。由此格诱导的代数系统为 <N,∨,∧ >
可以证明，该代数系统的两个运算满足定理 6-1.3的 4个运算律。
在此代数系统中，任意两个数 a和 b的最大值（最小值）与 b
和 a的最大值（最小值）是相等的，因此，并运算和交运算都是可交换的；又因为 max(max(a,b),c)和 max(a,max(b,c)) 都是三个数 a,b,c中的最大值，所以在 <N,∨,∧ >中并运算是可结合的，
同理,min(min(a,b),c)=min(a,min(b,c)),说明交运算的结合性；由于 max(a,a)=min(a,a)=a，所以幂等性成立；又由于
max(a,min(a,b)) =a和 min(a,max(a,b))=a，因此，吸收性也成立。
五、由代数系统确定的格引理 6-1.1 设 <A,∨,∧ >是一个代数系统,其中 ∨,∧
都是二元运算且满足吸收律，则 ∨ 和 ∧ 都满足幂等律。
证明思路,由吸收律：
a∨ (a∧ b)=a (1)
a∧ (a∨ b) =a (2)
将 (1)中的 b取为 (a∨ b),得 a∨ (a∧ (a∨ b))=a
再由得 a∨ a=a
同理可证 a∧ a=a?
定理 6-1.4 设 <A,∨,∧ >是一个代数系统,其中
∨,∧ 都是二元运算且满足交换律、结合律和吸收律，
则 A上存在偏序关系 ≤,使 <A,≤>是一个格。
证明思路,分四部分内容来证明：
(1) 定义二元关系 ≤,a ≤ b当且仅当 (a∧ b)=a
(2) 证明是偏序关系（证：自反、反对称和传递） ；
(3) 证明 a∧ b是 a和 b的最大下界（下确界）；
(4) 由 ∨,∧ 满足 交换律和吸收律，证明 a ∨ b是 a
和 b的最小上界。
六、在格 <A,≤>中并和交运算的性质定理 6-1.5 在一个格 <A,≤>中,对于任意的 a,b,c?A,
都有,a∨ (b∧ c) ≤ (a∨ b)∧ (a∨ c)
(a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c)
第 1式证明思路,由定理 6-1.1 a ≤ a∨ b,a ≤ a∨ c,
再由定理 6-1.2和幂等律得
a=a∧ a ≤ (a∨ b)∧ (a∨ c) (1)
另外,由于 b∧ c ≤ b ≤ a∨ b 和 b∧ c ≤ c ≤ a∨ c
所以 b∧ c=b∧ c∧ b∧ c ≤ (a∨ b)∧ (a∨ c) (2)
再对 (1)式和 (2)式应用定理 6-1.2得
a∨ (b∧ c) ≤ (a∨ b)∧ (a∨ c)
第 2式证明由对偶原理从上式直接可得。
定理 6-1.6 设 <A,≤>是一个格,那么，对于任意的
a,b?A,都有：
a ≤ b?(a∧ b)=a?(a∨ b)=b
a ≤ b?(a∧ b)=a证明思路：
(1)先证 a ≤ b? (a∧ b)=a
由 a ≤ b和 a ≤ a,根据定理 6-1.2得 a ≤ a∧ b
又根据 a∧ b的定义,有 a∧ b ≤ a
由二元关系 ≤的反对称性得,a∧ b = a
(2) 再证 (a∧ b)=a?a ≤ b
设 a∧ b=a，则 a=a∧ b ≤ b,这就证明了
(a∧ b)=a?a ≤ b
综合 (1)和 (2)得,a ≤ b?(a∧ b) =a?
定理 6-1.7 设 <A,≤>是一个格,那么，对于任意的
a,b,c?A,都有：
a ≤ c?a∨ (b∧ c) ≤ (a∨ b)∧ c
证明思路：
(1)先证 a ≤ c? a∨ (b∧ c) ≤ (a∨ b)∧ c
根据定理 6-1.6有 a ≤ c?(a∨ c)=c
根据定理 6-1.5有 a∨ (b∧ c) ≤(a∨ b)∧ (a∨ c)
a∨ (b∧ c) ≤(a∨ b)∧ c
(2) 再证 a∨ (b∧ c) ≤ (a∨ b)∧ c?a ≤ c
若 a∨ (b∧ c) ≤ (a∨ b)∧ c
则 a ≤ a∨ (b∧ c) ≤ (a∨ b)∧ c ≤ c 即 a ≤ c
综合 (1)和 (2)得,a ≤c?a∨ (b∧ c) ≤ (a∨ b)∧ c?
练习 242页
（ 4）
推论 设 <A,≤ >是一个格,那么，对于任意的
a,b,c?A,都有：
(a∧ b)∨ (a∧ c) ≤ a∧ (b ∨ (a∧ c) )
a∨ (b∧ (a∧ c) ) ≤ (a∨ b)∧ (a∨ c)
证明思路：
利用 a∧ c ≤ a,a ≤a∨ c 证第 1式第 2式是第 1式的对偶。
七、格同态、格同构定义 6-1.4 设 <A1,≤1>和 <A2,≤2>是两个格,那么,
由他们分别诱导的代数系统为 <A1,∨ 1,∧ 1>和
<A2,∨ 2,∧ 2>,如果存在着一个从 A1到 A2的映射 f，
使得对于任意的 a,b?A1,有
f(a∨ 1 b)= f(a)∨ 2 f(b)
f(a ∧ 1 b)= f(a)∧ 2 f(b)
则称 f为从 <A1,∨ 1,∧ 1> 到 <A2,∨ 2,∧ 2> 的格同态，
亦可称 < f(A1),≤2> 是 <A1,≤1> 的 格同态象。此外，
当 f是双射时，则称 f为从 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>
的格同构，亦可称 <A2,≤2>和 <A1,≤1>两个格是同构的 。
定理 6-1.8 设 f是格 <A1,≤1>到 <A2,≤2>的格同态,
则对于任意的 x,y?A1,若 x ≤1y,必有,f(x) ≤2f(y) 。
证明思路,因为 x ≤1y,所以 x∧ 1y=x
f(x∧ 1y) = f(x) f(x)∧ 2f(y) = f(x)
故 f(x) ≤2f(y)?
定理 6-1.8告诉我们格同态是保序的。但是定理 6-1.8
的逆命题是不一定成立的。
定理 6-1.9 设 <A1,≤1>和 <A2,≤2>是 两 个格,f是从 A1
到 A2的双射，则 f是从 <A1,≤1>到 <A2,≤2>的格同构，
当且仅当对任意的 a,b?A1,都有,a≤1b?f(a)≤2f(b)
证明,(1) 先证 f是 <A1,≤1>到 <A2,≤2>的格同构
a ≤1b?f(a) ≤2f(b)
由定理 6-1.8,若 a ≤1b,必有,f(a) ≤2f(b) (?)
反之，设 f(a) ≤2f(b),(?)
则 (格同构大条件 ) f(a)∧ 2f(b)= f(a∧ 1b)= f(a)
由于 f是双射，所以 a∧ 1b=a
故,a ≤1b
因此,a ≤1b?f(a) ≤2f(b)
(2) 再证 a≤1b?f(a)≤2f(b)?
f是 <A1,≤1>到 <A2,≤2>的格同构设对任意的 a,b?A1,a≤1b?f(a)≤2f(b)
设 a∧ 1b=c，则 c ≤ 1a,c ≤ 1b,
于是 f(a∧ 1b)=f (c),f(c) ≤ 2f(a),f(c) ≤ 2f(b)
故有 f(c) ≤ 2f(a)∧ 2f(b)
令 f(a)∧ 2f(b)=f(d)
则 f(c) ≤ 2f(d),f(d) ≤ 2f(a),f(d) ≤ 2f(b)
故有 d≤1a,d≤1b，于是 d≤1a∧ 1b,即 d≤1c，
所以 f(d) ≤ 2f(c)
因此 f(d)=f(c) 即 f(a∧ 1b)=f(a)∧ 2f(b)
类似地可证,f(a∨ 1b)=f(a)∨ 2 f(b) 格同构证毕。
练习,P242 (1)(2)
一、分配格定义 6-2.1 设 <A,∨,∧ > 是由格 <A,≤>是所诱导的代数系统。如果对任意的 a,b,c?A，满足：
a∧ (b∨ c)= (a∧ b)∨ (a∧ c)
a∨ (b∧ c)= (a∨ b)∧ (a∨ c)
则称 < A,≤> 是分配格 。
在定理 6-1.5中我们已经证明，在格 <A,≤ >中,对于任意的 a,b,c?A,都有,a∨ (b∧ c) ≤ (a∨ b)∧ (a∨ c)
和 (a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c)
成立。当上述两个式子中的等号成立的时候，我们就得到一类特殊的格。
6-2 分配格例 1 设 S={a,b,c}，则 <?(S),∪,∩ >是由格
<?(S),?>所诱导的代数系统。这个格所对应的哈斯图如图 6-2.1所示。
容易验证，对于任意的 P,Q,R(S)，有
P∩(Q∪R)=(P∩Q)∪(P∩R)
P∪(Q∩R)=(P∪Q)∩(P∪R)
成立。所以 <?(S),?>是一个分配格。
例 2 如图 6-2.2中所示的两个格都不是分配格。
这是因为，在图 6-2.2(a)中,b∧ (c∨ d )=b∧ a=b
而 (b∧ c)∨ (b∧ d) = e∨ e=e
所以 b∧ (c∨ d )? (b∧ c)∨ (b∧ d)
在图 6-2.2(b)中,c∧ (b∨ d )=c∧ a=c
而 (c∧ b)∨ (c∧ d) = e∨ d=d
所以 c∧ (b∨ d )? (c∧ b)∨ (c∧ d)
必须指出，在分配格的定义中，必须是对任意的 a,b,c?A都要满足分配等式，因此，决不能验证格中的某些元素满足分配等式就断定该格是分配格。
譬如，在例 2中，图 6-2.2(b)所示的格中，尽管有
d∧ (b∨ c )=d∧ a=d=e∨ d=(d∧ b)∨ (d∧ c)
b∧ (c∨ d )=b∧ c=e=e∨ e=(b∧ c)∨ (b∧ d)
但它不是分配格。
例 2中给出的两个具有五个元素的格是很重要的，
因为有一个定理证明了如下的结论,一个格是分配格的充要条件是在该格中没有任何子格与这两个五元素格中的任一个同构。 这个定理的证明已超出了本书的范围。
证明 定理的前半部分：
分配格中交对并可分配? 并对交也一定可分配设对任意的 a,b,c?A，
若 a∧ (b∨ c)= (a∧ b)∨ (a∧ c) (交对并可分配 a)
则 (a∨ b)∧ (a∨ c)
=((a∨ b)∧ a)∨ ((a∨ b)∧ c) (交对并可分配 (a∨ b))
=a∨ ((a∨ b)∧ c) (吸收律 )
=a∨ ((a∧ c)∨ (b∧ c)) (交对并可分配 c)
=(a∨ (a∧ c) )∨ (b∧ c) (结合律 )
=a∨ (b∧ c) (吸收律 )（并对交可分配）?
类似的可证明 分配格中并对交可分配?交 对并也一定可分配定理 6-2.1 如果在一个分配格中交运算对于并运算可分配，
则并运算对于交运算也一定是可分配的。反之亦然。
应该指出，在分配格的定义中，条件还可减弱，这就是两个分配等式是等价的。
证明 <A,≤ >是链? <A,≤ >是分配格设 <A,≤ >是一个链，所以,<A,≤ >一定是格。
对任意的 a,b,c?A，只要讨论以下两种情况：
（ 1） a ≤ b 或 a ≤ c （ a不是最大）
（ 2） b ≤ a 且 c ≤ a （ a是最大）
对于情况（ 1），无论是 b ≤ c还是 c ≤ b,都有
a∧ (b∨ c)= a 和 (a∧ b)∨ (a∧ c)=a （ a小）
对于情况（ 2），总有 b∨ c ≤ a
所以 a∧ (b∨ c) = b∨ c （ a大）
而由 b ≤ a和 c ≤ a,应有 (a∧ b)∨ (a∧ c)=b∨ c
故 a∧ (b∨ c)=(a∧ b)∨ (a∧ c)成立。
定理 6-2.2 每个链是分配格。
定理 6-2.3 设 <A,≤ >是分配格，那么，对任意的
a,b,c?A,如果满足,a∧ b=a∧ c和 a∨ b=a∨ c成立,
则必有 b=c 。
证明,因为 (a∧ b)∨ c= (a∧ c)∨ c=c (吸收律 )
而 (a∧ b)∨ c=(a∨ c)∧ (b∨ c)=(a∨ b)∧ (b∨ c)
= b∨ (a∧ c) (并对交可分配 b)
= b∨ (a∧ b) (a∧ b=a∧ c条件 )
=b (吸收律 )
所以 b = c成立。
二、模格定义 6-2.2 设 <A,∨,∧ > 是由格 <A,≤ >是所诱导的代数系统。如果对任意的 a,b,c?A，当 b ≤ a时，
有：
a∧ (b∨ c)= b∨ (a∧ c)
则称 <A,≤ > 是模格 。
定理 6-2.4 设 <A,≤ >是模格，当且仅当在 A中不含有适合下述条件的元素?,?,?满足：
≤? 且?∨? =?∨? 和?∧? =?∧?
证明,(1)先证：
有?,?,?,使? ≤?且?∨?=?∨?和?∧?=?∧
<A,≤ >不 是模格若存在上述?,?,?,
因为?≤?,且?∧ (?∨?)=?∧ (?∨?)=? (吸收律 )
(?∧?)∨?=(?∧?)∨?=? (吸收律 )
比较上两式，得 (?∧?)∨?≤?∧ (?∨?) (根据?≤?)
所以 <A,≤>不是模格。
(2) 再证：
<A,≤ >不 是模格?有?,?,?,使? ≤?且?∨?=?∨?和
∧?=?∧?
若 <A,≤ >不 是模格，则有 a,b,c满足：
b≤a 且 b∨ (c∧ a) ≤(b∨ c)∧ a
令?=b∨ (c∧ a)?= (b∨ c)∧ a?=c
有?∧?=(b∨ c)∧ a∧ c=a∧ ((b∨ c)∧ c)=a∧ c=a∧ c∧ c
因此?∧?≤?∧? (a∧ c ≤ b∨ (c∧ a)=?)
另外,由于 (条件 )?≤?,故有?∧?≤?∧?,所以,
∧?=?∧?
同理可证?∨?=?∨?。 (3)综合 (1)和 (2)得到结论。
定理 6-2.5 对于模格 <A,≤>，若有三个元素 a,b,c，使得以下三式中的任意一式中把,≤”换为,=”成立，则另外两个式子中把,≤”换为,=”也成立。
a∨ (b∧ c) ≤ (a∨ b )∧ (a∨ c) (1)
(a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c) (2)
(a∧ b)∨ (b∧ c)∨ (c∧ a) ≤(a∨ b)∧ (b∨ c)∧ (c∨ a) (3)
证明,设 (1)成立，根据对偶律 (2)也成立。
只需先证明,(1)成立? (3)也成立
(3)式右端 = (a∨ b)∧ (b∨ c)∧ (c∨ a)=((a∧ c)∨ b)∧ (c∨ a)
=((c∨ a)∧ b)∨ (a∧ c) (模格 (c∨ a))
= (a∧ b)∨ (b∧ c)∨ (c∧ a) = (3)式左端 (分配 b)
再证明,(3)也成立? (1)成立且 (2)成立
(1)左端 = a∨ (b∧ c)=利用 (3)式推导 = (1)右端 。
我们知道，在一般的格中，对于任意的 a,b,c，有以下三个式子成立
a∨ (b∧ c) ≤ (a∨ b )∧ (a∨ c) (1)
(a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c) (2)
(a∧ b)∨ (b∧ c)∨ (c∧ a) ≤(a∨ b)∧ (b∨ c)∧ (c∨ a) (3)
练习,P248 (2)
定理 6-2.6 对于分配格必定是模格。
证明,设 <A,≤>是一个分配格，对于 A的任意元素 a,b,c，如果 b ≤ a 则 a∧ b= b 。
因此 a∧ (b∨ c)= (a∧ b)∨ (b∧ c)
= b∨ (a∧ c)?
格论大体上是在 1935年左右形成的，它不仅是代数学的一个分支，而且在近代解析几何，半序空间等方面也都有重要的作用。我们在这里只介绍格的一些基本知识以及几个具有特别性质的格 —— 分配格、有补格。
学习,格与布尔代数,
这一章的要求一、学习目的与要求本章在已经学过的群、环和域几个代数系统的基础上，进一步学习格这个新的代数系统，并且学习在计算机科学中有重要应用的布尔代数。
通过本章的学习，使学生进一步了解格的基本概念，掌握布尔代数的运算规律，为学习数字逻辑、计算机硬件设计等课程打下数学基础。
二、知识点
1,格的概念,偏序集上的并运算,
偏序集上的交运算 。
2,分配格,有补格；
3,布尔代数,Stone表示定理及其推论,布尔表达式,布尔函数,开关代数的概念 。
三、要求
1,识记根据哈斯图识别是否是格,分配格,有补格,
模格,布尔格,布尔代数 。
2,领会格同构的概念,分配格与模格的关系,格的全上界的唯一性证明,Stone表示定理,布尔表达式,析取范式和合取范式 。
3,简单应用开关代数 。
复习
1.偏序集定义 3-12.1：设 A是一个集合，如果 A上的一个关系 R满足自反性、反对称性和传递性，则称 R是 A上的一个偏序关系，记作 ≤ 。 <A,≤ >称作偏序集。
2,最大元、最小元定义 3-12.6：设 <A,≤>是一个偏序集，且 B是 A的子集，
若有某个元素 b?B，对于 B中的每一个元素 x，有 x≤b，则称 b为 <B,≤>的最大元；同理，若有某个元素 b?B，对于 B
中的每一个元素 x，有 b≤x，则称 b为 <B,≤>的最小元。
3.哈斯图定义 3-12.2：在偏序集 <A,≤>中，如果 x,y∈ A,x≤y，
x≠y，且没有其他元素 z，使 x≤z,z≤y，则称元素 y盖住元素 x。记 COVA={<x,y>|x,y∈ A,y盖住 x}。
对于给定偏序集 <A,≤>，它的盖住关系是唯一的，
所以可用盖住的性质画出偏序集合图，或称哈斯图，其作图规则为：
(1)小圆圈代表元素。
(2)如果 x≤y且 x≠y，将代表 y的小圆圈画在代表 x的小圆圈之上。
(3)如果 <x,y>∈ COVA，则在 x与 y之间用直线连结。
4,上界、下界定义 3-12.7：设 <A,≤>是一偏序集，对于 B?A，如有 a∈ A，
且对任意元素 x∈ B，都有 x≤a，则称 a为 B的上界。同理，对任意元素 x∈ B，都有 a≤x，则称 a为 B的下界。
5,上确界、下确界定义 3-12.8：设 <A,≤>是一偏序集且 B?A,a是 B的任一上界，若对 B的所有上界 y均有 a≤y，则称 a是 B的最小上界 (上确界 )，记作 LUBB。同理,b是 B的任一下界，若对 B的所有下界 z均有 z≤b，则称 b是 B的最大下界 (下确界 )，记作 GLBB。
6-1 格的概念在第三章中，我们介绍了偏序集的概念，偏序集就是由一个集合 A以及 A上的一个偏序关系,≤”所组成的一个代数系统 <A,≤>。我们知道，对于偏序集来说，它的任一个子集不是必定存在最小上界或最大下界的。
例如，在由图 6-1.1所示的偏序集中,{a,b}的最小上界是 c，但没有最大下界； {e,f}的最大下界是 d，但没有最小上界。
今后，我们把 {a,b}的最小上界（最大下界）
称为元素 a,b的最小上界（最大下界）。
由图 6-1.2所示的偏序集都有这样一个共同的特性，那就是在这些偏序集中，任何两个元素都有最小上界和最大下界。我们把具有这种性质的偏序集称作格。
一、格的定义称为正整数格练习 242页（ 1）
定义 6-1.1 设 <A,≤>是一个偏序集，如果 A中任意两个元素都有最小上界和最大下界，则称 <A,≤>为 格 （ lattice）。
例 1 设 I+是所有正整数的结合，在 I+上定义一个二元关系 |，
对于 a,b?I+,a|b当且仅当 a整除 b。容易验证 |是 I+上的一个偏序关系，故 < I+,|>是偏序集。由于该偏序集中任意两个元素的最小公倍数、最大公约数就是这两个元素的最小上界和最大下界，且?I+，因此 < I+,|>是格。
例 2 设?(S)是给定集合 S的幂集,<?(S),?>是一个偏序集。由于?(S)中的任意两个元素 S1,S2，它们的最大下界为 S1∩ S2,最小上界为 S1∪ S2,且(S),所以 <?(S)，
>是格。
例 3 给定 S={a,b},?(S)={?,{a},{b},{a,b}}，那么，格
<?(S),?>如图 6-1.3所示。
二、由格 <A,≤>所诱导的代数系统定义 6-1.2 设 <A,≤>是一个格,如果在上定义两个二元运算 ∨ 和 ∧,使得对于任意的 a,b? A,a∨ b等于 a和 b的最小上界,a∧ b等于 a和 b的最大下界,那么,就称 <A,∨,∧ >为由格
<A,≤>所诱导的代数系统。二元运算 ∨ 和 ∧ 分别称为 并运算 和交运算 。
通常用 a∨ b表示 {a,b}的上确界,用 a∧ b 表示 {a,b}的下确界,∨ 和 ∧ 分别称为 保联 (join)和 保交 (meet)运算。由于对任何 a,b,因为在格中,a∨ b及 a∧ b都是 A中确定的成员，因此 ∨,∧ 均为 A上的运算。
设 S={a,b},?(S) ={?,{a},{b},{a,b}}由格 <?(S),? >
诱导的代数系统为 <?(S),∨,∧ >。其中 ∨ 为 集合的并运算和
∧ 为 集合的交运算。如表 6-1.1所示。
三、子格定义 6-1.3 设 <A,≤>是一个格,由格 <A,≤>所诱导的代数系统为 <A,∨,∧ >。设 B?A且 B≠?，如果 A中的两个运算 ∨ 和 ∧ 关于 B是封闭的，则称 <B,≤>是
<A,≤>的子格。
例 4 例 1给出了一个具体的格 < I+,|>,由它诱导的代数系统为 < I+,∨,∧ >,其中 a∨ b就是 a,b的最小公倍数,a∧ b就是 a,b的最大公约数。因为任何两个偶数的最大公约数和最小公倍数都是偶数，所以，
如果取 E+是正偶整数的全体，那么 ∨ 和 ∧ 关于 E+是封闭的，因此称 < E+,|>是 < I+,|>的子格。
必须指出，对于格 <A,≤>，设 B是 A的非空子集，尽管 <B,≤>必定是一个偏序集，然而 <B,≤>不一定是格，而且即使 <B,?>是格，也不一定是 <A,≤>的子格。
例题 1 设 <S,≤>是一个格，任取 a?S，构造 S的子集
T为：
T={x|x?S且 x≤a}
则 <T,≤>是 <S,≤>的一个子格。
解 对于任意的 x,y?T，必有 x≤a 和 y≤a，
所以 x∨ y≤a,x∧ y≤a
而 x∨ y?S,x∧ y?S
故 x∨ y?T,x∧ y?T
因此 <T,≤>是 <S,≤>的一个子格。
同样地，可以证明，如果取 Q={x|x?S且 a≤x}，
则 <Q,≤>也是 <S,≤>的一个子格。
四、格所诱导的代数系统的一些性质
1,对偶原理在讨论格以及格所诱导的代数系统的一些性质之前，先介绍格的对偶原理。
对偶这个概念在日常生活中也是屡见不鲜的，
譬如，在不同国家的交通规则可能不同，但基本上是两种，一种是以左为准，另一种是以右为准，那么，在以左为准的交通规则中，如果将左换成右，
右换成左就可得到另一种以右为准的交通规则，这里，左和右就是一种对偶的概念。
格对偶原理,设 <A,≤>是一个偏序集,在 A上定义一 个二元关系 ≤R,使得对于 A中任意两个元素 a,b都有关系 a ≤Rb当且仅当 b ≤ a,于是 <A,≤R>也是一个偏序集。把 <A,≤>和 <A,≤R>称为相互对偶的 (哈斯图相互颠倒 )。
可以证明，若 <A,≤>是格，则 <A,≤R>也是格。
称 ≤R是 ≤的逆关系。记为 ≥。
格对偶原理可以叙述为：设 P是对任意格都真的命题，如果在命题 P中把 ≤换成 ≥,∨ 换成 ∧,∧ 换成
∨,就得到另一个命题 P’，我们把 P’称为 P的对偶命题，则 P’对任意格也是真的命题。
定理 6-1.1 在一个格 <A,≤>中，对任意两个元素
a,b?A都有
a ≤ a∨ b b ≤ a∨ b
a∧ b ≤ a a∧ b ≤ b
证明思路,因为 a和 b的并是 a的一个上界，所以
a ≤ a∨ b
同理 b ≤ a∨ b
由对偶原理，即得 a∧ b ≤ a
a∧ b ≤ b?
2,格所诱导的代数系统的一些性质定理 6-1.2 在一个格 <A,≤>中，对于任意元素 a,b,c,d?A,
如果 a ≤ b 和 c ≤ d
则 a∨ c ≤ b∨ d
a∧ c ≤ b∧ d
证明 因为 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
推论 在一个格 <A,≤>中，对于任意元素 a,b,c?A,如果 b ≤
c,则 a∨ b ≤ a∨ c,a∧ b ≤ a∧ c(保序性 )。
证明 只要在定理 6-1.2中将 a代替 b,b代替 c,c代替 d，即可得证。
定理 6-1.3 在一个格 <A,≤>中,由格 <A,≤>所诱导的代数系统为 <A,∨,∧ >,则对于任意元素 a,b,c,d?A,有
(1) a∨ b= b∨ a
a∧ b= b∧ a
(2) a∨ (b∨ c)=(a∨ b)∨ c
a∧ (b∧ c)=(a∧ b)∧ c
(3) a∨ a=a
a∧ a=a
(4) a∨ (a∧ b)=a
a∧ (a∨ b)=a
（交换律）
（结合律）
（幂等律）
（吸收律）
（ 2）第一式：先证 [(a∨ b)∨ c] ≤[a∨ (b∨ c)]
根据定理 1（ x ≤ x∨ y,y ≤ x∨ y）
b ≤ b∨ c ≤ a∨ (b∨ c ),a ≤ a∨ (b∨ c )
根据定理 2（ x1 ≤ x2且 y1 ≤ y2?x1∨ y1 ≤ x2∨ y2）
a∨ b ≤ a∨ (b∨ c )
又因为
c ≤(b∨ c ) ≤ a∨ (b∨ c )
再根据定理 2
(a∨ b)∨ c ≤ a∨ (b∨ c )
再证 [a∨ (b∨ c)] ≤[(a∨ b)∨ c]
b ≤ a∨ b,c ≤ c? b∨ c ≤ (a∨ b)∨ c
a ≤ (a∨ b) ≤ a∨ (b∨ c )
a∨ (b∨ c) ≤ a∨ (b∨ c )?
证明思路,（ 1）格中任何两个元素 a,b的最小上界
（最大下界）当然等于 b,a的最小上界（最大下界），
故 a∨ b=b∨ a（ a∧ b=b∧ a）
（ 3）由定理 6-1.1可得 a ≤ a ∨ a
由自反性可知 a ≤ a
由此可得 a∨ a ≤ a
因此 a∨ a= a
利用对偶原理，即得 a∧ a=a
（ 4）由定理 6-1.1可得
a ≤ a ∨ （ a∧ b）
因为 a ≤ a和 a∧ b ≤ a
所以 a ∨ （ a∧ b） ≤ a
因此 a∨ (a∧ b)=a
利用对偶原理，即得 a∧ (a∨ b)=a
练习 242页（ 3）
例 6 设 <N,≤>是一个偏序集，这里 N是自然数集,≤是普通的数与数之间的,小于等于,关系，定义
a∨ b =max{a,b} （ 取大运算）
a∧ b =min {a,b} （ 取小运算）
则 <N,≤>是一个格。由此格诱导的代数系统为 <N,∨,∧ >
可以证明，该代数系统的两个运算满足定理 6-1.3的 4个运算律。
在此代数系统中，任意两个数 a和 b的最大值（最小值）与 b
和 a的最大值（最小值）是相等的，因此，并运算和交运算都是可交换的；又因为 max(max(a,b),c)和 max(a,max(b,c)) 都是三个数 a,b,c中的最大值，所以在 <N,∨,∧ >中并运算是可结合的，
同理,min(min(a,b),c)=min(a,min(b,c)),说明交运算的结合性；由于 max(a,a)=min(a,a)=a，所以幂等性成立；又由于
max(a,min(a,b)) =a和 min(a,max(a,b))=a，因此，吸收性也成立。
五、由代数系统确定的格引理 6-1.1 设 <A,∨,∧ >是一个代数系统,其中 ∨,∧
都是二元运算且满足吸收律，则 ∨ 和 ∧ 都满足幂等律。
证明思路,由吸收律：
a∨ (a∧ b)=a (1)
a∧ (a∨ b) =a (2)
将 (1)中的 b取为 (a∨ b),得 a∨ (a∧ (a∨ b))=a
再由得 a∨ a=a
同理可证 a∧ a=a?
定理 6-1.4 设 <A,∨,∧ >是一个代数系统,其中
∨,∧ 都是二元运算且满足交换律、结合律和吸收律，
则 A上存在偏序关系 ≤,使 <A,≤>是一个格。
证明思路,分四部分内容来证明：
(1) 定义二元关系 ≤,a ≤ b当且仅当 (a∧ b)=a
(2) 证明是偏序关系（证：自反、反对称和传递） ；
(3) 证明 a∧ b是 a和 b的最大下界（下确界）；
(4) 由 ∨,∧ 满足 交换律和吸收律，证明 a ∨ b是 a
和 b的最小上界。
六、在格 <A,≤>中并和交运算的性质定理 6-1.5 在一个格 <A,≤>中,对于任意的 a,b,c?A,
都有,a∨ (b∧ c) ≤ (a∨ b)∧ (a∨ c)
(a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c)
第 1式证明思路,由定理 6-1.1 a ≤ a∨ b,a ≤ a∨ c,
再由定理 6-1.2和幂等律得
a=a∧ a ≤ (a∨ b)∧ (a∨ c) (1)
另外,由于 b∧ c ≤ b ≤ a∨ b 和 b∧ c ≤ c ≤ a∨ c
所以 b∧ c=b∧ c∧ b∧ c ≤ (a∨ b)∧ (a∨ c) (2)
再对 (1)式和 (2)式应用定理 6-1.2得
a∨ (b∧ c) ≤ (a∨ b)∧ (a∨ c)
第 2式证明由对偶原理从上式直接可得。
定理 6-1.6 设 <A,≤>是一个格,那么，对于任意的
a,b?A,都有：
a ≤ b?(a∧ b)=a?(a∨ b)=b
a ≤ b?(a∧ b)=a证明思路：
(1)先证 a ≤ b? (a∧ b)=a
由 a ≤ b和 a ≤ a,根据定理 6-1.2得 a ≤ a∧ b
又根据 a∧ b的定义,有 a∧ b ≤ a
由二元关系 ≤的反对称性得,a∧ b = a
(2) 再证 (a∧ b)=a?a ≤ b
设 a∧ b=a，则 a=a∧ b ≤ b,这就证明了
(a∧ b)=a?a ≤ b
综合 (1)和 (2)得,a ≤ b?(a∧ b) =a?
定理 6-1.7 设 <A,≤>是一个格,那么，对于任意的
a,b,c?A,都有：
a ≤ c?a∨ (b∧ c) ≤ (a∨ b)∧ c
证明思路：
(1)先证 a ≤ c? a∨ (b∧ c) ≤ (a∨ b)∧ c
根据定理 6-1.6有 a ≤ c?(a∨ c)=c
根据定理 6-1.5有 a∨ (b∧ c) ≤(a∨ b)∧ (a∨ c)
a∨ (b∧ c) ≤(a∨ b)∧ c
(2) 再证 a∨ (b∧ c) ≤ (a∨ b)∧ c?a ≤ c
若 a∨ (b∧ c) ≤ (a∨ b)∧ c
则 a ≤ a∨ (b∧ c) ≤ (a∨ b)∧ c ≤ c 即 a ≤ c
综合 (1)和 (2)得,a ≤c?a∨ (b∧ c) ≤ (a∨ b)∧ c?
练习 242页
（ 4）
推论 设 <A,≤ >是一个格,那么，对于任意的
a,b,c?A,都有：
(a∧ b)∨ (a∧ c) ≤ a∧ (b ∨ (a∧ c) )
a∨ (b∧ (a∧ c) ) ≤ (a∨ b)∧ (a∨ c)
证明思路：
利用 a∧ c ≤ a,a ≤a∨ c 证第 1式第 2式是第 1式的对偶。
七、格同态、格同构定义 6-1.4 设 <A1,≤1>和 <A2,≤2>是两个格,那么,
由他们分别诱导的代数系统为 <A1,∨ 1,∧ 1>和
<A2,∨ 2,∧ 2>,如果存在着一个从 A1到 A2的映射 f，
使得对于任意的 a,b?A1,有
f(a∨ 1 b)= f(a)∨ 2 f(b)
f(a ∧ 1 b)= f(a)∧ 2 f(b)
则称 f为从 <A1,∨ 1,∧ 1> 到 <A2,∨ 2,∧ 2> 的格同态，
亦可称 < f(A1),≤2> 是 <A1,≤1> 的 格同态象。此外，
当 f是双射时，则称 f为从 <A1,∨ 1,∧ 1>到 <A2,∨ 2,∧ 2>
的格同构，亦可称 <A2,≤2>和 <A1,≤1>两个格是同构的 。
定理 6-1.8 设 f是格 <A1,≤1>到 <A2,≤2>的格同态,
则对于任意的 x,y?A1,若 x ≤1y,必有,f(x) ≤2f(y) 。
证明思路,因为 x ≤1y,所以 x∧ 1y=x
f(x∧ 1y) = f(x) f(x)∧ 2f(y) = f(x)
故 f(x) ≤2f(y)?
定理 6-1.8告诉我们格同态是保序的。但是定理 6-1.8
的逆命题是不一定成立的。
定理 6-1.9 设 <A1,≤1>和 <A2,≤2>是 两 个格,f是从 A1
到 A2的双射，则 f是从 <A1,≤1>到 <A2,≤2>的格同构，
当且仅当对任意的 a,b?A1,都有,a≤1b?f(a)≤2f(b)
证明,(1) 先证 f是 <A1,≤1>到 <A2,≤2>的格同构
a ≤1b?f(a) ≤2f(b)
由定理 6-1.8,若 a ≤1b,必有,f(a) ≤2f(b) (?)
反之，设 f(a) ≤2f(b),(?)
则 (格同构大条件 ) f(a)∧ 2f(b)= f(a∧ 1b)= f(a)
由于 f是双射，所以 a∧ 1b=a
故,a ≤1b
因此,a ≤1b?f(a) ≤2f(b)
(2) 再证 a≤1b?f(a)≤2f(b)?
f是 <A1,≤1>到 <A2,≤2>的格同构设对任意的 a,b?A1,a≤1b?f(a)≤2f(b)
设 a∧ 1b=c，则 c ≤ 1a,c ≤ 1b,
于是 f(a∧ 1b)=f (c),f(c) ≤ 2f(a),f(c) ≤ 2f(b)
故有 f(c) ≤ 2f(a)∧ 2f(b)
令 f(a)∧ 2f(b)=f(d)
则 f(c) ≤ 2f(d),f(d) ≤ 2f(a),f(d) ≤ 2f(b)
故有 d≤1a,d≤1b，于是 d≤1a∧ 1b,即 d≤1c，
所以 f(d) ≤ 2f(c)
因此 f(d)=f(c) 即 f(a∧ 1b)=f(a)∧ 2f(b)
类似地可证,f(a∨ 1b)=f(a)∨ 2 f(b) 格同构证毕。
练习,P242 (1)(2)
一、分配格定义 6-2.1 设 <A,∨,∧ > 是由格 <A,≤>是所诱导的代数系统。如果对任意的 a,b,c?A，满足：
a∧ (b∨ c)= (a∧ b)∨ (a∧ c)
a∨ (b∧ c)= (a∨ b)∧ (a∨ c)
则称 < A,≤> 是分配格 。
在定理 6-1.5中我们已经证明，在格 <A,≤ >中,对于任意的 a,b,c?A,都有,a∨ (b∧ c) ≤ (a∨ b)∧ (a∨ c)
和 (a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c)
成立。当上述两个式子中的等号成立的时候，我们就得到一类特殊的格。
6-2 分配格例 1 设 S={a,b,c}，则 <?(S),∪,∩ >是由格
<?(S),?>所诱导的代数系统。这个格所对应的哈斯图如图 6-2.1所示。
容易验证，对于任意的 P,Q,R(S)，有
P∩(Q∪R)=(P∩Q)∪(P∩R)
P∪(Q∩R)=(P∪Q)∩(P∪R)
成立。所以 <?(S),?>是一个分配格。
例 2 如图 6-2.2中所示的两个格都不是分配格。
这是因为，在图 6-2.2(a)中,b∧ (c∨ d )=b∧ a=b
而 (b∧ c)∨ (b∧ d) = e∨ e=e
所以 b∧ (c∨ d )? (b∧ c)∨ (b∧ d)
在图 6-2.2(b)中,c∧ (b∨ d )=c∧ a=c
而 (c∧ b)∨ (c∧ d) = e∨ d=d
所以 c∧ (b∨ d )? (c∧ b)∨ (c∧ d)
必须指出，在分配格的定义中，必须是对任意的 a,b,c?A都要满足分配等式，因此，决不能验证格中的某些元素满足分配等式就断定该格是分配格。
譬如，在例 2中，图 6-2.2(b)所示的格中，尽管有
d∧ (b∨ c )=d∧ a=d=e∨ d=(d∧ b)∨ (d∧ c)
b∧ (c∨ d )=b∧ c=e=e∨ e=(b∧ c)∨ (b∧ d)
但它不是分配格。
例 2中给出的两个具有五个元素的格是很重要的，
因为有一个定理证明了如下的结论,一个格是分配格的充要条件是在该格中没有任何子格与这两个五元素格中的任一个同构。 这个定理的证明已超出了本书的范围。
证明 定理的前半部分：
分配格中交对并可分配? 并对交也一定可分配设对任意的 a,b,c?A，
若 a∧ (b∨ c)= (a∧ b)∨ (a∧ c) (交对并可分配 a)
则 (a∨ b)∧ (a∨ c)
=((a∨ b)∧ a)∨ ((a∨ b)∧ c) (交对并可分配 (a∨ b))
=a∨ ((a∨ b)∧ c) (吸收律 )
=a∨ ((a∧ c)∨ (b∧ c)) (交对并可分配 c)
=(a∨ (a∧ c) )∨ (b∧ c) (结合律 )
=a∨ (b∧ c) (吸收律 )（并对交可分配）?
类似的可证明 分配格中并对交可分配?交 对并也一定可分配定理 6-2.1 如果在一个分配格中交运算对于并运算可分配，
则并运算对于交运算也一定是可分配的。反之亦然。
应该指出，在分配格的定义中，条件还可减弱，这就是两个分配等式是等价的。
证明 <A,≤ >是链? <A,≤ >是分配格设 <A,≤ >是一个链，所以,<A,≤ >一定是格。
对任意的 a,b,c?A，只要讨论以下两种情况：
（ 1） a ≤ b 或 a ≤ c （ a不是最大）
（ 2） b ≤ a 且 c ≤ a （ a是最大）
对于情况（ 1），无论是 b ≤ c还是 c ≤ b,都有
a∧ (b∨ c)= a 和 (a∧ b)∨ (a∧ c)=a （ a小）
对于情况（ 2），总有 b∨ c ≤ a
所以 a∧ (b∨ c) = b∨ c （ a大）
而由 b ≤ a和 c ≤ a,应有 (a∧ b)∨ (a∧ c)=b∨ c
故 a∧ (b∨ c)=(a∧ b)∨ (a∧ c)成立。
定理 6-2.2 每个链是分配格。
定理 6-2.3 设 <A,≤ >是分配格，那么，对任意的
a,b,c?A,如果满足,a∧ b=a∧ c和 a∨ b=a∨ c成立,
则必有 b=c 。
证明,因为 (a∧ b)∨ c= (a∧ c)∨ c=c (吸收律 )
而 (a∧ b)∨ c=(a∨ c)∧ (b∨ c)=(a∨ b)∧ (b∨ c)
= b∨ (a∧ c) (并对交可分配 b)
= b∨ (a∧ b) (a∧ b=a∧ c条件 )
=b (吸收律 )
所以 b = c成立。
二、模格定义 6-2.2 设 <A,∨,∧ > 是由格 <A,≤ >是所诱导的代数系统。如果对任意的 a,b,c?A，当 b ≤ a时，
有：
a∧ (b∨ c)= b∨ (a∧ c)
则称 <A,≤ > 是模格 。
定理 6-2.4 设 <A,≤ >是模格，当且仅当在 A中不含有适合下述条件的元素?,?,?满足：
≤? 且?∨? =?∨? 和?∧? =?∧?
证明,(1)先证：
有?,?,?,使? ≤?且?∨?=?∨?和?∧?=?∧
<A,≤ >不 是模格若存在上述?,?,?,
因为?≤?,且?∧ (?∨?)=?∧ (?∨?)=? (吸收律 )
(?∧?)∨?=(?∧?)∨?=? (吸收律 )
比较上两式，得 (?∧?)∨?≤?∧ (?∨?) (根据?≤?)
所以 <A,≤>不是模格。
(2) 再证：
<A,≤ >不 是模格?有?,?,?,使? ≤?且?∨?=?∨?和
∧?=?∧?
若 <A,≤ >不 是模格，则有 a,b,c满足：
b≤a 且 b∨ (c∧ a) ≤(b∨ c)∧ a
令?=b∨ (c∧ a)?= (b∨ c)∧ a?=c
有?∧?=(b∨ c)∧ a∧ c=a∧ ((b∨ c)∧ c)=a∧ c=a∧ c∧ c
因此?∧?≤?∧? (a∧ c ≤ b∨ (c∧ a)=?)
另外,由于 (条件 )?≤?,故有?∧?≤?∧?,所以,
∧?=?∧?
同理可证?∨?=?∨?。 (3)综合 (1)和 (2)得到结论。
定理 6-2.5 对于模格 <A,≤>，若有三个元素 a,b,c，使得以下三式中的任意一式中把,≤”换为,=”成立，则另外两个式子中把,≤”换为,=”也成立。
a∨ (b∧ c) ≤ (a∨ b )∧ (a∨ c) (1)
(a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c) (2)
(a∧ b)∨ (b∧ c)∨ (c∧ a) ≤(a∨ b)∧ (b∨ c)∧ (c∨ a) (3)
证明,设 (1)成立，根据对偶律 (2)也成立。
只需先证明,(1)成立? (3)也成立
(3)式右端 = (a∨ b)∧ (b∨ c)∧ (c∨ a)=((a∧ c)∨ b)∧ (c∨ a)
=((c∨ a)∧ b)∨ (a∧ c) (模格 (c∨ a))
= (a∧ b)∨ (b∧ c)∨ (c∧ a) = (3)式左端 (分配 b)
再证明,(3)也成立? (1)成立且 (2)成立
(1)左端 = a∨ (b∧ c)=利用 (3)式推导 = (1)右端 。
我们知道，在一般的格中，对于任意的 a,b,c，有以下三个式子成立
a∨ (b∧ c) ≤ (a∨ b )∧ (a∨ c) (1)
(a∧ b)∨ (a∧ c) ≤ a∧ (b∨ c) (2)
(a∧ b)∨ (b∧ c)∨ (c∧ a) ≤(a∨ b)∧ (b∨ c)∧ (c∨ a) (3)
练习,P248 (2)
定理 6-2.6 对于分配格必定是模格。
证明,设 <A,≤>是一个分配格，对于 A的任意元素 a,b,c，如果 b ≤ a 则 a∧ b= b 。
因此 a∧ (b∨ c)= (a∧ b)∨ (b∧ c)
= b∨ (a∧ c)?
