Chapter 7. Circuits: Basic logic

We are working toward understanding how a computer works. At the most basic level, a computer is an electrical circuit. In this chapter, we'll examine a system that computer designers use for designing circuits, called a logic circuit.

A logic circuit consists of lines, representing wires, and peculiar shapes called logic gates. There are three types of logic gates:

The relationship of the symbols to their names can be difficult to remember. I find it handy to remember that the word AND contains a D, and this is what an AND gate looks like. We'll see how logic gates work in a moment.

Each wire carries a single information element, called a bit. A bit's value can be either 0 or 1. In electrical terms, you can think of zero volts representing 0 and five volts representing 1. (In practice, there are many systems for representing 0 and 1 with different voltage levels. For our purposes, the details of voltage are not important.) The word bit, incidentally, comes from Binary digIT; the term binary comes from the two (hence bi-) possible values.

Here is a diagram of one example logic circuit.

Figure 7.1: An example logic circuit.

We'll think of a bit travelling down a wire until it hits a gate. You can see that some wires intersect in a small, solid circle: This circle indicates that the wires are connected, and so values coming into the circle continue down all the wires connected to the circle. If two wires intersect with no circle, this means that one wire goes over the other, like an Interstate overpass, and a value on one wire has no influence on the other.

Figure 7.2: Logic gate behavior.

ao
01
10
abo
000
010
100
111
abo
000
011
101
111
(a) NOT gate (b) AND gate (c) OR gate

Suppose that we take our example circuit and send a 0 bit on the upper input (x) and a 1 bit on the lower input (y). Then these inputs would travel down the wires until they hit a gate.

To understand what happens when a value reaches a gate, we need to define how the three gate types work.

NOT gate
Takes a single bit and produces the opposite bit (Figure 7.2(a)). In our example circuit, since the upper NOT gate takes 0 as an input, it will produce 1 as an output.
AND gate
Takes two inputs and outputs 1 only if both the first input and the second input are 1 (Figure 7.2(b)). In our example circuit, since both inputs to the upper AND gate are 1, the AND gate will output a 1.
OR gate
Takes two inputs and outputs 1 if either the first input or the second input are 1 (or if both are 1). (Figure 7.2(c))

After the values filter through the gates based on the behaviors of Figure 7.2, the values in the circuit will be as follows.

Based on this diagram, we can see that when x is 0 and y is 1, the output out is 1.

By doing the same sort of propagation for other combinations of input values, we can build up a table of how this circuit works for different combinations of inputs. We would end up with the following results.

xyout
000
011
101
110

Such a table, representing what a circuit computes for each combination of possible inputs, is a truth table. The second row, which says that out is 1 if x is 0 and y is 1, corresponds to the propagation illustrated above.

7.1. Boolean algebra

In the previous section, we saw how logic circuits work. This is helpful when you want to understand the behavior of a circuit diagram. But computer designers face the opposite problem: Given a desired behavior, how can we build a circuit with that behavior? In this section, we look at a systematic technique for designing circuits. First, though, we'll take a necessary detour through the study of Boolean expressions.

Boolean algebra, a system of logic designed by George Boole in the middle of the nineteenth century, forms the foundation for modern computers. George Boole noticed that logical functions could be built from AND, OR, and NOT gates and that this observation leads one to be able to reason about logic in a mathematical system.

As Boole was working in the nineteenth century, of course, he wasn't thinking about logic circuits. He was examining the field of logic, created for thinking about the validity of philosophical arguments. Philosophers have thought about this subject since the time of Aristotle. Logicians formalized some common mistakes, such as the temptation to conclude that if A implies B, and if B holds, then A must hold also. (Brilliant people wear glasses, and I wear glasses, so I must be brilliant.)

As a mathematician, Boole sought a way to encode sentences like this into algebraic expressions, and he invented what we now call Boolean expressions. An example of a Boolean expression is y x + y x. A line over a variable (or a larger expression) represents a NOT; for example, the expression y corresponds to feeding y through a NOT gate. Multiplication (as with x y) represents AND. After all, Boole reasoned, the AND truth table (Figure 7.2(b)) is identical to a multiplication table over 0 and 1. Addition (as with x + y) represents OR. The OR truth table (Figure 7.2(c)) doesn't match an addition table over 0 and 1 exactly — although 1 plus 1 is 2, the result of 1 OR 1 is 1 — but, Boole decided, it's close enough to be a worthwhile analogy.

In Boolean expressions, we observe the regular order of operations: Multiplication (AND) comes before addition (OR). Thus, when we write y x + y x, we mean (y x) + (y x). We can use parentheses when this order of operations isn't what we want. For NOT, the bar over the expression indicates the extent of the expression to which it applies; thus, x + y represents NOT (x OR y), while x + y represents (NOT x) OR (NOT y).

