---
name: functional completeness — NAND and NOR
---
# 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                                          |
|---------|--------------------------------------|----------------------------------------------|
| `¬a`    | `a ↑ a`                              | `!(a ∧ a)` is `!a`                           |
| `a ∧ b` | `(a ↑ b) ↑ (a ↑ b)`                  | NAND then negate the result, i.e. `!!(a ∧ b) ≡ a ∧ b` |
| `a ∨ b` | `(a ↑ a) ↑ (b ↑ b)`                  | De Morgan: `a ∨ b ≡ ¬(¬a ∧ ¬b) ≡ ¬a ↑ ¬b`    |
| `a ⊕ b` | `(a ↑ (a ↑ b)) ↑ (b ↑ (a ↑ b))`      | 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.

```perl
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:

1. **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.

2. **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.

3. **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.