[Math] A Proof relating to the Disjunctive normal form

discrete mathematicspropositional-calculus

Here is a problem from Kenneth Rosen's Discrete Mathematics and its Applications, Section 1.3

Suppose that a truth table in $n$ propositional variables is specified.
Show that a compound proposition with this truth table can be formed
by taking the disjunction of conjunctions of the variables or their
negations, with one conjunction included for each combination of
values for which the compound proposition is true. The resulting
compound proposition is said to be disjunctive normal form.

I have been stuck in this question for quite some time and I would really appreciate a nudge in the right direction.

This is a homework problem and I am not expecting a complete answer. However, what I would like is to get a feel of what a Disjunctive Normal form is. I have been looking it up on the internet but no explanation is a good enough explanation for me. I would really appreciate an explanation.

Thanks a lot!

Best Answer

This example is for explanation of what a Disjunctive Normal form is, On purpose i don't simplify the resulting formula, The question is about homework and it should stay homework.

suppose you have the truth table:

P  Q    Value
T  T      T
T  F      T
F  T      F
F  F      T   

and you want to transform that into a formula in the Disjunctive Normal form.

First add to the true values the formula that makes that row valid

P Q Value formula
T T T $ (P \land Q )$
T F T $ (P \land \neg Q )$
F T F ------------------ (this value is false so don't mention formula)
F F T $ (\neg P \land \neg Q )$

(sorry had some problems with the layout)

and then or them together

$ (P \land Q ) \lor (P \land \neg Q ) \lor (\neg P \land \neg Q ) $

And this formula is in Disjunctive Normal form.

notice this formula can be simplified but that is out of scope for this answer, see
http://en.wikipedia.org/wiki/Disjunctive_normal_form
and http://en.wikipedia.org/wiki/Karnaugh_map for that.

Good luck