Every first-order logic formula without quantifiers can be written in disjunctive normal form.

Question

I'm trying to prove the fact that every first-order logic formula without quantifiers can be written in disjunctive normal form (Disjunction of conjuctions) of atomic formulas and their negations; however, I'm having problem in the inductive step:

Let $\varphi = (\neg \psi)$, by induction hypothesis $\psi = \bigvee\limits_{i=1}^{m} \bigwedge\limits_{j=1}^{n} \sigma_{ij} $ where $\sigma_{ij}$ is an atomic formula, then using De Morgan: $$ \varphi = \bigwedge\limits_{i=1}^{m} \bigvee\limits_{j=1}^{n} (\neg\sigma_{ij}) $$

How do I get the normal disjunctive form?

Answer 1

You can always distribute the $\land$'s over the $\lor$'s.

For example,

$$(P \lor Q)\land (R \lor S) \Leftrightarrow (P \land R) \lor (P \land S) \lor (Q \land R) \lor (Q \land S)$$