I am currently reading Logic in Computer Science Modelling and Reasoning About Systems (by Michael Huth & Mark Ryan).
They introduced a fairly easy way to form conjunctive normal form (CNF) of an unknown formula using its truth table (p. 57):
There is one scenario in which computing an equivalent formula in CNF is really easy; namely, when someone else has already done the work of writing down a full truth table for φ. For example, take the truth table of $(p\to\neg{q})\to(q\lor\neg{p})$ in Figure 1.8 (page 40). For each line where $(p\to\neg{q})\to(q\lor\neg{p})$ computes F we now construct a disjunction of literals. Since there is only one such line, we have only one conjunct $\psi_1$. That conjunct is now obtained by a disjunction of literals, where we include literals $\neg{p}$ and $q$. Note that the literals are just the syntactic opposites of the truth values in that line: here $p$ is T and $q$ is F. The resulting formula in CNF
is thus $\neg{p}\lor q$ which is readily seen to be in CNF and to be equivalent to $(p\to\neg{q})\to(q\lor\neg{p})$.
However I cannot get the point when they come explain why the method is correct (p. 57-58):
Why does this always work for any formula $\phi$? Well, the constructed formula will be false iff at least one of its conjuncts $\psi_i$ will be false. This means that all the disjuncts in such a $\psi_i$ must be F. Using the de Morgan rule $\neg{\phi_1}\lor\neg{\phi_2}\lor\dots\lor\neg{\phi_n}\equiv\neg{(\phi_1\land\phi_2\land\dots\land\phi_n)}$, we infer that the conjunction of the syntactic opposites of those literals must be true. Thus, $\phi$ and the constructed formula have the same truth table.
May I ask why we can directly conclude $\phi$ and its CNF equivalence have the same truth table just by using the above information?
Best Answer
Consider a formula $\varphi$ (e.g. $p \to q$) and consider its CNF: $C_{\varphi}= D_1 \land \ldots \land D_n$, where each $D_i$ is a disjunction of literals constructed according to the rule above (in the example: $C_{\varphi}= D_1= \lnot p \lor q$).
We have to convince ourselves that to say that the CNF is equivalent to the original formula amounts to saying that the CNF is evaluated to False by a valuation $v$ exactly when the original formula is evaluated to False by $v$.
If $v(\varphi)= \text F$, we consider the corresponding line of the truth table for $\varphi$ and let $D_i$ the corresponding disjunct.
Due to the rule for building the disjunct, we have that all literals in $D_i$ are evaluated to False by $v$, and thus $v(D_i)= \text F$.
Being $C_{\varphi}$ a conjunction where at least one of the conjuncts is False, we will have that $v(C_{\varphi})= \text F$.
Consider now the case when $v(\varphi)= \text T$. This will correspond to a line that does not match any $D_i$.
Thus, for every $D_i$ there will be at least one literal $l_{ij}$ such that if the corresponding propositional variable $p_j$ is evaluated to True [i.e. $v(p_j)= \text T$], then $l_{ij}=p_j$ and if $p_j$ is evaluated to False, then $l_{ij}=\lnot p_j$.
Thus, $v(l_{ij})=\text T$ and also $v(D_i)=\text T$.
But this holds for every $D_i$, that means that $v(C_{\varphi})=\text T$.
Conclusion: