Getting Logical

IN THIS CHAPTER

check Learning about Boolean logic

check Examining the different types of logic gates

check Seeing how two or more gates can be used in combination

check Building logic circuits with only NAND or NOR gates

check Using software to simulate logic gate circuits

I grew up on Star Trek. Captain Kirk and his valiant crew sparked my imagination as they journeyed through the galaxy on their amazing adventures. So it’s only logical that I’m inclined to begin a chapter on logic with a reference to Mr. Spock. In fact, it would be illogical to begin this chapter in any other way.

In this chapter, I look at the basic principles of logic, which are the underpinnings of digital electronics. In particular, I explore logic gates, which are handy devices that perform a logical operation on two binary inputs and produce a single binary output result.

It’s incredible to realize that the overwhelming complexity of modern computer systems is built on the simple concept of logic gates. A modern computer processor consists of millions of individual logic gates connected in a way that enables the processor to perform complicated operations at amazing speed.

So back to Mr. Spock: My favorite Spock quote concerning logic is in an episode entitled “The Changeling.” At the very end of the episode, Spock congratulates Captain Kirk for getting the Enterprise crew out of a real bind by using sophisticated logic on a destruction-bent robot:

Spock: My congratulations, Captain. A dazzling bit of logic.
Kirk: You didn’t think I had it in me, did you, Spock?
Spock: No.

Well, Kirk did have it in him, and I think you have it in you, too. So let’s get started!

Introducing Boolean Logic and Logic Gates

In digital electronics, Boolean logic refers to the manipulation of binary values in which a 1 represents the concept of true and a 0 represents the concept of false. In electronic circuits that implement logic, binary values are represented by voltage levels. In the most common convention, a binary value of one is represented by images (also called HIGH ), and a binary zero is represented by 0 V (also called LOW).

This type of logic is called Boolean because it was invented in the nineteenth century by George Boole, an English mathematician and philosopher. In 1854, he published a book titled An Investigation of the Laws of Thought, which laid out the initial concepts that eventually came to be known as Boolean algebra, also called Boolean logic. Boolean logic is among the most important principles of modern computers. Thus, most people consider Boole to be the father of computer science.

As I mention at the start of this section, in Boolean logic, true is represented by the binary digit 1 and false by the binary digit 0. Logical operations (also called logical functions) are functions that can be applied to one or more logic inputs and produce a single logic output. One of the most common types of logic operations is NOT, which simply inverts the state of its input. In other words, with the NOT operation, if the input is true, the output is false; if the input is false, the output is true.

A gate is a circuit or device that implements a logical function. Thus, a NOT gate is a circuit or device that implements the logical NOT operation. NOT gates are very common in digital circuits.

You can create gate switches in a variety of ways. The most common method uses transistors as switches, arranged in such a way that the correct output is generated based on the logical inputs and the type of gate being implemented. In Chapter 3 , you see how gates are implemented. For the rest of this chapter, I discuss what the various types of gates do and how they can be combined in real-world circuits.

Regardless of the method used to create gate circuits, all logic circuits depend on different voltage ranges to represent 1 and 0. As I’ve already mentioned, the most common voltage convention is to represent 1 by approximately images and 0 by approximately 0 V. The images signal is usually referred to as HIGH, and the 0 V signal is usually called simply LOW.

In the rest of this chapter, I look at seven of the most common types of logic gates: NOT, AND, OR, NAND, NOR, XOR, and NXOR. All these gates except NOT use at least two inputs; the NOT gate has just one input. To help you get your bearings, Table 2-1 provides a brief overview of the distinctions among the gate types:

TABLE 2-1 The Most Common Types of Logic Gates

Gate	Description
NOT	Inverts the input (HIGH becomes LOW, LOW becomes HIGH)
AND	Outputs HIGH if all the inputs are HIGH; otherwise, outputs LOW
OR	Outputs HIGH if at least one of the inputs is HIGH; otherwise, outputs LOW
NAND	Outputs HIGH if all the inputs are LOW; otherwise, outputs LOW
NOR	Outputs HIGH if at least one of the inputs is LOW; otherwise, outputs LOW
XOR	Outputs HIGH if one, and only one, of the inputs is HIGH; otherwise, outputs LOW
NXOR	Outputs HIGH if one, and only one, of the inputs is LOW; otherwise, outputs LOW

Looking at NOT Gates

The simplest of all gates is the NOT gate, which is also called an inverter. A NOT gate has just one input, and its output is the opposite of the input. If the input is LOW, the output is HIGH. If the input is HIGH, the output is LOW.

Table 2-2 shows the truth table of an inverter. A truth table is simply a table that lists every possible combination of input values and shows the resulting output for each combination. For an inverter, the truth table is simple. Because only one input exists, only two possibilities exist: The input is LOW, or it is HIGH. As you can see in the table, the output is simply the opposite of the input.

TABLE 2-2 The Truth Table for an Inverter

Input	Output
0	1
1	0

Note that in truth tables, it’s common to use 0s and 1s to represent logic values rather than the terms HIGH and LOW.

Figure 2-1 shows the standard logic symbol for a NOT gate. Symbols such as this are often used in schematic diagrams for circuits that use gates. The NOT symbol is simply a triangle with the input at one end and the output at the other. The small circle on the output is called a negation bubble, which indicates that the output is inverted.

Looking at AND Gates

A two-input AND gate is a gate that has two inputs and one output. The output is HIGH only if both of the inputs are HIGH. Any other combination of inputs results in the output’s being LOW. Table 2-3 shows the truth table for an AND gate with two inputs.

TABLE 2-3 The Truth Table for a Two-Input AND Gate

Input A	Input B	Output
0	0	0
0	1	0
1	0	0
1	1	1

The standard symbol for an AND gate is shown in Figure 2-2 . The inputs are on the left, and the output is on the right.

FIGURE 2-2: The symbol for a two-input AND gate.

Note that you can create AND gates with more than two inputs. For each additional input that you add to a gate, the number of possible input combinations doubles. A two-input gate has four possible input combinations; for a three-input gate, there are eight possible combinations; a four-input gate has 16 possible input combinations, and so on.

Table 2-4 shows the truth table for a three-input AND gate. As you can see, the output is HIGH only if all the inputs are HIGH. Any other combination of inputs produces LOW output.

TABLE 2-4 The Truth Table for a Three-Input AND Gate

Input A	Input B	Input C	Output
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

You can combine gates in a circuit to create logic networks that are more complicated than a single gate could produce. For example, you can create a three-input AND gate by using two two-input AND gates as shown in Figure 2-3 . In that figure, the first AND gate produces a HIGH output only if the inputs A and B are true. Then the output of the first AND gate is used as one of the inputs to the second AND gate; the other input is the input C.

FIGURE 2-3: A pair of two-input AND gates can be used to create a logic network that operates like a three-input AND gate.

Because the output of the second gate will be HIGH only if both of its inputs are HIGH, and because the first input to the second gate is the output from the first gate, which is HIGH only if both of its inputs are HIGH, the output of the entire circuit (designated as X) is HIGH only if all three inputs (A, B, and C) are HIGH.

If you want to, you can think of an AND gate as being a form of multiplication. To understand why, first consider that when you multiply any quantity of single-bit binary numbers, only two possible results exist: zero or one. Look back at the truth tables in Table 2-3 and Table 2-4 , and try multiplying the binary inputs in each row. In each case, the answer will be zero for any combination that contains a zero in any of the inputs. The answer will be 1 only if all the inputs are 1.

The following paragraphs describe just two of the many situations in which you might use an AND gate in a real-life electronic circuit:

Figure 2-4 shows how AND gates might be used in a home alarm system. Here, the inputs for the various sensors placed on the home’s doors and windows are processed by the sensor circuit, which sends a HIGH signal to one of the inputs of the AND gate if any of the sensors indicates an intrusion anywhere in the house. Then the arming circuit sends a 1 to the other input of the AND gate if the system is armed. Finally, the alarm circuit sounds an audible alarm if the AND gate’s output is 1. As a result, the alarm will sound if an intrusion is detected and the system is armed.

