Logic gates and Karnaugh maps: worked exercises

End of September 2026, Year 3 of the technical school: in the Computer Science and Telecommunications track as well as in the mechanical and electrotechnical tracks, the first term brings combinational logic: AND/OR/NOT gates, truth tables, and the part that really makes the difference in a test, Karnaugh maps. In Systems/Electronics it arrives together with Boolean algebra; in Mechanics it sits inside the electrotechnics module and is a prerequisite for pneumatics. In both cases the module is taught between October and November, and the first test typically falls between six and nine weeks from now, so between the end of November and December.

The problem almost everyone has is not understanding what an AND gate does: it is getting from a truth table, or from a statement in words, to a simplified circuit, without getting a sign wrong or forgetting an adjacency across the edges of the map. Here you find the complete method, step by step, with three worked and checked exercises.

The basic logic gates

A logic gate takes one or more bits (0 or 1) as input and returns one bit as output, following a fixed rule. The six gates you need in Year 3:

NAND and NOR are called “universal” gates: with NAND gates alone (or NOR gates alone) you can build any other gate, including NOT (just connect the two inputs of a NAND to the same signal). In a test it is usually enough to be able to say this; you do not need to prove it.

Boolean algebra: the properties you use to simplify by hand

Before getting to Karnaugh maps, some properties are also used to simplify an expression “by eye”:

• Identity: $A+0=A$, $A\cdot 1=A$.
• Domination: $A+1=1$, $A\cdot 0=0$.
• Idempotence: $A+A=A$, $A\cdot A=A$.
• Complement: $A+\overline{A}=1$, $A\cdot \overline{A}=0$.
• Distributive law: $A\cdot (B+C)=A\cdot B+A\cdot C$.
• Absorption: $A+A\cdot B=A$.

The two that appear most often in tests are De Morgan’s theorems:

In words: the negation of an AND is the OR of the negations, and vice versa. They are used to rewrite an expression with NAND/NOR when the final circuit must use only that type of gate, and to “bring inside” a negation that sits over a whole expression in brackets.

From the truth table to the sum of products (minterms)

A logic function can always be written as a sum of products (SOP). For every row of the truth table where the output is 1, you write the product (AND) of all the variables, not negated if it is 1 in that row and negated if it is 0, then you add (OR) all these products. Each product obtained this way is called a minterm.

Example: if $F(A,B,C)=1$ for the rows $ABC=001$ and $ABC=110$, the two minterms are $\overline{A}\overline{B}C$ and $AB\overline{C}$, and $F=\overline{A}\overline{B}C+AB\overline{C}$. This form is always correct but almost never the simplest: it is the starting point, not the arrival. Karnaugh maps are used exactly to reduce it to the minimum number of gates.

Karnaugh maps: how they are built

A Karnaugh map is a truth table reorganised in a grid, so that two adjacent cells differ in only one variable. This is achieved by ordering rows and columns not in normal binary order but in Gray code (00, 01, 11, 10): at each step only one bit changes.

• 2 variables: one row for A (0, 1), one column for B (0, 1): 4 cells.
• 3 variables: rows AB in Gray order (00, 01, 11, 10), column C (0, 1): 8 cells.
• 4 variables: rows AB in Gray order, columns CD in Gray order: 16 cells.

Each cell corresponds to a row of the truth table: you write 1 in it if the function is 1 for that combination, 0 otherwise (or “X” for a don’t care, a combination that never occurs in practice and that you can treat as 0 or as 1, whichever helps you simplify more).

How to group

Once the map is filled in, you look for rectangular groups of adjacent 1s, whose size is a power of two: 1, 2, 4, 8, 16 cells. Rules:

1. Every group must contain only 1s (or don’t cares used as 1), never a 0.
2. The largest possible groups win: a group of 4 eliminates more variables than two groups of 2 covering the same cells.
3. Adjacency also holds across the edges: the last column is adjacent to the first, the last row is adjacent to the first. The map must be thought of as if it “rolled up” on itself, both horizontally and vertically. This is the most common mistake: stopping at the edges of the sheet as if they were the edges of the map.
4. Every group produces a term (product) in the final expression: the variables that change value inside the group disappear, and only those that stay constant remain (written not negated if constant at 1, negated if constant at 0).
5. The simplified function is the sum (OR) of all the terms of the chosen groups, covering all the 1s of the map with the fewest possible groups.

Exercise 1: simplification with 3 variables

$F(A,B,C)$ is 1 for minterms 1, 3, 5, 7 (that is, $ABC=001,011,101,111$).

The column $C=1$ is all 1s: it is a group of 4 cells (the whole column). Inside this group A and B change freely from row to row, so both disappear; only C remains, which is always 1 in the group.

From a statement with three variables, the final circuit is a single wire: no gate is needed, because the output always coincides with the input C. It rarely appears in a test in this clean form, but it is the clearest example to see the mechanism before complicating it.

Exercise 2: 4 variables, with adjacency across the edges

$F(A,B,C,D)$ is 1 for minterms 0, 1, 2, 3, 8, 9, 10, 11.

The rows $AB=00$ and $AB=10$ are both all 1s. They are the first and the last row of the map: they are not adjacent on the sheet, but they are by the edge rule (the last row “rolls up” onto the first). Together they form a group of 8 cells, the whole pair of rows. Inside this group A changes (0 in the first row, 1 in the second), and C and D change freely along the whole row: all three disappear. The only variable that is constant in the group is B, always 0.

Whoever does not think of the map as a torus sees here only two separate groups of 4 (the two rows taken one by one) and stops at $F=\overline{A}\overline{B}+A\overline{B}$: this is a correct expression but not a minimal one, although by the distributive law it reduces anyway to $\overline{B}(\overline{A}+A)=\overline{B}$. Seeing it directly as a single group of 8 on the map saves the extra step.

Exercise 3: a word problem, a majority alarm

A security system has three sensors A, B, C. The alarm must go off if at least two sensors out of three detect an anomaly (1 = anomaly detected). Design the logic function of the alarm F and simplify it.

First you write the truth table, counting how many inputs are 1 in each row: F is 1 when the sum A+B+C is at least 2, that is for $ABC=011,101,110,111$ (minterms 3, 5, 6, 7).

Here there is no single large group: there are three overlapping groups of 2 cells, each one compulsory because no larger group is possible without including a 0.

• $AB=11$ (both cells, C free) → $A\cdot B$
• $AB=01$ and $AB=11$ with $C=1$ (right-hand column, rows 01 and 11 adjacent) → $B\cdot C$
• $AB=11$ and $AB=10$ with $C=1$ (right-hand column, rows 11 and 10 adjacent) → $A\cdot C$

The final circuit has three AND gates (one for each pair of sensors) and a three-input OR gate that adds them up: whenever at least two sensors detect an anomaly, at least one of the AND gates switches on, and that is enough to set off the alarm. This is exactly the “majority of 3” rule that was asked for.

Typical mistakes

• Ignoring adjacency across the edges (exercise 2 above): it almost always leads to an expression that is correct but not minimal.
• Getting the polarity of the variables wrong: writing a minterm with the variable plain instead of negated (or the other way round) because a row was read in a hurry.
• Making groups that are not powers of two (3, 5, 6 cells): they are not allowed, and must always be split into groups of 1, 2, 4, 8…
• Not taking the largest possible group: using two groups of 2 where a single group of 4 would cover the same cells produces a valid expression but with one term too many.
• Confusing AND and OR in the final reading: the groups are added (OR) to each other, but inside each group the constant variables are multiplied (AND).

Cross-check: how to verify the result yourself

Before handing in, the most reliable way to check a simplification is to rebuild the truth table of the simplified function and compare it, row by row, with the starting one: they must coincide exactly, in every row. It is not enough that it “looks right”: a single different bit in a single row means a badly chosen group. It is the same check I used to verify the three exercises above before writing them.

If you need the university version, with more variables and more examples, you will find it in Karnaugh maps and Boolean algebra.

There is not yet a dedicated practice test on this topic: you can find the practice tests for school for maths and physics, but not yet for computer science. If you want to revise the basics before getting here, the starting point is binary and hexadecimal in Year 1 of the technical school; the next step in the Year 3 programme is two’s complement and floating point, and the gates you study here are the same building blocks from which the CPU described in Von Neumann architecture and the CPU is built. The full picture of the subject is on computer science. If you want a hand with the combinational logic test, start with a free introductory call.