2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Do you want a proof for each of the rewriting rules that work in terms of interpretations but doesn't mention truth tables? That will be somewhat difficult, because the definition of how an interpretation applies to, say, $\varphi\to\psi$ is usually by looking up the result in a truth table for $\to$, based on what $\varphi$ and $\psi$ produce for the interpretation. It is that truth table that defines how the connective behaves at all. $\endgroup$
    – hmakholm left over Monica
    Oct 29, 2014 at 0:13

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .