Question | How To Convert From CNF TO DNF?

[gabaygu]

using de' morgan Lows.
thanks!

 

[Office_Shredder]

Do you know what De Morgan's Laws are?

 

[gabaygu]

Yes...why?

 

[Office_Shredder]

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

 

[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?

 

[Edgardo]

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.

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)