◀ ▲ ▶Branches / Logic / Proof

Proof

(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.
    ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

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