= Solution
Translate <logical formulas> recursively, leaving <propositional variables> unchanged and translating <negation> by applying <negation> to the translation. For the other two <logical connectives> <set>
$$
T(\psi\lor\chi)=(\neg T(\psi)\to T(\chi)),\qquad
T(\psi\land\chi)=\neg(T(\psi)\to\neg T(\chi)).
$$
The 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>. \b[Thus $\{\neg,\to\}$ is adequate.]
Back to article page
