布尔代数与布尔环

逻辑合取、集合并与幂等元素的乘法遵循相关的代数规律。布尔代数使这种关系精确化。它不同于普通实数算术：重复一个逻辑命题不会增加第二份，而布尔环的加法表示异或，不是包含性或。

1 格运算与补元

布尔代数是带有交运算 $a\wedge b$、并运算 $a\vee b$、补元 $\neg a$ 和元素 0、1 的集合 $B$，满足交换律、结合律、吸收律、各运算对另一运算的分配律、单位律 $a\vee0=a$、$a\wedge1=a$，以及补元律

$$a\vee\neg a=1,\qquad a\wedge\neg a=0.$$

吸收律为 $a\wedge(a\vee b)=a$ 和 $a\vee(a\wedge b)=a$。当 $a\wedge b=a$ 时定义 $a\le b$。这些规律使它成为偏序，且并和交分别是最小上界和最大下界。

对任意集合 $X$，幂集 $\mathcal P(X)$ 在交、并和相对于 $X$ 的补运算下是布尔代数，0 为空集，1 为 $X$。按逻辑等价取类的命题在与、或、非运算下给出另一个例子。二元素代数 $\{0,1\}$ 是真值模型。

补元唯一。若 $b,c$ 都是 $a$ 的补元，则

$$b=b\wedge1=b\wedge(a\vee c)=(b\wedge a)\vee(b\wedge c)=b\wedge c,$$

同理 $c=b\wedge c$，故 $b=c$。

De Morgan 律。 $\neg(a\vee b)=(\neg a)\wedge(\neg b)$，且 $\neg(a\wedge b)=(\neg a)\vee(\neg b)$。

证明。 分配律与补元律表明 $(\neg a)\wedge(\neg b)$ 与 $a\vee b$ 的交为 0、并为 1。例如交展开为含有 $a\wedge\neg a$ 或 $b\wedge\neg b$ 的各项，而并等于 $[(a\vee b)\vee\neg a]\wedge[(a\vee b)\vee\neg b]=1$。补元唯一性证明第一个等式；交换交和并即可得到第二个。$\square$

2 布尔环使用不同的加法

这里的布尔环指每个元素都幂等（$a^2=a$）的含单位元交换环。它满足 $2\cdot1=0$：由 $(1+1)^2=1+1$ 得 $4=2$，故 $2=0$。因此非零布尔环的特征为 2；即使允许零环，每个 $a$ 也满足 $a+a=0$。

由这样的环定义

$$a\wedge b=ab,\qquad a\vee b=a+b+ab,\qquad\neg a=1+a.$$

这些运算给出布尔代数。补元等式立即成立：$a(1+a)=a+a^2=0$，$a+(1+a)+a(1+a)=1$。吸收律来自 $a(a+b+ab)=a+ab+ab=a$。展开两边并使用 $a^2=a$ 可得交对并的分配律；并的结合律两种分组都展开为

$$a+b+c+ab+ac+bc+abc.$$

其他格规律可用同样的环展开或补元得到。因此这个构造不只是表面类比，而是确实满足公理。

对集合，布尔环的乘法是交，加法是对称差

$$A\triangle B=(A\setminus B)\cup(B\setminus A).$$

每个点的成员关系将这些运算对应到模 2 的乘法和加法，逐点证明环规律。包含性并则是 $A\triangle B\triangle(A\cap B)$。

3 有限布尔代数中的原子

原子是在 $\le$ 下极小的非零元素。在有限布尔代数中，每个非零元素下方都有原子：从它的非零下界组成的有限非空集合取一个极小元素即可。不同原子的交为零；否则非零交会因极小性迫使它们相等。

每个元素 $a$ 都是它下方原子的并。设这些原子的并为 $s\le a$。若 $s\ne a$，则 $a\wedge\neg s\ne0$；否则 $a=a\wedge(s\vee\neg s)=a\wedge s\le s$。$a\wedge\neg s$ 下方的原子将是 $a$ 下方却被 $s$ 遗漏的原子，矛盾。因此将 $a$ 映到其下方原子的集合，就把有限布尔代数识别为其原子集合的幂集。特别地，其元素个数对某个 $k$ 为 $2^k$，不是任意有限数。

偏序、两个方向的环构造与有限表示

