2.1.6 布尔代数简介

二进制值是计算机编码、存储和操作信息的核心，所以围绕数值 0 和 1 的研究已经演化出了丰富的数学知识体系。这起源于 1850 年前后乔治·布尔（George Boole, 1815-1864）的工作，因此也称为布尔代数（Boolean algebra）。布尔注意到通过将逻辑值 TRUE（真）和 FALSE（假）编码为二进制值 1 和 0，能够设计出一种代数，以研究逻辑推理的基本原则。

最简单的布尔代数是在二元集合 {0, 1} 基础上的定义。图 2-7 定义了这种布尔代数中的几种运算。我们用来表示这些运算的符号与 C 语言位级运算使用的符号是相匹配的，这些将在后面讨论到。

图 2-7 布尔代数的运算

布尔运算 ~ 对应于逻辑运算 NOT，在命题逻辑中用符号 ¬ 表示。也就是说，当 P 不是真的时候，我们就说 ¬P 是真的，反之亦然。相应地，当 P 等于 0 时，~P 等于 1，反之亦然。

布尔运算 & 对应于逻辑运算 AND，在命题逻辑中用符号 ∧ 表示。当 P 和 Q 都为真时，我们说 P ∧ Q 为真。相应地，只有当 p = 1 且 q = 1 时，p & q 才等于 1。

布尔运算 | 对应于逻辑运算 OR，在命题逻辑中用符号 ∨ 表示。当 P 或者 Q 为真时，我们说 P ∨ Q 成立。相应地，当 p = 1 或者 q = 1 时，p | q 等于 1。

布尔运算 ^ 对应于逻辑运算异或，在命题逻辑中用符号 ⊕ 表示。当 P 或者 Q 为真但不同时为真时，我们说 P ⊕ Q 成立。相应地，当 p = 1 且 q = 0，或者 p = 0 且 q = 1 时，p ^ q 等于 1。

后来创立信息论领域的 Claude Shannon（1916-2001）首先建立了布尔代数和数字逻辑之间的联系。他在 1937 年的硕士论文中表明了布尔代数可以用来设计和分析机电继电器网络。尽管那时计算机技术已经取得了相当的发展，但是布尔代数仍然在数字系统的设计和分析中扮演着重要的角色。

我们可以将上述 4 个布尔运算扩展到位向量的运算，位向量就是固定长度为 w、由 0 和 1 组成的串。位向量的运算可以定义成参数的每个对应元素之间的运算。假设 a 和 b 分别表示位向量 [a_w-1, a_w-2, ..., a₀] 和 [b_w-1, b_w-2, ..., b₀]。我们将 a & b 也定义为一个长度为 w 的位向量，其中第 i 个元素等于 aᵢ & bᵢ，0 ≤ i < w。可以用类似的方式将运算 |、^ 和 ~ 扩展到位向量上。

举个例子，假设 w = 4，参数 a = [0110]，b = [1100]。那么 4 种运算 a & b、a | b、a ^ b 和 ~b 分别得到以下结果：

运算	结果
`0110 & 1100`	`0100`
`0110 \\| 1100`	`1110`
`0110 ^ 1100`	`1010`
`~1100`	`0011`

练习题 2.8 填写下表，给出位向量的布尔运算的求值结果。

运算	结果
`a`	`[01101001]`
`b`	`[01010101]`
`~a`
`~b`
`a & b`
`a \\| b`
`a ^ b`

网络旁注 DATA:BOOL：关于布尔代数和布尔环的更多内容

对于任意整数 w > 0，长度为 w 的位向量上的布尔运算 |、& 和 ~ 形成了一个布尔代数。最简单的情况是 w = 1 时，只有 2 个元素；但是对于更普遍的情况，有 2^w 个长度为 w 的位向量。布尔代数和整数算术运算有很多相似之处。例如，乘法对加法的分配律，写为 a · (b + c) = (a · b) + (a · c)，而布尔运算 & 对 | 的分配律，写为 a & (b | c) = (a & b) | (a & c)。此外，布尔运算 | 对 & 也有分配律，写为 a | (b & c) = (a | b) & (a | c)，但是对于整数我们不能说 a + (b · c) = (a + b) · (a + c)。

当考虑长度为 w 的位向量上的 ^、& 和 ~ 运算时，会得到一种不同的数学形式，我们称为布尔环（Boolean ring）。布尔环与整数运算有很多相同的属性。例如，整数运算的一个属性是每个值 x 都有一个加法逆元（additive inverse）-x，使得 x + (-x) = 0。布尔环也有类似的属性，这里的“加法”运算是 ^，不过这时每个元素的加法逆元是它自己本身。也就是说，对于任何值 a 来说，a ^ a = 0，这里我们用 0 来表示全 0 的位向量。可以看到对单个位来说这是成立的，即 0 ^ 0 = 1 ^ 1 = 0，将这个扩展到位向量也是成立的。当我们重新排列组合顺序，这个属性也仍然成立，因此有 (a ^ b) ^ a = b。这个属性会引起一些很有趣的结果和聪明的技巧，在练习题 2.10 中我们会有所探讨。

位向量一个很有用的应用就是表示有限集合。我们可以用位向量 [a_w-1, ..., a₁, a₀] 编码任何子集 A ⊆ {0, 1, ..., w - 1}，其中 aᵢ = 1 当且仅当 i ∈ A。例如（记住我们是把 a_w-1 写在左边，而将 a₀ 写在右边），位向量 a = [01101001] 表示集合 A = {0, 3, 5, 6}，而 b = [01010101] 表示集合 B = {0, 2, 4, 6}。使用这种编码集合的方法，布尔运算 | 和 & 分别对应于集合的并和交，而 ~ 对应于集合的补。还是用前面那个例子，运算 a & b 得到位向量 [01000001]，而 A ∩ B = {0, 6}。

在大量实际应用中，我们都能看到用位向量来对集合编码。例如，在第 8 章，我们会看到有很多不同的信号会中断程序执行。我们能够通过指定一个位向量掩码，有选择地使能或是屏蔽一些信号，其中某一位位置上为 1 时，表明信号 i 是有效的（使能），而 0 表明该信号是被屏蔽的。因而，这个掩码表示的就是设置为有效信号的集合。

练习题 2.9 通过混合三种不同颜色的光（红色、绿色和蓝色），计算机可以在视频屏幕或者液晶显示器上产生彩色的画面。设想一种简单的方法，使用三种不同颜色的光，每种光都能打开或关闭，投射到玻璃屏幕上，如图所示：

练习题 2.9 光源示意

那么基于光源 R（红）、G（绿）、B（蓝）的关闭（0）或打开（1），我们就能够创建 8 种不同的颜色：

G	B	颜色	R	G	B	颜色
0	0	黑色	1	0	0	红色
0	1	蓝色	1	0	1	红紫色
1	0	绿色	1	1	0	黄色
1	1	蓝绿色	1	1	1	白色

这些颜色中的每一种都能用一个长度为 3 的位向量来表示，我们可以对它们进行布尔运算。

A. 一种颜色的补是通过关掉打开的光源，且打开关闭的光源而形成的。那么上面列出的 8 种颜色每一种的补是什么？

B. 描述下列颜色应用布尔运算的结果：

蓝色 | 绿色 =
黄色 & 蓝绿色 =
红色 ^ 红紫色 =