Tabular Method for Boolean Simplification
The tabular method or the Quine-McCluskey method is a technique for simplifying Boolean algebraic expressions with four or more variables. The method involves the following steps:
List Minterms: Start by listing all the minterms (combinations of variables that produce a '1' in the truth table) of the Boolean function.
Group by Number of 1s: Group the minterms based on the number of '1's in their binary representation.
Compare and Combine: Compare minterms from adjacent groups to find pairs that differ by only one bit. Combine these pairs to form implicants, marking the differing bit with a (X).
Repeat: Continue the process of comparing and combining until no further combinations are possible.
Essential Prime Implicants: Identify the implicants which are necessary to cover all minterms.
Minimal Expression: Construct the minimal Boolean expression using the essential prime implicants.
Example with 4 Variables
Consider the Boolean function F(A, B, C, D) = ∑m(1, 3, 4, 5, 10, 12, 13, 15)
Write binary codes of the minterms. Minterms are those input combinations for which the function output is 1. Take A, B, C and D as input variables.
+--------+---+---------+
| ABCD | X | Minterm |
+--------+---+---------+
| 0000 | 0 | |
| 0001 | 1 | m1 |
| 0010 | 0 | |
| 0011 | 1 | m3 |
| 0100 | 1 | m4 |
| 0101 | 1 | m5 |
| 0110 | 0 | |
| 0111 | 0 | |
| 1000 | 0 | |
| 1001 | 0 | |
| 1010 | 1 | m10 |
| 1011 | 0 | |
| 1100 | 1 | m12 |
| 1101 | 1 | m13 |
| 1110 | 0 | |
| 1111 | 1 | m15 |
+--------+---+---------+
Arrange the minterms into groups according to number of 1s in the binary representation of the minterm. Group 1 is the collection of minterms whose binary representation has a single 1.
+---------+-------+----+
|No. of 1s|Minterm|ABCD|
+---------+-------+----+
| 1 | m1 |0001|
| | m4 |0100|
+---------+-------+----+
| 2 | m3 |0011|
| | m5 |0101|
| | m10 |1010|
| | m12 |1100|
+---------+-------+----+
| 3 | m13 |1101|
+---------+-------+----+
| 4 | m15 |1111|
+---------+-------+----+
Compare adjacent groups for minterms. If two minterms have same binary digits except at one position, a match is noted. A tick is marked in front of the minterms that matchs. The last colum in following table shows the matched pattern.
Comparing group1 and group2: m1 and m4 from group1 are to be compared with each of m3, m5, m10 and m12 from group2. There is a match found between m1 and m3 as 0001 and 0011 match except at 2nd bit from right. The match is written as 00x1, where x indicates the single digit where values are different. All matches are recorded in table below.
+----------+----------+-------+-----------------+
|No. of 1s | Minterm | ABCD | 1st Match |
|in Minterm| | | |
+----------+----------+-------+-----------------+
| 1 | m1 | 0001 ✓| (m1, m3) 00x1 |
| | m4 | 0100 ✓| (m1, m5) 0x01 |
+----------+----------+-------+-----------------+
| 2 | m3 | 0011 ✓| (m4, m5) 010x |
| | m5 | 0101 ✓| (m4, m12) x100 |
| | m10 | 1010 | (m5, m13) x101 |
| | m12 | 1100 ✓| (m12, m13) 110x |
+----------+----------+-------+-----------------+
| 3 | m13 | 1101 ✓| (m13, m15) 11x1 |
+----------+----------+-------+-----------------+
| 4 | m15 | 1111 ✓| |
+----------+----------+-------+-----------------+
Once all groups are matched, second level matches are to be performed. Again compare adjacent groups and not matches. The process is to be repeated till no matches can be found. Here we find two matches:
(m4, m5) in group 1 is matched to (m12, m13) in group2, giving x10x
(m4, m12) in group 1 is matched to (m5, m13) in group2; giving x10x
Infact, both the above matches are same. We can not make any further matches.
+-----------------+---+-------------------------+
| 1st Match | 1s| Second Match |
+-----------------+---+-------------------------+
|(m1, m3) 00x1 | 1 | (m4, m12, m5, m13) x10x |
|(m1, m5) 0x01 | | (m4, m5, m12, m13) x10x |
|(m4, m5) 010x ✓| | |
|(m4, m12) x100 ✓| | |
+-----------------+---+-------------------------+
|(m5, m13) x101 ✓| 2 | |
|(m12, m13) 110x ✓| | |
+-----------------+---+-------------------------+
|(m13, m15) 11x1 | 3 | |
+-----------------+---+-------------------------+
Identify the minterms that did not match, that is they are not ticked marked. Combine all such terms and write the Boolean expression:
F = BC + A BD + A CD + ABD + ABCD
The above expression can be further simplified by selecting only minimum number of terms that cover all the minterms. For that we make an "Essential Prime Implicants" table that ticks the minterms covered by each expression.
+---------------------+---+---+---+---+---+---+---+---+
| Minterms |m1 |m3 |m4 |m5 |m10|m12|m13|m15|
+---------------------+---+---+---+---+---+---+---+---+
|BC'(m4, m5, m12, m13)| | | ✓ | ✓ | | ✓ | ✓ | |
+---------------------+---+---+---+---+---+---+---+---+
|A'B'D(m1, m3) | ✓ | ✓ | | | | | | |
+---------------------+---+---+---+---+---+---+---+---+
|A'C'D(m1, m5) | ✓ | | | ✓ | | | | |
+---------------------+---+---+---+---+---+---+---+---+
|ABD(m13, m15) | | | | | | | ✓ | ✓ |
+---------------------+---+---+---+---+---+---+---+---+
|AB'CD'(m10) | | | | | ✓ | | | |
+---------------------+---+---+---+---+---+---+---+---+
^ ^ ^ ^ ^
| | | | |
Essential Prime Implicants
The minterms that have just one tick in the column are called "Essential Prime Implicants (EPI)" and these cannot be left out. After EPI, select PIs that are necessary. We get the foolowing expression. A'C'D is non-esential prime implicant and can be left out as m1 and m5 are already covered by BC' and A'B'D. Hence the final expression:
X = BC' + A'B'D + ABD + AB'CD'