1 Logic

1.8 Adequacy

One of the logical equivalences we proved earlier 1.7.1 was

pq(¬p)q

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

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 {,,¬} is adequate, but there are even smaller adequate sets.

Theorem 1.8.1.

{,¬} is adequate.

Proof.

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

¬(ϕψ)(¬ϕ)(¬ψ)

so by double negation, Theorem 1.6.2,

ϕψ¬((¬ϕ)(¬ψ)). (1.2)

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

Example 1.8.1.

Consider the formula ϕ given by

p(qr).

Because {,¬} is adequate there must exist a formula logically equivalent to ϕ using only ¬ and . Let’s find one.

p(qr) (¬p)(qr) Theorem 1.7.1
(¬p)¬((¬q)(¬r)) (1.2)
Theorem 1.8.2.

{,¬} is adequate.

Proof.

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

¬(ϕψ)(¬ϕ)(¬ψ)

and so using double negation (Theorem 1.6.2)

ϕψ¬((¬ϕ)(¬ψ)) (1.3)

which means we can replace every occurrence of ϕψ in a WFF with the right hand side of (1.3), which only involves ¬ and . ∎

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 only (any such formula is true when all its variables are true, so we can’t find one equivalent to ¬p) or using only (same argument) or only (same argument).

There are single connectives which are adequate on their own. For example, if we define pq to have the same truth table as ¬(pq) (the Sheffer stroke or NAND), and pq (the Pierce arrow or NOR) to have the truth table of ¬(pq), it can be shown that both {} and {} are adequate.

ϕ ψ (ϕψ)
T T F
T F F
F T F
F F T
Table 1.5: Truth table for

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