Prime Implicants and Essential Prime Implicants in K Map

Implicants 

Let an SOP function be expressed in the form  
                                                                                                                          
f(x1, x2,…, xm) = x1x2….xn + x1x2….xm                            (2.27)                  

Let, at least, any one of the product terms, say, x1, x2, x3, …, xm = 1. Then, we observe that the given function f(x1, x2, x3, …, xm) = 1. In such a case, we call the product term x1, x2, x3, …, xm  as an implicant of the given logic function f(x1, x2, x3, …, xm).
      We now define the term implicant. Let f(x1, x2, x3, …, xm) be an m-variable SOP function and S be the product term x1x2….xin that function. We now state that S is an implicant of the function f if and only if the value S is equal to 1 so that the value of the function f is also equal to 1. It can be seen that this definition is quite lengthy. To explain this, consider the following example. Let

                    f(x1, x2, x3, x4) = x1x2x3x4 + x1x2x3x4 + x1x2x4 + x1x3x4           (2.28)

In Eq. (2.28), we have four product terms on the RHS. Let any one or more of the above four terms give an output of 1. Then, this implies that f = 1. For example, if x1x2x4 = 1, then f = 1. Similarly, when x1x2x3x4 = 1 or x1x2x3x4 = 1, then also f = 1, and so on. Thus each one of the above terms is an implicant. Notice also that a minterm will be an implicant, but an implicant need not be a minterm. For example, the terms x1x2x3x4 and x1x2x3x4 are implicants as well as minterms. But, the implicants x1x3x4 and x1x2x4 are not minterms.
      If an implicant must make a function equal to 1, then a term that makes a function equal to 0 is not an implicant of that function. Consider the function 
                                                   f (a, b, c, d)= abd + abc + acd                 (2.29)

In this function, whenever b = d = 0, f = 0. This means that the term b'd' is not an implicant of f.

Prime Implicants

A prime implicant is an implicant from which if we delete any variable (or literal), then it can no longer be considered as an implicant. For example, consider the term abd in Eq. (2.28). From this equation, if we remove any one of the terms (i.e., a, b, or d), then the resulting product term will no longer imply f.  That is, if a is removed, then the resulting term bd is no longer an implicant of the function f. Then, we say that the term abd is a prime implicant of f. Similarly, the other terms (i.e., abc and acd) are also prime implicants of f.

Essential Prime Implicant

A prime implicant is said to be essential, if a minterm in an SOP expression is covered by only one prime implicant. For example, let us consider the K-map shown in Fig. 2.25. We find that minterm m2 is covered by prime implicant A only. So, we call A as an essential prime implicant. Similarly, minterm m12 is covered only by prime implicant B, and hence B is an essential prime implicant. We also find that minterms m5 and m15 are not covered by any other prime implicants; hence C is also an essential prime implicant. Summarizing the discussions, we may now state that:

  1. Any minterm or combinations of minterms, which make an SOP function equal to 1 is an implicant.
  2. If, from an implicant, a literal removed makes it not to be a member of the function, it becomes a prime implicant.
  3. In a reduced function, if the removal of a prime implicant changes the structure of the function, then that prime implicant is essential in forming the function.

Figure 2.26 highlights the implicants as A, B, C, D, and E, respectively. The corresponding minterms are a'cd, abd, ab’c, bc'd, and acd, respectively. Of the five implicants, all are prime implicants. However, implicants D, and E are not essential, as the minterms in them are already covered by A, B, and C. These prime implicants are called redundant terms.



K Map Don't Care Terms Problems


Example 5: Simplify S = S m(0, 1, 2, 4, 5, 7, 9, 10) + d (3, 8, 15), whered denotes don’t care terms.
                                             
Solution: The K-map is drawn as shown in Fig. 2.23. Here, we represent don’t-care terms by Greek letter f, since f may be thought of  as a combination of 0 and 1. We now look for the cells in which the fs are entered, and see whether they can be used to eliminate any variable or not.
      It can be observed that the don’t-care term in cell 3 can be grouped with entries in cells 1, 5 and 7. Hence, in this case, we treat the cell-3 entry f as a valid 1, and it forms a quad with the entries in cells 1, 5 and 7. Similarly, the entry f in cell 8 can be grouped with the 1 in cell 9 to form a pair. However, f in cell 15 cannot be combined with any 1-entry, and hence it is discarded. The final solution now becomes:

                              S = a′d  + b′cd′ + ab′c′+ a′bc′                                    (2.26)

      It is to be noted that f in cell 8 can be grouped with the 1 in cell 10 also. However, the 1 in cell 10 is already paired with the 1 in cell 2. Hence, we discard the pairing with f in this case.




