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

Question | How To Convert From CNF TO DNF?

  1. Jul 12, 2009 #1
    using de' morgan Lows.
    thanks!
     
  2. jcsd
  3. Jul 12, 2009 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you know what De Morgan's Laws are?
     
  4. Jul 12, 2009 #3
    Yes...why?
     
  5. Jul 12, 2009 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And do you know what conjunctive and disjunctive normal form are? This is fairly straightforward, why don't you post what the definition of everything is and describe where you're stuck
     
  6. Sep 27, 2009 #5
    Despite this being "fairly straightforward", I don't get it.

    Say you have something like (AB)+(CD). If you apply De Morgan's, you get something like ((A'+B')(C'+D'))', no? But now you've got this negation around the whole thing, so it's not in CNF. Conversely, if you start with something like (A+B)(C+D), you end up with ((A'B')+(C'D'))', don't you? But that's not DNF, because there's a negation around it.

    Can you really convert from CNF to DNF and visa versa using De Morgan's laws; if so, how do you do it? If not, what procedure should you use?

    If I think about it heuristically, I can see that (A+B)(C+D) = AC + AD + BC +BD, but I don't see a general procedure. Is it just that 'multiplying' it out is the manual procedure?
     
  7. Sep 27, 2009 #6
    You almost got it. But you must apply de Morgan's law twice because
    for every Boolean function f we have: f = f ''

    So let's say f = (AB)+(CD). Then, f = f '' = [ (AB)+(CD) ]'' = [ (A'+B')(C'+D') ] '
    Then, use the distributive law within the [] brackets:
    [ (A'+B')(C'+D') ]' = [ A'C' + A'D' + B'C' + B'D' ]' = (A+C) (A+D) (B+C) (B+D)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question | How To Convert From CNF TO DNF?
  1. CNF to DNF (Replies: 2)

Loading...