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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.