A warning: Students new to Boolean expressions frequently try to abbreviate x y as x y — that is, they draw a single line over the whole expresion, rather than two separate lines over the two individual pieces. This abbreviation is wrong. The first, x y, translates to (NOT x) AND (NOT y) (that is, both x and y are 0), while x y translates to NOT (x AND y) (that is, x and y aren't both 1). We could draw a truth table comparing the results for these two expressions.

xy x y x y x y x y
0011101
0110001
1001001
1100010

Since the fifth column (x y) and the seventh column (x y) aren't identical, the two expressions aren't equivalent.

Every expression directly corresponds to a circuit and vice versa. To determine the expression corresponding to a logic circuit, we feed expressions through the circuit just as values propagate through it. Suppose we do this for our circuit of Figure 7.1.

The upper AND gate's inputs are y and x, and so it outputs y x. The lower AND gate outputs y x, and the OR gate combines these two into y x + yx.

7.2. Algebraic laws

Boole's system for writing down logical expressions is called an algebra because we can manipulate symbols using laws similar to those of algebra. For example, the commutative law applies to both OR and AND. To prove that OR is commutative (that is, that A + B = B + A), we can complete a truth table demonstrating that for each possible combination of A and B, the values of A + B and B + A are identical.

AB A + B B + A
0000
0111
1011
1111

Since the third and fourth columns match, we would conclude that A + B = B + A) is a universal law.

Since OR (and AND) are commutative, we can freely reorder terms without changing the meaning of the expression. The commutative law of OR would allow us to transform y x + y x into y x + y x, and the commutative law of AND (applied twice) allows us to transform y x + y x to x y + xy.

Similarly, both OR and AND have an associative law (that is, A + (B + C) = (A + B) + C). Because of this associativity, we won't bother writing parentheses across the same operator when we write Boolean expressions. In drawing circuits, we'll freely draw AND and OR gates that have several inputs. A 3-input AND gate would actually correspond to two 2-input AND gates when the circuit is actually wired. There are two possible ways to wire this.

Because of the associative law for AND, it doesn't matter which we choose.

Figure 7.3: A sampler of important Boolean identities

(Those in red don't correspond to standard algebraic identities.)
ANDOR
commutative A B = B A A + B = B + A
associative A (B C) = (A B) C A + (B + C) = (A + B) + C
identity A ⋅ 1 = A A + 0 = A
distributive A (B + C) = A B + A C A + B C = (A + B) (A + C)
one/zero A ⋅ 0 = 0 A + 1 = 1
idempotency A A = A A + A = A
inverse A A = 0 A + A = 1
DeMorgan's law A B = A + B A + B = A B
double negation

There are many such laws, summarized in Figure 7.3. This includes analogues to all of the important algebraic laws dealing with multiplication and addition. There are also many laws that don't hold with addition and multiplication; these are marked with an exclamation point in the table.

7.3. Converting a truth table

Now we can return to our problem: If we have a particular logical function we want to compute, how can we build a circuit to compute it? We'll begin with a description of the logical function as a truth table. Suppose we start with the following function for which we want a circuit.

xyzout
0000
0011
0101
0110
1000
1010
1101
1111

Given such a truth table defining a function, we'll build up a Boolean expression representing the function. For each row of the table where the desired output is 1, we describe it as the AND of several factors.

xyzoutdescription
0011x y z
0101x y z
1101x y z
1111x y z

To arrive at a row's description, we choose for each variable either that variable or its negation, depending on which of these is 1 in that row. Then we take the AND of these choices. For example, if we consider the first of the rows above, we consider that since x is 0 in this row, x is 1; since y is 0, y is 1; and z is 1. Thus, our description is the AND of these choices, x y z. This expression gives 1 for the combination of values on this row; but for other rows, its value is 0, since every other row is different in some variable, and that variable's contribution to the AND would yield 0.

Once we have the descriptions for all rows where the desired output is 1, we observe the following: The value of the desired circuit should be 1 if the inputs correspond to the first 1-row, the second 1-row, the third 1-row, or the fourth 1-row. Thus, we'll combine the expressions describing the rows with an OR:

x y z + x y z + x y z + x y z

Note that we do not include rows where the desired output is 0 — for these rows, we want none of the AND terms to yield 1, so that the OR of all terms gives 0.

This expression leads immediately to the circuit of Figure 7.4.

Figure 7.4: A circuit derived from a given truth table.

The final expression we get is called a sum of products expression. It is called this because it is the OR (a sum, if we understand OR to be like addition) of several ANDs (products, since AND corresponds to multiplication). We call this technique of building an expression from a truth table the sum of products technique.

In general, this technique allows us take any function over bits and build a circuit to compute that function. The existence of such a technique proves that circuits can compute any logical function.

Note, incidentally, that the depth of this circuit will always be three (or less), since every path from input to output will go through a NOT gate (maybe), an AND gate, and an OR gate. Thus, this technique shows that it's never necessary to design a circuit that is more than three gates deep. Sometimes, though, designers build deeper circuits because they are concerned not only with speed, but also with size: A larger circuit can often accomplish the same task using fewer gates.


To summarize: We have seen three ways of describing a Boolean function: logic circuits, truth tables, and Boolean expressions. Moreover, we have seen systematic ways to convert between the three techniques, diagrammed as arrows in Figure 7.5 below.

Figure 7.5: Known Boolean function conversions.

The only missing arrow is the conversion from truth tables to circuits; we can handle that, though, by converting the truth table to a Boolean expression (using the sum of products technique) and converting that into a circuit.