1 We have discued how to simplify a logic function using logic algebra.This method relies on the skill of the individual in applying the appropriate rules.Sometimes it is hard to be sure whether the logical function is already simplest form or not.Now we will introduce a new method, which is graphical, known as the Karnaugh map.It’s a tool for performing the simplification of logic function.2 first, we must know what is the K-map, and how to design it! Usually, the K-map is made up of 3 parts, and the 3 parts are variables, cells and binary numbers.Ok, we can get 2 k-maps, you should note each map includes 3 parts.Please remember the 3 parts, when you design k-maps, each of the parts is eential.
3 we note the first map has 2 variables, it has 4cells, and the second map has 3 variables, it has 8 cells.So in an n-variable k-map, there are 2 to power n cells.4 then please observe the binary numbers on the upper and left side of the k-map.What do you discover from the changed values? Take the numbers on the upper side as example, look at the first map, the numbers is changed from 0 to 1 between adjacent cells, only one-bit is changed, of course, the number just has one-bit.On the second map, each number has 2 bits, the number is changed from 00 to 01, from 01 to 11, from 11 to 10, between the adjacent cells, there is only one-bit in the number changed.If we change the position of the 2 binary numbers, do you think this sequence is right? No! It’s not right, because the number is changed from 01 to 10, two bits are changed.So you should know there is only a single-variable value changed between adjacent cells.This is one of the K-map’s features.5 we look at other features.On the fist map, Cell 1’s adjacent cells are cell 2 and 3, it’s easy to understand.What are the cell 4’s adjacent cells? They are also cell 2 and 3.But on the second map, cell 3’s adjacent cells are cell 1, 4 and 7.This is easy to understand.Now please give the cell 1’s adjacent cells! You may list cell 2 and 3, it’s right, but it’s not all right, because you ignore the cell 5.Do you know what that is on the left side of cell 1? In fact, cell 5 is on the left side of cell 1, of course, cell 6 is on the left side of cell 2.In this case, adjacent cell include the cells located in the symmetric place.I hope everyone should note this.6 this is a 4-variable K-map.Please give the cell 11’s adjacent cells! Now you should know except cell 12 and 15, cell 3 and 9 are cell 11’s adjacent cells.Cell 3 is on the right side of the cell 11, and cell 9 is on the lower side.7 Ok, let’s summarize the feature of K-map.Fist, if a k-map has n variables, it must poe 2 to power n cells.Second, when you design a k-map, please note how to change the binary number on the upper and left side, there is only a single-variable value changed between adjacent cells.Third, it’s easy to find a cell’s adjacent cells, but I must emphasize that you don’t ignore these cells located in the symmetric place.Please care about these, it will easy for you to make use of K-map.8 after discuing K-map, let’s learn how to represent a truth table on k-map.Here is an example.This is a truth table of a 3-variable function, the knowledge about the truth table has been discued earlier.
9 The key step is to design a K-map, we know the function has 3 variables, the k-map also has 3-varibales, according to the features of k-map, there are 2 to power 3 cells in the K-map, they are 8 cells.Then the binary numbers will be written, you seem to note there is only single-variable value changed between adjacent cells, we have drawn a K-map.The second step is to mapping the logic function.It is an easy work for you to enter the value of the output variable Y in each cell. On the K-map, cell 0 corresponds to row 0, because the variables’ value are same, a is equal to 0, b is equal to 0, c is equal to 0, so we should enter 0 in cell 0.Cell 1 corresponds to row 1, a is equal to 0, b is equal to 0, c is equal to 0, enter 1 in cell 1.so we can draw a conclusion if all variables’ value on the map is same as those in the table, enter output value in corresponding cell.Ok, fig.5.3 gives the complete K-map of the truth table.
10 Look at this example 2, this equation is in SOP form, first we should convert it into standard SOP, and then it can be represented on K-map.Observe this equation, this term and this term are not minterm.Although minterm and SOP form are discued early, I think it’s neceary to review this knowledge.Minterm is also called standard product form, we look at example 2, the 3 terms are product form.This and this terms are only product form, they are not standard product form.But this term is standard product form.What’s minterm? A function has n variables, if the product term contains n variables, each variable may be in complemented form or in uncomplemented form.The product term is called a minterm or standard product form.11 of course, it’s easy to understand that if a function has n variables, there must be 2 to power n minterms.There are 3 variables A,B,C, so we can write 8 minterms.12 if the logical function is represented as a sum of minterms only, the function is said to be in standard sum of products form.This expreion is not in standard SOP form, because this and this term are not minterms, and this expreion is in standard SOP form.13 In fact, the logical function can be converted into standard SOP form.We know the C plus the complement of c equal 1, any term multiply 1 equal itself.So if the fist term multiplies this expreion, it can be converted into two minterms, the two sides of the equal mark are equivalent.The second term can be converted into two minterms by the same way.We can get a standard SOP form.14 the represent the SOP form on K-map.15 According to minterm’s features, logical 1 corresponds to the original variable, logical 0 corresponds to complement of variable.When a equal 0, b equal 0, c equal 0, we can get this minterm, this term corresponds to this cell.In fact, the K-Map includes all minterms.16 the first term corresponds to this cell, so we enter 1 in this cell.the second term corresponds to this cell, so we enter 1 in this cell.the third term corresponds to this cell, so we enter 1 in this cell.the forth term corresponds to this cell, so we enter 1 in this cell.the fifth term corresponds to this cell, so we enter 1 in this cell.17 Ok.The equation in standard SOP form is represented on K-Map.18 this section is very important.It is well-known that K-map is perhaps the most extensively used tool for simplification of logical function.Ok, let’s look at how to simplify logical function using K-map.We will illustrate every step through a example so that you can understand this method easily.Let’s look at the fist step, Mark those cells with a 1 that correspond to the terms in expreion.Here is an equation in standard SOP form.After designing a k K-map, enter 1s in corresponding cells.So we get fig 5.6.19 Form the 1s into the largest valid group.Some conditions limit the largest group.The group must be a rectangle, and must contain 2 to power i cells, i is equal 0, 1, 2, n.n is the number of variables.When you face this K-map, how to make valid group, on the left side, there are 3 ones, on the right side, there are 2 ones.The 3 ones couldn’t form a group, because it is not rectangle, and it has 3 cells, normally, the group should contain 1, 2, 3, or 8 cells.But these 2 ones can form a group, these and these also can form a group.u should remember this cell and this cell are adjacent, this cell is on the left side of this cell, this cell is in the right side of this cell, the two cells are the same.So these 4 cells should form a group, and it also satisfy the demand of form the largest group.ok we have formed two groups
20 Step 3 each 1 on the map must be included in at least one group.The ones already in a group can be included in another group as long as the overlapping groups include noncommon ones.Please note this cell, it isn’t only in the group, but also in this group, it belongs to the two groups, these 2 groups are permitted.Because the 2 overlapping groups include noncommon ones.Except this cell , this group has this cell, this group has this, this and this cells.21 Step 4 will give us a rule about how to produce terms.Identify adjacent ones in a group, then see the values of the variable aociated with these cells.If the variables will be different and they gets eliminated.Other variables will appear in ANDed form in the term.This map exist 2 groups.We observe this group first, the value of variable C is not changed, it is equal to 1.the value of A is also not changed, it’s equal to 0, but look at variable B, the value is changed from 0 to 1 between adjacent cells, variable B should be eliminated.The other two Variables A, and C will appear in ANDed form in the term, I have to emphasize that this term is written by the method of producing minterm.0 corresponds to complemented variable, 1corresponds to uncomplemented variable.So we get this term.Then we observe this group include 4 cells, the value of variable B is not changed, the others will be eliminated.We get the complemented B.two groups get 2 terms.22 step5 these terms are ORed to get the simplified equation in SOP form.This equation is previous, and this is simplified equation, in fact, it’s a simplest expreion, these two equations are equivalent.Now, we have simplified a logical expreion using K-map, do you find it is a simple and efficient method? Remember these 5 steps, they are useful.23 After this chapter, we should appreciate the two points.First, you must know how to design a K-map; it’s a basal and important knowledge.When you design a K-map, you should pay more attention to these details.Second, simplification a logical expreion using K-map method, we know this method is simplest and most commonly used method, it’s an eential knowledge in this chapter and easy for you to be operated, I will give you some homework to practice yourselves, they are 7, 12, 16, and 18 on the page 188 and 189 respectively.Please treat them seriously, you will get promoted.
