This document describes graphical and algebraic ways to minimize boolean functions. It includes a Java program that you can use to experiment with the algebraic algorithm outlined below. The subject of minimization is also covered in many textbooks, articles, and other web sites. Here are a few references:

All the datapath and control structures of a digital device can be represented as boolean functions, which take the general form:

*y = Σ(x, … )*

where “*(x, … )*” is a set of *boolean variables* (variables that
may take on only the values zero and one). These boolean functions must be converted into logic networks in the
most economical way possible. What qualifies as the “most economical way possible” varies, depending
on whether the network is built using discrete gates, a programmable logic device with a fixed complement of gates
available, or a fully-customized integrated circuit. But in all cases, minimization yields a network with as
small a number of gates as possible, and with each gate as simple as possible.

To appreciate the importance of minimization, consider the two networks in **Figures 1
**and** 2**. Both behave exactly the same way! No matter what pattern of ones and zeros you
put into *a*, *b*, and *c* in Fig. 1, the value it produces at *y* will be exactly
matched if you put the same pattern of values into the corresponding inputs in Fig. 2. Yet the network in Fig. 2
uses far fewer gates, and the gates it uses are simpler (have smaller fan-ins) than the gates in Fig. 1. Clearly,
the minimized circuit should be less expensive to build than the unminimized version. Although it is not true for
Fig. 2, it is often the case that minimized networks will be faster (have fewer propagation delays) than
unminimized networks.

- The variables in the expression on the right side of a boolean equation are the input wires to a logic network. The left side of a boolean equation is the output wire of the network.
- Any boolean equation or combinational logic network can be completely and exactly characterized by a
*truth table*. A truth table lists every possible combination of values of the input variables, and the corresponding output value of the function for each combination. There are 2^{n}rows in the truth table for a function or network with*n*input variables, so it isn’t always practical to write out an entire truth table. But for relatively small values of*n*, a truth table provides a convenient way to describe the function or network’s behavior exactly. - Every row of a truth table with a one in the output column is called a
*minterm*. A convenient way to represent a truth table is to treat each combination of input variables as a binary number and to list the numbers of the rows that are minterms.This document uses the function with the following truth table as a running example:

a b c Y 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 This truth table can also be represented as the list of minterms, [ 1, 2, 4, 5, 6, 7 ]. That is, the truth table has a 1 in the Y column for the rows where the binary number represented by the values of a, b, and c is one of the numbers listed inside the square brackets. The other two rows (0 and 3) have a 0 in the Y column, and thus are not minterms.

- One standard way to represent any boolean function is called “sum of products” (SOP) or, more
formally,
*disjunctive normal form*. In this form, the function is written as the logical OR (indicated by +) of a set of AND terms, one per minterm.For example, the disjunctive normal form for our sample function would be:

Y = a'b'c + a'bc' + ab'c' + ab'c + abc' + abc

- There is also a
*conjunctive normal form,*which represents an expression as a product of sums rather than as a sum of products. The material presented below can be extended to deal with conjunctive normal forms rather than disjunctive normal forms. We’ll leave that as as one of those classic “exercises left for the student,” and deal with just disjunctive normal forms. - A
*literal*is a variable that is either complemented or not in a product term. The minterms in our sample function have a total of six literals: a, a', b, b', c, and c'. The network in Figure 2 uses only 5 literals because a' isn’t used. In the disjunctive normal form of a function, each product term has one literal for each variable. (6 literals for 3 variables in our example function.) - Figure 1 implements our sample function, and demonstrates translating a disjunctive normal form function
directly into a logic network. The translation procedure is as follows:
- Use inverters to generate all possible literals (the six vertical wires on the left in Fig. 1).
- Draw an AND gate for each minterm. The fan-in (number of inputs) of each AND gate is equal to the number of input variables.
- Connect the outputs of all the AND gates to a single OR gate.
- Connect the inputs of each AND gate to a pattern of literals in such a way that it will generate a 1 when the pattern of input values matches the particular minterm assigned to it.

- A
*minimal*form of a boolean expression is one which implements the expression with as few literals and product terms as possible. There may be more than one minimal form of an expression; if there is jut one minimal form, that form is the*minimum.* - There are many rules for manipulating a boolean expression algebraically, but there is just one rule that
you need in order to minimize a function once it is in disjunctive normal form:
*the rule of complementation*.The rule of complementation says that (x + x') is always true (1), so any two terms that are in the form (x + x')Y can be reduced to just Y without changing its meaning. Another way of saying this is that two product terms can be simplified if the only difference between them is the value of exactly one variable, in which case that variable can be eliminated from both terms to give an equivalent single term. For example ab'c + a'b'c is equivalent to (a + a')b'c, which is the same as the single product term, b'c.

