编码 隐匿在计算机软硬件背后的语言

在布尔代数中，符号“×”表示两个集合的交集。两个集合的交集就是指既在第一个集合中又在第二个集合中的所有元素的集合。例如，F×T代表的是所有褐色母猫的集合。像传统代数一样，我们可以将F×T写为 $\pmb { F } \pmb { T } .$ ，或者简写为FT(布尔代数中的首选形式)。可以将两个字母想象成两个形容词串联在一起：褐色的母猫。

为了避免在传统代数与布尔代数间混淆，有时用符号“∪”和“∩”来代替“+”和“×”。布尔对数学方面的革命性影响是让人们熟知的符号更加抽象，因此，我决定坚持他的做法，而不是引入新的符号到他的代数中。

交换律、结合律和分配律都在布尔代数中同样成立。而且在布尔代数中，加法还可以来分配乘法，但在传统的代数中，这是不成立的：

$$
W + ( B \times F ) = ( W + B ) \times ( W + F )
$$

白猫和黑色母猫的并集与如下两个集合的交集是一样的，这两个集合分别是，白猫和黑猫的并集，白猫和母猫的并集。虽然有点难理解，但是，这个结论是成立的。

布尔代数中还有另外两个符号是非常重要的。这两个符号看起来像数字，但是它们并不是真正意义上的数字，相对于数字而言，它们有不同的意义。在布尔代数中，符号1表示“全集”也就是我们所提到的所有事物。在前面的例子中，符号1表示的就是“所有猫的集合”。因此：

$$
M + F = 1
$$

也就是说，公猫与母猫的并集是所有猫。同样的，褐色的猫、黑猫、白猫与其他颜色猫的并集也是所有猫的集合：

$$
\pmb { T } + \pmb { B } + \pmb { W } + \pmb { O } = 1
$$

通过以下方法也可以得到所有猫的集合：

$$
\pmb { N } + \pmb { U } = 1
$$

符号1与减号连用可以表示在全集中排除一些事物，例如，

$$
1 - M
$$

意思就是除去公猫的所有猫的集合。这个集合与母猫的集合是相等的：

编码—隐匿在计算机软硬件背后的语言

94

$$
1 - M = F
$$

另一个要用到的符号就是0，在布尔代数中，符号0表示空集一不包含任何元素的集合。空集往往是两个互斥集合的交集，例如，母猫与公猫的交集：

$$
\pmb { F } \times \pmb { M } = 0
$$

注意，在布尔代数中，1和0有时也同在传统代数中的应用一样。例如，所有猫与母猫的交集是母猫的集合：

$$
1 \times F = F
$$

空集与母猫的交集还是空集：

$$
0 \times { \pmb F } = 0
$$

空集与母猫的并集则是母猫：

$$
0 + F = F
$$

但是有时也会出现与传统代数相悖的结果。例如，所有猫与母猫的并集是所有猫的集合：

$$
1 + F = 1
$$

这个式子在传统代数中就是没有意义的。

由于F是母猫的集合，（1-F）是所有非母猫的猫的集合，因此这两个集合的并集是1:

$$
F + ( 1 { - } F ) = 1
$$

而这两个集合的交集为0：

$$
F \times ( 1 - F ) = 0
$$

在历史上，这个公式代表了逻辑学上的一个重要概念：这一概念被称为矛盾律。矛盾律指出事物不可能既是它本身，同时又是它的对立面。

布尔代数中与传统代数形式上最大区别之处就是这样一个表达式：

10 逻辑与开关

95

$$
F \times F = F
$$

这个表达式很明确地表达了布尔代数的意义；母猫和母猫的交集依然是母猫。但是如果F代表的是数字，这个表达式就不会成立。布尔认为式子：

$$
\scriptstyle x ^ { 2 } = X
$$

就是将其代数同传统代数区别开的一条语句。另一个在传统代数中看起来比较有趣的式子是：

$$
F + F = F
$$

母猫和母猫的并集依然是母猫。

布尔代数提供了一种解决亚里士多德三段论的数学方法。我们再看看最著名的三段论法中的前两句，但是现在不区分性别：

$$
\begin{array} { c } { { \hbar \hbar \uparrow \hbar \uparrow \uparrow \downarrow \downarrow \downarrow \downarrow \downarrow } } \\ { { \nonumber } } \\ { { \nRightarrow \hbar \downarrow \hbar \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow \downarrow } } \\ { { \nmid \hbar \uparrow \downarrow \downarrow \downarrow \downarrow } } \end{array}
$$

我们用P表示所有人的集合，M表示必有一死的事物，S表示苏格拉底的集合。

“所有人都难逃一死”是什么意思？意思就是说所有人的集合与必有一死的事物的交集是所有人：

$$
\pmb { P } \times \pmb { M } = \pmb { P }
$$

命题 $\pmb { P } \times \pmb { M } = \pmb { M }$ 是错误的，因为，在必有一死的事物中，还包含猫、狗和榆树等。

