208
Digital Electronics
Optional combinations can also be incorporated into and nomenclature using suitable identifiers;
or d are used as identifiers. For example, if ffAA BB CC = AABBC + AABBC + AABBC and AABBCC AABBC
are optional combinations, then
ffAA BB CC =
0 4 5 +
3 7 =
0 4 5 +
d
3 7
ffAA BB CC =
1 2 6 +
3 7 =
1 2 6 +
d
3 7
Example 6.8
For a Boolean function ffAA BB =
0 2 prove that ffAA BB =
1 3 and f
AA BB =
1 3 =
0 2.
Solution
• ffAA BB =
0 2 = AAB + AAB = BBBA + AA = B.
• Now,
1 3 = A + BBBBA + BB = AAA + AAB + BBA + BBB = AAB + AAB + B = B.
• Now,
1 3 = AAB + AAB = BBBA + AA = BB
and
0 2 =A + BBBBA + BB = AAA + AAB + BBA + BBB = AAB + AAB + B = B.
• Therefore,
1 3 =
0 2.
• Also, ffAA BB = B.
• Therefore, f
AA BB = B or f
AA BB =
1 3 =
0 2.
6.5 Quine–McCluskey Tabular Method
The Quine–McCluskey tabular method of simplification is based on the complementation theorem,
which says that
XXY + XXY = X
(6.34)
where X represents either a variable or a term or an expression and Y is a variable. This theorem
implies that, if a Boolean expression contains two terms that differ only in one variable, then they can
be combined together and replaced with a term that is smaller by one literal. The same procedure is
applied for the other pairs of terms wherever such a reduction is possible. All these terms reduced
by one literal are further examined to see if they can be reduced further. The process continues
until the terms become irreducible. The irreducible terms are called prime implicants. An optimum
set of prime implicants that can account for all the original terms then constitutes the minimized
expression. The technique can be applied equally well for minimizing sum-of-products and productof-sums expressions and is particularly useful for Boolean functions having more than six variables as
it can be mechanized and run on a computer. On the other hand, the Karnaugh mapping method, to be
discussed later, is a graphical method and becomes very cumbersome when the number of variables
exceeds six.
The step-by-step procedure for application of the tabular method for minimizing Boolean expressions,
both sum-of-products and product-of-sums, is outlined as follows:
1. The Boolean expression to be simplified is expanded if it is not in expanded form.
2. Different terms in the expression are divided into groups depending upon the number of 1s they have.
True and complemented variables in a sum-of-products expression mean ‘1’ and ‘0’ respectively.
Digital Electronics
Optional combinations can also be incorporated into and nomenclature using suitable identifiers;
or d are used as identifiers. For example, if ffAA BB CC = AABBC + AABBC + AABBC and AABBCC AABBC
are optional combinations, then
ffAA BB CC =
0 4 5 +
3 7 =
0 4 5 +
d
3 7
ffAA BB CC =
1 2 6 +
3 7 =
1 2 6 +
d
3 7
Example 6.8
For a Boolean function ffAA BB =
0 2 prove that ffAA BB =
1 3 and f
AA BB =
1 3 =
0 2.
Solution
• ffAA BB =
0 2 = AAB + AAB = BBBA + AA = B.
• Now,
1 3 = A + BBBBA + BB = AAA + AAB + BBA + BBB = AAB + AAB + B = B.
• Now,
1 3 = AAB + AAB = BBBA + AA = BB
and
0 2 =A + BBBBA + BB = AAA + AAB + BBA + BBB = AAB + AAB + B = B.
• Therefore,
1 3 =
0 2.
• Also, ffAA BB = B.
• Therefore, f
AA BB = B or f
AA BB =
1 3 =
0 2.
6.5 Quine–McCluskey Tabular Method
The Quine–McCluskey tabular method of simplification is based on the complementation theorem,
which says that
XXY + XXY = X
(6.34)
where X represents either a variable or a term or an expression and Y is a variable. This theorem
implies that, if a Boolean expression contains two terms that differ only in one variable, then they can
be combined together and replaced with a term that is smaller by one literal. The same procedure is
applied for the other pairs of terms wherever such a reduction is possible. All these terms reduced
by one literal are further examined to see if they can be reduced further. The process continues
until the terms become irreducible. The irreducible terms are called prime implicants. An optimum
set of prime implicants that can account for all the original terms then constitutes the minimized
expression. The technique can be applied equally well for minimizing sum-of-products and productof-sums expressions and is particularly useful for Boolean functions having more than six variables as
it can be mechanized and run on a computer. On the other hand, the Karnaugh mapping method, to be
discussed later, is a graphical method and becomes very cumbersome when the number of variables
exceeds six.
The step-by-step procedure for application of the tabular method for minimizing Boolean expressions,
both sum-of-products and product-of-sums, is outlined as follows:
1. The Boolean expression to be simplified is expanded if it is not in expanded form.
2. Different terms in the expression are divided into groups depending upon the number of 1s they have.
True and complemented variables in a sum-of-products expression mean ‘1’ and ‘0’ respectively.