Chapter Eight

Relays and Gates

Reduced to its essentials, a computer is a synthesis of Boolean algebra and electricity. The crucial components that embody this melding of math and hardware are known as logic gates. These gates are not unlike the familiar gates through which water or people pass. Logic gates perform simple operations in Boolean logic by blocking or letting through the flow of electrical current.

You’ll recall that in Chapter 6 you entered a pet shop and boldly announced, “I want a male cat, neutered, either white or tan; or a female cat, neutered, any color but white; or I’ll take any cat you have as long as it’s black.” These criteria are summarized by the following Boolean expression:

This expression can be interactively realized in a circuit made up of switches, a battery, and a lightbulb:

Such a circuit is sometimes called a network, except that nowadays that word is used much more often to refer to connected computers rather than to an assemblage of mere switches.

The circuit contains a combination of switches, some wired in series and some wired in parallel. Switches wired in series perform logical AND operations, symbolized in the Boolean expression with a × sign. Switches wired in parallel perform a logical OR operation corresponding to the + sign. Because this circuit is equivalent to a Boolean expression, if the Boolean expression can be simplified, the circuit can be as well.

Here’s the expression that indicates the characteristics you want in a cat:

Let’s try to simplify it. Using the commutative law, you can reorder the variables that are combined with the AND (×) signs and rewrite the expression this way:

In an attempt to clarify what I’m going to do here, I’ll define two new symbols named X and Y:

Now the expression for the cat that you want can be written like this:

After we’re finished, we can put the X and Y expressions back in.

Notice that the N variable appears twice in the expression. Using the distributive law, the expression can be rewritten like this, with only one N:

Now let’s put the X and Y expressions back in:

Due to the plethora of parentheses, this expression hardly looks simplified. But it has one less variable, which means one switch can be eliminated. Here’s the revised version:

Indeed, it’s probably easier to see that this network is equivalent to the earlier one than to verify that the expressions are the same!

But there are still too many switches in this network. There are separate switches for Male and Female, and only one should be required, perhaps on (or closed) for Female and off (or open) for Male. Similarly, there are separate switches for White and Not White.

Let’s make a control panel right now for choosing a cat. The control panel is simply five switches (much like the on/off switches you have on your walls for controlling your lights) and a lightbulb mounted in a panel:

The switches are on (closed) when they’re up, and off (open) when they’re down. The first switch lets you select Female or Male; the second is Neutered or Unneutered. There are three switches for selecting color: Black, White, and Tan. Only one of these should be on at any time, or none of them to select an Other-colored cat.

In computer terminology, the panel of switches constitutes an input device. Input is information that controls how a circuit behaves, in this case describing the characteristics of an ideal kitty. The output device is the lightbulb. This bulb lights up if the switches describe a satisfactory cat. The switches shown in the control panel are set for a female unneutered black cat. This satisfies your criteria, so the lightbulb is lit.

Now all we have to do is design a circuit that makes this control panel work.

In the previous chapter, you saw how devices called relays were crucial to the workings of the telegraph system. Over long distances, the wires connecting telegraph stations had a very high resistance. Some method was needed to receive a weak signal and resend an identical strong signal. The relay did this by using an electromagnet to control a switch, in effect, amplifying a weak signal to create a strong signal.

At this moment, we’re not interested in using the relay to amplify a weak signal. We’re interested only in the idea of a relay being a switch that can be controlled by electricity rather than by fingers. Although relays were originally designed for telegraphs, they eventually became part of the switching circuits used in the vast network of the telephone system, and this is how their versatility became more apparent to imaginative electrical engineers.

Like switches, relays can be connected in series and in parallel as logic gates to perform simple tasks in logic. When I say that these logic gates perform simple tasks in logic, I mean as simple as possible. Relays have an advantage over switches in that relays can be switched on and off by other relays rather than by fingers. This means that logic gates can be combined to perform more complex tasks, such as simple functions in arithmetic and, eventually, the workings of entire computers.

The discovery that relays could be used for performing Boolean operations is generally credited to computer pioneer Claude Elwood Shannon (1916–2001), whose famous 1938 M.I.T. master’s thesis was entitled “A Symbolic Analysis of Relay and Switching Circuits,” but a similar equivalence had been described a couple of years earlier by Japanese electrical engineer Akira Nakashima.

You can wire a relay with a switch, a lightbulb, and a couple of batteries like this:

The switch at the left is open, and the lightbulb is off. When you close the switch, the battery at the left causes current to flow through the many turns of wire around the iron bar. The iron bar becomes magnetic and pulls down a flexible or pivoting metal contact that connects the circuit to turn on the lightbulb:

When the electromagnet pulls the metal contact, the relay is said to be triggered. When the switch is turned off, the iron bar stops being magnetic, and the metal contact returns to its normal position.

This seems like a rather indirect route to light the bulb, and indeed it is. If we were interested only in lighting the bulb, we could dispense with the relay entirely. But we’re not interested in lighting bulbs. We have a much more ambitious goal.

I’ll be using relays a lot in this chapter (and then hardly at all after the logic gates have been built), so I want to simplify the diagram. We can eliminate some of the wires by using a ground and a capital V (for voltage) to represent the battery, as was done in Chapters 5 and 7. In this case, the grounds simply represent a common connection; they don’t need to be connected to the physical earth. Now the relay looks like this:

When the switch is closed, a current flows between V and ground through the coils of the electromagnet. This causes the electromagnet to pull the flexible metal contact. That connects the circuit between V, the lightbulb, and ground. The bulb lights up:

These diagrams of the relay show two voltage sources and two grounds, but in all the diagrams in this chapter, all the V’s can be connected to one another, and all the grounds can be connected to one another.

More abstractly, the relay can be shown without the switch and lightbulb but labeled with inputs and outputs:

If a current is flowing through the input (for example, if a switch connects the input to V), the electromagnet is triggered, and the output has a voltage.

The input of a relay need not be a switch, and the output of a relay need not be a lightbulb. The output of one relay can be connected to the input of another relay, for example, like this:

These relays are said to be cascaded. When you turn the switch on, the first relay is triggered, which then provides a voltage to the second relay. The second relay is triggered, and the light goes on:

Connecting relays is the key to building logic gates.

Just as two switches can be connected in series, two relays can be connected in series:

Now there are two switches on two relays. The output of the top relay supplies a voltage to the second relay. As you can see, when both switches are open, the lightbulb isn’t lit. We can try closing the top switch:

Still the lightbulb doesn’t light, because the bottom switch is still open and that relay isn’t triggered. We can try opening the top switch and closing the bottom switch:

The lightbulb is still not lit. The current can’t reach the lightbulb because the first relay isn’t triggered. The only way to get the bulb to light up is to close both switches:

Now both relays are triggered, and current can flow between V, the lightbulb, and ground.

Like the two switches wired in series that you saw in Chapter 6, these two relays are performing a little exercise in logic. The bulb lights up only if both relays are triggered. These two relays wired in series are known as an AND gate because it is performing a Boolean AND operation.

To avoid excessive drawing, electrical engineers have a special symbol for an AND gate. That symbol looks like this:

This is the first of six basic logic gates. The AND gate has two inputs and one output. You’ll often see the AND gate drawn with the inputs at the left and the output at the right. That’s because people who are accustomed to reading from left to right prefer reading electrical diagrams from left to right. But the AND gate can just as well be drawn with the inputs at the top, the right, or the bottom.

The previous diagram with two relays connected in series is symbolized more succinctly like this:

Notice that this symbol for the AND gate not only takes the place of two relays wired in series, but it also implies that the top relay is connected to a voltage and that both relays are connected to ground. Again, the lightbulb lights up only if both the top switch and the bottom switch are closed. That’s why it’s called an AND gate.

If we think of the absence of a voltage as a 0, and the presence of a voltage as a 1, the output of the AND gate is dependent on inputs like this:

As with the two switches wired in series, the AND gate can also be described in this little table:

The inputs of the AND gate don’t necessarily have to be connected to switches, and the output doesn’t necessarily have to be connected to a lightbulb. The output of one AND gate can be an input to a second AND gate, like this:

This bulb will light up only if all three switches are closed. Only if the top two switches are closed will the output of the first AND gate output a voltage, and only if the third switch is also closed will the second AND gate output a voltage.

This configuration can also be expressed by this symbol:

It’s called a 3-input AND gate. The output is 1 only if all the inputs are 1. You can also create AND gates with many more inputs.

The next logic gate requires two relays that are wired in parallel, like this:

Notice that the outputs of the two relays are connected to each other. This connected output then provides power for the lightbulb. Either one of the two relays is enough to light the bulb. For example, if we close the top switch, the bulb lights up. The bulb is getting power from the top relay:

Similarly, if we leave the top switch open but close the bottom switch, the bulb lights up:

