In Lesson 3 we learned several methods for specifying Boolean functions, and how to to create a two-level Boolean expression for a Boolean function.  Although it is possible to create a minterm or maxterm expression for a function, it is clear that such expressions are seldom the simplest expressions for a Boolean function.  Boolean functions can be simplified by applying the laws of Boolean algebra, but there is no systematic way of applying the different laws, and there is no way to determine, absolutely, that an expression has been simplified to the greatest degree possible.  An expression that is in its simplest form is said to have been minimized.  This lesson will familiarize you with a systematic method for minimizing Boolean functions.

For the most part we will be dealing with sum-of-products expressions.  Each term of a sum-of-products expression is known as an implicant of the function implemented by the expression. Consider the function f(a,b,c)=ab+a.   Both a and ab are implicants of the function f.   The term implicant is used because if any implicant of a function has the value one, this fact implies that function has the value one. For the preceding function, ab and a are not the only implicants.  The term abc is also an implicant of f.  Each implicant is a product of literals, where a literal is either a variable or its complement. In the implicant a'bc, the literals are a', b and c. If x and y are two implicants of a function g, and x contains every literal that occurs in y, then the implicant y is said to contain the implicant x. For the function f above, the implicant a contains both implicants ab and abc.  The implicants ab and abc are also said to be contained in implicant a.  If an implicant x contains another implicant y, x will generally have fewer literals than y.  An implicant of g that is not contained in any other implicant of g is called a prime implicant of g.

Let k be an input combination consisting of ones and zeros, and let x be an implicant of the function g.   The implicant x is said to cover the input k, if x has the value one for the input combination k. For the above function f, the implicant ab covers the inputs 1,1,0, and 1,1,1, while the implicant abc covers the input 1,1,1.  To minimize a function g we need to find a set of prime implicants S, such that each one of the function is covered by at least one element of S, and each prime implicant p in S covers at least one input that is not covered by any other element of S.  We create the minimized expression by summing the elements of S.

The Karnaugh map is a method for minimizing functions that works well for functions of three or four inputs.  It is also possible to use Karnaugh maps for functions with five or six inputs, but such maps are difficult to use.   For functions with more than six inputs, other methods must be used.  We will begin by creating a Karnaugh map for the following function.

Input	Value	Input	Value
0,0,0	0	1,0,0	0
0,0,1	0	1,0,1	1
0,1,0	1	1,1,0	0
0,1,1	1	1,1,1	1

The first step is to create the following table.   This table is used for all three-input functions.  The values across the top represent the values of a and b (in that order) and the values on the left represent the values of c.  Note the unusual ordering of the bit-pairs across the top.  This ordering is used to guarantee that each pair of adjacent cells differs by only one bit.

	00	01	11	10
0
1

To use this table it is necessary to identify the sections of the table that correspond to the six literals a, a', b, b', c and c'.   In the following table, the red area corresponds to a, while the blue area corresponds to a'.

	00	01	11	10
0
1

In the following, red corresponds to b while blue corresponds to b'.

	00	01	11	10
0
1

In the following, red corresponds to c while blue corresponds to c'.

	00	01	11	10
0
1

The next step is to insert the ones of the function into the table.  It is also possible to insert the zeros into the table, but this is not necessary.

	00	01	11	10
0		1
1		1	1	1

Prime implicants correspond to single squares, pairs of adjacent squares, and any set of four adjacent squares. Remember that the last column of the table is assumed to be adjacent to the first column of the table.  The following three tables show the three prime implicants of this function.

	00	01	11	10
0		1
1		1	1	1

 

	00	01	11	10
0		1
1		1	1	1

 

	00	01	11	10
0		1
1		1	1	1

The first prime implicant falls completely into the areas of the table that corresponds to the literals a' and b, and is split between the areas that correspond to c and c'.   Therefore the prime implicant is a'b.  The second prime implicant falls completely into the areas that correspond to the literals b and c, and spans the areas that correspond to a' and a.   Therefore the prime implicant is bc.  The third prime implicant falls completely within the areas that correspond to the literals a and c, and spans the areas that correspond to b' and b.   Therefore the prime implicant is ac.

Of the three prime implicants a'b, bc, and ac, it is necessary to include a'b, because it is the only prime implicant that covers the input 010.  It is also necessary to include ac, because it is the only prime implicant that covers the input 101.   Since these two prime implicants cover all ones, it is not necessary to include the prime implicant bc.  Therefore, the minimized expression is a'b+ac.

Next, let us consider the following function.

F(a,b,c,d) = S (0,2,3,4,11,12)

The following table is used for minimizing four-input functions. The values across the top correspond to the values of the variables a and b, in that order, while the values on the left correspond to the values of the variables c and d, in that order.  As in the previous Karnaugh map, the order of the bit pairs is chosen so that adjacent squares differ by only one bit.

	00	01	11	10
00
01
11
10

In the following diagram red corresponds to the literal a, while blue corresponds to a'.

	00	01	11	10
00
01
11
10

In the following diagram red corresponds to the literal b, while blue corresponds to b'.

	00	01	11	10
00
01
11
10

In the following diagram red corresponds to the literal c, while blue corresponds to c'.

	00	01	11	10
00
01
11
10

In the following diagram red corresponds to the literal d, while blue corresponds to d'.

	00	01	11	10
00
01
11
10

As before, the next step is to add the ones of the function into the table.  Due to the unusual ordering of the bit-pairs, it is necessary to take care while assigning values to the table.

	00	01	11	10
00	1	1	1
01
11	1			1
10	1

Prime implicants correspond to single squares, pairs of adjacent squares, sets of four adjacent squares, and sets of eight adjacent squares.   The last column is adjacent to the first column, and the last row is adjacent to the first row.  The following diagrams show the prime implicants of the function.

	00	01	11	10
00	1	1	1
01
11	1			1
10	1

This prime implicant falls completely into the areas corresponding to the literals a', c' and d', and spans the arreas corresponding to literals b and b'.   The prime implicant is a'c'd'.

	00	01	11	10
00	1	1	1
01
11	1			1
10	1

The prime implicant is bc'd'.

	00	01	11	10
00	1	1	1
01
11	1			1
10	1

The prime implicant is a'b'c.

	00	01	11	10
00	1	1	1
01
11	1			1
10	1

The prime implicant is b'cd.

	00	01	11	10
00	1	1	1
01
11	1			1
10	1

The prime implicant is a'b'd'.

Because the input combination 1100 is covered only by the prime implicant bc'd', it is necessary to include it.  Similarly it is necessary to include b'cd, because it is the only prime implicant that covers the input 1011.  The only input combinations that are not covered by these prime implicants are 0000 and 0010.   These two prime implicants are both covered by the prime implicant a'b'd'.   Therefore, the minimized expression is bc'd'+b'cd+a'b'd'.

It is possible to use Karnaugh maps to create a minimized product-of-sums expression for a function f.  The easiest way to to this is to create a minimized sum-of-products expression for f ', the complement of f, and then use DeMorgan's laws to create the product of sums expression for f.

To illustrate, consider the following function.

We create a Karnaugh map, and add the zeros of the function to the map, instead of the ones.

	00	01	11	10
0	0	0		0
1	0

The prime implicants of this function are a'c', b'c', and a'b'.  It is necessary to include all three prime implicants in the expression, so f '=a'c'+b'c'+a'b'.  To create the expression for f, we complement the expression (a'c'+b'c'+a'b')'=(a'c')'(b'c')'(a'b')'=(a+c)(b+c)(a+b)=f.

For some functions we will not care what the output of the function is for certain input combinations.  These are input combinations that can never occur, or input combinations that occur only when the output of the function is unused by other portions of the circuit.  When a function has don't care inputs, they should be included in the Karnaugh map to aid in simplifying the function.  These can either be included or not included in primary implicants, as is convenient.  Don't care inputs are entered as an x in the Karnaugh map. As an example, consider the following function with don't care specifications.

F(a,b,c,d) = a’bc’d’ + a’b’c’d + a’b’cd + a’bcd + abcd + ab’cd

DontCare(a,b,c,d) = a’b’c’d’ + a’bc’d + a’bcd’

The Karnaugh map for this function is as follows.

	00	01	11	10
00	x	1
01	1	x
11	1	1	1	1
10		x

Using the don't cares, the following four prime implicants can be obtained: cd, a'b, a'c', and a'd.  A minimized expression for the function is cd+a'c+a'd.   This expression does not cover the don't care 1001, but does cover 0000 and 0101.