proof that any boolean function can be written in canonical form

Question

It's bugging me for a while but although I can vaguely see that when writing canonical forms we kind "build them" in a way specificly to make it be true but I can't grasp exactly why it is possible to do so and if there is any proof of it. I've been having a hard time finding about this online so if anyone can help it would be awesome.

Answer 1

A Boolean function $\varphi$ is specified by its truth table. For the conjunctive normal form, we look at the rows where the function evaluates to $0$. Each row yields a distinct clause, and we take a conjunction of the clauses. Note that $\varphi(x_{1}, \ldots, x_{n}) = 0$ if and only if the specific values for $x_{1}, \ldots, x_{n}$ correspond to one of the rows specified by a given clause. Otherwise, $\varphi(x_{1}, \ldots, x_{n}) = 1$ on those inputs.

To build a clause from a given row, we record $x_{i}$ if $x_{i} = 0$ at that row. Otherwise, we record $\overline{x_{i}}$. We then consider the disjunction (OR) of those literals to obtain the clause.

Section 2.3 of Savage gives a good overview of this in more detail. (http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter2.pdf)