第 13章 格与布尔代数离 散 数 学哈尔滨理工大学本科生课程计算机系本章内容
13.1 格的定义与性质
13.2 子格与格同态
13.3 分配格与有补格
13.4 布尔代数本章总结作业
13.1 格的定义与性质定义 13.1 设 <S,≤> 是偏序集,如果?x,y∈S,{x,y}都有最小上界和最大下界,则称 S关于偏序 ≤ 作成一个 格 (lattice)。
说明,由于最小上界和最大下界的唯一性，可以把求 {x,y}的最小上界和最大下界看成 x与 y的二元运算 ∨ 和 ∧ 。
x∨ y：表示 x与 y的最小上界
x∧ y：表示 x和 y的最大下界。
本章出现的 ∨ 和 ∧ 符号只代表格中的运算，而不再有其它的含义。
格的实例例 13.1 设 n是正整数,Sn是 n的正因子的集合。 D为整除关系，
则偏序集 <Sn,D>构成格。x,y∈S n，
x∨y 是 lcm(x,y)，即 x与 y的最小公倍数。
x∧y 是 gcd(x,y)，即 x与 y的最大公约数。
下图给出了格 <S8,D>,<S6,D>和 <S30,D>。
例 13.2
例 13.2 判断下列偏序集是否构成格,并说明理由。
(1) <P(B),?>，其中 P(B)是集合 B的幂集。
(2) <Z,≤>,其中 Z是整数集,≤ 为小于或等于关系。
(3) 偏序集的哈斯图分别在下图给出。
例 13.2
解答 (1)是格。
x,y∈P(B),x∨y 就是 x∪y,x∧y 就是 x∩y 。
由于 ∪ 和 ∩ 运算在 P(B)上是封闭的，所以 x∪y,x∩y∈P(B) 。
称 <P(B),?>,为 B的 幂集格 。
(2)是格。
x,y∈Z,x∨y ＝ max(x,y),x∧y ＝ min(x,y)，它们都是整数。
(3)都不是格。
(a)中的 {a,b}没有最大下界。
(b)中的 {b,d}有两个上界 c和 e,但没有最小上界。
(c)中的 {b,c}有三个上界 d,e,f,但没有最小上界。
(d)中的 {a,g}没有最大下界。
例 13.3
例 13.3 设 G是群,L(G)是 G的所有子群的集合。即
L(G)＝ { H|H≤G }
对任意的 H1,H2∈L(G),H1∩H 2也是 G的子群，而 <H1∪H 2>是由
H1∪H 2生成的子群（即包含着 H1∪H 2的最小的子群）。
在 L(G)上定义包含关系?，则 L(G)关于包含关系构成一个格，
称为 G的 子群格 。
易见在 L(G)中,H1∧H 2就是 H1∩H 2,H1∨H 2就是 <H1∪H 2>。
对偶原理定义 13.2 设 f是含有格中元素以及符号＝,≤,≥,∨ 和 ∧ 的命题。令 f*是将 f中的 ≤ 替换成 ≥,≥ 替换成 ≤,∨ 替换成
∧,∧ 替换成 ∨ 所得到的命题。称 f*为 f的 对偶命题 。
例如 在格中令 f是 (a∨b)∧c≤c,则 f*是 (a∧b)∨c≥c 。
格的对偶原理 设 f是含有格中元素以及符号＝,≤,≥,∨ 和
∧ 的命题。若 f对一切格为真，则 f的对偶命题 f*也对一切格为真。
例如 对一切格 L都有?a,b∈L,a∧b≤a
(因为 a和 b的交是 a的一个下界 )
那么 对一切格 L都有?a,b∈L,a∨b≥a
说明 许多格的性质都是互为对偶命题的。
有了格的对偶原理，在证明格的性质时，
只须证明其中的一个命题即可。
格的运算性质定理 13.1 设 <L,≤> 是格，则运算 ∨ 和 ∧ 适合 交换律,结合律,幂等律 和 吸收律,即
(1)交换律?a,b∈L 有
a∨b ＝ b∨a a∧b ＝ b∧a
(2)结合律?a,b,c∈L 有
(a∨b)∨c ＝ a∨(b∨c) (a∧b)∧c ＝ a∧(b∧c)
(3)幂等律?a∈L 有
a∨a ＝ a a∧a ＝ a
(4)吸收律?a,b∈L 有
a∨(a∧b) ＝ a a∧(a∨b) ＝ a
定理 13.1
(1)a∨b 和 b∨a 分别是 {a,b}和 {b,a}的最小上界。
由于 {a,b}＝ {b,a}，所以 a∨b ＝ b∨a 。
由对偶原理,a∧b ＝ b∧a 得证。
(2)由最小上界的定义有
(a∨b)∨c≥a∨b≥a (13.1)
(a∨b)∨c≥a∨b≥b (13.2)
(a∨b)∨c≥c (13.3)
由式 13.2和 13.3有 (a∨b)∨c≥b∨c (13.4)
再由式 13.1和 13.4有 (a∨b)∨c≥a∨(b∨c)
(a∨b)∨c≤a∨(b∨c)
根据偏序关系的反对称性有 (a∨b)∨c ＝ a∨(b∨c)
由对偶原理,(a∧b)∧c ＝ a∧(b∧c) 得证。
定理 13.1
(3)显然 a≤a∨a,
又由 a≤a 可得 a∨a≤a 。
根据反对称性有 a∨a ＝ a，
由对偶原理,a∧a ＝ a 得证。
(4)显然 a∨(a∧b)≥a (13.5)
又由 a≤a,a∧b≤a 可得
a∨(a∧b)≤a (13.6)
由式 13.5和 13.6可得 a∨(a∧b) ＝ a，
根据对偶原理,a∧(a∨b) ＝ a 得证。
定理 13.2
定理 13.2 设 <S,*,?>是具有两个二元运算的代数系统，若对于 *和?运算适合 交换律,结合律,吸收律,则可以适当定义 S中的偏序 ≤,使得 <S,≤> 构成一个格，且 a,b∈S 有
a∧b ＝ a*b,a∨b ＝ a?b。
思路 (1)证明在 S中 *和?运算都适合幂等律。
(2)在 S上定义二元关系 R，并证明 R为偏序关系。
(3)证明 <S,≤> 构成格。
说明 通过规定运算及其基本性质可以给出格的定义。
定理 13.2
a∈S,由吸收律得
(1)证明在 S中 *和?运算都适合幂等律 。
a*a ＝ a*(a?(a*a))＝ a
同理有 a?a＝ a。
(2)在 S上定义二元关系 R,?a,b∈S 有 <a,b>∈R? a?b＝ b
下面证明 R在 S上的偏序。
根据幂等律,?a∈S 都有 a?a＝ a,即 <a,a>∈R,
所以 R在 S上是自反的。
a,b∈S 有
aRb且 bRa? a?b＝ b且 b?a＝ a
a＝ b?a＝ a?b＝ b (由于 a? b=b?a)
所以 R在 S上是反对称的。
定理 13.2
a,b,c∈S 有
aRb且 bRc? a?b＝ b 且 b?c＝ c
a?c＝ a?(b?c)
a?c＝ (a?b)?c
a?c＝ b?c＝ c
aRc
这就证明了 R在 S上是传递的。
综上所述,R为 S上的偏序。
以下把 R记作 ≤ 。
定理 13.2
(3) 证明 <S,≤ >构成格。 即证明 a∨b ＝ a?b,a∧b ＝ a*b 。
a,b∈S 有 a?(a?b)＝ (a?a)?b＝ a?b
b?(a?b)＝ a?(b?b)＝ a?b
根据 ≤ 的定义有 a≤a?b和 b≤a?b,所以 a?b是 {a,b}的上界。
假设 c为 {a,b}的上界,则有 a?c＝ c和 b?c＝ c,从而有
(a?b)?c ＝ a?(b?c) ＝ a?c ＝ c
这就证明了 a?b≤c,所以 a?b是 {a,b}的最小上界，即 a∨b ＝ a?b
为证 a*b是 {a,b}的最大下界,先证首先由 a?b＝ b 可知 a*b＝ a*(a?b)＝ a
反之由 a*b＝ a 可知 a?b ＝ (a*b)?b＝ b?(b*a)＝ b
再由式 (13.7)和 ≤ 的定义有 a≤b? a*b＝ a,依照前边的证明,
类似地可证 a*b是 {a,b}的最大下界,即 a∧b ＝ a*b。
a?b＝ b? a*b＝ a (13.7)
格的等价定义根据定理 13.2，可以给出格的另一个等价定义。
定义 13.3 设 <S,*,?>是代数系统,*和?是二元运算，如果 *和?满足交换律，结合律和吸收律，则 <S,*,?>构成一个 格 (lattice)。
说明 格中的幂等律可以由吸收律推出。
以后我们不再区别是偏序集定义的格，
还是代数系统定义的格，而统称为格 L。
格的性质定理 13.3 设 L是格，则?a,b∈L 有
a≤b? a∧b ＝ a? a∨b ＝ b
证明 先证 a≤b? a∧b ＝ a
由 a≤a 和 a≤b 可知,a是 {a,b}的下界，
故 a≤a∧b 。显然又有 a∧b≤a 。
由反对称性得 a∧b ＝ a。
再证 a∧b ＝ a? a∨b ＝ b。
根据吸收律有 b＝ b∨(b∧a)
由 a∧b ＝ a得 b＝ b∨a,即 a∨b ＝ b。
最后证 a∨b ＝ b? a≤b 。
由 a≤a∨b 得 a≤a∨b ＝ b。
格的性质定理 11.4 设 L是格,?a,b,c,d∈L,若 a≤b 且 c≤d,则
a∧c≤b∧d,a∨c≤b∨d
证明 a∧c≤a≤b
a∧c≤c≤d
因此,a∧c≤b∧d 。
同理可证 a∨c≤b∨d 。
例 13.4
例 13.4 设 L是格，证明?a,b,c∈L 有
a∨(b∧c)≤(a∨b)∧(a∨c)
证明 由 a≤a,b∧c≤b 得
a∨(b∧c)≤a∨b
由 a≤a,b∧c≤c 得
a∨(b∧c)≤a∨c
从而得到 a∨(b∧c)≤(a∨b)∧(a∨c)
说明 在格中分配不等式成立。
一般说来，格中的 ∨ 和 ∧ 运算并不是满足分配律的。
本节小结
偏序集构成格的条件：任意二元子集都有最大下界和最小上界 。
格的实例：正整数的因子格,幂集格,子群格 。
格的性质：对偶原理,格中算律 （ 交换,结合,幂等,
吸收 ）,保序性,分配不等式 。
格作为代数系统的定义 。
格的证明方法
13.2 子格与格同态定义 13.4 设 <L,∧,∨> 是格,S是 L的非空子集，若 S关于 L中的运算 ∧ 和 ∨ 仍构成格，则称 S是 L的 子格 。
例 13.5 设格 L如右图所示。令
S1＝ {a,e,f,g}
S2＝ {a,b,e,g}
则 S1不是 L的子格,S2是 L的子格。
因为对于 e和 f,有 e∧f ＝ c，
但 c?S1。
格同态定义 13.5 设 L1和 L2是格,?,L1→L 2，若?a,b∈L 1 有
(a∧b) ＝?(a)∧?(b),?(a∨b) ＝?(a)∨f(b)
成立，则称?为格 L1到 L2的 同态映射,简称 格同态 。
例 13.6 (1)设 L1＝ {2n|n∈Z+},L2＝ {2n+1|n∈N}
则 L1和 L2关于通常数的小于或等于关系构成格。
令?,L1→L 2,?(x)＝ x-1
不难验证?是 L1到 L2的同态映射，因为对任意的 x,y∈L 1有
(x∨y) ＝?(max(x,y))＝ max(x,y)-1
(x)∨?(y)＝ (x-1)∨(y -1)＝ max(x-1,y-1)＝ max(x,y)-1
(x∧y) ＝?(min(x,y))＝ min(x,y)-1
(x)∧?(y)＝ (x-1)∧(y -1)＝ min(x-1,y-1)＝ min(x,y)-1
即?(x∧y) ＝?(x)∧?(y),?(x∨y) ＝?(x)∨?(y)
例 13.6
(2)如图中的格 L1,L2和 L3，若定义
1:L1→L 2
1(a)＝?1(b)＝?1(c)＝ a1，
1(d)＝ d1
2:L1→L 3
2(a)＝ a2,?2(b)＝ b2,
2(c)＝ c2,?2(d)＝ d2
则?1和?2都不是格同态，因为
1(b∨c) ＝?1(d)＝ d1
1(b)∨?1(c)＝ a1∨a 1＝ a1
2(b∨c) ＝?2(d)＝ d2
2(b)∨?2(c)＝ b2∨c 2＝ c2
从而
1(b∨c)≠?1(b)∨?1(c)
2(b∨c)≠?2(b)∨?2(c)
格同态的性质定理 13.5 设?是格 L1到 L2的映射，
(1)若?是格同态映射，则?是保序映射，即?x,y∈L 1，有
x≤y(x)≤?(y)
(2)若?是双射，则?是格同构映射当且仅当?x,y∈L 1，有
x≤y(x)≤?(y)
证明 (1) 任取 x,y∈L 1,x≤y,
由格的性质知 x∨y ＝ y。
又由于?是格同态映射，必有
(y)＝?(x∨y) ＝?(x)∨?(y)
从而得到?(x)≤?(y)。
定理 13.5(2)的证明充分性。
(2)若?是双射，则?是格同构映射当且仅当?x,y∈L 1，有
x≤y(x)≤?(y)
只须证明?是 L1到 L2的同态映射即可。
任取 x,y∈L 1,令 x∨y ＝ z，由 x≤z 和 y≤z 知
(x)≤?(z),?(y)≤?(z)
从而有?(x)∨?(y)≤?(z)＝?(x∨y)
另一方面，由?(x)∨?(y)∈L 2和?的满射性可知，
必存在 u∈L 1使得?(u)＝?(x)∨?(y)
因此有?(x)≤?(u),?(y)≤?(u)。
由已知条件可得 x≤u,y≤u 。 从而推出 x∨y≤u 。
再次使用已知条件得?(x∨y)≤?(u)＝?(x)∨?(y)。
综合上述有?(x∨y) ＝?(x)∨?(y)。
同理可证?(x∧y) ＝?(x)∧?(y)。
定理 13.5(2)的证明必要性。 由 (1)的结论必有
x≤y(x)≤?(y)
反之，若?(x)≤?(y)，由于?是同构映射，则
(x∨y) ＝?(x)∨?(y)＝?(y)
又由于?是双射，必有 x∨y ＝ y。
从而证明了 x≤y 。
(2)若?是双射，则?是格同构映射当且仅当?x,y∈L 1，有
x≤y(x)≤?(y)
例 13.7
例 13.7 设 L1＝ <S12,D>,L2＝ <S12,≤> 是格，其中 S12是 12的所有正因子构成的集合,D为整除关系,≤ 为通常数的小于或等于关系。令
,S12→S 12,?(x)＝ x
则?是双射，但?不是格 L1到 L2的同构映射。
因为?(2)≤?(3)，但 2不整除 3。
根据定理 13.5可知,?不是同构映射。
格的直积类似于半群,群和环,也可以定义格的直积。
定义 13.6 设 L1和 L2是格，定义 L1× L2上的运算 ∩,∪,
即?<a1,b1>,<a2,b2>∈ L1× L2 有
<a1,b1>∩<a 2,b2>＝ <a1∧a 2,b1∧b 2>
<a1,b1>∪<a 2,b2>＝ <a1∨a 2,b1∨b 2>
称 <L1× L2,∩,∪> 为格 L1和 L2的 直积 。
可以证明 <L1× L2,∩,∪> 仍是格。
格的直积
<a1,b1>,<a2,b2>,<a3,b3>∈L 1× L2，有交换律 <a1,b1>∩<a 2,b2>＝ <a1∧a 2,b1∧b 2> ＝ <a2∧a 1,b2∧b 1>
＝ <a2,b2>∩<a 1,b1>
结合律 (<a1,b1>∩<a 2,b2>)∩<a 3,b3>
＝ <a1∧a 2,b1∧b 2>∩<a 3,b3>
＝ <(a1∧a 2)∧a 3,(b1∧b 2)∧b 3>
＝ <a1∧a 2∧a 3,b1∧b 2∧b 3>
<a1,b1>∩(<a 2,b2>∩<a 3,b3>)＝ <a1∧a 2∧a 3,b1∧b 2∧b 3>
同理可证 ∪ 运算也满足交换律和结合律。
格的直积吸收律 <a1,b1>∩(<a 1,b1>∪<a 2,b2>)
＝ <a1,b1>∩<a 1∨a 2,b1∨b 2>
＝ <a1∧(a 1∨a 2),b1∧(b 1∨b 2)>
＝ <a1,b1>
同理有 <a1,b1>∪(<a 1,b1>∩<a 2,b2>)＝ <a1,b1>
这就证明了 ∩ 和 ∪ 运算满足吸收律。
从而证明 L1× L2仍是格格的直积举例格 L＝ <{0,1},≤>,≤ 为通常的小于或等于关系。则
L× L＝ {<0,0>,<0,1>,<1,0>,<1,1>}，
其中 <0,0>是最小元,<1,1>是最大元，且
<0,0>≤<0,1>≤<1,1>,
<0,0>≤<1,0>≤<1,1>,
而 <0,1>与 <1,0>是不可比的。
易见 L× L与图 13.4的 L1同构。
本节小结
格 L的非空子集 S构成 L的子格的条件：
S对 L的两个运算封闭 。
函数?构成格同态的条件：
(a∧b) ＝?(a)∧?(b)
(a∨b) ＝?(a)∨?(b)
格同态的保序性 。
13.3 分配格与有补格
一般说来，格中运算 ∨ 对 ∧ 满足分配不等式，
即?a,b,c∈L,有
a∨(b∧c)≤(a∨b)∧(a∨c)
但是不一定满足分配律。满足分配律的格称为 分配格 。
定义 13.7 设 <L,∧,∨> 是格，若?a,b,c∈L,有
a∧(b∨c) ＝ (a∧b)∨(a∧c)
a∨(b∧c) ＝ (a∨b)∧(a∨c)
则称 L为 分配格 。
说明 上面两个等式互为对偶式。
在证明 L为分配格时，只须证明其中的一个等式即可。
例 13.8
L1和 L2是分配格,L3和 L4不是分配格。
在 L3中,b∧(c∨d) ＝ b∧e ＝ b
(b∧c)∨(b∧d) ＝ a∨a ＝ a
在 L4中,c∨(b∧d) ＝ c∨a ＝ c
(c∨b)∧(c∨d) ＝ e∧d ＝ d
钻石格 五角格分配格的判别定理 13.6 设 L是格，则 L是分配格当且仅当 L中不含有与钻石格或五角格同构的子格。
证明 略。
推论 (1) 小于五元的格都是分配格。
(2) 任何一条链都是分配格。
例 13.9
说明下图中的格是否为分配格，为什么？
L1,L2和 L3都不是分配格。
{a,b,c,d,e}是 L1的子格，并且同构于钻石格。
{a,b,c,e,f}是 L2的子格，并且同构于五角格。
{a,c,b,e,f}是 L3的子格，也同构于钻石格。
定理 13.7
定理 13.7 格 L是分配格 当且仅当
a,b,c∈L,a∧b ＝ a∧c 且 a∨b ＝ a∨c? b＝ c。
证明 必要性 。a,b,c∈L,有
b ＝ b∨( a∧b ) (吸收律,交换律 )
＝ b∨ (a∧c) (已知条件代入 )
＝ (b∨a )∧(b∨c) (分配律 )
＝ (a∨c )∧(b ∨c ) (已知条件代入,交换律 )
＝ (a∧b )∨c (分配律 )
＝ (a∧c)∨c (已知条件代入 )
＝ c (交换律,吸收律 )
定理 13.7
充分性。 假若?a,b,c∈L,有
a∧b ＝ a∧c 且 a∨b ＝ a∨c? b＝ c
成立，而 L不是分配格。
根据定理 13.6,L中必含有与钻石格或五角格同构的子格。
假设 L中含有与钻石格同构的子格，且该子格为 {u,v,x,y,z}，
其中 u为它的最小元,v为它的最大元。
从而推出
x∧y ＝ x∧z ＝ u,x∨y ＝ x∨z ＝ v
但 y≠z,与已知矛盾。
对五角格的情况同理可证。
v
u
x zy
定理 13.7的应用使用定理 13.7也可以判别一个格是否为分配格。
例如下图中的三个格都不是分配格。
在 L1中有 b∨c ＝ b∨d,b∧c ＝ b∧d,但 c≠d 。
在 L2中有 b∧c ＝ b∧e,b∨c ＝ b∨e,但 c≠e 。
在 L3中有 c∧b ＝ c∧d,c∨b ＝ c∨d,但 b≠d 。
格的全下界和全上界定义 13.8 设 L是格，
若存在 a∈L 使得?x∈L 有 a≤x,则称 a为 L的 全下界 ；
若存在 b∈L 使得?x∈L 有 x≤b,则称 b为 L的 全上界 。
命题 格 L若存在全下界或全上界，一定是唯一的。
证明 以全下界为例，假若 a1和 a2都是格 L的全下界,
则有 a1≤a 2和 a2≤a 1。
根据偏序关系的反对称性必有 a1＝ a2。
记法 将格 L的 全下界记为 0,全上界记为 1。
有界格定义 13.9 设 L是格，若 L存在全下界和全上界，则称 L为 有界格,
并将 L记为 <L,∧,∨,0,1> 。
说明 有限格 L一定是有界格。
举例
设 L是 n元格,且 L＝ {a1,a2,…,an}，那么 a1∧a 2∧ … ∧a n是 L的全下界，而 a1∨a 2∨ … ∨a n是 L的全上界。因此 L是有界格。
对于 无限格 L来说，有的是有界格，有的不是有界格。
如集合 B的 幂集格 <P(B),∩,∪>,不管 B是有穷集还是无穷集，
它都是有界格。它的全下界是空集?,全上界是 B。
整数集 Z关于通常数的小于或等于关系构成的格不是有界格，
因为不存在最小和最大的整数。
有界格的性质定理 13.8 设 <L,∧,∨,0,1> 是有界格，则?a∈L 有
a∧0 ＝ 0 a∨0 ＝ a
a∧1 ＝ a a∨1 ＝ 1
证明 由 a∧0≤0 和 0≤a∧0 可知 a∧0 ＝ 0。
说明 在有界格中，
全下界 0是关于 ∧ 运算的零元,∨ 运算的单位元。
全上界 1是关于 ∨ 运算的零元,∧ 运算的单位元。
对偶原理 对于涉及到有界格的命题，如果其中含有全下界 0或全上界 1，在求该命题的对偶命题时，必须将 0替换成 1，而将 1替换成 0。
例如 a∧0 ＝ 0 和 a∨1 ＝ 1 互为对偶命题，
a∨0 ＝ a 和 a∧1 ＝ a 互为对偶命题。
有界格中的补元定义 13.10 设 <L,∧,∨,0,1> 是有界格,a∈L,
若存在 b∈L 使得
a∧b ＝ 0 和 a∨b ＝ 1
成立，则称 b是 a的 补元 。
说明 若 b是 a的补元，那么 a也是 b的补元。
换句话说,a和 b互为补元。
例 13.10
考虑下图中的四个格。
L1中的 a与 c互为补元，其中 a为全下界,c为全上界,b没有补元。
L2中的 a与 d互为补元，其中 a为全下界,d为全上界,b与 c也互为补元。
L3中的 a与 e互为补元，其中 a为全下界,e为全上界,b的补元是 c
和 d,c的补元是 b和 d,d的补元是 b和 c。 b,c,d每个元素都有两个补元。
L4中的 a与 e互为补元。其中 a为全下界。 e为全上界。 b的补元是 c
和 d,c的补元是 b,d的补元是 b。
有界格中补元的说明在任何有界格中，
全下界 0与全上界 1互补。
对于其他元素，可能存在补元，也可能不存在补元。
如果存在，可能是唯一的，也可能是多个补元。
对于有界分配格，如果它的元素存在补元，一定是唯一的。
有界分配格中补元的唯一性定理 13.9 设 <L,∧,∨,0,1> 是有界分配格。
若 a∈L,且对于 a存在补元 b，则 b是 a的唯一补元。
证明 假设 c∈L 也是 a的补元，则有
a∨c ＝ 1,a∧c ＝ 0
又知 b是 a的补元，故
a∨b ＝ 1,a∧b ＝ 0
从而得到
a∨c ＝ a∨b,a∧c ＝ a∧b
由于 L是分配格，根据定理 13.7,b＝ c。
有补格的定义定义 13.11 设 <L,∧,∨,0,1> 是有界格，若 L中所有元素都有补元存在，则称 L为 有补格 。
L2,L3和 L4是有补格，
L1不是有补格。
L2和 L3是有补格，
L1不是有补格。
本节小结
如果格中一个运算对另一个运算是可分配的,称这个格是分配格 。
分配格的两种判别法：
不存在与钻石格或五角格同构的子格；
对于任意元素 a,b,c,有 a∧b ＝ a∧c 且 a∨b ＝ a∨c?b＝ c。
有界格的定义及其实例 。
格中元素的补元及其性质 （ 分配格中补元的唯一性 ） 。
有补格的定义 。
13.4 布尔代数定义 13.12 如果一个格是 有补分配格,则称它为 布尔格 或 布尔代数 。
说明 在布尔代数中，每个元素都存在着唯一的补元。
可以把求补元的运算看作是布尔代数中的一元运算。
可以把一个布尔代数标记为 <B,∧,∨,＇,0,1>，
＇为求补运算,?a∈B,a＇是 a的补元。
例 13.11
例 13.11 设 S110＝ {1,2,5,10,11,22,55,110}是 110的正因子集合。
令 gcd,lcm分别表示求最大公约数和最小公倍数的运算。问
<S110,gcd,lcm>是否构成布尔代数？为什么？
解答 证明 <S110,gcd,lcm>构成格。
容易验证?x,y,z∈S 110，有
gcd(x,y)∈S 110
lcm(x,y)∈S 110
gcd(x,y)＝ gcd(y,x)
lcm(x,y)＝ lcm(y,x)
gcd(gcd(x,y),z)＝ gcd(x,gcd(y,z))
lcm(lcm(x,y),z)＝ lcm(x,lcm(y,z))
gcd(x,lcm(x,y))＝ x
lcm(x,gcd(x,y))＝ x
二元运算交换律结合律吸收律例 13.11
证明 <S110,gcd,lcm>是分配格。
易验证? x,y,z∈S 110 有
gcd(x,lcm(y,z))＝ lcm(gcd(x,y),gcd(x,z))
证明 <S110,gcd,lcm>是有补格。
1 为 S110中的全下界
110为 S110中的全上界
1和 110互为补元,2和 55互为补元，
5和 22互为补元,10和 11互为补元。
综上所述,<S110,gcd,lcm>为布尔代数。
例 13.12
例 13.12 设 B为任意集合,证明 B的 幂集格 <P(B),∩,∪,～,
,B>构成布尔代数，称为 集合代数 。
证明 P(B)关于 ∩ 和 ∪ 构成格，因为
∩ 和 ∪ 运算满足交换律、结合律和吸收律。
由于 ∩ 和 ∪ 互相可分配，因此 P(B)是分配格，
且全下界是空集?,全上界是 B。
根据绝对补的定义，取全集为 B，
x∈P(B),～ x是 x的补元。
从而证明 P(B)是有补分配格，即布尔代数。
布尔代数的性质定理 13.10 设 <B,∧,∨,′,0,1> 是布尔代数，则
(1)?a∈B,(a＇ )＇＝ a
(2)?a,b∈B,(a∧b) ＇＝ a＇ ∨ b＇,(a∨b) ＇＝ a＇ ∧ b＇
说明 (1)称为 双重否定律 。
(2)称为 德摩根律 。
命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例。
可以证明德摩根律对有限个元素也是正确的。
证明 (1) (a′)′ 是 a′ 的补元,a也是 a′ 的补元。
由补元的唯一性得 (a′)′ ＝ a。
定理 13.10(2)的证明
(2)?a,b∈B,(a∧b) ＇＝ a＇ ∨ b＇,(a∨b) ＇＝ a＇ ∧ b＇
(a∧b) ∨(a ＇ ∨ b＇ )
＝ (a∨a ＇ ∨ b＇ )∧( b∨a ＇ ∨ b＇ )
＝ (1∨b ＇ )∧( a ＇ ∨ 1)
＝ 1∧1
＝ 1
(a∧b)∧ (a＇ ∨ b＇ )
＝ (a∧b ∧a ＇ )∨(a∧ b∧b ＇ )
＝ (0∧b)∨(a∧0)
＝ 0∨0 ＝ 0
所以 a＇ ∨ b＇是 a∧b 的补元，根据补元的唯一性有
(a∧b) ＇＝ a＇ ∨ b＇
同理可证 (a∨b) ＇ = a＇ ∧ b＇。
布尔代数作为代数系统的定义定义 13.13 设 <B,*,?>是代数系统,*和?是二元运算。
若 *和 ° 运算满足：
(1) 交换律,即?a,b∈B 有
a*b＝ b*a,a?b＝ b?a
(2) 分配律,即?a,b,c∈B 有
a*(b?c)＝ (a*b)?(a*c)
a?(b*c)＝ (a?b)*(a?c)
(3) 同一律,即存在 0,1∈B,使得?a∈B 有
a*1＝ a,a?0＝ a
(4) 补元律,即?a∈B,存在 a′ ∈B,使得
a*a′ ＝ 0,a?a′ ＝ 1
则称 <B,*,?>是一个 布尔代数 。
关于布尔代数定义的说明所谓 同一律就是指运算含有单位元的性质,这里的 1是 *运算的单位元,0是运算?的单位元。
可以证明 1和 0分别也是?和 *运算的零元。a∈B 有
a?1 ＝ (a?1)*1 （同一律）
＝ 1*(a?1) （交换律）
＝ (a?a′ )*(a?1) （补元律）
＝ a?(a′* 1) （分配律）
＝ a?a′ （同一律）
＝ 1 （补元律）
同理可证 a*0＝ 0。
关于布尔代数定义的说明为证明以上定义的 <B,*,° >是布尔代数，只需证明它是一个格，即 证明 *和 ° 运算满足结合律和吸收律。
证明吸收律,?a,b∈B 有
a?(a*b)
＝ (a*1)?(a*b) （同一律）
＝ a*(1?b) （分配律）
＝ a*1 （ 1是?运算的零元 )
＝ a （同一律）
同理有 a*(a?b)＝ a。
关于布尔代数定义的说明为证结合律，先证以下命题：
a,b,c∈B,a?b＝ a?c 且 ab＝ ac? b＝ c
由 a?b＝ a?c 且 ab＝ ac 可得
(a?b)*(ab)＝ (a?c)*(ac)
由分配律和交换律得
(a*a?)?b＝ (a*a?)?c
由补元律得
0?b＝ 0?c
由同一律和交换律得
b＝ c
关于布尔代数定义的说明使用这个命题，为证明 (a*b)*c＝ a*(b*c)，只需证明以下两个等式：
(1) a?((a*b)*c)＝ a?(a*(b*c))
(2) a((a*b)*c)＝ a(a*(b*c))
先证明第一个等式，由吸收律有
a?(a*(b*c))＝ a
a?((a*b)*c)
＝ (a?(a*b))*(a?c)(分配律 )
＝ a*(a?c) (吸收律 )
＝ a
所以 (1)式成立。
关于布尔代数定义的说明下面证明 (2)式,a((a*b)*c)＝ a(a*(b*c))
a(a*(b*c))
＝ (aa)*(a(b*c)) (分配律 )
＝ 1*(a(b*c)) (交换律,补元律 )
＝ a(b*c) (交换律,同一律 )
a((a*b)*c)
＝ (a(a*b))*(ac) (分配律 )
＝ ((aa)*(ab))*(ac) (分配律 )
＝ (1*(ab))*(ac) (交换律,补元律 )
＝ (ab)*(ac) (交换律,同一律 )
＝ a(b*c) (分配律 )
所以（ 2）式成立。
布尔代数的子代数定义 13.14 设 <B,∧,∨,?,0,1>是布尔代数,S是 B的非空子集，若 0,1∈S,且 S对 ∧,∨ 和?运算都是封闭的，则称 S
是 B的 子布尔代数 。
例 13.13
例 13.13 设 <B,∧,∨,?,0,1>是布尔代数,a,b∈B,且 a＜ b。令
S＝ {x|x∈B,且 a≤x≤b}
称 S为 B中的 区间,可简记为 [a,b]。
可以证明 [a,b]是一个布尔代数。
显然 S是 B的非空子集，且 a和 b分别为 S的全下界和全上界。
对任意的 x,y∈S 都有
a≤x≤b,a≤y≤b
从而有 a≤x∧y≤b,a≤x∨y≤b
S关于 ∧ 和 ∨ 运算是封闭的。
易见 ∧ 和 ∨ 运算在 S上适合交换律和分配律。
例 13.13
对任意的 x∈S,令 y＝ (a∨x?)∧b ( 下面证明 y为 x得补元。 )
由于 a≤a∨x?,a≤b,故 a≤(a∨x?)∧b 。
同时 (a∨x?)∧b≤b,因此 y∈S 。 又
x∨y ＝ x∨((a∨x?)∧b )
＝ x∨(( a∧b )∨(x?∧b)) (分配律 )
＝ x∨a ∨(x?∧b) (a＜ b)
＝ x∨ (x?∧b) (a≤x)
＝ (x∨x?)∧(x∨b) (分配律 )
＝ 1∧(x∨b) (补元律 )
＝ x∨b (交换律，同一律 )
＝ b (x≤b)
例 13.13
x∧y ＝ x∧((a∨x?)∧b )
＝ x∧ (a∨x?) (x≤b,交换律 )
＝ (x∧a)∨( x∧x?) (分配律 )
＝ (x∧a)∨ 0 (补元律 )
＝ x∧a (同一律 )
＝ a (a≤x)
根据定义 13.13,<S,∧,∨> 构成布尔代数。
其全上界是 a，全下界是 b。
x∈[a,b],x关于这个全上界和全下界的补元是 (a∨x?)∧b 。
当 a＝ 0且 b＝ 1时,[a,b]是 B的子布尔代数。
但当 a≠0 或 b≠1 时,[a,b]不是 B的子布尔代数。
例 13.14
考虑 110的正因子集合 S110关于 gcd,lcm运算构成的布尔代数。
它有以下的子布尔代数：
{1,110}
{1,2,55,110}
{1,5,22,110}
{1,10,11,110}
{1,2,5,10,11,22,55,110}
布尔代数的同态映射定义 13.15 设 <B1,∧,∨,?,0,1>和 <B2,∩,∪,-,θ,E> 是两个布尔代数。这里的 ∩,∪,-泛指布尔代数 B2中的求最大下界、最小上界和补元的运算。 θ 和 E分别是 B2的全下界和全上界。
,B1→B 2。如果对于任意的 a,b∈B 1 有
(a∨b) ＝?(a)∪?(b)
(a∧b) ＝?(a)∩?(b)
(a?) ＝ -?(a)
则称?是布尔代数 B1到 B2的 同态映射,简称 布尔代数的同态 。
说明 类似于其它代数系统，也可以定义布尔代数的单同态、
满同态和同构。
例 13.15
例 13.15 设 <B1,∧,∨,?,0,1>和 <B2,∩,∪,-,θ,E> 是布尔代数。
,B1→B 2。若?a,b∈B 1有
(a∧b) ＝?(a)∩?(b)
(a?) ＝ -?(a)
证明?是 B1到 B2的同态。
证明 只须证明?a,b∈B 1 有?(a∨b) ＝?(a)∪?(b)成立即可。
(a∨b)
＝?(((a∨b)?)?) (双重否定律 )
＝ -?((a∨b)?) (已知 )
＝ -?(a?∧b?) (德摩根律 )
＝ -(?(a?)∩?(b?)) (已知 )
＝ -(-?(a)∩ -?(b)) (已知 )
＝ -(-?(a))∪ -(-?(b)) (德摩根律 )
＝?(a)∪?(b) (双重否定律 )
有限布尔代数的结构定义 13.16 设 L是格,0∈L,a∈L,若?b∈L 有
0＜ b≤a? b＝ a
则称 a是 L中的 原子 。
考虑右图中的几个格。
L1的原子是 a。
L2的原子是 a,b,c。
L3的原子是 a和 b。
若 L是正整数 n的全体正因子关于整除关系构成的格，则 L的原子恰为 n的全体质因子。
若 L是集合 B的幂集合，则 L的原子就是由 B中元素构成的单元集。
引理１
引理 1 设Ｌ是格,a,b是Ｌ中的原子，若 a≠b,则 a∧b ＝ 0。
证明 假设 a∧b≠ 0，则有
0＜ a∧b≤a 和 0＜ a∧b≤b
由于 a,b是原子，则有 a∧b ＝ a 和 a∧b ＝ b，
从而有 a＝ b，与已知矛盾。
引理２
引理２ 设 B是有限的布尔代数,?x∈B,x≠ 0,令
T(x)＝ {a1,a2,…,an}
是 B中所有小于或等于 x的原子构成的集合，则
x＝ a1∨a 2∨ … ∨a n
称这个表示式为 x的原子表示，且是唯一的表示。
这里的唯一性是指：若
x＝ a1∨a 2∨ … ∨a n,x＝ b1∨b 2∨ … ∨b n
都是 x的原子表示，则有
{a1,a2,… an}＝ {b1,b2,… bn}
引理 2的证明令 y＝ a1∨a 2∨ … ∨a n。 由于 ai≤x,i＝ 1,2,… n,所以必有 y≤x 。
由此可知 t1是原子，且 t1≤x 和 t1≤y?。
假如 x∧y?≠0,则存在 B中元素 t1,t2,…,ts，现证明 x∧y?＝ 0。
使得 t1覆盖 0,t2覆盖 t1,…,ts覆盖 ts-1，且 ts＝ x∧y?。
由 t1≤x 可知 t1∈T(x) 。 即存在 ai∈T(x),使得 t1＝ ai。
又由 t1≤y?可知 t1∧y?＝ t1，从而有
t1＝ t1∧y?＝ ai∧ y? ＝ ai∧(a 1∨a 2∨ … ∨a n)?
＝ ai∧(a?1∧a?2∧ … ∧ a?i∧ … ∧?an)
＝ (ai∧a?i)∧(a?1∧ … ∧a?i-1∧a?i+1∧ … ∧a?n)
＝ 0∧a?1∧ … ∧a?i-1∧a?i+1∧ … ∧a?n＝ 0
这与 t1覆盖 0矛盾。 从而证明了 x∧y?＝ 0。
引理２
由 y＝ y∨ 0 ＝ (y∨x)∧( y∨y?)＝ y∨ (x∧y?) ＝ (y∨x)∧1 ＝ y∨x
可知 x≤y 。 综合上述得 x＝ y,即 x＝ a1∨a 2∨ … ∨a n。
设 x＝ b1∨b 2∨ … ∨b m是 x的另一个原子表示，
任取 ai∈{a 1,a2,…,an},假若 ai?{b1,b2,…,bm}。
由引理 1 必有 ai∧b j＝ 0,j＝ 1,2,… m。 又由于 ai≤x,于是
ai＝ ai∧ x ＝ ai∧ (b1∨b 2∨ … ∨b n)
＝ (ai∧b 1)∨(a i∧b 2)∨ … ∨(a i∧b m)
＝ 0∨0∨ … ∨0 ＝ 0
这与 ai是原子矛盾。 从而证明了 ai∈{b1,b2,…,bm}。
同理可证,?bj∈{b 1,b2,…,bm},必有 bj∈{a 1,a2,…,an}，
于是 {a1,a2,…,an}＝ {b1,b2,…,bm}。
有限布尔代数的表示定理定理 13.11 (有限布尔代数的表示定理 ) 设 B是有限布尔代数，
A是 B的全体原子构成的集合,则 B同构于 A的幂集代数 P(A)。
证明 任取 x∈B,令 T(x)＝ {a|a∈B,a 是原子且 a≤ x}
则 T(x)?A，定义函数
,B→ P(A),?(x)＝ T(x),?x∈B
下面证明?是 B到 P(A)的同构映射。
任取 x,y∈B,?b 有
b∈ T(x∧ y)? b∈A 且 b≤ x∧ y
(b∈A 且 b≤ x) 且 (b∈A 且 b≤y)
b∈ T(x)且 b∈ T(y)
b∈ T(x)∩T(y)
从而有 T(x∧ y)＝ T(x)∩T(y),
即?x,y?B 有?(x∧ y)＝?(x)∩?(y)。
定理 13.11证明任取 x,y∈B,设
x＝ a1∨ a2∨ … ∨ an，
y＝ b1∨ b2∨ … ∨ bm
是 x,y的原子表示，则
x∨ y＝ a1∨ a2∨ … ∨ an∨ b1∨ b2∨ … ∨ bm
由引理 2可知
T(x∨ y)＝ {a1,a2,…,an,b1,b2,…,bm}
又由于
T(x)＝ {a1,a2,…,an}，
T(y)＝ {b1,b2,…,bm}
所以 T(x∨ y)＝ T(x)∪T(y)
即?(x∨ y)＝?(x)∪?(y)
定理 13.11证明任取 x∈B,存在 x?∈ B 使得
x∨x?＝ 1,x∧x?＝ 0
因此有
(x)∪?(x?)＝?(x∨x?)＝?(1)＝ A
(x)∩?(x?)＝?(x∧x?)＝?(0)＝?
而?和 A分别为 P(A)的全下界和全上界，
因此?(x?)是?(x)在 P(A)中的补元，即
(x?)＝(x)
综上所述,?是 B到 P(A)的同态映射。
定理 13.11证明下面证明?为双射。
假设?(x)＝?(y)，则有
T(x)＝ T(y)＝ {a1,a2,…,an}
由引理 2可知 x＝ a1∨ a2∨ … ∨ an＝ y
于是?为单射。
任取 {b1,b2,…,bm}∈P(A),
令 x＝ b1∨ b2∨ … ∨ bm,则
(x)＝ T(x)＝ {b1,b2,…,bm}
于是?为满射。
定理得证。
例子考虑 110的正因子的集合 S110关于 gcd,lcm运算构成的布尔代数。
它的原子是 2,5和 11，因此原子的集合 A＝ {2,5,11}。
幂集 P(A)＝ {?,{2},{5},{11},{2,5},{2,11},{5,11},{2,5,11}}。
幂集代数是 <P(A),∩,∪,∽,?,A>。
只要令?,S110→P(A),
(1)＝?,?(2)＝ {2},?(5)＝ {5}，
(11)＝ {11},?(10)＝ {2,5},?(22)＝ {2,11}，
(55)＝ {5,11},?(110)＝ A，
那么 f就是定理 13.11中从 S110到幂集 P(A)的同构映射。
推论 1
推论 1 任何有限布尔代数的基数为 2n,n∈N 。
证明 设 B是有限布尔代数,A是 B的所有原子构成的集合，
且 |A|＝ n,n∈N 。
由定理 13.11 得
B≌ P(A)，而 |P(A)|＝ 2n，所以 |B|＝ 2n。
推论 2
推论 2 任何等势的有限布尔代数都是同构的。
证明 设 B1和 B2是有限布尔代数，且 |B1|=|B2|。
则 B1≌ P(A1),B2≌ P(A2)，其中 A1和 A2分别为 B1和 B2的原子集合。
易见 |A1|＝ |A2|，存在双射 f,A1→ A2。令
,P(A1)→P(A 2),?(x)＝ f(x),?x?A1
下面证明?是 P(A1)到 P(A2)的同构映射。
任取 x,y∈P(A 1)，由定理 7.5有
f(x∪y) ＝ f(x)∪f(y) f(x∩y)?f(x)∩f(y)
又由于 f的单射性，必有 f(x∩y) ＝ f(x)∩f(y)
由于 f(x)∩f( ～ x)＝ f(x∩ ～ x)＝ f(?)＝?
f(x)∪f( ～ x)＝ f(x∪ ～ x)＝ f(A1)＝ A2
得 f(～ x)＝ ～ f(x)，这就证明了?是 P(A1)到 P(A2)的同态映射。
综上所述,有 P(A1)≌ P(A2),根据习题十三章第 19题,B1≌ B2得证。
有限布尔代数的说明
有限布尔代数的基数都是 2的幂。
在同构意义上，对于任何 2n,n为自然数,仅存在一个 2n元的布尔代数 。
下图给出了 1元,2元,4元和 8元的布尔代数。
主要内容
布尔代数的两个等价定义：
– 有补分配格；
– 有两个二元运算并满足交换律,分配律,同一律和补元律的代数系统 。
布尔代数的特殊性质：双重否定律和德摩根律 。
子布尔代数的定义及其判别 。
布尔代数同态的判定：
– f(a∧b) ＝ f(a)∩f(b)( 或 f(a∨b) ＝ f(a)∪f(b)),
– f(a?)＝ -f(a)
对于任意自然数 n,只有一个 2n元的有限布尔代数,就是幂集代数 。
学习要求
能够判断给定偏序集或者代数系统是否构成格 。
能够确定一个命题的对偶命题 。
能够证明格中的等式和不等式 。
能够判别格 L的子集 S是否构成格 。
了解格的同态及其性质 。
能够判别给定的格是否为分配格 。
能够判别布尔代数并证明布尔代数的等式 。
作业习题十三
1,2,3,6,8,12,16,17,19
格的证明方法
格中等式的证明方法证明等式的左边,小于等于,右边，右边,小于等于,左边
。
根据偏序关系的反对称性，得到需要的等式。
格中不等式的证明方法
a≤a (偏序关系的自反性 )
a≤b 且 b≤c? a≤c (偏序关系的传递性 )
a∧b≤a,a∧b≤b,a≤a∨b,a≤a∨b
(下界定义与上界的定义 )
a≤b 且 a≤c? a≤b∧c,b≤a 且 c≤a? b∨c≤a
(最大下界定义与最小上界的定义 )
a≤b 且 c≤d? a∧c≤b∧d,a∨c≤b∨d (保序性 )
13.1 格的定义与性质
13.2 子格与格同态
13.3 分配格与有补格
13.4 布尔代数本章总结作业
13.1 格的定义与性质定义 13.1 设 <S,≤> 是偏序集,如果?x,y∈S,{x,y}都有最小上界和最大下界,则称 S关于偏序 ≤ 作成一个 格 (lattice)。
说明,由于最小上界和最大下界的唯一性，可以把求 {x,y}的最小上界和最大下界看成 x与 y的二元运算 ∨ 和 ∧ 。
x∨ y：表示 x与 y的最小上界
x∧ y：表示 x和 y的最大下界。
本章出现的 ∨ 和 ∧ 符号只代表格中的运算，而不再有其它的含义。
格的实例例 13.1 设 n是正整数,Sn是 n的正因子的集合。 D为整除关系，
则偏序集 <Sn,D>构成格。x,y∈S n，
x∨y 是 lcm(x,y)，即 x与 y的最小公倍数。
x∧y 是 gcd(x,y)，即 x与 y的最大公约数。
下图给出了格 <S8,D>,<S6,D>和 <S30,D>。
例 13.2
例 13.2 判断下列偏序集是否构成格,并说明理由。
(1) <P(B),?>，其中 P(B)是集合 B的幂集。
(2) <Z,≤>,其中 Z是整数集,≤ 为小于或等于关系。
(3) 偏序集的哈斯图分别在下图给出。
例 13.2
解答 (1)是格。
x,y∈P(B),x∨y 就是 x∪y,x∧y 就是 x∩y 。
由于 ∪ 和 ∩ 运算在 P(B)上是封闭的，所以 x∪y,x∩y∈P(B) 。
称 <P(B),?>,为 B的 幂集格 。
(2)是格。
x,y∈Z,x∨y ＝ max(x,y),x∧y ＝ min(x,y)，它们都是整数。
(3)都不是格。
(a)中的 {a,b}没有最大下界。
(b)中的 {b,d}有两个上界 c和 e,但没有最小上界。
(c)中的 {b,c}有三个上界 d,e,f,但没有最小上界。
(d)中的 {a,g}没有最大下界。
例 13.3
例 13.3 设 G是群,L(G)是 G的所有子群的集合。即
L(G)＝ { H|H≤G }
对任意的 H1,H2∈L(G),H1∩H 2也是 G的子群，而 <H1∪H 2>是由
H1∪H 2生成的子群（即包含着 H1∪H 2的最小的子群）。
在 L(G)上定义包含关系?，则 L(G)关于包含关系构成一个格，
称为 G的 子群格 。
易见在 L(G)中,H1∧H 2就是 H1∩H 2,H1∨H 2就是 <H1∪H 2>。
对偶原理定义 13.2 设 f是含有格中元素以及符号＝,≤,≥,∨ 和 ∧ 的命题。令 f*是将 f中的 ≤ 替换成 ≥,≥ 替换成 ≤,∨ 替换成
∧,∧ 替换成 ∨ 所得到的命题。称 f*为 f的 对偶命题 。
例如 在格中令 f是 (a∨b)∧c≤c,则 f*是 (a∧b)∨c≥c 。
格的对偶原理 设 f是含有格中元素以及符号＝,≤,≥,∨ 和
∧ 的命题。若 f对一切格为真，则 f的对偶命题 f*也对一切格为真。
例如 对一切格 L都有?a,b∈L,a∧b≤a
(因为 a和 b的交是 a的一个下界 )
那么 对一切格 L都有?a,b∈L,a∨b≥a
说明 许多格的性质都是互为对偶命题的。
有了格的对偶原理，在证明格的性质时，
只须证明其中的一个命题即可。
格的运算性质定理 13.1 设 <L,≤> 是格，则运算 ∨ 和 ∧ 适合 交换律,结合律,幂等律 和 吸收律,即
(1)交换律?a,b∈L 有
a∨b ＝ b∨a a∧b ＝ b∧a
(2)结合律?a,b,c∈L 有
(a∨b)∨c ＝ a∨(b∨c) (a∧b)∧c ＝ a∧(b∧c)
(3)幂等律?a∈L 有
a∨a ＝ a a∧a ＝ a
(4)吸收律?a,b∈L 有
a∨(a∧b) ＝ a a∧(a∨b) ＝ a
定理 13.1
(1)a∨b 和 b∨a 分别是 {a,b}和 {b,a}的最小上界。
由于 {a,b}＝ {b,a}，所以 a∨b ＝ b∨a 。
由对偶原理,a∧b ＝ b∧a 得证。
(2)由最小上界的定义有
(a∨b)∨c≥a∨b≥a (13.1)
(a∨b)∨c≥a∨b≥b (13.2)
(a∨b)∨c≥c (13.3)
由式 13.2和 13.3有 (a∨b)∨c≥b∨c (13.4)
再由式 13.1和 13.4有 (a∨b)∨c≥a∨(b∨c)
(a∨b)∨c≤a∨(b∨c)
根据偏序关系的反对称性有 (a∨b)∨c ＝ a∨(b∨c)
由对偶原理,(a∧b)∧c ＝ a∧(b∧c) 得证。
定理 13.1
(3)显然 a≤a∨a,
又由 a≤a 可得 a∨a≤a 。
根据反对称性有 a∨a ＝ a，
由对偶原理,a∧a ＝ a 得证。
(4)显然 a∨(a∧b)≥a (13.5)
又由 a≤a,a∧b≤a 可得
a∨(a∧b)≤a (13.6)
由式 13.5和 13.6可得 a∨(a∧b) ＝ a，
根据对偶原理,a∧(a∨b) ＝ a 得证。
定理 13.2
定理 13.2 设 <S,*,?>是具有两个二元运算的代数系统，若对于 *和?运算适合 交换律,结合律,吸收律,则可以适当定义 S中的偏序 ≤,使得 <S,≤> 构成一个格，且 a,b∈S 有
a∧b ＝ a*b,a∨b ＝ a?b。
思路 (1)证明在 S中 *和?运算都适合幂等律。
(2)在 S上定义二元关系 R，并证明 R为偏序关系。
(3)证明 <S,≤> 构成格。
说明 通过规定运算及其基本性质可以给出格的定义。
定理 13.2
a∈S,由吸收律得
(1)证明在 S中 *和?运算都适合幂等律 。
a*a ＝ a*(a?(a*a))＝ a
同理有 a?a＝ a。
(2)在 S上定义二元关系 R,?a,b∈S 有 <a,b>∈R? a?b＝ b
下面证明 R在 S上的偏序。
根据幂等律,?a∈S 都有 a?a＝ a,即 <a,a>∈R,
所以 R在 S上是自反的。
a,b∈S 有
aRb且 bRa? a?b＝ b且 b?a＝ a
a＝ b?a＝ a?b＝ b (由于 a? b=b?a)
所以 R在 S上是反对称的。
定理 13.2
a,b,c∈S 有
aRb且 bRc? a?b＝ b 且 b?c＝ c
a?c＝ a?(b?c)
a?c＝ (a?b)?c
a?c＝ b?c＝ c
aRc
这就证明了 R在 S上是传递的。
综上所述,R为 S上的偏序。
以下把 R记作 ≤ 。
定理 13.2
(3) 证明 <S,≤ >构成格。 即证明 a∨b ＝ a?b,a∧b ＝ a*b 。
a,b∈S 有 a?(a?b)＝ (a?a)?b＝ a?b
b?(a?b)＝ a?(b?b)＝ a?b
根据 ≤ 的定义有 a≤a?b和 b≤a?b,所以 a?b是 {a,b}的上界。
假设 c为 {a,b}的上界,则有 a?c＝ c和 b?c＝ c,从而有
(a?b)?c ＝ a?(b?c) ＝ a?c ＝ c
这就证明了 a?b≤c,所以 a?b是 {a,b}的最小上界，即 a∨b ＝ a?b
为证 a*b是 {a,b}的最大下界,先证首先由 a?b＝ b 可知 a*b＝ a*(a?b)＝ a
反之由 a*b＝ a 可知 a?b ＝ (a*b)?b＝ b?(b*a)＝ b
再由式 (13.7)和 ≤ 的定义有 a≤b? a*b＝ a,依照前边的证明,
类似地可证 a*b是 {a,b}的最大下界,即 a∧b ＝ a*b。
a?b＝ b? a*b＝ a (13.7)
格的等价定义根据定理 13.2，可以给出格的另一个等价定义。
定义 13.3 设 <S,*,?>是代数系统,*和?是二元运算，如果 *和?满足交换律，结合律和吸收律，则 <S,*,?>构成一个 格 (lattice)。
说明 格中的幂等律可以由吸收律推出。
以后我们不再区别是偏序集定义的格，
还是代数系统定义的格，而统称为格 L。
格的性质定理 13.3 设 L是格，则?a,b∈L 有
a≤b? a∧b ＝ a? a∨b ＝ b
证明 先证 a≤b? a∧b ＝ a
由 a≤a 和 a≤b 可知,a是 {a,b}的下界，
故 a≤a∧b 。显然又有 a∧b≤a 。
由反对称性得 a∧b ＝ a。
再证 a∧b ＝ a? a∨b ＝ b。
根据吸收律有 b＝ b∨(b∧a)
由 a∧b ＝ a得 b＝ b∨a,即 a∨b ＝ b。
最后证 a∨b ＝ b? a≤b 。
由 a≤a∨b 得 a≤a∨b ＝ b。
格的性质定理 11.4 设 L是格,?a,b,c,d∈L,若 a≤b 且 c≤d,则
a∧c≤b∧d,a∨c≤b∨d
证明 a∧c≤a≤b
a∧c≤c≤d
因此,a∧c≤b∧d 。
同理可证 a∨c≤b∨d 。
例 13.4
例 13.4 设 L是格，证明?a,b,c∈L 有
a∨(b∧c)≤(a∨b)∧(a∨c)
证明 由 a≤a,b∧c≤b 得
a∨(b∧c)≤a∨b
由 a≤a,b∧c≤c 得
a∨(b∧c)≤a∨c
从而得到 a∨(b∧c)≤(a∨b)∧(a∨c)
说明 在格中分配不等式成立。
一般说来，格中的 ∨ 和 ∧ 运算并不是满足分配律的。
本节小结
偏序集构成格的条件：任意二元子集都有最大下界和最小上界 。
格的实例：正整数的因子格,幂集格,子群格 。
格的性质：对偶原理,格中算律 （ 交换,结合,幂等,
吸收 ）,保序性,分配不等式 。
格作为代数系统的定义 。
格的证明方法
13.2 子格与格同态定义 13.4 设 <L,∧,∨> 是格,S是 L的非空子集，若 S关于 L中的运算 ∧ 和 ∨ 仍构成格，则称 S是 L的 子格 。
例 13.5 设格 L如右图所示。令
S1＝ {a,e,f,g}
S2＝ {a,b,e,g}
则 S1不是 L的子格,S2是 L的子格。
因为对于 e和 f,有 e∧f ＝ c，
但 c?S1。
格同态定义 13.5 设 L1和 L2是格,?,L1→L 2，若?a,b∈L 1 有
(a∧b) ＝?(a)∧?(b),?(a∨b) ＝?(a)∨f(b)
成立，则称?为格 L1到 L2的 同态映射,简称 格同态 。
例 13.6 (1)设 L1＝ {2n|n∈Z+},L2＝ {2n+1|n∈N}
则 L1和 L2关于通常数的小于或等于关系构成格。
令?,L1→L 2,?(x)＝ x-1
不难验证?是 L1到 L2的同态映射，因为对任意的 x,y∈L 1有
(x∨y) ＝?(max(x,y))＝ max(x,y)-1
(x)∨?(y)＝ (x-1)∨(y -1)＝ max(x-1,y-1)＝ max(x,y)-1
(x∧y) ＝?(min(x,y))＝ min(x,y)-1
(x)∧?(y)＝ (x-1)∧(y -1)＝ min(x-1,y-1)＝ min(x,y)-1
即?(x∧y) ＝?(x)∧?(y),?(x∨y) ＝?(x)∨?(y)
例 13.6
(2)如图中的格 L1,L2和 L3，若定义
1:L1→L 2
1(a)＝?1(b)＝?1(c)＝ a1，
1(d)＝ d1
2:L1→L 3
2(a)＝ a2,?2(b)＝ b2,
2(c)＝ c2,?2(d)＝ d2
则?1和?2都不是格同态，因为
1(b∨c) ＝?1(d)＝ d1
1(b)∨?1(c)＝ a1∨a 1＝ a1
2(b∨c) ＝?2(d)＝ d2
2(b)∨?2(c)＝ b2∨c 2＝ c2
从而
1(b∨c)≠?1(b)∨?1(c)
2(b∨c)≠?2(b)∨?2(c)
格同态的性质定理 13.5 设?是格 L1到 L2的映射，
(1)若?是格同态映射，则?是保序映射，即?x,y∈L 1，有
x≤y(x)≤?(y)
(2)若?是双射，则?是格同构映射当且仅当?x,y∈L 1，有
x≤y(x)≤?(y)
证明 (1) 任取 x,y∈L 1,x≤y,
由格的性质知 x∨y ＝ y。
又由于?是格同态映射，必有
(y)＝?(x∨y) ＝?(x)∨?(y)
从而得到?(x)≤?(y)。
定理 13.5(2)的证明充分性。
(2)若?是双射，则?是格同构映射当且仅当?x,y∈L 1，有
x≤y(x)≤?(y)
只须证明?是 L1到 L2的同态映射即可。
任取 x,y∈L 1,令 x∨y ＝ z，由 x≤z 和 y≤z 知
(x)≤?(z),?(y)≤?(z)
从而有?(x)∨?(y)≤?(z)＝?(x∨y)
另一方面，由?(x)∨?(y)∈L 2和?的满射性可知，
必存在 u∈L 1使得?(u)＝?(x)∨?(y)
因此有?(x)≤?(u),?(y)≤?(u)。
由已知条件可得 x≤u,y≤u 。 从而推出 x∨y≤u 。
再次使用已知条件得?(x∨y)≤?(u)＝?(x)∨?(y)。
综合上述有?(x∨y) ＝?(x)∨?(y)。
同理可证?(x∧y) ＝?(x)∧?(y)。
定理 13.5(2)的证明必要性。 由 (1)的结论必有
x≤y(x)≤?(y)
反之，若?(x)≤?(y)，由于?是同构映射，则
(x∨y) ＝?(x)∨?(y)＝?(y)
又由于?是双射，必有 x∨y ＝ y。
从而证明了 x≤y 。
(2)若?是双射，则?是格同构映射当且仅当?x,y∈L 1，有
x≤y(x)≤?(y)
例 13.7
例 13.7 设 L1＝ <S12,D>,L2＝ <S12,≤> 是格，其中 S12是 12的所有正因子构成的集合,D为整除关系,≤ 为通常数的小于或等于关系。令
,S12→S 12,?(x)＝ x
则?是双射，但?不是格 L1到 L2的同构映射。
因为?(2)≤?(3)，但 2不整除 3。
根据定理 13.5可知,?不是同构映射。
格的直积类似于半群,群和环,也可以定义格的直积。
定义 13.6 设 L1和 L2是格，定义 L1× L2上的运算 ∩,∪,
即?<a1,b1>,<a2,b2>∈ L1× L2 有
<a1,b1>∩<a 2,b2>＝ <a1∧a 2,b1∧b 2>
<a1,b1>∪<a 2,b2>＝ <a1∨a 2,b1∨b 2>
称 <L1× L2,∩,∪> 为格 L1和 L2的 直积 。
可以证明 <L1× L2,∩,∪> 仍是格。
格的直积
<a1,b1>,<a2,b2>,<a3,b3>∈L 1× L2，有交换律 <a1,b1>∩<a 2,b2>＝ <a1∧a 2,b1∧b 2> ＝ <a2∧a 1,b2∧b 1>
＝ <a2,b2>∩<a 1,b1>
结合律 (<a1,b1>∩<a 2,b2>)∩<a 3,b3>
＝ <a1∧a 2,b1∧b 2>∩<a 3,b3>
＝ <(a1∧a 2)∧a 3,(b1∧b 2)∧b 3>
＝ <a1∧a 2∧a 3,b1∧b 2∧b 3>
<a1,b1>∩(<a 2,b2>∩<a 3,b3>)＝ <a1∧a 2∧a 3,b1∧b 2∧b 3>
同理可证 ∪ 运算也满足交换律和结合律。
格的直积吸收律 <a1,b1>∩(<a 1,b1>∪<a 2,b2>)
＝ <a1,b1>∩<a 1∨a 2,b1∨b 2>
＝ <a1∧(a 1∨a 2),b1∧(b 1∨b 2)>
＝ <a1,b1>
同理有 <a1,b1>∪(<a 1,b1>∩<a 2,b2>)＝ <a1,b1>
这就证明了 ∩ 和 ∪ 运算满足吸收律。
从而证明 L1× L2仍是格格的直积举例格 L＝ <{0,1},≤>,≤ 为通常的小于或等于关系。则
L× L＝ {<0,0>,<0,1>,<1,0>,<1,1>}，
其中 <0,0>是最小元,<1,1>是最大元，且
<0,0>≤<0,1>≤<1,1>,
<0,0>≤<1,0>≤<1,1>,
而 <0,1>与 <1,0>是不可比的。
易见 L× L与图 13.4的 L1同构。
本节小结
格 L的非空子集 S构成 L的子格的条件：
S对 L的两个运算封闭 。
函数?构成格同态的条件：
(a∧b) ＝?(a)∧?(b)
(a∨b) ＝?(a)∨?(b)
格同态的保序性 。
13.3 分配格与有补格
一般说来，格中运算 ∨ 对 ∧ 满足分配不等式，
即?a,b,c∈L,有
a∨(b∧c)≤(a∨b)∧(a∨c)
但是不一定满足分配律。满足分配律的格称为 分配格 。
定义 13.7 设 <L,∧,∨> 是格，若?a,b,c∈L,有
a∧(b∨c) ＝ (a∧b)∨(a∧c)
a∨(b∧c) ＝ (a∨b)∧(a∨c)
则称 L为 分配格 。
说明 上面两个等式互为对偶式。
在证明 L为分配格时，只须证明其中的一个等式即可。
例 13.8
L1和 L2是分配格,L3和 L4不是分配格。
在 L3中,b∧(c∨d) ＝ b∧e ＝ b
(b∧c)∨(b∧d) ＝ a∨a ＝ a
在 L4中,c∨(b∧d) ＝ c∨a ＝ c
(c∨b)∧(c∨d) ＝ e∧d ＝ d
钻石格 五角格分配格的判别定理 13.6 设 L是格，则 L是分配格当且仅当 L中不含有与钻石格或五角格同构的子格。
证明 略。
推论 (1) 小于五元的格都是分配格。
(2) 任何一条链都是分配格。
例 13.9
说明下图中的格是否为分配格，为什么？
L1,L2和 L3都不是分配格。
{a,b,c,d,e}是 L1的子格，并且同构于钻石格。
{a,b,c,e,f}是 L2的子格，并且同构于五角格。
{a,c,b,e,f}是 L3的子格，也同构于钻石格。
定理 13.7
定理 13.7 格 L是分配格 当且仅当
a,b,c∈L,a∧b ＝ a∧c 且 a∨b ＝ a∨c? b＝ c。
证明 必要性 。a,b,c∈L,有
b ＝ b∨( a∧b ) (吸收律,交换律 )
＝ b∨ (a∧c) (已知条件代入 )
＝ (b∨a )∧(b∨c) (分配律 )
＝ (a∨c )∧(b ∨c ) (已知条件代入,交换律 )
＝ (a∧b )∨c (分配律 )
＝ (a∧c)∨c (已知条件代入 )
＝ c (交换律,吸收律 )
定理 13.7
充分性。 假若?a,b,c∈L,有
a∧b ＝ a∧c 且 a∨b ＝ a∨c? b＝ c
成立，而 L不是分配格。
根据定理 13.6,L中必含有与钻石格或五角格同构的子格。
假设 L中含有与钻石格同构的子格，且该子格为 {u,v,x,y,z}，
其中 u为它的最小元,v为它的最大元。
从而推出
x∧y ＝ x∧z ＝ u,x∨y ＝ x∨z ＝ v
但 y≠z,与已知矛盾。
对五角格的情况同理可证。
v
u
x zy
定理 13.7的应用使用定理 13.7也可以判别一个格是否为分配格。
例如下图中的三个格都不是分配格。
在 L1中有 b∨c ＝ b∨d,b∧c ＝ b∧d,但 c≠d 。
在 L2中有 b∧c ＝ b∧e,b∨c ＝ b∨e,但 c≠e 。
在 L3中有 c∧b ＝ c∧d,c∨b ＝ c∨d,但 b≠d 。
格的全下界和全上界定义 13.8 设 L是格，
若存在 a∈L 使得?x∈L 有 a≤x,则称 a为 L的 全下界 ；
若存在 b∈L 使得?x∈L 有 x≤b,则称 b为 L的 全上界 。
命题 格 L若存在全下界或全上界，一定是唯一的。
证明 以全下界为例，假若 a1和 a2都是格 L的全下界,
则有 a1≤a 2和 a2≤a 1。
根据偏序关系的反对称性必有 a1＝ a2。
记法 将格 L的 全下界记为 0,全上界记为 1。
有界格定义 13.9 设 L是格，若 L存在全下界和全上界，则称 L为 有界格,
并将 L记为 <L,∧,∨,0,1> 。
说明 有限格 L一定是有界格。
举例
设 L是 n元格,且 L＝ {a1,a2,…,an}，那么 a1∧a 2∧ … ∧a n是 L的全下界，而 a1∨a 2∨ … ∨a n是 L的全上界。因此 L是有界格。
对于 无限格 L来说，有的是有界格，有的不是有界格。
如集合 B的 幂集格 <P(B),∩,∪>,不管 B是有穷集还是无穷集，
它都是有界格。它的全下界是空集?,全上界是 B。
整数集 Z关于通常数的小于或等于关系构成的格不是有界格，
因为不存在最小和最大的整数。
有界格的性质定理 13.8 设 <L,∧,∨,0,1> 是有界格，则?a∈L 有
a∧0 ＝ 0 a∨0 ＝ a
a∧1 ＝ a a∨1 ＝ 1
证明 由 a∧0≤0 和 0≤a∧0 可知 a∧0 ＝ 0。
说明 在有界格中，
全下界 0是关于 ∧ 运算的零元,∨ 运算的单位元。
全上界 1是关于 ∨ 运算的零元,∧ 运算的单位元。
对偶原理 对于涉及到有界格的命题，如果其中含有全下界 0或全上界 1，在求该命题的对偶命题时，必须将 0替换成 1，而将 1替换成 0。
例如 a∧0 ＝ 0 和 a∨1 ＝ 1 互为对偶命题，
a∨0 ＝ a 和 a∧1 ＝ a 互为对偶命题。
有界格中的补元定义 13.10 设 <L,∧,∨,0,1> 是有界格,a∈L,
若存在 b∈L 使得
a∧b ＝ 0 和 a∨b ＝ 1
成立，则称 b是 a的 补元 。
说明 若 b是 a的补元，那么 a也是 b的补元。
换句话说,a和 b互为补元。
例 13.10
考虑下图中的四个格。
L1中的 a与 c互为补元，其中 a为全下界,c为全上界,b没有补元。
L2中的 a与 d互为补元，其中 a为全下界,d为全上界,b与 c也互为补元。
L3中的 a与 e互为补元，其中 a为全下界,e为全上界,b的补元是 c
和 d,c的补元是 b和 d,d的补元是 b和 c。 b,c,d每个元素都有两个补元。
L4中的 a与 e互为补元。其中 a为全下界。 e为全上界。 b的补元是 c
和 d,c的补元是 b,d的补元是 b。
有界格中补元的说明在任何有界格中，
全下界 0与全上界 1互补。
对于其他元素，可能存在补元，也可能不存在补元。
如果存在，可能是唯一的，也可能是多个补元。
对于有界分配格，如果它的元素存在补元，一定是唯一的。
有界分配格中补元的唯一性定理 13.9 设 <L,∧,∨,0,1> 是有界分配格。
若 a∈L,且对于 a存在补元 b，则 b是 a的唯一补元。
证明 假设 c∈L 也是 a的补元，则有
a∨c ＝ 1,a∧c ＝ 0
又知 b是 a的补元，故
a∨b ＝ 1,a∧b ＝ 0
从而得到
a∨c ＝ a∨b,a∧c ＝ a∧b
由于 L是分配格，根据定理 13.7,b＝ c。
有补格的定义定义 13.11 设 <L,∧,∨,0,1> 是有界格，若 L中所有元素都有补元存在，则称 L为 有补格 。
L2,L3和 L4是有补格，
L1不是有补格。
L2和 L3是有补格，
L1不是有补格。
本节小结
如果格中一个运算对另一个运算是可分配的,称这个格是分配格 。
分配格的两种判别法：
不存在与钻石格或五角格同构的子格；
对于任意元素 a,b,c,有 a∧b ＝ a∧c 且 a∨b ＝ a∨c?b＝ c。
有界格的定义及其实例 。
格中元素的补元及其性质 （ 分配格中补元的唯一性 ） 。
有补格的定义 。
13.4 布尔代数定义 13.12 如果一个格是 有补分配格,则称它为 布尔格 或 布尔代数 。
说明 在布尔代数中，每个元素都存在着唯一的补元。
可以把求补元的运算看作是布尔代数中的一元运算。
可以把一个布尔代数标记为 <B,∧,∨,＇,0,1>，
＇为求补运算,?a∈B,a＇是 a的补元。
例 13.11
例 13.11 设 S110＝ {1,2,5,10,11,22,55,110}是 110的正因子集合。
令 gcd,lcm分别表示求最大公约数和最小公倍数的运算。问
<S110,gcd,lcm>是否构成布尔代数？为什么？
解答 证明 <S110,gcd,lcm>构成格。
容易验证?x,y,z∈S 110，有
gcd(x,y)∈S 110
lcm(x,y)∈S 110
gcd(x,y)＝ gcd(y,x)
lcm(x,y)＝ lcm(y,x)
gcd(gcd(x,y),z)＝ gcd(x,gcd(y,z))
lcm(lcm(x,y),z)＝ lcm(x,lcm(y,z))
gcd(x,lcm(x,y))＝ x
lcm(x,gcd(x,y))＝ x
二元运算交换律结合律吸收律例 13.11
证明 <S110,gcd,lcm>是分配格。
易验证? x,y,z∈S 110 有
gcd(x,lcm(y,z))＝ lcm(gcd(x,y),gcd(x,z))
证明 <S110,gcd,lcm>是有补格。
1 为 S110中的全下界
110为 S110中的全上界
1和 110互为补元,2和 55互为补元，
5和 22互为补元,10和 11互为补元。
综上所述,<S110,gcd,lcm>为布尔代数。
例 13.12
例 13.12 设 B为任意集合,证明 B的 幂集格 <P(B),∩,∪,～,
,B>构成布尔代数，称为 集合代数 。
证明 P(B)关于 ∩ 和 ∪ 构成格，因为
∩ 和 ∪ 运算满足交换律、结合律和吸收律。
由于 ∩ 和 ∪ 互相可分配，因此 P(B)是分配格，
且全下界是空集?,全上界是 B。
根据绝对补的定义，取全集为 B，
x∈P(B),～ x是 x的补元。
从而证明 P(B)是有补分配格，即布尔代数。
布尔代数的性质定理 13.10 设 <B,∧,∨,′,0,1> 是布尔代数，则
(1)?a∈B,(a＇ )＇＝ a
(2)?a,b∈B,(a∧b) ＇＝ a＇ ∨ b＇,(a∨b) ＇＝ a＇ ∧ b＇
说明 (1)称为 双重否定律 。
(2)称为 德摩根律 。
命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例。
可以证明德摩根律对有限个元素也是正确的。
证明 (1) (a′)′ 是 a′ 的补元,a也是 a′ 的补元。
由补元的唯一性得 (a′)′ ＝ a。
定理 13.10(2)的证明
(2)?a,b∈B,(a∧b) ＇＝ a＇ ∨ b＇,(a∨b) ＇＝ a＇ ∧ b＇
(a∧b) ∨(a ＇ ∨ b＇ )
＝ (a∨a ＇ ∨ b＇ )∧( b∨a ＇ ∨ b＇ )
＝ (1∨b ＇ )∧( a ＇ ∨ 1)
＝ 1∧1
＝ 1
(a∧b)∧ (a＇ ∨ b＇ )
＝ (a∧b ∧a ＇ )∨(a∧ b∧b ＇ )
＝ (0∧b)∨(a∧0)
＝ 0∨0 ＝ 0
所以 a＇ ∨ b＇是 a∧b 的补元，根据补元的唯一性有
(a∧b) ＇＝ a＇ ∨ b＇
同理可证 (a∨b) ＇ = a＇ ∧ b＇。
布尔代数作为代数系统的定义定义 13.13 设 <B,*,?>是代数系统,*和?是二元运算。
若 *和 ° 运算满足：
(1) 交换律,即?a,b∈B 有
a*b＝ b*a,a?b＝ b?a
(2) 分配律,即?a,b,c∈B 有
a*(b?c)＝ (a*b)?(a*c)
a?(b*c)＝ (a?b)*(a?c)
(3) 同一律,即存在 0,1∈B,使得?a∈B 有
a*1＝ a,a?0＝ a
(4) 补元律,即?a∈B,存在 a′ ∈B,使得
a*a′ ＝ 0,a?a′ ＝ 1
则称 <B,*,?>是一个 布尔代数 。
关于布尔代数定义的说明所谓 同一律就是指运算含有单位元的性质,这里的 1是 *运算的单位元,0是运算?的单位元。
可以证明 1和 0分别也是?和 *运算的零元。a∈B 有
a?1 ＝ (a?1)*1 （同一律）
＝ 1*(a?1) （交换律）
＝ (a?a′ )*(a?1) （补元律）
＝ a?(a′* 1) （分配律）
＝ a?a′ （同一律）
＝ 1 （补元律）
同理可证 a*0＝ 0。
关于布尔代数定义的说明为证明以上定义的 <B,*,° >是布尔代数，只需证明它是一个格，即 证明 *和 ° 运算满足结合律和吸收律。
证明吸收律,?a,b∈B 有
a?(a*b)
＝ (a*1)?(a*b) （同一律）
＝ a*(1?b) （分配律）
＝ a*1 （ 1是?运算的零元 )
＝ a （同一律）
同理有 a*(a?b)＝ a。
关于布尔代数定义的说明为证结合律，先证以下命题：
a,b,c∈B,a?b＝ a?c 且 ab＝ ac? b＝ c
由 a?b＝ a?c 且 ab＝ ac 可得
(a?b)*(ab)＝ (a?c)*(ac)
由分配律和交换律得
(a*a?)?b＝ (a*a?)?c
由补元律得
0?b＝ 0?c
由同一律和交换律得
b＝ c
关于布尔代数定义的说明使用这个命题，为证明 (a*b)*c＝ a*(b*c)，只需证明以下两个等式：
(1) a?((a*b)*c)＝ a?(a*(b*c))
(2) a((a*b)*c)＝ a(a*(b*c))
先证明第一个等式，由吸收律有
a?(a*(b*c))＝ a
a?((a*b)*c)
＝ (a?(a*b))*(a?c)(分配律 )
＝ a*(a?c) (吸收律 )
＝ a
所以 (1)式成立。
关于布尔代数定义的说明下面证明 (2)式,a((a*b)*c)＝ a(a*(b*c))
a(a*(b*c))
＝ (aa)*(a(b*c)) (分配律 )
＝ 1*(a(b*c)) (交换律,补元律 )
＝ a(b*c) (交换律,同一律 )
a((a*b)*c)
＝ (a(a*b))*(ac) (分配律 )
＝ ((aa)*(ab))*(ac) (分配律 )
＝ (1*(ab))*(ac) (交换律,补元律 )
＝ (ab)*(ac) (交换律,同一律 )
＝ a(b*c) (分配律 )
所以（ 2）式成立。
布尔代数的子代数定义 13.14 设 <B,∧,∨,?,0,1>是布尔代数,S是 B的非空子集，若 0,1∈S,且 S对 ∧,∨ 和?运算都是封闭的，则称 S
是 B的 子布尔代数 。
例 13.13
例 13.13 设 <B,∧,∨,?,0,1>是布尔代数,a,b∈B,且 a＜ b。令
S＝ {x|x∈B,且 a≤x≤b}
称 S为 B中的 区间,可简记为 [a,b]。
可以证明 [a,b]是一个布尔代数。
显然 S是 B的非空子集，且 a和 b分别为 S的全下界和全上界。
对任意的 x,y∈S 都有
a≤x≤b,a≤y≤b
从而有 a≤x∧y≤b,a≤x∨y≤b
S关于 ∧ 和 ∨ 运算是封闭的。
易见 ∧ 和 ∨ 运算在 S上适合交换律和分配律。
例 13.13
对任意的 x∈S,令 y＝ (a∨x?)∧b ( 下面证明 y为 x得补元。 )
由于 a≤a∨x?,a≤b,故 a≤(a∨x?)∧b 。
同时 (a∨x?)∧b≤b,因此 y∈S 。 又
x∨y ＝ x∨((a∨x?)∧b )
＝ x∨(( a∧b )∨(x?∧b)) (分配律 )
＝ x∨a ∨(x?∧b) (a＜ b)
＝ x∨ (x?∧b) (a≤x)
＝ (x∨x?)∧(x∨b) (分配律 )
＝ 1∧(x∨b) (补元律 )
＝ x∨b (交换律，同一律 )
＝ b (x≤b)
例 13.13
x∧y ＝ x∧((a∨x?)∧b )
＝ x∧ (a∨x?) (x≤b,交换律 )
＝ (x∧a)∨( x∧x?) (分配律 )
＝ (x∧a)∨ 0 (补元律 )
＝ x∧a (同一律 )
＝ a (a≤x)
根据定义 13.13,<S,∧,∨> 构成布尔代数。
其全上界是 a，全下界是 b。
x∈[a,b],x关于这个全上界和全下界的补元是 (a∨x?)∧b 。
当 a＝ 0且 b＝ 1时,[a,b]是 B的子布尔代数。
但当 a≠0 或 b≠1 时,[a,b]不是 B的子布尔代数。
例 13.14
考虑 110的正因子集合 S110关于 gcd,lcm运算构成的布尔代数。
它有以下的子布尔代数：
{1,110}
{1,2,55,110}
{1,5,22,110}
{1,10,11,110}
{1,2,5,10,11,22,55,110}
布尔代数的同态映射定义 13.15 设 <B1,∧,∨,?,0,1>和 <B2,∩,∪,-,θ,E> 是两个布尔代数。这里的 ∩,∪,-泛指布尔代数 B2中的求最大下界、最小上界和补元的运算。 θ 和 E分别是 B2的全下界和全上界。
,B1→B 2。如果对于任意的 a,b∈B 1 有
(a∨b) ＝?(a)∪?(b)
(a∧b) ＝?(a)∩?(b)
(a?) ＝ -?(a)
则称?是布尔代数 B1到 B2的 同态映射,简称 布尔代数的同态 。
说明 类似于其它代数系统，也可以定义布尔代数的单同态、
满同态和同构。
例 13.15
例 13.15 设 <B1,∧,∨,?,0,1>和 <B2,∩,∪,-,θ,E> 是布尔代数。
,B1→B 2。若?a,b∈B 1有
(a∧b) ＝?(a)∩?(b)
(a?) ＝ -?(a)
证明?是 B1到 B2的同态。
证明 只须证明?a,b∈B 1 有?(a∨b) ＝?(a)∪?(b)成立即可。
(a∨b)
＝?(((a∨b)?)?) (双重否定律 )
＝ -?((a∨b)?) (已知 )
＝ -?(a?∧b?) (德摩根律 )
＝ -(?(a?)∩?(b?)) (已知 )
＝ -(-?(a)∩ -?(b)) (已知 )
＝ -(-?(a))∪ -(-?(b)) (德摩根律 )
＝?(a)∪?(b) (双重否定律 )
有限布尔代数的结构定义 13.16 设 L是格,0∈L,a∈L,若?b∈L 有
0＜ b≤a? b＝ a
则称 a是 L中的 原子 。
考虑右图中的几个格。
L1的原子是 a。
L2的原子是 a,b,c。
L3的原子是 a和 b。
若 L是正整数 n的全体正因子关于整除关系构成的格，则 L的原子恰为 n的全体质因子。
若 L是集合 B的幂集合，则 L的原子就是由 B中元素构成的单元集。
引理１
引理 1 设Ｌ是格,a,b是Ｌ中的原子，若 a≠b,则 a∧b ＝ 0。
证明 假设 a∧b≠ 0，则有
0＜ a∧b≤a 和 0＜ a∧b≤b
由于 a,b是原子，则有 a∧b ＝ a 和 a∧b ＝ b，
从而有 a＝ b，与已知矛盾。
引理２
引理２ 设 B是有限的布尔代数,?x∈B,x≠ 0,令
T(x)＝ {a1,a2,…,an}
是 B中所有小于或等于 x的原子构成的集合，则
x＝ a1∨a 2∨ … ∨a n
称这个表示式为 x的原子表示，且是唯一的表示。
这里的唯一性是指：若
x＝ a1∨a 2∨ … ∨a n,x＝ b1∨b 2∨ … ∨b n
都是 x的原子表示，则有
{a1,a2,… an}＝ {b1,b2,… bn}
引理 2的证明令 y＝ a1∨a 2∨ … ∨a n。 由于 ai≤x,i＝ 1,2,… n,所以必有 y≤x 。
由此可知 t1是原子，且 t1≤x 和 t1≤y?。
假如 x∧y?≠0,则存在 B中元素 t1,t2,…,ts，现证明 x∧y?＝ 0。
使得 t1覆盖 0,t2覆盖 t1,…,ts覆盖 ts-1，且 ts＝ x∧y?。
由 t1≤x 可知 t1∈T(x) 。 即存在 ai∈T(x),使得 t1＝ ai。
又由 t1≤y?可知 t1∧y?＝ t1，从而有
t1＝ t1∧y?＝ ai∧ y? ＝ ai∧(a 1∨a 2∨ … ∨a n)?
＝ ai∧(a?1∧a?2∧ … ∧ a?i∧ … ∧?an)
＝ (ai∧a?i)∧(a?1∧ … ∧a?i-1∧a?i+1∧ … ∧a?n)
＝ 0∧a?1∧ … ∧a?i-1∧a?i+1∧ … ∧a?n＝ 0
这与 t1覆盖 0矛盾。 从而证明了 x∧y?＝ 0。
引理２
由 y＝ y∨ 0 ＝ (y∨x)∧( y∨y?)＝ y∨ (x∧y?) ＝ (y∨x)∧1 ＝ y∨x
可知 x≤y 。 综合上述得 x＝ y,即 x＝ a1∨a 2∨ … ∨a n。
设 x＝ b1∨b 2∨ … ∨b m是 x的另一个原子表示，
任取 ai∈{a 1,a2,…,an},假若 ai?{b1,b2,…,bm}。
由引理 1 必有 ai∧b j＝ 0,j＝ 1,2,… m。 又由于 ai≤x,于是
ai＝ ai∧ x ＝ ai∧ (b1∨b 2∨ … ∨b n)
＝ (ai∧b 1)∨(a i∧b 2)∨ … ∨(a i∧b m)
＝ 0∨0∨ … ∨0 ＝ 0
这与 ai是原子矛盾。 从而证明了 ai∈{b1,b2,…,bm}。
同理可证,?bj∈{b 1,b2,…,bm},必有 bj∈{a 1,a2,…,an}，
于是 {a1,a2,…,an}＝ {b1,b2,…,bm}。
有限布尔代数的表示定理定理 13.11 (有限布尔代数的表示定理 ) 设 B是有限布尔代数，
A是 B的全体原子构成的集合,则 B同构于 A的幂集代数 P(A)。
证明 任取 x∈B,令 T(x)＝ {a|a∈B,a 是原子且 a≤ x}
则 T(x)?A，定义函数
,B→ P(A),?(x)＝ T(x),?x∈B
下面证明?是 B到 P(A)的同构映射。
任取 x,y∈B,?b 有
b∈ T(x∧ y)? b∈A 且 b≤ x∧ y
(b∈A 且 b≤ x) 且 (b∈A 且 b≤y)
b∈ T(x)且 b∈ T(y)
b∈ T(x)∩T(y)
从而有 T(x∧ y)＝ T(x)∩T(y),
即?x,y?B 有?(x∧ y)＝?(x)∩?(y)。
定理 13.11证明任取 x,y∈B,设
x＝ a1∨ a2∨ … ∨ an，
y＝ b1∨ b2∨ … ∨ bm
是 x,y的原子表示，则
x∨ y＝ a1∨ a2∨ … ∨ an∨ b1∨ b2∨ … ∨ bm
由引理 2可知
T(x∨ y)＝ {a1,a2,…,an,b1,b2,…,bm}
又由于
T(x)＝ {a1,a2,…,an}，
T(y)＝ {b1,b2,…,bm}
所以 T(x∨ y)＝ T(x)∪T(y)
即?(x∨ y)＝?(x)∪?(y)
定理 13.11证明任取 x∈B,存在 x?∈ B 使得
x∨x?＝ 1,x∧x?＝ 0
因此有
(x)∪?(x?)＝?(x∨x?)＝?(1)＝ A
(x)∩?(x?)＝?(x∧x?)＝?(0)＝?
而?和 A分别为 P(A)的全下界和全上界，
因此?(x?)是?(x)在 P(A)中的补元，即
(x?)＝(x)
综上所述,?是 B到 P(A)的同态映射。
定理 13.11证明下面证明?为双射。
假设?(x)＝?(y)，则有
T(x)＝ T(y)＝ {a1,a2,…,an}
由引理 2可知 x＝ a1∨ a2∨ … ∨ an＝ y
于是?为单射。
任取 {b1,b2,…,bm}∈P(A),
令 x＝ b1∨ b2∨ … ∨ bm,则
(x)＝ T(x)＝ {b1,b2,…,bm}
于是?为满射。
定理得证。
例子考虑 110的正因子的集合 S110关于 gcd,lcm运算构成的布尔代数。
它的原子是 2,5和 11，因此原子的集合 A＝ {2,5,11}。
幂集 P(A)＝ {?,{2},{5},{11},{2,5},{2,11},{5,11},{2,5,11}}。
幂集代数是 <P(A),∩,∪,∽,?,A>。
只要令?,S110→P(A),
(1)＝?,?(2)＝ {2},?(5)＝ {5}，
(11)＝ {11},?(10)＝ {2,5},?(22)＝ {2,11}，
(55)＝ {5,11},?(110)＝ A，
那么 f就是定理 13.11中从 S110到幂集 P(A)的同构映射。
推论 1
推论 1 任何有限布尔代数的基数为 2n,n∈N 。
证明 设 B是有限布尔代数,A是 B的所有原子构成的集合，
且 |A|＝ n,n∈N 。
由定理 13.11 得
B≌ P(A)，而 |P(A)|＝ 2n，所以 |B|＝ 2n。
推论 2
推论 2 任何等势的有限布尔代数都是同构的。
证明 设 B1和 B2是有限布尔代数，且 |B1|=|B2|。
则 B1≌ P(A1),B2≌ P(A2)，其中 A1和 A2分别为 B1和 B2的原子集合。
易见 |A1|＝ |A2|，存在双射 f,A1→ A2。令
,P(A1)→P(A 2),?(x)＝ f(x),?x?A1
下面证明?是 P(A1)到 P(A2)的同构映射。
任取 x,y∈P(A 1)，由定理 7.5有
f(x∪y) ＝ f(x)∪f(y) f(x∩y)?f(x)∩f(y)
又由于 f的单射性，必有 f(x∩y) ＝ f(x)∩f(y)
由于 f(x)∩f( ～ x)＝ f(x∩ ～ x)＝ f(?)＝?
f(x)∪f( ～ x)＝ f(x∪ ～ x)＝ f(A1)＝ A2
得 f(～ x)＝ ～ f(x)，这就证明了?是 P(A1)到 P(A2)的同态映射。
综上所述,有 P(A1)≌ P(A2),根据习题十三章第 19题,B1≌ B2得证。
有限布尔代数的说明
有限布尔代数的基数都是 2的幂。
在同构意义上，对于任何 2n,n为自然数,仅存在一个 2n元的布尔代数 。
下图给出了 1元,2元,4元和 8元的布尔代数。
主要内容
布尔代数的两个等价定义：
– 有补分配格；
– 有两个二元运算并满足交换律,分配律,同一律和补元律的代数系统 。
布尔代数的特殊性质：双重否定律和德摩根律 。
子布尔代数的定义及其判别 。
布尔代数同态的判定：
– f(a∧b) ＝ f(a)∩f(b)( 或 f(a∨b) ＝ f(a)∪f(b)),
– f(a?)＝ -f(a)
对于任意自然数 n,只有一个 2n元的有限布尔代数,就是幂集代数 。
学习要求
能够判断给定偏序集或者代数系统是否构成格 。
能够确定一个命题的对偶命题 。
能够证明格中的等式和不等式 。
能够判别格 L的子集 S是否构成格 。
了解格的同态及其性质 。
能够判别给定的格是否为分配格 。
能够判别布尔代数并证明布尔代数的等式 。
作业习题十三
1,2,3,6,8,12,16,17,19
格的证明方法
格中等式的证明方法证明等式的左边,小于等于,右边，右边,小于等于,左边
。
根据偏序关系的反对称性，得到需要的等式。
格中不等式的证明方法
a≤a (偏序关系的自反性 )
a≤b 且 b≤c? a≤c (偏序关系的传递性 )
a∧b≤a,a∧b≤b,a≤a∨b,a≤a∨b
(下界定义与上界的定义 )
a≤b 且 a≤c? a≤b∧c,b≤a 且 c≤a? b∨c≤a
(最大下界定义与最小上界的定义 )
a≤b 且 c≤d? a∧c≤b∧d,a∨c≤b∨d (保序性 )