偏序结论可从已列公理推导。吸收律给出 $a\wedge a=a$、$a\vee a=a$，从而关系 $\le$ 自反；交换律给出反对称性。若 $a\wedge b=a$、$b\wedge c=b$，则 $a\wedge c=(a\wedge b)\wedge c=a\wedge(b\wedge c)=a$，故关系传递。元素 $a\wedge b$ 在两个因子下方；任意公共下界 $u$ 满足 $u\wedge(a\wedge b)=u$，所以它是最大下界。吸收律说明 $a\vee b$ 为上界；若 $a,b\le c$，分配律给出 $(a\vee b)\wedge c=(a\wedge c)\vee(b\wedge c)=a\vee b$，证明它是最小上界。

在由布尔环构造代数的方向，另一条分配律与吸收律可明确写成

$$(a\vee b)\wedge(a\vee c)=a+bc+abc=a\vee(b\wedge c), \qquad a\vee(a\wedge b)=a+ab+a^2b=a.$$

交的结合律、交换律和单位元 1 来自环乘法；并满足交换律、单位元为 0，结合律由前述展开式给出。此外 $a\vee a=a$、$a\wedge a=a$。连同两条补元等式和前面已证的另一条分配律，这就核对了列出的全部布尔代数公理。

反过来，在任意布尔代数中定义

$$a\oplus b=(a\wedge\neg b)\vee(\neg a\wedge b),\qquad a\cdot b=a\wedge b.$$

第一种运算满足交换律、单位元为 0，且 $a\oplus a=0$。为证明而非假设结合律，用 De Morgan 律展开 $(a\oplus b)\oplus c$ 或 $a\oplus(b\oplus c)$，两者均为下列四个互不相交项的并：

$$(a\wedge\neg b\wedge\neg c)\vee (\neg a\wedge b\wedge\neg c)\vee (\neg a\wedge\neg b\wedge c)\vee (a\wedge b\wedge c).$$

分别从 $a,\neg a$、$b,\neg b$、$c,\neg c$ 各选一个得到的八项两两相交为零，且并为 1；这由展开 $(a\vee\neg a)\wedge(b\vee\neg b)\wedge(c\vee\neg c)$ 得到。因此上述展开无须预先假设集合表示。展开 $a\wedge(b\oplus c)$ 得 $(a\wedge b\wedge\neg c)\vee(a\wedge\neg b\wedge c)$；展开 $(a\wedge b)\oplus(a\wedge c)$ 也得同式，所以乘法对 $\oplus$ 分配。交提供满足结合律、交换律、含单位元 1 且幂等的乘法。至此所有环公理均已证明。公式 $a\oplus b\oplus(a\wedge b)=a\vee b$ 与 $1\oplus a=\neg a$ 恢复原运算。

最后，有限原子映射确实是同构，而不只是计数。对原子 $t$，每个 $t\wedge a$ 只能为 $0$ 或 $t$。因此 $t\le a\vee b$ 当且仅当 $t\le a$ 或 $t\le b$；$t\le\neg a$ 当且仅当 $t\not\le a$。这证明了并与补元被保持；交的保持是直接的。每个元素都是其原子的并，故映射单射。对有限原子集的任意子集，取其中全部原子的并；互不相交性说明所得元素下方的原子恰为所选子集，从而满射。若允许退化代数 $0=1$，它没有原子，所得为无原子集合（空集）的一元素幂集。这里没有声称每个无限布尔代数都是完整幂集。

4 分级练习

E1 基础。 设 $X=\{1,2,3\}$、$A=\{1,2\}$、$B=\{2,3\}$，计算交、并、布尔环和以及 $A$ 的补集。

E2 代数。 用布尔环公式验证 $a\vee a=a$，并与 $a+a$ 比较。

E3 有限结构。 布尔代数能恰有六个元素吗？16 元布尔代数有多少原子？

E4 逻辑。 化简 $(p\wedge q)\vee(p\wedge\neg q)$，并解释为什么不涉及概率假设。

5 完整解答

S1. 交为 $\{2\}$，并为 $X$，环和为 $\{1,3\}$，且 $\neg A=\{3\}$。环和不含共有元素 2，而并包含它。

S2. $a\vee a=a+a+a^2=0+a=a$。相反，环加法给出 $a+a=0$。因此不说明约定而用同一加号表示并和环加法会产生歧义。

S3. 不能：有限布尔代数的大小是 2 的幂。由于 $16=2^4$，它有四个原子。

S4. 由分配律得 $p\wedge(q\vee\neg q)=p\wedge1=p$。这是对所有真值赋值都成立的逻辑恒等式，不是独立性陈述或概率计算。

总结

布尔代数抽象集合与逻辑运算。布尔环以幂等乘法和特征为二的加法编码同样的模式。包含性或与异或是不同运算。有限布尔代数由其原子决定，因此大小是 2 的幂。