8X.5 Building a Computer
Now that you know the basic Boolean logic gates, it is time to start doing interesting things with them.
If your friend asked you for a Boolean control panel for her birthday, you would already know how to build something like this:
The two toggle switches represent the inputs, the truth values of the atomic sentences P and Q. The light bulbs display the truth values of various sentences. Using your knowledge from previous sections, you could wire up the machine so that the bulbs are on just in case the sentences they represent are true.
For example, if you flip the P switch to true, it should look like this:
But that’s just the beginning. What we want is a machine that can do computations.
One of the fundamental jobs of any computer processor is adding numbers. For example, a computer will often perform a task repeatedly, keeping count of how many times it’s done the task. When it does that, it uses a counter, and after each time it does the task it adds one to the counter. If a computer can’t do arithmetic, it can’t compute.
What we’ll learn in this section, then, is how to use logic gates to perform the most basic arithmetical task: adding two one-digit binary numbers together. A single binary digit of information is called a bit, so what will learn is how to build a 1-bit adder.
What we want is a machine that takes two inputs, call them X and Y, and provides an output number, Z, so that X+Y=Z. It will look something like this:
Since this is a 1-bid adder, X and Y will each be one digit, but Z could be two digits, since in binary 1+1=10.
That means we need two bits of information to display the sum, and this is why we have two light bulbs on the right side of this machine. Our goal is to wire the machine so it implements a table like this:
This is just a numerical truth table, using 1=T and 0=F. We’ve changed the letters from P and Q to X and Y, but that is only because you’re already used to thinking about X and Y standing for numbers.
The answer is the sum, in binary, of the two 1-bit inputs. Since we are dealing with binary, we cannot represent a number like 10 with a single light bulb. Instead, each bit of the answer will get its own bulb: one bulb for the first digit and another for the second.
Carry = twos’-place output
There is actually a special name for each of those bits: the ones’-place digit is called the sum, and the twos’-place digit is called the carry.
We can think of each of those outputs as it’s own truth function. So here is our plan for our 1-bit adder:
If we can hook up the wires of the control panel so that the light bulbs have those truth functions, then our machine will be a 1-bit adder:
Let’s take carry and sum each in turn. Carry, from the table above, has the truth function 1 on the top row and then the rest 0s.
That’s right: you already know how to wire carry, since you learned how to wire conjunction in previous sections. I bet you didn’t think it was going to be that easy!
Sum = Exclusive disjunction
Actually, it’s not going to be that easy. Wiring sum will be a lot harder. Sum is close to disjunction, but it is 0 (false) on the top row. In other words, sum is the exclusive disjunction (XOR, for short).
What we have to do is figure out how to wire XOR with just the Boolean logic gates, and then we will be done.
There are several good ways to do so. See if you can find them below.
As you can see, one way to create XOR from Boolean operations to use (P&~Q)v(~P&Q). Another equivalent formulation is (PvQ)&~(P&Q).
Let’s work with the first idea: (P&~Q)v(~P&Q). In order to build this, we will need to consider current coming from P as well as ~P, and from Q as well as ~Q.
In itself, that’s isn’t a big problem. Consider, for example, this idea:
This plan allows us to use current from each atomic being 1 or 0. But there is still a problem. The gates for P and Q are parallel, but the sentence (P&~Q)v(~P&Q) also has a conjunction in it. We somehow need to conjoin the lines for P and ~Q, as well as the lines for ~P and Q.
The solution is a simple bit of engineering, and once we have it we need nothing else in order to build a working computer. From an engineering point of view, there several different ways of solving this problem, and they chart the history of the development of computers: electromagnets, vacuum tubes, transistors, etc.
We will use electromagnets because they are wonderfully simple from the perspective of physics, and they show you just how rudimentary the inner workings of a computer can be.
To make an electromagnet, wrap a coil of wire around a piece of iron, like this:
Now, all we have to do is run electric current through the wire, and the iron becomes a magnet:
That’s all there is to it. What we can do with it is use the magnet to move a piece of metal. For example, let’s put another gate above the magnet, made of any material that will be attracted to it.
Here’s a second gate:
Now, if we close the P gate, the magnet fires and pulls the second gate closed as well. (The second gate has a spring or counterweight, so that it opens again if the magnet isn’t pulling it down.)
We could even put a light bulb on the circuit with this second gate.
Now, this machine itself is not earth shattering, since this light bulb will light up just as if it were on the inner P circuit.
What is powerful about this idea is that the second gate and the light bulb are on a different lines of wire, which allows us to combine gates like we need to build XOR.
Our diagrams are about to get messier, so we’d like to introduce some conventions for keeping them as clear as possible. Instead of drawing all the extra wires to get the circuits to return to the battery, let’s use a triangle.
We also don’t need to connect the various circuits to the same battery, so we can diagram it like this:
In the end we’ll just connect them all to the power source for our machine.
There’s no difference in substance between this style of diagram and the original, but once we add a lot more wires, this type will be much easier to look at.
Let’s return to our goal, to build a circuit that represents this sentence: (P&~Q)v(~P&Q).
Creating a parallel circuit for the disjunction was easy, but we didn’t know how to conjoin the P line and the ~Q line to make P&~Q.
To do that, we just need to put two electromagnets in series. Then we hook the first one up to P and the second one to ~Q.
First, let’s just look at what two electromagnets in series looks like. Say we have two gates, S and T.
If we just close one of the gates, like S, we pull down one of the upper gates. But the light doesn’t go on, because the gates are in series.
But if we close both S and T, then the light goes on.
Now we just need to apply this idea to create (P&~Q)v(~P&Q).
Let’s start by connecting wires to a P gate, so that one is powered when P is true and the other is powered when P is false. That allows us to represent P and ~P.
Now what we need to do is put the ~P line with the bulb in series with a gate for Q.
As you can see in this picture, the bulb isn’t on because Q is not true/closed.
So currently this circuit really does represent ~P&Q. It is on only when P = 0 and Q = 1.
What we need to do next is create a similar circuit for P&~Q, and then disjoin it with this one.
Here’s how we would disjoin it with P.
Like before, if P = 0 and Q = 1, then the light is on. But also if P = 1, then the light is on regardless of what Q is.
We are almost done, because now we just have to put an electromagnet for ~Q in series with the line coming from P.
This next step is going to make our diagram look messy, because the line from ~Q is going to cross some of the other lines. Just think of it as a separate wire passing in the background. They do not actually intersect. The dot at the intersection near the light bulb, by contrast, represents that all those lines are actually connected.
Here’s our completed diagram.
You can see from its current state that if P = 1 and Q = 1, the light is off. But if you change either one of those to zero, the bulb will go on.
But if both P = 0 and Q = 0, then the light is also off. What that means is that we have successfully created an XOR circuit.
Let’s recall what this accomplishes. Our goal was to use Boolean circuits to create a 1-bit adder. That means we need to connect the wires behind this control panel so that it actually does arithmetic.
That means that it has these outputs:
- When X = 1 and Y = 1, then carry = 1 and sum = 0
- When X = 1 and Y = 0, then carry = 0 and sum = 1
- When X = 0 and Y = 1, then carry = 0 and sum = 1
- When X = 0 and Y = 0, then carry = 0 and sum = 0
Wiring the carry bulb was easy: we just used the Boolean “&” circuit, putting them in series.
Wiring the sum bulb was difficult, though, because we needed an exclusive or. But now we know how to do that. With X and Y in the place of P and Q, the XOR circuit we created will light the sum bulb correctly.
Of course, this is just the beginnings of a computer, but it’s as far as we are going to get in this book. If you’d like to keep going, just find a copy of the book Code by Charles Petzold.