= Solution
Fix any <Boolean valuation> $v$. <Logical equivalence> of $\alpha$ and $\beta$ means $v(\alpha)=v(\beta)$ for this <Boolean valuation> and every other one. Follow the unique path from the replaced node to the root of the <formula syntax tree>. At a <negation> node, equal input <truth values> have equal <negations>. At a <logical implication> node, the unaffected child has the same <truth value> before and after <subformula replacement>, while the affected child has the same <truth value> by induction; the resulting <logical implications> therefore agree as well.
Induction along that finite path yields $v(\phi)=v(\phi')$. Since $v$ was arbitrary,
$$
\boxed{\phi\equiv\phi'.}
$$
This is the <replacement theorem for logical equivalence>: the semantics of each <logical connective> depends only on the <truth values> of its immediate inputs.
Back to article page
