返回：0100 离散数学课程总目录 · 上一章：0117 环与域 · 下一章：0119 组合数学引言、鸽巢原理与 Ramsey 定理

1、学习目标

本章把偏序集中的“最大下界”和“最小上界”代数化，得到格。随后沿着“格 → 模格 → 分配格 → 有补格 → 布尔代数”的路线，学习如何从哈斯图和代数等式判断结构。

主线：

1
2
3
4
5
格：任意两个元素都有 meet 和 join
模格：满足模律，等价于不含五角格 N5 子格
分配格：满足分配律，等价于不含 N5 与钻石格 M3 子格
有补格：有界格中每个元素都有补元
布尔代数：有补分配格

本章要熟练掌握：

1
2
3
4
5
1. 从哈斯图判断是否为格。
2. 求 meet、join、补元、子格、理想。
3. 用 N5、M3 判断模格和分配格。
4. 证明格同态、格同构、理想格与直积格。
5. 使用布尔代数的德摩根律、补元唯一性和有限表示定理。

判断题不要只看图像“像不像”。核心是检查任意两个元素是否都有唯一的最大下界和最小上界；判断模格、分配格时，再找禁用子格 N5 和 M3。

2、格的定义

偏序集 <L, <= > 是格，当且仅当任意 a,b in L 都存在：

1
2
a /\ b：a 与 b 的最大下界，称为 meet
a \/ b：a 与 b 的最小上界，称为 join

常见例子：

1
2
3
4
1. 正因子格 Sn：x /\ y = gcd(x,y)，x \/ y = lcm(x,y)。
2. 幂集格 P(A)：X /\ Y = X ∩ Y，X \/ Y = X ∪ Y。
3. 子群格 L(G)：H /\ K = H ∩ K，H \/ K = <H ∪ K>。
4. 整数链 <Z, <= >：x /\ y = min(x,y)，x \/ y = max(x,y)。

从偏序角度看：

1
2
3
a <= b
<=> a /\ b = a
<=> a \/ b = b

这组三个等价条件非常常用。证明某个不等式时，可以把 x <= y 改写成 x /\ y = x 或 x \/ y = y。

3、格的代数性质

格中的两个运算满足：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
交换律：
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

反过来，若代数系统 <L, /\ , \/> 的两个二元运算满足交换律、结合律和吸收律，就可以定义偏序：

1
a <= b <=> a \/ b = b

在这个偏序下，/\ 就是最大下界，\/ 就是最小上界，因此它构成格。

4、对偶原理

若命题 P 中只出现：

1
<=, >=, /\, \/, =

把 <= 与 >= 互换，把 /\ 与 \/ 互换，得到的命题称为对偶命题 P*。

例如：

1
2
P : a /\ b = b /\ a
P*: a \/ b = b \/ a

对偶原理：

1
如果 P 对一切格都成立，那么 P* 也对一切格成立。

有界格中做对偶时，还要交换：

1
0 <-> 1

5、格中的常用不等式

保序不等式：

1
2
3
a <= b, c <= d
=> a /\ c <= b /\ d
=> a \/ c <= b \/ d

分配不等式：

1
2
a \/ (b /\ c) <= (a \/ b) /\ (a \/ c)
a /\ (b \/ c) >= (a /\ b) \/ (a /\ c)

模不等式：

1
2
a <= b
=> a \/ (c /\ b) <= (a \/ c) /\ b

这些不等式在任意格中成立；若不等式升级为等式，就对应更强的结构，如模格或分配格。

6、子格、同态、直积与理想

子格

S 是格 L 的非空子集，且对 L 中的两个运算封闭：

1
2
3
任意 x,y in S：
x /\ y in S
x \/ y in S

则 S 是 L 的子格。

子格的 meet 和 join 是在原格 L 中求出来的。不能只在子集内部重新画图后另算一套。

格同态

设 L1, L2 是格，映射 f:L1 -> L2 若满足：

1
2
f(x /\ y) = f(x) /\ f(y)
f(x \/ y) = f(x) \/ f(y)

则 f 是格同态。

格同态保持偏序：

1
x <= y => f(x) <= f(y)

