Understanding Logic Gates

Inside your computer are billions of units called transistors. These transistors serve a variety of purposes, but they commonly act as a sort of very small light switch. Each switch can be turned on or turned off. Computer scientists will often represent a switch that's turned on with the number 1, and a switch that's turned off with the number 0. These zeros and ones form a number system called binary, and it's the language of computers. From just these zeros and ones, we end up with computers that can perform calculations, create documents, view images, browse the web, and more. How does that happen? In this series, we'll explore the foundations of computer logic, starting from the fundamentals, and building our way to more and more sophisticated systems. Using these switches, our computers can store information. Each switch stores a single bit of information, a 0 or a 1. But computers don't just store information, they process it, transforming inputs into outputs. That's where logic gates come in. Logic gates are the building blocks of computer circuits. They accept input, and produce output according to a set of logical rules. One of the simplest logic gates is the NOT gate, represented graphically here. The NOT gate takes a single input, either a 0 or a 1, and inverts it, so that the output is the opposite of whatever the input is. If the input is a 1, then the NOT gate outputs a 0. If the input is a 0, then the NOT gate outputs a 1. To represent the logical rule this gate obeys, we can draw a truth table, which is just a way of writing down the rules for some logical formula. This table says that if the input is 0, then the output is 1, and if the input is 1, the output is 0. Often though, our computers need to be able to perform calculations not just on a single bit of information, but on multiple bits of information. The AND gate, shown here for example, is a logic gate that takes two inputs instead of one. Let's call these two inputs A and B. As the name might suggest, the AND gate will output a 1 when both A and B are 1s, but in all other cases, AND will output a 0. We can construct a truth table here too. This truth table is a bit bigger, since with two inputs there are more possibilities to consider. If A and B are 0, the output is 0. If A is 0 and B is 1, the output is 0. If A is 1 and B is 0, the output is still 0, and only when both A and B are 1s is the output a 1. The OR gate, meanwhile, is also a logic gate that takes two inputs. This gate outputs a 1 when A is a 1, or when B is a 1. So if both inputs are 0, the OR gate outputs a 0. But if either of the inputs is a 1, or both inputs are a 1, then the output of the OR gate is also going to be a 1. These logic gates on their own follow fairly simple rules, but they can combine with each other to form more complex calculations. Imagine what would happen if, for example, we took two inputs, passed them into an AND gate, and then passed that output into a NOT gate. What would happen? If both inputs are 0, the AND gate will output a 0, and the NOT will turn that 0 into a 1. If only one of the inputs is a 0, nothing changes. But if both inputs are 1, the AND gate will output a 1, and the NOT will turn that 1 into a 0. In other words, this circuit appears to do the opposite of whatever the AND gate on its own would do. It turns out that inverting the result of an AND calculation is such a common operation that it has its own logic gate, the NAND gate. This gate is equivalent to an AND followed by a NOT. So if the AND truth table looks like this, then the NAND truth table is identical, except all of the outputs are inverted. Whenever AND would output a 0, NAND outputs a 1. Whenever AND would output a 1, NAND outputs a 0. As you might guess, if there's a logic gate to take the opposite of an AND gate, there's also a logic gate that takes the opposite of an OR gate. This is the NOR gate. When both inputs are 0, OR would normally output a 0 too, so the NOR gate will flip that and output a 1. In all other cases, at least one of the inputs is 1, so OR would output a 1, and so the NOR gate will output a 0 instead. Let's now use these gates to solve a sample problem. Given two inputs A and B, we'd like to calculate whether exactly one of them is a 1. Well, what does it mean logically for exactly one of these two inputs to be a 1? Well, it means that either A or B must be a 1, but it also means they can't both be a 1. So logically, we might represent this as A OR B, and NOT A AND B, to mean that one of the two must be a 1, but both can't be a 1. We could create a circuit to perform this calculation too, but this circuit is starting to look fairly complex. So once again, there's a logic gate to solve this problem precisely. The exclusive OR gate outputs a 1 when exactly one of its inputs is a 1. So if only A is 1, or only B is 1, then the output of exclusive OR is 1. But otherwise, if both inputs have the same value, both 0s or both 1s, then the output is 0. And just for completeness sake, there's also a gate for inverting the exclusive OR gate, the exclusive NOR gate. This gate does the opposite of what exclusive OR does. Well, exclusive OR will output a 1 when the two inputs are different from each other. Exclusive NOR will output a 1 when the two inputs are the same, both 0s or both 1s. These logical gates, NOT, AND, OR, NAND, NOR, exclusive OR, and exclusive NOR, make up the foundation of computation in computers. By combining just these few logical gates, each of which obeys a relatively simple logical rule, we can construct computers that can represent all of the data, and perform all of the complex calculations that our computers do every day.