NUTS AND SOL TS 19
lying representation. Once we figure out how to accomplish a given function, we can put the mechanism inside a “black box,” or a “building block” and stop thinking about it. The function embodied by the building block can be used over and over, without reference to the details of what’s inside. This process of functional abstraction is a fundamental in computer design-not the only way to design complicated systems but the most common way (later, I’ll describe an alternate method). Computers are built up of a hierarchy of such functional abstractions, each one embodied in a build ing block. The blocks that perform functions are hooked together to implement more complex functions, and these collections of blocks in turn become the new building blocks for the next level.
This hierarchical structure of abstraction is our most powerful tool in understanding complex systems, because it lets us focus on a single aspect of a problem at a time. For instance, we can talk about Boolean functions like And and Or in the abstract, without worrying about whether they are built o ut of electrical switches or sticks and strings or water operated valves. For most purposes, we can forget about technology. This is wonderful, because it means that almost everything we say about computers will be true even when transistors and silicon chips become obsolete.
CHAPTER 2
………………………………………………………………..
U NIVERSAL BU ILDING BL O CKS
From now on, we can forget about wires and switches and work with the abstraction of logic blocks operating on l’s and O’s, a simple step that allows us to pass from the realm
of engineering into the realm of mathematics. This is the most abstract chapter in the book; it will show you how the methods used to construct a tic-tac-toe machine can be used to construct almost any function. In it, we’ll define a power ful set of building blocks: logical functions and finite-state machines. With these elements, it’s easy to build a com puter.
LOGICAL FUNCTIONS
In constructing the tic-tac-toe machine, we began by writing
the game tree, whch gave us a set of rules for generating the outputs from the inputs. This turns out to be a generally use ful method of attack. Once we write down the rules that specify what outputs we want for each combination of inputs, we can build a device that implements these rules
using And, Or, and Invert functions. The logic blocks And,
21
22 THE PATTERN ON THE STONE
Or, and Invert form a universal construction set, which
can be used to implement any set of rules. (These primi
tive types of logic blocks are sometimes also called logic
gates.)
This idea of a universal set of blocks is important: it
means that the set is general enough to build anything. My
favorite toy when I was a child was a set of interlocking plas
tic bricks called Lego blocks, with which I built all kinds of
toys: cars, houses, spaceships, dinosaurs. I loved to play
with these blocks, but they were not quite universal, since
the only objects you could build with them had a certain
squarish, stair-steppy look. Building something with a differ
ent shape-a cylinder or a sphere, for example-would
require a new type of block. Eventually, I had to switch to
another medium in order to build the things I wanted. But
the And, Or, and Invert blocks of Boolean logic are a univer
sal construction set for converting inputs to outputs. The
best way to see how they form a universal set is to under
stand a general method for using them to implement rules.
To start, we will consider binary rules-rules that specify
inputs and outputs that are either 1 or 0. The tic-tac-toe
machine is a good example of a function specified by binary
rules, because the input switches and the output lights are
either on or off-that is, either 1 or 0. (Later, we will discuss
rules for handling letters, numbers, or even pictures and
sounds as inputs and outputs.) Any set of binary rules can be
completely specified by showing a table of the outputs for
each possible combination of l’s and O’s on the inputs. For
example, the rules for the Or function are specified by the
following table:
Input A Input B Output
0 0 0
OR Function 0 1 1
1 0 1
1 1 1
UNIVERSAL BUILDING BLOCKS 23
The Invert function is specified by an even simpler table:
Invert Function
Input
0
1
Output
1
0
For a binary function with n inputs, there are zn possiblecombinations of input signals. Sometimes we won’t bother tospecify all of them, because we don’t care about certain combinations of inputs. For example, in specifying the functionperformed by the tic-tac-toe machine, we don’t care whathappens if the human player plays in all squares simultaneously. This move would be disallowed, and we don’t need tospecify the function’s output for this combination of inputs. Complex logic blocks are constructed by connecting And,Or, and Invert blocks. In drawings of the connection pattern,the three blocks are conventionally represented by boxes ofdifferent shape (see Figure 9); the lines connecting on the leftside represent inputs to the blocks, and the lines connectingon the right represent the output. Figure 10 shows how apair of two-input Or blocks can be connected to form a threeinput Or function; the output of this function will be 1 if any
one of its three inputs is 1. It’s also possible to string severalAnd blocks together in a similar manner to make an Andblock with any number of inputs.
INPt,ir A=&- INPUT A-j}- IINI> OUTPUT 01( 0UTPtl1′ /NPllT B INPUT a–
INPur� ourrur
I A/VE 1?.r
FIGURE 9
And, Or, and Invert Blocks
24 THE PATTER N ON THE STON
E
FIGURE 10
==}, A three-input Or block
made from a pair of two-in put Or blocks
Figure 11 shows how an And bl ock can be constructed by
connecting an Inverter to the i nputs and output of an Or
block. (Here is De Morgan’s theo rem again.) The best way to
get a feeling for how this works i s to trace through the 1 ‘s and
O’s for every combination of inpu ts. Notice that this illustra
tion is essentially the same as Fi gure 6 in the previous chap
ter. It points up an interesting fa ct: we don’t really need And
blocks in our universal building set, because we can always
construct them out of Or blocks and Inverters.
l>- FIGURE 11
Making And out of Or
UNIVERSAL BUILDING BLOCKS 25
block, majority wins-that is, the output will be 1 only if two or more of the inputs are