若 f 是双射，并且：

1
x <= y <=> f(x) <= f(y)

则 f 是格同构。

格的直积

格直积按分量定义：

1
2
(a1,b1) /\ (a2,b2) = (a1 /\ a2, b1 /\ b2)
(a1,b1) \/ (a2,b2) = (a1 \/ a2, b1 \/ b2)

多个格的直积同理。

理想

I 是格 L 的非空子集，若满足：

1
2
1. a,b in I => a \/ b in I；
2. a in I, x in L, x <= a => x in I。

则 I 是 L 的理想。

关键关系：

1
2
3
4
理想一定是子格，但子格不一定是理想。
L 的全部理想按包含关系构成理想格 I(L)。
I0(L)=I(L) ∪ {空集} 是完备格。
任意格 L 都可嵌入完备格 I0(L)。

7、特殊的格

模格

格 L 是模格，当且仅当：

1
a <= b => a \/ (c /\ b) = (a \/ c) /\ b

判别：

1
L 是模格 <=> L 不含与五角格 N5 同构的子格。

等价判据：

1
若 a <= b，a \/ c = b \/ c，a /\ c = b /\ c，则 a=b。

分配格

格 L 是分配格，当且仅当满足任意一个分配律：

1
2
a /\ (b \/ c) = (a /\ b) \/ (a /\ c)
a \/ (b /\ c) = (a \/ b) /\ (a \/ c)

在任意格中，这两个分配等式等价。

判别：

1
L 是分配格 <=> L 不含与 N5 或 M3 同构的子格。

若已知 L 是模格，则：

1
L 是分配格 <=> L 不含与钻石格 M3 同构的子格。

常见结论：

1
2
3
4
1. 所有链都是分配格。
2. 4 元以下的格都是分配格。
3. 钻石格 M3 是模格，但不是分配格。
4. 五角格 N5 不是模格，也不是分配格。

有界格与有补格

有界格存在最小元 0 和最大元 1：

1
2
3
4
a /\ 1 = a
a \/ 0 = a
a /\ 0 = 0
a \/ 1 = 1

若：

1
2
a /\ b = 0
a \/ b = 1

则 a 与 b 互为补元。

有补格：

1
每个元素都有补元的有界格。

在有界分配格中，若补元存在，则补元唯一。

8、布尔代数

布尔代数可以从两种角度理解。

格论角度：

1
布尔代数 = 有补分配格。

代数系统角度：

1
<B, /\ , \/, -, 0, 1>

其中 /\、\/ 满足交换律、结合律、分配律，0 和 1 是单位元，-x 是 x 的补元。

常用性质：

