2.4: Disjunctive Normal Form (DNF)

Disjunctive Normal Form (DNF) is a standard way to write Boolean functions. It can be described as a sum of products, and an OR and ANDS³. To understand DNF, first the concept of a minterm will be covered.

A minterm is a row in the truth table where the output function for that term is true. For example, in Table 2.3.3, the function f1(A,B,C) has a minterm when A=1, B=0, and C=0. We can write this minterm a AB'C' (A and not-B and not-C), since A is true, and B and C are both false. Function f1(A,B,C) also has three other minterms, AB'C, ABC', and ABC. So the DNF for the function f1(A,B,C) would be written as:

f1(A,B,C) = AB'C' + AB'C + ABC' + ABC

Note that these minterms are numbers 4, 5, 6, and 7⁴ in the table so a short hand to write the DNF is the following:

f1(A,B,C)= Σ(4,5,6,7)

Likewise f2(A,B,C) can be written as:

f2(A,B,C) = A'B'C + A'BC + AB'C + ABC =Σ(1, 3, 5, 7)

Note that any Boolean function can be written in DNF, and DNF requires only 3 types of operations, the AND, OR, and NOT. This is why AND, OR, and NOT are universal. The proof of this is left for the exercises at the end of the chapter.

\(\PageIndex{1}\) Boolean Relationships

The next question to be asked is if any Boolean function can be written in DNF, should DNF be used to represent all Boolean functions? The answer to this question comes from the engineering the circuit. At some point, a computer has to implement the Boolean function as a circuit. That circuit will need 1 gate for each operation. And in engineering the circuit, the goal is to minimize the number of gates needed.

Why should the number of gates be minimized? When a gate is actually included in a circuit, it has 3 bad effects:

• Every gate requires power to operate it. The more gates in the circuit means that power will be needed to operate the computer.
• Since gates require power, they produce heat as a result. More gates mean more heat from the CPU.
• There are always delays in propagating the signal across the gates. The speed of light is very fast, but it is not infinite. The further the electricity has to go to reach the end of the circuit, the longer it takes. So the more gates in the circuit, the slower the CPU. And in modern computers, the speed of light is often the limiting factor in how fast the CPU can cycle, and thus in the speed of the CPU.

Thus the goal in any circuit design is to limit the number of gates in the circuit. For the function f1(A,B,C) in Table 2.3.3, the number of AND gates is 8, or gates is 3, and not gates is 4, or a total of 15 gates. The question is whether or not the circuit can be implemented in less than 15 gates.

Boolean algebra is the mechanism which is used to answer this question. Boolean algebra is just like traditional algebra in that there are a set of relationships that can be applied to a function to transform it. And those operations are generally somewhat analogous to the operations in traditional algebra, making the transition to Boolean algebra somewhat easier. A list of these relationships is given in table \(\PageIndex{1}\).

Table \(\PageIndex{1}\)

Relationship	Rule No.	Relationship	Rule No.
x+0=x	1	x*0=0	2
x+1=1	3	x*1=x	4
x+x =x	5	x*x=x	6
x+x’=1	7	x*x’=0	8
x+y=y+x	9	xy=yx	10
x+(y+z)=(x+y)+z	11	x(yz) = (xy)z	12
x(y+z)=xy+yz	13	x+yz=(x+y)(x+z)	14
(x+y)’ = x’y’	15	(xy)’=x’+y’	16
(x’)’ = x	17

All of these relationships except for 15 and 16 should can be easily derived. Relationships 15 and 16 are known as DeMorgan's Laws, and should simply be memorized.

Applying these relationships for f1(A,B,C), we find the following:

f1(A,B,C)

= AB'C' + AB'C + ABC' + ABC = AB'(C'+C) + AB(C'+C) (rule 13) = AB'(1) + AB(1) (rule 7) = AB' + AB (rule 4) = A(B'+B) (rule 13) = A(1) (rule 7) = A (rule 4)

This expression is obviously simpler than the original, and the number of gates needed for this circuit has been reduced from 15 to 0. This reduction was obviously worth the effort.

But how did we know to continue to reduce this expression after "AB' + AB"? This was a significant reduction in itself, form 15 to 4 gates. Since we have now shown that DNF does not necessarily (and often does not) result in a minimum expression, how can we know if a minimum expression has been reached? That is the topic of the next section of this chapter.

---

³ Another way to represent the function is Conjunctive Normal Form (CNF). CNF can be described as a product of sums, or an AND or ORs. The use of CNF is left to the problems at the end of the chapter.
⁴ Note that the number starts at 0, not 1.