FAQ - Simplifying Expressions

Q1: How do I place a Boolean expression into a K-Map?

Q2: How do I select a prime implicant?

Q3: How do I extract a Boolean expression from a Karnaugh map?

Q4: How would I place a POS expression into a K-map?

Q5: What do I group in POS K-maps?

Q6: How do I choose a non-essential prime implicant to span the high (or
low) outputs?

Q7: When should I include non-essential prime implicants in a simplified
expression?

Q8: How can I simplify a Boolean expression?

Q9: What's a good review resource for simplification?

Q1:
On the sample tests, there were examples in which you gave an
expression and told us to translate it into a Karnaugh map. The
examples you gave in class seemed quite a bit less complex than the
ones in the tests. The only way I could think of solving these
problems was to just go through every possibility and manually figure
it out. After attempting a couple of these with this method I noticed
it took me well over 10 minutes to just do one and it was very mistake
prone due to careless errors. Is there any way to do it more
efficiently?

When given an expression to be simplified, each term should be
included in the K-map as a grouping. So ~A*B would lead to a grouping
of ones where A is low and B is high. C+~D would be a grouping of
zeros where C is low and D is high. I can't think of an easier way to
create the K-map ones and zeros.

Q2:
I am still unclear on how to derive the prime implicants of
a Karnaugh map when using product of sums. I looked at the practice
tests and problems, and I have just been unable to figure it out. I
understand that you group the zeroes not the ones, but when it comes
to classifying them, I am TOTALLY wrong...If you could explain what I
am doing wrong, that would help me out a lot.

Remember that the POS expression still defines when the output is
high. After grouping zeros, one needs to define when one is not
in that grouping. So a grouping of zeros that might be defined when A
is high and B is low will in fact be described as (~A+B) since this is
when you're not in that grouping of zeros.

Q3:
For Karnaugh maps, how do we get an expression from a map?

A SOP or POS expression can be simplified using a K-map. Once the
behavior (ones and zeros) is included in the map, the simplified
expression can be extracted in SOP form (by grouping one ones) or POS
form (by grouping the zeros).

Q4:
How is the expression (a+b)*(c+d) placed in a K-map?

This four variable map would include a group of zeros when A is low
AND B is low, and another grouping when C is low AND D is low.

Q5:
When finding the Karnaugh map for a given function as a Product of
Sums, what is the best method to find the Karnaugh map? I remember you
covering it in lecture, but I'm having a little trouble applying
it.

For a simplified product of sums expression, one should group prime
implicants of zeros and then write a sum expression for when one is
not in that grouping. By ANDing all these expressions, one
states when the behavior is 1.

Q6:
When writing an expression from Prime Implicants (PIs) gathered
from a Karnaugh Map, if you have two nonessential PIs, and you need to
use either one to cover a 1 in the Karnaugh map, does it matter which
you choose? In this case both PIs are covering the same number of
1's.

If two non-essential PIs cover a needed one, you should use the larger
grouping (simpler term). It is also important to minimize the number
of non-essential PIs used.

Q7:
I was working simplification worksheet 2, problem 1, and I don’t
understand why the answer has AD in the simplified expression. Do we
include everything, including the “nonessential” prime implicants?

%

In K-map simplification, the goal is to minimally span (cover) all
selected values. In the SOP expression, we are covering ones. The
essential PIs cover all but one of the high values. The missed value
is at A -B -C D. To cover this, we must select one of the
non-essential PIs. AD or -CD would accomplish this.

Q8:
In Spring 1999 - Exam 1 - Problem 3, it states that we are supposed to
simplify the SOP using any method we can. The Min term was A'BC' +
ABC' + ABC. I simplified using algebra. I factored the AB in the last
2 expressions to give me A'BC' + AB(C+C'). This simplifies to A'BC' +
AB. Then I factored the B and got B(A + A'C'). I remember that A+A'C'
is an identity equal to A+C' so I plugged that in and got B(A+C')
which the right answer. I was just wondering if we could do this on
tomorrow's test and if would be feasible to do so? (This problem
worked out easily this way). If not, do we use K-maps? Is there any
other way to simplify these problems?

The decision on how to simplify a problem depends on the wording of
problem. If a problem asks to simplify an expression using a Karnaugh
Map, this procedure is being tested and should be demonstrated. If a
problem asks only to provide a simplified expression (and no map is
provided), it is up to you as to how to perform the simplification
(K-map versus algebra). Generally algebraic simplification is more ad
hoc and error prone; so to coin a phrase "when in doubt, map it out".

Q9:
I'm working on the problems on Karnaugh maps and I'm having problems
in identifying the prime implicants and the essentials.Some i get
right and others, it's like I'm missing. Could you give me an outline
of the basic procedures in identifying these prime implicants and the
essentials?

I know this sounds crazy; but any digital design book actually
provides a helpful supplementary explanation for this process. In
order to maintain its perfect "book stinks!" rating, it uses a
different method for labeling the map, plus a totally unnecessary
scheme to represent a truth table as a series of binary numbers.