Digital Electronics: CT 304N

Unit–2(Part-3)
Binary Logic and Boolean
Algebra
Dr. Anand J. Patel
Quine-McCluskey Tabulation Method
• Follow these steps for simplifying Boolean functions using Quine-
McClukey tabular method.
• Step 1 − Arrange the given min terms in an ascending order and make
the groups based on the number of ones present in their binary
representations. So, there will be at most ‘n+1’ groups if there are ‘n’
Boolean variables in a Boolean function or ‘n’ bits in the binary
equivalent of min terms.
• Step 2 − Compare the min terms present in successive groups. If
there is a change in only one-bit position, then take the pair of those
two min terms. Place this symbol ‘_’ in the differed bit position and
keep the remaining bits as it is.
Quine-McCluskey Tabulation Method(1)
• Step 3 − Repeat step2 with newly formed terms till we get all prime
implicants.
• Step 4 − Formulate the prime implicant table. It consists of set of
rows and columns. Prime implicants can be placed in row wise and
min terms can be placed in column wise. Place ‘1’ in the cells
corresponding to the min terms that are covered in each prime
implicant.
Quine-McCluskey Tabulation Method(2)
• Step 5 − Find the essential prime implicants by observing each
column. If the minterm is covered only by one prime implicant, then it
is essential prime implicant. Those essential prime implicants will be
part of the simplified Boolean function.
• Step 6 − Reduce the prime implicant table by removing the row of
each essential prime implicant and the columns corresponding to the
min terms that are covered in that essential prime implicant. Repeat
step 5 for Reduced prime implicant table. Stop this process when all
minterms of given Boolean function are over.
Example
• Simplify the following Boolean function:
• F(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15) using Quine-McClukey tabulation
method.
• Step 1 − The given Boolean function is in sum of min terms form. It is
having 4 variables W, X, Y & Z. The given min terms are 2, 6, 8, 9, 10,
11, 14 and 15. The ascending order of these min terms based on the
number of ones present in their binary equivalent is 2, 8, 6, 9, 10, 11,
14 and 15. The following table shows these minterms and their
equivalent binary representations.
Step 1
• The given min terms are arranged into 4 groups based on the number
of ones present in their binary equivalents. The following table shows
the possible merging of min terms from adjacent groups.

Group Min terms W X Y Z

6 0 1 1 0

GA2 9 1 0 0 1

10 1 0 1 0

11 1 0 1 1
GA3
14 1 1 1 0

GA4 15 1 1 1 1
 Step 2
The min terms, which are differed in only one-bit position from adjacent groups are merged. That differed
bit is represented with this symbol, ‘-‘. In this case, there are three groups and each group contains
combinations of two min terms. The following table shows the possible merging of minterm pairs from
adjacent groups.

Group Minterms W X Y Z
Name
2,6 0 - 1 0

2,10 - 0 1 0
GB1
8,9 1 0 0 -

8,10 1 0 - 0

6,14 - 1 1 0

9,11 1 0 - 1
GB2
10,11 1 0 1 -

10,14 1 - 1 0

11,15 1 - 1 1
GB3
14,15 1 1 1 -
 Step 3
The successive groups of min term pairs, which are differed in only one-bit position are merged. That differed
bit is represented with this symbol, ‘-‘. In this case, there are two groups and each group contains
combinations of four min terms. Here, these combinations of 4 min terms are available in two rows. So, we
can remove the repeated rows. The reduced table after removing the redundant rows is shown below.

Group Minterms W X Y Z
Name
2,6,10,14 - - 1 0

2,10,6,14 - - 1 0
GB1
8,9,10,11 1 0 - -

8,10,9,11 1 0 - -

10,11,14,15 1 - 1 -
GB2
10,14,11,15 1 - 1 -
Step 3
Further merging of the combinations of min terms from adjacent groups is not possible, since they are
differed in more than one-bit position. There are three rows in the above table. So, each row will give one
prime implicant. Therefore, the prime implicants are YZ’, WX’ & WY.

Group Minterms W X Y Z
Name
GC1 2,6,10,14 - - 1 0

8,9,10,11 1 0 - -

GC2 10,11,14,15 1 - 1 -
Step 4
The prime implicants are placed in row wise and min terms are placed in column wise. 1s are placed
in the common cells of prime implicant rows and the corresponding min term columns.

The min terms 2 and 6 are covered only by one prime implicant YZ’. So, it is an essential prime
implicant. This will be part of simplified Boolean function. Now, remove this prime implicant row and
the corresponding min term columns. The reduced prime implicant table is shown below.

Min terms / Prime 2 6 8 9 10 11 14 15

YZ’ 1 1 1 1

WX’ 1 1 1 1

WY 1 1 1 1
Step 5-6
• Now, remove this prime implicant YZ’ row and the corresponding min term
columns. The reduced prime implicant table is shown below.
• The min terms 8 and 9 are covered only by one prime implicant WX’. So, it is
an essential prime implicant. This will be part of simplified Boolean function.
Now, remove this prime implicant row and the corresponding min term
columns. The reduced prime implicant table is shown below.

Min terms / Prime 8 9 11 15

WX’ 1 1 1

WY 1 1
 Step 5-6
• Now, remove this prime implicant WX’ row and the corresponding minterm
columns. The reduced prime implicant table is shown below.
• The minterm 15 is covered only by one prime implicant WY. So, it is an essential
prime implicant. This will be part of simplified Boolean function.

Min terms / Prime 15

WY 1
Answer
• Therefore, the simplified Boolean function is
F(W,X,Y,Z) = YZ’ + WX’ + WY.
Exercise Example 1
• Simplify the following expression to sum of product (SOP) using
Tabulation Method
• F(a,b,c,d)= ∑(0,1,2,3,4,6,7,11,12,15)
Exercise Example 2
• Simplify the following expression to sum of product (SOP) using
Tabulation Method
• F(a,b,c,d)= ∑(0,4,8,10,12,13,15) + d(1,2 )
Exercise Example 3
• Simplify the following expression to product of sum (POS) using
Tabulation Method
• F(a,b,c,d)= ∏(1,3,5,7,13,15)
Exercise Example 4
• Simplify the following expression to product of sum (POS) using
Tabulation Method
• F(a,b,c,d)= ∏(0,8,10,12,13,15).d(1,2,3)
The End