Boolean Algebra and K-Maps for GATE: Laws, Minimization, Don't Cares and Solved Examples

Boolean algebra and K-maps for GATE: the laws that matter, minterms, grouping rules, wrap-around, don't cares, a solved K-map, common traps and practice questions.

Every digital circuit you'll meet in GATE, from a simple adder to a counter, starts life as a Boolean expression. The shorter that expression, the fewer gates you need, the cheaper the chip and the faster the signal gets through. So the very first skill in Digital Electronics is taking a messy expression and making it as small as possible.

There are two tools for this: Boolean algebra and the Karnaugh map, or K-map. GATE asks about both almost every year, usually as quick one- or two-mark questions. Once you know the handful of laws and the grouping rules below, most of them take under two minutes.

The Boolean laws you actually need

A Boolean variable is either 0 or 1. We write OR as $+$, AND as a product $\cdot$ (or just side by side), and NOT with a bar, $\bar{A}$. Here are the laws that do almost all the work:

Law OR form AND form --------- Identity $A + 0 = A$ $A \cdot 1 = A$ Null $A + 1 = 1$ $A \cdot 0 = 0$ Idempotent $A + A = A$ $A \cdot A = A$ Complement $A + \bar{A} = 1$ $A \cdot \bar{A} = 0$ Absorption $A + AB = A$ $A(A + B) = A$ De Morgan $\overline{A + B} = \bar{A}\,\bar{B}$ $\overline{AB} = \bar{A} + \bar{B}$

Two more come up so often that they deserve their own lines. The first one saves a step in many simplifications:

The second is the consensus theorem. The term $BC$ is redundant, because whenever it's 1, one of the other two terms is already 1:

A quick example. Simplify $F = AB + A\bar{B} + \bar{A}B$:

Three terms became one OR gate.

Minterms, maxterms and the Σ notation

GATE questions usually give a function as a list of minterms, the input rows of the truth table where the output is 1. Each row is numbered by reading its inputs as a binary number, with $A$ as the most significant bit. For three variables, row $A = 1, B = 0, C = 1$ is $1012 = 5$, and its minterm is $A\bar{B}C$.

means $F$ is 1 on rows 1, 3, 5 and 7, and 0 everywhere else. The same function in maxterm form lists the 0 rows instead:

The two lists are always complements of each other. A sum of minterms leads to a sum of products (SOP) answer, and a product of maxterms leads to a product of sums (POS) answer. In this example, every listed row has $C = 1$, so $F = C$.

How a K-map works

Algebra works, but it's easy to miss a step. A K-map does the same job visually. It's the truth table rearranged into a grid so that cells next to each other differ in exactly one variable. That's why the rows and columns run 00, 01, 11, 10, in Gray code, and not in normal binary order.

When two neighbouring cells are both 1, the one variable that changes between them drops out, just as $AB + A\bar{B} = A$ did above. Group four cells and two variables drop out. Group eight and three drop out.

Look at Fig. 1. The four 1s in the centre all have $B = 1$ and $D = 1$, while $A$ and $C$ change, so that group is simply $BD$. The four corners look far apart, but the map wraps around from top to bottom and from left to right, so the corners are neighbours too. All four have $B = 0$ and $D = 0$, which gives $\bar{B}\bar{D}$. So

That's an XNOR of $B$ and $D$. Eight minterms, each with four literals, shrank to two terms with two literals each. You can see it clearly in a timing diagram:

$F$ is high exactly when $B$ and $D$ are both high or both low.

The grouping rules

These rules decide whether your answer is truly minimal.

Groups must be rectangles of 1, 2, 4, 8 or 16 cells. Never 3, 5 or 6. Make every group as large as possible, even if that means overlapping another group. Use as few groups as possible to cover every 1. The map wraps around: the left edge touches the right edge and the top touches the bottom. A 1 that can only be covered by one particular group makes that group essential. Take the essential groups first.

The whole method fits in one short routine:

Don't-care conditions

Sometimes certain inputs can never happen. A BCD digit, for example, never goes above 1001, so rows 10 to 15 of a BCD circuit don't matter. These are don't cares, written $d(\ldots)$ and marked X on the map. You may treat each X as a 1 when it helps you make a bigger group, and as a 0 when it doesn't.

Here's a typical GATE question:

The 1s at 3, 7, 11 and 15 form a column of four with $C = 1$ and $D = 1$, giving $CD$. That leaves minterm 1. Using the don't cares at 0 and 2, it joins 0, 1, 2 and 3 in a group of four, the whole top row, which is $\bar{A}\bar{B}$. So

Notice that we could also have grouped 1, 3, 5 and 7 using the don't care at 5, which gives $F = CD + \bar{A}D$. Both answers have the same size, so both are minimal. A minimal answer isn't always unique, and GATE options sometimes include both forms. Check each option against the map instead of expecting one fixed answer.

Common traps in GATE questions

These are the mistakes I see most often.

Numbering the map in binary order. The rows and columns go 00, 01, 11, 10. Put 10 before 11 and your groups will be wrong. Forgetting the wrap-around. The four corners of a four-variable map are one group. Students miss this more than anything else. Groups of three or six. Only powers of two are allowed. Stopping at small groups. A pair inside a possible quad isn't minimal. Always try to make each group bigger. Treating don't cares as required. You never have to cover an X. Use it only when it makes a group bigger. Mixing up SOP and POS. For POS, group the 0s and write each group as a sum, with each variable complemented. Getting the variable order wrong. In $\sum m(\ldots)$, $A$ is the most significant bit. Swap the order and every minterm number changes.

Practice questions

Give yourself about two minutes each.

Simplify $A + \bar{A}B + AB$. Simplify $F(A, B, C) = \sum m(0, 2, 4, 6)$. Remove the redundant term from $XY + \bar{X}Z + YZ$. Minimise $F(A, B, C, D) = \sum m(0, 1, 2, 5, 8, 9, 10)$ in SOP form. How many different Boolean functions of 3 variables are there? What is the minimum number of 2-input NAND gates needed to build an XOR gate?

Answers

$A + \bar{A}B = A + B$, and $AB$ is already covered by $A$, so $F = A + B$. All four minterms have $C = 0$, so $F = \bar{C}$. $YZ$ is the consensus term, so $XY + \bar{X}Z$. $F = \bar{B}\,\bar{C} + \bar{B}\,\bar{D} + \bar{A}\,\bar{C}D$. The corners give $\bar{B}\bar{D}$, the quad 0, 1, 8, 9 gives $\bar{B}\bar{C}$, and minterm 5 pairs with 1 to give $\bar{A}\bar{C}D$. A truth table with 3 inputs has 8 rows, and each row can be 0 or 1, so there are $2^{2^3} = 256$ functions. Four.

If question 4 took you longer than two minutes, redraw Fig. 1 with those minterms and look for the corners first. Next time we'll put these skills to work on combinational circuits: adders, multiplexers and decoders. Tell me in the comments which question slowed you down.