(related to Lemma: Boolean Function)

Now we will prove the above lemma by verifying that a Boolean function $f_\phi$ is properly defined of any proposition $\phi$.

- Case 1: Assume that $\phi$ is a prime proposition.
- Then $\phi$ is by definition either a Boolean constant or a Boolean variable.
- For any given interpretation $I$ and the corresponding valuation function $[[]]_I$, it follows from the definition of the semantics of $PL0$ that $$f_\phi=\cases{ [[ 1 ]]_I&\text{if }\phi\text{ is the Boolean constant }1,\\ [[ 0 ]]_I&\text{if }\phi\text{ is the Boolean constant }0,\\ [[x]]_I&\text{if }\phi\text{ is the Boolean variable }x,\\ }$$
- Therefore, $f_\phi$ is well-defined.

- Case 2: Now assume that $\phi$ is a proposition compound of prime propositions, i.e. $\phi=p_1\circ\ldots\circ p_n$ for an $n$-ary connective "$\circ$", all $p_i$ being prime.
- From Case 1 it follows that the Boolean functions $f_{p_1},\ldots,f_{p_n}$ are well-defined.
- The valuation function $[[p_1\circ\ldots\circ p_n]]_I$ induces a composition of Boolean functions $f_{\phi}=f_{p_1}\circ \ldots\circ f_{p_n}$.
- We know that any composition of functions is again a function. This holds for functions in general, and for Boolean functions in particular.
- Therefore, $f_\phi$ is well-defined.

- General Case 3: Now assume that $\phi$ is a proposition compound of compound propositions $p_1,\ldots, p_n$.
- Since by Case 2, $f_{p_1},\ldots, f_{p_n}$ are well-defined and since any composition of functions is again a function, therefore $f_\phi=f_{p_1}\circ \ldots\circ f_{p_n}$ is well-defined.∎

- Since by Case 2, $f_{p_1},\ldots, f_{p_n}$ are well-defined and since any composition of functions is again a function, therefore $f_\phi=f_{p_1}\circ \ldots\circ f_{p_n}$ is well-defined.

**Mendelson Elliott**: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982