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

Question

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.

Answer 1

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 ...

Answer 2

"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.)