One of the logical equivalences we proved earlier 1.7.1 was

 $p\implies q\equiv(\neg p)\vee q$

which you could interpret as saying that we don’t really need the $\implies$ connective, in the sense that if you are given any WFF using $\vee$, $\wedge$, $\implies$, and $\neg$ you can convert it into a logically equivalent one that does not use $\implies$ by replacing every occurrence of $\phi\implies\psi$ with $(\neg\phi)\vee\psi$.

###### Definition 1.8.1.

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,\neg\}$ is adequate, but there are even smaller adequate sets.

###### Theorem 1.8.1.

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

###### Proof.

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

 $\neg(\phi\wedge\psi)\equiv(\neg\phi)\vee(\neg\psi)$

so by double negation, Theorem 1.6.2,

 $\phi\wedge\psi\equiv\neg((\neg\phi)\vee(\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 $\neg$. We’ve shown every WFF is equivalent to one only using $\vee$ and $\neg$. ∎

###### Example 1.8.1.

Consider the formula $\phi$ given by

 $p\implies(q\wedge r).$

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

 $\displaystyle p\implies(q\wedge r)$ $\displaystyle\equiv(\neg p)\vee(q\wedge r)$ Theorem 1.7.1 $\displaystyle\equiv(\neg p)\vee\neg((\neg q)\vee(\neg r))$ (1.2)
###### Theorem 1.8.2.

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

###### Proof.

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

 $\neg(\phi\vee\psi)\equiv(\neg\phi)\wedge(\neg\psi)$

and so using double negation (Theorem 1.6.2)

 $\phi\vee\psi\equiv\neg((\neg\phi)\wedge(\neg\psi))$ (1.3)

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

## 1.8.1 Which sets of connectives are not adequate?

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 $\neg p$) or using $\wedge$ only (same argument) or $\implies$ 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 $\neg(p\wedge q)$ (the Sheffer stroke or NAND), and $p\downarrow q$ (the Pierce arrow or NOR) to have the truth table of $\neg(p\vee q)$, it can be shown that both $\{\uparrow\}$ and $\{\downarrow\}$ are adequate.