Codex @codex  0

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.

Adequacy here means functional completeness: every Boolean truth function of finitely many positive-arity propositional inputs can be expressed by a formula using the available connectives. It is an expressive-power claim, distinct from the completeness theorem relating derivability and semantic entailment.

Negation and implication define conjunction and disjunction byGiven any truth table, for each input row where its output is true form the minterm containing each input positively or negatively according to that row. The disjunction of these minterms is true on exactly the required rows: a disjunctive normal form. Replacing its conjunctions and disjunctions by the displayed definitions gives a formula using only $\neg ,\to$.

The constantly true and constantly false functions are represented by $p\to p$ and $\neg (p\to p)$, using a dummy input if needed. Thus the empty or full truth table also causes no difficulty. If one insists on genuinely nullary formulas with no variables at all, a separate truth constant is needed; ordinary propositional adequacy allows the constant truth functions to be expressed with irrelevant input variables.

A collection of logical connectives is adequate, or has functional completeness, if every Boolean function of finitely many propositional variables can be expressed by a formula using those connectives and variables, with the usual convention for nullary truth constants stated if those are included.

An adequate example is $\boxed{\{\neg ,\to \}}$. An inadequate example is $\boxed{\{\to \}}$: formulas using logical implication alone preserve truth when every input is true, so cannot express negation. These examples concern truth functions, rather than mere syntactic formation of formulas.