8.8. Minterm vs maxterm solutionSo far we have been finding SumOfProduct (SOP) solutions to logic reduction problems. For each of these SOP solutions, there is also a ProductOfSums solution (POS), which could be more useful, depending on the application. Before working a ProductOfSums solution, we need to introduce some new terminology. The procedure below for mapping product terms is not new to this chapter. We just want to establish a formal procedure for minterms for comparison to the new procedure for maxterms.
A minterm is a Boolean expression resulting in 1 for the output of a single cell, and 0s for all other cells in a Karnaugh map, or truth table. If a minterm has a single 1 and the remaining cells as 0s, it would appear to cover a minimum area of 1s. The illustration above left shows the minterm ABC, a single product term, as a single 1 in a map that is otherwise 0s. We have not shown the 0s in our Karnaugh maps up to this point, as it is customary to omit them unless specifically needed. Another minterm A'BC' is shown above right. The point to review is that the address of the cell corresponds directly to the minterm being mapped. That is, the cell 111 corresponds to the minterm ABC above left. Above right we see that the minterm A'BC' corresponds directly to the cell 010. A Boolean expression or map may have multiple minterms. Referring to the above figure, Let's summarize the procedure for placing a minterm in a Kmap:
A Boolean expression will more often than not consist of multiple minterms corresponding to multiple cells in a Karnaugh map as shown above. The multiple minterms in this map are the individual minterms which we examined in the previous figure above. The point we review for reference is that the 1s come out of the Kmap as a binary cell address which converts directly to one or more product terms. By directly we mean that a 0 corresponds to a complemented variable, and a 1 corresponds to a true variable. Example: 010 converts directly to A'BC'. There was no reduction in this example. Though, we do have a SumOfProducts result from the minterms. Referring to the above figure, Let's summarize the procedure for writing the SumOfProducts reduced Boolean equation from a Kmap:
Nothing new so far, a formal procedure has been written down for dealing with minterms. This serves as a pattern for dealing with maxterms. Next we attack the Boolean function which is 0 for a single cell and 1s for all others.
A maxterm is a Boolean expression resulting in a 0 for the output of a single cell expression, and 1s for all other cells in the Karnaugh map, or truth table. The illustration above left shows the maxterm (A+B+C), a single sum term, as a single 0 in a map that is otherwise 1s. If a maxterm has a single 0 and the remaining cells as 1s, it would appear to cover a maximum area of 1s. There are some differences now that we are dealing with something new, maxterms. The maxterm is a 0, not a 1 in the Karnaugh map. A maxterm is a sum term, (A+B+C) in our example, not a product term. It also looks strange that (A+B+C) is mapped into the cell 000. For the equation out=(A+B+C)=0, all three variables (A, B, C) must individually be equal to 0. Only (0+0+0)=0 will equal 0. Thus we place our sole 0 for minterm (A+B+C) in cell A,B,c="000" in the Kmap, where the inputs are all0 . This is the only case which will give us a 0 for our maxterm. All other cells contain 1s because any input values other than ((0,0,0) for (A+B+C) yields 1s upon evaluation. Referring to the above figure, the procedure for placing a maxterm in the Kmap is:
Another maxterm A'+B'+C' is shown above. Numeric 000 corresponds to A'+B'+C'. The complement is 111. Place a 0 for maxterm (A'+B'+C') in this cell (1,1,1) of the Kmap as shown above. Why should (A'+B'+C') cause a 0 to be in cell 111? When A'+B'+C' is (1'+1'+1'), all 1s in, which is (0+0+0) after taking complements, we have the only condition that will give us a 0. All the 1s are complemented to all 0s, which is 0 when ORed.
A Boolean ProductOfSums expression or map may have multiple maxterms as shown above. Maxterm (A+B+C) yields numeric 111 which complements to 000, placing a 0 in cell (0,0,0). Maxterm (A+B+C') yields numeric 110 which complements to 001, placing a 0 in cell (0,0,1). Now that we have the kmap setup, what we are really interested in is showing how to write a ProductOfSums reduction. Form the 0s into groups. That would be a group of two below. Write the binary value corresponding to the sumterm which is (0,0,X). Both A and B are 0 for the group. But, C is both 0 and 1 so we write an X as a place holder for C. Form the complement (1,1,X). Write the Sumterm (A+B) discarding the C and the X which held its' place. In general, expect to have more sumterms multiplied together in the ProductOfSums result. Though, we have a simple example here.
Let's summarize the procedure for writing the ProductOfSums Boolean reduction for a Kmap:
Example: Simplify the ProductOfSums Boolean expression below, providing a result in POS form.
Solution: Transfer the seven maxterms to the map below as 0s. Be sure to complement the input variables in finding the proper cell location.
We map the 0s as they appear left to right top to bottom on the map above. We locate the last three maxterms with leader lines.. Once the cells are in place above, form groups of cells as shown below. Larger groups will give a sumterm with fewer inputs. Fewer groups will yield fewer sumterms in the result.
We have three groups, so we expect to have three sumterms in our POS result above. The group of 4cells yields a 2variable sumterm. The two groups of 2cells give us two 3variable sumterms. Details are shown for how we arrived at the Sumterms above. For a group, write the binary group input address, then complement it, converting that to the Boolean sumterm. The final result is product of the three sums. Example: Simplify the ProductOfSums Boolean expression below, providing a result in SOP form.
Solution: This looks like a repeat of the last problem. It is except that we ask for a SumOfProducts Solution instead of the ProductOfSums which we just finished. Map the maxterm 0s from the ProductOfSums given as in the previous problem, below left.
Then fill in the implied 1s in the remaining cells of the map above right.
Form groups of 1s to cover all 1s. Then write the SumOfProducts simplified result as in the previous section of this chapter. This is identical to a previous problem.
Above we show both the ProductOfSums solution, from the previous example, and the SumOfProducts solution from the current problem for comparison. Which is the simpler solution? The POS uses 3OR gates and 1AND gate, while the SOP uses 3AND gates and 1OR gate. Both use four gates each. Taking a closer look, we count the number of gate inputs. The POS uses 8inputs; the SOP uses 7inputs. By the definition of minimal cost solution, the SOP solution is simpler. This is an example of a technically correct answer that is of little use in the real world. The better solution depends on complexity and the logic family being used. The SOP solution is usually better if using the TTL logic family, as NAND gates are the basic building block, which works well with SOP implementations. On the other hand, A POS solution would be acceptable when using the CMOS logic family since all sizes of NOR gates are available.
The gate diagrams for both cases are shown above, ProductOfSums left, and SumOfProducts right. Below, we take a closer look at the SumOfProducts version of our example logic, which is repeated at left.
Above all AND gates at left have been replaced by NAND gates at right.. The OR gate at the output is replaced by a NAND gate. To prove that ANDOR logic is equivalent to NANDNAND logic, move the inverter invert bubbles at the output of the 3NAND gates to the input of the final NAND as shown in going from above right to below left.
Above right we see that the output NAND gate with inverted inputs is logically equivalent to an OR gate by DeMorgan's theorem and double negation. This information is useful in building digital logic in a laboratory setting where TTL logic family NAND gates are more readily available in a wide variety of configurations than other types. The Procedure for constructing NANDNAND logic, in place of ANDOR logic is as follows:
Example: Let us revisit a previous problem involving an SOP minimization. Produce a ProductOfSums solution. Compare the POS solution to the previous SOP.
Solution: Above left we have the original problem starting with a 9minterm Boolean unsimplified expression. Reviewing, we formed four groups of 4cells to yield a 4productterm SOP result, lower left. In the middle figure, above, we fill in the empty spaces with the implied 0s. The 0s form two groups of 4cells. The solid red group is (A'+B), the dashed red group is (C'+D). This yields two sumterms in the ProductOfSums result, above right Out = (A'+B)(C'+D) Comparing the previous SOP simplification, left, to the POS simplification, right, shows that the POS is the least cost solution. The SOP uses 5gates total, the POS uses only 3gates. This POS solution even looks attractive when using TTL logic due to simplicity of the result. We can find AND gates and an OR gate with 2inputs.
The SOP and POS gate diagrams are shown above for our comparison problem. Given the pinouts for the TTL logic family integrated circuit gates below, label the maxterm diagram above right with Circuit designators (U1a, U1b, U2a, etc), and pin numbers.
Each integrated circuit package that we use will receive a circuit designator: U1, U2, U3. To distinguish between the individual gates within the package, they are identified as a, b, c, d, etc. The 7404 hexinverter package is U1. The individual inverters in it are are U1a, U1b, U1c, etc. U2 is assigned to the 7432 quad OR gate. U3 is assigned to the 7408 quad AND gate. With reference to the pin numbers on the package diagram above, we assign pin numbers to all gate inputs and outputs on the schematic diagram below. We can now build this circuit in a laboratory setting. Or, we could design a printed circuit board for it. A printed circuit board contains copper foil "wiring" backed by a non conductive substrate of phenolic, or epoxyfiberglass. Printed circuit boards are used to mass produce electronic circuits. Ground the inputs of unused gates.
Label the previous POS solution diagram above left (third figure back) with Circuit designators and pin numbers. This will be similar to what we just did.
We can find 2input AND gates, 7408 in the previous example. However, we have trouble finding a 4input OR gate in our TTL catalog. The only kind of gate with 4inputs is the 7420 NAND gate shown above right. We can make the 4input NAND gate into a 4input OR gate by inverting the inputs to the NAND gate as shown below. So we will use the 7420 4input NAND gate as an OR gate by inverting the inputs.
We will not use discrete inverters to invert the inputs to the 7420 4input NAND gate, but will drive it with 2input NAND gates in place of the AND gates called for in the SOP, minterm, solution. The inversion at the output of the 2input NAND gates supply the inversion for the 4input OR gate.
The result is shown above. It is the only practical way to actually build it with TTL gates by using NANDNAND logic replacing ANDOR logic.
