Functionally Complete Logical Connectives

Theorem

These sets of logical connectives are functionally complete:

• $\left\{{\neg, \land, \lor}\right\}$: Not, And and Or

• $\left\{{\neg, \land}\right\}$: Not and And
• $\left\{{\neg, \lor}\right\}$: Not and Or
• $\left\{{\neg, \implies}\right\}$: Not and Implies

• $\left\{{\uparrow}\right\}$: NAND
• $\left\{{\downarrow}\right\}$: NOR

There are others, but these are the main ones.

Further, the only connectives that form singleton sets which are functionally complete are NAND and NOR.

Proof

It suffices to consider binary operators:

Constant Functions

• Two constant functions:
  • $f_F \left({p, q}\right) = F$;
  • $f_T \left({p, q}\right) = T$.

From Equivalence Properties and Exclusive Or Properties, we have that:

• $p \iff p \dashv \vdash \top \dashv \vdash f_T \left({p, q}\right)$
• $p \oplus p \dashv \vdash \bot \dashv \vdash f_F \left({p, q}\right)$

So both of the constant functions can be expressed in terms of $\oplus$ and $\iff$.

Equivalence and Non-Equivalence

• The exclusive or: $p \oplus q$:

We note that by definition $p \oplus q \dashv \vdash \neg \left({p \iff q}\right)$.

Thus $\oplus$ can be expressed in terms of $\neg$ and $\iff$.

• The equivalence: $p \iff q$:

We note that by definition $p \iff q \dashv \vdash \left({p \implies q}\right) \land \left({q \implies p}\right)$.

Thus $\iff$ can be expressed in terms of $\implies$ and $\land$.

Projections and Negated Projections

• Two projections:
  • $\operatorname{pr}_1 \left({p, q}\right) = p$
  • $\operatorname{pr}_2 \left({p, q}\right) = q$

We note that:

• $p \land p \dashv \vdash p \dashv \vdash \operatorname{pr}_1 \left({p, q}\right)$
• $p \lor p \dashv \vdash p \dashv \vdash \operatorname{pr}_1 \left({p, q}\right)$

and similarly for $\operatorname{pr}_2 \left({p, q}\right)$.

So the projections can be expressed in terms of either $\land$ or $\lor$.

• Two negated projections:
  • $\overline {\operatorname{pr}_1} \left({p, q}\right) = \neg p$
  • $\overline {\operatorname{pr}_2} \left({p, q}\right) = \neg q$

It immediately follows from the above that these can be expressed in terms of either:

• $\neg$ and $\land$

or:

• $\neg$ and $\lor$

NAND and NOR

• The NAND: $p \uparrow q$
• The NOR: $p \downarrow q$

By definition:

• $p \uparrow q \dashv \vdash \neg \left({p \land q}\right)$
• $p \downarrow q \dashv \vdash \neg \left({p \lor q}\right)$

So:

• $\uparrow$ can be expressed in terms of $\neg$ and $\land$
• $\downarrow$ can be expressed in terms of $\neg$ and $\lor$

Conjunction, Disjunction, Conditional

• The conjunction: $p \land q$
• The disjunction: $p \lor q$

• Two conditionals:
  • $p \implies q$
  • $q \implies p$

• Two negated conditionals:
  • $\neg \left({p \implies q}\right)$
  • $\neg \left({q \implies p}\right)$

All of the above are already expressed in terms of $\neg, \land, \lor, \implies$.

Functionally Complete Sets

So we have shown that all sixteen of the binary operators can be expressed in terms of $\neg, \land, \lor, \implies$.

Next we show the sufficiency of the sets $\left\{{\neg, \land}\right\}, \left\{{\neg, \lor}\right\}, \left\{{\neg, \implies}\right\}$.

From these stronger results we can see that the set $\left\{{\neg, \land, \lor}\right\}$ is also functionally complete.

And and Not

From Conjunction and Implication, we have that:

$p \implies q \dashv \vdash \neg \left({p \land \neg q}\right)$

From De Morgan's laws, we have that:

$p \lor q \dashv \vdash \neg \left({\neg p \land \neg q}\right)$

So any instance of either $\implies$ or $\lor$ can be replaced identically with one using just $\neg$ and $\land$.

It follows that $\left\{{\neg, \land}\right\}$ is functionally complete.

$\blacksquare$

Or and Not

From De Morgan's laws, we have that:

$p \land q \dashv \vdash \neg \left({\neg p \lor \neg q}\right)$

From the above, we can represent any boolean expression in terms of $\land$ and $\neg$.

So it follows that we can replace all occurrences of $\land$ by $\lor$ and $\neg$, and so $\left\{{\neg, \lor}\right\}$ is functionally complete.