“苏格拉底是人”这句话的意思就是苏格拉底的集合（一个很小的集合）与所有人的集合（一个很大的集合）的交集是苏格拉底：

$$
\pmb { S } \times \pmb { P } = \pmb { S }
$$

根据第一个等式我们可以得到 $\pmb { P } = \pmb { P } \times \pmb { M }$ ，我们将这个等式带入到第二个等式中去：

$$
\pmb { S } \times ( \pmb { P } \times \pmb { M } ) = \pmb { S }
$$

根据结合律，可以写为：

编码—隐匿在计算机软硬件背后的语言

96

$$
( \pmb { S } \times \pmb { P } ) \times \pmb { M } = \pmb { S }
$$

并且我们已知 $\pmb { S } \times \pmb { P } = \pmb { S }$ ，因此上式可以简化为：

$$
\pmb { S } \times \pmb { M } = \pmb { S }
$$

到此，我们得出了结论。这个表达式告诉我们，苏格拉底的集合与必有一死的事物的集合的交集是S，也就是说，苏格拉底必有一死。如果我们让 $\pmb { S } \times \pmb { M } = \pmb { 0 }$ ，会得出苏格拉底不会死。如果 $\pmb { S } \times \pmb { M } = \pmb { M }$ ，结论就会是：只有苏格拉底会死，其他任何事物都是不死的！

应用布尔代数证明这个显而易见的事实（实际上在2400年前苏格拉底自己就证明了他必有一死）似乎有点小题大做，然而布尔代数同样可以用来确定某种事物是否遵循特定的标准。或许某天你走进了一家宠物商店，对店员说：“我想要一只公猫，已绝育的，白色或褐色都可以，或者一只母猫，也要是已绝育的，除了白色任何颜色都可以；或者，只要是黑猫就可以。”店员会对你说：“你想要的猫是在以下这样的集合里：

$$
( \pmb { M } \times \pmb { N } \times ( \pmb { W } + \pmb { T } ) ) + ( \pmb { F } \times \pmb { N } \times ( 1 - \pmb { W } ) ) + \pmb { B }
$$

对么？”你会说：“是的！正是！”

为了确定店员是正确的，你大概会去抛弃并集和交集的概念，并用OR和AND取而代之。这里将字母大写是因为，它们表示的不仅是字面意义，而表示布尔代数中的运算。做并集的时候，可以看做：第一个集合OR第二个集合。做交集的时候，可以看做：第一个集合AND第二个集合。除此之外，NOT可以看做在1后面加一个减号。总的来说：

符号“+”（之前作为并集的符号）现在可以用OR来表示。

符号“×”（之前作为交集的符号）现在可以用AND来表示。

符号“1-”（之前意思是从全集中去掉某些元素）现在用NOT来表示。

因此，原表达式可以写为：

$$
( M \operatorname { A N D } N \operatorname { A N D } \left( W \operatorname { O R } T \right) ) \operatorname { O R } \left( F \operatorname { A N D } N \operatorname { A N D } \left( \operatorname { N O T } W \right) \right) \operatorname { O R } B
$$

这样就非常接近你所说的话了。注意，这里是如何用括号表述清楚你的意图的。你想要的猫来自以下三个集合中的一个：

10 逻辑与开关

97

$$
\begin{array} { r l } & { ( M \operatorname { A N D } N \operatorname { A N D } \left( W \operatorname { O R } T \right) ) } \\ & { \qquad \operatorname { O R } } \\ & { ( F \operatorname { A N D } N \operatorname { A N D } \left( \operatorname { N O T } W \right) ) } \\ & { \qquad \operatorname { O R } } \\ & { \qquad \quad \quad \quad \quad \quad \quad \quad \quad \quad } \\ & { \qquad \quad \quad \quad \quad \quad \quad \quad \quad \quad B } \end{array}
$$

有了这个公式，店员就可以做一个布尔测试了。为了避免麻烦，我采用了一种略微有点不同的布尔代数形式—一字母不仅仅代表集合。这里，字母可以用数字来赋值。我们只用数字0和1。数字1代表YES，True，即这只猫是符合这样的标准的。数字0表示NO，False，即这只猫不符合这种特定标准。

首先，店员拿出了一只未绝育的褐色公猫。以下是我期望得到的猫的表达式：

$$
( M \times N \times ( W + T ) ) + ( F \times N \times ( 1 - W ) ) + B
$$

以下是用0和1替换之后的式子：

$$
( 1 \times 0 \times ( 0 + 1 ) ) + ( 0 \times 0 { \times } ( 1 - 0 ) ) + 0
$$

注意，只有M和T的值为1，因为这只猫是褐色的公猫。

现在我们要做的就是化简这个表达式。如果简化结果为1，则这只猫就符合你的标准；如果简化结果为0，那么这只猫就不符合。在化简的时候要切记，我们并不是真的在进行加和乘的运算，尽管通常我们可以当做是。符号“+”代表OR，符号“×”代表AND，在大多同类的规则中适用（有时在现代课本中也使用符号“∧”和“√”来表示AND和OR，而非用符号“×”和“+”。但是在这里符号“+”和“×”是具有特殊意义的）。