When used in this way, an AND gate is often called an enable input, as one of the inputs to the AND gate enables the other input to be processed. When the enable input is HIGH, the controlled input is allowed to pass through the AND gate. When the enable is LOW, the controlled input is inhibited.

Figure 2-5 shows a more developed version of the home alarm system that uses an enable input. In this version, the alarm doesn’t sound immediately when an intrusion is detected. Instead, the alarm sounds 30 seconds after it is triggered. This gives you time to disable the alarm before waking up the neighbors. When the sensor circuit detects an intrusion, it sends a trigger pulse to a 555 timer circuit, which then generates a 30-second HIGH pulse. The HIGH signal from the 555 timer output is routed through a NOT gate, which inverts the signal to LOW. The LOW signal is sent to one of the inputs to the second AND gate. The other input to the second AND gate is the output of the first AND gate, which indicates that an intrusion has been detected, and the system is armed.

For the first 30 seconds after the intrusion is detected, the first input to the second AND gate is LOW, and the second input is HIGH, so the output from the second AND gate is LOW. Thus, the alarm doesn’t sound. In effect, the timer output inhibits the alarm from sounding. But when the output from the 555 timer circuit goes LOW after the 30-second pulse ends, the NOT gate inverts the signal, sending a HIGH output to the second AND gate. This situation causes the second AND gate’s output to go HIGH, so the alarm sounds. Thus, the inverted pulse from the timer circuit enables the alarm circuit.

FIGURE 2-4: An AND gate used in a home alarm system.

FIGURE 2-5: An AND gate used as an enable input.

Looking at OR Gates

An OR gate produces a HIGH output if any of the inputs is HIGH. The output from an OR gate is LOW only if all the inputs are LOW. Table 2-5 shows the truth table for a two-input OR gate.

TABLE 2-5 The Truth Table for a Two-Input OR Gate

Input A	Input B	Output
0	0	0
0	1	1
1	0	1
1	1	1

It’s important to note that in an OR gate, it doesn’t matter how many of the inputs are HIGH. If at least one input is HIGH, the output will be HIGH. Thus, in a two-input OR gate, the output will be HIGH if either input is HIGH or both inputs are HIGH. In a three-input OR gate, the output will be HIGH if any one, any two, or all three of the inputs are HIGH.

The standard symbol for an OR gate is shown in Figure 2-6 . The inputs are on the left, and the output is on the right.

FIGURE 2-6: The symbol for a two-input OR gate.

Like AND gates, OR gates with more than two inputs are easy to create. No matter how many inputs the OR gate has, the output is HIGH if any of the inputs is HIGH.

Multiple-input OR gates are easy to create by combining two input OR gates. Figure 2-7 shows a logic network with three OR gates, effectively acting like a four-input OR gate: If any of the four inputs is HIGH, the output will be HIGH.

FIGURE 2-7: Three OR gates used to create a four-input OR gate.

You can combine 2-Input OR gates in a circuit to create OR networks that have more than two inputs. For example, Figure 2-8 shows how OR gates might be used in the sensor circuit of a home alarm system that has more than two inputs. In this circuit, eight separate alarm sensors are fed into a network of OR gates. If any one of the inputs is HIGH, the output from the sensor circuit is HIGH.

FIGURE 2-8: OR gates used in a sensor circuit.

The sensor circuit uses seven OR gates to create an eight-input OR gate. Study the way that the OR gates are arranged in this network for a few moments to make sure you understand how it works. Each of the eight inputs is routed to one of the four OR gates in the first tier of gates. These four OR gates reduce the eight inputs to four outputs, which are then sent to the two OR gates in the second tier. These two OR gates reduce their four inputs to two outputs, which are sent to the final OR gate. Then the output of the last OR gate becomes the output of the entire sensor circuit.

Looking at NAND Gates

A NAND gate is a combination of an AND gate and a NOT gate. In fact, the name NAND is a contraction of NOT and AND. As you can see in Table 2-6 , the output of a NAND gate is LOW when both of the inputs are HIGH. Otherwise, the output of the NAND gate is HIGH.

TABLE 2-6 The Truth Table for a Two-Input NAND Gate

