The path to simplicity often leads through a seemingly needless level of complexity—and this case is no exception. To even begin, we must consider the work of another 19th-century mathematician, Augustus DeMorgan (1806–71). DeMorgan’s law states that “a complement of disjunction is the conjunction of complements.” This infamous exercise in obfuscating trivial concepts has some profound consequences for Boolean logic and, ultimately, the design of digital circuits.
In plain English, DeMorgan’s law explains that when any (or both) of two conditions is not satisfied, a sentence that claims that both conditions are met (or, in other words, a conjunction of conditions occurs) will be false as well—oh, and vice versa.
The law concludes that NOT OR (a, b) should be logically equivalent to AND (NOT a, NOT b). Consider a real-world example in which a and b represent the following:
| a = “Bob likes milk” |
| b = “Bob likes apples” |
The two sides of the DeMorgan’s equation can be now written as:
| OR (NOT a, NOT b) ⇔ Bob does NOT like milk OR does NOT like apples |
| NOT AND (a, b) ⇔ It is NOT true that Bob likes both milk AND apples |
Both expressions are functionally equivalent. If it is true that Bob dislikes either milk or apples, the first expression is true; it is then also true that he does not like both, which means that the second expression is also true.
Reversing the situation also results in agreement: If it is not true that Bob dislikes at least one of the choices, he likes both (and the first expression is false). In that case, it is also not true that he does not like both (and the second expression is also false).
To evaluate logic statements beyond appeals to intuition and some hand waving, it helps to construct so-called truth tables that demonstrate all the results that can be calculated from all possible combinations of true and false operators.
The following two tables represent each expression from the previous example. Each table includes columns for both operators and the corresponding results for all possible true and false combinations. And so, in the first row, you can see that two first columns—both operands to NOT AND(a, b)—are false. This causes AND(a, b) to be false, as well, hence causing NOT AND(a, b) to be true. The outcome is denoted in the third column.
As you can see, the two expressions behave identically:
NOT AND(a, b): AND w/Result Negated | ||
|---|---|---|
Operand 1 (a) | Operand 2 (b) | Result |
FALSE | FALSE | TRUE |
FALSE | TRUE | TRUE |
TRUE | FALSE | TRUE |
TRUE | TRUE | FALSE |
OR(NOT a, NOT b): OR w/Operands Negated | ||
|---|---|---|
Operand 1 | Operand 2 | Result |
FALSE | FALSE | TRUE |
FALSE | TRUE | TRUE |
TRUE | FALSE | TRUE |
TRUE | TRUE | FALSE |
But why do computer designers care about Bob’s food preferences? Because in the context of Boolean operators, DeMorgan’s law means that the set of basic operations proposed by Boolean algebra is actually partially redundant: a combination of NOT and any of the two other operators (OR and AND) is always sufficient to synthesize the remaining one. For example:
| OR (a, b) ⇔ NOT AND (NOT a, NOT b) |
| AND (a, b) ⇔ NOT OR(NOT a, NOT b) |
This understanding reduces the set of operators to two, but the Boolean system can be simplified still further.
Several additional operators are not crucial for implementing Boolean logic, but complement the existing set of operations. These additional operators, NAND and NOR, are true only when AND and OR respectively are false:
| NAND(a, b) ⇔ NOT AND(a, b) ⇔ OR(NOT a, NOT b) |
| NOR(a, b) ⇔ NOT OR(a, b) ⇔ AND(NOT a, NOT b) |
These new functions are no more complex than AND and OR. Each has a four-state (four-row) truth table, and hence its value can determined with just as much effort.
Note
NOR and NAND are not found in the basic set of operands because neither one corresponds to a commonly used, basic type of logical relation between sentences and has no atomic representation in the common language.
I have just introduced a set of new operators, derived from the existing set, that seem to offer nothing but a dubious convenience feature for those wanting to express more bizarre logic dependencies or problems using formal notation. What for?
The introduction of NAND or NOR alone makes it possible to get rid of AND, OR, and NOT altogether. This furthers our goal of simplicity and affords us the ability to describe the entire Boolean algebra system with fewer elements and operators.
The importance of those negated auxiliary operators is that you can use any one of them to build a complete Boolean algebra system. In fact, you can construct all basic operators using NAND, as shown here (T stands for a true statement, and F stands for false[8]). How? Well, quite obviously, the following pairs of statements are equivalent:
| NOT a ⇔ NAND(T, a) |
| AND(a, b) ⇔ NOT NAND(a, b) ⇔ NAND(T, NAND(a, b)) |
| OR(a, b) ⇔ NAND(NOT a, NOT b) ⇔ NAND(NAND(T, a), NAND(T, b)) |
or, if we prefer to rely exclusively on NOR, rather than NAND, we can say
| NOT a ⇔ NOR(F, a) |
| OR(a, b) ⇔ NOT NOR(a, b) ⇔ NOR(F, NOR(a, b)) |
| AND(a, b) ⇔ NOR(NOT a, NOT b) ⇔ NOR(NOR(F, a), NOR(F, b)) |
It can be hard to believe that the essence of all computing can be captured within one of the universal logic operators. You can implement most complex algorithms, advanced computations, cutting-edge games, and Internet browsing using an array of simple circuits that involve one of the following truth tables, which convert input signals to output signals:
NAND State Table | ||
|---|---|---|
Operand 1 | Operand 2 | Result |
FALSE | FALSE | TRUE |
FALSE | TRUE | TRUE |
TRUE | FALSE | TRUE |
TRUE | TRUE | FALSE |
NOR State Table | ||
|---|---|---|
Operand 1 | Operand 2 | Result |
FALSE | FALSE | TRUE |
FALSE | TRUE | FALSE |
TRUE | FALSE | FALSE |
TRUE | TRUE | FALSE |
It would seem we are going nowhere, though. . . . How come this trivial set of dependencies make it possible to build a device capable of solving complex problems, such as rejecting your credit application in a tactful manner? And what does a piece of theory based on the states “true” and “false” have in common with digital circuits?
[8] Purists may want to assume that T is equivalent to AND(a, a), for example, which is always true, and F is equivalent to NOT AND (a, a), which is always false. In other words, we do not introduce a new concept or equation element—we only simplify the notation a bit at this point.