Exercise $2$ Give a semantic proof of the Craig Interpolation Lemma: Given propo$-$ sitional formulas A and B$,$ let S be the set of atoms which occur in both A and B$,$ and assume that S is nonempty. If A $$ B is valid, then there is a formula C $($an $$interpolant$)$ containing only atoms from S such that both A $$ C and C $$ B are valid.

Remark: The Lemma still holds even when S is empty, provided we include the symbols $0$ and $1($meaning False and True$)$ as building blocks in our definition of formula. It is illuminating to consider this special case when trying to find the proof.