204
Digital Electronics
AB+AB
–
–
A . AB
–—
——–
A
B
AB
––
B . AB
–—
——–
Figure 6.5 Example 6.7.
6.4 Simplification Techniques
In this section, we will discuss techniques other than the application of laws and theorems of Boolean
algebra discussed in the preceding paragraphs of this chapter for simplifying or more precisely
minimizing a given complex Boolean expression. The primary objective of all simplification procedures
is to obtain an expression that has the minimum number of terms. Obtaining an expression with the
minimum number of literals is usually the secondary objective. If there is more than one possible
solution with the same number of terms, the one having the minimum number of literals is the choice.
The techniques to be discussed include:
(a) the Quine–McCluskey tabular method;
(b) the Karnaugh map method.
Before we move on to discuss these techniques in detail, it would be relevant briefly to describe
sum-of-products and product-of-sums Boolean expressions. The given Boolean expression will be in
either of the two forms, and the objective will be to find a minimized expression in the same or the
other form.
6.4.1 Sum-of-Products Boolean Expressions
A sum-of-products expression contains the sum of different terms, with each term being either a
single literal or a product of more than one literal. It can be obtained from the truth table directly
by considering those input combinations that produce a logic ‘1’ at the output. Each such input
combination produces a term. Different terms are given by the product of the corresponding literals.
The sum of all terms gives the expression. For example, the truth table in Table 6.5 can be represented
by the Boolean expression
Y = A + AABBC + AABBC + AABBC
(6.33)
Considering the first term, the output is ‘1’ when A = 0 B = 0 and C = 0. This is possible only when
A, B and C are ANDed. Also, for the second term, the output is ‘1’ only when B, C and A are ANDed.
Other terms can be explained similarly. A sum-of-products expression is also known as a minterm
expression.
Digital Electronics
AB+AB
–
–
A . AB
–—
——–
A
B
AB
––
B . AB
–—
——–
Figure 6.5 Example 6.7.
6.4 Simplification Techniques
In this section, we will discuss techniques other than the application of laws and theorems of Boolean
algebra discussed in the preceding paragraphs of this chapter for simplifying or more precisely
minimizing a given complex Boolean expression. The primary objective of all simplification procedures
is to obtain an expression that has the minimum number of terms. Obtaining an expression with the
minimum number of literals is usually the secondary objective. If there is more than one possible
solution with the same number of terms, the one having the minimum number of literals is the choice.
The techniques to be discussed include:
(a) the Quine–McCluskey tabular method;
(b) the Karnaugh map method.
Before we move on to discuss these techniques in detail, it would be relevant briefly to describe
sum-of-products and product-of-sums Boolean expressions. The given Boolean expression will be in
either of the two forms, and the objective will be to find a minimized expression in the same or the
other form.
6.4.1 Sum-of-Products Boolean Expressions
A sum-of-products expression contains the sum of different terms, with each term being either a
single literal or a product of more than one literal. It can be obtained from the truth table directly
by considering those input combinations that produce a logic ‘1’ at the output. Each such input
combination produces a term. Different terms are given by the product of the corresponding literals.
The sum of all terms gives the expression. For example, the truth table in Table 6.5 can be represented
by the Boolean expression
Y = A + AABBC + AABBC + AABBC
(6.33)
Considering the first term, the output is ‘1’ when A = 0 B = 0 and C = 0. This is possible only when
A, B and C are ANDed. Also, for the second term, the output is ‘1’ only when B, C and A are ANDed.
Other terms can be explained similarly. A sum-of-products expression is also known as a minterm
expression.