$\blacksquare$

Implies and Not

From Conjunction and Implication, we have that:

$p \land q \dashv \vdash \neg \left({p \implies \neg q}\right)$

From the above, we can represent any boolean expression in terms of $\land$ and $\neg$.

So it follows that we can replace all occurrences of $\land$ by $\implies$ and $\neg$, and so $\left\{{\neg, \implies}\right\}$ is functionally complete.

$\blacksquare$

NAND

From the above, we can represent any boolean expression in terms of $\land$ and $\neg$.

From Properties of NAND, we can express $\neg p$ in terms of $\uparrow$ as follows:

$\neg p \dashv \vdash p \uparrow p$

Having established that, we can then express $p \land q$ solely in terms of $\uparrow$ as follows:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p \land q\)	\(\dashv \vdash\)	\(\displaystyle \neg \neg \left({p \land q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Double Negation
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\dashv \vdash\)	\(\displaystyle \neg \left({p \uparrow q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of NAND
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\dashv \vdash\)	\(\displaystyle \left({p \uparrow q}\right) \uparrow \left({p \uparrow q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Properties of NAND

So any boolean expression can be represented solely in terms of $\uparrow$.

Hence $\left\{{\uparrow}\right\}$ is functionally complete.

$\blacksquare$

NOR

From the above, we can represent any boolean expression in terms of $\lor$ and $\neg$.

From Properties of NOR, we can express $\neg p$ in terms of $\downarrow$ as follows:

$\neg p \dashv \vdash p \downarrow p$.

Having established that, we can then express $p \lor q$ solely in terms of $\downarrow$ as follows:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p \lor q\)	\(\dashv \vdash\)	\(\displaystyle \neg \neg \left({p \lor q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Double Negation
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\dashv \vdash\)	\(\displaystyle \neg \left({p \downarrow q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of NOR
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\dashv \vdash\)	\(\displaystyle \left({p \downarrow q}\right) \downarrow \left({p \downarrow q}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Properties of NOR

So any boolean expression can be represented solely in terms of $\downarrow$.

Hence $\left\{{\downarrow}\right\}$ is functionally complete.

$\blacksquare$

Only NAND and NOR

Suppose $\circ$ is a binary logical connective such that $\left\{{\circ}\right\}$ is a functionally complete set.

The unary logical connective $\neg$ has to be equivalent to some formula:

$\cdots \circ \left({p \circ p}\right) \circ \cdots$.

Suppose some interpretation $v$ assigns $T$ to $p$.

Then $v \left({\neg p}\right) = F$. So:

$v \left({\cdots \circ \left({p \circ p}\right) \circ \cdots}\right) = F$

So it has to be true that $T \circ T = F$, otherwise:

$v \left({\cdots \circ \left({T \circ T}\right) \circ \cdots}\right) = v \left({\cdots \circ \left({T}\right) \circ \cdots}\right) = T$

Similarly, $F \circ F = T$.

Now we look at $T \circ F$ and $F \circ T$.

Suppose $T \circ F = F$.

If $F \circ T = T$, then we have the function defined by this truth table:

$v \left({p}\right)$	$v \left({q}\right)$	$v \left({p \circ q}\right)$
$F$	$F$	$T$
$F$	$T$	$T$
$T$	$F$	$F$
$T$	$T$	$F$

which is $\neg p$, and hence only negation would be definable.

So if $T \circ F = F$ we need $F \circ T = F$.

This gives the truth table for the NOR function:

$v \left({p}\right)$	$v \left({q}\right)$	$v \left({p \circ q}\right)$
$F$	$F$	$T$
$F$	$T$	$F$
$T$	$F$	$F$
$T$	$T$	$F$

... which we have seen is functionally complete.

Similarly, Suppose $T \circ F = T$.

If $F \circ T = F$, then we have the function defined by this truth table:

$v \left({p}\right)$	$v \left({q}\right)$	$v \left({p \circ q}\right)$
$F$	$F$	$T$
$F$	$T$	$F$
$T$	$F$	$T$
$T$	$T$	$F$

which is $\neg q$, and hence only negation would be definable.

So if $T \circ F = T$ we need $F \circ T = T$.

This gives the truth table for the NAND function:

$v \left({p}\right)$	$v \left({q}\right)$	$v \left({p \circ q}\right)$
$F$	$F$	$T$
$F$	$T$	$T$
$T$	$F$	$T$
$T$	$T$	$F$

... which we have seen is functionally complete.

Thus it follows that there can be no functionally complete binary logical connectives apart from NAND and NOR.

$\blacksquare$