Input A	Input B	Output
0	0	1
0	1	1
1	0	1
1	1	0

The standard symbol for a NAND gate is shown in Figure 2-9 . This symbol is the same as the symbol for an AND gate, with the addition of a circle at the output. As in the symbol for a NOT gate, the circle indicates that the output is inverted. In other words, a NAND gate is an AND gate whose output is inverted.

FIGURE 2-9: The symbol for a two-input NAND gate.

The NAND gate is special because you can use various combinations of NAND gates to create AND, OR, or NOT gates. Thus, a logic network that consists of a combination of NOT, AND, and OR gates can be created with an equivalent combination of just NAND gates. For this reason, the NAND gate is called a universal gate. You learn more about this characteristic of NAND gates in “Universal NAND Gates,” later in this chapter.

Another interesting thing about the NAND gate is that it can be used as a kind of OR gate that tests for LOW inputs instead of HIGH inputs. In other words, the output of a NAND gate is HIGH whenever either of the inputs are LOW.

This characteristic of NAND gates is useful in many situations. For example, consider the alarm sensor circuit that was presented in the previous section and in Figure 2-8 . Suppose all the alarm sensors produce a HIGH signal when there is no intrusion, then go LOW when there is an intrusion. In the real world, many alarm sensors work exactly in this way. For example, a sensor that detects whether a door is open is essentially a simple switch that is closed when the door is closed and open when the door is open. When the door is closed, current flows through the switch so the signal from the sensor is HIGH. When the door is opened, current stops flowing and the signal from the sensor goes LOW.

Figure 2-10 shows how NAND gates can be used to test for a LOW input on any of eight sensors. This circuit is identical to the circuit that was shown in Figure 2-8 , except that all the OR gates have been replaced by NAND gates.

FIGURE 2-10: NAND gates used in a sensor circuit.

Looking at NOR Gates

A NOR gate is a combination of an OR gate and a NOT gate. As with NAND, the name NOR is a contraction of NOT and OR. The truth table for a NOR gate is shown in Table 2-7 . As you can see, the output of a NOR gate is LOW when any of its input are HIGH. Otherwise, the output of the NAND gate is HIGH.

TABLE 2-7 The Truth Table for a Two-Input NOR Gate

Input A	Input B	Output
0	0	1
0	1	0
1	0	0
1	1	0

As you can see in Figure 2-11 , the standard symbol for a NOR gate is the same as the symbol for an OR gate, with a negation circle added to the output. The circle simply indicates that the output is inverted. A NOR gate is essentially a combination of an OR gate and a NOT gate

FIGURE 2-11: The symbol for a two-input NOR gate.

Like the NAND gate, the NOR gate is a universal gate. Any logic network that consists of NOT, AND, and OR gates can be recreated with just NOR gates. For more information, see the section “All You Need Is NAND (or NOR). ”

Just as a NAND gate is like an OR gate for LOW inputs, a NOR gate is like an AND gate for LOW inputs. In other words, the output of a NAND gate is HIGH when both of the inputs are LOW.

Figure 2-5 , earlier in this chapter, shows an alarm circuit that sounds an alarm 30 seconds after an input sensor detects an intrusion. In that circuit, the output pulse from a 555 timer circuit is inverted by a NOT gate and then sent to an AND gate, which sends a HIGH output to an audible alarm circuit when the output from a sensor circuit is HIGH and when the 30-second timer pulse ends.

Figure 2-12 shows a version of the same circuit that uses a NOR gate instead of an AND gate to feed the audible alarm circuit. In this circuit, the alarm sounds when the output from the sensor circuit is LOW and the output from the timer circuit is also LOW. A NOT gate isn’t needed for the 555 timer output, but now a NOT gate is required on the output from the AND gate to invert its signal, so that it emits LOW when the system is armed and the alarm is tripped.

FIGURE 2-12: Using a NOR gate in a sensor circuit.

Looking at XOR and XNOR Gates

I have but two gate types remaining for your approval in this chapter: XOR, which stands for Exclusive OR, and XNOR, which stands for Exclusive NOR.

