The existence of conjunctive/disjunctive normal forms?

Question

I am studying propositional logic/calculus and I am currently learning about normal forms. The algorithm to construct a conjunctive/disjunctive normal form from any given formula is straightforward. I analyzed some examples via truth/semantic tables but it's still not very clear to me why this works i.e. why are the conjunctive/disjunctive normal form versions of a given formula equivalent to the original formula.

Could you recommend a book(s)/website/... where I could find a proof about the equivalence of a formula and it's conjunctive/disjunctive normal form (or maybe provide a proof here)?

I would very much appreciate a proof in terms of "interpretations" where an interpretation is every mapping from the set of all propositional variables to the set $\{0,1\}$ i. e. $$I : \{P_0, P_1, P_2, ...\} \to \{ 0, 1 \}$$ where $\{P_0, P_1, P_2, ...\} $ is the set (an infinite countable set) of all propositional variables, instead of a proof with truth tables, i.e. "If we have $n$ variables, we have $2^n$ rows, ... , consider the $i$-th row ...".

Answer 1

The procedure to convert a formula into conjunctive (or disjunctive) normal form can be presented in several different ways, but one of them is to do it as a series of small local rewritings:

1. First get rid of all implications by the rule $p\to q \equiv \neg p \lor q$.

2. Then push all negations down to atomic formulas using De Morgan's rules and double-negation elimination.

3. Finally distribute conjuctions over disjunctions or vice versa, depending on which normal form you want.

Convincing oneself that the whole thing works is then just a matter of seeing that each little rewriting rule you use along the way take formulas to equivalent formulas.

Answer 2

For a similar discussion, see this post.

Anyway, if you are looking for additional information, the following links may be useful for you:

• There is a simple proof for the propositional calculus and the conjunctive normal form here.
• There are some useful information in the Wikipedia's entry about conjunctive normal form.

The proof simple: it follows exactly the steps described in the answer above.