Mathematicians use Venn diagrams to show
the logical relationships of sets (collections of objects) to one
another. Perhaps you have already seen Venn diagrams in your algebra or
other mathematics studies. If you have, you may remember overlapping circles
and the union and intersection of sets. We will review the
overlapping circles of the Venn diagram. We will adopt the terms OR and AND
instead of union and intersection since that is the terminology used in
digital electronics.
The Venn diagram bridges the Boolean algebra from a previous chapter to
the Karnaugh Map. We will relate what you already know about Boolean algebra
to Venn diagrams, then transition to Karnaugh maps.
Venn Diagrams and Sets
A set is a collection of objects out of a universe as shown below.
The members of the set are the objects contained within the set. The
members of the set usually have something in common; though, this is not a
requirement. Out of the universe of real numbers, for example, the set of
all positive integers {1,2,3...} is a set. The set {3,4,5} is an example of
a smaller set, or subset of the set of all positive integers. Another
example is the set of all males out of the universe of college students. Can
you think of some more examples of sets?
Above left, we have a Venn diagram showing the set A in the circle within
the universe U, the rectangular area. If everything inside the circle is A,
then anything outside of the circle is not A. Thus, above center, we label
the rectangular area outside of the circle A as A-not instead of U. We show
B and B-not in a similar manner.
What happens if both A and B are contained within the same universe? We
show four possibilities.
Let's take a closer look at each of the the four possibilities as shown
above.
The first example shows that set A and set B have nothing in common
according to the Venn diagram. There is no overlap between the A and B
circular hatched regions. For example, suppose that sets A and B contain the
following members:
set A = {1,2,3,4}
set B = {5,6,7,8}
None of the members of set A are contained within set B, nor are any of
the members of B contained within A. Thus, there is no overlap of the
circles.
In the second example in the above Venn diagram, Set A is totally
contained within set B How can we explain this situation? Suppose that sets
A and B contain the following members:
set A = {1,2}
set B = {1,2,3,4,5,6,7,8}
All members of set A are also members of set B. Therefore, set A is a
subset of Set B. Since all members of set A are members of set B, set A is
drawn fully within the boundary of set B.
There is a fifth case, not shown, with the four examples. Hint: it is
similar to the last (fourth) example. Draw a Venn diagram for this fifth
case.
The third example above shows perfect overlap between set A and set B. It
looks like both sets contain the same identical members. Suppose that sets A
and B contain the following:
set A = {1,2,3,4} set B = {1,2,3,4}
Therefore,
Set A = Set B
Sets And B are identically equal because they both have the same
identical members. The A and B regions within the corresponding Venn diagram
above overlap completely. If there is any doubt about what the above
patterns represent, refer to any figure above or below to be sure of what
the circular regions looked like before they were overlapped.
The fourth example above shows that there is something in common between
set A and set B in the overlapping region. For example, we arbitrarily
select the following sets to illustrate our point:
set A = {1,2,3,4}
set B = {3,4,5,6}
Set A and Set B both have the elements 3 and 4 in common These elements
are the reason for the overlap in the center common to A and B. We need to
take a closer look at this situation
Boolean Relationships on Venn Diagrams
The fourth example has A partially overlapping B. Though,
we will first look at the whole of all hatched area below, then later only
the overlapping region. Let's assign some Boolean expressions to the regions
above as shown below. Below left there is a red horizontal hatched area for
A. There is a blue vertical hatched area for B.
If we look at the whole area of both, regardless of the hatch style, the
sum total of all hatched areas, we get the illustration above right which
corresponds to the inclusive OR function of A, B. The Boolean
expression is A+B. This is shown by the 45o hatched area.
Anything outside of the hatched area corresponds to (A+B)-not as
shown above. Let's move on to next part of the fourth example
The other way of looking at a Venn diagram with overlapping circles is to
look at just the part common to both A and B, the double
hatched area below left. The Boolean expression for this common area
corresponding to the AND function is AB as shown below right.
Note that everything outside of double hatched AB is AB-not.
Note that some of the members of A, above, are members of (AB)'.
Some of the members of B are members of (AB)'. But, none of
the members of (AB)' are within the doubly hatched area AB.
We have repeated the second example above left. Your fifth example, which
you previously sketched, is provided above right for comparison. Later we
will find the occasional element, or group of elements, totally contained
within another group in a Karnaugh map.
Next, we show the development of a Boolean expression involving a
complemented variable below.
Example: (above)
Show a Venn diagram for A'B (A-not AND B).
Solution:
Starting above top left we have red horizontal shaded A' (A-not),
then, top right, B. Next, lower left, we form the AND function A'B
by overlapping the two previous regions. Most people would use this as the
answer to the example posed. However, only the double hatched A'B is
shown far right for clarity. The expression A'B is the region where
both A' and B overlap. The clear region outside of A'B
is (A'B)', which was not part of the posed example.
Let's try something similar with the Boolean OR function.
Example:
Find B'+A
Solution:
Above right we start out with B which is complemented to B'.
Finally we overlay A on top of B'. Since we are interested in
forming the OR function, we will be looking for all hatched area
regardless of hatch style. Thus, A+B' is all hatched area above
right. It is shown as a single hatch region below left for clarity.
Example:
Find(A+B')'
Solution:
The green 45o A+B' hatched area was the result of the
previous example. Moving on to a to,(A+B')' ,the present example,
above left, let us find the complement of A+B', which is the white
clear area above left corresponding to (A+B')'. Note that we have
repeated, at right, the AB' double hatched result from a previous
example for comparison to our result. The regions corresponding to (A+B')'
and AB' above left and right respectively are identical. This can be
proven with DeMorgan's theorem and double negation.
This brings up a point. Venn diagrams don't actually prove anything.
Boolean algebra is needed for formal proofs. However, Venn diagrams can be
used for verification and visualization. We have verified and visualized
DeMorgan's theorem with a Venn diagram.
Example:
What does the Boolean expression A'+B' look like on a Venn
Diagram?
Solution: above figure
Start out with red horizontal hatched A' and blue vertical hatched
B' above. Superimpose the diagrams as shown. We can still see the
A' red horizontal hatch superimposed on the other hatch. It also fills
in what used to be part of the B (B-true) circle, but only that part
of the B open circle not common to the A open circle. If we
only look at the B' blue vertical hatch, it fills that part of the
open A circle not common to B. Any region with any hatch at
all, regardless of type, corresponds to A'+B'. That is, everything
but the open white space in the center.
Example:
What does the Boolean expression (A'+B')' look like on a Venn
Diagram?
Solution: above figure, lower left
Looking at the white open space in the center, it is everything NOT
in the previous solution of A'+B', which is (A'+B')'.
Example:
Show that (A'+B') = AB
Solution: below figure, lower left
We previously showed on the above right diagram that the white open
region is (A'+B')'. On an earlier example we showed a doubly hatched
region at the intersection (overlay) of AB. This is the left and
middle figures repeated here. Comparing the two Venn diagrams, we see that
this open region , (A'+B')', is the same as the doubly hatched region
AB (A AND B). We can also prove that (A'+B')'=AB by DeMorgan's
theorem and double negation as shown above.
We show a three variable Venn diagram above with regions A (red
horizontal), B (blue vertical), and, C (green 45o).
In the very center note that all three regions overlap representing Boolean
expression ABC. There is also a larger petal shaped region where A
and B overlap corresponding to Boolean expression AB. In a
similar manner A and C overlap producing Boolean expression
AC. And B and C overlap producing Boolean expression BC.
Looking at the size of regions described by AND expressions above, we see
that region size varies with the number of variables in the associated AND
expression.
A, 1-variable is a large circular region.
AB, 2-variable is a smaller petal shaped region.
ABC, 3-variable is the smallest region.
The more variables in the AND term, the smaller the region.
Making a Venn diagram look like a Karnaugh map
Starting with circle A in a rectangular A' universe in
figure (a) below, we morph a Venn diagram into almost a Karnaugh map.
We expand circle A at (b) and (c), conform to the rectangular
A' universe at (d), and change A to a rectangle at (e). Anything
left outside of A is A' . We assign a rectangle to A'
at (f). Also, we do not use shading in Karnaugh maps. What we have so far
resembles a 1-variable Karnaugh map, but is of little utility. We need
multiple variables.
Figure (a) above is the same as the previous Venn diagram showing A
and A' above except that the labels A and A' are above
the diagram instead of inside the respective regions. Imagine that we have
go through a process similar to figures (a-f) to get a "square Venn diagram"
for B and B' as we show in middle figure (b). We will now
superimpose the diagrams in Figures (a) and (b) to get the result at (c),
just like we have been doing for Venn diagrams. The reason we do this is so
that we may observe that which may be common to two overlapping regions--
say where A overlaps B. The lower right cell in figure (c)
corresponds to AB where A overlaps B.
We don't waste time drawing a Karnaugh map like (c) above, sketching a
simplified version as above left instead. The column of two cells under
A' is understood to be associated with A', and the heading A
is associated with the column of cells under it. The row headed by B'
is associated with the cells to the right of it. In a similar manner B
is associated with the cells to the right of it. For the sake of simplicity,
we do not delineate the various regions as clearly as with Venn diagrams.
The Karnaugh map above right is an alternate form used in most texts. The
names of the variables are listed next to the diagonal line. The A
above the diagonal indicates that the variable A (and A') is
assigned to the columns. The 0 is a substitute for A', and the
1 substitutes for A. The B below the diagonal is
associated with the rows: 0 for B', and 1 for B
Example:
Mark the cell corresponding to the Boolean expression AB in the
Karnaugh map above with a 1
Solution:
Shade or circle the region corresponding to A. Then, shade or
enclose the region corresponding to B. The overlap of the two regions
is AB. Place a 1 in this cell. We do not necessarily enclose
the A and B regions as at above left.
We develop a 3-variable Karnaugh map above, starting with Venn diagram
like regions. The universe (inside the black rectangle) is split into two
narrow narrow rectangular regions for A' and A. The variables
B' and B divide the universe into two square regions. C
occupies a square region in the middle of the rectangle, with C'
split into two vertical rectangles on each side of the C square.
In the final figure, we superimpose all three variables, attempting to
clearly label the various regions. The regions are less obvious without
color printing, more obvious when compared to the other three figures. This
3-variable K-Map (Karnaugh map) has 23 = 8 cells,
the small squares within the map. Each individual cell is uniquely
identified by the three Boolean Variables (A, B, C). For example,
ABC' uniquely selects the lower right most cell(*), A'B'C'
selects the upper left most cell (x).
We don't normally label the Karnaugh map as shown above left. Though this
figure clearly shows map coverage by single boolean variables of a 4-cell
region. Karnaugh maps are labeled like the illustration at right. Each cell
is still uniquely identified by a 3-variable product term, a Boolean
AND expression. Take, for example, ABC' following the A
row across to the right and the BC' column down, both intersecting at
the lower right cell ABC'. See (*) above figure.
The above two different forms of a 3-variable Karnaugh map are
equivalent, and is the final form that it takes. The version at right is a
bit easier to use, since we do not have to write down so many boolean
alphabetic headers and complement bars, just 1s and 0s Use the
form of map on the right and look for the the one at left in some texts. The
column headers on the left B'C', B'C, BC, BC' are equivalent to
00, 01, 11, 10 on the right. The row headers A, A' are equivalent
to 0, 1 on the right map. |