# Disjunctive Normal Form (DNF) of a boolean combination

Upon revisiting chapter 1 of Robert S. Wolf's "A tour though mathematical logic" I sumbled upon the following Proposition on page 13 :

Suppose that $P$ is a Boolean combination of statements $Q_1,Q_2, \ldots , Q_n$. Then there is a statement that is propositionally equivalent to $P$ and is in disjunctive normal form with respect to $Q_1,Q_2, \ldots, Q_n$, meaning a disjunction of conjunctions of the $Q_i$'s and their negations

This is accompanied by the following "proof":

Essentially, the disjunctive normal form of a statement comes directly from its truth table. Each row of the truth table with output T indicates one of the conjunctions whose disjunction must be taken.

I am a weary of the informality of the proof , and I went searching for a more formal proof.

Most of the potential proofs that I found seem to rely on a through discussion of First order language. Which is discussed later on in the chapter.

So is a more formal proof possible without definition and a discussion of first order logic

See Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001), page 47 :

Theorem 15B : Let G be an $n$-place Boolean function, $n \ge 1$. We can find a wff $\alpha$ such that $G = B^n_{\alpha}$, i.e., such that $\alpha$ realizes the function G

where :

Suppose that $\alpha$ is a wff whose sentence symbols are at most $A_1,..., A_n$. We define an $n$-place Boolean function $B^n_{\alpha}$, the Boolean function realized by $\alpha$, by :

$B^n_{\alpha}(X_1,..., Х_n)$ = the truth value given to $\alpha$ when $A_1, ..., A_n$ are given the values $X_1, ..., X_n$.

Then [page 49] :

Corollary 15C : For any wff $\varphi$, we can find a tautologically equivalent wff $\alpha$ in disjunctive normal form.