Page 41 - Computer science 868 Class 12
P. 41

The four variable POS K-map in both forms can be drawn as follows:

                                  C+D       C+D'       C'+D'      C'+D
                         A+B   A+B+C+D    A+B+C+D'   A+B+C'+D'  A+B+C'+D
                                   0          1         3          2              C+D
                         A+B'  A+B'+C+D   A+B'+C+D'  A+B'+C'+D'  A+B'+C'+D     A+B     0 0      0 1     1 1     1 0
                                   4          5         7          6           0 0      0       1       3        2
                         A'+B'  A'+B'+C+D  A'+B'+C+D' A'+B'+C'+D' A'+B'+C'+D
                                  12         13         15         14          0 1      4       5       7        6
                         A'+B  A'+B+C+D   A'+B+C+D'  A'+B+C'+D'  A'+B+C'+D     1 1      12      13      15      14
                                   8          9         11         10          1 0      8       9       11      10

                 1.12.2 Plotting Values in the Grids
                 We know that the terms in the Boolean expression are mentioned either in canonical form or cardinal form of its
                 maxterms and minterms. Thus, values are plotted in the grids in the following manner:
                 •  If it is a SOP expression, the specified minterm boxes are filled by 1 and the remaining boxes by 0.
                 •  If it is a POS expression, the corresponding maxterm grids are filled by 0 and the remaining grids by 1.

                 1.12.3 Formation of Groups
                 The next step involves framing groups. Groups are formed by combining similar values of consecutive cells either
                 horizontally or vertically. Grouping diagonally is not allowed. A group can be
                 a.  A Pair: Combining TWO consecutive horizontal or vertical cells containing 1’s (in case of SOP) or 0’s (in case of POS).
                 b.  A Quad: Joining a set of FOUR 1’s (in case of SOP) or FOUR 0’s (in case of POS) placed together horizontally or vertically.
                 c.  An Octet: Taking a group of EIGHT 1’s (in case of SOP) or EIGHT 0’s (in case of POS) placed together horizontally or
                   vertically.

                 We must consider the maximum combination. Hence, first look for an Octet, then a Quad and finally a Pair.
                 Let us understand this better with the help of some examples.             An Octet eliminates 3 variables.
                                                                                           A Quad removes 2 variables.
                 Example 1: Minimise a Boolean expression F(A, B, C) = Σ(0, 2, 3, 4)       A Pair cancels 1 variable.
                 Solution: First, draw the SOP K-map properly mentioning the literals and the cardinal numbers.

                                                          B'.C'   B'.C     B.C    B.C'
                                                    A'     0       1       3       2
                                                    A      4       5       7       6
                 Plot 1’s in the grids mentioned (i.e., 0, 2, 3 and 4) and 0 in the other squares (i.e., 1, 5, 6 and 7).

                                                          B'.C'   B'.C     B.C    B.C'
                                                    A'    1 0     0 1     1 3     1 2
                                                    A     1 4     0 5     0 7     0 6
                 The squares containing 1’s vertically (i.e., m  and m ) and horizontally (i.e., m  and m ) will form pairs. The variables
                                                        0
                                                                                             3
                                                                                      2
                                                               4
                 that are changing their signs are eliminated to minimize the variables.
                                     Pair 1                            Pair 2
                                     m  = A'.B'.C'                     m  = A'.B.C'
                                                                         2
                                      0
                                     m  = A. B'.C'                     m  = A'. B.C
                                                                         3
                                      4
                                     A is changing sign and is cancelled  C is changing sign and is removed
                                     Resulting minimised value = B'.C'  Resulting minimised value = A'.B
                 So, the minimised expression is B'.C' + A'.B

                                                                                                                        39
                                                                                                      Boolean Algebra   39
   36   37   38   39   40   41   42   43   44   45   46