A Proof relating to the Disjunctive normal form 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!
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
Show that ¬ and ∧ form a functionally complete collection
of logical operators. [Hint: First use a De Morgan
law to show that p ∨ q is logically equivalent to
¬(¬p ∧ ¬q)