[Tutorial] Introduction to Boolean Algebra, Part IV

[Acid_Snake]

Karnaugh Maps

karnaugh_map_4variables.png (9.38 KiB) Viewed 958 times

a Karnaugh Map allows us to simplify a function to the max in a very graphical and useful way, without relying on Boolean properties. Although you still need to use properties to make a function look like the standard form, there's no need to actually break your head in simplifying it, and you can never be so sure of its simplification as you can be with Karnaugh maps.


How it works:
The first thing you have to do it obtain the minterms of a function if you don't have them already.
Let's take this function for example: AB'C'D + AC'D' + AB + A'BD + AB'C
after obtaining the minterms we have:
S(5,7,8,9,10,11,12,13,14,15)
What we do is write a 1 on the boxes of the Karnaugh for each of the minterms in their correct place, the result is:

karnaugh_map_example.png (9.98 KiB) Viewed 958 times

Next comes the important part, we have to make groups with those ones in order to do the simplification, these groups must be a power of two, so you can only make groups of 1, 2, 4, 8, 16, etc, you can have groups overlaying each other, it doesn't matter, what matters is that you don't leave any 1 behind. The more ones inside a group, the more simplified it the function will be.
Let's take the two bottom row 1's and make a group like this:

karnaugh_map_example-2.png (11.98 KiB) Viewed 958 times

now we gotta look for the variables that are constant.
First we look at A, it is constant as in the entire circle A is the same value.
B is not constant, as in the upper part of the circle we got B, but in the lower part we got B'
C is not constant either as the right side of the circle has C, but the left side has C'
Same with D, the center has D, but the sides has D'
So this circle gets simplified as: A
now we need to make another circle for the other two 1's. At first we can grab those two 1's by themselves, but that won't simplify the function to the max, for that we also choose the two 1's bellow those ones, even if it overlaps with the other circle:

karnaugh_map_example-3.png (13.17 KiB) Viewed 958 times

As we did before we look at each variable and write down the ones that are constant:
- A is not constant.
- B is constant.
- C is not constant.
- D is constant.
So this circle is simplified to BD, which added to the other circle, the resulting function is: A+BD, which is a smaller than the original function.

Karnaugh Maps using maxterms:
When using maxterms, instead of writing down 1 in the map, you write down 0, and instead of obtaining an expression of the type: AB in a circle, you obtain one of the type (A+B). Let's take this function for example:
(B + E)*(C + D' + E)*(B' + C + D')*(C + E')
We obtain the maxterms:
P(0,1,2,3,4,6,9,10,11)
and we write 0's where needed:

karnaugh_map_maxterms.png (14.81 KiB) Viewed 958 times

And we make groups:

karnaugh_map_maxterms-2.png (18.46 KiB) Viewed 958 times

We study these groups and obtain the function.


Undetermined output
Last but not least, there exists one type of output, other than minterms and maxterms, that can be used to simplify a function, in a Karnaugh map these are shown as X's, and can be use to help make bigger groups for more simplification.
Taking this function into consideration:
S(5,7,8,9,10,11,12,13,14,15)+d(4,6)
This is what it looks like in a K-map:

karnaugh_map_example-4.png (11.44 KiB) Viewed 958 times

We can now make bigger groups using those X's, but there are two things you have to take into consideration:
- NEVER make a group that only has X's, this is not correct.
- You don't have to take all the X's, you do have to make groups with all the 1's and 0's, but not with the X's, use the X's only when strictly needed for simplification.


So far so good, the best way to learn this is practicing on paper, use the following functions to practice:

Code: Select all

F(A,B,C,D) = S(3,5,6,7,8,10,12,13,14)

Code: Select all

F(A,B,C,D) = P(0,1,2,4,9,11,15)

Code: Select all

F(A,B,C,D) = S(0,4,5,8,10,15) + d(2,7,9,13)

Previous: viewtopic.php?f=37&t=33566
Next: viewtopic.php?f=37&t=33736

Advertising

[Xian Nox]

What I understood from your description is that you need to find the minterms or maxterms to make a Veitch diagram. No, you do not.

Code: Select all

f = ab'c'd + ac'd' + ab + a'bd + ab'c

ab'c'd: a is true for the last two rows, b is not true for the last row, c is not true for the first two cells, d is true for the second cell
      c c
.+-+-+-+-+
.| | | | |
.+-+-+-+-+
b| | | | |
.+-+-+-+-+
b| | | | |a
.+-+-+-+-+
.| |1| | |a
.+-+-+-+-+
    d d
ac'd'
      c c
.+-+-+-+-+
.| | | | |
.+-+-+-+-+
b| | | | |
.+-+-+-+-+
b|1| | | |a
.+-+-+-+-+
.|1| | | |a
.+-+-+-+-+
    d d
ab
      c c
.+-+-+-+-+
.| | | | |
.+-+-+-+-+
b| | | | |
.+-+-+-+-+
b|1|1|1|1|a
.+-+-+-+-+
.| | | | |a
.+-+-+-+-+
    d d
a'bd
      c c
.+-+-+-+-+
.| | | | |
.+-+-+-+-+
b| |1|1| |
.+-+-+-+-+
b| | | | |a
.+-+-+-+-+
.| | | | |a
.+-+-+-+-+
    d d
ab'c
      c c
.+-+-+-+-+
.| | | | |
.+-+-+-+-+
b| | | | |
.+-+-+-+-+
b| | | | |a
.+-+-+-+-+
.| | |1|1|a
.+-+-+-+-+
    d d
f
      c c
.+-+-+-+-+
.| | | | |
.+-+-+-+-+
b| |1|1| |
.+-+-+-+-+
b|1|1|1|1|a
.+-+-+-+-+
.|1|1|1|1|a
.+-+-+-+-+
    d d

Advertising