Digital Logic Gates
Before there were physical logic gates, there was the math. In 1847, English mathematician George Boole published The Mathematical Analysis of Logic.
He invented Boolean Algebra- a system where logical propositions could be evaluated using only two states: True (1) and False (0). He formally defined the fundamental logical operations, AND, OR, XOR (eXclusive OR) and NOT, but using other names. Each performs some operation based on the 1/0 state of its inputs.
By wiring copies of these four basic gate types, we can construct any digital computing device. The four gates are:
A and B are the inputs, either 1 or 0 for either. C is the output.
Importantly, all digital gates are internally built from combinations of on/off switches.
By definition;
-
AND: A and B must both be 1 for C=1
-
OR: A or B must be 1 for C=1
-
XOR: Output C= 1 only when its two inputs are different. So, C=0 when A=B.
-
INV: The output is the inversion of the input. 1 becomes 0 , 0 becomes 1
Experiment with the Digital Logic Evaluator below to see how each gate works. Keep in mind that all computer hardware operations are made from these gate types or logically equivalent circuits.
The power of the inverter
Augustus De Morgan, a 19th-century British mathematician proved (De Morgan’s Law) that NAND (AND with Inverter on output) gates alone can build any logic circuit. The same holds true for a NOR (OR with Inverter on output).
This means that the four basic gates above can each be made using some wired combo of NANDs only (or NORs only). For example, here is the equivalent of a standalone XOR gate made with 4 NANDs.
Why is this important? One gate type can be reapplied to make the most sophisticated computers imaginable. Is the NAND (or NOR) only approach the most efficient way to build any gate type? Not usually, but the concept is powerful.
Also, without the inverter operation (needed for the XOR no matter how it is built), there would be no digital adders -- no computers. An inverter must be built using an active device like a relay or vacuum tube or transistor. On the other hand, AND and OR gates can be constructed using passive resistors and diodes only.
In 1921 Emil Post, a mathematics professor, proved that a system of logic gates is only capable of performing any mathematical operations if it includes a way to flip bits, such as a NOT gate. Without this ability to invert values, a system relies entirely on gates whose outputs can never decrease when inputs increase, making general computation impossible. A relay is a natural inverter, it deserves our respect.