Associated Topics || Dr. Math Home || Search Dr. Math

### 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)?

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/
```
Associated Topics:
College Logic
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search