Karnaugh map (PHC504) - Incomplete

Introduction

The Boolean functions can be simplified using the theorems of Boolean algebra. The reduced Boolean expression helps to get the simple, less expensive, and smaller circuit. This method of simplification is not used in practice as it is difficult to apply. Further, it is impossible to guarantee that the reduced expression is minimal, and it cannot be reduced beyond the obtained expression. One is known as the Karnaugh map (K-map) method.

Karnaugh map (K-map) method:

The Karnaugh map method is very commonly used to simplify Boolean expressions since no algebraic rules are applied in this method. It is simply a graphic method and provides a systematic approach for getting the simplified Boolean expression. If this method is properly used, then the available Boolean expression will be minimal and will not further be simplified by any method. The Karnaugh map also called the K-map method, is suitable for simplifying Boolean expression, which contains four or fewer variables (or literals) with their complements.

Two Variable K-map:

For two variable K-maps, two lines are drawn: one horizontal and the other vertical. On one line, the complement of one variable followed by the variable itself is written and on the other line, the complement of the other variable followed by that variable itself is written. Let the two variables be (A) and ((B)). So (A) and variable (A), are written on a vertical line; ((B)) and variable ((B)) are written on a horizontal line or otherwise, as shown in figure (1). The other method of writing K-map for two variables is that in place of (A) , 0 is written and in place of (A), 1 is written; as illustrated in figure (2), where (A) and ((B)) are shown separately over and below of a leaning line.

Figure: K-map representation: 1

Figure: K-map representation: 2

These two figures are similar and show the same meaning. One can use either of the two ways mentioned above. Each K-map show four squares represented by four minterms \(m_{0}\), \(m_{1}\), \(m_{2}\), and \(m_{3}\). In the truth table of two variables if there are 1’s entry corresponding to the some minterms, then 1s are entered corresponding to those minterms. Let us assume that we have 1s entry for the minterms \(m_{2}\) and \(m_{3}\). The K-map for the same is represented as shown in figure.

Three Variable K-map:

For three variables two adjacent variables are taken on either side (vertical line or horizontal line) of the K-map and the remaining one variable on the other side. Let (A), ((B)) and (C) are the three variables, the two variables will have four combinations labeled on one side as (A).((B)) , (A).((B)) , (A).((B)) and (A).((B)) ; (C) and (C) on the other side as shown in figure

The other method of writing K-map for three variables is that in place of the possible combinations of two variables (A) & ((B)) it is written as 00, 01, 11 and 10; and in place of (C) & (C) , 0 & 1 are written; as illustrated in figure, where AB and (C) are shown separately over and below of a leaning line.

Four Variable K-map:

For four variables, two adjacent variables are taken on either side (vertical line or horizontal line) of the K-map, and the two variables are on the other side. Let (A), ((B)), (C), and (D) be the four variables, the two variables will have four combinations labeled on one side as (A).((B)) , (A).((B)) , (A).((B)) and (A).((B)) ; and the other two will also have the four combinations as (C).(D) , (C).(D) , (C).(D) and (C).(D) on the other side as shown in figure.

If a Boolean function of three variables or four variables is given, the 1s entry in the K-map is done for those combinations that are present in the given expression, and for the other combinations, 0s entries are made.

Example 1: Draw the K-maps for the following Boolean function of three variables.

Solution:

In the K-map of three variables 1s entries are made for the combinations m1, m3, m5, m6, m7, and in the remaining combinations, 0s are entered. The K-map for the same is shown in figure.

Example 2: Draw the K-maps for the following Boolean function of four variables.

Solution:

In the K-map of four variables 1s entries are made for the combinations m2, m3, m4, m6, m7, m11, m14, m15, and in the remaining combinations, 0s are entered. The K-map for the same is shown in figure.

Encircling of Groups:

After constructing the K-map, the pairs of quads and octets of adjacent 1s in the K-map are made for getting the minimal Boolean expression. A pair eliminates one variable with its complement; a quad and an octet eliminate two variables and three variables, respectively, with their complements. Now, it will be discussed how pairs, quads, and octets are formed in the K-map and help minimize the Boolean expression.

Pairs:

In the three-variable or four-variable K-map having 1s and 0's entry, two adjacent 1s (vertically or horizontally) are encircled. The diagonally adjacent 1s are never encircled. The encircled 1s form the pairs, as shown in the figure.

Now it is clear from the K-map of three variables (ref. figure 10 a) that there are two encircled pairs of adjacent 1s, and these pairs correspond to the terms (A) ((B)) and AC . The method of writing these terms is that the variable, which gets changed from complemented form to un-complemented form or vice versa, is dropped with its complement. This can be illustrated as follows: Consider the pair (fig. 10a) whose term is (A) ((B)), the two 1s contained in the pair have the binary numbers 000 and 001 for the variables ABC. In the binary numbers, the variable (C) changes from 0 to 1 (complemented to un-complemented), so this variable is dropped with its complement. The binary number left is 00, having the term (in SOP form) as (A) ((B)) . Similarly, consider the second pair whose term is AC . The two 1s contained in this pair have the binary numbers 110 & 100 for variables ABC. The variable ((B)) changes from 1 to 0, so this variable is dropped with its complement. The remaining (common) binary number 10 for variables AC will have the term (in SOP) as AC . The Boolean algebra is involved in getting the expression for a pair. In the first encircled pair (discussed above) of three variable K-map, each 1 of the pair shows the terms (A) ((B)) (C) and (A) ((B)) (C) (corresponding to binary numbers 000 & 001). When these terms are ANDed, (A) ((B)) is obtained:

\[ (A) ((B)) A (B) (C) (C) A (B) (C) A (B) (C) \]

Similarly, one can verify the terms corresponding to encircled pairs in four variable K-maps as given in the figure.

From the above discussion, it is clear that a pair eliminates one variable with its complements, i.e., the pair will contain the term of two variables in a three-variable K-map and the term of three variables in a four-variable K-map.

Quads:

In the K-map, if four 1s are adjacent in a row or column or in the form of a square, then these 1s are encircled and called quads. (A) term is written for each quad using the same techniques discussed above. The variables that change from complemented to uncomplemented or vice versa are dropped, and the variables that are common in all the four 1s of a quad are considered to write terms in SOP form. Consider a K-map shown in figure.

In the K-map of three variables (figure), the encircled group of 1s shows the quad whose four elements represent the binary numbers 000, 010, 110 & 100 for variables ABC. In the binary numbers, 0 for (C) is common for all four binary numbers, so (C) (in SOP form) is the term for this quad. The variables AB are dropped as each of the variables changes from 0 to 1 or 1 to 0. The Boolean algebra is involved in getting the expression for a quad. The quad combines two pairs (shown by dotted encircles in the figure). In the encircled quad, the two pairs will show the terms AC and AC . When these terms are ANDed, (C) is obtained as

\[ (C) (C) A A A (C) A (C) \]

Similarly, the two quads are encircled in the K-map of four variables (figure). One can verify the terms for each quad. It is clearly illustrated that the quad will contain the term of one variable in a K-map of three variables, and it will contain the terms of two variables in the K-map of four variables. It may, therefore, be stated that a quad eliminates two variables with their complements.

Octets:

The eight adjacent 1s are encircled in a K-map known as an octet. Figure 12 shows the encircled octet (solid line) in a K-map of 4 variables. The term for the octet is ((B)), written with the same technique used for pairs and quads.

An octet eliminates three variables with their complements and gives a term of one variable in a K-map of four variables. In fact, an octet is a combination of two quads, as shown by dotted lines (figure). The terms for two quads are (B) (C) and (B) (C) . When these two terms are combined, it gives:

\[ = (B) (C) + (B) (C) = (B)((C) + (C)) = (B) \]

Overlapping groups:

While making encircled groups in the K-map, it is always tried to have the groups of the largest number of 1s first, then others, i.e., octets are encircled first, then quads, and then pairs. It is important to use the same 1 more than once. In other words, same 1 may be used in more than one encircled group. Such groups are called as the overlapped groups. Some overlapped groups are shown in the figure.

The terms for each encircled group are written in the same manner as is done for regular pairs, quads, and octets.

Rolling groups:

It is also allowed to roll the K-map so that grouping of the largest number of 1s may be formed. To understand this, consider a K-map as shown in figure (14a). In this K-map, while encircling, one can obtain two quads, but using the rolling of the K-map, an octet may be formed as shown in the figure. Here, the rolling is done in such a way that the left-hand side encircled quad touches the right-hand side encircled quad. This looks like an octet. The rolling is shown by half encircling the two groups, as shown in the figure. Thus, the term corresponding to the rolled octet is written in the same fashion as in normal encircling.

The rolling is possible for quads and pairs as illustrated in the figure.

Redundant Groups:

While encircling the groups in the K-maps, there is a possibility that all the elements (1s) of some groups/groups are overlapped by other groups. Such a group whose all 1s are overlapped by other groups is called a redundant group. The redundant groups may be illustrated by considering a K-map shown in the figure.

In this K-map, the encircled groups are one quad and four pairs. But quad is redundant since all four 1s are used to form other pairs. The quad is, therefore, eliminated. So, the valid encircled groups will be as shown in the figure.

The encircled groups of this figure are simplified one and the minimal expression of this K-map is given as: F = A (B) (C) + (B) (C) (D) + (B) (C) (D) + A (B) (C)

Procedure for Simplification:

The different rules for encircling the groups in the K-map have been discussed in the above sections. Now, using these rules, the method of getting the minimal Boolean expression of the given truth table (or function) will be summarized below:

• After forming the K-map, enter 1s for the min-terms corresponding to 1 in the truth table (or enter 1s for the min-terms of the given function to be simplified). Enter 0s for the remaining min-terms.
• Encircle octets, quads, and pairs, of course, remembering rolling and overlapping. Try to form groups of the maximum number of 1s.
• If any such 1s occur that are not used in any of the encircled groups, then these isolated 1s are encircled separately.
• Review all the encircled groups and remove the redundant groups, if any.
• Write the terms for each encircled group.
• The final minimal Boolean expression corresponding to the K-map will be obtained by ORing all the terms obtained above.

Example 3: Using K-map simplify the following Boolean function of three variables.

\[F(A, B, C) =\Sigma (m_0, m_1, m_5, m_6, m_7)\]

Solution:

The K-map for the given function is drawn after encircling the groups of 1s, as shown in figure.

\[F = A (B) + A (B) + (B) (C)\]

Example 4: Using K-map simplify the following Boolean function of four variables. \[F(A,B,C,D,) = \Sigma (0,1,2,4,7,9,11,12)\]

Solution:

The K-map for the given function is drawn, after encircling the groups of 1s, as shown in the figure.

Example 5: Minimize the following function using K-map and realize it with AND, OR & NOT logic gates. \[X(A,B,C,D,) = \Sigma (0,1,2,5,8,10,11,14,15)\]

Solution:

The K -map drawn after encircling the groups of 1s, for the given function is shown in figure.

\[X = AC + (B) (D) + (B) (C) (D)\]

It is interesting to note from this figure that the four 1s at the corners of the K-map forms a quad due to the rolling on both sides, whose term will be (B) (D) .

After getting the minimal Boolean expression, the realization of the function will be as shown in the figure.

Incompletely Specified Functions:

In digital circuits, we come across two types of functions, namely completely specified functions and incompletely specified functions. The functions whose values are specified for all min-terms are known as completely specified functions, and in the K-map, either 0s or 1s are entered for all the min-terms; such functions have been considered so far. But sometimes, we encounter situations in which some min-terms do not occur. For example, Input data to a digital system are sent in 8421 code in which the combinations 0000 through 1001 occur, and 1010 through 1111 are known as illegal combinations as these combinations do not occur. So, the combinations 0000 to 1001 will have the output as 0 or 1, and accordingly, these values may be entered in the K-map. The combinations 1010 to 1111 will have the output of neither 0 nor 1, as these combinations do not occur in the given system. So, these combinations are called as the incompletely specified functions. In the K-map, φ is entered for every incompletely specified function. The φ is called the ‘don't care' condition. While encircling the groups in the K -map φ may be assumed to be either 0 or 1, whichever helps give the simplest expression. The don't care are treated as 1s inside encircled groups in the K-map and are treated as 0s outside the encircled groups. This can be illustrated by taking an example. Suppose we wish to minimize the following function of four variables having the 'don't care' also. The 'don't care' is shown by φ below the summation symbol.

\[X (A, B, C, D) = \Sigma (1,2,3,5,13)+\Sigma_{\phi} (6,7,8,9,10,11)\]

This function shows that in the K-map, 1s are entered corresponding to the minterms 1,2,3,5,13, and φ are entered for 6,7,8,9,10,11, and 0s are entered for the remaining terms. The K-map with these entries is shown in the figure, and its encircling & simplification are shown in the figure. There are two encircled quads, and φ, which are inside the encircled groups, are treated as 1s. The last column of this K-map is not encircled to form the quad, as all its elements are φ. It must be remembered that no such group is formed whose all the elements are φ. The minimal Boolean function of this K - map is given by:

\[X = AC + (C) (D)\]

The general procedure of getting the minimal Boolean expression of a K-map, including the 'don't care' conditions, is summarized below

• After forming the K-map, enter 1s for the min-terms corresponding to 1 in the truth table (or enter 1s for the min-terms of the given function to be simplified). Enter φ to the ‘don't care' conditions and 0s for the remaining min-terms.
• Remembering rolling and overlapping, encircle octets, quads, and pairs. The φ may be treated as 1 if these help in forming the largest groups. No such group will be formed whose all the elements are φ.
• If any such 1s occur that are not used in any of the encircled groups, then these isolated 1s are encircled separately.
• Review all the encircled groups and remove the redundant groups, if any.
• Write the terms for each encircled group.
• The final minimal Boolean expression corresponding to the K-map will be obtained by ORing all the terms obtained above.

Example 6: Minimize the following function using K-map and realize it with NAND gates only.

\[F (W , X ,Y , Z )= \Sigma (0,2,3,5,6,8,9) + \Sigma_{\phi} (10, 11, 12, 13, 14, 15)\]

Solution:

The K -map is drawn for the given function, and encircling of the groups is done as shown in figure.

\[F = W + Y Z + X Z + X Y + X Y Z\]

The realization of this function using NAND gates only is shown in the figure.

NOR Implementation of Boolean Functions:

Implementing the Boolean function with NOR gates requires the simplified Boolean function in the product of sums form. But the K-map discussed above gives the simplified expression in the sum of products form. So, for getting the Boolean expression in POS form, the encircling may be done with 0s and don't care conditions. The same rules will be followed for encircling with 0s and φ. However, the terms for encircled groups are obtained in max-term form. The variables that get changed in moving from one element to the adjacent element in the encircled groups of 0s will be eliminated with their complements, and the variables common to all the elements in the encircled group will be used in writing the max-term. For example, if 01 is common for AB variables in an encircle group of 0s, then the max-term corresponding to 01 will be ((A) + (B)). The final minimal Boolean expression for the K-map will be obtained by ANDing all the terms obtained above. It can further be illustrated by taking an example. Find the minimal Boolean expression using K-map for the following function.

\[F (A, B, C, D) =\Pi(4,6,7,8,10,11) \Pi_{\phi}(0,1,2,13,14,15)\]

In this given function, 0s are entered for the terms 4,6,7,8,10,11 and (\phi) are entered for (0, 1 , 2, 13, 14 , 15) in the K-map, and the minimal expression is obtained in POS form. The K-map is shown in the figure.

\[F = ((B) + (D) () (B) + (C) () A + (C) () A + (C) + (D))\]

Example 7: Minimize the following function using K-map and realize it with NOR gates only.

\[F (A, B, C, D)= \Pi(0,1,4,5,8,12,14,15) \Pi_{phi}(9,11,13)\]

Solution: The K -map is drawn for the given function, and encircling of the groups is done as shown in the figure.

\[F = (A + (B))(C)\]

The realization of this function using NOR gates is shown in the figure.

Example 8: Minimize the following function using K-map and realize it with NOR gates only. \[F (A, B, C, D) =\Sigma (0,1,5,8,10,14) + \Sigma_{\phi}(2,7,11,15)\]

Solution:

The entries of 0s, 1s, and don't care conditions in the K-map are made as per the given problem. The encircling of the groups is done with 0s and φ (shown in figure), since the minimized function is to be realized with NOR gates only.

The minimized function in POS form is given by:

\[F = (A + (C) () A + (D) () (B) + (C) + (D))\]

The realization of this function using NOR gates is shown in the figure.

Five and Six Variable K-map:

The simplification of the Boolean function up to four variables has been discussed in the foregoing sections of this chapter. Maps for more than four variables become complicated, and their use is not very simple. The five-variable map should have 32 squares as it will have min-terms, and the six-variable map will have 64 squares as it will have 64 min-terms. So, the 5-variable K-map will have two blocks (two K-maps, four variables each) of 16 squares, as shown in the figure. If the 5 variables are ABCDE, then variable (A) will represent the two K-maps (of four variables BCDE) for (A) and (A) .

Similarly, a K-map of six variables will have four blocks (four K-maps of four variables) of 16 squares each. If six variables are ABCDEF, the four K-maps of four variables (CDEF) will belong to (A) (B) , (A) (B) , (A) (B) & (A) (B) variables, as shown in the figure.

Simplification of Five and Six Variable Maps:

It has been discussed that the K-map of five variables has two blocks of 16 squares, and the K-map of six variables has four blocks of 16 squares. A pair (two adjacent min-terms) in one block and the other pair in the other adjacent block will be considered adjacent if the positions of the two pairs are the same in their respective blocks. For example, squares 13 & 9 (forming a pair of one block) are adjacent to squares 29 & 25 (a pair of the adjacent block) in a five-variable K-map and thus reduce two variables using the same procedure used in the four-variable map. Similarly, a quad (four adjacent min-terms) of one block and the other quad of the other adjacent bock will be adjacent if the positions of the two quads are the same in their respective blocks. That is, the four squares 19, 23, 31 & 27 (forming a quad of one block) are adjacent to the squares 51, 55, 63 & 59 in an adjacent block of a six-variable map, and these two quads will eliminate three variables. The elements of the diagonal blocks will not be adjacent even if their positions are the same. The simplification can be illustrated by using the following two examples.

Example 9: Simplify the Boolean function of five variables:

\[F (A, B, C, D, E) = \Sigma (0,2,3,4,6,7,8,11,12,13,16,18,19,20,22,23,24,27,28,29)\]

Solution: The K-map for five variables is drawn, 1s are entered for the min terms given in the problem, and the remaining entries are filled with 0s, as shown in the figure.

The encircling is done as given in the figure. The min-terms 0, 4, 12 & 8 of block (A) (forming quad) and the min-terms 16, 20, 28 & 24 of other block (A) are adjacent, thus giving the term of two variables (D) E. The min-terms 3, 2, 7 & 6 of block (A) (forming quad) and the min-terms 19, 18, 23 & 22 of other block (A) are adjacent, thus giving the term of two variables (B) (D) . The min-terms 12, 13 of block (A) (forming a pair) and the min-terms 28, 29 of other block (A) are adjacent, thus giving the term of three variables (B) (C) (D).

