Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is disjunctive normal form.

http://en.wikipedia.org/wiki/Disjunctive_normal_form

I understand what it is. However, I lack a systematic way of converting any complicated expression into it.

For instance, should I expand all negations with DeMorgan's rules first? Should I distribute ANDs over ORs first? Is there a systematic way to do this conversion?

share|improve this question
1  
You can make Truth table for your logical expression , then deduce from it DNF...and after that if you wish you can minimize DNF using Karnaugh map... –  pedja Feb 4 '12 at 5:23
1  
@pedja Of course Karnaugh maps don't work well all that well when you have too many variables in the formula. –  Doug Spoonwood Feb 4 '12 at 14:11
add comment

2 Answers

up vote 3 down vote accepted

In addition to the truth table method described by André, there is also a syntactical approach:

First push the negations down to the leaves of the syntax tree using De Morgan's laws and double-negation elminiation.

Then float the disjunctions to the top using the distributive law $a\land(b\lor c)=(a\land b)\lor(a\land c)$.

This will often create shorter DNF's -- but there is still a risk of exponential blowup, of course.,

share|improve this answer
add comment

This answers the "is there a systematic way" part of your question, but not in a manner that solves your actual problem. So you should look briefly at it, and then disregard it, and listen to those who provide practical advice relevant to homework/tests.

Take a specific expression $\mathcal{E}$, say involving the propositional variables $P$, $Q$, $R$, and $S$. In principle the number of propositional variables doesn't matter.

1. Produce the complete truth-table for $\mathcal{E}$. This is a purely mechanical albeit lengthy procedure. For if $\mathcal{E}$ has $n$ propositional variables, the truth table will have $2^n$ rows. We are only interested in the truth values of the variables for which $\mathbb{E}$ is true, and the logical structure of $\mathbb{E}$ may suggest useful shortcuts.

2. Suppose that, for example, among other rows in your truth-table, $\mathcal{E}$ is true when $P$ is true, $Q$ is false, $R$ is false, and $S$ is true.

Produce the conjunction $(P\land \lnot Q \land \lnot R \land S)$.

Do this sort of thing for every combination of truth values that make $\mathcal{E}$ true.

3. You will get a bunch, possibly a very large bunch, of conjunctions. Put these conjunctions together with disjunctions ($\lor$). End of algorithm.

To see that the algorithm works, note that the disjunctive normal form (DNF) so produced is true precisely for those truth assignments to the propositional variables that make $\mathbb{E}$ true. So our DNF is logically equivalent to $\mathbb{E}$. The DNF produced by this algorithm is sometimes called the canonical DNF.

Remark: However, the above is probably not what you are expected to do.

Even for a "small" example, the execution time of this procedure can be painfully long. The real practical downside is that the DNF produced by the algorithm can be grossly inefficient. There are usually far simpler DNF's for the same expression $\mathbb{E}$. So if we use disjunctive normal form for circuit design, the above algorithm, though simple, will often produce impractically large circuits. There are systematic procedures for then reducing the complexity of circuits, but they can be painful for hand computation.

share|improve this answer
    
There is nice free software "Logic Friday 1"... –  pedja Feb 4 '12 at 5:33
    
@pdja: Thanks, I am so out of touch with what is available nowadays. Antique mainframes, that's another matter. –  André Nicolas Feb 4 '12 at 5:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.