当符号“×”代表AND时，有以下几种可能的结果：

$$
\begin{array} { l } { 0 \times 0 = 0 } \\ { 0 \times 1 = 0 } \\ { 1 \times 0 = 0 } \\ { 1 \times 1 = 1 } \end{array}
$$

也就是说，只有当运算符AND左右两端都为1的时候，结果才为1。这个运算与常规的乘法是完全相同的，该规则可以总结为如下这样一个表格，这与第8章中加法和乘

编码隐匿在计算机软硬件背后的语言

98

法表的形式类似。

当符号“+”表示OR的时候，有以下几种可能的结果：

$$
\begin{array} { l } { 0 + 0 = 0 } \\ { \qquad 0 + 1 = 1 } \\ { \qquad 1 + 0 = 0 } \\ { \qquad 1 + 1 = 1 } \end{array}
$$

如果运算符OR左右两端有一个操作数为1，则其运算结果就为1。这个运算与常规的加法类似，但是在1+1=1这里例外。运算符OR可以概括为如下这样一个表格。

我们应用这两个表格来计算一下原表达式的结果：

$$
( 1 \times 0 \times 1 ) + ( 0 \times 0 \times 1 ) + 0 = 0 + 0 + 0 = 0
$$

结果为0，意味着NO，False，这只小猫不符合标准。

接着，店员拿出了一只已绝育的白色母猫。原始表达式是：

$$
( M \times N \times ( W + T ) ) + ( F \times N \times ( 1 - W ) ) + B
$$

将0和1带入得：

$$
( 0 \times 1 \times ( 1 + 0 ) ) + ( 1 \times 1 \times ( 1 - 1 ) ) + 0
$$

化简得：

$$
( 0 \times 1 \times 1 ) + ( 1 \times 1 \times 0 ) + 0 = 0 + 0 + 0 = 0
$$

因此，第二只小猫也不符合标准。

然后，店员拿出了一只已绝育的灰色母猫(灰色属于其他颜色——非白色、黑色或褐

10 逻辑与开关

99

色）。表达式如下：

$$
( 0 \times 1 \times ( 0 + 0 ) ) + ( 1 \times 1 { \times } ( 1 - 0 ) ) + 0
$$

化简结果为：

$$
( 0 \times 1 \times 0 ) + ( 1 \times 1 \times 1 ) + 0 = 0 + 1 + 0 = 1
$$

最后结果为1，意味着Yes，True，这个只小猫可以带回家（而且还是只漂亮的小猫！)。

当晚，在小猫蜷缩在你的腿上睡觉的时候，你突发奇想是否可以通过连通开关和灯泡的方法来确定某类猫咪是否符合你的标准（是的，你就是个奇怪的孩子）。你根本没发现，你将做出一个重要的概念上的突破。你要做的这些实验将布尔代数与电路相融合，并且可以设计和制造利用二进制进行计算的计算机。但是，不要让这些吓倒你。

在实验的开始，将灯泡和电池正常连接起来，但是，你用了两个开关，而不是一个，如下图所示。

像这样一个接着一个首尾相连的接线方式称做串联(series)。如果你闭合左端的开关，什么都不会发生。

编码隐匿在计算机软硬件背后的语言

100

如果让左边的开关保持断开，而闭合右边的开关，同样什么都不会发生。只有当左右两个开关都闭合时灯泡才会亮，如下图所示。

这个电路是一个简单的逻辑演示。实际上，灯泡是在回答“两个开关是否都闭合？”这样一个问题。这个电路的运转情况，我们可以总结为如下表格。

在之前的章节中，我们已经知道二进制数是如何表示信息的一而信息是无所不包的，无论是简单的数字还是罗杰·艾伯特²拇指的方向都是信息。我们可以说二进制0代表“艾伯特的拇指向下”，二进制1代表“艾伯特的拇指向上。”一个开关有两个状态，因此可以代表二进制数。我们可以说0代表“开关断开”，1代表“开关闭合”。一个灯泡有两种状态，因此，它也可以用二进制数来表示。我们可以说0代表“灯泡不亮”，1代表“灯泡亮”。根据以上表述，我们可以将表格简化为如下形式。

10 逻辑与开关

2 美国影评家一译者注

101

注意，如果将左边的开关和右边的开关调换位置，结果是一样的。我们不用分辨开关哪个是哪个。所以，上面的表也可以写为和AND表或OR表类似的形式。

的确，这与AND表是一样的。

这个简单的电路演示了布尔代数中的AND运算。

接下来，稍微改变一下开关连接方式，如下图所示。

这种连接方式叫做并联（parallel)。这种连接与上一种连接的不同之处就在于，闭合上面的开关，灯泡就会亮。

编码隐匿在计算机软硬件背后的语言

102

或者闭合下面的开关，灯泡也会亮。

或者闭合所有的开关，灯泡还是会亮。

10 逻辑与开关

103