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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)
