Introduction to Karnaugh Maps - Combinational Logic Circuits, Functions, & Truth Tables

Consider the

truth

table shown on the screen, how can we take the data in its

truth

table and write a function using the variables a, b and c? Enter Carnot

maps

. The Karnaugh map will be very useful for us to write a function that describes this truth table. we have three variables, so we need a three-variable Karnaugh map with eight squares. Now the eight squares will match the eight different input possibilities that we have here, so this is just one of two ways we can draw a three-variable cardinal map. We are going to have two rows and four columns, so at the top I am going to place the inputs a b at the bottom c, so now the inputs a b could be 0 0 0 1 1 1 and 1 0. now the input for c is just 0 or 1. now the values ​​that we are going to put inside the square are the function values ​​that we see here, so for this first square a b is 0 and c is 0, which corresponds to a function value of 0. now for the next one, a b is still zero, which means we are dealing with this column and c is one, so we are dealing with this particular square, the function value is still zero.

Now for the third row we can see that a b is 0. 1 and c is 0 and the value of the function is 1 so let's put a 1 for that square now for the next a b is still 0 1 and c is 1. so this is where a b is 0 1 and c is 1 giving We have this square whose function value is 0. Then a b is 1 0, so we are dealing with the last column and c is zero, so the function value is one. Now for this a b is one zero, still c is one and the value of the function. is one next we have a b is one one then that is the third column c is zero and the function value is one and for the last one the function value is zero where a b and c are one that is how we can take the data in truth table and put it into a Karnaugh map or for short we could say k map now how can we take this data and convert it into a function?

What we have to do is basically surround groups of ones together, we can surround one or we can surround two ones but we cannot surround three once the number of ones that you can surround could be one two four eight and so on it has to be a power of two so you can't surround three ones five ones six ones is not going to work so the The best thing we can do is surround two groups or two pairs of ones. Let me use a different color so you can see it, so let's start with this one.

What kind of information can we derive from that group of ones? Those two highlights do. depend on the input, a notice that the input a varies between 0 and 1, but the output is the same, so the output for those two depends on a notice that it depends on b when b is one, the output is one, then We are looking for the variable that does not change b does not change so we should write b or not b because b is one and the output is one we are going to write b now these two or this pair of ones also corresponds to a value c of zero, Note that c is always zero for that pair of ones, so because z c is zero and the output is one, we should write not c.

Now let's move on to the next pair of ones, so let's put an o symbol represented by plus sign, so for the second pair of ones, which variables do not change, notice that c changes, so for this pair of ones it is independent of c , but notice that a b is the same a is one b is zero, so what is it going to be? not a, it is air b, so since a is one and it matches the output function one, we will leave it as a, but since b is zero, we must put not b because non-zero is one, so this is the function that explain this truth table now we could test it so let's see if a is zero and if b is one and if c is one if we get a function value of zero then b is one c is one a is zero and b is one then if we put yes we write the complement of one which is going to be zero so we have zero times one which is zero and zero times zero is zero so we get an output of zero so it worked, let's try another one, let's try this one, see if the function will give us the output correct so b is zero c is one a is one and b is zero now one's complement is zero and zero's complement is one zero times zero is zero one times one is one zero plus one is one so now we get the output correct, for the sake of practice, let's make sure we have the correct function, let's try the last one, so b is one, c is one, a is one and b is one too, so one's complement is zero. and one times zero is zero zero plus zero is zero and we can see that we have the correct output, so we have the correct function, this is how you could use a Karnaugh map to quickly write a function that corresponds to a truth table .

Now let's take the function we have and convert it into a circuit diagram, so the function we have is b times the complement of c plus a times the complement of b, so we can write it as b c prime plus a b prime, so we need an y gate to connect b and c prime so let's start with that and we need another y gate to connect a and b prime so this will be b and c prime and here we have a and b prime. Now notice that we have one more symbol among these. two terms, so we need to use an o gate, the plus symbol is associated with the o operation, so the output of this y gate will be b c prime and the output of this y gate will be a b prime and the output of o gate will give us the function f which is what we have here, so that is the circuit diagram that corresponds to this function.

