计算机科学导论：跨学科方法

7.3　组合电路

许多计算任务都可以归约为寻找特定数学函数在给定输入情况下的函数值。在本节中，我们重点关注构建电路以完成这部分任务。例如，我们知道任何计算机都需要一个将两个二进制数相加的电路：那么我们如何构建一个这样的电路呢？

解决这个问题的过程中你可能会有两个惊喜的发现。第一，有一个简单的系统化的方法来构建电路，它可以计算任何定义明确的布尔函数。我们会在本节中的后续部分介绍这种方法。一旦你掌握了这种方法，你就会发现它仅在输入值较少时适用，因为过多的输入值会导致大量的开关和导线的使用。在设计计算机的过程中，我们不仅要考虑如何为我们需要的函数建立电路，而且还要考虑这样的电路在现实世界是否可行。第二，对于实现TOY这样的计算机需要的函数所需的电路，只需要经过一些简单的层次抽象就能开发出来，而且非常容易理解。本节的重点是学习这类电路的原理。

我们会具体讲解如何为布尔函数构建对应的电路。这些电路被称为组合电路（combinational circuit），因为它们的输出值取决于它们的输入值。组合电路是理解计算机操作必不可少的出发点。

我们从大家所知的门级电路开始讲解。它们的基本功能是实现“非”“或非”“或”以及“与”等布尔函数。然后，我们将进入更深的一个层次：通过将众多门级电路连接在一起，构建实现各种逻辑开关的电路。之后，我们考虑将布尔函数的真值表定义转换为实现它的电路的一般结构。为了解释这些模块的构建过程，我们首先从将两个二进制数字相加的电路开始。通过本节内容，我们会对电路组合、电路连接，以及利用它们在更深层次上构建电路等有更深入的了解。

门　正如我们在7.1节看到的那样，布尔逻辑是一个抽象的数学系统，在近两个世纪里，它在数学推理中发挥了核心作用。但是它与构建计算机有什么关系呢？这种联系是由克劳德·香农（Claude ...