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

