Past exam of the logic and set theory course of the University of Oxford / 2008 / A / 2 / b / Solution

Translate logical formulas recursively, leaving propositional variables unchanged and translating negation by applying negation to the translation. For the other two logical connectives setThe first logical implication is false exactly when both original inputs are false; the second displayed logical formula is true exactly when both inputs are true. Hence each clause preserves truth values. Structural induction gives $v(T(\theta ))=v(\theta )$ for every Boolean valuation and every logical formula $\theta$ in the larger language.

By the assumed functional completeness of negation, logical conjunction and logical disjunction, any finite Boolean function has such a logical formula $\theta$. Its translation $T(\theta )$ uses only negation and logical implication and represents the same function. Thus $\{\neg ,\to \}$ is adequate.