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!

  • $\begingroup$ It doesn't seem stated quite right as a question. If you have a wff with at least three-variables like ApAqr (I use Polish notation), then you have conjunctions like KKpqr, which means you've used two conjunctions. If the author wants to introduce an n-ary conjuction preferably would make clear how to do that first, and show how they can get derived from the binary conjunction connective that you start with. $\endgroup$ – Doug Spoonwood Sep 9 '13 at 16:31

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
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)


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.