AMAZON multi-meters discounts AMAZON oscilloscope discounts
Truth Tables from Equations
Sometimes you will wish to convert a logic expression into its truth-table form.
If the expression is in sum-of-products form, the conversion is easy. Each product term will form one or more truth-table rows having a true function value.
A canonical product term (one with all the variables in it; a minterm) produces one row with an output of TRUE. A product term with fewer variables yields more rows, since such a term is true for any values of the missing variables.
Often more than one product term in the sum will contribute truth for a given row of the truth table. This is fine-double-truth is still truth! As an example, consider this equation of three variables: (eqn. 18)
Term 1 Term 2 Term 3 Term 4
The truth table f or this equation is
Terms 2 and 3 are canonical; each contributes a true output to one row of the table. Terms 1 and 4, having a missing variable, contribute true outputs to two rows each.
Equations in product-of-sums form are most easily translated into truth tables by focusing on the conditions for having false function values. Each sum term in the product will assure a false expression value whenever all its variables are the opposite of the form in the term. For example, consider the following equation of three variables:
G = (A + B + C) o (A + B) o (A + Jj + C)
Term 1 Term 2 Term 3
Term 1 makes G false for row 4 (100) of the truth table; term 3 produces a result of false for row 7 (111). Term 2, with its missing variable C, produces a result of false for two rows, 4 (100) and 5 (101). Terms 1 and 3 are canonical: each contributes a false function value for one row; term 2 is not canonical. Here is the truth table:
For logic expressions of more general form than the sum of products or the product of sums, we fall back on the ultimate method of deriving truth tables: evaluating the function for every combination of values of the input variables.
This means that we explicitly determine each function value. The process is often laborious, but (barring error!) is foolproof. For example, from the equation
K = (L + G)o(L + G)
we get the following truth table by computing the value of K for each of the four .sets of values of Land G:
Another approach for forming a truth table from a general Boolean equation is to manipulate the expression (usually using De Morgan's law) until it becomes a sum-of-products or product-of-sums form, and then use the methods presented earlier in this section.
Condensing Truth Tables
A canonical truth table of n input variables has 2n rows arranged in binary numerical order on its inputs, corresponding to all the possible values of the input variables. The canonical form explicitly displays the function's value for every possible set of input conditions. This form of truth table-the only one we have used so far-is the counterpart of the canonical forms of sum-of products and product-of-sums equations. Just as we frequently use Boolean equations in a simplified form, we also sometimes wish to deal with a simplified or collapsed truth-table notation.
Consider Eq. (18) again:
Y = JoK + JoKoL + JoKor + KoL
Term 1 Term 2 Term 3 Term 4
The canonical terms (2 and 3) each contribute one row to the canonical truth table in Eq. (eqn. 19). Term 1, however, is independent of the value of variable L (L does not appear), so term 1 contributes two rows with true output to the canonical truth table, one for each value of the missing variable. If we are willing to abandon the canonical form for the truth table, we may introduce a shorthand notation for this situation. We collapse these two rows for term 1 into a single row and place an X for the value of the missing variable L. The X means "both values" and implies that the function value is independent of that variable whenever the other inputs are in their stated conditions. Similar arguments apply to term 4, which lacks the variable J.
Applying this concept to the expression, we may derive a shortened truth table:
(eqn. 20)
Note how this truth table yields the original equation in a direct manner.
The X is the truth-table equivalent of the important Boolean algebraic identity of Eq. (eqn. 9)
There are various applications of this identity that we could introduce directly into the truth table of Eq. (eqn. 20) if we desired. For instance, here are two more stages in the condensation of this table:
(eqn. 21)
If we are presented with a truth table containing X's, the derived Boolean equation will not be canonical, but will contain some simplified terms. A sum of-products equation for the right-hand truth table in Eq. (eqn. 21) is
Y = K·L + J
Satisfy yourself that the original Eq. (eqn. 18) is equivalent to this, and that all these truth tables based on Eq. (eqn. 18) are equivalent.
Condensed tables are convenient, since the original statement of a problem will often lead in a natural way to the condensing of rows. The main virtue of the notation is in allowing the truth table to reflect its origins more faithfully.
A secondary virtue is in the resultant shortening. Attempts as in Eq. (eqn. 21) to simplify truth tables by collapsing rows of a less simplified form are tricky and can lead the inexperienced into errors. Soon we will discuss a graphical method for simplifying logic functions that is easier for people to use.
Don't-Care Outputs in Truth Tables
Truth tables have a useful property that a logic equation cannot express. We often know from the nature of the problem that the function's value is irrelevant for certain combinations of the input variables. This situation usually arises when we know that the inputs will never legitimately assume certain sets of values. We may use a small dash "-" for the truth-table function value in such cases. The - means "don't care." In deriving a logic equation from the truth table, we are free to use either a T or F value for the don't-care dash, whichever will yield the more useful form. For instance, look at the condensed truth table below:
Of the various equations that we may derive from this truth table, a choice of T for the don't-care output might yield the sum-of-products form:
Y = A +A-B"
which can be simplified to Y=A+B
whereas a choice of F for the don't-care gives the quite different equation Y=A
You may use either equation; your choice may depend on other factors in the problem design.
KARNAUGH MAPS
In the early years of digital computers, each logic element in a circuit was large and cumbersome by modem standards, and consumed considerable power. There was a natural emphasis on reducing the number of circuit elements to the bare minimum so as to cut the total cost. Designers developed many elaborate techniques for simplifying logic expressions, and much effort went into perfecting these tools. Today, hardware for digital logic is inexpensive, and in modem design work the emphasis on circuit minimization has given way to a concern for modularity and clarity in the design process.
One result of this shift in technology and design style is that circuit building blocks have become larger and more powerful, while the "glue" that holds them together (the logic equations) has become simpler and less voluminous. Although the minimization of complex Boolean equations is no longer of paramount importance, simplification of small and manageable equations remains a routine task that we should make as easy and mechanical as practical. Manipulating equations through the Boolean algebraic identities, as we have done in the previous sections, is an arcane art. There are few guidelines to follow other than our intuition (based on experience) and trial and error. You have seen that sum of products is a common form of Boolean expression. This form results from truth-table derivations and occurs in other steps of our design process. The Boolean identity that is of most frequent use in simplifying sum-of-products forms is Eq. (eqn. 9), which allows the elimination of a variable and its complement when these have a common factor:
A-B +A-B = (A +A)-B = T-B = B
The Karnaugh map (K-map) is a graphic display whose visual impact assists us in the systematic application of this identity. * [The Karnaugh map is also known as a Veitch diagram.] A Karnaugh map is a canonical truth table rearranged in form. Fig. 1 is a truth table and its K-map for an arbitrary function of two variables. The Karnaugh map has a square for each truth-table row; each combination of variables identifies a square in the map.
In the two-variable case, the values of one variable appear as the labels for the vertical edges of the squares (B = 0 and B = 1 in Fig. 1), and the other variable's values mark the horizontal edges (A = 0 and A = 0. Each square contains the value of the given function (YJ corresponding to the appropriate truth-table row, as specified by the labels on the edges of the K-map. For instance, the lower left square in the K-map of Fig. 1, corresponding to A = 0, B = 1, has the function value Yj •
Fig. 1. A truth table and its Karnaugh map.
Functions of more than two variables also have K-map representations.
Three- and four-variable functions are easy to manage; with more than four variables, the K-map technique becomes unwieldy, but fortunately most of the simplifications of design equations that we encounter in practice involve no more than four variables. The three-variable map contains eight squares, corresponding to the eight rows in the canonical truth table. Fig. 2 shows two notations for K-maps of three variables. Both forms are equivalent, and both are in common use. Our mild preference is for the left-hand form, but you should be familiar with each. We like the left-hand form because it has an explicit display of the values of the variables on each edge of the map. The right-hand form explicitly labels only the location of true values for each variable. Some people prefer this form; take your pick. Conventionally, the third variable (rightmost in the truth table) appears on the vertical edge, while the horizontal edge displays the first and second variables.
Fig. 2. Two forms of a K-map of three variables.
Note carefully the order of the labels on the top edge. In moving from square to square across a row (and around the corner, also), the value of only one variable changes at a time. As you will see, this unit distance property gives the K-map its virtue in simplifying logic expressions.
Extending the K-map to four variables adds an additional variable to the vertical edge, resulting in 16 squares. Fig. 3 illustrates both notations for Karnaugh maps of four variables.
Fig. 3. Two forms of a K-map of four variables.
Building K-Maps
There is a one-to-one correspondence between Karnaugh map squares and canonical truth-table rows. Deriving either the map or the table from the other is just a matter of rearranging the information. Don't-care outputs from truth tables are directly transferable to the appropriate K-map squares. Condensed truth-table rows yield values for more than one K-map square, in an obvious way.
We may view the K-map as a representation of the canonical sum-of products form of a Boolean expression. Just as we may derive a truth table from a logic equation, we may move directly to a K-map from an equation, when this is appropriate. Fig. 4 shows the three forms for a function of two variables.
The techniques for creating a truth table from a logic equation will also yield the K-map for the equation. The expression in Fig. 4 is already in canonical form, so the transformations among table, K-map, and equation are easy. Consider now the three-variable equation
v = AoJj + B + Ao Jj o e
The first term in the sum yields l's in the K-map when A,B = 10 and e = anything. To give a true value, the second term requires B = 1, but A and e may be anything. The third term yields 1 for A,B,e = 101, which already appears in the map because of the AoB term. The resulting map is Fig. 5.
Fig. 4. (above left) Three representations of a Boolean function.
(right) Fig. 1. K-map for V = A·B + B + A·B·C.
Simplifying with K-Maps
Why bother with these maps? You may get a clue from Fig. 4. You have probably noticed that the expression for X can be simplified with Eq. (eqn. 9):
X=A·Jj+AoJj
= (A+A)oJj
= ToJj
=Jj
How does the K-map display this simplification? The key point is that a certain term (B in this case) is ANDed with both A and A. On the K-map this results in 1's in both the A = 0 and A = 1 squares for B = O. Let's circle these adjacent 1's to remind us that the A variable disappears from the simplified expression because it appears as both A and A (see Fig. 6). Note how the simplified form A = Jj stands out more clearly: the condition for X to be true is that B is false (or B is true). Thus X = B.
The drawing of circles (really ovals) among adjacent 1's is the basis for using K-maps in Boolean simplification. On K-maps of two variables, there are five ways to display applications of the basic identity of Eq. (eqn. 9) with circles.
Fig. 7 shows these forms.
Fig. 6. Circling adjacent 1 'so
Fig. 7. Simplifications of K-maps of two variables.
In using the K-map for simplification, we look for applications of the rules for circling. Depending on the position of the 1's, we may have several circles, each spanning a grouping of one, two, four, eight, ... 1 'so The K-map method requires that each 1 in the map appear in at least one circle, even if it is by itself. Circling two 1's causes two canonical terms to collapse into one term; one variable drops out. Four circled 1's bring four terms into one term, eliminating two variables. A proper group of eight circled 1's drops three variables, and so on.
On K-maps of three or more variables, some applications of the simplifying identity do not involve physically adjacent 1 'so In these cases, we must draw "around-the-corner" circles. Fig. 8a shows some typical ordinary circle patterns for a K-map of three variables; Fig. 8b gives all the around-the-corner patterns of two 1’s; and Fig. 8c shows the only around-the-corner pattern involving four 1's.
Fig. 8. Typical circlings of K-maps of three variables.
Fig. 9 shows three improper circlings.
Fig. 9 shows three improper circlings. Diagonal or L-shaped arrangements do not correspond to applications of Eq. (eqn. 9), nor does the circling of three 1’s, since 3 is not a power of 2.
K-maps of four variables are similar to the three-variable variety. Fig. 10 shows some forms involving correct circlings of four and eight 1's. You should inspect these patterns until you are comfortable with their meaning.
Fig. 10. Typical circlings of four 1's and eight 1's on K-maps of four
variables.
Here is the prescription for circling 1's in a K-map: Draw circles (ovals or around-the-corner patterns) around properly positioned collections of 1's, starting with the largest possible circles, and working toward smaller circles. Overlapping circles are appropriate when they allow a larger circle to appear. (Do not draw a circle that is completely within a larger circle; this would result in a redundant term and an incompletely simplified function.) Drawing the largest circles possible, cover all the l's on the map. Use don't-care dashes "-" as either a 1 or a 0, as convenient. The point of using K-maps is to let the drawing display the simplified result in a systematic and mechanical fashion. When you have finished drawing circles, read off the simplified function as a sum of products, in which each circle contributes one product term to the sum.
Fig. 11 shows two examples of functions of two variables, derived from their K-maps. Fig. 11b yields no simplification.
The K-map method allows a simple derivation of the important identity of Eq. (eqn. 8); Fig. 12 shows the process.
Fig. 11. Simplifiable and unsimplifiable functions of two variables.
Fig. 12. Proof of the identity A + Xo B= A + B.
Fig. 13 shows the simplifications of two functions of four variables.
Notice the use of overlapping circles to achieve the largest circles. Some 1’s must be circled by themselves, yielding un simplified four-variable terms.
Fig. 13. Simplification of two functions of four variables.
Fig. 14. Common blunders in circling K-maps.
K-Map Simplification Blunders
The most common error in simplifying expressions with K-maps is to fail to circle the largest possible groupings of 1 'so A less common error is to introduce a redundant smaller circle within a larger one. Fig. 14 shows some typical blunders and the correct forms. Although Figs. 14a and 14c produce correct Boolean expressions, these expressions are not as simple as the K-map method allows. Design criteria may sometimes require the use of an incompletely simplified form, but these occasions are rare and we will not consider them here. Make all your circles as large as possible. Fig. 14a has four circling errors: two incomplete circlings and two redundant circles. Fig. 14c has three errors, all incomplete circlings.
Other Ways of Reading K-Maps
We have stressed the method of circling l's and reading a sum of products for the function. If you are interested in developing the best facility with K-maps, you will want to investigate three other interpretations. These are analogous to the forms for reading expressions from truth tables shown earlier in this section.
We give the three additional K-map methods below, with one example, leaving a comprehensive study of these techniques as grist for your mental mill.
Method 1: Circle 1's and read a sum of products for the function (the normal method).
Method 2: Circle 0's and read a sum of products for the inverse of the function (also a frequently used method).
Method 3: Circle 0's and read a product of sums for the function.
Method 4: Circle 1's and read a product of sums for the inverse of the function.
Fig. 15a shows a K-map with l's circled; Fig. 15b is the same map with 0's circled. The resulting equivalent simplified forms of the function are:
From method 1: S = A o B + A o C
From method 2: S = A + lioc
From method 3: S = A o(B + C)
From method 4: S = (A + li)o(A + C)
Fig. 15. Two ways of circling a K-map.
CONCLUSION
You now have the knowledge of the foundations of digital logic that you need to continue your introduction to digital design. Boolean algebra and its allied techniques are a fascinating field of study, and you may wish to pursue these topics in more depth as your skill as a designer grows. We have just scratched the surface of the field, but the information in this section is sufficient for our purposes. Going deeper would deflect us from our goal, which is to build up the necessary tools as rapidly as possible in Part I so you may quickly reach the study of the design process in later parts of the guide.
Now it is time to develop tools for systematically translating logic expressions into hardware.
EXERCISES
1. Have you read the Preface?
2. What is the goal of Part I of this guide? Part II? Part III? When may you read the material in Part IV?
3. What are the basic logical operators in digital design? What are the constants? What does the numeral 1 mean in digital design?
4. How many different Boolean functions of two variables are there? Of three variables? Derive an expression for the number of different Boolean functions of n variables.
5. What is a canonical truth table? Give examples of a canonical truth table and a non-canonical truth table of three variables.
6. Give the operator hierarchies for AND, OR, and NOT. By inserting full parentheses, show the order of evaluation of these functions: (a) B-A-C + D + E (b) A + B-C + D (c) A + B-(C + D)
7. By using the operator hierarchies, write the following expressions with as few parentheses as possible: (a) «Q + (R-S» + U- V) (b) «Q-(R + S»-( U + V»
8. Prove the following identities by writing the truth tables for both sides.
(a) A-(B + C) == (A-B) + (A-C) (b) A + (B-C) == (A + B)-(A +C) (c) if == A (d) ~ == A + B + C (e) A + B + C == A-B-C (I) A + if-B == A + B (g) A-(A + B) == A
9. The cancellation law of regular algebra states that If X (+) Y = X (+) Z, then Y = Z Show by giving counterexamples that Boolean algebra has no equivalent cancellation law. In other words, show that the following statements are false: If X + Y = X + Z, then Y = Z If X-Y = X-Z, then Y = Z 1-10. NAND and NOR are Boolean functions sometimes used in design. NAND (NOT AND) is defined as AND followed by NOT; NOR (NOT OR) is defined as OR followed by NOT. Write the defining truth tables for A NAND B and A NOR B.
11. (a) Write each of the following expressions in a form that has no AND operators: (A + B)-C (b) Write each of the following expressions in a form that has no OR operators: A + B + C if + B + C o D + E
12. Define the following terms:
(a) Canonical.
(b) Minterm.
(c) Maxterm.
(d) Sum-of-products form.
(e) Product-of-sums form.
(f) Canonical sum-of-products form.
(g) Canonical product-of-sums form.
13. Which of the following expressions is in sum-of-products form? Which is in product of-sums form?
(a) A + B o D (b) C o D o E + F + D (c) (A + B) o C
14. (a) Write a four-element vector describing the function X(A,B):
(b) Derive a logic equation for X directly from the truth table.
(c) Derive a logic equation for X directly from your vector expression.
(d) Show that the results from parts (b) and (c) are equivalent.
15. Without formally deriving any logic expressions, deduce the value of each function W, X, Y, and Z:
16. Write the logic equations corresponding to the following: (a) X(A,B,C) = Il1o + m2 + m5 (b) X(P,Q) = M) o M3
17. Write the canonical truth tables for each of the following: (a) Y(V,W,X) = M2 o M3 o M5 o M6 (b) Y(C,B,G) = m) + m2 + m7
18. Show that Eq. (eqn. 13) reduces to Y = Xo B: (a) By using Boolean algebraic reductions.
(b) By developing the canonical truth table for each sum term in Eq. (eqn. 13), then … performing the AND of the truth-table function values to produce a truth table for Y, and finally reading the sum-of-products logic equation for Y from the truth table.
19. Consider the following truth table: Derive canonical equations for G or G in the following forms:
(a) Sum of products on true outputs.
(b) Sum of products on false outputs.
(c) Product of sums on true outputs.
(d) Product of sums on false outputs.
20. Prove the correctness of your answers to Exercise 19 by reconstructing a truth table for G from each equation.
21. Consider the following canonical truth table for two functions Sand C: (a) Express Sand C as eight-element vectors.
(b) Working directly from the vectors, write a canonical sum-of-products equation for S and a product-of-sums equation for S. Show the equivalence of the equations by Boolean algebraic manipulations.
(c) Repeat part (b) for functions C and C. (d) Directly from the truth table, write a vector for the function S·C. Working from the vector, give a logic equation for S·C. (e) Repeat part (d) for the function S + C.
22. By Boolean algebraic transformations, show the equivalence of the forms in Eqs. 0-14) through 0-17).
23. Express Eqs. 0-14) through (eqn. 17) using the minterm and maxterm notations.
24. Explain the use of X for "both values" and - for "don't care" in truth tables.
25. Derive the canonical truth tables that correspond to each of the following K-maps:
26. Plot the function in Exercise 19 on two K-maps, one map labeled as in Fig.
2a and the other as in Fig. 2b. Simplify the function if possible.
27. Draw a K-map for each of the truth tables below. Derive a simplified logic equation from each K-map.
28. Here is a K-map for a function S:
By circling zeros, give a logic equation for S as a sum of products with each product term containing two variables.
29. By circling zeros, simplify the functions in Fig. 13.
30. Assuming that there are three inputs A, B, and C, write a truth table to describe each of these ideas: (a) The output should be true only when two or more of the input variables are true.
(b) The output should be true only when the number of true input variables is odd.
(c) The output should be true only when the number of false input variables is even.
(d) The output should be false only when exactly two of the input variables are true.
31. Simplify the functions derived in Exercise 30, using K-maps.
32. Often the natural formulation of a logic function is not in perfect sum-of-products or product-of-sums form. For example, consider the equation M = X·(B + C) + A·C. Simplify this equation using two different K-map circlings. Are the resulting sum-of-products forms less compact or more compact than the original? (A criterion for compactness is the number of binary AND and OR operators in the expression.) Can you perform elementary factorings on the K-map results that make the results more compact? Compare the original equation with each of the final equations.
33. Consider two 2-bit binary numbers, say, A, B and C,D. A function X is true only when the two numbers are different.
(a) Construct a truth table for X. (b) Construct a four-variable K-map for X, directly from the word definition of X. (c) Derive a simplified logical expression for X.
34. You are installing an alarm bell to help protect a room at a museum from unauthorized entry. Sensor devices provide the following logic signals: ARMED = The control system is active DOOR = The room door is closed OPEN = The museum is open to the public MOTION = There is motion in the room Devise a sensible logic expression for ringing the alarm bell.
35. A large room has three doors, A, B, and C, each with a light switch that can turn the room light on or off. Flipping any switch will change the condition of the light.
(a) Assuming that the light is off when the switch variables have the values 0, 0, 0, write a truth table for a function LIGHT that can be used to direct the behavior of the light.
(b) Derive a logic equation for LIGHT. (c) Can you simplify this equation? (d) How is this exercise related to Exercise I-30? 1-36. Electronic watches display time by turning on a certain combination of seven light bar segments to yield approximations of the shape of the decimal digits. For each digit position, the segments are labeled as follows:
The decimal digit displays have the form
For example, the digit 4 has segments b, c,f, and g lighted. Internally, the watch represents a decimal digit by a 4-bit binary code, say, D,C,B,A. For example:
DeB A
7=0 1 1 1
(a) Develop a multi-output truth table for lighting the segments. The truth table will have inputs D, C, B, and A, and outputs a, b, c, d, e, t, and g. Notice that don't-care conditions arise naturally, since 4 bits can encode 16 combinations, whereas the decimal digits use only 10 of them. Binary codes above 1001 will never occur.
(b) Plot the light segment outputs a through g on four-variable K-maps, and derive a simplified equation for each segment.
37. The university pool room has four pool tables lined up in a row. Although each table is far enough from the walls of the room, students have found that the tables are too close together for best play. The experts are willing to wait until they can reserve enough adjacent tables so that one game can proceed unencumbered by nearby tables. A light board visible outside the poolroom shows vacant tables.
The manager has developed a digital circuit that will display an additional light whenever the experts' desired conditions arise. Give a logic equation for the assertion of the new light signal. Simplify the equation, using a K-map.
READINGS AND SOURCES
BLAKESLEE, THOMAS R., Digital Design with Standard MSI and LSI, 2nd ed. John Wiley & Sons, New York, 1979.
BOOLE, GEORGE, An Investigation of the Laws of Thought, on which are Founded the Mathematical Theories of Logic and Probability, 1849. Dover Publications, 31 East 2nd Street, Mineola, N.Y. 11501, 1954. Where it all started. A Dover reprint of the classic work.
DIETMEYER, DONALD L., Logic Design of Digital Systems, 2nd ed. Allyn & Bacon, Boston, 1978. Good exposition of traditional switching theory and minimizations.
FLETCHER, WILLIAM I., An Engineering Approach to Digital Design. Prentice-Hall, Englewood Cliffs, N.J., 1980. Section 3 contains a good exposition of Karnaugh maps and minimization.
HILL, FREDERICK J., and GERALD R. PETERSON, Introduction to Switching Theory and Logical Design, 3rd ed. John Wiley & Sons, New York, 1981.
KARNAUGH, M., "The map method for synthesis of combinational logic circuits," Communications and Electronics, No.9, November 1953.
MILLER, RAYMOND E., Switching Theory, Vol. 1: Combinational Circuits. John Wiley & Sons, New York, 1966. An important early work.
SHANNON, C. E., "Symbolic analysis of relay and switching circuits," Transactions AIEE, Vol. 57, 1938, p. 713.
VIETCH, E. W., "A chart method for simplifying truth functions," Proceedings ACM, Pittsburgh, 1952, p. 127.
PREV. | NEXT
Related Articles -- Top of Page -- Home