Functional completeness#
A set of boolean operators is functionally complete when every
one of the sixteen binary truth functions can be built from
operators in that set, by composition. The classical complete
sets you already know are {∧, ∨, ¬} and {→, ⊥}. The
surprising — and useful — result is that a single operator
suffices, but only two of the sixteen binary functions have
this property: NAND and NOR.
NAND is named after Henry M. Sheffer (1913) and written ↑; NOR
is named after Charles Sanders Peirce (who described it earlier)
and written ↓. They are the two Sheffer strokes.
Building everything from NAND#
NAND alone gives you all sixteen functions. The constructions
below show the four most useful — NOT, AND, OR, XOR — in terms
of ↑. Think of a ↑ b as !($a && $b).
Target |
In terms of NAND |
Why |
|---|---|---|
|
|
|
|
|
NAND then negate the result, i.e. |
|
|
De Morgan: |
|
|
XOR is the AND of (a ∨ b) and ¬(a ∧ b) — left as exercise |
The same constructions exist with NOR; they are the De Morgan duals.
In Perl#
You will not write your code this way in production — (a ↑ a) ↑ (b ↑ b) is a worse spelling of OR than || is. But it is worth
seeing the constructions actually run, because the abstract claim
(“everything reduces to one operator”) becomes concrete when you
type it.
sub nand { !($_[0] && $_[1]) } # the only primitive
sub not_a { nand($_[0], $_[0]) } # ¬a
sub and_ { my $n = nand($_[0], $_[1]); nand($n, $n) } # a ∧ b
sub or_ { nand(nand($_[0], $_[0]), nand($_[1], $_[1])) } # a ∨ b
sub xor_ {
my ($a, $b) = @_;
my $n = nand($a, $b);
nand(nand($a, $n), nand($b, $n));
}
# Verify across all four input combinations:
for my $a (0, 1) {
for my $b (0, 1) {
printf "a=%d b=%d not=%d and=%d or=%d xor=%d\n",
$a, $b,
not_a($a) ? 1 : 0,
and_($a, $b) ? 1 : 0,
or_($a, $b) ? 1 : 0,
xor_($a, $b) ? 1 : 0;
}
}
Output:
a=0 b=0 not=1 and=0 or=0 xor=0
a=0 b=1 not=1 and=0 or=1 xor=1
a=1 b=0 not=0 and=0 or=1 xor=1
a=1 b=1 not=0 and=1 or=1 xor=0
Each row matches the truth table from the previous chapter.
Why this matters#
Three things, in order of practical-to-deep:
It explains the bestiary of identities. NAND, NOR, and the eleven non-direct rows of the truth-table chapter are not a zoo of separate facts. They are all expressible from a single operator; the eleven non-direct spellings in Perl are just readable shortcuts for short NAND or NOR compositions.
It is how silicon actually works. Static-CMOS logic produces NAND and NOR more cheaply than AND and OR — a two-input AND gate is built as a NAND followed by an inverter. Every other gate on a chip is a composition of NANDs (or NORs). The pattern repeats in solver and constraint-engine internals: SAT solvers normalise to CNF precisely because OR-of-(literals) and AND-of-(clauses) is the minimal vocabulary they need.
It teaches the discipline of canonical form. Every boolean expression has many equivalent shapes, but only a few are canonical. CNF (conjunctive normal form: an AND of ORs of possibly-negated literals) and DNF (disjunctive normal form: an OR of ANDs) are the two most common. Reducing a tangle to CNF or DNF is a pure mechanical procedure based on De Morgan plus distributivity, and once your expression is in normal form you can compare it with another normal-form expression to test equivalence — without truth tables, without testing.
You will not implement a SAT solver next week. But the next time
you find yourself writing if ((!$a && $b) || (!$c && $b) || ($a && !$c)) and wondering whether the previous version was
equivalent, you have a tool: distribute, factor, normalise.
Two expressions that reduce to the same DNF compute the same
function.
What you should remember from this chapter#
NAND and NOR are each individually sufficient to express every boolean function. No other two-input operator has this property.
The constructions are short and you can verify them in Perl in ten lines.
The point is not to write code in NAND, but to know that all sixteen binary functions live on one foundation. The apparently disparate rows of the truth-table chapter are one family.