Functional Completeness of Connectives

Why a handful of connectives — or NAND alone — express every truth table.

The idea

Functional completeness measures whether a set of connectives can express everything sentential logic can say. Each formula computes a Boolean function of its variables: run through every assignment of true and false to the variables and record the output on each row. A formula in $n$ variables has $2^{n}$ rows to fill, so there are $2^{2^{n}}$ Boolean functions of $n$ variables.

Definition (Functionally complete).

A set of connectives is functionally complete when every Boolean function, on any number of variables, is the output column of some formula built from that set alone.

Theorem.

The set $\{\neg, \wedge, \vee\}$ is functionally complete.

Consequently any set of connectives that can express each of $\neg$, $\wedge$ and $\vee$ is functionally complete as well: the familiar connectives $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$ form one such set, and much smaller sets suffice.

The two halves of the question call for opposite arguments. To show a set is complete, either give a construction that reaches every truth table, or express the connectives of a set already known to be complete using only the new ones. To show a set is not complete, no search through formulas can succeed, since there are infinitely many; instead, find a property shared by all of its connectives and inherited by every formula built from them. Any Boolean function without that property is then unreachable, and one such function is enough.

Ways to work on it

• Walkthrough. Disjunctive normal form, trimming to , , and NAND alone.
• Practice. Decide whether a given set of connectives is functionally complete.
• Hardest. Prove a set is incomplete via a shared preserved property.

Not sure where to start? Take the ten-question placement test.