Page 43 - Computer science 868 Class 12
P. 43
1.13 FORMATION OF GROUPS BY OVERLAPPING
One or more minterms or maxterms may be included in multiple groups in a K-map. This is due to the unavailability
of other consecutive terms or with the intent of forming the maximum combinations of the groups. For making the
maximum combinations of the groups, they can be overlapped with other groups. A few examples are given below to
support this fact.
Example 5: Minimise a Boolean expression F(A, B, C) = π(0, 1, 2, 3, 4, 5)
Solution: First, draw a POS K-map with A at the left and B, C at the top. Quad 1: M , M , M , M 3
2
1
0
M = A+B+C
0
Then fill 0 in the grids mentioned and 1 in the remaining boxes. M = A+B+C'
1
B+C B+C' B'+C' B'+C M = A+B'+C
2
3
A 0 0 0 1 0 3 0 2 M = A+B'+C'
Literals B and C are in both forms.
A' 0 4 0 5 1 7 1 6 Hence, M .M .M .M = A
1
3
2
0
A quad can be formed either with M +M +M +M or with M +M +M +M . Quad 2: M , M , M , M 5
1
0
4
0
1
4
2
3
1
5
0
Then M +M can form a pair in the former case and M +M can form a pair M = A+B+C
0
3
2
5
4
in later case. But a pair eliminates only 1 variable and a quad removes 2 M = A+B+C'
1
M = A'+B+C
4
variables. The purpose of minimisation is to eliminate maximum variables, M = A'+B+C'
5
hence overlapping quad is considered and not pairs. Literals A and C are in both forms.
Hence, M .M .M .M = B
1
4
5
0
Example 6: Given F(P, Q, R, S) = Σ(4, 5, 8, 9, 10, 11, 12, 13, 14, 15) Thus, the reduced POS expression = A.B
Reduce the above expression by using a four-variable Karnaugh’s Map.
Solution:
R'.S' R'.S R.S R.S' Octet 1: m +m +m +m +m +m +m +m = P
15
14
10
12
11
13
9
8
P'.Q' 0 0 0 1 0 3 0 2 Quad 1: m +m +m +m = Q.R'
4
5
12
13
P'.Q 1 4 1 5 0 7 0 6 [Here overlapping quad m +m +m +m is preferred
13
12
5
4
P.Q 1 12 1 13 1 15 1 14 over pair m +m as it eliminates 2 variables.]
5
4
P.Q' 1 8 1 9 1 11 1 10 Thus, the reduced SOP expression: P+Q.R'
1.14 GROUPING BY MAP ROLLING
If we fold a K-map horizontally or vertically, then the edges intersect and a formation of a pair, a quad or an octet is
made. A few formations of the pairs, the quads and the octets are illustrated below.
0 1 3 2
0 1 3 2 4 5 7 6
4 5 7 6 12 13 15 14
8 9 11 10
0 1 3 2 0 1 3 2
4 5 7 6 4 5 7 6
12 13 15 14 12 13 15 14
8 9 11 10 8 9 11 10
41
Boolean Algebra 41

