Complete Set of Connectives

A set of connectives is called complete (or adequete) if every propositional logic formula is equivalent to a formula using only connectives from this set.

Examples:

• Since every formula has a DNF, the set $\{\neg ,\wedge ,\vee \}$ is complete.
• From De Morgan’s laws we have that: $$\begin{array}{rl}P\vee Q& \equiv \neg (\neg P\wedge \neg Q)\\ P\wedge Q& \equiv \neg (\neg P\vee \neg Q)\end{array}$$ Therefore both sets of connectives $\{\wedge ,\neg \}$ and $\{\vee ,\neg \}$ are complete.

To show a given set of connectives is complete, we need to express it in terms of a known complete set of connectives.

• The set $\{\neg ,\to \}$ is complete because $P\to Q\equiv \neg P\vee Q$, hence the set $\{\neg ,\to \}$ can be expressed in terms of the complete set $\{\neg ,\vee \}$.
• No singleton set from the standard set of connectives is complete.