Google Answers Logo
View Question
Q: WFF to DNF algorithm ( Answered 5 out of 5 stars,   0 Comments )
Subject: WFF to DNF algorithm
Category: Science > Math
Asked by: krokodil-ga
List Price: $10.00
Posted: 04 Jan 2005 19:52 PST
Expires: 03 Feb 2005 19:52 PST
Question ID: 452083
I am looking for clear description of an algorithm which could be used to 
convert arbitrary well formed proposition logic formula (WFF) into 
disjuntive normal form (DNF). Original formula uses only OR, AND and
NOT operations. I am not looking for sophisticated high-performace
algorithm - a basic one will do. The algorithm should not use truth tables, 
but rather work with formula in symbolic form.
Subject: Re: WFF to DNF algorithm
Answered By: mathtalk-ga on 06 Jan 2005 06:46 PST
Rated:5 out of 5 stars
A formula of the propositional calculus is said to be in disjunctive
normal form (DNF) if it is a disjunction of elementary conjunctions. 
An elementary conjunction is a conjunction of some combination of
propositional variables and negations of propositional variables.

 1. Distribute negation (NOT) over any conjunctions or disjunctions
according to deMorgan's laws:

  ~(p & q) = ~p OR ~q

  ~(p OR q) = ~p & ~q

until negation is only applied to atomic propositions (propositional
variables). Remove double negations where these arise.  A
propositional variable or its negation will be called an elementary
proposition below.

 2. The algorithm then proceeds recursively on the results of the
first step.  The DNF of "P OR Q" is simply:

  (DNF(P)) OR (DNF(Q))

The DNF of "P & Q" is more complicated.  Start by finding the DNF of P, say:

   P_1 OR P_2 OR ... OR P_m

and the DNF of Q, say:

   Q_1 OR Q_2 OR ... OR Q_n

where each P_i, Q_j is a conjunction of elementary propositions.  Then
the DNF of "P & Q" is obtained as the disjunction of all possible
pairs of distributed conjunctions:

   ... OR ( P_i & Q_j ) OR ...

where I mean that the various elementary propositions of P_i and Q_j
are now to be conjuncted to form a single disjunction of the DNF for
"P & Q".

3. Optionally you may remove "inner" conjunctions which happen to
contain both an atomic proposition and its negation as these are
"false".  You may also remove duplicates of elementary propositions in
an "inner" conjunction.  Finally if the exact same "inner" conjunction
appears more than once in the "outer" disjunction, that duplication
can be eliminated by removing one copy.

Further pruning of the DNF may be possible but is not necessary in
order to satisfy the definition.  Such pruning is useful if one wishes
to obtain a "canonical" form of a formula, ie. to recognize when two
formulas are equivalent (in particular when a formula is tautologous),
but I'm not sure if this is important for your application.


  The disjunctive normal form is "dual" to the conjunctive normal form
(CNF), where the outer operation is a conjunction of elementary
disjunctions.  Any WFF of the propositional calculus can be expressed
in DNF or CNF.

  An empty conjunction is considered "true", by analogy with an empty
product being 1.  An empty disjunction is considered "false", by
analogy with an empty sum being 0.  This is consistent with the
proposed pruning/simplification rules above, as removing an obvious
"false" term from a disjunction should be interpreted as finally
"false" if all terms are removed.

regards, mathtalk-ga
krokodil-ga rated this answer:5 out of 5 stars
Exactly what I wanted. Thanks.

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy