# Question | How To Convert From CNF TO DNF?

1. Jul 12, 2009

### gabaygu

using de' morgan Lows.
thanks!

2. Jul 12, 2009

### Office_Shredder

Staff Emeritus
Do you know what De Morgan's Laws are?

3. Jul 12, 2009

### gabaygu

Yes...why?

4. Jul 12, 2009

### Office_Shredder

Staff Emeritus
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

5. Sep 27, 2009

### luddite

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?

6. Sep 27, 2009

### Edgardo

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)