One of the logical equivalences we proved earlier 1.7.1 was

$$p\u27f9q\equiv (\mathrm{\neg}p)\vee q$$ |

which you could interpret as saying that we don’t really *need* the
$\u27f9$ connective, in the sense that if you give me any WFF using
$\vee $, $\wedge $, $\u27f9$, and $\mathrm{\neg}$ I can convert it into a
logically equivalent one that does not use $\u27f9$ by replacing every
occurrence of $\varphi \u27f9\psi $ with $(\mathrm{\neg}\varphi )\vee \psi $.

A set of connectives is adequate if every WFF is logically equivalent to one using only the connectives from that set.

The argument above shows that the set $\{\wedge ,\vee ,\mathrm{\neg}\}$ is adequate, but there are even smaller adequate sets.

$\{\vee ,\mathrm{\neg}\}$ is adequate.

Every WFF is equivalent to one using only $\wedge $, $\vee $, and $\mathrm{\neg}$. By the second of De Morgan’s laws, Theorem 1.6.3 part 2,

$$\mathrm{\neg}(\varphi \wedge \psi )\equiv (\mathrm{\neg}\varphi )\vee (\mathrm{\neg}\psi )$$ |

so by double negation, Theorem 1.6.2,

$$\varphi \wedge \psi \equiv \mathrm{\neg}((\mathrm{\neg}\varphi )\vee (\mathrm{\neg}\psi )).$$ | (1.2) |

This means every occurrence of $\wedge $ in a formula can be replaced with the logically equivalent formula on the right hand side of (1.2) which only uses $\vee $ and $\mathrm{\neg}$. We’ve shown every WFF is equivalent to one only using $\vee $ and $\mathrm{\neg}$. ∎

Consider the formula $\varphi $ given by

$$p\u27f9(q\wedge r).$$ |

Because $\{\vee ,\mathrm{\neg}\}$ is adequate there must exist a formula logically equivalent to $\varphi $ using only $\mathrm{\neg}$ and $\vee $. Let’s find one.

$p\u27f9(q\wedge r)$ | $\equiv (\mathrm{\neg}p)\vee (q\wedge r)$ | Theorem 1.7.1 | ||

$\equiv (\mathrm{\neg}p)\vee \mathrm{\neg}((\mathrm{\neg}q)\vee (\mathrm{\neg}r))$ | (1.2) |

$\{\wedge ,\mathrm{\neg}\}$ is adequate.

We already know that every WFF is logically equivalent to one only using $\mathrm{\neg}$, $\wedge $, and $\vee $. By the first of De Morgan’s laws, Theorem 1.6.3 part 1,

$$\mathrm{\neg}(\varphi \vee \psi )\equiv (\mathrm{\neg}\varphi )\wedge (\mathrm{\neg}\psi )$$ |

and so using double negation (Theorem 1.6.2)

$$\varphi \vee \psi \equiv \mathrm{\neg}((\mathrm{\neg}\varphi )\wedge (\mathrm{\neg}\psi ))$$ | (1.3) |

which means we can replace every occurrence of $\varphi \vee \psi $ in a WFF with the right hand side of (1.3), which only involves $\mathrm{\neg}$ and $\wedge $. ∎

It’s clear that we can’t go any further: it isn’t true that every WFF is equivalent to one using $\vee $ only (any such formula is true when all its variables are true, so we can’t find one equivalent to $\mathrm{\neg}p$) or using $\wedge $ only (same argument) or $\u27f9$ only (same argument).

There *are* single connectives which are adequate on their own. For
example, if we define $p\uparrow q$ to have the same truth table as
$\mathrm{\neg}(p\wedge q)$ (the *Sheffer stroke* or NAND), and $p\downarrow q$ (the *Pierce arrow* or NOR) to have the truth table
of $\mathrm{\neg}(p\vee q)$, it can be shown that both $\{\uparrow \}$ and
$\{\downarrow \}$ are adequate.

$\varphi $ | $\psi $ | $(\varphi \downarrow \psi )$ |
---|---|---|

T | T | F |

T | F | F |

F | T | F |

F | F | T |

Firstly it can be useful for proving theorems to be able to find logical
equivalents to a WFF in simple standard forms, e.g.
disjunctive
normal form and its and-analogue conjunctive normal form. Second,
*logic gates* (electronic devices implementing logical connectives)
are a fundamental part of digital circuit design. A computer chip is
largely made up of many logic gates connected together. In the early
days of digital electronics using only one type of logic gate helped
make the design much easier. The
Apollo
guidance computer, used on the first ever moon landing, was built
using only NOR gates (about 6000 of them).