6.6 Min and Max Terms

The simplification process discussed in the previous section allows a function to be reduced to a simpler form, but it does not necessarily guarantee the simplest form of the function. The approach simply used the rules of Boolean algebra in an insightful manner. Unfortunately this approach does not always lead to the simplest form of the function. To solve this problem a systematic method can be developed to arrive at the simplest form of the function. Consider the case of a two variable Boolean function. In this case the outcomes of the function, regardless of the complexity, will be one of the following. There are no other possibilities.

In the above set of possible combinations or possible function results the functions f₁, f₂, f₄, and f₈ are of interest to us. Using this set of four results all other results can be obtained by creating combinations of f₁, f₂, f₄, and f₈ in various ways with OR operations. For example, f₆ could be obtained by using f₂ and f₄ (f₆ = f₂ OR f₄ see table 6.5). Similarly all other functions could be expressed using f₁,f₂, f₄, and f₈. Due to this feature this set of functions are called the min terms, and in this case there are four min terms. The number of possible results and the number of min terms is dependent on the number of Boolean variables present. In the case of 3 Boolean variables the number of min terms will turn out to be 8. An interesting property of the min terms is that it is simply combinations of the variable and its complement. The min terms f₁, f₂, f₄, and f₈ can therefore be expressed as xy’, x’y, xy’, and xy. So the min terms can be arrived at quickly by creating the various combinations of the variables and their complements. In the case of three variables ( x,y,z ), the min terms can be created using the variables ( x,y,z ) and the complements ( x’ ,y’ ,z’ ). These combinations are x’y’z’, x,y’z’, x’y,z’, x’y’z, xyz’, xy’z, x’yz, xyz

The min terms are useful because they can be used to simplify Boolean functions to the simplest form. This is done by expressing the Boolean function in terms of the min terms, first representing it on a logic map, and then simplifying using a logic map. Consider the simplification of the function F = (x + y)x+y(x’+y) shown below.

At this point the function is expressed using the min terms. Though several lines are shown this is a relatively quick process. Now the min terms are represented using a logic map (see chapter 3). This type of representation using min terms is called a Karnaugh Map or K-map. In this case there are two variables so a 2x2 map is needed. The Karnaugh map is slightly different from the logic map discussed in chapter 3 in that it uses the variable and its complements to create the map. Each min term that is present in the function is then represented in the Karnaugh map with a 1. The missing min terms are ignored.

The next step is to draw loops around the 1's in the map that are next to each other horizontally and vertically. The terms in each of the loops can be simplified as shown below.

In this case the terms in the horizontal loop represent xy + xy’. This can be simplified to x , using the Boolean relationship x(y+y’) = x. Similarly the terms in the vertical loop represent xy+x’y , and it can be simplified to y using the same reasoning as the previous simplification. Once each loop has been simplified the results are simply combined using the OR or + operation. In this case the final result will be x + y. So the simplest form of the function F = (x + y)x+y(x’+y) is F = x + y . The validity of the result can be easily verified using a truth table, as shown in table 6.6. The Karnaugh map is an ideal tool for simplification because it is visual and it guarantees the simplest form of the expression.

The pattern in the third column and the pattern in the last column are identical. Therefore, the function F=(x + y)x+y(x’+y) = x + y . The validity of the result can also be shown using the rules of Boolean algebra to show that the conclusion reached by the Karnaugh map is valid. To do this the min term expression of the function F = xy’ +yx +yx’ can be manipulated using the rules of Boolean algebra to arrive at the results produced by the Kanaugh map as shown below.

The advantage of the map method is that it requires only a few rules to be remembered, and it guarantees the simplest form of the function. The approach can be used for the simplification of a three variable function as well. The process is shown in the following 3 variable example.

In this case there are four out of a possible eight min terms. In the case of the 3 variable logic map the squares could be imagined to be a 2x2x2 cube that has been opened up. Therefore, the min term for each square will be as follows:

In this arrangement each adjacent square differs from the other by one variable. This is the key to Karnaugh maps. In this case the min terms could be arranged differently to meet this condition. This condition is needed to make the simplification possible.

If the min terms of the function are now represented with 1s on a Karnaugh map, it will be as follows.

In this case there are three groups of min terms, shown within loops that can be simplified as:

xyz +xyz’ = xy  xyz + xy’z =xz                         xyz + x’yz =yz

The original function expressed in its simplest form is F = xy + xz + yz. Like the two variable analysis the validity of the result can be shown using truth tables or algebraic manipulation.            

Diagonal loops are not allowed in a Karnaugh map because the diagonal terms cannot be simplified to a simpler form. The number of terms in a loop could be greater than two, but it must be a multiple of 2.

So far the discussion has been focused on min terms, which are the Boolean products (AND) of the variables and their complements. Using the different rules of Boolean algebra it was possible to express any Boolean expression as a sum (OR) of min terms. Similarly it is possible to convert any Boolean expression to a product of max terms. Max terms are the sum (OR) of the Boolean variables and their complement. In the case of two variable there are a total of four max terms, and they are: (x + y’), (x’ + y), (x + y’), and (x + y). Using these four max terms and the product (AND) operation all possible logical outcomes can be achieved. Therefore, all Boolean expression can be converted to a product of max terms. For example, the rules of Boolean algebra the function F = xy + x’y can be converted to a product of max terms.

The conversion is done by repeatedly applying the rule x + (y ^. z) = (x + y)(x +z) at each step and then simplifying the expression. Like min terms, max terms can be used to simplify expressions.