Let's try another example. Let's use this truth table to create a k-map and then use it to write a function that Then I'll use it to turn it into a circuit diagram if you want to pause the video and try this problem, feel free now, the type of k-met I'm going to draw will be a little different than before. the last one was a three variable k map drawn in horizontal direction, but I'm going to draw one in vertical orientation, so instead of having two rows, four columns, I'm going to have two columns and four rows, so let's put one variable above the diagonal line two variables below it so that a has two possibilities zero or one bc can be zero zero zero one one or one zero this is how you can draw a map k of three variables with vertical orientation now let's fill in a table, for this first column a is zero, which we can see for the first four entries, so here when b is when b and c is zero, the function will be zero and when bc is 0 1, the function will be 1. when bc is 1 0 the function is 0 and when bc is 1 the function is 1. now for the second column a is always one that will correspond to these four so when bc is zero the function is one and when bc is zero one the function is also one when bc is one zero the function is one and when bc is one one the function is zero this is how we can quickly complete this k-map now how can we use it to write a function for the truth table so let's start with this pair of ones.

Notice that a is always zero, so we need to write the complement of a because the complement of zero will give us an output of one. Now, for those pairs of ones, notice that b changes, so the output. is independent of b, so we're not going to include b, but notice that c is one, so we'll just write c. Now let's draw the next pair of ones, so notice that a is always one for that group and this time c. changes so it's independent of c but b is consistent b is always zero so let's write b prime now there's only one last one we need to consider and that's here so a is one we're just going to write a b is one let's write b and since c is zero we are going to write c prime, so this is the function that corresponds to this truth table.

Now let's test the function to make sure that we do indeed have the correct one, so let's start with what we have here so a is zero c is zero a is still zero b prime b is one and then we have a b c prime so a is zero b is one c is zero zero's complement is one one's complement is zero and zero's complement is one one times zero is zero zero times zero is zero and zero times one is also zero so this adds up to zero, which we can see, that is the case now let's try one more, let's try this one where a b and c are a one so we have the complement of one times one plus one times the complement of one plus one times one times the complement of one the complement of one is zero, so automatically zero times one is zero one times zero is still zero and the last one is going to be zero, so the output will be zero again, okay, let's try one that will give us a value of one, let's try this one, then a is one, c is one, b is zero and a is one, b is zero, c is one, then the complement of one is zero the complement of zero is one and the complement of one is zero zero times one is zero one times one is one one times zero times zero is zero zero plus one plus zero is one so this function works so you already know how to write a function using the k-map, but now let's convert this function into a circuit diagram, let's draw the

logic

circuit that corresponds to this function so let's start with the first term that we have so we need a y gate so it will be a prime c and the output will be a prime c now for the second y gate the input will be a and the second input will be b prime giving us the output a b prime now for the last one I'm going to use a three inputs and gates, so the three inputs will be a b and c prime.

Now we need three inputs or gates, so this will give us the output function f and this is how you can draw the

logic

circuit for this particular function, consider the four variables. k map that we have on the screen, go ahead and write a function for this k-map, feel free to pause the video, so let's first start by analyzing those two pairs of ones, so notice that a and b are always one for that selection, so have a and b and for that selection notice that c is always zero but d changes, so it depends on c but not d, so we have b and since c is zero, we are going to have c prime, now let's select another pair of ones, so Go with that now notice that a is always zero so we will have a prime b changes so it will be independent of b now c is always one and d is always zero so we will write d prime now let's select this pair of ones which we have there, so a is always one and b is always zero, so let's write b prime for that part.

Now notice that c changes with the numbers zero and one, but d stays the same d is always one, so this is going to be a b prime d so this is the function that corresponds to this map k of four particular variables, let's try another example , go ahead and try this so that instead of selecting two, we can select a group of four, for that particular group which variables remains the same, notice that a is always 0 and b is always 0. so we are going to have a prime and b prime, now c can be 0 or 1 so it is independent of c and d can also be zero or one so it is just It will depend on a and b for that first selection.

Now for the next selection, we can basically take a square of ones, so the variables are constants. Note that a is always one, so we will write that b changes between one and zero, so it is independent. of b on this side notice that d is always one, so it will depend on the changes of d c, so it is independent of c, so this particular function is represented by this equation is a prime b plus prime to d, so now you know how to take the information from a four-variable k-map and turn it into a function.

