Hello World！我是老乔，欢迎来到超智星球。在这里，每篇都学一个小知识。

微号：超智星球 网站:http://chaozhixingqiu.com

这期呢，还是计算机原理系列，上期最后讲到了自动制表机和IBM。本期接着讲计算机历史。

## 前言与内容提纲

上集，我们谈了计算机最早是机电设备，一般用十进制计数，比如用齿轮数来代表十进制。再到晶体管计算机电子计算机的晶体管可以打开或关闭电流(二进制)。

只用开/关两种状态也可以代表信息，这叫二进制。二进制计算机运算的核心，是各种开关。那么，为什么一堆开关，就能完成运算呢？这就是本期我们要讲的内容。

* 为什么用二进制, 布尔代数与布尔逻辑

* 3个基本操作：NOT，AND，OR——或且非

* 对应的：非门、且门、或门的电路实现

* 基于上述门，制作一个XOR——异或门

## 二进制的工程优势与数学基础

你可能觉得晶体管只有两种状态不多，功能很有限。事实上，晶体管的确可以不只是开/关，还可以让不同大小的电流通过，一些早期电子计算机是三进制的，有3种状态(比如苏联的某些计算机)，甚至五进制，5种状态。

问题是，状态越多，越难区分信号-如果手机快没电了或者附近有电噪音(因为有人在用微波炉)，信号可能会混在一起...而每秒百万次变化的晶体管会让这个问题变得更糟！

所以我们把两种信号尽可能分开 - 只用"开"和"关"两种状态，可以尽可能减少这类问题

这是计算机使用二进制的好处，但是，我们关心的问题是，为什么只凭借开关两种状态，就可以完成这么复杂的运算呢？

最关键的原因是，在当时，有一整个数学分支存在，专门处理"真"和"假"，它已经解决了所有法则和运算,叫"布尔代数"(Boolean Algebra)！

布尔代数是计算机的基础。没有它，就不会有计算机。所有数字芯片，从设计到生产，每一个环节都离不开布尔代数。事实上，它是现在计算机类学科必修的知识，从大学一年级课程开始，AND, OR, NOT 逻辑运算，CNF, DNF, 笛摩根定理…等等等等，就已经植根到每一个业者的脑海里。

## 布尔代数因布尔而得名

布尔代数的本质，是通过符号化和代数化来有系统地进行逻辑推理。它为逻辑推理发明了一套可以像算术演算一样的计算方法。

说起逻辑，这其实本来是哲学和语言学的一个分支，研究怎们样有条理的说话和写文章，远在古希腊时代就已经存在了。比如，与或非等逻辑的思想，从亚里士多德时代就有了。著名的三段论，就是亚里士多德提出的。

但哲学领域的逻辑学，都是用文字标书的。人的思维过程能用数学表示吗？在这个问题上，最早的可以追溯到莱布尼茨，他曾试图将逻辑思想形式化，就是将它们用简洁的数学形式表达出来，但没有获得成功。

> 我想寻求这样一张特殊的字母表，其元素表示的不是声音而是概念。有了这样一个符号系统，我们就可以发展出一种语言，我们仅凭符号演算，就可以确定用这种语言写成的哪些句子为真，以及它们之间存在着什么样的逻辑关系。——莱布尼茨的愿望

这个问题在莱布尼茨的一百多年后，终于被布尔解决(莱布尼茨和牛顿的微积分大约是在布尔出生前150年出现)。

布尔应用代数方法研究了逻辑，把一些简单的逻辑思维数学化，建立了逻辑代数【在之前，1843年，汉密尔顿已经发明了四元数代数，这个东西肯定对布尔有所启发】

1847年，32岁的布尔出版了一本书，将他的研究成果整理发表，只有86页。名字叫做《逻辑的数学分析》The Mathematical Anaysis of Logic。这也是布尔代数第一次公之于众。

## 布尔代数的内容

现在的数学书上已经把布尔代数讲的云里雾里，非常抽象，看起来就让人头大，但其实它本来是很简单的。本文帮助你理解布尔代数，以及为什么它促成了计算机的诞生。

所谓逻辑，就是判断真假或者是非。逻辑的基础是三段论，这是古希腊的哲学家亚里斯多德发明的，包括一个大前提、一个小前提和一个结论。我们举个例子来看一下：

