1.3.5 Simplification of Boolean Function using Karnaugh Map (K-Map)

Boolean functions can be simplified using a visual method called the Karnaugh Map. This method makes it easier to reduce a Boolean expression to its simplest form, which results in cheaper and simpler logic circuits.

Definition

Karnaugh Map (K-Map) was introduced by Maurice Karnaugh in 1953. It provides a simple method for simplifying Boolean functions.

Main Idea

When a simplified Boolean function is converted into a logic circuit, it requires less number of gates and hence costs less. K-map is a pictorial form of a truth table. It consists of square boxes called cells. All the possible combinations of variables involved in a Boolean function are written inside the cells in their respective positions.

Core Concept

Structure of a K-Map A two-variable K-map contains 22=422=4 cells. A three-variable K-map contains 23=823=8 cells. And so forth for more variables. Two-Variable K-Map A two-variable K-map for variables A and B consists of four cells having two rows and two columns. Each row and column is labelled with a variable and its complement. The complement of a variable is also called prime.

Each cell contains a product term of variables A and B in its respective cell. For example, the term AB is placed in the cell that is in row A and column B.

Detailed Explanation

Simplification of a Two-Variable Boolean Function Using K-Map Example 1: Simplify the Boolean function F1=AˉB+ABˉ+ABF1=AˉB+ABˉ+AB using K-map. Step 1: Plot the terms of the function on the Karnaugh map. This function has three terms. For each term, a 1 will be placed in the corresponding cell. Step 2: Group cells for simplification. Grouping means combining cells in adjacent cells. The K-map contains a pair of 1s that is horizontally adjacent and another pair of 1s that is vertically adjacent. Step 3: Combine two terms by eliminating the variable that is in both normal and complemented form. In the horizontal group, B appears in both normal and complemented form. Therefore, B will be eliminated in this group and only A is left. In the vertical group, A appears in both normal and complemented form. Therefore, A will be eliminated in this group and only B is left. Step 4: Write the result as the sum of variables. F1=A+BF1=A+B Rules for Simplifying a Two-Variable Boolean Function The book gives the following rules:

For each term of the function, place 1 in the corresponding cell in the Karnaugh map.1. Make groups of two cells that contain 1.2. Groups may be horizontal or vertical but not diagonal.3. Groups may overlap.4. Eliminate the variable that is in normal and complemented form in the group.5. Write the simplified function in the form of sum of variables that were not eliminated in groups.6. If a K-map contains two 1s in diagonal cells, then a group cannot be formed, which means the function cannot be simplified.7. Simplification of a Three-Variable Boolean Function using K-Map A three-variable K-map for variables A, B and C consists of eight cells having two rows and four columns. Rows are labelled with the complement and normal form of the variable A. Each column is labelled with two variables, B and C, in their normal or complemented form. Each cell contains a product term of variables A, B and C in its respective cell. For example, the term ABC is placed in the cell that is in row A and column BC. Rules for Simplifying a Three-Variable K-Map: The book gives the following rules: For each term of the function, place 1 in the corresponding cell in the Karnaugh map.1. Form groups of four if possible, otherwise groups of two.2. Groups can contain only 1s.3. Groups can be horizontal or vertical.4. Groups can overlap and wrap around the side of the K-map.5. If possible, include each 1 in at least one group.6. Eliminate the variables that are in normal and complemented form in a group and create a term for each group.7. Write the simplified function in the form of sum of terms.8. If a cell containing a 1 cannot be included in any group, then write the full term with three variables.9. Example 2: Simplify the Boolean function

F1=AˉBC+AˉBˉCˉ+ABˉCˉ+ABˉCF1=AˉBC+AˉBˉCˉ+ABˉCˉ+ABˉC Step 1: Plot all the terms of the function on the three-variable Karnaugh map. This function has four terms. For each term, a 1 will be placed in the corresponding cell. (Further simplification steps follow the same grouping and elimination rules as for the two-variable K-map.)

Important Points

• K-Map was introduced by Maurice Karnaugh in 1953.
• K-Map provides a simple method for simplifying Boolean functions.
• Simplified Boolean functions require fewer gates and cost less.
• K-map is a pictorial form of a truth table.
• It consists of square boxes called cells.
• A two-variable K-map has 4 cells; a three-variable K-map has 8 cells.
• Each row and column is labelled with a variable and its complement.
• The complement of a variable is also called prime.
• Groups may be horizontal or vertical but not diagonal.
• Groups may overlap.
• In a three-variable K-map, groups can wrap around the side.
• Eliminate the variable that is in both normal and complemented form in a group.
• If two 1s are in diagonal cells, a group cannot be formed.

Remember

• K-Map = pictorial form of a truth table.
• Introduced by Maurice Karnaugh in 1953.
• Two-variable K-map 4 cells.
• Three-variable K-map 8 cells.
• Groups horizontal or vertical, not diagonal.
• Groups may overlap.
• In three-variable K-map, groups can wrap around the side.
• Eliminate the variable that appears in both normal and complemented form.
• Two 1s in diagonal cells no group cannot be simplified.
• Result is written as the sum of the remaining variables or terms.

Common Mistakes

• Forming diagonal groups. Groups must be horizontal or vertical only.
• Forgetting that groups may overlap.
• Forgetting that in a three-variable K-map, groups can wrap around the side.
• Not eliminating the variable that appears in both normal and complemented form within a group.
• Trying to form a group from two diagonal 1s — this is not allowed.
• Missing a 1 that should be included in at least one group.
• Writing the simplified function incorrectly instead of as a sum of the terms obtained from the groups.

Quick Revision

Karnaugh Map (K-Map) was introduced by Maurice Karnaugh in 1953. It provides a simple method for simplifying Boolean functions.

When a simplified Boolean function is converted into a logic circuit, it requires fewer gates and hence costs less. K-map is a pictorial form of a truth table. It consists of square boxes called cells. All possible combinations of variables involved in a Boolean function are written inside the cells in their respective positions. A two-variable K-map contains 4 cells, a three-variable K-map contains 8 cells, and so forth. Each row and column is labelled with a variable and its complement. The complement of a variable is also called prime. In a two-variable K-map, the simplification is done by grouping adjacent 1s (horizontally or vertically, not diagonally). Groups may overlap. The variable that appears in both normal and complemented form in a group is eliminated. If two 1s are in diagonal cells, a group cannot be formed, which means the function cannot be simplified. For a three-variable K-map, groups of four are formed if possible, otherwise groups of two. Groups can overlap and wrap around the side of the K-map. If a cell containing a 1 cannot be included in any group, then the full term with three variables is written.

60-Second Revision

K-Map = pictorial truth table; introduced by Maurice Karnaugh in 1953. Fewer gates lower cost. 2-variable K-map 4 cells; 3-variable K-map 8 cells. Rows/columns labelled with variable and its complement (prime). Groups: horizontal or vertical, not diagonal. Groups may overlap; in 3-variable K-map they can wrap around the side. Eliminate the variable in both normal and complemented form. Warning: diagonal 1s cannot form a group — such functions cannot be simplified.