Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!


  1. Jan 24, 2005 #1
    Will this method always convert a CNF formula to an equivalent DNF formula:

    1. negate the ENTIRE formula
    2. negate each literal
    3. simplify using DeMorgan's laws

    For example, given:

    A:&\quad(p \vee q) \wedge (q \vee r ) \wedge (p \vee r )\notag \\
    &\quad\overline{(\overline p \vee \overline q) \wedge (\overline q \vee \overline r) \wedge (\overline p \vee \overline r )}\notag \\
    &\quad\overline{(\overline p \vee \overline q)} \vee \overline{(\overline q \vee \overline r)} \vee \overline{(\overline p \vee \overline r )}\notag \\
    B:&\quad(p \wedge q) \vee (q \wedge r ) \vee (p \wedge r )\notag \\

    A truth table shows that A and B are equivalent. But is this valid for ANY formula?
  2. jcsd
  3. Jan 25, 2005 #2
    No; for example, it does not work on (p + q).(q + r). You would get (p.q) + (q.r) which is not equivalent since when q is true and p and r are false, the formulas yield different truth values.
  4. Jan 25, 2005 #3
    You're right. Thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook