Boolean algebra and Karnaugh maps: the method

End of September 2026: in the first year of computer engineering or electronics and computer science, the Logic Networks course (sometimes inside Computer Architecture or Fundamentals of Computer Science) opened the year with Boolean algebra and is moving into Karnaugh maps — after the semester start in mid-September, at the Politecnico di Milano on 14 September 2026. Where a mid-term test (the Italian prova in itinere) is scheduled, it typically falls at the end of October or the start of November — at the Politecnico from 29 October to 2 November 2026, about five weeks from now — and it is almost always the stumbling block on which combinational logic stakes half the grade. The same topic, with a more applied angle, is also met in Year 3 of technical institutes (Electronics, Computer Science, Mechanics), inside Systems and Electronics.

The typical problem is not understanding what AND, OR and NOT are — that is immediate. It is that between the truth table, the algebraic form and the Karnaugh map there are three different representations of the same function, and moving from one to another without a fixed method almost always leads to a trivial mistake: a wrong grouping, a bit order not respected, an adjacency on the edges forgotten.

Logic gates and truth tables

The fundamental logic gates operate on Boolean variables (0 or 1) and return a Boolean value. The truth tables below are the basic tool for defining them, with $A$ and $B$ as input variables:

And the single-input or negated gates:

NAND and NOR are AND and OR with the output negated, but they deserve separate attention because they are functionally complete: with the NAND gate alone (or the NOR alone) you can build any Boolean function, including AND, OR and NOT themselves — hence the recurring request in tests: “implement the function using only NAND gates”.

Axioms and theorems you really need

Besides the elementary properties (commutative, associative, distributive — identical to those of ordinary algebra, with $\cdot$ in place of “and” and $+$ in place of “or”), three results come back continually in algebraic simplification:

De Morgan’s theorems, the most used of all:

In words: the negation of an AND is the OR of the negations, and vice versa. It is the law that allows any expression to be converted into a form that can be implemented with NAND gates only or NOR gates only.

Absorption law:

Useful for eliminating redundant terms in an expression already written, even before drawing a map.

Consensus theorem (or redundancy theorem): if an expression contains the terms $A\cdot B$, $\overline{A}\cdot C$ and $B\cdot C$, the last is always redundant and can be eliminated:

This theorem explains why sometimes an expression “looks” already minimal but in reality still contains a term that can be eliminated — and it is one of the reasons why it is always worth going through the Karnaugh map rather than trusting only algebraic manipulation by hand.

From the truth table to canonical forms

Every Boolean function can be written in two equivalent canonical forms, both derivable mechanically from the truth table:

SOP form (Sum of Products): you take all the rows where the function equals 1, write for each the minterm (the product of all the variables, negated if they are 0 in that row) and add up all the minterms.

POS form (Product of Sums): you take all the rows where the function equals 0, write for each the maxterm (the sum of all the variables, negated if they are 1 in that row) and multiply all the maxterms.

Example with two variables: if $F=1$ only when $A=0,B=1$ and when $A=1,B=1$, the SOP form is

The two forms are always equivalent (they represent the same function), but almost always one of the two leads to a simpler circuit than the other depending on how many rows are 1 compared with how many are 0 — another reason to check both before choosing how to implement.

Karnaugh maps: the method

The Karnaugh map is a truth table rearranged into a grid, where adjacent cells differ in a single variable. To obtain this property, the row and column headings do not follow the normal binary order (00, 01, 10, 11) but the Gray code:

This is the point that generates the most mistakes: using binary order instead of Gray breaks the adjacency property that makes the map useful, and leads to incorrect groupings.

2-variable map

3-variable map ($A$, $B$, $C$)

4-variable map ($A$, $B$, $C$, $D$)

The grouping rules

1. Each group must contain a power of 2 of cells with 1: 1, 2, 4, 8, 16 — never 3, 6 or other numbers.
2. A group may also extend across opposite edges of the map: the first and last columns are adjacent to each other, as are the first and last rows (and the four corners of a 4-variable map are all adjacent to each other).
3. Groups must be made as large as possible: a group of 4 eliminates more variables than two groups of 2 covering the same cells.
4. The cover must be minimal: each cell with 1 must be covered by at least one group, but a group that covers only cells already covered by other, larger groups is redundant and must be removed.
5. From each group you read a product term: the variables that do not change within the group appear in the term (negated if they are 0), those that change disappear.

Don’t-care conditions

In many real problems some input combinations never occur — in BCD (Binary-Coded Decimal) coding the combinations from 1010 to 1111 do not represent any valid decimal digit. These cells are marked with an X (“don’t care”) in the map and can be treated as 0 or as 1, depending on what is convenient for the largest possible grouping: a margin of freedom that often simplifies the final function. Only the X cells actually grouped count as 1; an X left out of every group remains meaningless.

Implementation with NAND gates only

Once the minimal SOP form is obtained, to implement it with NAND gates only you negate the whole expression twice (a double negation changes nothing) and distribute the inner negation with De Morgan, turning every AND and OR into a combination of NANDs. The practical result taught almost everywhere: every AND gate becomes a NAND followed by an inverter, and every OR gate with negated inputs becomes directly a NAND. You do not need to redo the proof each time: once the principle is understood, the conversion is mechanical.

The three worked exercises

Exercise 1 — algebraic simplification with De Morgan

Simplify the expression:

I apply De Morgan to the first term:

So:

I factor out $A$:

Check by cases: if $A=0$, $F=0$ for both combinations of $B$ (you can check by substituting directly into the starting expression); if $A=1$, $F=1$ for both. Consistent with $F=A$.

Exercise 2 — 3-variable Karnaugh map

Given the function with minterms $F(A,B,C)=\sum (0,1,2,3,6)$ (that is, $F=1$ for those minterms, 0 elsewhere), find the minimal form.

Map (rows $A$, columns $BC$ in Gray order 00-01-11-10):

Groupings: the whole row $A=0$ forms a group of 4, where $A$ stays 0 and $B$, $C$ both change → term $\overline{A}$. The cell $m_6$ ($A=1,B=1,C=0$) seems isolated, but it is adjacent to $m_2$ ($A=0$, $BC=10$), which is in the same column: a vertical group of 2 in which only $A$ changes and $B=1$, $C=0$ stay fixed → term $B\cdot \overline{C}$. The fact that $m_2$ is already covered by the first group does not matter: a cell can be in several groups, and using it here makes a literal disappear.

If I had left $m_6$ alone you would have written $F=\overline{A}+AB\overline{C}$: correct, but with one literal too many. It is the same result that algebra gives, because $\overline{A}+AX=\overline{A}+X$.

Check on $m_6$ ($A=1,B=1,C=0$): $B\overline{C}=1$ → $F=1$. Correct. On $m_4$ ($A=1,B=0,C=0$, must give 0): $\overline{A}=0$, $B\overline{C}=0$ → $F=0$. Correct. On $m_7$ ($A=1,B=1,C=1$, must give 0): $\overline{A}=0$, $B\overline{C}=0$ → $F=0$. Correct.

Exercise 3 — 4-variable map with don’t cares (BCD)

A circuit must switch on a signal $F$ when the 4-bit input $ABCD$ (BCD coding) represents a digit greater than or equal to 5. The combinations from 1010 to 1111 (10-15) never occur: they are don’t cares.

$F=1$ for $5,6,7,8,9$ (minterms $m_5,m_6,m_7,m_8,m_9$); don’t care for $10$–$15$ ($m_{10}$–$m_{15}$); $F=0$ for $0,1,2,3,4$.

Map (rows $AB$, columns $CD$, both in Gray order):

Here the don’t cares make the difference: you use them as 1 whenever they let you enlarge a group, and ignore them when they are not needed. Three groups cover all the 1s:

• Group 1 — of 8: the two whole rows $AB=11$ and $AB=10$ (four X plus $m_8$, $m_9$ and the X $m_{10}$, $m_{11}$). In those rows $A=1$ is fixed and $B$, $C$, $D$ all change → term $A$.
• Group 2 — of 4: rows $AB=01,11$, columns $CD=01,11$: $m_5,m_7,m_{13},m_{15}$. Fixed $B=1$ and $D=1$ → term $B\cdot D$.
• Group 3 — of 4: rows $AB=01,11$, columns $CD=11,10$: $m_7,m_6,m_{15},m_{14}$. Fixed $B=1$ and $C=1$ → term $B\cdot C$.

Without exploiting the X cells all the way you easily arrive at $F=BD+A\overline{C}+BC\overline{D}$: it is a correct function (it gives the same values on all digits from 0 to 9), but it is not minimal — three extra literals and a three-input gate. In a test it is worth fewer marks, and it is the typical mistake of someone who draws the groups starting from the 1s without asking whether an X would make them grow.

Check on $m_9$ ($1001$: $A=1$) → $F=1$. Correct. On $m_4$ ($0100$: $A=0,B=1,C=0,D=0$): $B\cdot D=0$, $B\cdot C=0$ → $F=0$. Correct. On $m_6$ ($0110$): $B\cdot C=1$ → $F=1$. Correct.

The mistakes that cost marks

• Binary order instead of Gray on the map headings: it breaks adjacency and leads to groupings that look valid but are not.
• Groups of 3 or 6: only powers of 2 (1, 2, 4, 8…) are valid groupings.
• Forgetting adjacency across the edges and corners: the map “closes into a ring” in every dimension, and many students treat the edges as limits rather than as boundaries that touch.
• Redundant groups: a small group whose cells are all already covered by larger groups must be removed, otherwise the form is not minimal.
• Treating an ungrouped X as if it counted as 1 anyway: only the X cells actually included in a group contribute to the final function.

Where it leads next

Boolean algebra and Karnaugh maps are the foundation of combinational logic: the typical next step in the syllabus is sequential logic (flip-flops, registers, counters), which is built precisely on top of the combinational circuits simplified here. If you need to review first the representation of the numbers these circuits really work with — signed integers, floating point — the step-by-step method is in two’s complement and floating point, while for the wider picture of how these blocks fit into the CPU the reference is Von Neumann architecture and the CPU.

How I work on this topic in lessons

With my students the first rule I set is: never go directly from the algebraic expression to simplification by eye. You first write the truth table or identify the minterms, then you always draw the map with the Gray order written explicitly at the head of rows and columns — it is one second that avoids the most common mistake of all. There is no dedicated practice test for Logic Networks on the site yet: if you want to train in the meantime on other university subjects you will find the category in university practice tests.

If you need the high-school version, with logic gates in Year 3 of the technical school, I have written it in logic gates and Karnaugh maps.

For the overview of the computer science subjects I teach there is the computer science page, and for university support in general the one on university tutoring. If Karnaugh maps remain a weak point after trying this method, write to me through contact: the first introductory call is free and lasts half an hour.