Four Variable Karnaugh Map with Examples

Two types of designations of the 4-variable K-map are shown in Figs. 2.20(a) and (b), respectively.


It can be seen that the four-variable K-map may be regarded as a combination of a three-variable horizontal K-map and a three-variable vertical K-map. The cells are designated as shown in the figures. In the Format-1 scheme shown in Fig. 2.20(a), which we follow in this text, the left topmost cell is designated as 0 and this represents cell 0000. The right cell adjacent to this is designated as 4 and this represents cell 0100. Similarly, the bottom cell adjacent to cell 0 is designated as 1 and this represents cell 0001. The other designations follow this pattern.
       In the Format-2 scheme, cell 0 is the same as in our system. But cell 1 in the new scheme is our cell 4. Similarly, cell 4 in the new scheme is cell 1 in our scheme. The Type-2 designations are illustrated in Fig. 2.20(b).

EXAMPLE 3: Simplify S = S (0, 1, 2, 3, 7, 13, 14, 15)

Solution: The desired four-variable K-map is drawn as shown in Fig. 2.21.


From the figure, we find that there are 5 groups in this example. Of these, Group 1 is a quad and Group 2 to 5 are pairs. We find that the members of Group 5 have already been selected by Groups 1 and 2; therefore it (Group 5) is a redundant group and can be discarded from the final expression.  The desired answer is:  
                                                                                                                                                                                       
                                      S = Group 1 + Group 2  + Group 3 + Group 4
                                         a'b' + bcd + abc + abd             (2.24)

Example 4:     S = S(m0, m1, m4, m5, m6, m7, m8, m9, m10, m11, m12, m13, m14, m15)

Solution: The K-map for Example 4 is shown in Fig. 2.22. We find that we can combine eight members horizontally, and eight members vertically. A grouping of eight members (called as an octet) eliminates three variables. Thus the vertical group Octet 1 can be seen to eliminate the variables a, c, and d, as they appear in  the complemented and uncomplemented forms. This leaves b  as one of the variable left uneliminated in the final output. Similarly, the horizontal group Octet 2 can be seen to eliminate the variables a, b, and d, as they also appear in the complemented and uncomplemented forms. This grouping leaves c′ as the uneliminated variable. Finally, we notice that a quad group also exists in this case. The quad produces the product term ab′.                                                        The reduced sum S can now be obtained as the sum of the two uneliminated varables b and c′ and the term ab′. Thus we obtain:

S = Octet 1 + Octet 2+ Quad
   = b + c+ ab                                                         (2.25)



Three Variable Karnaugh Map with Examples

The three-variable K-map is shown in Fig. 2.18. Notice the way in which the cells are designated. The cells 4 and 5, as well as 6 and 7, are designated in a reversed order.  This is done in order to bring together the adjacent cells that differ from each other in one variable only. For example, cells 00 and 01 differ in the position of the variable b, a being the same for both the cells. Similarly, cells 01 and 11 differ in the position of a, and cells 11 and 10 differ in the position of b. This means that K-map makes use of Gray code to designate its cells.


It may also be noted from Fig. 2.18 that cells 10 and 00 are adjacent, since they differ in one position only. Therefore we can club (or group or pair) the entries in these two cells for the elimination of the variable a that appears as complemented and uncomplemented in the map.

Example 2: Simplify the logic expression, S = S (m0, m1, m2, m4, m7).

Solution: The given logic function has eight minterms and hence requires a three-varible K-map for its reduction. The relevant map is drawn as shown in Fig. 2.19. and grouping of the entries are done as shown. The 1-entry cells are m0 = 000, m1= 001, m2 = 010, m4 = 100, and m7 = 111. These are the given minterms. The cells not mentioned in the given example will have 0s as entries. Thus cells m3, m5, and m6 have 0 as entry, as shown. It is important that in a K-map all the cells must be filled with entries; no cells must be left empty.
      There are four groups in the map. Of these, we notice that Pair 1 eliminates the variable c, as this is an encirclement covering cells 000 and 001. Similarly, Pair 2 covers cells 000 and 011; this eliminates the variable b. In the same fashion, Pair 3 eliminates the variable a since this is an encirclement between cells 000 and 100. Finally, Group 4 has only one member in it, and it can be seen that this member cannot be paired with any other member for want of adjacency. So, no elimination is possible in this case. Such an entry with only one element in it is called a singleton.


The final answer can now be obtained as follows:

                                             Pair 1:     a'b'c' + a'b'c = a'b'(c + c')  = a'b'
                                          Pair 2:    a'b'c' + a'bc' =  a'c' (b + b') = a'c'
                                          Pair 3:    a'b'c' + ab'c' = (a'+ a)'b'c' = b'c'
                                    Singleton:     abc