1. 所有人都是会死的。（这是大前提）

2. 苏格拉底是人。（这是小前提）

3. 所以，苏格拉底也是会死的。（这是结论）

在这个推理的三段论中，我们关心的是最后的结论是真的，还是假的。当大前提和小前提都是真的时，那么结论也必然是真的。

前面的例子是一个单一的判断。布尔代数是关于几个判断之间的逻辑关系的演算，所以称为逻辑代数。

假设，关于苏格拉底，有下面两种说法：

* 苏格拉底是一个人————这个大家都知道是 **真** 的

* 苏格拉底还活着————这显然是 **假的** ，苏格拉底已经死了两千多年了

在这两种说法的基础上，我们来看看下面几种说法的真假：

* 苏格拉底是一个人 **并且** 苏格拉底还活着。

这种说法自然不能成立。因为，'并且'是一个并列的逻辑关系，其前后的条件都必须为真，整个判断才能成立；如果其中的任何一个条件是**假**的，那么整个判断就是假的，这个事件就不会发生。

在上面的说法中，如果把表示逻辑关系的词'并且'换成'或者'，像下面这样：

* 苏格拉底是一个人，或者，苏格拉底还活着。

那么，这种说法就是成立的，因为，'或者'是一个选择性的逻辑关系，所有的条件中，只要其中任意一个条件是真的，那么，这个判断就是**真**的，这整个事件就会发生。

这是两种最基本的逻辑关系。除此之外，我们还有关于'否定'的逻辑关系，就是'非'逻辑。'非逻辑'就是对一个判断作相反的操作，'真'的一否定，就变成了'假'的；'假'的一否定，就变成了'真'的。比如：

* 苏格拉底不是人————这显然是假的

乔治·布尔就是用数学的方法来研究我们前面讲的这些逻辑关系。在"常规"代数里(你在高中学的那种)变量的值是数字，可以进行加法或乘法之类的操作。

简单代数系统可以表达为：

数量属性：

1. 变量是自然数

2. 每一个自然数a都有一个后继a+1

数量值运算：加减乘除

运算法则：结合律、分配率等等

但在布尔代数中，变量的值是 true 和 false，能进行逻辑操作。

逻辑代数有下面几个规则和运算法则，因为逻辑运算不是算术计算，所以有以下规定：

（1)布尔代数中，数值只能取true和false或者0和1

用字母来代替我们前面那些例子中的具体的人和事，并且他用数字1表示'真'，用数字0表示'假'。这样一来，逻辑判断就变成了数学运算。

* 用A代表'苏轼是诗人'，所以A = 1

* 用B代表'苏轼还活着'，所以B = 0

* 用C表示'苏轼已经死了'，所以C = 1

(2)布尔代数中，变量可以进行“或且非”三种逻辑操作

用'乘法'来表示'且'运算，用'加法'来表示'或'运算，在字母上面加一撇'''表示'非'运算，那么，这三个判断之间的逻辑关系就可以变成这样：

* A + B = 1 + 0 = 1

* A + C = 1 + 1 = 1

* A·B = 1·0 = 0

* A·C = 1·1 = 1

* B' = C = 0' = 1

(3)逻辑运算满足以下定律：

* 交换律：

* A + B = B + A

* A·B = B·A

* 结合律：

* (A+B) + C = A + (B + C)

* (A·B)·C = A·(B·C)

* 吸收律：

* A + A·B = A

* (A + B)(A + C)=A + B·C

* 反演律：

* （A·B·C……）' = A' + B' + C' + ……

有了吸收率和反演律，有些看似非常复杂的逻辑关系，就可以化简合并。比如：

这个式子中字母上面的短横和前面式子中的'''是同样的意思，代表'非'运算。

去掉算术系统中数字的属性及其意义，保留对数字的操作；用逻辑值（true和false）代替数值，而逻辑值有自己的属性和意义，就形成了布尔逻辑系统。

其他运算可以参照代数逻辑推演出来。这样布尔就把逻辑归约成代数运算系统，发现代数系统中的运算法则（结合，交换，分配法则）同样也适用于逻辑系统。