Similarly, isolated 1 (min-term 11) of block (A) and isolated 1 (min-term 27) of block (A) are adjacent, thus giving the term (B) (C) (D) E. Now ORing all the terms obtained above, the minimized Boolean expression is given by:

\[F = (D) E + (B) (D) + (B) (C) (D) + (C) (D) E\]

Example 10: Simplify the Boolean function of six variables:

\[F (A, B, C, D, E, F) = \Sigma (2, 3, 6, 7, 10, 11, 14, 15, 18, 20, 22, 24, 26, 28, 30, 41, 50, 52, 54, 56, 58, 60, 62)\]

Solution:

Figure shows the K-map of the given problem.

The encircling is done as given in the figure. The adjacent groups of 1s are shown by dotted lines, and the minimized Boolean expression is shown as:

\[F = A (B) E + (B) E F + (B) (D) F + (B) (C) F + A (B) (C) (D) E F\]

Model questions

1. Discuss K-map for reducing the Boolean function of 4 variables.
2. Taking a suitable example, verify that a quad eliminates two variables and an octet eliminates three variables in a K-map of four variables.
3. What are pairs quads and octets? What is their importance in K-maps? What are the rules for getting the minimal Boolean function using K-maps? Illustrate with examples.
4. Discuss the redundant groups in the K-map.
5. What do you understand by incompletely specified functions? How are these used in eliminating the Boolean functions?
6. Discuss the K-map method of reducing the Boolean function of five variables.
7. Discuss K-map method of reducing the Boolean function of six five variables.
8. Simplify the following Boolean functions using K-map and verify your answer using the theorems of Boolean algebra also. (i) ( , , ) = ∑ )7,5,4,1,0( 1 F a b c (ii) ),,( = ∑ )7,5,4,3,2,1,0( 2 F a b c (iii) ( , , ) = ∑ )7,6,3,1( F3 W X Y Ans.: (i) F = b + a c 1 (ii) F = a + b + c 2 (iii) F3 = W X +W Y
9. Simplify the following Boolean functions using K -map and realized the minimized functions with NAND gates only. (i) Z = A (B) (C) + A (B) (C) + A (B) (C) + A (B) (C) (ii) Z = A (B) (C) + A (B) (C) + A (B) (C) + A (B) (C) + A (B) (C) (iii) f = W X Y +W X Y +W X Y +W X Y +W X Y Ans.: (i) Z = AC + A (B) + A (B) (C) (ii) Z = AC + A (B) + AC (iii) f = W Y + X Y +W Y
10. Simplify the following Boolean functions using K -map and verify your answer using the theorems of Boolean algebra also. (i) ( () ) ( ) ( ) f 1 = A+ (B) +(C) A+ (B) +(C) + A+ (B) +(C) + A+ (B) +(C) (ii) ( () () ) f 2 = A + (B) + (C) A + (B) + (C) A + (B) + (C) (iii) ( () () () ) f 3 = A + (B) + (C) A + (B) + (C) A + (B) + (C) A + (B) + (C) Ans.: (i) ( () () ) f 1 = A + (C) A + (B) A + (B) + (C) (ii) ( () ) f 2 = A + (B) (B) + (C) (iii) ( () ) f 3 = A + (C) A + (B)
11. Minimize the following Boolean functions using K -map and then realize them with NOR gates only. (i) Z a b c ),,( = ∏ )7,6,4,3,2,1( (ii) Z a b c ),,( = ∏ )6,5,4,3,2,0( (iii) Z a b c ),,( = ∏ )6,5,3,2,1,0( Ans.: (i) Z = b (a + c () a + c) (ii) Z = c (a + b () a + b) (iii) Z = a (b + c () b + c)
12. Get the minimal Boolean functions of the following using K-map: (i) = ∑ + ∑ φ ( , , ) )5,2,0( )6,3,1( f 1 A (B) (C) (ii) = ∑ + ∑ φ ( ,, ) )4,1( )7,6,5,0( f 2 X Y Z (iii) = ∑ + ∑ φ ( ,, ) )6,5( )3,2,1,0( 3 f a b c Ans.: (i) f 1 = A + (B) (C) (ii) f 2 = X + Y (iii) f = b c + b c 3 1 Obtain the minimal SOP expression of the following functions and implement them using NAND gates only. (i) ( , , , ) = ∑ 13,9,6,4,1,0( 14, 15, ) F1 A (B) (C) (D) (ii) ( , , , ) = ∑ 13,9,8,7,4,3,2,1,0( 14, 15, ) F2 A (B) (C) (D) (iii) ( , , , ) = ∑ 11,9,8,6,5,3,2,0( 12, 14, 15, ) F3 A (B) (C) (D) (iv) ( , , , ) = ∑ 10,8,5,4,0( 12, 15, ) F4 A (B) (C) (D) (v) ( , , , ) = ∑ 15,7,5,3,2,1( ) F5 A (B) (C) (D) Ans.: (i) F1 = AC (D) + (B) (C) (D) + A (B) (D) + (B) (C) (D) (ii) F2 = A (B) + (C) (D) + A (B) + AC + (B) (C) (D) (iii) F3 = A (B) (D) + A (B) (C) + A (B) (D) + A (B) (C) + (B) (C) (D) + A (B) (C) + A (B) (C) (D) (iv) F4 = (C) (D) + A (B) (D) + A (B) (C) + A (B) (C) (D) (v) F5 = A (D) + (B) (C) (D) + A (B) (C)
13. Obtain the minimal Boolean functions of the following, using K-map: (i) = ∑ + ∑ φ ( , , , ) )9,8,7,6,5,3,2,0( 10( 11, 12, 13, 14, 15, ) F1 A (B) (C) (D) (ii) ( , , , ) = ∑ )9,8,7,4,3,2,1,0( + ∑ 10( 11, 12, 13, 14, 15, ) 2 φ F A (B) (C) (D) (iii) = ∑ + ∑ φ ( , , , ) 13,5,3,2,1( ) 11,9,8,7,6( 15, ) F3 A (B) (C) (D) (iv) = ∑ + ∑ φ ( , , , ) 10,9,2( 12, 13, ) 14,5,1( 15, ) F4 A (B) (C) (D) (v) = ∑ + ∑ φ ( , , , ) 10,8,5,1,0( 14, ) 11,2( 15, ) F5 A (B) (C) (D) Ans.: (i) F1 = A + (C) + (B) (D) + (B) (D) (ii) F2 = (B) + (C) (D) + (C) (D) (iii) F3 = AC + (D) (iv) F4 = (C) (D) + A (B) + (B) (C) (D) (v) F5 = (B) (D) + AC + AC (D)
14. Using K-map, obtain the minimal POS expressions of the following and implement them with NOR gates only. (i) ,,( , ) = ∏ 15,14,13,12,11,10,9,5,4,2,1,0( ) F1 A (B) (C) (D) (ii) ( , , , ) = ∏ 12,11,9,7,5,3,2( 13, 14, 15, ) F2 A (B) (C) (D) (iii) ( , , , ) = ∏ 10,8,5,4,3,2,1,0( 14,13, ) F3 A (B) (C) (D) (iv) ( , , , ) = ∏ 13,11,9,8,7,6,4,2,1,0( ) F4 A (B) (C) (D) (v) ( , , , ) = ∏ 12,11,7,6,5,1( 15,13, ) F5 A (B) (C) (D) Ans.: (i) ( () () () () ) F1 = (C) + (D) A + (C) A + (B) A + (C) A + (B) + (D) (ii) ( () () () ) F2 = A + (B) (B) + (D) A + (D) A + (B) + (C) (iii) ( () () () () ) F3 = A + (B) (B) + (D) A + (C) A + (C) + (D) (B) + (C) + (D) (iv) ( () () () ) F4 = A + (D) (B) + (C) A + (C) + (D) A + (B) + (D) (v) ( () () () ) F5 = A + (B) + (C) A + (B) + (C) A + (C) + (D) A + (C) + (D)
15. Using K-map, obtain the minimal POS expressions of the following and implement them with NOR gates only. (i) ,,( , ) 14,13,12,6,5,1( ) )4,2( 1 = ∏ ∏ φ F A (B) (C) (D) (ii) ( , , , ) 10,7,3,2( 14,11, 15, ) 12,5,1( ) 2 = ∏ ∏ φ F A (B) (C) (D) (iii) ( , , , ) )8,7,6,5,3,2( 10( 12,11, 14,13, 15, ) 3 = ∏ ∏ φ F A (B) (C) (D) (iv) ( , , , ) 12,9,7,5,4,2( ) )6,1,0( 4 = ∏ ∏ φ F A (B) (C) (D) (v) ( , , , ) 14,7,6,5,4,3,1,0( 15, ) 13,9,2( ) 5 = ∏ ∏ φ F A (B) (C) (D) Ans.: (i) ( () () ) F1 = (B) + (D) (B) + (C) A + (C) + (D) (ii) ( () () ) F2 = A + (C) (B) + (C) (C) + (D) (iii) ( ) F3 = (C) (B) + (D) (iv) ( () () ) F4 = A + (B) A + (D) (B) + (C) + (D) (v) ( ) F5 = A (B) + (C)
16. Minimize the following functions using the K-map method. (i) ( , , , , ) = ∑ 14,9,8,7,4,3,2,1,0( 15, 16, 17, 18, 19, 25, 31, ) F1 A (B) (C) (D) E (ii) ,,,,( ) = ∑ )29,23,22,21,20,15,14,13,12,10,7,6,5,4( + ∑ )26,25,24,2,1,0( 2 φ F A (B) (C) (D) E (iii) ),,,,( = ∑ )23,22,20,19,17,16,11,10,9,7,6,4,2,1( + ∑ )31,30,29,28,24,13,12( 3 φ F A (B) (C) (D) E (iv) ,,,,,( ) = ∏ 4,2,1,0( )43,42,41,40,36,34,29,28,20,19,17,15,14,10,9,8,7,5, F4 A (B) (C) (D) E F (v) F 5 BA (C) (D) E F ),,,,,( = ∑ ,16,15,13,10,8,,4,2,0( )61,60,58,57,56,50,48,47,45,42,40,34,32,26,24,20,18 (vi) ),,,,( = ∑ ,10,9,5,4( )31,30,29,27,26,25,24,21,20,19,18,16,15,14,13,12,11 F6 A (B) (C) (D) E Ans.:(i) F1 = BC +(C) (D) + A (B) (D) E + A (B) (C) (D) + A (B) (D) E + (B) (C) (D) E + (B) (C) (D) E (ii) F2 = AC + BC + A (B) (D) E (iii) F3 =(C) (D) E+(B) (C) (D) E+(B) (C) (D)+ A (B) (D) E+ A (B) (C) E+ A (B) (C) (D)+ A (B) (C) (D)+ A (B) (C) (D) (iv) = ( + + + () + + + () + + + () + + + ) F4 A (B) (C) E (B) (C) (D) E A (B) (C) (D) (B) (D) E F (A + (B) + (C) + (D) + E () A + (B) + (D) + E + F () A + (B) + (C) + (D) + F) (A + (B) + (C) + (D) + E () (B) + (C) + (D) + E + F) (v) F5 = DF+(B) (C) DF+ A (C) E F+ A (B) (C) E (vi) F6 = BD+BE+(B) (C) (D)+ A (C) E+ A (C) (D)+A (B) (C)