Conjunctive and Disjunctive Normal Forms

Date: 09/25/2000 at 17:39:44
From: Patrick
Subject: Disjunctive Normal Form

Let's say I have a function:

     F(a,b,c,d) = ab'c + bc'd

Then the DNF is:

     DNF = ab'c(d + d') + (a + a')bc'd 
         = ab'cd + ab'cd' + abc'd + a'bc'd
 
The CNF would be the compliment of the compliment of the original 
function.

How do you obtain the CNF (the product of sums)? 

Any help you could give me would be greatly appreciated.

Thanks.

Date: 10/02/2000 at 10:51:39
From: Doctor TWE
Subject: Re: Disjunctive Normal Form

Hi Patrick - thanks for writing to Dr. Math.

A Boolean expression is in disjunctive normal form (DNF) if:

   1. the variables within each term are ANDed together,

   2. the terms are ORed together, and

   3. every variable or its complement is represented in every term 
      (i.e. either A or ~A is in each term, B or ~B is in each term, 
      etc.).

   4. No parentheses or other Boolean operations appear in the 
      expression.

For example, ~A~BC + ~AB~C + ABC. (This is "not A and not B and C, or 
not A and B and not C, or A and B and C." I'm assuming that without 
parentheses, ANDs take precedence over ORs - kind of the way  
multiplication is done before addition.) This is in DNF because:

   1, 2. There are three terms; the first term is ~A~BC, the second 
         term is ~AB~C and the third term is ABC. Note that the
         "terms" are defined by the way the variables are ANDed and 
         ORed.

   3. Every term has either A or ~A, B or ~B, and C or ~C. These are 
      the only variables in the expression.

   4. There are no parentheses and no other Boolean operations (like 
      exclusive-ors, etc.)

The following are NOT in DNF:

1. (~A+B+C)(A+B+~C)   
   Reason: Terms are ANDed, variables are ORed. (This is actually in  
   conjunctive normal form - see below.)

2. ~AB + AB~C   
   Reason: Not every term has all variables. (First term is missing a
   C or ~C.)

3. A(BC + ~B~C)   
   Reason: Parentheses present.

4. ABC (+) ~A~B~C   
   Reason: Other Boolean operators present. [The '(+)' represents    
   'exclusive-or'.]

The rules for conjunctive normal form (CNF) are similar to the rules 
for DNF except for the precedence of the ANDs and ORs. A Boolean 
expression is in CNF if:

   1. the variables within each term are ORed together,

   2. the terms are ANDed together, and

   3. every variable or its complement is represented in every term 
      (i.e. either A or ~A is in each term, B or ~B is in each term, 
      etc.).

   4. No parenthesis - other than those separating the terms - or 
      other Boolean operations appear in the expression.

For example, (~A+B+C)(~A+~B+~C)(A+~B+C). (This is "not A or B or C, 
and not A or not B or not C, and A or not B or C.") This is in CNF 
because:

   1, 2. There are three terms; the first term is ~A+B+C, the second 
         term is ~A+~B+~C and the third term is A+~B+C. Note that the 
         "terms" are again defined by the way the variables are ANDed 
         and ORed, but this time the variables must be ORed within the 
         terms, and the terms must be ANDed.

   3. Every term has either A or ~A, B or ~B, and C or ~C. These are 
      the only variables in the expression.

   4. The only parentheses are those separating the terms, and no 
      other Boolean operations (like exclusive-ors, etc.) appear in 
      the expression.

The following are NOT in CNF:

1. ~AB~C + ABC   
   Reason: Terms are ORed, variables are ANDed. (This is in DNF.)

2. ~A(~B+C)(B+~C)   
   Reason: Not every term has all variables. (First term, ~A, is     
   missing a B or ~B and C or ~C. Second and third terms each missing
   A or ~A.)

3. ~C(~A(~B+AC)+B)   
   Reason: Improper use of parentheses.

4. (A(+)B(+)C)(~A(+)~B(+)~C)   
   Reason: Other Boolean operators present. [The '(+)' represents     
   'exclusive-or'.]

The method you suggest for converting a DNF expression into CNF 
actually produces the complement of a CNF expression, not a CNF 
expression itself. For example, suppose we had the DNF expression:

     ~A~BC + ~AB~C + ~ABC + A~BC

First, we double negate it:

     ~[~(~A~BC + ~AB~C + ~ABC + A~BC)]

Then we use DeMorgan's theorem to eliminate the inner negation [this 
breaks up the negation by converting the ORs to ANDs; ~(P+Q) = ~P~Q]:

     ~[~(~A~BC)~(~AB~C)~(~ABC)~(A~BC)]

Next, we use DeMorgan's theorem again to break up the inner 
disjunctions [this time we'll use the form ~(PQ) = ~P + ~Q]:

     ~{[~(~A)+~(~B)+~C][~(~A)+~B+~(~C)][~(~A)+~B+~C][~A+~(~B)+~C]}

Now we'll use double negation to get rid of the excess negations:

     ~[(A+B+~C)(A+~B+C)(A+~B+~C)(~A+B+~C)]

Note that what we wind up with is the complement of a CNF expression. 
The part in the square brackets [...] is a CNF expression, but the 
result we got is its complement.

One technique to get a CNF expression given the DNF expression is as 
follows. First write down every combination of each variable or 
complement. There should be 2^n (where n is the number of variables) 
combinations. For example, for A, B and C the 2^3 = 8 combinations 
are:

     ~A~B~C
     ~A~B C
     ~A B~C
     ~A B C
      A~B~C
      A~B C
      A B~C
      A B C

Next, cross out all combinations in the original DNF expression. For 
~A~BC + ~AB~C + ~ABC + A~BC, we would cross out the second, third, 
fourth, and sixth combinations (as I've listed them):

     ~A~B~C
     ------
     ------
     ------
      A~B~C
     ------
      A B~C
      A B C

Then we negate each variable on the list of remaining terms:

      A B C
     ------
     ------
     ------
     ~A B C
     ------
     ~A~B C
     ~A~B~C

Finally, we write an expression in CNF using the variable combinations 
left on the list. For CNF, we OR the variables within the terms and 
AND the terms together:

     (A+B+C)(~A+B+C)(~A+~B+C)(~A+~B+~C)

The resulting expression is the CNF equivalent of the original DNF 
expression. We can prove this by truth table:

      A B C | ~A~BC ~AB~C ~ABC A~BC | DNF
     -------+-----------------------+-----
      0 0 0 |   0     0    0    0   |  0
      0 0 1 |   1     0    0    0   |  1
      0 1 0 |   0     1    0    0   |  1
      0 1 1 |   0     0    1    0   |  1
      1 0 0 |   0     0    0    0   |  0
      1 0 1 |   0     0    0    1   |  1
      1 1 0 |   0     0    0    0   |  0
      1 1 1 |   0     0    0    0   |  0


      A B C | A+B+C ~A+B+C ~A+~B+C ~A+~B+~C | CNF
     -------+-------------------------------+--------
      0 0 0 |   0      1      1       1     |  0
      0 0 1 |   1      1      1       1     |  1
      0 1 0 |   1      1      1       1     |  1
      0 1 1 |   1      1      1       1     |  1
      1 0 0 |   1      0      1       1     |  0
      1 0 1 |   1      1      1       1     |  1
      1 1 0 |   1      1      0       1     |  0
      1 1 1 |   1      1      1       0     |  0

Since the final columns of the truth tables are identical, the 
expressions are equivalent.

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/