# Show that every well formed formula has a disjunctive and a conjunctive normal form.

If $\varphi$ is a $wff$, then there exist $\varphi^c$ and $\varphi^d$ on conductive normal form and disjunctive normal form respectively, such that $\varphi \sim \varphi^c$ and $\varphi \sim \varphi^d$.

I tried to prove it using induction. For the first case, $\top$ and $\bot$ are trivially $DNF$'s and $CNF$'s, and so is $p \in \Sigma$ for every $p$.

Now for the induction process, let's first consider the case where $\varphi = \neg \chi$ for some $\chi \in L_{\Sigma}$, assuming that $\chi$ has already both a $DNF$ and a $CNF$. Then, using De Morgan's laws, $$\varphi = \neg \chi \sim \neg \chi^d = \neg \left( \bigvee_{i=1}^n \bigwedge_{j=1}^m \xi_{ij}\right) = \bigwedge_{i=1}^n \left( \neg \bigwedge_{j=1}^m \xi_{ij}\right) = \bigwedge_{i=1}^n \bigvee_{j=1}^m(\neg \xi_{ij})$$ which is a $CNF$ for $\varphi$. Similary, $$\varphi = \neg \chi \sim \neg \chi^c = \neg \left( \bigwedge_{i=1}^n \bigvee_{j=1}^m \xi_{ij} \right)= \bigvee_{i=1}^n \left( \neg \bigvee_{j=1}^m \xi_{ij}\right) = \bigvee_{i=1}^n \bigwedge_{j=1}^m (\neg\xi_{ij})$$ which is a $DNF$ for $\varphi$. The problem now comes when dealing with the connectives $\vee, \wedge, \rightarrow, \leftrightarrow$. Any help with that would be highly appreciated. Thank you.

Assume $\varphi = \chi_1 \land \chi_2$

Then $$\varphi = \chi_1 \land \chi_2 \sim \chi_1^d \land \chi_2^d = \left( \bigvee_{i=1}^n \bigwedge_{j=1}^m \xi_{1ij} \right) \land \left( \bigvee_{i=1}^n \bigwedge_{j=1}^m \xi_{2ij} \right)$$

Now distribute $\land$ over $\lor$ ... sorry, there is no nice way to put that into a formula, but just to give an example:

$\chi_1^d = (\xi_{111} \land \xi_{112}) \lor (\xi_{121} \land \xi_{121})$

$\chi_2^d = (\xi_{211} \land \xi_{212}) \lor (\xi_{221} \land \xi_{221})$

Then

$$\chi_1^d \land \chi_2^d = ((\xi_{111} \land \xi_{112}) \lor (\xi_{121} \land \xi_{121})) \land (\xi_{211} \land \xi_{212}) \lor (\xi_{221} \land \xi_{221}) =$$

$$(\xi_{111} \land \xi_{112} \land \xi_{211} \land \xi_{212}) \lor (\xi_{111} \land \xi_{112} \land \xi_{221} \land \xi_{221}) \lor (\xi_{121} \land \xi_{122} \land \xi_{211} \land \xi_{212}) \lor (\xi_{121} \land \xi_{122} \land \xi_{221} \land \xi_{221})$$

and so is in DNF

Similar for the others ...

• Thank you! I was trying to work on that, but the calculations were too tedious and I thought I was doing something wrong. So once done for $\vee$ and $\wedge$, I can just invoke De Morgan's laws for $\rightarrow$ and $\leftrightarrow$, right? – user313212 Mar 21 '17 at 20:48
• Well, use $\varphi \rightarrow \psi \sim \neg \varphi \lor \psi$ and $\varphi \leftrightarrow \psi \sim (\varphi \land \psi) \lor (\neg \varphi \land \psi)$ to rewrite to $\land$, $\lor$, and $\neg$, and then you can point to the fact that we just proved this for $\land$ and $\lor$ (and to show the $\lor$ you could indeed appeal to DeMorgan and use the fact that we just showed it for the $\neg$ and the $\land$) – Bram28 Mar 21 '17 at 20:52

"Brute force" proofs by induction are often not the most illuminating proofs, and may give us little intuition why something should be true.

That, perhaps, is the case here. So I really wouldn't encourage following your route! The elementary textbook proof surely gives us more insight. I'm thinking of the following line of proof that a non-contradictory $\varphi$ has a DNF (leaving this case for special treatment).

Consider the truth-table for $\varphi$ giving it as a truth-function of its constituent atoms.

Take the lines where $\varphi$ comes out true (there is at least one by hypothesis). For each such line form the basic conjunction of atoms and negations corresponding to the assignment of values on that line. For example, if we are on the line where $P \Rightarrow T, Q \Rightarrow F, R \Rightarrow T$, form the conjunction $(P \land \neg Q \land \neg R)$.

Disjoin those conjunctions and we have a wff in DNF which is true whenever $\varphi$ is true.

This simple and direct line of proof tells us why wffs have a DNF equivalent.

(To prove $\varphi$ has a CNF, make use of the fact that $\neg\varphi$ has a DNF, take negations and use De Morgan's Laws, etc.)

• Thank you for your answer! It does indeed provide more insight than my "brute force" argument, but I find it more difficult to write down the general case, that is, an arbitrary $\varphi$ with a general truth table and so, than with the induction hypothesis that if $\varphi = \chi_1 \square \chi_2$, then $\chi_1$ and $\chi_2$ have a $CNF$ and a $DNF$ – user313212 Mar 22 '17 at 8:11