Boolean Algebra and Simplification Techniques
211
The second round of matching begins with the table shown on the previous page. Each term in the first
group is compared with every term in the second group. For instance, the first term in the first group
00−1 matches with the second term in the second group 01−1 to yield 0−−1, which is recorded in
the table shown below. The process continues until all terms have been compared for a possible match.
Since this new table has only one group, the terms contained therein are all prime implicants. In the
present example, the terms in the first and second tables have all found a match. But that is not always
the case.
A
B
C
D
0
−
−
1
*
−
−
0
1
*
0
1
−
−
*
−
1
0
−
*
The next table is what is known as the prime implicant table. The prime implicant table contains all the
original terms in different columns and all the prime implicants recorded in different rows as shown
below:
0001
0011
0100
0101
0110
0111
1001
1100
1101
0− −1
P → AAD
− −01
Q → CCD
01− −
R → AAB
–10−
S → BBC
Each prime implicant is identified by a letter. Each prime implicant is then examined one by one and
the terms it can account for are ticked as shown. The next step is to write a product-of-sums expression
using the prime implicants to account for all the terms. In the present illustration, it is given as follows.
P + QQQQPPPPR + SSSSP + Q + R + SSSSRRRRP + RRRRQQQQSSSSQ + SS
Obvious simplification reduces this expression to PQRS which can be interpreted to mean that all
prime implicants, that is, P, Q, R and S, are needed to account for all the original terms.
Therefore, the minimized expression = AAD + CCD + AAB + BBC.
What has been described above is the formal method of determining the optimum set of prime
implicants. In most of the cases where the prime implicant table is not too complex, the exercise can
be done even intuitively. The exercise begins with identification of those terms that can be accounted
for by only a single prime implicant. In the present example, 0011, 0110, 1001 and 1100 are such
terms. As a result, P, Q, R and S become the essential prime implicants. The next step is to find out if
any terms have not been covered by the essential prime implicants. In the present case, all terms have
been covered by essential prime implicants. In fact, all prime implicants are essential prime implicants
in the present example.
As another illustration, let us consider a product-of-sums expression given by
A + B + C + DDDDA + B + C + DDDDA + B + C + DDDDA + B + C + DDDDA + B + C + DD
The procedure is similar to that described for the case of simplification of sum-of-products expressions.
The resulting tables leading to identification of prime implicants are as follows:
211
The second round of matching begins with the table shown on the previous page. Each term in the first
group is compared with every term in the second group. For instance, the first term in the first group
00−1 matches with the second term in the second group 01−1 to yield 0−−1, which is recorded in
the table shown below. The process continues until all terms have been compared for a possible match.
Since this new table has only one group, the terms contained therein are all prime implicants. In the
present example, the terms in the first and second tables have all found a match. But that is not always
the case.
A
B
C
D
0
−
−
1
*
−
−
0
1
*
0
1
−
−
*
−
1
0
−
*
The next table is what is known as the prime implicant table. The prime implicant table contains all the
original terms in different columns and all the prime implicants recorded in different rows as shown
below:
0001
0011
0100
0101
0110
0111
1001
1100
1101
0− −1
P → AAD
− −01
Q → CCD
01− −
R → AAB
–10−
S → BBC
Each prime implicant is identified by a letter. Each prime implicant is then examined one by one and
the terms it can account for are ticked as shown. The next step is to write a product-of-sums expression
using the prime implicants to account for all the terms. In the present illustration, it is given as follows.
P + QQQQPPPPR + SSSSP + Q + R + SSSSRRRRP + RRRRQQQQSSSSQ + SS
Obvious simplification reduces this expression to PQRS which can be interpreted to mean that all
prime implicants, that is, P, Q, R and S, are needed to account for all the original terms.
Therefore, the minimized expression = AAD + CCD + AAB + BBC.
What has been described above is the formal method of determining the optimum set of prime
implicants. In most of the cases where the prime implicant table is not too complex, the exercise can
be done even intuitively. The exercise begins with identification of those terms that can be accounted
for by only a single prime implicant. In the present example, 0011, 0110, 1001 and 1100 are such
terms. As a result, P, Q, R and S become the essential prime implicants. The next step is to find out if
any terms have not been covered by the essential prime implicants. In the present case, all terms have
been covered by essential prime implicants. In fact, all prime implicants are essential prime implicants
in the present example.
As another illustration, let us consider a product-of-sums expression given by
A + B + C + DDDDA + B + C + DDDDA + B + C + DDDDA + B + C + DDDDA + B + C + DD
The procedure is similar to that described for the case of simplification of sum-of-products expressions.
The resulting tables leading to identification of prime implicants are as follows: