1 of 2

9.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:

Control panel with lights for P, ~P, P&Q and PvQ. Switches for P and Q.

“Just what I wanted!” your friend tells you.

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:

Control panel with lights for P, ~P, P&Q and PvQ. Switch for P is on and Q is off.

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.

Bit: a binary digit of information.

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 we will learn is how to build a 1-bit adder.

The beginnings of computation: we use Boolean logic 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:

Control panel with lights for X+Y=Z. Switches for X and Y.

Since this is a 1-bit 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:

Numerical truth table for X, Y where the complex answer is binary addition: 10 on top row, 01, 01 and 00 on last row.

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.

Sum = ones’-place output
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 its own truth function. So here is our plan for our 1-bit adder:

Numerical truth table with carry (1000) and sum (0110) as separate columns.

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:

Control panel with X and Y inputs, carry and sum as separate light bulb outputs.

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!

Carry = Conjunction
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 two of them below.

As you can see, one way to create XOR from Boolean operations is 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:

Circuit showing PvQ with branches for P, ~P, Q and ~Q.

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 are 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:

Circuit with electromagnet, open.

Now, all we have to do is run electric current through the wire, and the iron becomes a magnet:

Circuit with electromagnet, closed.

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:

Open circuit with electromagnet controlling a gate above it.

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.)

Closed circuit with electromagnet controlling a gate above it.

We could even put a light bulb on the circuit with this second gate.

Circuit with electromagnet controlling a gate above it, all using same battery.

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 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.

Circuit with electromagnet controlling a gate above it and now showing wires running to ground.

Triangles will always represent completion of the circuit, without the mess of  the extra wires.

We also don’t need to connect the various circuits to the same battery, so we can diagram it like this:

Circuit with electromagnet controlling a gate above it not showing wires to ground and using separate batteries.

In the end we’ll just connect them all to the power source for our machine, like when you plug in your computer.

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.

Two electromagnets in series: S&T.

First, let’s just look at what two electromagnets in series looks like. Say we have two gates, S and T.

Open gates S and T in series, both using electromagnets.

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.

Open gate S and closed gate T in series, both using electromagnets.

But if we close both S and T, then the light goes on.

Closed gates S and T in series, both using electromagnets. Light 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.

P gate with negation and P running to different light bulbs.

Now what we need to do is put the ~P line with the bulb in series with a gate for Q.

P and Q gates with electromagnets. ~P and Q in series.

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.

P and Q gates with electromagnets. ~P and Q in series. Q now closed. Light on.

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.

P and Q gates with electromagnets. ~P and Q in series. P true gate also running to same light bulb.

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.

P and Q gates with electromagnets. ~P and Q in series. P true gate also running to same light bulb. P true and light on.

We are almost done, because now we just have to put an electromagnet for ~Q in series with the line coming from P.

If there is no dot at an intersection, that means the wires do not actually intersect.

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.

P and Q gates with electromagnets. ~P and Q in series. P true gate also running in series with ~Q to same light bulb. P and Q both true. Light off.

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.

P and Q gates with electromagnets. ~P and Q in series. P true gate also running in series with ~Q to same light bulb. P true and Q false. Light 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.

Control panel with X, Y in puts and carry and sum outputs.

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.

You’ve created a machine that can process one bit of information!

This is just the beginning for computers, 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.