We get the final sum as:
                                             S = Pair 1 + Pair 2 + Pair 3 + Singleton
                                   = a'b' + a'c'+ b'c' +abc                   (2.23)

          In the discussion given above, we have explained the K-map reduction process in detail. In actual practice, we don’t follow such detailed steps on the paper, but make the eliminations mentally. For this we notice (as explained previously) that the element that appears in complemented and uncomplemented forms gets eliminated in a pairing process. For example, when the cells 00 and 10 are paired together, the first variable gets eliminated, as it appears in the complemented and uncomplemented forms. Thus, by visual inspection of the K-map, we can perform logic reduction. It can be easily seen that the K-map method of logic simplification is very fast and simple.

Two Variable Karnaugh Map Tutorial

Figure 2.16(a) shows a two-variable K-map. This is a square with four cells in it. The variables are entered on the map, as shown in the figure. It can be seen that each cell represents a particular minterm (or maxterm). For example, top cell on the left represents the minterm a'b' (≡00), the top cell on the right represents a'b (≡01), the left cell on the bottom represents ab' (≡10), and the right cell on the bottom represents ab (≡11).  An entry in a particular cell represents the presence (or, absence) of the corresponding minterm. This is illustrated in Fig. 2.16(b).  The 1s in cells 01 and 11 indicate that the minterms a'b and ab, respectively, are present in the SOP expression. The 0s entered in cells 00 and 10 represent the absence of the minterms a'b' and ab', respectively, in the SOP expression.


Figure 2.17(a) shows the pairing of variable b and its complement b’. This pairing eliminates the variable b. The variables b and b’ are said to form a pair. We find similar pairs in Figs. 2.17(b), and 2.17(c), where variables a, and a’ are, respectively, eliminated.  In Fig. 2.17(d), however, we find that we can pair all the four variables; this results in the elimination of both the variables a and b, as illustrated in the figure. The grouping of four variables is called a quad (the author prefers to call this as a quartet, in similarity to the term octet, which represents the grouping eight variables).



Consensus Theorem with Examples

Consensus Theorem in Digital Electronics are a powerful pair of theorems used in algebraic simplification of logic functions. The main theorem and its complementary may be stated as:

             xy + yz + zx′ = xy + zx′                                     (2.21a)
                 (x + y)(y + z)(z + x′) = (x+ y)(z +x′)                 (2.21b)
(a) Proof of the main theorem: First, multiply the middle term yz with  to yield

                          LHS = xy + (x + x′)yz + zx′ = xy + xyz + x′yz x′z
                                  = xy(1 + z) + x′z(1 + y) = xy + xz = RHS

(b) Proof of the complementary theorem: To prove the complement of the consensus theorem, as before, consider the LHS term:

                               LHS =  (x+ y)(y +z)(z + x′) = (xy + xz + y + yz)(z + x′)
                                        =  xyz + xz + yz + yx′ + xz + x′yz
                                        = xz + yz + yx′
                                     
Now, we expand RHS, which yields

                              RHS =  (x+y)(z+x′) = xz + yz +x′y
                                                                       
                              LHS = RHS

Extended Form I of the Consensus Theorem

This theorem states that:
                                      x′y′ + y′z′ + z′x = x′y′ + z′x

Proof:  We have the LHS given by

                                     LHS = x′y′ + y′z′ + z′x

Adding x and x′ to the middle term yields
                x′y′ + x′y′z′ + xy′z′ +z′x = x′y′(1+ z′) + zx′(1+ y′) = x′y′ + z′x = RHS
Complementary of Extended Form I

                                               (x′ + y′)(y′ + z′)(z′ + x) = (x′ + y′)(z′ + x)

Extended Form II of the Consensus Theorem

This theorem states that:
                                     xy +yzw + zx′ = xy + zx

Proof: Proof follows the same steps as given above. It can also be noticed that the middle term can contain any number of terms; all of them will get eliminated as illustrated below:

                                     xy + yzwabcd..... + zx′ = xy + zx′

STRAIGHT SIMPLIFICATION  BY  USING  BASIC  RULES

We now perform logic simplifications using the laws are rules given in Sections 2.16 and 2.17.  Reduction using basic laws and rules is known as straight simplification. The examples to follow will illustrate the procedure.

Example 1: Simplify the Consensus theorem

(a) Proof of the main theorem: First, multiply the middle term yz with  to yield

                                LHS = xy + (x + x′)yz + zx′ = xy + xyz + x′yz + x′z
                                = xy(1 + z) + x′z(1 + y) = xy + xz  = RHS

