# Boolean Disjunctive Normal Form

• Nov 5th 2011, 02:49 AM
terrorsquid
Boolean Disjunctive Normal Form
I'm trying to get $f(a,b,c) = (a'b)'(a+c)'+a(c+b')+ab'(c+a')$ into DNF and was wondering what happens when I get terms that don't have all three boolean algebras in them or two of the same in a group?

Solving, I get:

$(a+b')(a'c')+(ac+ab')+(ab'c+ab'a')$

$aa'c'+b'a'c'+ac+ab'+ab'c+ab'a'$

Do I just drop everything other than $b'a'c'$ and $ab'c$?
• Nov 5th 2011, 03:23 AM
emakarov
Re: Boolean Disjunctive Normal Form
Quote:

Originally Posted by terrorsquid
what happens when I get terms that don't have all three boolean algebras

Boolean variables.

We have xx = x, x'x' = x', xx' = 0, and x0 = 0. Therefore, when a literal (a variable or its negation) occurs several times in a conjunction, just one occurrence can be left. If two opposite literals (x and x') occur in a conjunction, the whole conjunction is always false and can be removed.

Finally, what you do when not all variables occur in a conjunction depends on the definition of the DNF. According to Wikipedia, DNF that requires variables to appear exactly once in every clause is called full DNF. If you need that, use the fact that x1 = x and 1 = x + x'. So, e.g., ac = a1c = a(b + b')c = abc + ab'c.