布尔代数与逻辑函数代数

代数运算不一定是数的加法和乘法。逻辑与、或、非构成布尔代数。另一种表示使用模 2 运算，其中加法成为异或。研究逻辑函数可具体区分这些运算，并给出一个具有原子和商的完整有限模型。

1 布尔运算与序

布尔代数具有交 $a\wedge b$、并 $a\vee b$、补 $\neg a$，以及特殊元素 0 和 1。交与并满足结合律、交换律、吸收律及相互分配律；0 和 1 满足 $a\vee0=a$、$a\wedge1=a$；补满足 $a\wedge\neg a=0$、$a\vee\neg a=1$。

序关系 $a\le b$ 的意思是 $a\wedge b=a$。由于公理蕴含幂等性，它具有自反性。例如，结合 $a\vee0=a$ 与吸收律得到 $a\wedge a=a$。反对称性来自交换律；传递性来自结合律：若 $a\wedge b=a$ 且 $b\wedge c=b$，则 $a\wedge c=(a\wedge b)\wedge c=a\wedge(b\wedge c)=a$。

补是唯一的。若 $b,c$ 均为 $a$ 的补，分配律给出 $b=b\wedge(a\vee c)=b\wedge c$ 及 $c=c\wedge(a\vee b)=b\wedge c$。故 $b=c$。验证 $\neg a\wedge\neg b$ 是 $a\vee b$ 的补并利用唯一性，可得德摩根律；对偶论证给出另一条。

对集合而言，交是集合交、并是集合并、补是相对于全集的补，0 是空集，1 是全集。对按逻辑等价分类的命题而言，它们分别是合取、析取、否定、假与真。逻辑蕴含对应此序，而不是任意表达式之间普通的数值不等式。

2 有限赋值集上的所有逻辑函数

令 $X=\{0,1\}^n$ 为 $n$ 个变量所有真值赋值的集合，共有 $2^n$ 个赋值。逻辑函数是任意映射 $f:X\to\{0,1\}$，运算逐点进行。选出取值为 1 的赋值，就将函数与 $X$ 的子集对应起来，因此这些函数构成有 $2^{2^n}$ 个元素的布尔代数。

原子是极小的非零元素。这里原子是恰好一个赋值的指示函数。对变量 $p,q$，四个原子为

$$p\wedge q,\quad p\wedge\neg q,\quad\neg p\wedge q,\quad\neg p\wedge\neg q.$$

每个逻辑函数都是使其为真的赋值原子的并。这就是析取范式。作为选定的原子子集，它是唯一的，尽管写出的表达式可以有许多代数等价形式。

例。 异或恰在赋值 $(p,q)=(1,0),(0,1)$ 为真，因此

$$p\mathbin{\mathrm{XOR}}q=(p\wedge\neg q)\vee(\neg p\wedge q).$$

包含性或还包括原子 $p\wedge q$，故是不同函数。吸收律将 $p\vee(p\wedge q)$ 化简为 $p$，但对任意实数输入，相应的实数恒等式 $p+(pq)=p$ 并不成立。

3 布尔环运算

在同一函数集上，按 $\mathbb F_2$ 逐点定义加法和乘法。乘法是交，加法是异或。由于每个值是 0 或 1，每个函数都满足 $f^2=f$。这样的含单位交换环称为布尔环。

在任意布尔环中，$2\cdot1=0$，因为 $(1+1)^2=1+1$ 给出 $4\cdot1=2\cdot1$。因此 $a+a=0$。非零布尔环的特征为 2；如果允许零环，它是惯例上的例外。并与补可恢复为

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

对于逻辑函数，可代入四种真值对验证并的公式。在抽象布尔环中，利用 $a^2=a$ 和 $a+a=0$ 展开，可验证同样的格律。例如 $a(a+b+ab)=a+ab+ab=a$，证明吸收律；而 $(a+b+ab)+c+(a+b+ab)c$ 关于三个元素对称，证明并的结合律。