(b). Proof of the complementary theorem: To prove the complement of the consensus theorem, as before, consider the LHS term. Thus

                               LHS =  (x + y)(y + z)(z + x′) = (xy + xz +yy + yz)(z + x′)
                                        = xyz + xz + yz + yzx′ = xz + yz

It can be seen that this kind of simplification is based on hunch and experience, and can be quite difficult when the expressions become complex. So, we make use of the Karnaugh-Map method or the Quine-McCluskey tabular method for logic simplification.

Boolean Algebra Simplification Laws with Proof

We now discuss a few basic laws used in logic simplification. Each of these basic laws is stated along with its complementary law. It may be seen that these laws can be proved using either truth tables or the basic rules given above.

2.16.1    Idempotent Laws

Idempotent  laws state that :                          
                                                                  x + x = x                                                          (2.14a)
                                                     x × x = x                                                     (2.14b)

The word idempotent (same power) was coined by the American professor of computer science Benjamin C. Pierce. It was derived from the words idem (same) and potent (power). Proofs of the relations stated above are given in Table 2.10. Inspection of columns 3 and 4 of Table 2.10 reveals that the summation x + x and the product xx results in x itself.

Table 2.10 Truth table proving Eqs. (2.14a) and (2.14b)                                                             
x
x
x + x = x
x× x = x
0
1
0
1
0
1
0
1

2.16.2    Absorption Laws

 Let x and y be Boolean variables. Then, absorption laws state that:

                                                         x + xy = x                                                             (2.15a)
                                                        x(x + y) = y                                                      (2.15b)

Proof of absorption laws using truth table: As stated above, these laws can be proved by using truth tables, or otherwise.  Proof of the first of the two absorption laws (i.e., x + x y = x) is given in Table 2.11.  Similar steps can be used to prove the remaining relations. The first and last columns of Table 2.11 agree showing the validity of the proof.  Here, the variable y is absorbed by the variable x, and hence the name absorption law.

                    Table 2.11 Truth table to prove x + xy = x

x
Y
x y
x + x y
0
0
1
1
0
1
0
1
0
0
0
1
0
0
1
1

Proof of Absorption law using algebraic method: We can prove the first of the absorption laws by using basic algebra also. For this, we write the LHS of the given equation:
                                   
                                                LHS = x + x y = x (1 + y) = x∙1 = x = RHS

where we have used the basic rule 1 + y = 1. It can be seen that this proof is comparatively faster. However, it may be simpler and faster only for equations containing a smaller number of variables.

Proof of the complement of the absorption law: LHS of Eq. (2.15b) is given by

                                       LHS =  x (x + y) = x + x y = x(1 + y) = x = RHS                      
where for proving the law, we have used two basic relations, viz.,  x x = x, and 1 + y = 1.

2.16.3   Laws Related to Absorption Laws

There are a few other laws associated with the absorption law. These are discussed below.

(a) Subsidiary 1: This law states that

x + x′y = x + y                 (2.16a)

Proof: The LHS of the given expression may be written in the form:

LHS = x+x′y = x(1+y)+ x′y = x+xy+ x′y = x+y(x+x′) = x + y = RHS                                                             

where we have introduced the term 1 + = 1 into the LHS part of the equation for the simplification.

(b) Subsidiary 2 (Complementary of law a): This law states that:

x(x′ + y) xy                       (2.16b)

Proof: The LHS of the given expression may be written in the form:

LHSx(x′ y) xx′ + xy xy = RHS

(c) Subsidiary 3: This law states that

x′ + xy = x′ y                                                             (2.17a)                             
Proof: The LHS of the given expression may be written in the form:

                  LHSx′ xy =  x′(1+y)+ xy = x+x′xy = x′+y(1+x) = x′ + y  = RHS

(d) Subsidiary 4 (Complementary of law c): This law states that

                               x′(x+y) =  x′y                                                                   (2.17b)                        
Proof: The LHS of the given expression may be written in the form:

                                              LHS = x′(x+y) =  x′x + x′y = x′y  = RHS

2.16.4   Commutative Laws

Commutative laws state that:
x + y = y + x                         (2.18a)                             
               x y = y x                           (2.18b)

2.16.5   Associative Laws

Associative laws state that:
 x + (y + z) = (x + y) + z                 (2.19a)
         x(y z) = (x y)z                         (2.19b)

2.16.6   Distributive Laws

Distributive laws state that:
                                                        x(y + z) = x y + x z                                                     (2.20a)                     
                                                       x + yz = (x + y) (x +z)                                                  (2.20b)

The second law given by Eq. (2.20b), viz., x + y z = (x + y)(x +z) is not found to conventional algebra and is special of Boolean algebra alone.