Conjunctive and Disjunctive Normal FormsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/