有了逻辑系统，我们就可以对句子进行推理，也就实现了开头莱布尼茨的愿望。这样代数系统就有了推理能力。

推理能力正是布尔逻辑产生的原因，也是其最重要的意义所在。而推理是比代数运算更具有普适性的运算，因此，推理反过来又可以构建代数系统，甚至可以用来构建任何系统(计算机的强大就是证明)。

明白这一点也就明白了计算机中的抽象的本质，明白了如何去构建一个可用的抽象系统，计算理论中有一个名词，图灵可归约，其实是一个意思。

## 布尔代数因香农而不凡

讲了这么多，大家可能要问，布尔搞出这些无聊的字母游戏有什么用？

这个问题，不仅你我疑惑，在当时，整个学界也是疑惑的。布尔代数发明后很久都不受重视。数学家们曾轻蔑地说它：没有数学意义，在哲学上也属于稀奇古怪的东西。

直到20世纪初，罗素在《数学原理》中提到：“纯数学是布尔在一部他称之为《思想规律》的著作中发现的”，人们这才关注到布尔代数。但还是认为它是毫无实际用途的“纯数学”。

直到1938年，一位年仅22岁的美国年轻人在《继电器与开关电路的符号分析》中，将布尔代数与开关电路联系起来了。这篇文章是他在麻省理工学院（MIT）获得电气工程硕士学位的毕业论文。

上世纪八十年代，被誉为“多元智能理论”之父的哈佛大学教授霍华德.加德纳（HowardGardner）曾经评论这篇文章：“它可能是本世纪最重要、最著名的一篇硕士论文”。

这位年轻人就是克劳德.艾尔伍德.香农(这位后面我们也会讲到)

## 用布尔代数制作计算机

我们前面已经说过，这个东西用处非常巨大。它是我们现代这个电子时代和信息社会最底层的基本原理。如果没有布尔代数，什么计算机、自动控制、手机、互联网等等这一切，都不可能存在。

数学公式和科学原理，并不能直接产生任何实际的用途，还必须有相应的实现这些功能的物理元件。恰好，咱上期继电器、电子管和晶体管的发明，为实现逻辑控制和信息的数字化处理，铺平了道路。没看过的同学，可以关注超智星球公号，看一下。

我们知道，计算机、手机、自动控制系统、人工智能等等这些东西，都是用集成电路——也就是电子芯片组装起来的。而集成电路是由几千万、上亿个晶体管组成的。

而晶体管，我们上一篇文章说过了，就是个受控制的开关。可以接收控制信号，改变是否导电。我们可以假设开关接通的状态为'1'，开关不通的状态为'0'，这样就可以用开关电路模拟逻辑状态，组成逻辑电路。而这最最基本的逻辑电路，我们称为**“逻辑门”**。之所以叫 "门"，是因为它能控制电流的路径。

逻辑门可以由电阻、电容、二极管、三极管等分立原件构成，成为**分立元件门**。也可以将门电路的所有器件及连接导线制作在同一块半导体基片上，构成**集成逻辑门电路**。

对应布尔代数中有三个基本操作：NOT, AND 和 OR。构成计算机最基本的逻辑门就是：与门、或门、非门。将这三个基本逻辑电路通过不同的组合关系，就形成了人们所需要的各种数字电路。

我们来看下如何使用晶体管制作这三个逻辑门。

## NOT 和 "非门"

NOT 操作把布尔值反转，把 true 进行 NOT 就会变成 false，反之亦然。我们可以根据 NOT 操作的输入和输出，做出这个表。我们叫NOT操作表。

我们先来看一个晶体管。晶体管只是电控制的开关，有3根线：2根电极和1根控制线。

控制线通电时，电流就可以从一个电极流到另一个电极。就像水龙头一样- 打开水龙头，就有水流出来；关掉水龙头，就没水了。

可以把控制线，当做输入(input)；底部的电极，当做输出（output）；所以 1 个晶体管，有一个输入和一个输出。

如果我们打开输入（input on)，输出也会打开（output on），因为电流可以流过；如果关闭输入（input off），输出也会关闭（output off），因为电流无法通过

或者用布尔术语来说，输入为真，输出为真；输入为假，输出为假，我们也可以把这个做成"真值表"

