Home   |  Schematics |  Products |  Tutorials  |  Datasheets  |  Robotics   |   Download    |   Link Exchange


Direct Current
Alternating Current
Digital Electronics
PC Architecture
Electronics Dictionary
Resources

Experiment
Calculator/Converters
Radio
Newsletter
Associations and Societies
Component Manufacturers

Electronics Symentics


 
 
 

Venn Diagram

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.

 




Home  Products  Tutorials   Schematics   Robotics   Resources   Radio Stuff    Career    Download   Link Exchange

HTML Sitemap   XML Sitemap


Terms & Conditions  Privacy Policy and Disclaimer