1 Logic 1.7 The contrapositive 1.9 First order logic

1.8 Adequacy

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.

$\phi$	$\psi$	$(\phi\downarrow\psi)$
T	T	F
T	F	F
F	T	F
F	F	T

Table 1.5: Truth table for

\downarrow

1.8.2 Why should you care about adequacy?

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).