Now let's say we are given a function ac plus a b prime, so how can we take this function and create a map k of three variables and let's create it in the horizontal direction? We'll need two rows and four columns, so we'll put a b above the diagonal line and c below it so that a b can be 0 0 0 1 1 1 or 1 0 and c can be 0 or 1. Now let's focus on ac. term note that we don't have any compliments here, so we're looking for when a is one and when c is one c is one anywhere in this row a is one here, so what we're going to do is go to put a 1 in those boxes now let's focus on the next term a b prime so we just have a we're going to put one we have the complement of b so we're going to write zero so let's identify where a is one and b is zero, so this is when a is one and b is zero, so anywhere in this region we need to fill this row with a one and we have one overlapping there, now every two frames we're going to put a 0 in it.

This is how we can take a function and draw a k-map from it. Now let's try another example. Let's say the function is a b prime plus ac plus a prime bc prime, so let's create another three-variable map k, but in vertical orientation. We're going to have two columns and four rows, so we're going to put the letter a at the top and below the diagonal line so that a can be 0 or 1 and bc can be 0 0 0 1 1 1 or 1 0. Now let's start with this term a b prime so a is going to be 1 b is going to be 0. a is 1 in this column so let me highlight it in red and b is 0 here, that means we're going to put a 1 in those first two boxes at the right now let's move on to the next term ac so that's when a is one and when c is one so we need to put a one here and here now for the next one we have a prime b c prime I forgot put 1 1 for that now for a prime let's write 0 for b we are going to put 1 for c cuz we are going to write 0.so a is 0 in the first column and b is 1 here and c is 0 here, so we want a to be 0, b to be 1 and c to be 0. that just corresponds to this last square, so let's put a 1 in there, like this that every two frames we are going to set to 0 and that is the k-map that corresponds to that function here is another more difficult example, let's say the function is a b prime plus a prime c d plus a b c prime go ahead and draw a k map for that function now what kind of k map do we make?

I need, would you say it's a three-variable k-map or a four-variable k-map? Notice that we have four variables a, b, c and d, so this time we are going to need four columns and four rows. Let's put the letters a.b at the top and c d at the bottom, so a b could be 0 0 0 1 1 1 and 1 0 and the same is true for cd now let's focus on a b prime, so we have a to which we'll put a 1 for that and for the complement of b let's put a zero so that one is one and one is b zero a is one and b is zero anywhere in this column, so we'll put a one everywhere in that column now let's pass to the next term a prime c d so let's put zero for the complement of a and a one for c and d, so notice that c and d are one in this region and a is zero in the first two columns, so we have to put a one in the crossing squares now for the last term a b c prime we are going to put a 1 for a and b and a 0 for the complement of c so a and b are 1 in this region c is 0 in the first two rows, so we are we are going to put a 1 here in all the Elsewhere, we'll fill it in with a zero and now that we've completed the four variable k map, let's work on one more example, so in this one I'm going to color code differently, so let's say the function is c a d prime plus a prime b c prime d plus a b prime c so go ahead and complete the map k of four variables given this function so let's start with lettuce c since we have c and not the complement of c it's just going to be one c is one in this region, so it's anywhere in the last two rows, so we're going to have to put a one in all of those rows, meaning those two rows, so I'm going to color code this group. of eight ones, notice that when we have only one term with one variable, we will get eight ones for a term with two variables, we will get four ones, for a term with three variables, we will get two ones. and four a term with four variables we're only going to get one, so let's move on to the next one, a d prime, so for a I'll put one and for d prime it's zero, so a is one in the last two columns. to the right and d is zero here, so we're going to have a 1 and these too, so now I'm going to surround those with a red color so we can see that for a term with two variables we have a total of four ones highlighted in red now let's move on to the next term which has four variables so we should only get one in map k so for a prime we will write zero for b one c prime 0 d1 so when a is 0 and b is 1 here c is 0 and d is 1 here we're just going to put a 1 in this region and now I'm going to highlight it in green for the last a b prime c so we're going to have a 1 for a 0 for b prime and a 1 for c, so let's first identify where a b is 1 0, so it's going to be in this region and now let's identify where c is one c is one in the second and third row from the top, so we're going to need a one here and the one we already have here, as you can See, for a term with three variables we get a pair of ones or two ones, everything else we put a zero, and now you know. how to convert a function to a k-map so that's all for this video thanks for watching