This post assumes you know what logic gates are, but not much more. I wrote it to serve as a quick guide on some very basic facts about logic gates that aren't often justified, and when they are, they're justified in an overcomplicated way. The two facts we'll go over are:
The first of these is often mentioned but rarely justified (it's often said there are seven: the seventh they're talking about is NOT, which is a unary gate I'm ignoring). Not knowing why there are only six can lead people to wonder about the possibility of other, undiscussed (hidden?) gates. As such, I find justifiying the count of six as essential, as you know you're not missing out on anything.
For the second, it's often shown how NAND and NOR are functionally complete, but rarely shown that the others cannot be. This is actually surprisingly trivial to do, as you'll see.
There are four possible combinations of two binary inputs. For each of these combinations a binary gate produces a binary output. There are thus 24 ways to make a gate, and thus 24 possible binary gates.
You might notice that 16 is more that 6. This is true. I lied to you. But I did it for your own good! 10 of these gates are not very useful.
Two of these gates are actually not useful in any way at all: the gate that is always false and the gate that is always true. Neither of these gates have an output that is a function of its inputs, so are obviously useless.
The other 8 gates I claim as not very useful because they're not symmetric: if you switch A and B the output changes. This might be a desirable property in some cases, in particular for the relationship A implies B (or vice versa), but generally being asymmetric complicates analysis and in a practical setting makes the gates much more error-prone.
That leaves these six, for which I've produced their truth tables below. I've omitted the case A and ~B, as that will be the same as ~A and B for symmetric gates:
| A | B | AND | XOR | OR | NOR | XNOR | NAND |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
The naming of these is straightforward: AND and OR correspond to their English words, XOR is short for "eXclusive OR", and the other three are negations of the first three, so get an N in the name.
This table counts up in binary as you go left to right. If you imagine a complete table where all 16 possibilities are present (with an extra row for A and ~B), you can see how the table would begin with 0000 and end with 1111, and how half of the gates would have a 01 or 10 for the middle rows, which would make them asymmetric. Those are the 10 less useful gates.
In case you don't know, of the above gates only NOR and NAND are functionally complete.
As a reminder, a set of gates (which may just be one gate) is functionally complete if and only if they (or it) can be used to create any truth table. There are other ways to define functional completeness, but this is the definition we'll use.
As an example, the set {AND, OR, NOT} is functionally complete. This is very easy to show: for any truth table, you can OR together all combinations of inputs that result in a true output. As an example, consider the truth table for A implies B:
| A | B | A implies B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
This is equivalent to (~A AND ~B) OR (~A AND B) OR (A AND B).
This technique can be extended to create any truth table with just {AND, OR, NOT}. However, this set is actually redundant. You can do away with AND or OR and still be functionally complete. DeMorgan's Laws show us why:
These laws show that you can use {OR, NOT} to create AND, and likewise use {AND, NOT} to create OR. So the sets {OR, NOT} and {AND, NOT} are functionally complete, because they can do everything {AND, OR, NOT} can.
Knowing that {AND, NOT} and {OR, NOT} are functionally complete allows us to show that {NAND} and {NOR} are functionally complete, so long as we can show that both {NAND} and {NOR} can each be used to create one of the sets already established as functionally complete. Let's do this.
First, we'll show that {NOR} can be used to create both NOT and OR:
Likewise, we can show that {NAND} can be used to create both NOT and AND:
This shows that both {NAND} and {NOR} are functionally complete.
But we've yet to show that none of the other (useful) binary gates are complete. To do that, we'll show that these gates have a property that prevent them from creating certain truth tables.
If you look back at the truth tables for the six gates you might be able to spot what's different about NOR and NAND. If both inputs are 0 or 1, the output of NOR and NAND is the opposite. This is actually a necessary feature of being functionally complete.
To see why, consider the case of both inputs being 0. Because the ouput or AND, XOR, and OR will be 0, any combination of them will also be 0. This means they cannot produce any truth table that has a true output for all-false inputs. Likewise, if both inputs are 1, any combination of AND, OR, and XNOR will be 1, and so cannot produce any truth table that has a false output for all-true inputs. This means that AND, XOR, OR, and XNOR cannot be functionally complete.
With all that we've shown that there only six (useful) binary gates, and we have a complete understanding of why each one is or is not functionally complete.