1
2
3
4
5
6
7
8
9
10
11
12
13
双重否定律：
(a')' = a

德摩根律：
(a /\ b)' = a' \/ b'
(a \/ b)' = a' /\ b'

偏序等价：
a <= b
<=> a /\ b = a
<=> a \/ b = b
<=> a /\ b' = 0
<=> a' \/ b = 1

有限布尔代数表示定理：

1
2
设 B 是有限布尔代数，A 是 B 的全体原子集合。
则 B 与 P(A) 同构。

因此：

1
2
3
有限布尔代数的元素个数一定是 2^n。
有限布尔代数都同构于 {0,1}^n。
若 |B|=2^n，则 B 恰好有 n 个原子。

9、证明套路

判断是否为格：

1
2
3
找一对元素。
若没有最大下界或没有最小上界，则不是格。
若任意二元组都能找到 meet 和 join，则是格。

判断子格：

1
只查封闭性：x,y in S => x /\ y, x \/ y in S。

判断模格和分配格：

1
2
3
含 N5 => 不是模格，也不是分配格。
含 M3 且不含 N5 => 模格但不分配。
不含 N5 和 M3 => 分配格。

证明布尔代数化简：

1
2
3
4
5
6
优先用：
1. 补元律：a /\ a'=0，a \/ a'=1；
2. 德摩根律；
3. 分配律；
4. 吸收律；
5. a <= b 的等价条件。

10、习题十九答案速查

19.1、判断哈斯图是否为格

答案：

1
2
3
4
(2) 不是格：{a,b} 没有最大下界，也没有最小上界。
(3) 不是格：{a,b} 没有最大下界，也没有最小上界。
(6) 不是格：{a,c} 没有最大下界。
(7) 不是格：{e,f} 没有最大下界。

其余图按答案判为格。

19.2、整除偏序是否为格

答案：

1
2
3
4
(1) {1,2,3,4,6} 不是格，因为 {4,6} 没有最小上界。
(2) {1,2,3,4,6,12} 是格。
(3) {1,2,3,4,6,9,12,18,36} 是格。
(4) {1,5,5^2,5^3,...} 是格。

整除格里：

1
2
x /\ y = gcd(x,y)
x \/ y = lcm(x,y)

但前提是 gcd 和 lcm 仍在给定集合中。

19.3、链上元素的等式

已知 a <= b <= c。

1
2
3
(1) a \/ b = b，b /\ c = b，所以 a \/ b = b /\ c。
(2) (a /\ b) \/ (b /\ c)=a \/ b=b；
    (a \/ b) /\ (a \/ c)=b /\ c=b。

所以两个等式都成立。

19.4、格中的两个不等式

结论：

1
(a /\ b) \/ (c /\ d) <= (a \/ c) /\ (b \/ d)

证明要点：

1
2
3
a /\ b <= a <= a \/ c
c /\ d <= c <= a \/ c
=> (a /\ b) \/ (c /\ d) <= a \/ c

同理它也小于等于 b \/ d，所以小于等于二者的 meet。

第二个结论：

1
2
3
(a /\ b) \/ (b /\ c) \/ (c /\ a)
<=
(a \/ b) /\ (b \/ c) /\ (c \/ a)

证明方法相同：分别证明左侧三个 meet 项都小于右侧每个 join 项。

19.5、meet 等于 join 的充要条件

结论：

1
2
a1 /\ a2 /\ ... /\ an = a1 \/ a2 \/ ... \/ an
<=> a1=a2=...=an

证明：

1
a1 /\ ... /\ an <= ai <= a1 \/ ... \/ an

若两端相等，则每个 ai 都夹在同一个元素之间，所以全部相等。反向显然。

19.6、不可比的判定

结论：

1
2
a /\ b < a 且 a /\ b < b
<=> a 与 b 不可比

若 a <= b，则 a /\ b=a，矛盾；若 b <= a 同理。反过来，若 a /\ b < a 不成立，则 a /\ b=a，推出 a<=b，与不可比矛盾。

19.7、求对偶命题

答案：

1
2
3
4
5
6
7
8
9
(1) a \/ (b /\ c) = (a \/ b) /\ (a \/ c)

(2) (a \/ b) /\ (b \/ c) = (a /\ b) \/ (a /\ c)

(3) (a \/ b) /\ (c \/ d) >= (a /\ c) \/ (b /\ d)

(4) (a \/ b) /\ (b \/ c) /\ (c \/ a)
    >=
    (a /\ b) \/ (b /\ c) \/ (c /\ a)

自对偶命题：

1
(4)

19.8、找子格

答案中的子格如下。

L1：

1
2
3
4
5
6
7
8
三元子格：
{a,b,c}, {a,b,d}, {a,b,e}, {a,c,e}, {a,d,e}, {b,c,e}, {b,d,e}

四元子格：
{a,b,c,e}, {a,b,d,e}, {b,c,d,e}

五元子格：
{a,b,c,d,e}

L2：

1
2
3
4
5
6
7
8
9
10
11
三元子格：
{a,b,e}, {a,b,g}, {a,d,e}, {a,d,f}, {a,d,g},
{a,c,f}, {a,c,g}, {a,e,g}, {a,f,g}, {b,e,g},
{d,e,g}, {c,f,g}, {d,f,g}

四元子格：
{a,b,e,g}, {a,d,e,g}, {a,d,f,g}, {a,c,f,g}, {a,b,d,e},
{a,c,d,f}, {d,e,f,g}, {a,b,f,g}, {a,c,e,g}

五元子格：
{a,b,d,e,g}, {a,c,d,f,g}, {a,d,e,f,g}, {a,b,c,e,g}, {a,b,c,f,g}

19.9、三个区间都是子格

给定 a < b：

1
2
3
L1={x | x<=a}
L2={x | a<=x}
L3={x | a<=x<=b}

证明：

1
2
3
x,y in L1 => x /\ y <= a，x \/ y <= a。
x,y in L2 => a <= x /\ y，a <= x \/ y。
x,y in L3 => a <= x /\ y <= b，a <= x \/ y <= b。

所以三者均对 meet 和 join 封闭，都是子格。

19.10、判断模格和分配格

答案：

1
2
3
4
5
L1：模格，但不是分配格，因为 {d,e,f,g,h} 与钻石格 M3 同构。
L2：不是模格，也不是分配格，因为 {a,b,d,c,g} 与五角格 N5 同构。
L3：不是模格，也不是分配格，因为 {a,b,e,c,h} 与五角格 N5 同构。
L4：不是模格，也不是分配格，因为 {a,b,d,e,f} 与五角格 N5 同构。
L5：不是模格，也不是分配格，因为 {a,b,c,d,f} 与五角格 N5 同构。

19.11、三个 6 元格举例

可取：

1
2
3
1. 6 个元素的链：分配格。
2. 在钻石格下方连接 1 个结点：模格但不是分配格。
3. 在五角格下方连接 1 个结点：不是模格，也不是分配格。

19.12、模格的等价式

要证：

1
2
3
L 是模格
<=> 任意 a,b,c in L，
    a \/ (b /\ (a \/ c)) = (a \/ b) /\ (a \/ c)

必要性：

1
a <= a \/ c

由模律直接得到等式。

充分性：若 a<=b，则 a \/ b=b，于是：

1
2
3
4
(a \/ c) /\ b
= (a \/ c) /\ (a \/ b)
= a \/ (c /\ (a \/ b))
= a \/ (c /\ b)

这正是模律。

19.13、分配格中的区间表达

结论：

1
2
3
a /\ b <= c <= a \/ b
<=>
c = (a /\ c) \/ (b /\ c) \/ (a /\ b)

证明关键等式：

1
2
(a \/ c) /\ (a \/ b) /\ (b \/ c)
= (a /\ c) \/ (b /\ c) \/ (a /\ b)

若 c<=a\/b，左边夹出 c；反向由右边表达式立即得到 a/\b<=c，再由等价式推出 c<=a\/b。

19.14、模格中一个分配式推出另外两个

已知 L 是模格，且：

1
a /\ (b \/ c) = (a /\ b) \/ (a /\ c)

可推出：

1
2
(1) b /\ (a \/ c) = (b /\ a) \/ (b /\ c)
(2) a \/ (b /\ c) = (a \/ b) /\ (a \/ c)

证明思路：

1
2
先在等式两边 join c，用模律转化得到 (1)；
再在 (1) 两边 join a，再用模律得到 (2)。

19.15、有界格中的极端情况

结论：

1
2
(1) a \/ b = 0 => a=b=0。
(2) a /\ b = 1 => a=b=1。

证明：

1
a <= a \/ b = 0 且 0 <= a，所以 a=0。

b=0 同理。第二问对偶。

19.16、有限链不是有补格

结论：

1
2
(1) 若 |L|>=2，则 L 中不存在以自身为补元的元素。
(2) 若 |L|>=3 且 L 是链，则 L 不是有补格。

证明要点：

若 a'=a，则：

1
2
1=a' \/ a=a
0=a' /\ a=a

推出 0=1，与 |L|>=2 矛盾。

若链中存在 0<a<1，任意补元 a' 都与 a 可比，会推出 a=0 或 a=1，矛盾。

19.17、有补元素构成子格

设 L 是有界分配格，L1 是所有有补元元素构成的集合。

证明要点：

1
2
3
4
0 in L1，L1 非空。
若 x,y in L1，则：
(x /\ y)' = x' \/ y'
(x \/ y)' = x' /\ y'

因此 x/\y 与 x\/y 仍有补元，L1 对 meet 和 join 封闭，是 L 的子格。

19.18、所有 5 元格分类

答案：

1
2
3
4
不同构的 5 元格共有 5 个。
其中 L1, L2, L3, L4 是模格；
L1, L2, L3 是分配格；
L4, L5 是有补格。

判断依据：

1
2
3
含 N5 => 非模、非分配。
含 M3 => 模但非分配。
补元存在性决定是否有补。

19.19、链与循环群子群格同构

设 L={0,1,...,t} 是长为 n=t+1 的链，G=<a> 是 p^t 阶循环群。

G 的子群为：

1
2
3
4
H0=<a^(p^t)>=<e>
H1=<a^(p^(t-1))>
...
Ht=<a>

定义：

1
f(i)=Hi

则 f 是双射，且若 i<j：

1
2
f(i /\ j)=f(i)=Hi=Hi ∩ Hj
f(i \/ j)=f(j)=Hj=<Hi ∪ Hj>

所以 L 与 G 的子群格同构。

19.20、两个自同态及其像

设 L 是分配格，固定 a in L：

1
2
f(x)=x \/ a
g(x)=x /\ a

利用分配律可得：

1
2
3
4
f(x \/ y)=f(x) \/ f(y)
f(x /\ y)=f(x) /\ f(y)
g(x \/ y)=g(x) \/ g(y)
g(x /\ y)=g(x) /\ g(y)

所以 f,g 都是自同态。

同态像：

1
2
f(L)={x | a<=x 且 x in L}
g(L)={x | x<=a 且 x in L}

19.21、两个区间之间的格同构

设：

1
2
3
4
X={x | a /\ b <= x <= a}
Y={y | b <= y <= a \/ b}
f(x)=x \/ b
g(y)=y /\ a

结论：

1
2
f:X -> Y，g:Y -> X
f 和 g 是互逆的格同构。

关键计算：

1
2
g(f(x))=(x \/ b) /\ a=(x /\ a) \/ (a /\ b)=x
f(g(y))=(y /\ a) \/ b=(y \/ b) /\ (a \/ b)=y

其中使用 x<=a、a/\b<=x、b<=y、y<=a\/b。

19.22、自同态构成独异点

设 A 是 L 的所有自同态集合。

证明：

1
2
3
若 f,g in A，则 f∘g 仍保持 /\ 和 \/，所以 f∘g in A。
映射合成本身满足结合律。
恒等映射 id_L 是单位元。

因此 <A,∘> 是独异点。

19.23、钻石格的理想

设钻石格：

1
L={0,a,b,c,1}

全部理想：

1
2
3
4
5
{0}
{0,a}
{0,b}
{0,c}
{0,a,b,c,1}

理想格 I(L) 的哈斯图是：底部 {0}，中间三点 {0,a}、{0,b}、{0,c}，顶部为整个 L。

19.24、有限格与理想格同构

结论：

1
对有限格 L，有 I(L) ≅ L。

构造映射：

1
2
f:I(L)->L
f(I)=\/I

有限理想 I 有最大元 \/I，并且：

1
2
f(<I1 ∪ I2>) = f(I1) \/ f(I2)
f(I1 ∩ I2) = f(I1) /\ f(I2)

单射：若 \/I1=\/I2=x，则：

1
I1=I2={z | z<=x}

满射：任意 x in L，取：

1
I={z | z<=x}

则 f(I)=x。

19.25、格直积哈斯图

设：

1
2
L1={0,a,1}
L2={0,1}

则：

1
2
L1 x L2 有 6 个元素，形如 (x,y)。
L1 x L2 x L2 有 12 个元素，形如 (x,y,z)。

偏序逐分量比较：

1
2
(x1,y1) <= (x2,y2)
<=> x1<=x2 且 y1<=y2

哈斯图按分量提升画即可。

19.26、布尔代数吸收型公式

证明：

1
2
(1) a \/ (a' /\ b) = a \/ b
(2) a /\ (a' \/ b) = a /\ b

计算：

1
2
3
4
a \/ (a' /\ b)
=(a \/ a') /\ (a \/ b)
=1 /\ (a \/ b)
=a \/ b

第二式对偶：

1
2
3
4
a /\ (a' \/ b)
=(a /\ a') \/ (a /\ b)
=0 \/ (a /\ b)
=a /\ b

19.27、对称差构成 Abel 群

定义：

1
a (+) b = (a /\ b') \/ (a' /\ b)

即布尔代数中的对称差。

结论：

1
<B,(+)> 构成 Abel 群。

理由：

1
2
3
4
5
封闭性：由布尔运算封闭。
交换律：定义式对 a,b 对称。
结合律：可展开验证，等同于对称差结合律。
单位元：0，因为 a(+)0=a。
逆元：a 自己，因为 a(+)a=0。

19.28、构造布尔环

定义：

1
2
a (+) b = (a /\ b') \/ (a' /\ b)
a (*) b = a /\ b

由 19.27 可知 <B,(+)> 是 Abel 群；(*) 是交换半群；并且 /\ 对对称差满足分配律：

1
a*(b(+)c) = (a*b) (+) (a*c)

又有：

1
a*a = a /\ a = a

因此 <B,(+),(*)> 是布尔环。

19.29、由原子判定零元

设 A={a1,...,an} 是布尔代数 B 的全体原子。

结论：

1
2
x=0
<=> 对每个 i，x /\ ai=0。

证明：

1
x=0 => x /\ ai=0。

反向若 x!=0，则有限布尔代数中存在某个原子 aj<=x，于是：

1
x /\ aj = aj != 0

矛盾。

19.30、广义德摩根律

结论：

1
2
(a1 /\ a2 /\ ... /\ an)' = a1' \/ a2' \/ ... \/ an'
(a1 \/ a2 \/ ... \/ an)' = a1' /\ a2' /\ ... /\ an'

证明用数学归纳法。n=2 是德摩根律；从 n=k 到 n=k+1 时，把前 k 项看成一个整体再应用二元德摩根律。

19.31、化简表达式

答案：

1
(1) (a /\ b) \/ (a /\ b') \/ (a' \/ b) = 1

按答案展开：

1
2
3
4
(a /\ b) \/ (a /\ b') \/ (a' \/ b)
= a /\ (b \/ b') \/ (a' \/ b)
= a \/ (a' \/ b)
= 1

第二题：

1
(2) (a /\ b) \/ (a' /\ b /\ c) \/ c' = b \/ c'

化简：

1
2
3
4
5
6
(a /\ b) \/ (a' /\ b /\ c) \/ c'
= b /\ (a \/ (a' /\ c)) \/ c'
= b /\ (a \/ c) \/ c'
= (a /\ b) \/ (b /\ c) \/ c'
= (a /\ b) \/ (b \/ c')
= b \/ c'

19.32、由 meet 与补保持推出同态

已知：

1
2
phi(a /\ b)=phi(a) /\ phi(b)
phi(a')=phi(a)'

要证 phi 是布尔代数同态，只需再证保持 join：

1
2
3
4
5
6
phi(a \/ b)
= phi((a' /\ b')')
= phi(a' /\ b')'
= (phi(a') /\ phi(b'))'
= (phi(a)' /\ phi(b)')'
= phi(a) \/ phi(b)

19.33、区间布尔代数

设 B 是布尔代数，a<=b，区间：

1
[a,b]={x | a<=x<=b}

结论：

1
[a,b] 也是布尔代数。

其中：

1
2
下界为 a，上界为 b。
x 在 [a,b] 中的补元为 a \/ (x' /\ b)。

但当 a!=0 或 b!=1 时，[a,b] 通常不是 B 的子布尔代数，因为它不保留原布尔代数的 0,1 和原补元。

19.34、同构保持原子

结论：

1
2
(1) 若 a 是 B1 的原子，则 phi(a) 是 B2 的原子。
(2) 2^n 个元素的布尔代数有且仅有 n 个原子。

理由：

同构保持偏序。若存在：

1
0 < y <= phi(a)

由满射取 x 使 phi(x)=y，再由保序反推：

1
0 < x <= a

由于 a 是原子，所以 x=a，从而 y=phi(a)。

第二问由有限布尔代数表示定理：

1
2
B ≅ P(A)
|B|=2^n => |A|=n

19.35、同态核是理想

设：

1
J=phi^{-1}(0)={x | phi(x)=0}

证明：

1
2
3
(1) 0 in J，因为 phi(0)=0。
(2) 若 a in J 且 x<=a，则 phi(x)<=phi(a)=0，所以 phi(x)=0，x in J。
(3) 若 a,b in J，则 phi(a \/ b)=phi(a) \/ phi(b)=0，所以 a \/ b in J。

因此 J 是格意义下的理想。

19.36、4 元布尔代数到 2 元布尔代数的同态

设：

1
2
B1={0,a,b,1}，且 a'=b
B2={0,1}

全部同态：

1
2
phi1(0)=phi1(a)=0，phi1(b)=phi1(1)=1
phi2(0)=phi2(b)=0，phi2(a)=phi2(1)=1

两者同态像均为：

1
{0,1}

对应商布尔代数：

1
2
phi1：B1/~ = {{0,a},{b,1}}
phi2：B1/~ = {{0,b},{a,1}}

运算按等价类代表元诱导：

1
2
3
[x] /\ [y] = [x /\ y]
[x] \/ [y] = [x \/ y]
[x]' = [x']

19.37、幂集分解同构

若 A 与 B 不交，定义：

1
2
f:P(A ∪ B)->P(A) x P(B)
f(X)=<X ∩ A, X ∩ B>

则 f 是同构。

单射：

1
X∩A=Y∩A 且 X∩B=Y∩B => X=Y

满射：

1
2
任意 <C,D>，其中 C subset A, D subset B，
取 X=C∪D，则 f(X)=<C,D>。

保持运算：

1
2
3
f(X∩Y)=f(X) /\ f(Y)
f(X∪Y)=f(X) \/ f(Y)
f((A∪B)-X)=f(X)'

19.38、满同态诱导商同构

设 phi:B1->B2 是满同态，~ 是由 phi 导出的同余关系：

1
x ~ y <=> phi(x)=phi(y)

自然映射：

1
g(x)=[x]

定义：

1
2
f:B1/~ -> B2
f([x])=phi(x)

证明：

1
2
3
4
良定义：若 [x]=[y]，则 phi(x)=phi(y)。
单射：f([x])=f([y]) => phi(x)=phi(y) => [x]=[y]。
满射：phi 满射。
同态：f([x] /\ [y])=phi(x /\ y)=phi(x) /\ phi(y)。

并且：

1
f(g(x))=f([x])=phi(x)

所以：

1
f ∘ g = phi

唯一性来自每个商类都形如 [x]=g(x)。

19.39、8 元布尔代数的所有子代数

设 8 元布尔代数如答案图，元素为：

1
{0,a,b,c,d,e,f,1}

全部子代数：

1
2
3
4
5
{0,1}
{0,c,d,1}
{0,a,f,1}
{0,b,e,1}
{0,a,b,c,d,e,f,1}

理解方法：8 元布尔代数同构于 3 个原子的幂集，子布尔代数对应原子集合的划分，所以共有 Bell(3)=5 个。

19.40、由任一元素生成的子布尔代数

设 B 是有限布尔代数，|B|>2，任取 x in B。

结论：

1
{0,x,x',1}

是 B 的子布尔代数。

验证：

1
2
3
4
5
6
7
1. 非空，且含 0、1。
2. 对补运算封闭：0'=1，1'=0，x'=x'，(x')'=x。
3. 对 /\ 和 \/ 封闭：
   x /\ x'=0
   x \/ x'=1
   x /\ 0=0，x \/ 0=x
   x /\ 1=x，x \/ 1=1

所以它是子布尔代数。若 x=0 或 x=1，集合退化为 {0,1}，仍成立。

11、复盘清单

1
2
3
4
5
6
1. 会从哈斯图找 meet 和 join。
2. 会用 a<=b <=> a/\b=a <=> a\/b=b。
3. 记住模格排除 N5，分配格排除 N5 和 M3。
4. 会判断子格、理想、同态和直积。
5. 会用补元唯一性、德摩根律和吸收律化简布尔表达式。
6. 记住有限布尔代数 B ≅ P(A)，所以 |B|=2^n。