In an XOR gate, the output is HIGH if one, and only one, of the inputs is HIGH. If both inputs are LOW or both are LOW, the output is LOW. The truth table for an XOR gate is shown in Table 2-8 .

TABLE 2-8 The Truth Table for a Two-Input XOR Gate

Input A	Input B	Output
0	0	0
0	1	1
1	0	1
1	1	0

Another way to explain an XOR gate is as follows: The output is HIGH if the inputs are different; if the inputs are the same, the output is LOW.

The XOR gate has a lesser-known cousin called the XNOR gate. An XNOR gate is an XOR gate whose output is inverted. Table 2-9 lists the truth table for an XNOR gate.

TABLE 2-9 The Truth Table for a Two-Input XNOR Gate

Input A	Input B	Output
0	0	1
0	1	0
1	0	0
1	1	1

Figure 2-13 shows the symbols used for both XOR and XNOR gates. As you can see, the only difference between these two symbols is that the XNOR has a circle on its output to indicate that the output is inverted.

FIGURE 2-13: The symbols for two-input XOR and XNOR gates.

One of the most common uses for XOR gates is to add two binary numbers. For this operation to work, the XOR gate must be used in combination with an AND gate, as shown in Figure 2-14 .

FIGURE 2-14: An XOR gate and an AND gate can be used to add two binary numbers.

To understand how the circuit shown in Figure 2-14 works, review how binary addition works:

If you wanted, you could write the results of each of the preceding addition statements by using two binary digits, like this:

When results are written with two binary digits, as in this example, you can easily see how to use an XOR and an AND circuit in combination to perform binary addition. If you consider just the first binary digit of each result, you’ll notice that it looks just like the truth table for an AND circuit and that the second digit of each result looks just like the truth table for an XOR gate.

The adder circuit shown in Figure 2-14 has two outputs. The first is called the Sum, and the second is called the Carry. The Carry output is important when several adders are used together to add binary numbers that are longer than 1 bit.

De Marvelous De Morgan’s Theorem

It’s time for a theorem! Although I present some pretty sophisticated logic concepts in this chapter, I’ve avoided mentioning any that go by the name theorem — until now, anyway.

De Morgan’s Theorem was created by Augustus De Morgan, a nineteenth-century British mathematician who developed many of the concepts that make Boolean logic work. Among De Morgan’s most important work are two related theorems that have to do with how NOT gates are used in conjunction with AND and OR gates:

An AND gate with inverted output behaves the same as an OR gate with inverted inputs.
An OR gate with inverted output behaves the same as an AND gate with inverted inputs.

An AND gate with inverted output is also called a NAND gate, of course, and an OR gate with inverted output is also called a NOR gate. Thus, De Morgan’s laws can also be stated like this:

A NAND gate behaves the same as an OR gate with inverted inputs.
A NOR gate behaves the same as an AND gate with inverted inputs.

An OR gate with inverted inputs is called a negative OR gate, and an AND gate with inverted inputs is called a negative AND gate.

In case you’re not persuaded, review for a moment the truth table for a NAND gate:

A	B	X
0	0	1
0	1	1
1	0	1
1	1	0

Now look at the truth table for an OR gate, with an extra set of columns added to show the inverted inputs:

A	B	NOT A	NOT B	X
0	0	1	1	1
0	1	1	0	1
1	0	0	1	1
1	1	0	0	0

Here, the A and B columns represent the inputs. The NOT A and NOT B columns are the inputs after they’ve been inverted. Finally, the X column represents an OR operation applied to the NOT A and NOT B values.

As you can see, the final output column of these truth tables is the same. Thus, a NAND gate is equivalent to a negative OR gate. Any time you see a NAND gate in a circuit diagram, you can substitute a negative OR gate.

Now take a look at the other side of De Morgan’s Theorem. Here’s a truth table for a NOR gate:

A	B	X
0	0	1
0	1	0
1	0	0
1	1	0

And here’s the output of a negative AND gate:

A	B	NOT A	NOT B	X
0	0	1	1	1
0	1	1	0	0
1	0	0	1	0
1	1	0	0	0

Again, you can see that these two truth tables give the same output.

