👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Number Systems & Logic
Study mode

K-map

Study Practice Revise 🔒 Test

Introduction to Karnaugh Maps (K-maps)

In the study of computer aptitude and digital logic, simplifying Boolean expressions is a crucial skill. Boolean expressions represent logical relationships using variables that can be either true (1) or false (0). However, as the number of variables increases, these expressions can become complex and difficult to manage.

This is where the Karnaugh Map, or K-map, comes into play. A K-map is a graphical tool that helps visualize and simplify Boolean expressions efficiently. It reduces the complexity of logical expressions by organizing truth table values into a grid format, making it easier to spot patterns and minimize terms.

For students preparing for competitive exams, mastering K-maps is essential because it saves time and reduces errors when simplifying logic functions, which often appear in entrance tests for engineering and computer science courses.

K-map Layout and Basics

To understand K-maps, let's start from the basics. A K-map is essentially a visual representation of a truth table arranged in a way that adjacent cells differ by only one variable. This arrangement follows the Gray code sequence, which ensures that only one bit changes between neighboring cells.

Each cell in a K-map corresponds to a specific combination of input variables and holds the output value (0 or 1) of the Boolean function for that combination.

Let's begin with the simplest K-map - a 2-variable K-map.

2-variable K-map Layout

For two variables, say A and B, there are \(2^2 = 4\) possible input combinations. The K-map is a 2x2 grid where each cell corresponds to one combination of A and B.

The variables are arranged such that the columns and rows follow Gray code ordering:

B A 0 1 0 1 00 01 11 10 Cell labels show (A,B)

Explanation: The top row corresponds to \(B=0\), the bottom row to \(B=1\). The left column corresponds to \(A=0\), and the right column to \(A=1\). Notice the Gray code ordering in the bottom row: 11 (A=1,B=1) is adjacent to 10 (A=1,B=0), differing by only one bit.

Grouping and Simplification Rules

The main power of K-maps lies in grouping adjacent cells containing 1s to simplify the Boolean expression. These groups must follow specific rules:

  • Groups must contain 1, 2, 4, 8, ... (powers of two) cells.
  • Cells in a group must be adjacent horizontally or vertically (not diagonally).
  • Groups can wrap around the edges of the K-map, treating the map as if it loops around.
  • Each 1 in the K-map must be included in at least one group.
  • Groups should be as large as possible to maximize simplification.

Let's see how grouping works in a 3-variable K-map.

Grouping in a 3-variable K-map

A 3-variable K-map has \(2^3 = 8\) cells arranged in a 2x4 grid. Here's an example with some 1s grouped:

AB C 0 0 1 1 0 1 1 1 0 0 1 1 0 0

Explanation: The red rectangle groups four 1s in the top-left corner (cells with C=0, AB=00 and 01). The green rectangle groups four 1s in the bottom-left corner (cells with C=1, AB=00 and 01). These groups help simplify the Boolean expression by combining terms.

Worked Example 1: Simplify a 2-variable Boolean Expression using K-map

Example 1: Simplify F(A,B) = \(\sum m(1,3)\) Easy

Given the Boolean function \(F(A,B)\) which is 1 for minterms 1 and 3, simplify it using a 2-variable K-map.

Step 1: List all minterms for 2 variables. The minterms correspond to the decimal equivalent of the binary inputs:

  • 0: A=0, B=0
  • 1: A=0, B=1
  • 2: A=1, B=0
  • 3: A=1, B=1

Step 2: Draw the 2-variable K-map and fill in 1s for minterms 1 and 3, 0s elsewhere.

A
0 1
B=0 0 0
B=1 1 1

Step 3: Group adjacent 1s. Here, the two 1s are adjacent horizontally in the bottom row.

Step 4: Determine the simplified expression from the group. Since B=1 in both cells and A changes, the simplified expression is:

Answer: \(F = B\)

Worked Example 2: Simplify a 3-variable Boolean Expression with Don't Care Conditions

Example 2: Simplify \(F(A,B,C) = \sum m(1,3,5,7)\) with don't care \(d(0,2)\) Medium

Simplify the Boolean function \(F\) where the function is 1 for minterms 1, 3, 5, 7 and don't care for minterms 0 and 2 using a 3-variable K-map.

Step 1: Identify the minterms and don't care terms.

  • 1: 001
  • 3: 011
  • 5: 101
  • 7: 111
  • Don't care: 0 (000), 2 (010)

Step 2: Draw the 3-variable K-map (2 rows for C, 4 columns for AB in Gray code order: 00, 01, 11, 10).

AB
00 01 11 10
C=0 d (X) 1 1 d (X)
C=1 0 1 1 0

Step 3: Use don't care cells (marked X) to form larger groups of 1s.

Step 4: Group the four 1s in the middle columns (01 and 11) across both rows, including don't cares to maximize group size.

Step 5: Simplify the expression from the group.

  • Group covers AB=01 and 11, so B=1 (since B=0 to 1 changes, but A=1 or 0)
  • C changes from 0 to 1, so C is eliminated.

Answer: \(F = B\)

Worked Example 3: Simplify a 4-variable Boolean Expression

Example 3: Simplify \(F(A,B,C,D) = \sum m(0,2,5,7,8,10,13,15)\) Hard

Simplify the Boolean function \(F\) with four variables \(A, B, C, D\) given the minterms above using a 4-variable K-map.

Step 1: Understand that a 4-variable K-map has \(2^4 = 16\) cells arranged in a 4x4 grid.

The rows represent variables \(A\) and \(B\) in Gray code order: 00, 01, 11, 10.

The columns represent variables \(C\) and \(D\) in Gray code order: 00, 01, 11, 10.

CD
00 01 11 10
00 (AB) 1 (0) 0 (1) 0 (3) 1 (2)
01 (AB) 0 (4) 1 (5) 0 (7) 0 (6)
11 (AB) 0 (12) 0 (13) 1 (15) 0 (14)
10 (AB) 1 (8) 0 (9) 0 (11) 1 (10)

Step 2: Mark 1s in the K-map for minterms 0, 2, 5, 7, 8, 10, 13, 15.

Step 3: Group adjacent 1s in powers of two, remembering to consider wrapping around edges.

  • Group 1: Minterms 0 and 8 (top-left and bottom-left corners) wrap vertically.
  • Group 2: Minterms 2 and 10 (top-right and bottom-right corners) wrap vertically.
  • Group 3: Minterms 5 and 7 (middle row) horizontally adjacent.
  • Group 4: Minterms 13 and 15 (third row) horizontally adjacent.

Step 4: Write simplified terms for each group:

  • Group 1 (0,8): \(B'=0\) (B=0), \(D'=0\) (D=0), \(A\) and \(C\) vary -> term: \(B'D'\)
  • Group 2 (2,10): \(B'=0\), \(D=1\) -> term: \(B'D\)
  • Group 3 (5,7): \(A=0\), \(B=1\), \(C=1\), \(D\) varies -> term: \(AB C\)
  • Group 4 (13,15): \(A=1\), \(B=1\), \(C=1\), \(D\) varies -> term: \(AB C\)

Step 5: Combine terms:

\(F = B'D' + B'D + AB C\)

Answer: The simplified Boolean expression is \(F = B' + AB C\)

Worked Example 4: Simplify a Boolean Function from a Real-life INR-based Logic Scenario

Example 4: Simplify a logic function for currency denomination detection Medium

A vending machine accepts INR notes of denominations Rs.10, Rs.20, Rs.50, and Rs.100. The machine uses three sensors represented by variables \(A, B, C\) to detect the note type. The output \(F\) is 1 if the note is Rs.20 or Rs.100. Given the truth table below, simplify \(F\) using a 3-variable K-map.

ABCF
0000
0011
0100
0110
1001
1010
1100
1110

Step 1: Identify minterms where \(F=1\): minterms 1 (001) and 4 (100).

Step 2: Draw the 3-variable K-map and plot 1s at minterms 1 and 4.

AB
00 01 11 10
C=0 0 0 0 1
C=1 1 0 0 0

Step 3: Since the two 1s are not adjacent, each forms a group of one.

Step 4: Write simplified terms:

  • Minterm 1 (001): \(A=0, B=0, C=1\) -> \(A' B' C\)
  • Minterm 4 (100): \(A=1, B=0, C=0\) -> \(A B' C'\)

Answer: \(F = A' B' C + A B' C'\)

Worked Example 5: Simplify a Logic Circuit Expression for a Metric Measurement Sensor System

Example 5: Simplify \(F(A,B,C,D) = \sum m(1,3,7,11,15)\) Hard

A sensor system uses four binary inputs \(A, B, C, D\) to measure metric units. The output \(F\) is 1 for minterms 1, 3, 7, 11, and 15. Simplify the function using a 4-variable K-map.

Step 1: Plot the 1s in the 4-variable K-map.

Step 2: Identify possible groups:

  • Group 1: Minterms 3, 7, 11, 15 (rightmost column) form a vertical group of 4.
  • Group 2: Minterms 1 and 3 (top row) form a horizontal group of 2.

Step 3: Write simplified terms:

  • Group 1: \(D=1\), \(B=1\), \(A\) and \(C\) vary -> term: \(B D\)
  • Group 2: \(A=0\), \(B=0\), \(C=0\), \(D\) varies -> term: \(A' B' C'\)

Answer: \(F = B D + A' B' C'\)

Formula Bank

Boolean Expression Simplification
\[ F = \sum m(\text{minterms}) \]
where: \(F\) is the Boolean function; \(m\) are minterms representing input combinations where \(F=1\)
Number of Cells in K-map
\[ N = 2^n \]
where: \(N\) is the number of cells; \(n\) is the number of variables

Tips & Tricks

Tip: Always look for the largest possible groups (powers of two) to simplify more effectively.

When to use: When grouping 1s in the K-map to minimize Boolean expressions.

Tip: Use don't care conditions to your advantage by including them in groups to simplify expressions further.

When to use: When don't care terms are present in the Boolean function.

Tip: Remember that K-map edges wrap around, so cells on the borders can be grouped together.

When to use: When grouping cells at the edges of the K-map.

Tip: Practice converting truth tables to K-maps quickly to save time during exams.

When to use: When given truth tables in competitive exam questions.

Tip: Use mnemonic devices to remember Gray code ordering for variable labeling in K-maps.

When to use: When setting up K-map cells for multiple variables.

Common Mistakes to Avoid

❌ Grouping cells that are not adjacent or not in powers of two.
✓ Only group 1s that are adjacent horizontally or vertically in groups of 1, 2, 4, 8, etc.
Why: Students often try to group diagonally or irregular groups, which leads to incorrect simplification.
❌ Ignoring don't care conditions or treating them as zeros.
✓ Use don't care terms as either 1 or 0 to maximize group sizes for simplification.
Why: Students miss the opportunity to simplify expressions further by not utilizing don't care terms.
❌ Forgetting that K-map edges wrap around and missing possible groups.
✓ Always consider wrap-around adjacency when grouping cells on edges.
Why: Students overlook wrap-around adjacency, leading to suboptimal grouping and more complex expressions.
❌ Mislabeling K-map cells due to incorrect Gray code ordering.
✓ Follow Gray code sequence strictly when labeling rows and columns in the K-map.
Why: Incorrect labeling causes wrong grouping and wrong final expressions.
❌ Overlapping groups unnecessarily or missing larger groups.
✓ Aim for the largest possible groups and avoid redundant smaller groups unless necessary.
Why: Smaller groups increase the complexity of the simplified expression.
Key Concept

K-map Grouping Rules

Group 1s in powers of two (1, 2, 4, 8), groups must be adjacent horizontally or vertically, edges wrap around, largest groups simplify best.

Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
K-map · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.