第 8章 格与布尔代数第 8章 格与布尔代数
8.1 格
8.2 布尔代数返回总目录第 8章 格与布尔代数第 8章 格与布尔代数
8.1格
8.1.1格的概念和性质定义 8.1.1 设?X,是偏序集,如果?x,y?X,集合?x,y?
都有最小上界和最大下界,则称?X,是格 。
【 例 8.1】 设 S12＝?1,2,3,4,6,12?是 12的因子构成的集合 。
其上的整除关系 R=x,y?| x?S12∧ y?S12∧ x整除 y?,R是 S12
上的偏序关系,?S12,R?是偏序集 。 写出 S12上的盖住关系
COV S12,画出哈斯图,验证偏序集?S12,R?是格 。
解,S12上的盖住关系
COV S12＝1,2?,?1,3?,?2,4?,?2,6?,?3,6?,
4,12?,?6,12，
哈斯图如图 8.1所示 。 从哈斯图中可看出,集合 S12的任意两个元素都有最小上界和最大下界,故偏序集?S12,R?是格 。
第 8章 格与布尔代数第 8章 格与布尔代数
【 例 8.2】 图 8.2中给出了一些偏序集的哈斯图,判断它们是否构成格 。
解,它们都不是格 。 在 (a)中,?1,2?没有下界,因而没有最大下界 。 在 (b)中,?2,4?虽有两个上界,但没有最小上界 。 在 (c)中,?1,3?没有下界,因而没有最大下界 。 在 (d)中,
2,3?虽有三个上界,但没有最小上界 。
第 8章 格与布尔代数设?X,是格,?x,y?X，今后用 x∨ y表示集合?x,y?的最小上界，二元运算 ∨ 称为并运算；用 x∧ y表示集合?x,y?的最大下界，二元运算 ∧ 称为交运算。
定义 8.1.2 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。 则称?X,∨,∧?是格?X,导出的代数系统 。
在例 4.28中，根据图 4.14，集合a?,?b的最小上界为
a,b?，即?a?∨?b?=?a,b?=?a?∪?b?；它的最大下界为?，
即?a?∧?b?=? =?a?∩?b?。这个结果可以推广到一般情况。
x,y?P (A),x∨ y=x∪ y,x∧ y=x∩y。这样，格?P (A),R导出的代数系统?P (A),∨,∧?实际就是代数系统?P (A),∪,∩?，
所以，二元运算 ∨ 和 ∧ 的运算表如表 8.1和表 8.2所示。
在例 8.1中,根据图 8.1,集合?4,6?的最小上界为 12,即
4∨ 6=12=4 和 6 的最小公倍数；它的最大下界为 2,即
4∧ 6=2=4和 6的最大公约数 。 同样,这个结果也可以推广到一般情况 。 即在格?S12,R?导出的代数系统?S12,∨,∧?中,二元运算 ∨ 是求最小公倍数；二元运算 ∧ 是求最大公约数 。
第 8章 格与布尔代数表 8,1
表 8,2
∨a?
a?
b?
b?
a,b?
aaaa,b?
a,b?
a,b?
bba,ba,b?
a,ba,ba,b?
b?
a,ba,b?
∧aba,b?
aaa?
bbb?
a,baba,b?
第 8章 格与布尔代数下面介绍格的对偶原理 。
设?X,是偏序集,在 X上定义二元关系
=a,b?|?b,a
可以证明?X,也是偏序集 。
定义 8.1.3 设 f是含有格中元素以及符号 =,?,?,∨ 和 ∧ 的命题 。 将 f中的?替换成?,?替换成?,∨ 替换成 ∧,∧ 替换成 ∨,得到一个新命题,所得的命题叫做 f的对偶命题,
记为 f *。
例如,在格中,f为 a∧ (b∨ c)?a,则 f的对偶命题 f *为
a∨ (b∧ c)?a
命题 f和它的对偶命题 f *遵循下列的规则，这规则叫做格的对偶原理。
设 f是含有格中元素以及符号 =,?,?,∨ 和 ∧ 的命题 。
若 f对一切格为真,则 f的对偶命题 f *也对一切格为真 。
格的许多性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只需证明其中的一个就可以了。
第 8章 格与布尔代数定理 8.1.1 设?X,是格,?X,∨,∧?是格?X,导出的代数系统 。 则?a,b,c?X有
⑴ a∨ b=b∨ a,a∧ b=b∧ a (交换律 )
⑵ (a∨ b)∨ c=a∨ (b∨ c)
(a∧ b)∧ c=a∧ (b∧ c) (结合律 )
⑶ a∨ a= a,a∧ a= a (幂等律 )
⑷ a∨ (a∧ b)=a
a∧ (a∨ b)=a (吸收律 )
证明,⑴?a,b?X,?a,b?=?b,a?,所以它们的最小上界相等 。 即 a∨ b=b∨ a,同理可证 a∧ b=b∧ a
⑵ a和 b的最大下界一定是 a,b的下界,即 a∧ b?a，
同理,(a∧ b)∧ c?a∧ b,所以,(a∧ b)∧ c?a∧ b?a
同理有 (a∧ b)∧ c?a∧ b?b 和 (a∧ b)∧ c?c
第 8章 格与布尔代数由以上 3式得 (a∧ b)∧ c?b∧ c和 (a∧ b)∧ c?a∧ (b∧ c)
类似地可证 a∧ (b∧ c)?(a∧ b)∧ c
根据偏序关系的反对称性有 (a∧ b)∧ c= a∧ (b∧ c)
由对偶原理得 (a∨ b)∨ c= a∨ (b∨ c)
⑶ 显然 a?a∨ a,又由?的自反性得 a?a,从而推出
a∨ a?a,根据偏序关系的反对称性有 a∨ a=a
由对偶原理得 a∧ a=a
⑷ 显然 a?a∨ (a∧ b)，
又由 a?a,a∧ b?a得 a∨ (a∧ b)?a,从而得
a∨ (a∧ b)=a。
由对偶原理得 a∧ (a∨ b)=a
第 8章 格与布尔代数定理 8.1.2 设?X,∨,∧?是代数系统,其中 ∨,∧ 都是二元运算 。 如果 ∨ 和 ∧ 满足吸收律,则 ∨ 和 ∧ 满足幂等律 。
证明,a∨ a=a∨ (a∧ (a∨ b))=a,同理可证 a∧ a=a
定理 8.1.3 设?X,∨,∧?是代数系统,其中 ∨,∧ 都是二元运算,满足交换律,结合律和吸收律,则可适当定义 X的偏序关系?,使?X,构成一个格 。
证明,定义 X上的一个二元关系
=a,b?|a,b?X且 a∧ b=a?
⑴ 证明?是 X上的偏序关系 。
由定理 8.1.2知 ∧ 满足幂等律,即 a∧ a=a,所以 a?a。 故
是自反的 。
设 a?b且 b?a,则 a∧ b=a且 b∧ a=b,于是 a=a∧ b=b∧ a
=b。 所以?是反对称的 。
设 a?b且 b?c,则 a∧ b=a且 b∧ c=b,于是 a∧ c=(a∧ b)∧ c
=a∧ (b∧ c)=a∧ b=a,即 a?c,故?是传递的 。
这就证明了?是 X上的偏序关系。
第 8章 格与布尔代数
⑵ 证明?a,b?X,a∧ b是集合?a,b?的最大下界 。 因为
(a∧ b)∧ a=a∧ b和 (a∧ b)∧ b=a∧ b
所以 a∧ b?a且 a∧ b?b,即 a∧ b是?a,b?的下界 。
下证 a∧ b是?a,b?的最大下界 。
设 c是?a,b?的任一下界,即 c?a,c?b,那么有
c∧ a=c,c∧ b=c
而 c∧ (a∧ b)=(c∧ a)∧ b=c∧ b=c
所以 c?a∧ b,即 a∧ b是?a,b?的最大下界 。
⑶ 证明 a∧ b=a的充分必要条件是 a∨ b= b
设 a∧ b=a,由吸收率可得
a∨ b=(a∧ b)∨ b=b∨ (b∧ a)=b,即 a∨ b= b
设 a∨ b=b,由吸收率可得
a∧ b=a∧ (a∨ b)=a,即 a∧ b=a
第 8章 格与布尔代数
⑷ 证明?a,b?X,a∨ b是集合?a,b?的最小上界 。
根据 ⑶,偏序关系?可以等价的定义为：
=a,b?|a,b?X且 a∨ b=b?，
用这个定义和类似于 ⑵ 的方法可以证明 a∨ b是集合?a,b?的最小上界 。
因此,?X,构成一个格 。
根据定理 8.1.3，可以给出格的另一个等价定义。
定义 8.1.4 设?X,*,°?是代数系统,其中 *和 °都是二元运算,如果 *和 °在 X上封闭且满足交换律,结合律和吸收律,
则称?X,*,°?为格 。
根据定义 8.1.4和定理 8.1.1,格?X,导出的代数系统
X,∨,∧?是格,以后不再区分偏序集定义的格和代数系统定义的格,统称为格 。
第 8章 格与布尔代数定理 8.1.4 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。 则?a,b?X有
⑴ a?b当且仅当 a∧ b=a
⑵ a?b当且仅当 a∨ b=b
证明,⑴ 设 a?b,下证 a∧ b=a
由 a?a且 a?b知 a是集合?a,b?的下界,故有 a?a∧ b；另一方面,由于 a∧ b是?a,b?的最大下界,所以是?a,b?的下界,
即 a∧ b?a。 根据偏序关系的反对称性得 a∧ b=a
设 a∧ b=a,下证 a?b
a=a∧ b?b,即 a?b
⑵ 可类似 ⑴ 进行证明 。
第 8章 格与布尔代数定理 8.1.5 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。a,b,c,d?X,若 a?b且 c?d,则 a∨ c?b∨ d，
a∧ c?b∧ d
证明,a?b?b∨ d,c?d?b∨ d,因此 a∨ c?b∨ d
类似的可以证明 a∧ c?b∧ d
定理 8.1.6 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。 则?a,b,c?X有
⑴ a∨ (b∧ c)? (a∨ b)∧ (a∨ c)
⑵ (a∧ b)∨ (a∧ c)? a∧ (b∨ c)
证明,⑴ 根据定理 8.1.5,由 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)
利用对偶原理,即得 ⑵ 。
一般地说,格中的 ∨ 和 ∧ 并不满足分配律 。
第 8章 格与布尔代数
8.1.2子格和格的同态定义 8.1.5 设?X,∨,∧?是格,B是 X的非空子集,如果 B
关于运算 ∨ 和 ∧ 也构成格,则称?B,∨,∧?是?X,∨,∧?的子格 。
在例 8.1中,令 B1＝?1,2,3,6?,B2＝?2,4,6,12?,则
B1,∨,∧?和?B2,∨,∧?是格?S12,∨,∧?的子格 。
令 B3＝?1,2,3,12?,由于 2∨ 3=6,而 6?B3,所以
B3,∨,∧?不是格?S12,∨,∧?的子格 。
以下定义格的同态 。
定义 8.1.6 设?X1,∨ 1,∧ 1?和?X2,∨ 2,∧ 2?是格,其中 ∨ 1,
∧ 1,∨ 2和 ∧ 2都是二元运算 。 f是从 X1到 X2的一个映射,对任意的 a,b?X1有 f(a∨ 1b)=f(a)∨ 2 f(b)，
f(a∧ 1b)=f(a)∧ 2f(b)
则称 f是格?X1,∨ 1,∧ 1?到格?X2,∨ 2,∧ 2?的格同态 。 如果 f是单射,满射和双射,分别称 f是格单同态,格满同态和格同构 。 称?f(X1),∨ 2,∧ 2?是?X1,∨ 1,∧ 1?的格同态像 。
第 8章 格与布尔代数定理 8.1.7 设?X1,?1?和?X2,?2?是格,?X1,∨ 1,∧ 1?和
X2,∨ 2,∧ 2?是它们导出的代数系统 。 f是格?X1,∨ 1,∧ 1?到格
X2,∨ 2,∧ 2?的格同态,则? a,b?X1,如果 a?1b,必有
f(a)?2f(b)
证明,设 a?1b,根据定理 8.1.4,a∧ 1b=a,由于 f 是格
X1,∨ 1,∧ 1?到格?X2,∨ 2,∧ 2?的格同态,所以 f(a)=f(a∧ 1b)=
f (a)∧ 2f (b),再由定理 8.1.4,f (a)?2f (b)。
定理 8.1.7说明格同态是保序的 。 一般地说,定理 8.1.7
的逆并不成立 。
【 例 8.3】 设 A=?a,b,c,d,e?,?A,是格,其哈斯图如图
8.3所示,P(A)是 A的幂集合,R?=x,y?|x?P(A)∧ y?P(A)∧
x?y?是 P(A)上的偏序关系 。P(A),R也是格 。 作映射
f,A→ P (A),定义为,?x?A,f(x)=?y|y?A且 y?x?,即：
f(a)=?a,b,c,d,e?=A,f(b)=?b,e?,f(c)=?c,e?,f(d)=?d,e?,
f(e)=?e?。 证明 f是保序的,但不是格同态 。
第 8章 格与布尔代数证明,?a,b?A,设 a?b，
c?f(a),c?a,由偏序关系的传递性得 c?b,所以 c?f(b)，
即 f(a)?f(b),于是 f(a)R?f(b)。
故 f是保序的 。
对于 b,d?A,b∨ d=a
f(b∨ d)=f(a)=A
f(b)∪ f (d)=?b,e?∪?d,e?
=?b,d,e?
f(b∨ d)≠f(b)∪ f (d)
f不是格同态 。
但是,当 f是格同构时,
定理 8.1.7的逆成立 。
第 8章 格与布尔代数定理 8.1.8 设?X1,?1?和?X2,?2?是格,?X1,∨ 1,∧ 1?和?X2,
∨ 2,∧ 2?是它们导出的代数系统 。 f 是 X1到 X2的双射,则 f 是
X1,∨ 1,∧ 1?到?X2,∨ 2,∧ 2?的格同构的充分必要条件是
a,b?X1,a?1b?f(a)?2f(b)
证明,设 f是?X1,∨ 1,∧ 1?到?X2,∨ 2,∧ 2?的格同构,下证
a,b?X1,a?1b?f(a)?2f(b)
由定理 8.1.7可知,?a,b?X1,如果 a?1b,必有 f(a)?2f(b)
设 f(a)?2f(b),由定理 8.1.4有 f(a)=f(a)∧ 2f(b)=f(a∧ 1b)，
由于 f是双射,故 a∧ 1b=a,所以 a?1b
这就证明 a?1b?f(a)?2f(b)
设?a,b?X1,a?1b?f(a)?2f(b),下证 f 是?X1,∨ 1,∧ 1?到
X2,∨ 2,∧ 2?的格同构 。
设 a∧ 1b=c,则 c?1a,c?1b,f(c)=f(a∧ 1b),f(c)?2f(a)，
f(c)?2f(b),故 f(c)?2f(a)∧ 2f(b)。
设 f(a)∧ 2f(b)=f(d)，则有 f(c)?2f(a)∧ 2f(b)=f(d)，即
f(c)?2f(d)；还有 f(d)?2f(a)和 f(d)?2f(b)。所以有 d?1a和 d?1b，
第 8章 格与布尔代数于是 d?1a∧ 1b,即 d?1c,故 f(d)?2f(c),再由偏序关系的反对称性有 f(c)=f(d)。 即 f(a∧ 1b)=f(c)=f(d)=f (a)∧ 2f(b)
类似地可以证明 f(a∨ 1b)=f (a)∨ 2f(b)
这就证明了 f是?X1,∨ 1,∧ 1?到?X2,∨ 2,∧ 2?的格同构 。
定义 8.1.7 设?X1,?1?和?X2,?2?是格,?X1,∨ 1,∧ 1?和
X2,∨ 2,∧ 2?是它们导出的代数系统 。 其中 ∨ 1,∧ 1,∨ 2和 ∧ 2
都是二元运算 。?a1,b1X1× X2和a2,b2X1× X2,定义 X1× X2上的二元运算 ∨ 3和 ∧ 3为：
a1,b1?∨ 3?a2,b2?=?a1∨ 1a2,b1∨ 2b2?
a1,b1?∧ 3?a2,b2?=?a1∧ 1a2,b1∧ 2b2?
代数系统? X1× X2,∨ 3,∧ 3?称为格?X1,∨ 1,∧ 1?到格?X2,∨ 2,
∧ 2?的直积 。
如果?X1,∨ 1,∧ 1?和?X2,∨ 2,∧ 2?是格，可以证明代数系统?X1× X2,∨ 3,∧ 3?也是格第 8章 格与布尔代数
8.1.3分配格定义 8.1.8 设?X,是格,?X,∨,∧?是?X,导出的代数系统,如果?a,b,c?X有
a∨ (b∧ c)=(a∨ b)∧ (a∨ c) (并运算对交运算可分配 )
a∧ (b∨ c)=(a∧ b)∨ (a∧ c) (交运算对并运算可分配 )
则称?X,∨,∧?为分配格 。
因为 a∨ (b∧ c)=(a∨ b)∧ (a∨ c)和
a∧ (b∨ c)=(a∧ b)∨ (a∧ c)
互为对偶命题,根据对偶原理,定义 8.1.8还可以改写为：
一个格如果交运算对并运算可分配或并运算对交运算可分配,则称该格为分配格 。
第 8章 格与布尔代数
【 例 8.4】 设 A=?a,b,c?,P (A)=,?a?,?b?,?c?,?a,b?,
a,c?,?b,c?,?a,b,c是 A的幂集合,P(A)上的包含关系 R?=
x,y?| x?P (A)∧ y?P (A)∧ x?y?是 P (A)上的偏序关系 。
P (A),R是偏序集,P (A)上的盖住关系
COVP(A)=,?a,,?b,,?c,a?,?a,b,
b?,?a,b,a?,?a,c,c?,?a,c,
b?,?b,c,c?,?b,c,a,b?,?a,b,c,
a,c?,?a,b,c,b,c?,?a,b,c
其哈斯图如图 8.4所示 。P (A),∨,∧?是?P (A),R导出的代数系统,证明?P (A),∨,∧?是分配格 。
证明,前面已经证明了格?P (A),R导出的代数系统
P (A),∨,∧?实际就是代数系统?P (A),∪,∩?,其中 ∪ 是集合的并运算,∩是集合的交运算 。 而集合的并,交运算满足分配律：
第 8章 格与布尔代数
P,Q,R?P (A)
P∪ (Q∩R)=(P∪ Q)∩(P∪ R)
P∩(Q∪ R)=(P∩Q)∪ (P∩R)
所以,?P (A),∨,∧?分配格 。
第 8章 格与布尔代数
【 例 8.5】 A=?a,b,c,d,e?,?A,是格,其哈斯图如图 8.3
所示,证明?A,不是分配格 。
证明,b∨ (c∧ d)=b∨ e=b
(b∨ c)∧ (b∨ d)=a∧ a=a
b∨ (c∧ d)≠ (b∨ c)∧ (b∨ d)
所以,?A,不是分配格 。
本例中的格叫做钻石格,钻石格不是分配格 。
第 8章 格与布尔代数
【 例 8.6】 设 A=?a,b,c,d,e?,
A,是格,其哈斯图如图 8.5所示,
证明?A,不是分配格 。
证明,d∨ (b∧ c)=d∨ e=d
(d∨ b)∧ (d∨ c)=a∧ c=c
d∨ (b∧ c)≠(d∨ b)∧ (d∨ c)
所以,?A,不是分配格 。
本例中的格叫做五角格,五角格也不是分配格 。 钻石格和五角格是两个很重要的格 。
第 8章 格与布尔代数定理 8.1.9 一个格是分配格的充分必要条件是该格中不含有与钻石格或五角格同构的子格 。
这个定理的证明已经超过了本书的范围,故略去 。
推论 1 设?A,是格,如果 |A|＜ 5,则?A,一定是分配格 。
推论 2 设?A,是格,如果?A,是全序集,则?A,
一定是分配格 。
【 例 8.7】 图 8.6给出了两个格的哈斯图 。 试证明它们都不是分配格 。
证明,在图 8.6 (a)中含有与五角格同构的子格，所以不是分配格；在图 8.6 (b)中含有与钻石格同构的子格，所以不是分配格。
第 8章 格与布尔代数第 8章 格与布尔代数定理 8.1.10 设?X,是格,?X,∨,∧?是格?X,导出的代数系统 。X,是分配格的充分必要条件是?a,b,c?X，
当 a∧ b=a∧ c且 a∨ b=a∨ c时,必有 b= c
证明,设?X,是分配格,?a,b,c?X，
a∧ b=a∧ c且 a∨ b=a∨ c
b=b∨ (b∧ a)=b∨ (a∧ b) (吸收律和交换律 )
=b∨ (a∧ c)= (b∨ a)∧ (b∨ c) (已知代入和分配律 )
=(a∨ c)∧ (b∨ c) (交换律和已知代入 )
=(a∧ b)∨ c (分配律 )
=(a∧ c)∨ c (已知条件代入 )
=c (交换律和吸收律 )
设?a,b,c?X,当 a∧ b=a∧ c且 a∨ b=a∨ c时,有 b=c,但
X,∨,∧?不是分配格 。 由定理 8.1.9知?X,∨,∧?中必含有与钻石格或五角格同构的子格 。 假设?X,∨,∧?含有与钻石格同构的子格,且此子格为?S,∨,∧?,其中 S=?u,v,x,y,z?,u
为它的最大元,v为它的最小元 。 从而 x∨ y=u=x∨ z，
x∧ y=v=x∧ z,但 y≠z,与已知矛盾 。
第 8章 格与布尔代数对五角格的情况,可类似证明 。
例如，在图 8.6 (a)中,b∧ c=g=b∧ f且 b∨ c=a=b∨ f，但
c≠f；在图 8.6 (b)中,b∧ c=f= b∧ e且 b∨ c=a= b∨ e，但 c≠e。
根据定理 8.1.10它们不是分配格。
8.1.4有补格定义 8.1.9 设?X,是格,如果?a?X,?x?X都有
a?x (x?a)
则称 a为格?X,的全下 (上 )界,记为 0(1)。
定理 8.1.11 设?X,是格,若格?X,有全下界或全上界,
则它们一定是惟一的 。
证明,用反证法 。
如果有两个全下界 a和 b,a,b?X。 因为 a是全下界,所以
a?b；又因为 b是全下界,所以 b?a。 再由?的反对称性有
a=b
类似地可证明全上界的惟一性 。
第 8章 格与布尔代数定义 8.1.10设?X,是格,?X,∨,∧?是格?X,导出的代数系统 。 若格?X,∨,∧?存在全下界 0和全上界 1,则称
X,∨,∧?为有界格,记为?X,∨,∧,0,1?。
在例 8.4中,?P (A),R是格 。P (A),∨,∧?是?P (A),
R导出的代数系统 。 空集?是格的全下界,而集合 A是格的全上界 。 因而?P (A),∨,∧?是有界格,可记为?P(A)∨,
∧,?,A?。 在例 8.6中,从哈斯图 (图 8.5)中可以看出,a是全上界,而 e是全下界,所以?A,是有界格 。
定理 8.1.12 设?X,∨,∧,0,1?为有界格,则?a?X有
a∧ 0=0,a∨ 0=a
a∧ 1=a,a∨ 1=1
证明,因为 0是全下界且 a∧ 0?X,所以 0?a∧ 0,又因为 a∧ 0?0,由?的反对称性有 a∧ 0=0
显然 a?a,由于 1是全上界,所以有 a?1,从而推出
a?a∧ 1,又因为 a∧ 1?a,再由?的反对称性有 a∧ 1=a
a∨ 0=a 和 a∨ 1=1可以类似地证明 。
第 8章 格与布尔代数设?X,∨,∧,0,1?为有界格,a?X有 a∧ 0=0,因为格满足交换律,所以 0∧ a=0,这说明 0是交运算的零元；同样的道理,0是并运算的幺元,而 1是交运算的幺元和并运算的零元 。
定义 8.1.11 设?X,∨,∧,0,1?为有界格,如果对于 a?X，
b?X,使得 a∨ b=1且 a∧ b=0,则称 b是 a的补元 。
如果 b是 a的补元,从定义 8.1.11可以看出,a也是 b的补元 。 因此,可以说 a和 b是互补的,或者说 a和 b互为补元 。
例如，在例 8.6中，从哈斯图 (图 8.5)中可以看出,b和 c互为补元,b和 d也互为补元,b有两个补元 c和 d。所以格中元素的补元并不惟一。
第 8章 格与布尔代数
【 例 8.8】 图 8.7是一个有界格的哈斯图。找出 a,b,c,d,e的补元。
解,从图 8.7中可以看出,a的补元是 e； b没有补元； c的补元是 d；
d的补元是 c和 e,e的补元是 a和 d，
0和 1互为补元。
显然，在有界格中，全上界 1
的惟一补元是全下界 0，而全下界 0
的惟一补元是全上界 1。除了 1和 0，
其它元素有的有补元，有的没有补元。如果某个元素的补元存在，补元可能有一个，也可能有多个。但在有界分配格中，如果元素的补元存在，则一定惟一。
第 8章 格与布尔代数定理 8.1.13设?X,∨,∧,0,1?为有界分配格,如果对于
a?X,a存在补元 b,则 b是 a的惟一补元 。
证明,因为 b是 a的补元,所以有 a∨ b=1,a∧ b=0
设 c?X,c是 a的另一个补元,同样也有 a∨ c=1，
a∧ c=0
从而有 a∨ b= a∨ c,a∧ b= a∧ c
由于?X,∨,∧,0,1?为分配格,根据定理 8.1.10必有 b=c，
即 a的补元惟一 。
定义 8.1.12设?X,∨,∧,0,1?为有界格,如果?a?X,在
X中都有 a的补元存在,则称?X,∨,∧,0,1?为有补格例如，图 8.8是三个有界格的哈斯图，由于每一个元素至少有一个补元，所以它们都是有补格。
第 8章 格与布尔代数返回章目录第 8章 格与布尔代数
8.2布尔代数定义 8.2.1 有补分配格称为布尔格 。
在布尔格中每一个元素都有补元 。 因为有补格一定是有界格,所以布尔格一定是有界分配格,根据定理 8.1.13，
布尔格中的每一个元素的补元存在且惟一 。 于是可以将求补元的运算看作一元运算且把 a的补元记为 a′。
定义 8.2.2 设?X,是布尔格,?X,∨,∧,′?是格?X,导出的代数系统 。 称代数系统?X,∨,∧,′?为布尔代数 。
在 8.1节中证明了?P (A),R是格，其中 A=?a,b?。
P (A),∪,∩?是?P(A),R导出的代数系统，其中 ∪ 和 ∩是集合并运算和交运算。以后又进一步说明了?P (A),∪,
∩?是分配格和有界格,?是全下界,A是全上界。从而
P(A),∪,∩?是有界分配格。令 A为全集,?T?P(A),T的补集 ~T=A–T?P (A)，满足 T∪ ~T= A和 T∩~T=?，所以 T的补元
T′=~T。根据定义 8.2.2,?P (A),∪,∩,~?是布尔代数。
第 8章 格与布尔代数可以证明,当 A为任意集合时,?P (A),∪,∩,~?也是布尔代数 。 称为集合代数 。 集合代数是布尔代数的一个具体模型 。
布尔代数一定是格 。 根据定理 8.1.1,布尔代数中的两个二元运算满足交换律,结合律,幂等律和吸收律 。 此外,布尔代数还有下面的性质：
定理 8.2.1 设?X,∨,∧,′?为布尔代数,?a,b?X,必有
⑴ (a′)′=a
⑵ (a∨ b)′= a′∧ b′
⑶ (a∧ b)′= a′∨ b′
证明,⑴ a′是 a的补元,a也是 a′的补元,由布尔代数中补元的惟一性有 (a′)′=a
第 8章 格与布尔代数
⑵ (a∨ b)∨ (a′∧ b′)=((a∨ b)∨ a′)∧ ((a∨ b)∨ b′)
=(b∨ (a∨ a′))∧ (a∨ (b∨ b′))
=(b∨ 1)∧ (a∨ 1)=1∧ 1=1
(a∨ b)∧ (a′∧ b′)=(a∧ (a′∧ b′))∨ (b∧ (a′∧ b′))
=((a∧ a′)∧ b′)∨ ((b∧ b′)∧ a′)
=(0∧ b′)∨ (0∧ a′)=0∨ 0=0
所以 (a∨ b)′= a′∧ b′
⑶ 同理可证 (a∧ b)′= a′∨ b′
定理 8.2.1中的 ⑴ 称为双重否定律,⑵ 和 ⑶ 称为德摩根律 。 布尔代数满足双重否定律和德摩根律 。
第 8章 格与布尔代数定理 8.2.2 设?X,*,°,′?是代数系统,其中 *和 °都是二元运算,′是一元运算 。X,*,°,′?是布尔代数的充分必要条件是,⑴ *和 °在 X上封闭且满足交换律 。
⑵ *和 °满足分配律 (满足 *对 °的分配律和 °对 *的分配律 )。
⑶ X中存在运算 *的幺元和运算 °的幺元 。 设运算 *的幺元为 0,运算 °的幺元为 1。 即?a?X,有 a*0=a,a°1=a
⑷?a?X,?a′?X,使得 a*a′=1,a°a′=0
由于篇幅的限制,证明从略 。
定理 8.2.2给出的四个条件可以作为布尔代数的等价定义 。
布尔代数?X,*,°,′?也可以表示成为?X,*,°,′,0,1?,其中
0是运算 *的幺元,1是运算 °的幺元 。
第 8章 格与布尔代数
【 例 8.9】 设 P是所有命题构成的集合,∨,∧ 和?分别是命题的析取,合取和否定联结词 。 证明代数系统?P,∨,∧,
是布尔代数 。
证明,根据第 1章的内容,∨ 和 ∧ 在 P上封闭且满足交换律,分配律 。 命题常元 0(假 )和 1(真 )是集合 P的元素,满足
q?P,q∨ 0=q,q∧ 1=q。q?P,?q?P,满足 q∨?q=1，
q∧?q=0。
根据定理 8.2.2,?P,∨,∧,是布尔代数 。
例 8.9中的布尔代数?P,∧,∨,叫做命题代数，它是布尔代数的又一个模型。
8.2.2布尔代数的子代数和同态定义 8.2.3 设?X,∨,∧,′,0,1? 是布尔代数,B 是 X的非空子集，若 0,1?B且?B,∨,∧,′,0,1? 也是布尔代数。则称
B,∨,∧,′,0,1?是?X,∨,∧,′,0,1?子布尔代数。
第 8章 格与布尔代数定理 8.2.3 设?X,∨,∧,′,0,1?是布尔代数,B是 X的非空子集,若 0,1?B且运算 ∨,∧,′在 B上封闭,则?B,∨,∧,′,0,1?是
X,∨,∧,′,0,1?子布尔代数证明,⑴?a,b?B,因为 B?X,所以 a,b?X。 又因为
X,∨,∧,′,0,1?是布尔代数,故 a∨ b=b∨ a,a∧ b=b∧ a
⑵ 类似 ⑴ 可以证明 *和 °满足分配律 。
⑶ 已知 0,1?B,?a?B?X,a?X,有 a∨ 0=a和 a∧ 1=a
⑷?a?B,由 ′在 B上封闭知有 a′?B,使得 a∨ a′=1，
a∧ a′=0
根据定理 8.2.2,?B,∨,∧,′,0,1? 是布尔代数,它是
X,∨,∧,′,0,1?的子布尔代数 。
为了方便，以下将 x?y且 x≠y记为 x?y。
第 8章 格与布尔代数
【 例 8.10】 设?X,∨,∧,′,0,1?是布尔代数,a,b?X，
a?b,令 S=?x| x?X,a?x且 x?b?
试证明?S,∨,∧,′,0,1?是?X,∨,∧,′,0,1?的子布尔代数 。
证明,由于 a?a且 a?b,所以 a?S,S是 X的非空子集,
由 S的定义知 a是 S的全下界,b是 S的全上界 。x,y?S，
a?x且 x?b,a?y且 y?b
a?x∨ y且 x∨ y?b,a?x∧ y且 x∧ y?b
从而 x∨ y?S且 x∧ y?S,即运算 ∨ 和 ∧ 在 S上封闭 。
x?S,令 y=(a∨ x′)∧ b
由于 a?a∨ x′,a?b,故 a?(a∨ x′)∧ b；
又由于 (a∨ x′)∧ b?b,所以 y=(a∨ x′)∧ b?S,又
x∨ y=x∨ ((a∨ x′)∧ b)
=x∨ ((a∧ b)∨ (x′∧ b)) (分配律 )
=x∨ (a∨ (x′∧ b)) (由定理 8.1.4,a?b?a∧ b=a)
第 8章 格与布尔代数
= (x∨ a)∨ (x′∧ b) (结合律 )
= x∨ (x′∧ b) (由定理 8.1.4,a?x?a∨ x=x)
=(x∨ x′)∧ (x∨ b) (分配律 )
=1∧ (x∨ b) (x′是 x的补元 )
=x∨ b (1是 ∧ 的幺元 )
=b (由定理 8.1.4,x?b?x∨ b=b)
x∧ y=x∧ ((a∨ x′)∧ b)
=(x∧ b)∧ (a∨ x′) (交换律和结合律 )
=x∧ (a∨ x′) (由定理 8.1.4,x?b?x∧ b=x)
=(x∧ a)∨ (x∧ x′) (分配律 )
=(x∧ a)∨ 0 (x′是 x的补元 )
=(x∧ a) (0是 ∨ 的幺元 )
=a (由定理 8.1.4,a?x?a∧ x=a)
所以 x′=y?S,一元运算 ′在 S上封闭 。
根据定理 8.2.3,?S,∨,∧,′,0,1?是?X,∨,∧,′,0,1?的子布尔代数 。
第 8章 格与布尔代数定义 8.2.4 设?X1,∨ 1,∧ 1,′,0,1?和?X2,∨ 2,∧ 2,",?,E?是两个布尔代数,其中 ∨ 1,∧ 1,∨ 2和 ∧ 2都是二元运算,′和 "是一元运算,0和 1 是 X1的全下界和全上界,?,E是 X2的全下界和全上界 。 f是从 X1到 X2的一个映射,对任意的 a,b?X1有
f (a∨ 1b)=f (a)∨ 2f (b)
f (a∧ 1b)=f (a)∧ 2 f (b)
f (a′)=(f (a))"
则称 f是布尔代数?X1,∨ 1,∧ 1,′,0,1?到?X2,∨ 2,∧ 2,",?,E?的同态，简称布尔代数同态。如果 f是单射、满射和双射，
分别称 f是布尔代数单同态、布尔代数满同态和布尔代数同构。称?f (X1),∨ 2,∧ 2,",?,E?是?X1,∨ 1,∧ 1,′,0,1?的布尔代数同态像。
第 8章 格与布尔代数定义 8.2.5 设?X,
是格,具有全下界 0,若
X中的元素 a盖住了 0,则称元素 a为原子 。
根据盖住的定义,a
盖住了 0可以描述为：
0?a 且? b?X,如 果 有
0?b?a,则 a=b。
图 8.10是三个格的哈斯图,在 (a)中,a是原子；
在 (b)中,a,b,c是原子；
在 (c)中,a,b是原子 。
8.2.3有限布尔代数的结构第 8章 格与布尔代数定理 8.2.4 设?X,是格,具有全下界 0,a和 b是原子,
如果 a≠b,则 a∧ b=0。
证明,设 a∧ b≠0,0?a∧ b?a且 0?a∧ b?b,因为 a是原子,所以 a∧ b=a。 同样的道理 a∧ b=b。 于是,a=a∧ b=b。
与假设矛盾 。
在图 8.10的 (b)中,a∧ b=0,a∧ c＝ 0,b∧ c=0；在图
8.10的 (c)中,a∧ b=0。
设?X,是格，如果集合 X是有限集，则称?X,是有限格。
定理 8.2.5 设?X,是有限格,具有全下界 0,则?b?X且
b≠0,至少存在一个原子 a,使得 a?b。
证明,如果 b是一个原子,则 b?b。 定理得证 。
如果 b不是原子,必有 b1使得 0?b1?b。 如果 b1是一个原子,定理得证 。 否则,必有 b2使得 0?b2?b1?b。 ……
第 8章 格与布尔代数由于?X,是有限格,通过有限步总可找到一个原子 bi，
使得
0?bi?…?b2?b1?b
由?的传递性,bi?b
定理 8.2.5中的原子 a不一定惟一,图 8.10的 (c)是有限格,
元素 c有惟一的原子 b,使得 b?c。 图 8.10的 (b)也是有限格,
元素 d却有三个原子 a,b,c,使得 a?d,b?d,c?d。
引理 8.2.1 设?X,是布尔格,0是全下界,a,b?X,则
a∧ b′=0当且仅当 a?b。
证明,设 a∧ b′=0,由 0∨ b=b,有
b=0∨ b=(a∧ b′)∨ b=(a∨ b)∧ (b′∨ b)=(a∨ b)∧ 1=a∨ b
由定理 8.1.4知,a?b。
设 a?b，由于 b′?b′，根据定理 8.1.5有 a∧ b′?b∧ b′，而
b∧ b′=0，所以 a∧ b′?0。又因为 0?a且 0?b′，故有 0?a∧ b′。
由?的反对称性知 a∧ b′=0。
第 8章 格与布尔代数引理 8.2.2设?X,∨,∧,′?是有限布尔代数,0是全下界,
如果?b?X且 b≠0,a1,a2,…,ak是 X中满足 aj?b(j=1,…,k)的所有原子,则 b=a1∨ a2∨ … ∨ ak
证明,因为 aj?b(j=1,…,k),所以 a1∨ a2∨ … ∨ ak?b
再证 b?a1∨ a2∨ … ∨ ak,根据引理 8.2.1,只需证明
b∧ (a1∨ a2∨ … ∨ ak)′=0。
用反证法 。 设 b∧ (a1∨ a2∨ … ∨ ak)′≠0
由定理 8.2.5,至少存在一个原子 a,使得
a?b∧ (a1∨ a2∨ … ∨ ak)′
又因为 b∧ (a1∨ a2∨ … ∨ ak)′?b和
b∧ (a1∨ a2∨ … ∨ ak)′?(a1∨ a2∨ … ∨ ak)′
由?的传递性可得 a?b和 a?(a1∨ a2∨ … ∨ ak)′
因为 a是原子且满足 a?b,所以 a必是原子 a1,a2,…,ak中的一个,因此第 8章 格与布尔代数
a?a1∨ a2∨ … ∨ ak
于是有 a?(a1∨ a2∨ … ∨ ak)∧ (a1∨ a2∨ … ∨ ak)′=0
即 a?0
这与 a是原子相矛盾 。 所以 b∧ (a1∨ a2∨ … ∨ ak)′＝ 0,根据引理 8.2.1有
b?a1∨ a2∨ … ∨ ak
由?的反对称性知 b＝ a1∨ a2∨ … ∨ ak
引理 8.3.3 设?X,∨,∧,′?是有限布尔代数，如果?b?X且
b≠0,a1,a2,…,ak是 X中满足 aj?b(j=1,…,k)的所有原子。则
b=a1∨ a2∨ … ∨ ak是将 b表示为原子的惟一形式。
第 8章 格与布尔代数证明,设有 b的另外一种表示形式
b= ∨ ∨ … ∨ 且 是 X中的原子 。
因为 b是 的最小上界,所以必有?b
(i=1,…,t),而 a1,a2,…,ak是 X中满足 aj?b(j=1,…,k)的所有不同的原子 。 所以,必有 t≤k。
当 t＜ k时,a1,a2,…,ak中必有 使得 ≠,i=1,…,t
于是,∧ =( ∧ a1)∨ ( ∧ a2)∨ … ∨ ( ∧ )∨ …
∨ ( ∧ ak)
= ∧ (a1∨ a2∨ … ∨ ak)
= ∧ ( ∨ ∨ … ∨ )
=( ∧ )∨ ( ∧ )∨ … ∨ ( ∧ )
=0∨ 0∨ … ∨ 0=0
1ja
ija
0ja
0ja
0ja
0ja 0ja 0ja 0ja
0ja
0ja
1ja
0ja
0ja
tjjj aaa,,,21?2ja tja
tjjj aaa,,,21?
2ja tja
0ja 0ja 0ja1ja 2ja tja
ija
第 8章 格与布尔代数从而 =0,与 是原子矛盾 。 所以只能有 t=k
定理 8.2.6 (有限布尔代数表示定理 ) 设?X,∨,∧,′?是由有限布尔格?X,导出的有限布尔代数,S是布尔格?X,
中所有原子的集合,则?X,∨,∧,′?和?P(S),∪,∩,~?同构 。
证明,?x?X，令 T(x)=?a |a?S且 a?x?，显然 T(x)?S。
定义函数 f,X→ P (S),f(x)=T(x),?x?X
⑴ 证明 f是 X到 P (S)的双射函数 。
设 f(x)=f(y),令 f(x)=f(y)=?a1,a2,…,an?,由引理 8.2.3知
x＝ a1∨ a2∨ … ∨ an＝ y。 于是 f是单射 。
设?b1,b2,…,bnP (S),令 x=b1∨ b2∨ … ∨ bn,由运算
∨ 的封闭性得 x?X且 bi?x,i=1,…,n,f(x)=T(x)=?b1,b2,…,
bn?,所以 f是满射 。
故 f是 X到 P (S)的双射函数。
0ja 0ja
第 8章 格与布尔代数
⑵ 证明 f是?X,∨,∧,′?和?P (S),∪,∩,~?同构 。
x,y?X,对于任意的 b
b?T(x∧ y)? b?S且 b?x∧ y
(b?S且 b?x)且 (b?S且 b?y)
b?T(x)且 b?T(y)
b?T(x)∩T(y)
从而有 T(x∧ y)=T(x)∩T(y)，
因此 f(x∧ y)=T(x∧ y)= T(x)∩T(y)= f(x)∩f(y)
x,y?X，
令 T(x)=?a|a?S且 a?x?=?a1,a2,…,an?,则由引理 8.2.3，
x可以惟一的表示为：
x＝ a1∨ a2∨ … ∨ an
令 T(y)=?a|a?S且 a?y?=?b1,b2,…,bm?,则 y可以惟一的表示为：
y=b1∨ b2∨ … ∨ bm
第 8章 格与布尔代数从而 x∨ y= a1∨ a2∨ … ∨ an∨ b1∨ b2∨ … ∨ bm
则有 ai?x∨ y,i=1,…,n,bi?x∨ y,i=1,…,m
所以 T(x∨ y) =?a1,a2,…,an,b1,b2,…,bm?=T(x)∪ T(y)
因此 f(x∨ y)= T(x∨ y)=T(x)∪ T(y)= f(x)∪ f(y)
x?X,?x′?X,使得 x∨ x′=1且 x∧ x′=0
f(x)∪ f(x′)=f(x∨ x′)=f(1)=T(1)=S
(S是?P (S),∪,∩,~?的全上界 )
f(x)∩f(x′)=f(x∧ x′)=f(0)=T(0)=?
(?是?P (S),∪,∩,~?的全下界 )
所以,f(x′)是 f(x)的补元,即 f(x′)=~f(x)
综上所述,?X,∨,∧,′?和?P (S),∪,∩,~?同构 。
第 8章 格与布尔代数由定理 8.2.6可以得到以下的推论：
推论 1 设?X,∨,∧,′?是有限布尔代数,则 |X|=2n,其中 n
是该布尔代数中所有原子的个数 。
证明,设 S是布尔代数?X,∨,∧,′?中所有原子的集合,
|S|=n,由定理 8.2.6知?X,∨,∧,′?和?P (S),∪,∩,~?同构 。 所以 |X|= |P (S)| =2|S|=2n
设?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,“?是两个布尔代数,如果
|X1|=|X2|,则称布尔代数?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,"?等势 。
推论 2 任何等势的有限布尔代数是同构的 。
证明,设?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,,?是两个有限布尔代数,|X1|=|X2|。由定理 8.2.6可以得?X1,∨ 1,∧ 1,′?与
P (S1),∪,∩,~?同构,?X2,∨ 2,∧ 2,,?与?P (S2),∪,∩,~?同构，
其中 S1和 S2分别是 X1和 X2中的所有原子的集合，显然
|P (S1)|=|P (S2)|，由此推出 |S1|=|S2|。因为 S1和 S2都是有限集，
它们之间存在双射函数，设为 g,S1→ S2
第 8章 格与布尔代数令 P (S1)=?A1,A2,…,An?,Bj=?x|x=g(a)且 a?Aj?,则
P (S2)=?B1,B2,…,Bn?。
作双射函数 f,P (S1)→ P (S2),f(Aj)= Bj,j=1,…,n
x?f(Ai∪ Aj)?x=g(a)且 a?Ai∪ Aj
x=g(a)且 (a?Ai或 a?Aj)
(x=g(a)且 a?Ai)或 (x=g(a)且 a?Aj)
(x?f (Ai))或 (x?f (Aj))
x?f (Ai)∪ f (Aj)
所以 f (Ai∪ Aj)=f (Ai)∪ f (Aj)
类似的可以证明 f (Ai∩Aj)=f (Ai)∩f (Aj)
f (Ai)∪ f (~Ai)=f (Ai∪ (~Ai))=f(S1)=S2
f (Ai)∩f (~Ai)=f(Ai∩(~Ai))=f(?)=?
第 8章 格与布尔代数故有 ~f(Ai)=f(~Ai)，即
f是?P (S1),∪,∩,~?到?P (S2),∪,∩,~?的同构映射。
即有限布尔代数?P (S1),∪,∩,~?和?P (S2),∪,∩,~?同构。
所以，有限布尔代数?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,"?也同构。
返回总目录返回章目录
8.1 格
8.2 布尔代数返回总目录第 8章 格与布尔代数第 8章 格与布尔代数
8.1格
8.1.1格的概念和性质定义 8.1.1 设?X,是偏序集,如果?x,y?X,集合?x,y?
都有最小上界和最大下界,则称?X,是格 。
【 例 8.1】 设 S12＝?1,2,3,4,6,12?是 12的因子构成的集合 。
其上的整除关系 R=x,y?| x?S12∧ y?S12∧ x整除 y?,R是 S12
上的偏序关系,?S12,R?是偏序集 。 写出 S12上的盖住关系
COV S12,画出哈斯图,验证偏序集?S12,R?是格 。
解,S12上的盖住关系
COV S12＝1,2?,?1,3?,?2,4?,?2,6?,?3,6?,
4,12?,?6,12，
哈斯图如图 8.1所示 。 从哈斯图中可看出,集合 S12的任意两个元素都有最小上界和最大下界,故偏序集?S12,R?是格 。
第 8章 格与布尔代数第 8章 格与布尔代数
【 例 8.2】 图 8.2中给出了一些偏序集的哈斯图,判断它们是否构成格 。
解,它们都不是格 。 在 (a)中,?1,2?没有下界,因而没有最大下界 。 在 (b)中,?2,4?虽有两个上界,但没有最小上界 。 在 (c)中,?1,3?没有下界,因而没有最大下界 。 在 (d)中,
2,3?虽有三个上界,但没有最小上界 。
第 8章 格与布尔代数设?X,是格,?x,y?X，今后用 x∨ y表示集合?x,y?的最小上界，二元运算 ∨ 称为并运算；用 x∧ y表示集合?x,y?的最大下界，二元运算 ∧ 称为交运算。
定义 8.1.2 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。 则称?X,∨,∧?是格?X,导出的代数系统 。
在例 4.28中，根据图 4.14，集合a?,?b的最小上界为
a,b?，即?a?∨?b?=?a,b?=?a?∪?b?；它的最大下界为?，
即?a?∧?b?=? =?a?∩?b?。这个结果可以推广到一般情况。
x,y?P (A),x∨ y=x∪ y,x∧ y=x∩y。这样，格?P (A),R导出的代数系统?P (A),∨,∧?实际就是代数系统?P (A),∪,∩?，
所以，二元运算 ∨ 和 ∧ 的运算表如表 8.1和表 8.2所示。
在例 8.1中,根据图 8.1,集合?4,6?的最小上界为 12,即
4∨ 6=12=4 和 6 的最小公倍数；它的最大下界为 2,即
4∧ 6=2=4和 6的最大公约数 。 同样,这个结果也可以推广到一般情况 。 即在格?S12,R?导出的代数系统?S12,∨,∧?中,二元运算 ∨ 是求最小公倍数；二元运算 ∧ 是求最大公约数 。
第 8章 格与布尔代数表 8,1
表 8,2
∨a?
a?
b?
b?
a,b?
aaaa,b?
a,b?
a,b?
bba,ba,b?
a,ba,ba,b?
b?
a,ba,b?
∧aba,b?
aaa?
bbb?
a,baba,b?
第 8章 格与布尔代数下面介绍格的对偶原理 。
设?X,是偏序集,在 X上定义二元关系
=a,b?|?b,a
可以证明?X,也是偏序集 。
定义 8.1.3 设 f是含有格中元素以及符号 =,?,?,∨ 和 ∧ 的命题 。 将 f中的?替换成?,?替换成?,∨ 替换成 ∧,∧ 替换成 ∨,得到一个新命题,所得的命题叫做 f的对偶命题,
记为 f *。
例如,在格中,f为 a∧ (b∨ c)?a,则 f的对偶命题 f *为
a∨ (b∧ c)?a
命题 f和它的对偶命题 f *遵循下列的规则，这规则叫做格的对偶原理。
设 f是含有格中元素以及符号 =,?,?,∨ 和 ∧ 的命题 。
若 f对一切格为真,则 f的对偶命题 f *也对一切格为真 。
格的许多性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只需证明其中的一个就可以了。
第 8章 格与布尔代数定理 8.1.1 设?X,是格,?X,∨,∧?是格?X,导出的代数系统 。 则?a,b,c?X有
⑴ a∨ b=b∨ a,a∧ b=b∧ a (交换律 )
⑵ (a∨ b)∨ c=a∨ (b∨ c)
(a∧ b)∧ c=a∧ (b∧ c) (结合律 )
⑶ a∨ a= a,a∧ a= a (幂等律 )
⑷ a∨ (a∧ b)=a
a∧ (a∨ b)=a (吸收律 )
证明,⑴?a,b?X,?a,b?=?b,a?,所以它们的最小上界相等 。 即 a∨ b=b∨ a,同理可证 a∧ b=b∧ a
⑵ a和 b的最大下界一定是 a,b的下界,即 a∧ b?a，
同理,(a∧ b)∧ c?a∧ b,所以,(a∧ b)∧ c?a∧ b?a
同理有 (a∧ b)∧ c?a∧ b?b 和 (a∧ b)∧ c?c
第 8章 格与布尔代数由以上 3式得 (a∧ b)∧ c?b∧ c和 (a∧ b)∧ c?a∧ (b∧ c)
类似地可证 a∧ (b∧ c)?(a∧ b)∧ c
根据偏序关系的反对称性有 (a∧ b)∧ c= a∧ (b∧ c)
由对偶原理得 (a∨ b)∨ c= a∨ (b∨ c)
⑶ 显然 a?a∨ a,又由?的自反性得 a?a,从而推出
a∨ a?a,根据偏序关系的反对称性有 a∨ a=a
由对偶原理得 a∧ a=a
⑷ 显然 a?a∨ (a∧ b)，
又由 a?a,a∧ b?a得 a∨ (a∧ b)?a,从而得
a∨ (a∧ b)=a。
由对偶原理得 a∧ (a∨ b)=a
第 8章 格与布尔代数定理 8.1.2 设?X,∨,∧?是代数系统,其中 ∨,∧ 都是二元运算 。 如果 ∨ 和 ∧ 满足吸收律,则 ∨ 和 ∧ 满足幂等律 。
证明,a∨ a=a∨ (a∧ (a∨ b))=a,同理可证 a∧ a=a
定理 8.1.3 设?X,∨,∧?是代数系统,其中 ∨,∧ 都是二元运算,满足交换律,结合律和吸收律,则可适当定义 X的偏序关系?,使?X,构成一个格 。
证明,定义 X上的一个二元关系
=a,b?|a,b?X且 a∧ b=a?
⑴ 证明?是 X上的偏序关系 。
由定理 8.1.2知 ∧ 满足幂等律,即 a∧ a=a,所以 a?a。 故
是自反的 。
设 a?b且 b?a,则 a∧ b=a且 b∧ a=b,于是 a=a∧ b=b∧ a
=b。 所以?是反对称的 。
设 a?b且 b?c,则 a∧ b=a且 b∧ c=b,于是 a∧ c=(a∧ b)∧ c
=a∧ (b∧ c)=a∧ b=a,即 a?c,故?是传递的 。
这就证明了?是 X上的偏序关系。
第 8章 格与布尔代数
⑵ 证明?a,b?X,a∧ b是集合?a,b?的最大下界 。 因为
(a∧ b)∧ a=a∧ b和 (a∧ b)∧ b=a∧ b
所以 a∧ b?a且 a∧ b?b,即 a∧ b是?a,b?的下界 。
下证 a∧ b是?a,b?的最大下界 。
设 c是?a,b?的任一下界,即 c?a,c?b,那么有
c∧ a=c,c∧ b=c
而 c∧ (a∧ b)=(c∧ a)∧ b=c∧ b=c
所以 c?a∧ b,即 a∧ b是?a,b?的最大下界 。
⑶ 证明 a∧ b=a的充分必要条件是 a∨ b= b
设 a∧ b=a,由吸收率可得
a∨ b=(a∧ b)∨ b=b∨ (b∧ a)=b,即 a∨ b= b
设 a∨ b=b,由吸收率可得
a∧ b=a∧ (a∨ b)=a,即 a∧ b=a
第 8章 格与布尔代数
⑷ 证明?a,b?X,a∨ b是集合?a,b?的最小上界 。
根据 ⑶,偏序关系?可以等价的定义为：
=a,b?|a,b?X且 a∨ b=b?，
用这个定义和类似于 ⑵ 的方法可以证明 a∨ b是集合?a,b?的最小上界 。
因此,?X,构成一个格 。
根据定理 8.1.3，可以给出格的另一个等价定义。
定义 8.1.4 设?X,*,°?是代数系统,其中 *和 °都是二元运算,如果 *和 °在 X上封闭且满足交换律,结合律和吸收律,
则称?X,*,°?为格 。
根据定义 8.1.4和定理 8.1.1,格?X,导出的代数系统
X,∨,∧?是格,以后不再区分偏序集定义的格和代数系统定义的格,统称为格 。
第 8章 格与布尔代数定理 8.1.4 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。 则?a,b?X有
⑴ a?b当且仅当 a∧ b=a
⑵ a?b当且仅当 a∨ b=b
证明,⑴ 设 a?b,下证 a∧ b=a
由 a?a且 a?b知 a是集合?a,b?的下界,故有 a?a∧ b；另一方面,由于 a∧ b是?a,b?的最大下界,所以是?a,b?的下界,
即 a∧ b?a。 根据偏序关系的反对称性得 a∧ b=a
设 a∧ b=a,下证 a?b
a=a∧ b?b,即 a?b
⑵ 可类似 ⑴ 进行证明 。
第 8章 格与布尔代数定理 8.1.5 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。a,b,c,d?X,若 a?b且 c?d,则 a∨ c?b∨ d，
a∧ c?b∧ d
证明,a?b?b∨ d,c?d?b∨ d,因此 a∨ c?b∨ d
类似的可以证明 a∧ c?b∧ d
定理 8.1.6 设?X,是格,∨ 是 X上的并运算,∧ 是 X上的交运算 。 则?a,b,c?X有
⑴ a∨ (b∧ c)? (a∨ b)∧ (a∨ c)
⑵ (a∧ b)∨ (a∧ c)? a∧ (b∨ c)
证明,⑴ 根据定理 8.1.5,由 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)
利用对偶原理,即得 ⑵ 。
一般地说,格中的 ∨ 和 ∧ 并不满足分配律 。
第 8章 格与布尔代数
8.1.2子格和格的同态定义 8.1.5 设?X,∨,∧?是格,B是 X的非空子集,如果 B
关于运算 ∨ 和 ∧ 也构成格,则称?B,∨,∧?是?X,∨,∧?的子格 。
在例 8.1中,令 B1＝?1,2,3,6?,B2＝?2,4,6,12?,则
B1,∨,∧?和?B2,∨,∧?是格?S12,∨,∧?的子格 。
令 B3＝?1,2,3,12?,由于 2∨ 3=6,而 6?B3,所以
B3,∨,∧?不是格?S12,∨,∧?的子格 。
以下定义格的同态 。
定义 8.1.6 设?X1,∨ 1,∧ 1?和?X2,∨ 2,∧ 2?是格,其中 ∨ 1,
∧ 1,∨ 2和 ∧ 2都是二元运算 。 f是从 X1到 X2的一个映射,对任意的 a,b?X1有 f(a∨ 1b)=f(a)∨ 2 f(b)，
f(a∧ 1b)=f(a)∧ 2f(b)
则称 f是格?X1,∨ 1,∧ 1?到格?X2,∨ 2,∧ 2?的格同态 。 如果 f是单射,满射和双射,分别称 f是格单同态,格满同态和格同构 。 称?f(X1),∨ 2,∧ 2?是?X1,∨ 1,∧ 1?的格同态像 。
第 8章 格与布尔代数定理 8.1.7 设?X1,?1?和?X2,?2?是格,?X1,∨ 1,∧ 1?和
X2,∨ 2,∧ 2?是它们导出的代数系统 。 f是格?X1,∨ 1,∧ 1?到格
X2,∨ 2,∧ 2?的格同态,则? a,b?X1,如果 a?1b,必有
f(a)?2f(b)
证明,设 a?1b,根据定理 8.1.4,a∧ 1b=a,由于 f 是格
X1,∨ 1,∧ 1?到格?X2,∨ 2,∧ 2?的格同态,所以 f(a)=f(a∧ 1b)=
f (a)∧ 2f (b),再由定理 8.1.4,f (a)?2f (b)。
定理 8.1.7说明格同态是保序的 。 一般地说,定理 8.1.7
的逆并不成立 。
【 例 8.3】 设 A=?a,b,c,d,e?,?A,是格,其哈斯图如图
8.3所示,P(A)是 A的幂集合,R?=x,y?|x?P(A)∧ y?P(A)∧
x?y?是 P(A)上的偏序关系 。P(A),R也是格 。 作映射
f,A→ P (A),定义为,?x?A,f(x)=?y|y?A且 y?x?,即：
f(a)=?a,b,c,d,e?=A,f(b)=?b,e?,f(c)=?c,e?,f(d)=?d,e?,
f(e)=?e?。 证明 f是保序的,但不是格同态 。
第 8章 格与布尔代数证明,?a,b?A,设 a?b，
c?f(a),c?a,由偏序关系的传递性得 c?b,所以 c?f(b)，
即 f(a)?f(b),于是 f(a)R?f(b)。
故 f是保序的 。
对于 b,d?A,b∨ d=a
f(b∨ d)=f(a)=A
f(b)∪ f (d)=?b,e?∪?d,e?
=?b,d,e?
f(b∨ d)≠f(b)∪ f (d)
f不是格同态 。
但是,当 f是格同构时,
定理 8.1.7的逆成立 。
第 8章 格与布尔代数定理 8.1.8 设?X1,?1?和?X2,?2?是格,?X1,∨ 1,∧ 1?和?X2,
∨ 2,∧ 2?是它们导出的代数系统 。 f 是 X1到 X2的双射,则 f 是
X1,∨ 1,∧ 1?到?X2,∨ 2,∧ 2?的格同构的充分必要条件是
a,b?X1,a?1b?f(a)?2f(b)
证明,设 f是?X1,∨ 1,∧ 1?到?X2,∨ 2,∧ 2?的格同构,下证
a,b?X1,a?1b?f(a)?2f(b)
由定理 8.1.7可知,?a,b?X1,如果 a?1b,必有 f(a)?2f(b)
设 f(a)?2f(b),由定理 8.1.4有 f(a)=f(a)∧ 2f(b)=f(a∧ 1b)，
由于 f是双射,故 a∧ 1b=a,所以 a?1b
这就证明 a?1b?f(a)?2f(b)
设?a,b?X1,a?1b?f(a)?2f(b),下证 f 是?X1,∨ 1,∧ 1?到
X2,∨ 2,∧ 2?的格同构 。
设 a∧ 1b=c,则 c?1a,c?1b,f(c)=f(a∧ 1b),f(c)?2f(a)，
f(c)?2f(b),故 f(c)?2f(a)∧ 2f(b)。
设 f(a)∧ 2f(b)=f(d)，则有 f(c)?2f(a)∧ 2f(b)=f(d)，即
f(c)?2f(d)；还有 f(d)?2f(a)和 f(d)?2f(b)。所以有 d?1a和 d?1b，
第 8章 格与布尔代数于是 d?1a∧ 1b,即 d?1c,故 f(d)?2f(c),再由偏序关系的反对称性有 f(c)=f(d)。 即 f(a∧ 1b)=f(c)=f(d)=f (a)∧ 2f(b)
类似地可以证明 f(a∨ 1b)=f (a)∨ 2f(b)
这就证明了 f是?X1,∨ 1,∧ 1?到?X2,∨ 2,∧ 2?的格同构 。
定义 8.1.7 设?X1,?1?和?X2,?2?是格,?X1,∨ 1,∧ 1?和
X2,∨ 2,∧ 2?是它们导出的代数系统 。 其中 ∨ 1,∧ 1,∨ 2和 ∧ 2
都是二元运算 。?a1,b1X1× X2和a2,b2X1× X2,定义 X1× X2上的二元运算 ∨ 3和 ∧ 3为：
a1,b1?∨ 3?a2,b2?=?a1∨ 1a2,b1∨ 2b2?
a1,b1?∧ 3?a2,b2?=?a1∧ 1a2,b1∧ 2b2?
代数系统? X1× X2,∨ 3,∧ 3?称为格?X1,∨ 1,∧ 1?到格?X2,∨ 2,
∧ 2?的直积 。
如果?X1,∨ 1,∧ 1?和?X2,∨ 2,∧ 2?是格，可以证明代数系统?X1× X2,∨ 3,∧ 3?也是格第 8章 格与布尔代数
8.1.3分配格定义 8.1.8 设?X,是格,?X,∨,∧?是?X,导出的代数系统,如果?a,b,c?X有
a∨ (b∧ c)=(a∨ b)∧ (a∨ c) (并运算对交运算可分配 )
a∧ (b∨ c)=(a∧ b)∨ (a∧ c) (交运算对并运算可分配 )
则称?X,∨,∧?为分配格 。
因为 a∨ (b∧ c)=(a∨ b)∧ (a∨ c)和
a∧ (b∨ c)=(a∧ b)∨ (a∧ c)
互为对偶命题,根据对偶原理,定义 8.1.8还可以改写为：
一个格如果交运算对并运算可分配或并运算对交运算可分配,则称该格为分配格 。
第 8章 格与布尔代数
【 例 8.4】 设 A=?a,b,c?,P (A)=,?a?,?b?,?c?,?a,b?,
a,c?,?b,c?,?a,b,c是 A的幂集合,P(A)上的包含关系 R?=
x,y?| x?P (A)∧ y?P (A)∧ x?y?是 P (A)上的偏序关系 。
P (A),R是偏序集,P (A)上的盖住关系
COVP(A)=,?a,,?b,,?c,a?,?a,b,
b?,?a,b,a?,?a,c,c?,?a,c,
b?,?b,c,c?,?b,c,a,b?,?a,b,c,
a,c?,?a,b,c,b,c?,?a,b,c
其哈斯图如图 8.4所示 。P (A),∨,∧?是?P (A),R导出的代数系统,证明?P (A),∨,∧?是分配格 。
证明,前面已经证明了格?P (A),R导出的代数系统
P (A),∨,∧?实际就是代数系统?P (A),∪,∩?,其中 ∪ 是集合的并运算,∩是集合的交运算 。 而集合的并,交运算满足分配律：
第 8章 格与布尔代数
P,Q,R?P (A)
P∪ (Q∩R)=(P∪ Q)∩(P∪ R)
P∩(Q∪ R)=(P∩Q)∪ (P∩R)
所以,?P (A),∨,∧?分配格 。
第 8章 格与布尔代数
【 例 8.5】 A=?a,b,c,d,e?,?A,是格,其哈斯图如图 8.3
所示,证明?A,不是分配格 。
证明,b∨ (c∧ d)=b∨ e=b
(b∨ c)∧ (b∨ d)=a∧ a=a
b∨ (c∧ d)≠ (b∨ c)∧ (b∨ d)
所以,?A,不是分配格 。
本例中的格叫做钻石格,钻石格不是分配格 。
第 8章 格与布尔代数
【 例 8.6】 设 A=?a,b,c,d,e?,
A,是格,其哈斯图如图 8.5所示,
证明?A,不是分配格 。
证明,d∨ (b∧ c)=d∨ e=d
(d∨ b)∧ (d∨ c)=a∧ c=c
d∨ (b∧ c)≠(d∨ b)∧ (d∨ c)
所以,?A,不是分配格 。
本例中的格叫做五角格,五角格也不是分配格 。 钻石格和五角格是两个很重要的格 。
第 8章 格与布尔代数定理 8.1.9 一个格是分配格的充分必要条件是该格中不含有与钻石格或五角格同构的子格 。
这个定理的证明已经超过了本书的范围,故略去 。
推论 1 设?A,是格,如果 |A|＜ 5,则?A,一定是分配格 。
推论 2 设?A,是格,如果?A,是全序集,则?A,
一定是分配格 。
【 例 8.7】 图 8.6给出了两个格的哈斯图 。 试证明它们都不是分配格 。
证明,在图 8.6 (a)中含有与五角格同构的子格，所以不是分配格；在图 8.6 (b)中含有与钻石格同构的子格，所以不是分配格。
第 8章 格与布尔代数第 8章 格与布尔代数定理 8.1.10 设?X,是格,?X,∨,∧?是格?X,导出的代数系统 。X,是分配格的充分必要条件是?a,b,c?X，
当 a∧ b=a∧ c且 a∨ b=a∨ c时,必有 b= c
证明,设?X,是分配格,?a,b,c?X，
a∧ b=a∧ c且 a∨ b=a∨ c
b=b∨ (b∧ a)=b∨ (a∧ b) (吸收律和交换律 )
=b∨ (a∧ c)= (b∨ a)∧ (b∨ c) (已知代入和分配律 )
=(a∨ c)∧ (b∨ c) (交换律和已知代入 )
=(a∧ b)∨ c (分配律 )
=(a∧ c)∨ c (已知条件代入 )
=c (交换律和吸收律 )
设?a,b,c?X,当 a∧ b=a∧ c且 a∨ b=a∨ c时,有 b=c,但
X,∨,∧?不是分配格 。 由定理 8.1.9知?X,∨,∧?中必含有与钻石格或五角格同构的子格 。 假设?X,∨,∧?含有与钻石格同构的子格,且此子格为?S,∨,∧?,其中 S=?u,v,x,y,z?,u
为它的最大元,v为它的最小元 。 从而 x∨ y=u=x∨ z，
x∧ y=v=x∧ z,但 y≠z,与已知矛盾 。
第 8章 格与布尔代数对五角格的情况,可类似证明 。
例如，在图 8.6 (a)中,b∧ c=g=b∧ f且 b∨ c=a=b∨ f，但
c≠f；在图 8.6 (b)中,b∧ c=f= b∧ e且 b∨ c=a= b∨ e，但 c≠e。
根据定理 8.1.10它们不是分配格。
8.1.4有补格定义 8.1.9 设?X,是格,如果?a?X,?x?X都有
a?x (x?a)
则称 a为格?X,的全下 (上 )界,记为 0(1)。
定理 8.1.11 设?X,是格,若格?X,有全下界或全上界,
则它们一定是惟一的 。
证明,用反证法 。
如果有两个全下界 a和 b,a,b?X。 因为 a是全下界,所以
a?b；又因为 b是全下界,所以 b?a。 再由?的反对称性有
a=b
类似地可证明全上界的惟一性 。
第 8章 格与布尔代数定义 8.1.10设?X,是格,?X,∨,∧?是格?X,导出的代数系统 。 若格?X,∨,∧?存在全下界 0和全上界 1,则称
X,∨,∧?为有界格,记为?X,∨,∧,0,1?。
在例 8.4中,?P (A),R是格 。P (A),∨,∧?是?P (A),
R导出的代数系统 。 空集?是格的全下界,而集合 A是格的全上界 。 因而?P (A),∨,∧?是有界格,可记为?P(A)∨,
∧,?,A?。 在例 8.6中,从哈斯图 (图 8.5)中可以看出,a是全上界,而 e是全下界,所以?A,是有界格 。
定理 8.1.12 设?X,∨,∧,0,1?为有界格,则?a?X有
a∧ 0=0,a∨ 0=a
a∧ 1=a,a∨ 1=1
证明,因为 0是全下界且 a∧ 0?X,所以 0?a∧ 0,又因为 a∧ 0?0,由?的反对称性有 a∧ 0=0
显然 a?a,由于 1是全上界,所以有 a?1,从而推出
a?a∧ 1,又因为 a∧ 1?a,再由?的反对称性有 a∧ 1=a
a∨ 0=a 和 a∨ 1=1可以类似地证明 。
第 8章 格与布尔代数设?X,∨,∧,0,1?为有界格,a?X有 a∧ 0=0,因为格满足交换律,所以 0∧ a=0,这说明 0是交运算的零元；同样的道理,0是并运算的幺元,而 1是交运算的幺元和并运算的零元 。
定义 8.1.11 设?X,∨,∧,0,1?为有界格,如果对于 a?X，
b?X,使得 a∨ b=1且 a∧ b=0,则称 b是 a的补元 。
如果 b是 a的补元,从定义 8.1.11可以看出,a也是 b的补元 。 因此,可以说 a和 b是互补的,或者说 a和 b互为补元 。
例如，在例 8.6中，从哈斯图 (图 8.5)中可以看出,b和 c互为补元,b和 d也互为补元,b有两个补元 c和 d。所以格中元素的补元并不惟一。
第 8章 格与布尔代数
【 例 8.8】 图 8.7是一个有界格的哈斯图。找出 a,b,c,d,e的补元。
解,从图 8.7中可以看出,a的补元是 e； b没有补元； c的补元是 d；
d的补元是 c和 e,e的补元是 a和 d，
0和 1互为补元。
显然，在有界格中，全上界 1
的惟一补元是全下界 0，而全下界 0
的惟一补元是全上界 1。除了 1和 0，
其它元素有的有补元，有的没有补元。如果某个元素的补元存在，补元可能有一个，也可能有多个。但在有界分配格中，如果元素的补元存在，则一定惟一。
第 8章 格与布尔代数定理 8.1.13设?X,∨,∧,0,1?为有界分配格,如果对于
a?X,a存在补元 b,则 b是 a的惟一补元 。
证明,因为 b是 a的补元,所以有 a∨ b=1,a∧ b=0
设 c?X,c是 a的另一个补元,同样也有 a∨ c=1，
a∧ c=0
从而有 a∨ b= a∨ c,a∧ b= a∧ c
由于?X,∨,∧,0,1?为分配格,根据定理 8.1.10必有 b=c，
即 a的补元惟一 。
定义 8.1.12设?X,∨,∧,0,1?为有界格,如果?a?X,在
X中都有 a的补元存在,则称?X,∨,∧,0,1?为有补格例如，图 8.8是三个有界格的哈斯图，由于每一个元素至少有一个补元，所以它们都是有补格。
第 8章 格与布尔代数返回章目录第 8章 格与布尔代数
8.2布尔代数定义 8.2.1 有补分配格称为布尔格 。
在布尔格中每一个元素都有补元 。 因为有补格一定是有界格,所以布尔格一定是有界分配格,根据定理 8.1.13，
布尔格中的每一个元素的补元存在且惟一 。 于是可以将求补元的运算看作一元运算且把 a的补元记为 a′。
定义 8.2.2 设?X,是布尔格,?X,∨,∧,′?是格?X,导出的代数系统 。 称代数系统?X,∨,∧,′?为布尔代数 。
在 8.1节中证明了?P (A),R是格，其中 A=?a,b?。
P (A),∪,∩?是?P(A),R导出的代数系统，其中 ∪ 和 ∩是集合并运算和交运算。以后又进一步说明了?P (A),∪,
∩?是分配格和有界格,?是全下界,A是全上界。从而
P(A),∪,∩?是有界分配格。令 A为全集,?T?P(A),T的补集 ~T=A–T?P (A)，满足 T∪ ~T= A和 T∩~T=?，所以 T的补元
T′=~T。根据定义 8.2.2,?P (A),∪,∩,~?是布尔代数。
第 8章 格与布尔代数可以证明,当 A为任意集合时,?P (A),∪,∩,~?也是布尔代数 。 称为集合代数 。 集合代数是布尔代数的一个具体模型 。
布尔代数一定是格 。 根据定理 8.1.1,布尔代数中的两个二元运算满足交换律,结合律,幂等律和吸收律 。 此外,布尔代数还有下面的性质：
定理 8.2.1 设?X,∨,∧,′?为布尔代数,?a,b?X,必有
⑴ (a′)′=a
⑵ (a∨ b)′= a′∧ b′
⑶ (a∧ b)′= a′∨ b′
证明,⑴ a′是 a的补元,a也是 a′的补元,由布尔代数中补元的惟一性有 (a′)′=a
第 8章 格与布尔代数
⑵ (a∨ b)∨ (a′∧ b′)=((a∨ b)∨ a′)∧ ((a∨ b)∨ b′)
=(b∨ (a∨ a′))∧ (a∨ (b∨ b′))
=(b∨ 1)∧ (a∨ 1)=1∧ 1=1
(a∨ b)∧ (a′∧ b′)=(a∧ (a′∧ b′))∨ (b∧ (a′∧ b′))
=((a∧ a′)∧ b′)∨ ((b∧ b′)∧ a′)
=(0∧ b′)∨ (0∧ a′)=0∨ 0=0
所以 (a∨ b)′= a′∧ b′
⑶ 同理可证 (a∧ b)′= a′∨ b′
定理 8.2.1中的 ⑴ 称为双重否定律,⑵ 和 ⑶ 称为德摩根律 。 布尔代数满足双重否定律和德摩根律 。
第 8章 格与布尔代数定理 8.2.2 设?X,*,°,′?是代数系统,其中 *和 °都是二元运算,′是一元运算 。X,*,°,′?是布尔代数的充分必要条件是,⑴ *和 °在 X上封闭且满足交换律 。
⑵ *和 °满足分配律 (满足 *对 °的分配律和 °对 *的分配律 )。
⑶ X中存在运算 *的幺元和运算 °的幺元 。 设运算 *的幺元为 0,运算 °的幺元为 1。 即?a?X,有 a*0=a,a°1=a
⑷?a?X,?a′?X,使得 a*a′=1,a°a′=0
由于篇幅的限制,证明从略 。
定理 8.2.2给出的四个条件可以作为布尔代数的等价定义 。
布尔代数?X,*,°,′?也可以表示成为?X,*,°,′,0,1?,其中
0是运算 *的幺元,1是运算 °的幺元 。
第 8章 格与布尔代数
【 例 8.9】 设 P是所有命题构成的集合,∨,∧ 和?分别是命题的析取,合取和否定联结词 。 证明代数系统?P,∨,∧,
是布尔代数 。
证明,根据第 1章的内容,∨ 和 ∧ 在 P上封闭且满足交换律,分配律 。 命题常元 0(假 )和 1(真 )是集合 P的元素,满足
q?P,q∨ 0=q,q∧ 1=q。q?P,?q?P,满足 q∨?q=1，
q∧?q=0。
根据定理 8.2.2,?P,∨,∧,是布尔代数 。
例 8.9中的布尔代数?P,∧,∨,叫做命题代数，它是布尔代数的又一个模型。
8.2.2布尔代数的子代数和同态定义 8.2.3 设?X,∨,∧,′,0,1? 是布尔代数,B 是 X的非空子集，若 0,1?B且?B,∨,∧,′,0,1? 也是布尔代数。则称
B,∨,∧,′,0,1?是?X,∨,∧,′,0,1?子布尔代数。
第 8章 格与布尔代数定理 8.2.3 设?X,∨,∧,′,0,1?是布尔代数,B是 X的非空子集,若 0,1?B且运算 ∨,∧,′在 B上封闭,则?B,∨,∧,′,0,1?是
X,∨,∧,′,0,1?子布尔代数证明,⑴?a,b?B,因为 B?X,所以 a,b?X。 又因为
X,∨,∧,′,0,1?是布尔代数,故 a∨ b=b∨ a,a∧ b=b∧ a
⑵ 类似 ⑴ 可以证明 *和 °满足分配律 。
⑶ 已知 0,1?B,?a?B?X,a?X,有 a∨ 0=a和 a∧ 1=a
⑷?a?B,由 ′在 B上封闭知有 a′?B,使得 a∨ a′=1，
a∧ a′=0
根据定理 8.2.2,?B,∨,∧,′,0,1? 是布尔代数,它是
X,∨,∧,′,0,1?的子布尔代数 。
为了方便，以下将 x?y且 x≠y记为 x?y。
第 8章 格与布尔代数
【 例 8.10】 设?X,∨,∧,′,0,1?是布尔代数,a,b?X，
a?b,令 S=?x| x?X,a?x且 x?b?
试证明?S,∨,∧,′,0,1?是?X,∨,∧,′,0,1?的子布尔代数 。
证明,由于 a?a且 a?b,所以 a?S,S是 X的非空子集,
由 S的定义知 a是 S的全下界,b是 S的全上界 。x,y?S，
a?x且 x?b,a?y且 y?b
a?x∨ y且 x∨ y?b,a?x∧ y且 x∧ y?b
从而 x∨ y?S且 x∧ y?S,即运算 ∨ 和 ∧ 在 S上封闭 。
x?S,令 y=(a∨ x′)∧ b
由于 a?a∨ x′,a?b,故 a?(a∨ x′)∧ b；
又由于 (a∨ x′)∧ b?b,所以 y=(a∨ x′)∧ b?S,又
x∨ y=x∨ ((a∨ x′)∧ b)
=x∨ ((a∧ b)∨ (x′∧ b)) (分配律 )
=x∨ (a∨ (x′∧ b)) (由定理 8.1.4,a?b?a∧ b=a)
第 8章 格与布尔代数
= (x∨ a)∨ (x′∧ b) (结合律 )
= x∨ (x′∧ b) (由定理 8.1.4,a?x?a∨ x=x)
=(x∨ x′)∧ (x∨ b) (分配律 )
=1∧ (x∨ b) (x′是 x的补元 )
=x∨ b (1是 ∧ 的幺元 )
=b (由定理 8.1.4,x?b?x∨ b=b)
x∧ y=x∧ ((a∨ x′)∧ b)
=(x∧ b)∧ (a∨ x′) (交换律和结合律 )
=x∧ (a∨ x′) (由定理 8.1.4,x?b?x∧ b=x)
=(x∧ a)∨ (x∧ x′) (分配律 )
=(x∧ a)∨ 0 (x′是 x的补元 )
=(x∧ a) (0是 ∨ 的幺元 )
=a (由定理 8.1.4,a?x?a∧ x=a)
所以 x′=y?S,一元运算 ′在 S上封闭 。
根据定理 8.2.3,?S,∨,∧,′,0,1?是?X,∨,∧,′,0,1?的子布尔代数 。
第 8章 格与布尔代数定义 8.2.4 设?X1,∨ 1,∧ 1,′,0,1?和?X2,∨ 2,∧ 2,",?,E?是两个布尔代数,其中 ∨ 1,∧ 1,∨ 2和 ∧ 2都是二元运算,′和 "是一元运算,0和 1 是 X1的全下界和全上界,?,E是 X2的全下界和全上界 。 f是从 X1到 X2的一个映射,对任意的 a,b?X1有
f (a∨ 1b)=f (a)∨ 2f (b)
f (a∧ 1b)=f (a)∧ 2 f (b)
f (a′)=(f (a))"
则称 f是布尔代数?X1,∨ 1,∧ 1,′,0,1?到?X2,∨ 2,∧ 2,",?,E?的同态，简称布尔代数同态。如果 f是单射、满射和双射，
分别称 f是布尔代数单同态、布尔代数满同态和布尔代数同构。称?f (X1),∨ 2,∧ 2,",?,E?是?X1,∨ 1,∧ 1,′,0,1?的布尔代数同态像。
第 8章 格与布尔代数定义 8.2.5 设?X,
是格,具有全下界 0,若
X中的元素 a盖住了 0,则称元素 a为原子 。
根据盖住的定义,a
盖住了 0可以描述为：
0?a 且? b?X,如 果 有
0?b?a,则 a=b。
图 8.10是三个格的哈斯图,在 (a)中,a是原子；
在 (b)中,a,b,c是原子；
在 (c)中,a,b是原子 。
8.2.3有限布尔代数的结构第 8章 格与布尔代数定理 8.2.4 设?X,是格,具有全下界 0,a和 b是原子,
如果 a≠b,则 a∧ b=0。
证明,设 a∧ b≠0,0?a∧ b?a且 0?a∧ b?b,因为 a是原子,所以 a∧ b=a。 同样的道理 a∧ b=b。 于是,a=a∧ b=b。
与假设矛盾 。
在图 8.10的 (b)中,a∧ b=0,a∧ c＝ 0,b∧ c=0；在图
8.10的 (c)中,a∧ b=0。
设?X,是格，如果集合 X是有限集，则称?X,是有限格。
定理 8.2.5 设?X,是有限格,具有全下界 0,则?b?X且
b≠0,至少存在一个原子 a,使得 a?b。
证明,如果 b是一个原子,则 b?b。 定理得证 。
如果 b不是原子,必有 b1使得 0?b1?b。 如果 b1是一个原子,定理得证 。 否则,必有 b2使得 0?b2?b1?b。 ……
第 8章 格与布尔代数由于?X,是有限格,通过有限步总可找到一个原子 bi，
使得
0?bi?…?b2?b1?b
由?的传递性,bi?b
定理 8.2.5中的原子 a不一定惟一,图 8.10的 (c)是有限格,
元素 c有惟一的原子 b,使得 b?c。 图 8.10的 (b)也是有限格,
元素 d却有三个原子 a,b,c,使得 a?d,b?d,c?d。
引理 8.2.1 设?X,是布尔格,0是全下界,a,b?X,则
a∧ b′=0当且仅当 a?b。
证明,设 a∧ b′=0,由 0∨ b=b,有
b=0∨ b=(a∧ b′)∨ b=(a∨ b)∧ (b′∨ b)=(a∨ b)∧ 1=a∨ b
由定理 8.1.4知,a?b。
设 a?b，由于 b′?b′，根据定理 8.1.5有 a∧ b′?b∧ b′，而
b∧ b′=0，所以 a∧ b′?0。又因为 0?a且 0?b′，故有 0?a∧ b′。
由?的反对称性知 a∧ b′=0。
第 8章 格与布尔代数引理 8.2.2设?X,∨,∧,′?是有限布尔代数,0是全下界,
如果?b?X且 b≠0,a1,a2,…,ak是 X中满足 aj?b(j=1,…,k)的所有原子,则 b=a1∨ a2∨ … ∨ ak
证明,因为 aj?b(j=1,…,k),所以 a1∨ a2∨ … ∨ ak?b
再证 b?a1∨ a2∨ … ∨ ak,根据引理 8.2.1,只需证明
b∧ (a1∨ a2∨ … ∨ ak)′=0。
用反证法 。 设 b∧ (a1∨ a2∨ … ∨ ak)′≠0
由定理 8.2.5,至少存在一个原子 a,使得
a?b∧ (a1∨ a2∨ … ∨ ak)′
又因为 b∧ (a1∨ a2∨ … ∨ ak)′?b和
b∧ (a1∨ a2∨ … ∨ ak)′?(a1∨ a2∨ … ∨ ak)′
由?的传递性可得 a?b和 a?(a1∨ a2∨ … ∨ ak)′
因为 a是原子且满足 a?b,所以 a必是原子 a1,a2,…,ak中的一个,因此第 8章 格与布尔代数
a?a1∨ a2∨ … ∨ ak
于是有 a?(a1∨ a2∨ … ∨ ak)∧ (a1∨ a2∨ … ∨ ak)′=0
即 a?0
这与 a是原子相矛盾 。 所以 b∧ (a1∨ a2∨ … ∨ ak)′＝ 0,根据引理 8.2.1有
b?a1∨ a2∨ … ∨ ak
由?的反对称性知 b＝ a1∨ a2∨ … ∨ ak
引理 8.3.3 设?X,∨,∧,′?是有限布尔代数，如果?b?X且
b≠0,a1,a2,…,ak是 X中满足 aj?b(j=1,…,k)的所有原子。则
b=a1∨ a2∨ … ∨ ak是将 b表示为原子的惟一形式。
第 8章 格与布尔代数证明,设有 b的另外一种表示形式
b= ∨ ∨ … ∨ 且 是 X中的原子 。
因为 b是 的最小上界,所以必有?b
(i=1,…,t),而 a1,a2,…,ak是 X中满足 aj?b(j=1,…,k)的所有不同的原子 。 所以,必有 t≤k。
当 t＜ k时,a1,a2,…,ak中必有 使得 ≠,i=1,…,t
于是,∧ =( ∧ a1)∨ ( ∧ a2)∨ … ∨ ( ∧ )∨ …
∨ ( ∧ ak)
= ∧ (a1∨ a2∨ … ∨ ak)
= ∧ ( ∨ ∨ … ∨ )
=( ∧ )∨ ( ∧ )∨ … ∨ ( ∧ )
=0∨ 0∨ … ∨ 0=0
1ja
ija
0ja
0ja
0ja
0ja 0ja 0ja 0ja
0ja
0ja
1ja
0ja
0ja
tjjj aaa,,,21?2ja tja
tjjj aaa,,,21?
2ja tja
0ja 0ja 0ja1ja 2ja tja
ija
第 8章 格与布尔代数从而 =0,与 是原子矛盾 。 所以只能有 t=k
定理 8.2.6 (有限布尔代数表示定理 ) 设?X,∨,∧,′?是由有限布尔格?X,导出的有限布尔代数,S是布尔格?X,
中所有原子的集合,则?X,∨,∧,′?和?P(S),∪,∩,~?同构 。
证明,?x?X，令 T(x)=?a |a?S且 a?x?，显然 T(x)?S。
定义函数 f,X→ P (S),f(x)=T(x),?x?X
⑴ 证明 f是 X到 P (S)的双射函数 。
设 f(x)=f(y),令 f(x)=f(y)=?a1,a2,…,an?,由引理 8.2.3知
x＝ a1∨ a2∨ … ∨ an＝ y。 于是 f是单射 。
设?b1,b2,…,bnP (S),令 x=b1∨ b2∨ … ∨ bn,由运算
∨ 的封闭性得 x?X且 bi?x,i=1,…,n,f(x)=T(x)=?b1,b2,…,
bn?,所以 f是满射 。
故 f是 X到 P (S)的双射函数。
0ja 0ja
第 8章 格与布尔代数
⑵ 证明 f是?X,∨,∧,′?和?P (S),∪,∩,~?同构 。
x,y?X,对于任意的 b
b?T(x∧ y)? b?S且 b?x∧ y
(b?S且 b?x)且 (b?S且 b?y)
b?T(x)且 b?T(y)
b?T(x)∩T(y)
从而有 T(x∧ y)=T(x)∩T(y)，
因此 f(x∧ y)=T(x∧ y)= T(x)∩T(y)= f(x)∩f(y)
x,y?X，
令 T(x)=?a|a?S且 a?x?=?a1,a2,…,an?,则由引理 8.2.3，
x可以惟一的表示为：
x＝ a1∨ a2∨ … ∨ an
令 T(y)=?a|a?S且 a?y?=?b1,b2,…,bm?,则 y可以惟一的表示为：
y=b1∨ b2∨ … ∨ bm
第 8章 格与布尔代数从而 x∨ y= a1∨ a2∨ … ∨ an∨ b1∨ b2∨ … ∨ bm
则有 ai?x∨ y,i=1,…,n,bi?x∨ y,i=1,…,m
所以 T(x∨ y) =?a1,a2,…,an,b1,b2,…,bm?=T(x)∪ T(y)
因此 f(x∨ y)= T(x∨ y)=T(x)∪ T(y)= f(x)∪ f(y)
x?X,?x′?X,使得 x∨ x′=1且 x∧ x′=0
f(x)∪ f(x′)=f(x∨ x′)=f(1)=T(1)=S
(S是?P (S),∪,∩,~?的全上界 )
f(x)∩f(x′)=f(x∧ x′)=f(0)=T(0)=?
(?是?P (S),∪,∩,~?的全下界 )
所以,f(x′)是 f(x)的补元,即 f(x′)=~f(x)
综上所述,?X,∨,∧,′?和?P (S),∪,∩,~?同构 。
第 8章 格与布尔代数由定理 8.2.6可以得到以下的推论：
推论 1 设?X,∨,∧,′?是有限布尔代数,则 |X|=2n,其中 n
是该布尔代数中所有原子的个数 。
证明,设 S是布尔代数?X,∨,∧,′?中所有原子的集合,
|S|=n,由定理 8.2.6知?X,∨,∧,′?和?P (S),∪,∩,~?同构 。 所以 |X|= |P (S)| =2|S|=2n
设?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,“?是两个布尔代数,如果
|X1|=|X2|,则称布尔代数?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,"?等势 。
推论 2 任何等势的有限布尔代数是同构的 。
证明,设?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,,?是两个有限布尔代数,|X1|=|X2|。由定理 8.2.6可以得?X1,∨ 1,∧ 1,′?与
P (S1),∪,∩,~?同构,?X2,∨ 2,∧ 2,,?与?P (S2),∪,∩,~?同构，
其中 S1和 S2分别是 X1和 X2中的所有原子的集合，显然
|P (S1)|=|P (S2)|，由此推出 |S1|=|S2|。因为 S1和 S2都是有限集，
它们之间存在双射函数，设为 g,S1→ S2
第 8章 格与布尔代数令 P (S1)=?A1,A2,…,An?,Bj=?x|x=g(a)且 a?Aj?,则
P (S2)=?B1,B2,…,Bn?。
作双射函数 f,P (S1)→ P (S2),f(Aj)= Bj,j=1,…,n
x?f(Ai∪ Aj)?x=g(a)且 a?Ai∪ Aj
x=g(a)且 (a?Ai或 a?Aj)
(x=g(a)且 a?Ai)或 (x=g(a)且 a?Aj)
(x?f (Ai))或 (x?f (Aj))
x?f (Ai)∪ f (Aj)
所以 f (Ai∪ Aj)=f (Ai)∪ f (Aj)
类似的可以证明 f (Ai∩Aj)=f (Ai)∩f (Aj)
f (Ai)∪ f (~Ai)=f (Ai∪ (~Ai))=f(S1)=S2
f (Ai)∩f (~Ai)=f(Ai∩(~Ai))=f(?)=?
第 8章 格与布尔代数故有 ~f(Ai)=f(~Ai)，即
f是?P (S1),∪,∩,~?到?P (S2),∪,∩,~?的同构映射。
即有限布尔代数?P (S1),∪,∩,~?和?P (S2),∪,∩,~?同构。
所以，有限布尔代数?X1,∨ 1,∧ 1,′?和?X2,∨ 2,∧ 2,"?也同构。
返回总目录返回章目录
