Karnaugh Maps (K-Map) Masterclass: 3-Variable and 4-Variable Solved TU BCA Problems

Author: Bhuban Subedi | Subject: Digital Logic (CACS105) | Semester: First Semester

In the Tribhuvan University (TU) BCA First Semester Digital Logic (CACS105) board examination, if there is one question that is guaranteed to appear every single year without fail, it is Karnaugh Map (K-Map) Simplification.

Usually carrying 6 to 8 marks, K-Map problems are your golden opportunity to secure full marks. Yet, many students struggle with grouping mistakes, improper Gray code labeling, or misunderstanding how to leverage Don’t Care ($d$) conditions.

In this master tutorial, we will break down the underlying logic of K-Maps, understand why Gray code is used, master the grouping rules (pairs, quads, octets, and overlapping/wrapping), and solve both Sum of Products (SOP) and Product of Sums (POS) board questions.

1. What Is a Karnaugh Map & Why Do We Use It?

While algebraic minimization using Boolean theorems works well for simple 2-variable expressions, it quickly becomes error-prone and tedious for 3, 4, or 5 variables.

A Karnaugh Map (K-Map) is a graphical tabular technique invented by Maurice Karnaugh in 1953. It arranges minterms or maxterms in a grid such that adjacent cells differ by exactly one binary bit.

Number of Cells in a K-Map = 2^n  (where n is the number of input variables)
- 2 Variables -> 2^2 = 4 cells
- 3 Variables -> 2^3 = 8 cells
- 4 Variables -> 2^4 = 16 cells

Why Gray Code Ordering?

Look closely at the column and row headings: 00, 01, 11, 10.
Notice that between 01 and 11, only one bit changes ($0 \rightarrow 1$). If we had used standard binary order (00, 01, 10, 11), moving from 01 to 10 would change two bits simultaneously, breaking spatial adjacency.

2. Standard 3-Variable and 4-Variable K-Map Grids

A. 3-Variable K-Map Layout ($A, B, C$)

Variables: $A$ (Row: 1 bit), $BC$ (Columns: 2 bits)

       BC
 A    00    01    11    10
    +-----+-----+-----+-----+
 0  | m0  | m1  | m3  | m2  |
    +-----+-----+-----+-----+
 1  | m4  | m5  | m7  | m6  |
    +-----+-----+-----+-----+

(Notice cell ordering: $0, 1, 3, 2$ and $4, 5, 7, 6$)

B. 4-Variable K-Map Layout ($A, B, C, D$)

Variables: $AB$ (Rows: 2 bits), $CD$ (Columns: 2 bits)

        CD
 AB     00     01     11     10
     +------+------+------+------+
 00  |  m0  |  m1  |  m3  |  m2  |
     +------+------+------+------+
 01  |  m4  |  m5  |  m7  |  m6  |
     +------+------+------+------+
 11  | m12  | m13  | m15  | m14  |
     +------+------+------+------+
 10  |  m8  |  m9  | m11  | m10  |
     +------+------+------+------+

(Notice both the 3rd column and 3rd row swap positions to maintain Gray code integrity!)

3. The Golden Rules of K-Map Grouping

To achieve the Minimal Expression, you must follow these rules strictly:

1. Groups Must Be Powers of 2: You can only group $1, 2, 4, 8, 16$ adjacent cells containing 1s (Single, Pair, Quad, Octet). You cannot group 3, 5, or 6 cells.
2. Groups Must Be Rectangular or Square: Diagonal groupings are strictly illegal.
3. Always Target the Largest Possible Group: An octet eliminates 3 variables, a quad eliminates 2 variables, and a pair eliminates 1 variable. Larger groups yield simpler final expressions.
4. Map Wrapping / Torus Property: The leftmost column is adjacent to the rightmost column. The top row is adjacent to the bottom row. The 4 extreme corners ($m_0, m_2, m_8, m_{10}$) form a valid Quad!
5. Overlapping Is Allowed: A 1 can be part of multiple groups if it helps enlarge another group.
6. Eliminate Redundant Groups: If every 1 inside a group is already covered by other valid groups, that group is redundant and must be discarded.

4. Solved TU Board Question 1: 4-Variable SOP with Don’t Cares

Board Question:

“Simplify the following Boolean function in SOP form using a 4-variable K-Map and draw the logic circuit using NAND gates only:”
$$F(A, B, C, D) = \sum m(1, 3, 7, 11, 15) + d(0, 2, 5)$$

Step 1: Populate the K-Map Grid

• Place 1 in minterm cells: $1, 3, 7, 11, 15$.
• Place X in Don’t Care cells: $0, 2, 5$.
• All remaining cells are 0.

        CD
 AB     00     01     11     10
     +------+------+------+------+
 00  |  X   |  1   |  1   |  X   |
     +------+------+------+------+
 01  |  0   |  X   |  1   |  0   |
     +------+------+------+------+
 11  |  0   |  0   |  1   |  0   |
     +------+------+------+------+
 10  |  0   |  0   |  1   |  0   |
     +------+------+------+------+

Step 2: Form Optimal Groups

1. Group 1 (Entire Column $CD = 11$):
2. Covers minterms: $m_3, m_7, m_{15}, m_{11}$ (all four are 1).
3. Group size: Quad (4 cells).
4. Elimination: Row variables $AB$ vary through $00, 01, 11, 10$ and cancel out completely.

5. Remaining Term: $\mathbf{CD}$

6. Group 2 (Top Row with Don’t Cares):

7. Look at the top row ($AB = 00$): cells are $X, 1, 1, X$ (indices $0, 1, 3, 2$).
8. By utilizing the Don’t Cares $X$ at $m_0$ and $m_2$, we can form a Quad (4 cells) across the entire top row!
9. Covers minterm $m_1$ and $m_3$.
10. Elimination: Column variables $CD$ cancel out.

11. Remaining Term: $\mathbf{A’B’}$

12. Check Coverage & Don’t Cares:

13. Minterms covered: $1, 3, 7, 11, 15$ (All 1s are 100% covered).
14. Don’t care at $m_5$ remains unused. We do not need to group unused Don’t Cares.

Step 3: Minimal SOP Expression

$$\mathbf{F = CD + A’B’}$$

Logic Circuit using NAND Gates (Universal Gate Implementation):
Apply Double Negation: F = ((CD + A'B')')' = ((CD)' . (A'B')')'

  C ---+
       |--- [NAND 1] ---> (CD)' -------+
  D ---+                               |
                                       |--- [NAND 3] ---> F
  A' --+                               |
       |--- [NAND 2] ---> (A'B')' -----+
  B' --+

5. Solved TU Board Question 2: Product of Sums (POS) Form

Board Question:

“Minimize the following function in POS form using K-Map:”
$$F(A, B, C, D) = \prod M(0, 1, 4, 5, 8, 9, 12, 13)$$

Step 1: POS Mapping Strategy

In POS minimization, we plot 0s for the given maxterm numbers and group the 0s together.

        CD
 AB     00     01     11     10
     +------+------+------+------+
 00  |  0   |  0   |  1   |  1   |
     +------+------+------+------+
 01  |  0   |  0   |  1   |  1   |
     +------+------+------+------+
 11  |  0   |  0   |  1   |  1   |
     +------+------+------+------+
 10  |  0   |  0   |  1   |  1   |
     +------+------+------+------+

Step 2: Form Grouping of 0s

• Notice the first two columns ($CD = 00$ and $CD = 01$) are completely filled with 0s.
• This forms an Octet (8 cells) covering $M_0, M_1, M_4, M_5, M_{12}, M_{13}, M_8, M_9$.
• Row variables $AB$ cancel completely across all 4 rows.
• For columns: $C$ remains $0$, while $D$ changes from $0$ to $1$ (cancels).
• In POS form, a variable with value $0$ is written uncomplemented: $\mathbf{(C)}$.

$$\mathbf{Minimal\ POS\ Expression: F = C}$$

Frequently Asked Questions (FAQ)

Q1: What is an Essential Prime Implicant (EPI)?

A Prime Implicant is a group of adjacent minterms that cannot be combined with any larger group. An Essential Prime Implicant (EPI) is a prime implicant that covers at least one 1 that is not covered by any other prime implicant. EPIs must always be included in the final minimal expression.

Q2: Do we have to include all Don’t Care ($d$ or $X$) terms in our groups?

No! Don’t care conditions are optional tools. You should only include an $X$ if it helps you form a larger group (e.g., turning a pair into a quad). If an $X$ does not help enlarge any group of 1s, leave it alone.