布尔代数简介
二进制值是计算机编码、存储和操作信息的核心，所以围绕数值 0 和 1 的研究已经演化出了丰富的数学知识体系。这起源于 1850 年前后乔治·布尔 (George Boole，1815-1864)的工作，因此也称为布尔代数 (Boolean algebra) 。布尔注意到通过将逻辑值 TRUE( 真）和 FALSE( 假）编码为二进制值 0 和 1，能够设计出一种代数，以研究逻辑推理的基本原则。
最简单的布尔代数是在二元集合{0, 1}基础上的定义。如下图所示，定义了这种布尔代数的几种运算。我们用来表示这些运算的符号与 C 语言位集运算使用的符号是相匹配的，这些将在后面讨论到。布尔运算 对应于逻辑运算 NOT，在命题逻辑中用符号
表示。也就是说，当 P 不是真的时候我们就说
是真的，反之亦然。相应地，当 P 等于 0 时，
等于 1，反之亦然。布尔运算 & 对应于逻辑运算 AND，在命题逻辑中用符号
表示。当 P 和 Q 都为真时，我们说
为真。相应地，只有当 p=1 且 q=1 时，p&q 才等于 1。布尔运算 | 对应于逻辑运算 OR，在命题逻辑中用符号
表示。当 P 或者 Q 为真时，我们说 P
Q 成立。相应地，当 p=1 或者 q=1 时， p|q 等于 1。布尔运算＾对应于逻辑运算异或，在命题逻辑中用符号
表示。当 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&b 也定义为一个长度为 w 的位向量，其中第 i 个元素等于
，0 ≤ i ≤ w。可以用类似的方式将运算 |、^ 和 ~ 扩展到位向量上。
举个例子，假设 w = 4，参数 a = [0110]，b = [1100]。那么 4 种运算 a&b 、a|b、a^b 和 ~b 分别得到以下结果：
| a | 0110 | 0110 | 0110 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 操作（b） | & | 1100 | 1100 | ^ | 1100 | ~ | 1100 | |||||
| 结果 | 0100 | 1110 | 1010 | 0011 |
位向量一个很有用的应用就是表示有限集合。我们可以用位向量 [] 编码任何子集
，其中
当且仅当
。例如（记住我们是把
写在左边，而将
写在右边），位向 a = [0110 1001] 表示集合 A={O, 3, 5, 6}，而 b=[0101 0101] 表示集合 B={O, 2, 4, 6} 。使用这种编码集合的方法，布尔运算 | 和＆分别对应千集合的并和交，而～对应于集合的补。还是用前面那个例子，运算 a&b 得到位向量 [0100 0001]，而
在大量实际应用中，我们都能看到用位向量来对集合编码。例如，在第 8 章，我们会看到有很多不同的信号会中断程序执行。我们能够通过指定一个位向量掩码，有选择地使能或是屏蔽一些信号，其中某一位位置上为 1 时，表明信号 i 是有效的（使能），而 0 表明该信号是被屏蔽的。因而，这个掩码表示的就是设置为有效信号的集合。
