Mastering Karnaugh Maps (K-Maps) for GCE A/L
Welcome! If you are finding Boolean Algebra confusing, K-Maps are your best friend. They turn complex algebra into a visual puzzle. Here is everything you need to know, step-by-step.
1. What is the Purpose?
The main purpose of a K-Map is to simplify Boolean equations. Instead of using long algebraic laws (like De Morgan's or Distributive laws), we use a visual grid to group terms together and eliminate variables.
2. Truth Tables vs. K-Maps
- Normal Truth Tables (1D): These are lists. You read them from top to bottom. They show every possible input combination.
- K-Maps (2D): These are grids (tables). We take that 1D list and "fold" it into a 2D shape. This allows us to see patterns (neighbors) that are hard to see in a list.
3. SOP vs. POS
There are two ways to write equations, and two ways to use K-Maps:
- SOP (Sum of Products): You look for Minterms. In the K-Map, you place 1s and group the 1s.
- POS (Product of Sums): You look for Maxterms. In the K-Map, you place 0s and group the 0s.
Note: For this guide, we will focus on SOP (Grouping 1s) as it is the most common method for beginners.
4. Grid Sizes (Dimensions)
The size of your K-Map depends on the number of variables (inputs). For 3 Variables (x, y, z):
Total combinations = $2^3 = 8$.
You can arrange these 8 cells in different 2D shapes:
- 1 row × 8 columns (1x8)
- 8 rows × 1 column (8x1)
- 2 rows × 4 columns (2x4) (Most Common for 3 variables)
- 4 rows × 2 columns (4x2)
5. The Secret Weapon: Gray Code
This is the most important rule in K-Maps. When labeling the rows and columns, you cannot use normal binary counting (00, 01, 10, 11). You must use Gray Code.
Rule: Between any two adjacent numbers, only one bit (value) changes.
Sequence for 2 bits: 00 → 01 → 11 → 10
- 00 to 01: Only the right bit changed.
- 01 to 11: Only the left bit changed.
- 11 to 10: Only the right bit changed.
If you do not use Gray Code, your K-Map will not work!
6. Step-by-Step Example
Let's solve this function together:
Step 1: Convert to Binary (Minterms)
Look at each term. If a variable has a bar (like x'), it is 0. If it has no bar (like x), it is 1.
x'y'z→ 0 0 1 (Decimal 1)x'yz→ 0 1 1 (Decimal 3)xy'z→ 1 0 1 (Decimal 5)xyz'→ 1 1 0 (Decimal 6)xyz→ 1 1 1 (Decimal 7)
Step 2: Create the Truth Table
We list all 8 combinations (0 to 7). We put a 1 in the Output column if the number matches our list above (1, 3, 5, 6, 7). Otherwise, put a 0.
| Decimal | x | y | z | Output (F) | Note |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | From x'y'z |
| 2 | 0 | 1 | 0 | 0 | |
| 3 | 0 | 1 | 1 | 1 | From x'yz |
| 4 | 1 | 0 | 0 | 0 | |
| 5 | 1 | 0 | 1 | 1 | From xy'z |
| 6 | 1 | 1 | 0 | 1 | From xyz' |
| 7 | 1 | 1 | 1 | 1 | From xyz |
Step 3: Draw the K-Map Grid
We will use a 2 rows × 4 columns grid.
- Rows (x): 0, 1
- Columns (yz): 00, 01, 11, 10 (Remember Gray Code!)
| x \ yz | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
We placed 1s in cells 1, 3, 5, 6, and 7 based on our Truth Table.
Step 4: Grouping (The Magic Step)
Rules for grouping:
- Groups must contain $2^n$ cells (1, 2, 4, 8, 16...).
- Groups must be rectangular or square.
- Try to make groups as large as possible.
- Every 1 must be inside at least one group.
- Groups can overlap.
Let's group our example:
- Group A (Red): Look at the middle two columns (01 and 11). We have four 1s forming a square (Cells 1, 3, 5, 7).
Why? In this group, x changes (0 to 1) and y changes (0 to 1). But z is always 1.
Result:z - Group B (Blue): Look at the bottom right corner. We have two 1s (Cells 6 and 7).
Why? In this group, z changes (0 to 1). But x is always 1 and y is always 1.
Result:xy
Step 5: Final Equation
Combine the results of the groups with an OR (+) sign.
This is much simpler than the original long equation!
7. How to do POS (Product of Sums)
If the question asks for POS, or gives you Maxterms (0s):
- Fill the K-Map with 0s instead of 1s (wherever the function is false).
- Group the 0s together.
- When writing the equation:
- If a variable is 0 in the group, write it normally (e.g., A).
- If a variable is 1 in the group, write it with a bar (e.g., A').
- Combine variables with OR (+), and combine groups with AND (·).
