Digital Logic Gates

CSC 105 - The Digital Age - Weinman

We discuss the basics of electronic digital logic, the foundation of computing hardware.


Up to this point we have been thinking about the logical building blocks of computation: bits. You've learned how to represent integers, fractions, and images using zeros and ones, as well as how to add bits that represent positive and negative numbers. So why do we bother with these digital bits and not the customary decimal digits? The main reason is that building computers to use bits is much easier. While early computers were mechanical, representing their computations and information (switch states) via the physical configuration of gears and the like, today's computation uses electricity to represent state and electrical properties to control the flow of algorithms. How? Let's start from the bottom and work our way up.
In common terminology, a circuit is a closed path or loop where the end point is the same as the start point. Electricity flows along or around a set of wires much like walkers along a circuit path. Transistors are essentially electrical switches that route electricity through a set of wires, in the same way that railroad switches route the flow of trains along tracks. An electrical voltage applied to one pair of wires can change the voltage on another pair of wires. It turns out these transistors are the most basic elements of electronic circuits. However, assembling transistors into useful circuits was extraordinarily sensitive, complicated, and expensive. Robert Noyce, whom our building is named for, is credited with inventing the so-called "integrated circuit," which allowed his company to mass-produce pre-packaged transistors into more complicated circuits. This development help give rise to the electronic "digital age."
In digital computers, a wire at any point along a circuit carries "high" voltage (typically around five volts, 5V) or a "low" voltage (around zero volts, 0V). These two states of the wire are considered mutually exclusive and can be thought of as "on" (5V) and "off" (0V) or more abstractly "true" and "false." We might even think of them as our familiar digital bits 0 and 1.
These two states form the foundation of Boolean logic, a useful system of reasoning about things that have just two states, typically referred to as true and false. This logic is named for George Boole (1815-1864), the British mathematician and logician who described it. As you might guess, this logic forms the foundation of digital circuitry. In the discussion that follows, we will be talking about electricity on wires and this binary (two-stated) logic interchangeably.

Logic Gates

Imagine an input wire, which we'll call x, that can take on two states. For shorthand, we call the false state 0 and the true state 1. What can we do with these values? If they represent our familiar bits, we might want to figure out how to encode in electricity the rules we've been using to add two bits together. In this reading and the subsequent class period, we'll put together the building blocks for this process.

Boolean Negation

What can we do with a single wire whose value is represented by x? Not a whole lot, but we can do one thing: "negate" the value of x. This process of logical negation means giving something its opposite value. If something is NOT false, what must it be? We only have two possible states, so if it's NOT false it must be true. Similarly, if something is NOT true, it must therefore be false. (Pause here before going on and make sure you understand perfectly those last two sentences.)
If that "something" is x, we are talking about the value of NOT x. We might represent this in the following table where the left hand column shows the input, which we've labeled x, and the right column shows its logical negation, which we've titled NOT x.
xNOT x
Quite simply, the NOT operator "flips the bit."
How could we draw a diagram of an electronic circuit? The convention is to indicate electrical wires (that carry a voltage) as lines. What if we want to flip the voltage along the wire from high to low (true to false, 0 to 1, etc.) or low to high? We need a symbol that indicates this NOT operation. The symbol is called a NOT "gate". For instance, in the diagram below, the current flows from left to right along the wire, and the triangle next to the circle indicates a NOT gate. The input wire to this gate is labeled x, and the output wire is NOT x after it has gone through the NOT gate.
Circuit:xlogic-gates-NOT.pngNOT x
Meaning: inputNOT Gateoutput

Boolean AND

If we have two input values (wires) to think about, things can get a lot more interesting. Let's call these two input values x1 and x2. It might be useful to have a circuit indicates when both of these values are true (high, 1, etc.). Thus, we'd have two input wires to a gate, and one output wire. This output wire would only be true when both of its inputs were true. Using a table much like we had for the NOT gate, we can specify the output of the gate for every possible input. As it turns out, the name of this gate is the rather intuitive AND gate, because the output is only true when x1 AND x2 are true. Thus, the only 1 in the table is in the bottom row, where both x1=1 and x2=1.
x1x2x1 AND x2
As you might guess, this operator is also useful to represent in an electronic circuit. The so-called AND gate is shown below.
Like the NOT gate, it is read from left to right, with the two input wires x1 and x2 on the left and the output wire, representing the value x1 AND x2 on the right.

Boolean OR

In English, the word "or" can be somewhat ambiguous. Consider the following two common phrases:
The first usage of the English "or" means "either one or both," while the second usage means "which one, exclusively." Of course, context helps us disambiguate these. That's not a useful strategy for a circuit, so in Boolean logic, we specify that an OR has the first meaning.
In addition to being able to combine two wires with an AND gate, we might want to reason about whether either one of the two inputs x1 and x2 were 1 (true, high, etc.) Thus, the only case for which the OR operator is false is when both inputs are false. In the other three possible cases, at least one of the inputs is true, meaning the output is true. We indicate this with a similar table for the Boolean OR operator.
x1x2x1 OR x2
The OR operator has a gate representation as well. The OR gate represented below is read from left to right with the two input wires on the left and the output wire on the right.

Digital Circuits

The three logic gates above give us the foundations for electronic digital circuits, which are at the heart of today's computers. We can combine and connect these gates to build bigger and more interesting circuits. For instance, the circuit below is represented with three input wires, x1, x2, and x3. We connect an AND gate, using its output as the input to an OR gate.
The result gives us a circuit whose output wire is the Boolean function (x1 AND x2) OR x3.
Perhaps this circuit represents your function for determining whether to come to class. Say x1 represents whether there is a homework assignment due today, x2 represents whether you've completed it, and x3 represents whether we are doing a lab exercise. Thus, one condition for your coming to class would be homework is due AND you've completed it. Another condition is we are doing a lab. If one OR the other is true, you'd come to class.
Of course, I don't recommend using this circuit in your decision-making process, because you'll miss out on the fact that in class we'll see how to use these gates to build circuits that represent the other form of the English "or", how to "remember" a value, and how to add two bits together, including representing the carry.


Adapted from materials by Marge Coahran. Used by permission.

Copyright © 2011 Jerod Weinman.
cc-by-nc-sa.png This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.