Page 45 - Computer science 868 Class 12
P. 45

1.15 REDUNDANT GROUPS
                 We have learnt that the groups can also be formed in a K-map by overlapping with other groups. When two groups
                 overlap, there are some common elements in both groups while some are distinct. But if any group has all the elements
                 already contained in other groups, then it is termed as a redundant group. A redundant group is thus an extra group
                 that is not included in the final expression.
                 Let us understand this with the help of some examples.

                 Example 10: Minimise a Boolean expression F(A, B, C) = Σ(0, 1, 5, 7)    Pair 1: m +m  = A'.B'
                                                                                                    1
                                                                                                 0
                 Solution:                         B'.C'   B'.C     B.C    B.C'          Pair 2: m +m  = A.C
                                                                                                    7
                                                                                                 5
                                                                                                    5
                                                                                                 1
                                             A'    1 0     1 1     0 3     0 2           Pair 3: m +m  = B'.C
                                             A     0 4     1 5     1 7     0 6           Reduced SOP expression: A.B'+A.C
                 Pair m +m  is an extra pair as m  is already paired with m  and m  is already paired with m . So, this redundant group
                      1
                                             1
                                                                                                 7
                          5
                                                                    0
                                                                          5
                 is not included in the Boolean expression.
                 Example 11: Given F(P, Q, R, S) = Σ(0, 1, 2, 3, 5, 7, 13, 15)
                 Reduce the above expression by using a 4 – variable K-map, showing the various groups (i.e., octal, quads and pairs).
                 Solution:
                                                   R'.S'    R'.S    R.S     R.S'
                                                                                         Quad 1: m +m +m +m  = P'.Q'
                                                                                                  0
                                                                                                        2
                                                                                                     1
                                                                                                           3
                                            P'.Q'  1  0    1  1    1  3    1  2          Quad 2: m +m +m +m  = Q.S
                                                                                                        13
                                                                                                            15
                                                                                                  5
                                                                                                     7
                                            P'.Q   0  4    1  5    1  7    0  6          Quad 3: m +m +m +m  = P'.S
                                                                                                           7
                                                                                                  1
                                                                                                     3
                                                                                                        5
                                             P.Q    0     12   1     13   1     15   0    14  Reduced SOP expression: P'.Q'+Q.S
                                            P.Q'   0  8    0  9     0     11   0     10
                 The elements of m .m .m .m  group are already involved in the other two quads. Hence, it is an extra (redundant)
                                        5
                                           7
                                     3
                                  1
                 quad that is excluded from the final expression.
                 Example 12: Given F(A, B, C, D) = π(0, 1, 2, 3, 5, 6, 7, 8, 10, 14)
                 Reduce the above expression by using a 4 – variable K-map, showing the various groups (i.e., octal, quads and pairs).
                 Solution:                          C+D     C+D'    C'+D'   C'+D
                                             A+B    0  0    0  1    0  3    0  2
                                             A+B'   1  4    0  5    0  7    0  6
                                             A'+B'   1     12   1     13   1     15   0    14
                                             A'+B   0  8    1  9     1     11   0     10

                 Terms M  and M  had already formed a quad with M .M .M .M  and terms M1, M3 with M .M .M .M . So, M .M .
                                                                          10
                                                                       8
                                                                                                       3
                        0
                                                                                                          5
                                                                                                    1
                                                                                                                        1
                                                                                                                    0
                                                                                                             7
                                                                0
                                                                   2
                                2
                 M .M  is a redundant group.
                  2
                      3
                 Quad 1: M .M .M .M  = B+D
                                    10
                                 8
                             2
                          0
                 Quad 2: M .M .M .M  = C'+D
                                     14
                                 10
                          2
                             6
                 Quad 3: M .M .M .M  = A+D'
                             3
                                 5
                                    7
                          1
                 Quad 4: M .M .M .M  = A+B
                                 2
                                    3
                          0
                             1
                 Reduced POS expression: (C'+D).(B+D).(A+D')
                                                                                                                        43
                                                                                                      Boolean Algebra   43
   40   41   42   43   44   45   46   47   48   49   50