Just as a circle is used on the output of a NAND or NOR gate to indicate that the output is inverted, you can use a circle on the inputs to an OR or AND gate to indicate that the inputs are inverted. Figure 2-15 shows these symbols. The figure also shows that the negative OR and AND gates are interchangeable with the NAND and NOR gates.

FIGURE 2-15: NAND and NOR gates are equivalent to negative OR and negative AND gates.

All You Need Is NAND (Or NOR)

In “Looking at NAND Gates ” and “Looking at NOR Gates ,” earlier in this chapter, I mention that the NAND gate is a universal gate because any other type of gate (such as AND, OR, XOR, and NXOR) can be constructed solely from combinations of NAND gates.

This fact is incredibly useful because it enables you to build any logic circuit, simple or complex, by using just NAND gates. When you begin to build your own digital circuits, you can stock up on integrated circuits that contain just NAND gates and be assured that you can build even the most complex circuits with your stock of NAND gates.

In “Looking at NOR Gates ,” I also mention that the NOR gate is a universal gate. Thus, you can also build any logic circuit by using nothing but NOR gates.

In the following sections, I first explain how you can use NAND gates to build other types of gates; then I show you how to do the same thing with NOR gates.

Universal NAND gates

Figure 2-16 shows how you can use NAND gates in various combinations to create NOT, AND, OR, and NOR gates. The following paragraphs describe how the circuits work:

NOT: You can create a NOT gate from a NAND gate simply by tying the two inputs of the NAND gate together. Because the two inputs of the NAND gate are tied together, only two input combinations are possible: both HIGH or both LOW. If both inputs are HIGH, the NAND gate will output a LOW. If both inputs are LOW, the NAND gate will output HIGH. Thus, the circuit behaves exactly as a NOT gate would.
AND: You can create an AND gate by using two NAND gates. The first NAND gate does what NAND gates do: returns LOW if both inputs are HIGH and returns HIGH if both inputs are anything else. Then the second NAND gate is configured as a NOT gate to invert the output from the first NAND gate.

One of the basic rules of NOT gates is that if you invert a signal twice, you end up with the same signal. If the original input is HIGH, and you invert it, the signal becomes LOW. Invert the input again, and it returns to HIGH. With this rule in mind, you should be able to see how the two NAND gates work together to create an AND gate.
OR: You need three NAND gates to create an OR gate. First, you use a pair of NAND gates configured as NOT gates to invert the two inputs. Then the third NAND gate produces a LOW output if both of the original inputs are LOW. If one of the original inputs is HIGH, or if both of the original inputs are HIGH, the output of the third gate is HIGH.
NOR: It takes four NAND gates to create a NOR gate. As you can see in Figure 2-16 , this circuit is the same as the OR gate circuit, with the addition of another NOT gate to invert the output from the third NAND gate. Inverting the output changes the overall function of the circuit from OR to NOR.

FIGURE 2-16: Creating NOT, AND, OR, and NOR gates by using nothing but NAND gates.

Universal NOR gates

Like NAND, NOR is a universal gate. Figure 2-17 shows how NOR gates can be combined in various and sundry ways to create NOT, AND, OR, and NAND gates.

FIGURE 2-17: Creating NOT, OR, AND, and NAND gates by using nothing but NOR gates.

The following paragraphs describe how the circuits work:

NOT: Creating a NOT gate from a NOR gate is the same as creating a NOT gate from a NAND gate: You simply tie the two inputs of the NOR gate together. If both inputs are LOW, the NOR gate will output a HIGH. Otherwise, the output is LOW.
OR: You need two NOR gates to create an OR gate. The first NOR gate returns LOW if either input is HIGH or both inputs are HIGH. Then the second NOR gate is configured as a NOT gate to invert the output of the first NOR gate.
AND: You need three NOR gates to create an AND gate. The first two are configured as NOT gates, so they invert the inputs. Then the third NOR gate produces a HIGH output if both of the original inputs are HIGH.
NAND: It takes four NOR gates to create a NAND gate. The first three NOR gates are configured just as they are for an AND gate. Then a fourth NOR gate configured as a NOT gate inverts output from the third NOR gate.