The bulb also lights if both switches are closed:

We’ve made a circuit in which the bulb lights up if the top switch or the bottom switch is closed. The key word here is or, so this is called the OR gate. Electrical engineers use a symbol for the OR gate that looks like this:

It’s somewhat similar to the symbol for the AND gate except that the input side is rounded, much like the O in OR. (That might help you to remember which is which.)

The output of the OR gate supplies a voltage if either of the two inputs has a voltage. Again, if we say that the absence of a voltage is 0 and the presence of a voltage is 1, the OR gate has four possible states:

The output of the OR gate can be summarized the same way as the AND gate:

OR gates can also have more than two inputs. The output of such a gate is 1 if any of the inputs are 1; the output is 0 only if all the outputs are 0.

The relays that I’ve been showing you here are called double-throw relays. At rest, the pivoting metal bar at the top is touching one contact, and when the electromagnet pulls it, it hits another contact. The lower contact is called the normally open output. That’s the one we’ve been using, but we could just as well use the upper contact, called normally closed. When we use this upper contact, the output of the relay is reversed. The lightbulb is on when the input switch is open:

When the input switch is closed, the bulb goes out:

A single relay wired in this way is called an inverter. It’s represented by a special symbol that looks like this:

It’s called an inverter because it inverts 0 (no voltage) to 1 (voltage) and vice versa:

This is a realization of the Boolean NOT operator.

Sometimes when people see the top inverter here, they ask, “How can there be a voltage at the output if there’s no voltage at the input? Where does that voltage come from?” Keep in mind that the inverter is actually a relay that is connected to a voltage.

With the inverter, the AND gate, and the OR gate, we can start wiring the control panel to automate a choice of the ideal kitty. Here it is again:

Let’s begin with the switches. The first switch is closed for female and open for male. Thus we can generate two signals that we’ll call F and M, like this:

When F is 1, M will be 0, and vice versa. Similarly, the second switch is closed for a neutered cat and open for an unneutered cat:

The other three switches select the color: black, white, or tan. Here are all three wired to a voltage:

Some simple rules govern how you can connect gates and inverters: The output of one gate (or inverter) can be the input to one or more other gates (or inverters). But do not connect the outputs of two or more gates (or inverters) to one another.

The simplified version of the cat-selection expression was

For every + sign in this expression, there must be an OR gate in the circuit. For every × sign, there must be an AND gate.

The symbols down the left side of the circuit diagram are in the same order as they appear in the expression. These signals come from the previous three illustrations. Notice the use of another inverter for the (1 − W) part of the expression.

Now you might say, “That’s a heck of a lot of relays,” and yes, that’s true. There are two relays in every AND gate and OR gate, and one relay for each inverter. But I’m afraid you’ll be seeing a lot more relays in the chapters ahead. Just be thankful you don’t actually have to buy them and wire them at home. (Unless you want to.)

I mentioned earlier that there are six standard logic gates. You’ve already seen three, and now it’s time for the others. The first two use the normally closed output of the relay that is used for the inverter. This output has a voltage present when the relay is untriggered. For example, in this configuration the output from one relay supplies power to a second relay. With both inputs off, the lightbulb is on:

If the top switch is closed, the bulb goes off:

The light goes off because power is no longer being supplied to the second relay. Similarly, if the top switch is open but the bottom switch is closed, the light is also off:

And if both switches are closed, the lightbulb is off:

This behavior is precisely the opposite of what happens with the OR gate. It’s called NOT OR or, more concisely, NOR. This is the symbol for the NOR gate:

It’s the same as the symbol for the OR except with a little circle at the output. The circle means invert. The NOR is the same as an OR gate followed by an inverter.

The output of the NOR gate is shown in the following table:

This table shows results opposite those of the OR gate, which are 1 if either of the two inputs is 1 and 0 only if both inputs are 0.

Yet another way to wire two relays is shown here:

In this case, the two outputs are connected, which is similar to the OR configuration but using the other contacts. The lightbulb is on when both switches are open.

The lightbulb remains on when only the top switch is closed because the bulb can get power from the bottom relay:

Similarly, the lightbulb remains on when only the bottom switch is closed because it gets power from the top relay:

Only when both switches are closed does the lightbulb go off:

This behavior is exactly opposite that of the AND gate. This is called NOT AND or, more concisely, NAND. Unlike NOR, the word NAND was coined specifically to describe this type of logic. The word dates from 1958.

The NAND gate is drawn just like the AND gate but with a circle at the output, meaning the output is the inverse of the AND gate:

The NAND gate has the following 'margin-bottom:0cm;text-align:justify;line-height: normal'>

You’ll recall that the output of the AND gate is 1 only if both inputs are 1; otherwise, the output is 0. The output of the NAND gate is opposite that.

At this point, we’ve looked at four different ways of wiring relays that have two inputs and one output. Each configuration behaves in a slightly different way. To avoid drawing and redrawing the relays, we’ve called them logic gates and decided to use the same symbols to represent them that are used by electrical engineers. The output of the particular logic gate depends on the input, which is summarized here:

The inverter looks like this:

It inverts a signal from 0 to 1 or from 1 to 0.

Completing this array of tools is just a regular old relay:

This is called a buffer, and this is the symbol for it:

It’s the same symbol as the inverter but without the little circle. The buffer is remarkable for not doing much. The output of the buffer is the same as the input:

But you can use a buffer when an input signal is weak. You’ll recall that this was the reason relays were invented for the telegraph many years ago. In real-life logic circuits, sometimes one output must serve as many inputs. This is known as fan out, and it can result in a lessening of the power available to each output. Buffers can help boost that power. Or a buffer can be used to slightly delay a signal. This works because the relay requires a little time—some fraction of a second—to be triggered.

From here on in this book, you’ll see very few drawings of relays. Instead, the circuits that follow will be built from buffers, inverters, the four basic two-input logic gates, and more sophisticated circuits built from these logic gates. All these other components are made from relays, of course, but we don’t actually have to look at the relays anymore.

Toward the beginning of this chapter, a little control panel was shown that let you select an ideal kitten. It had switches for black, white, and tan cats, but it omitted a switch for other colors—any cat that is not black or white or tan. But that’s a signal that can be created using three inverters and a three-input AND gate:

Three inputs are inverted and become inputs to an AND gate. Only when B, W, and T are all 0 will all the inputs to the AND gate be 1, causing the output to be 1.

Sometimes a configuration like that is drawn without the inverters:

Notice the little circles at the input to the AND gate. Those little circles mean that the signals are inverted at that point—a 0 (no voltage) becomes a 1 (voltage) and vice versa.

If you had to choose just one logic gate from the six that I’ve shown you, make it either a NAND or a NOR. You can use a NAND or a NOR to create all the other logic gates. For example, here’s how to combine the inputs of a NAND gate to create an inverter:

You can use that inverter on the output of another NAND gate to make an AND gate. At first, it doesn’t seem possible that you can make an OR gate from a NAND gate, but you can. That’s because an AND gate with all its inputs inverted does exactly the same thing as a NOR gate:

The output is 1 only if both inputs are 0.

Similarly, an OR gate with the two inputs inverted is equivalent to a NAND gate:

The output is 0 only if both inputs are 1.

These two pairs of equivalent circuits represent an electrical implementation of De Morgan’s laws. Augustus De Morgan was another Victorian mathematician, nine years older than George Boole, whose book Formal Logic was published in 1847, the very same day (the story goes) as Boole’s The Mathematical Analysis of Logic. Indeed, Boole had been inspired to investigate logic by a very public feud that was being waged between De Morgan and another British mathematician involving accusations of plagiarism. (De Morgan has been exonerated by history.) Very early on, De Morgan recognized the importance of Boole’s insights. He unselfishly encouraged Boole and helped him along the way and is today sadly almost forgotten except for his famous laws.

De Morgan’s laws are most concisely expressed this way:

A and B are two Boolean operands. The bars on top indicate an inversion. In the first expression, A and B are inverted and then combined with the Boolean AND operator. This is the same as combining the two operands with the Boolean OR operator and then inverting the result (which is the NOR). It also works in English: If it’s not raining and it’s not snowing, then it’s not raining or snowing.

In the second expression, the two operands are inverted and then combined with the Boolean OR operator. This is the same as combining the operands with the Boolean AND operator and then inverting (which is the NAND). If I’m not big or I’m not strong, then I’m not big and strong. De Morgan’s laws are an important tool for simplifying Boolean expressions and, hence, for simplifying circuits. Historically, this was what Claude Shannon’s paper really meant for electrical engineers. But obsessively simplifying circuits won’t be a major concern in this book. It’s preferable to get things working rather than to get things working as simply as possible.

The next major project is nothing less than a digital adding machine implemented entirely with logic gates. But that project will need to be deferred for several chapters while we go back to elementary school and learn to count.