这个电路没什么意思，因为它没做什么事-输入和输出是一样的，但我们可以稍加修改，实现NOT。

与其把下面那根线当做输出，我们可以把输出放到上面，如果打开输入，电流可以流过然后 "接地"，输出就没有电流，所以输出是off。如果用水来举例，就像家里的水都从一个大管子流走了，打开淋浴头一点水也没有。

如果输入是on，输出是 off；当输入是 off，电流没法接地，就流过了输出，所以输出是 on；如果输入是off，输出是on。和NOT操作表一样！太棒了！

我们做了个有点用的电路！我们叫它 "非门"-。

## AND 和 "且门"

在布尔代数中，"AND"操作有 2 个输入，1 个输出；和上次一样，可以给"AND"做个表。

为了实现 "AND 门"，我们需要2个晶体管连在一起，这样有2个输入和1个输出

如果只打开 A，不打开 B 电流无法流到 output，所以输出是 false;如果只打开B，不打开 A，也一样，电流无法流到 output;只有 A 和 B 都打开了，output 才有电流。

## OR 和 “或门”

最后一个是OR-- 只要 2 个输入里，其中 1 个是 true，输出就是 true

实现 "OR 门" 除了晶体管还要额外的线，不是串联起来。而是并联，然后左边这条线有电流输入。用"小拱门"代表2条线没连在一起，只是跨过而已(虽然看起来像连在一起)

如果 A 和 B 都是 off，电流无法流过，所以输出是 off；如果打开 A，电流可以流过。输出是 on。如果只打开 B 也一样，只要 A OR B是on，输出就是 on；如果 A 和 B 都 on，结果是on。

## 一次抽象：制作"异或门"-XOR

好，现在 NOT门, AND门, OR门 都搞定了，我们可以基于它们构建更复杂的门了。

但在开始之前呢，我们先进行一次抽象，我们只是用符号来代表这三个门，这样我们构建其他电路的时候，就不再管底层的细节(也就是那些开关)，可以集中精力用来构建更复杂的系统。

NOT门的画法是三角形前面一个圆点；AND门用D表示；OR门用太空船表示————"D 形状和太空船"不是标准叫法, 只是我喜欢这样叫而已。

前面说的三个操作，是最基本的逻辑操作。除了前面说的三个，另一个有用的布尔操作叫"异或"，XOR。

XOR就像普通OR，但有一个区别：如果2个输入都是true，XOR输出false；想要XOR输出true，一个输入必须是true，另一个必须是false

用晶体管实现XOR门有点烧脑子，但可以展示一下怎么用前面提到的3种门来做XOR门：

XOR门有2个输入，A和 B ，还有1个输出.

## 最后，聊聊抽象

XOR超有用的，我们下次再说它。因为超有用，工程师给了它一个符号，一个 OR 门 + 一个笑脸

重要的是，我们现在可以知道怎么造XOR门了，并且用抽象符号封装了它。我们完成了又一层抽象，把 XOR 放入"工具箱"了。

后面的课程中，我们可以直接使用它来推导更高级的运算，而不用担心XOR具体用了几个门，这几个门又是怎么用晶体管拼的，或电子是怎么流过半导体的。

工程师设计处理器时，很少在晶体管的层面上思考，而是用更大的组件，比如逻辑门，或者由逻辑门组成的更大组件，我们以后会讲，就算是专业程序员也不用考虑逻辑是怎样在物理层面实现的。

这关键的能力，就是抽象，封装。抽象能力决定一个人的编程能力。

我们从电信号开始，到现在第一次表示数据-真和假-开始有点"计算"的感觉了。

好啦，本期我们实现了布尔代数最最重要的三层门。我们下期见。

微号：超智星球 网站:http://chaozhixingqiu.com

参考文献：

1. 杨露斯, 黎炼. 论计算机发展史及展望[J]. 信息与电脑(理论版), 2010(06):194.

2. N·M·莫里斯, 杨光辉. 英国标准——二进制逻辑元件的符号[J]. 煤矿自动化, 1984(02):41.

3. N.A.知乎.布尔代数是怎么出现的？.2017.

4. 阮一峰.布尔代数入门.阮一峰博客.2016

5. CrashCourse/CrashCourse字幕组.《计算机科学速成课》.youtube.2018