The Explanation on how to form CNF

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?

• @Algebruh yes, in the example they use some lines from the original truth table to build the CNF. I just don't understand the part that "[...] all the disjuncts in such a $\psi_i$ must be F [...], we infer that the conjunction of the syntactic opposites of those literals must be true." and they directly conclude two formulas have the same truth table. Commented Apr 2, 2021 at 8:58
• If I get the citation right, you use some parts of the truthtable of $\phi$ to construct an equivalent formula $\phi′$ in CNF? Truthtables describe all outcomes of a formula for any possible value on every variable. EDIT: While constructing a normal form you pick for example all rows with outcome true. All remaining cases are the ones with outcome false. Commented Apr 2, 2021 at 9:00
• The dual of this is probably easier to understand: you can construct a DNF from the truth table, by identifying each true row in the truth table with a conjunction of literals which is true iff the assignment matches that row. Commented Apr 2, 2021 at 12:02

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:

for every valuation $$v, \ v(\varphi)=\text T \text { iff } v(C_{\varphi})=\text T$$.