若布尔环是整环，则仅含 0 和 1：$a(a-1)=0$ 迫使 $a=0$ 或 $a=1$。因此唯一的非零布尔域是 $\mathbb F_2$。四元素域不是布尔域，尽管其特征也是 2。特征为 2 本身并不蕴含每个元素幂等。

4 有限原子与商的例子

在任意有限布尔代数中，每个非零元素之下都有原子：取极小的非零下界即可。不同原子的交为零。每个元素等于其下所有原子的并：若它们的并 $s$ 严格小于 $a$，则 $a\wedge\neg s$ 非零，并包含另一个原子，与 $s$ 的定义矛盾。因此每个有限布尔代数都是其原子的幂集代数；若有 $k$ 个原子，便有 $2^k$ 个元素。

作为具体环商，取逐坐标运算的 $R=\mathbb F_2^3$ 与理想 $I=\{(a,0,0):a\in\mathbb F_2\}$。投影 $(a,b,c)\mapsto(b,c)$ 是核为 $I$ 的满环同态，给出 $R/I\cong\mathbb F_2^2$。忘掉一个坐标移除一个原子，使布尔代数从八个元素减至四个。商乘法有效是因为 $I$ 是理想，而不只是因为底层集合有限。

在完整构造前，先用本章符号证明两条补元等式及第一条分配律。由 $a^2=a$ 和 $a+a=0$，有 $a(1+a)=a+a^2=0$，且 $a+(1+a)+a(1+a)=1$。又有 $a(b\vee c)=ab+ac+abc=(ab)\vee(ac)$，最后一步使用 $a^2=a$。因此这些规律已在此处证明，无须借用其他章节。

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

偏序结论可从已列公理推导。吸收律给出 $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$，它没有原子，所得为无原子集合（空集）的一元素幂集。这里没有声称每个无限布尔代数都是完整幂集。

5 分级练习

E1 基础。 三个变量有多少个赋值、原子和逻辑函数？

E2 化简。 化简 $(p\wedge q)\vee(p\wedge\neg q)$。用布尔环记号写出异或，并与并比较。

E3 结构。 有限布尔代数能有 12 个元素吗？若有 32 个元素，它有多少原子？

E4 环。 证明 $\mathbb Z/4\mathbb Z$ 不是布尔环，并解释四元素域也不是布尔环。

E5 商。 在 $\mathbb F_2^4$ 中投影到第 1 和第 4 坐标。求核、商的大小以及商布尔代数的原子个数。

6 详解

S1. 有 $2^3=8$ 个赋值及八个赋值原子。逻辑函数在每个赋值处独立选择 0 或 1，因此有 $2^8=256$ 个函数。混淆变量与赋值会错误地只得到八个函数。

S2. 分配律给出 $p\wedge(q\vee\neg q)=p$。在布尔环中异或为 $p+q$，而并为 $p+q+pq$。当两个输入均为 1，异或为 0、并为 1，故不能混淆两种运算。

S3. 不能，因为 12 不是 2 的幂。32 元素布尔代数有五个原子，其元素是这五个原子的所有子集。

S4. 模 4 有 $[2]^2=[0]\ne[2]$，违反幂等性。布尔整环至多有 0 和 1 两个元素，因此四元素域不能是布尔环。等价地，其满足 $\alpha^2=\alpha+1$ 的元素 $\alpha$ 不幂等。

S5. 核为 $\{(0,a,b,0):a,b\in\mathbb F_2\}$。像为 $\mathbb F_2^2$，故商有四个元素和两个原子。第一同构定理给出商的对应。

小结

布尔代数组织逻辑与集合运算，其有限结构由原子控制。逻辑函数提供完整的具体模型。布尔环加法是异或而不是包含性或，仅有特征为 2 并不足够。理想与商映射将逻辑代数直接联系到环结构。