Determine the Minimal sum of products for the Boolean expression?
Obtain the minimal sum of products for the Boolean expression f=(1,2,3,7,8,9,10,11,14,15) using Quine-McCluskey method.
Initially these minterms are represented in the binary form as shown in below table and the above binary representation is grouped into a number of sections in terms of the number of 1's as shown in below table.
Binary representation of minterms
|
Minterms
|
U
|
V
|
W
|
X
|
|
1
|
0
|
0
|
0
|
1
|
|
2
|
0
|
0
|
1
|
0
|
|
3
|
0
|
0
|
1
|
1
|
|
7
|
0
|
1
|
1
|
1
|
|
8
|
1
|
0
|
0
|
0
|
|
9
|
1
|
0
|
0
|
1
|
|
10
|
1
|
0
|
1
|
0
|
|
11
|
1
|
0
|
1
|
1
|
|
14
|
1
|
1
|
1
|
0
|
|
15
|
1
|
1
|
1
|
1
|
The Group of minterms for different number of 1's
|
of 1's
|
Minterms
|
U
|
V
|
W
|
X
|
|
1
|
1
|
0
|
0
|
0
|
1
|
|
1
|
2
|
0
|
0
|
1
|
0
|
|
1
|
8
|
1
|
0
|
0
|
0
|
|
2
|
3
|
0
|
0
|
1
|
1
|
|
2
|
9
|
1
|
0
|
0
|
1
|
|
2
|
10
|
1
|
0
|
1
|
0
|
|
3
|
7
|
0
|
1
|
1
|
1
|
|
3
|
11
|
1
|
0
|
1
|
1
|
|
3
|
14
|
1
|
1
|
1
|
0
|
|
4
|
15
|
1
|
1
|
1
|
1
|
Any of two numbers in these groups which differ from each other by only one variable can be combined and chosen, to get 2-cell combination as shown in table below.
2-Cell combinations
|
Combinations
|
U
|
V
|
W
|
X
|
|
(1,3)
|
0
|
0
|
-
|
1
|
|
(1,9)
|
-
|
0
|
0
|
1
|
|
(2,3)
|
0
|
0
|
1
|
-
|
|
(2,10)
|
-
|
0
|
1
|
0
|
|
(8,9)
|
1
|
0
|
0
|
-
|
|
(8,10)
|
1
|
0
|
-
|
0
|
|
(3,7)
|
0
|
-
|
1
|
1
|
|
(3,11)
|
-
|
0
|
1
|
1
|
|
(9,11)
|
1
|
0
|
-
|
1
|
|
(10,11)
|
1
|
0
|
1
|
-
|
|
(10,14)
|
1
|
-
|
1
|
0
|
|
(7,15)
|
-
|
1
|
1
|
1
|
|
(11,15)
|
1
|
-
|
1
|
1
|
|
(14,15)
|
1
|
1
|
1
|
-
|
From the 2-cell combinations, dash and one variable in the same position can be combined to form 4-cell combinations as shown in figure below.
|
Combinations
|
U
|
V
|
W
|
X
|
|
(1,3,9,11)
|
-
|
0
|
-
|
1
|
|
(2,3,10,11)
|
-
|
0
|
1
|
-
|
|
(8,9,10,11)
|
1
|
0
|
-
|
-
|
|
(3,7,11,15)
|
-
|
-
|
1
|
1
|
|
(10,11,14,15)
|
1
|
-
|
1
|
-
|
The cells (1, 3) and (9, 11) form a same 4-cell combination as the cells (1, 9) and (3, 11). The order in which the cells are placed in the combination doesn't have any effect. Therefore (1, 3, 9, 11) combination could be written as (1, 9, 3, 11).
From above 4-cell combination table and the prime implicants table can be plotted as shown in table below.
The Prime Implication Table
|
Prime Implicants
|
1
|
2
|
3
|
7
|
8
|
9
|
10
|
11
|
14
|
15
|
|
(1,3,9,11)
|
X
|
-
|
X
|
-
|
-
|
X
|
-
|
X
|
-
|
-
|
|
(2,3,10,11)
|
-
|
X
|
X
|
-
|
-
|
-
|
X
|
X
|
-
|
-
|
|
(8,9,10,11)
|
-
|
-
|
-
|
-
|
X
|
X
|
X
|
X
|
-
|
-
|
|
(3,7,11,15)
|
-
|
-
|
-
|
-
|
-
|
-
|
X
|
X
|
X
|
X
|
|
-
|
X
|
X
|
-
|
X
|
X
|
-
|
-
|
-
|
X
|
-
|
The columns contain only one cross mark corresponds to essential prime implicants and a yellow cross is used against every essential prime implicant and the sum of the prime implicants gives the function in its minimal SOP form.
Y = V'X + V'W + UV' + WX + UW