A Karnaugh Map is a graphical way of minimizing a boolean expression based on the rule of complementation. It works well if there are 2, 3, or 4 variables, but gets messy or impossible to use for expressions with more variables than that.

The idea behind a Karnaugh Map (Karnaugh, 1953) is to draw an expression’s truth table as a matrix in such a way that each row and each column of the matrix puts minterms that differ in the value of a single variable adjacent to each other. Then, by grouping adjacent cells of the matrix, you can identify product terms that eliminate all complemented literals, resulting in a minimized version of the expression.

**Figure 3** shows how the minterms in truth tables
are placed in a Karnaugh Map grid for both 3 and 4 variable
expressions.

Looking at the 3 variable map on the left in Fig. 3, note that
minterm 0 (000_{2}) is just above minterm 4
(100_{2}). This arrangement means that if both minterms 0 and
4 occur in a function, the first variable (the one named *a* in
Fig. 3) appears in both its true and complemented form, and can be
eliminated. The top row of the Karnaugh Map is labeled with
*a'* and the lower row with *a*: Any minterms appearing
in the top row have the literal *a'* in them, and any minterms
in the bottom row have the literal *a* in them. At the same
time, note that each column has the same values for the variables
*b* and *c*. Also, the columns are arranged in an order
so that only one variable changes value as you go from one column to
the next. Thus, the first two columns differ in the value of
*c*, the second and third columns differ in the value of
*b*, and the third and fourth columns differ in the value of
*c* again. Furthermore, the first and fourth columns are
“next to” each other as well, because they differ from
each other just in the value of *b*.

The right side of Figure 3 shows that this same pattern (adjacent
*columns* differ by the value of a single variable) applies to
the *rows* of a Karnaugh map too: The first and second rows of
that map differ in the value of *b*, the second and third
differ in the value of *a*, the third and fourth differ in
the value of *b*, and the first and fourth differ in the
value of *a*.

**Figure 4** shows our sample function drawn as a
Karnaugh Map. Minterms 1 and 2 are in the second and fourth columns
of the top row, while minterms 4, 5, 7, and 6 appear from left to
right in the four columns of the bottom row.

A Karnaugh Map is used to produce a minimal sum of products implementation of an expression by drawing rectangles around groups of adjacent minterms in the map; each rectangle will correspond to one product term, and the full expression will be constructed as the OR (sum) of all the product terms. The goal is to have as few product terms as possible, which implies that each product term will account for as many minterms as possible.

Here are the rules for drawing the rectangles:

- Every minterm must be inside at least one rectangle, but there must not be any zeros inside any rectangles.
- Every rectangle has to be as large as possible.
- Rectangles may wrap around to include cells in both the leftmost and rightmost columns. likewise for the top and bottom rows.
- The number of minterms enclosed in a rectangle must be a power of two (1, 2, 4, 8, or 16 minterms for 4-variable maps).
- Some functions have "don’t care" conditions, which are combinations of inputs that will never occur, resulting in cases where it doesn’t matter whether the output is a zero or a one. Where these don’t care conditions appear in a Karnaugh Map (usually indicated by X’s instead of ones or zeros), they may be included inside rectangles or not depending on what will make the rectangles as few and as large as possible.

**Figure 5** shows the rectangles for our sample
function, following the procedure outlined above:

The largest rectangle (the bottom row) corresponds to the product
term *a*. By enclosing four minterms, two variables have
been eliminated resulting in a single product term with a single
variable. The rectangle in the second column encloses two minterms,
eliminating one variable (*a*) from that product term.
Similarly, the rectangle in the fourth column eliminates *a*
from that product term. The resulting sum of products function
is:

*y = a + b'c + bc'*

If you examine Fig. 2, you will see that that logic network implements exactly this function.

Every time you double the number of minterms inside a rectangle, you eliminate one variable from the resulting product term. Every doubling corresponds to applying the rule of complementation again. The next section shows how to do the same thing algebraically.

The Interactive
Karnaugh Map mentioned at the beginning of this page is a very
nice way to see how to draw the rectangles. You can enter the function
you want to process algebraically, by editing a truth table, or just
by clicking on cells in the Karnaugh Map itself. **Figure
6** is a screen shot of the applet showing how it displays our
sample function:

Minimizing an expression algebraically involves repeatedly
applying the rule of complementation, starting with the disjunctive
normal form of the function, and ending with a set of product terms
called *prime implicants.* A prime implicant is a product
term that will generate ones only for combinations of inputs that
are minterms of the disjunctive normal form of the function, and
which cannot be further reduced by combining with any other term.
They correspond to the rectangles in a Karnaugh Map.

We will call each step in this process a “pass.” It takes two passes to minimize our sample function. The following chart shows the original disjunctive normal form of the function as “Pass 0” and shows what reductions are performed for the other two passes.

---------------------------------------------------------------
| Pass 0: a'b'c + a'bc' + ab'c' + ab'c + abc' + abc |
---------------------------------------------------------------
---------------------------------------------------------------
| Pass 1: a'b'c + ab'c reduces to b'c |
| a'bc' + abc' reduces to bc' |
| ab'c + ab'c' reduces to ab' |
| abc' + abc reduces to ab |
---------------------------------------------------------------
| b'c + bc' + ab' + ab |
---------------------------------------------------------------
---------------------------------------------------------------
| Pass 2: ab' + ab reduces to a |
---------------------------------------------------------------
| a + b'c + bc' |
---------------------------------------------------------------

The rules to follow for each pass are:

- Each term present in one pass must be combined with another term if possible.
- Any terms that cannot be combined are carried forward unchanged to the next pass.
- A term that has already been used once in a pass should be used again if it will allow another term to be reduced. For example, in Pass 1 above, ab'c is used twice, and so is abc'.

The rule about reusing terms in a pass corresponds to circling some minterms more than once in a Karnaugh Map. The two minterms that are reused in Pass 1 above are exactly the same two that are circled twice in the Karnaugh Map of Figure 5.

Once the prime implicants of an expression have been determined, a
minimal subset of them has to be selected. Picking a minimal subset
of prime implicants relies on the notion of minterms being
“covered” by prime implicants. For our sample function,
the prime implicant *a* covers minterms 4, 5, 6, and 7; the
prime implicant b'c covers minterms 1 and 5, and and the prime
implicant bc' covers minterms 2 and 6. In this example, we need all
three prime implicants in order to cover all the minterms at least
once, and the expression shown at the end of Pass 2 is the minimized
form for our sample function.

But whenever there is more than one minimal form for an expression, the different forms will correspond to different subsets of the complete set of prime implicants. For any one of the minimal forms there will be extra prime implicants that have to be discarded.

The following procedure describes a way to determine one minimal form of an expression after all the prime implicants have been determined.

- For every minterm that is covered by just one prime implicant,
that prime implicant must be included in the minimal form. These
minterms are called
*essential prime implicants*because it is essential to include them in the minimization.For our sample function, minterms 2, 3, and 4 are each covered by exactly one prime implicant, so all three of the prime implicants are essential, there is just one minimized form, and there is nothing more to do.

- Make a list of all minterms that are not covered by any of the essential prime implicants.
- Make a list of unused prime implicants. Order this list by the number of literals each prime implicant contains.
- If any remaining minterms are covered by just one of the remaining prime implicants, the corresponding prime implicants must be added to the minimization, and all the minterms they cover must be removed from the list of uncovered minterms.
- If there are any uncovered minterms add the unused prime
implicant with the smallest number of literals to the minimization,
and remove all minterms that are covered by this prime implicant
from the list of uncovered minterms.
If two or more prime implicants have equally small numbers of literals, there is more than one minimal solution. Finding them all involves systematically substituting each of the tied prime implicants into the different minimal forms being generated.

- Remove all prime implicants that fail to cover any of the remaining minterms from the list of unused prime implicants.
- Repeat the previous three steps until all minterms have been covered.

**Disclaimer!** The algorithm given here is based on
the Quine-McClusky “chart” method described in (McClusky,
1965) and in (Kohavi, 1970). But it is not exactly the same as the
procedure given in those references, and may not produce the same
results. It should, however, produce a fully minimized function.

There are two version of the minimization program available. The first was developed in 2000. It must be invoked from a command prompt such as a Windows "DOS Window" or a L/Unix shell prompt. The second version was developed in 2005, and can still be run from a command prompt, but also can be run with a graphical user interface. Both versions require a Java runtime environment (JRE), available from Sun Microsystems' Java web site. The first version of the program will work with JRE version 1.3 or later, and probably works with some older JRE's as well. The second version definitely needs JRE version 1.5 or later.

**Download either version of the program:**

- Minimize.jar: The current version of the program. Requires JRE 1.5 or later. Includes source code.
- Minimize.zip: Previous version of the program. Runs with JRE 1.3 or later. Does not include source code.

The program allows you to enter either a boolean expression or a list of minterm numbers, and displays a series of messages that show the steps it followed to perform the minimization. Some expressions can be minimized more than one way, but the program shows just one minimization even if others are possible.

**Current Version**

If you are running Windows and have the proper JRE installed, you can run the program by double-clicking on it’s icon.

You may enter either a boolean expression or a list of minterm numbers in the entry field in the upper left corner of the window, and the minimized version of the expression will appear immediately below it. Do not use quotes for either type of input. Use single-letter variable names (case sensitive), * or nothing for AND, + for OR, ^ for XOR, and ' for postfix NOT. You may also use the boolean constants 0 and 1, and you may use parentheses to control evaluation order. When entering minterm numbers instead of an expression, use either spaces or commas to separate the numbers.

When you enter an expression or minterm list, the minimized
result of the algorithm appears immediately below the entry field.
This string is automatically copied to the system clipboard and can
be pasted into another application if desired. (There is no visual
indication that the result string has been selected, but it
*can* be pasted.)

The Minterm Table immediately below the minimized result shows the minterms for the sum of products form of the expression you entered. The left column shows the product terms as truth table row numbers, and the right column shows the product terms algebraically. The Prime Implicant Table below that shows each minimized product term in the first column, and a list of the full product terms that each minimized term “covers” (implies) in the second column.

The right side of the window shows the processing steps the program went through to do the minimization. (Or an error message if you entered an invalid expression.) This is the information that is written to the console when you run either version of the program from the command line.

Use the “New Window” button if you want to have multiple minimizations visible at the same time. The size, shape, and interior divisions of the last window you exit will be reused if you run the program again.

You can also launch the graphical interface from the command line
using the command, *java -jar Minimize.jar*. If you want to
run the command line version, the command is:

java -cp Minimize.jar MinimizedTable *<expression or minterm
list>*

.
See the description of the older program version below for the
syntax of *<expression or minterm list>*.

**Previous Version**

Open a command line window on your computer, and change to the directory where you downloaded Minimize.zip. The command to run the program is:

java -cp Minimize.zip Minimize *<expression or minterm
list>*

The boolean expression you enter on the command line must use the following syntax:

- Put quotes around the entire expression so that embedded spaces and other symbols such as asterisks will not be modified by the command interpreter.
- Use single letters for the variable names. Upper and lowercase letters are different variables. Don’t use more than 31 different variables. (Your computer will undoubtedly run out of memory before you get close to this limit.)
- Use * for AND, + for inclusive OR, and ^ for exclusive OR. You can leave out the *'s. That is, ab is the same as a*b.
- Use ' for complementation
*after*the item to be complemented. - AND has precedence over OR and XOR. The latter two will be evaluated in right to left order. Use parentheses to control the order of evaluation.
- Spaces have no effect.
- The constant literals 0 and 1 may be used.

Alternatively, you may write a list of minterm numbers on the command line. There must be spaces but no commas between numbers. The largest minterm number you supply will determine the number of variables in the expression and the number of rows in the resulting truth table. For example:

java -cp Minimize.zip Minimize 4 6

There have to be three variables and 8 rows in the truth table to include these two minterms. The variables will automatically be named a, b, and c.

$ java -cp Minimize.zip Minimize "a+b^c"
Finding One Minimization
Minterm Numbers: [1,2,4,5,6,7]
Reduced ab'c and a'b'c to b'c in pass 1.
Reduced abc' and a'bc' to bc' in pass 1.
Reduced ab'c and ab'c' to ab' in pass 1.
Reduced abc' and ab'c' to ac' in pass 1.
Reduced abc and ab'c to ac in pass 1.
Reduced abc and abc' to ab in pass 1.
Unable to reduce b'c in pass 2
Unable to reduce bc' in pass 2
Reduced ab and ab' to a in pass 2.
Unable to reduce b'c in pass 3
Unable to reduce bc' in pass 3
Unable to reduce a in pass 3
Minterm 1 is covered by 1 prime implicant.
Minterm 2 is covered by 1 prime implicant.
Minterm 4 is covered by 1 prime implicant.
Minterm 5 is covered by 2 prime implicants.
Minterm 6 is covered by 2 prime implicants.
Minterm 7 is covered by 1 prime implicant.
Expression: a+b^c
Sum of products: a'b'c + a'bc' + ab'c' + ab'c + abc' + abc
Prime implicants: [ a: ab'c', ab'c, abc', abc ], [ b'c: a'b'c, ab'c ], [ bc': a'bc', abc' ]
Minimized: b'c + bc' + a
$ java -cp Minimize.zip Minimize "aa'+b1"
Finding One Minimization
Minterm Numbers: [1,3]
Reduced ab and a'b to b in pass 1.
Unable to reduce b in pass 2
Minterm 1 is covered by 1 prime implicant.
Minterm 3 is covered by 1 prime implicant.
Expression: a*a'+b*1
Sum of products: a'b + ab
Prime implicants: [ b: a'b, ab ]
Minimized: b
$