1. From problem statement to truth table
The input is a number N = ABCD between 0 and 15 (A is the most significant bit) and the output F is 1 if N is prime. The primes in that range are 2, 3, 5, 7, 11 and 13, so the function is written as a sum of minterms:
F(A,B,C,D) = Σm(2, 3, 5, 7, 11, 13)
| N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ABCD | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| F | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Written as is, as a sum of the six minterms, the function needs six 4-input AND gates and one 6-input OR. Simplifying means finding an equivalent expression with fewer terms and fewer literals.
2. From map to groups
On the map, rows are AB and columns are CD, in Gray order (00, 01, 11, 10): between two neighbouring cells only one bit changes, even from one edge to the opposite one. Each rectangular group of 2, 4 or 8 ones removes the variables that change inside the group.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 00 | 01 | 13 | 12 |
| 01 | 04 | 15 | 17 | 06 |
| 11 | 012 | 113 | 015 | 014 |
| 10 | 08 | 09 | 111 | 010 |
- m2 can only be grouped with m3:
A'B'C. - m11 only with m3 (same column, rows 00 and 10, which touch across the edge):
B'CD. - m13 only with m5:
BC'D. - m7 can go with m3 (A'CD) or with m5 (A'BD). Both options are equally good.
F = A'B'C + B'CD + BC'D + A'CD
Four terms of 3 literals. The first three are essential prime implicants (they cover a 1 that no other group covers); the fourth is chosen between two candidates. The minimizer reaches the same expression.
3. Don’t cares change the result
Now suppose the input is a BCD digit: values 10 to 15 never occur. Those combinations are don’t cares (X): we can treat them as 1 whenever it helps to enlarge groups. 11 and 13 stop mattering and the function becomes Σm(2, 3, 5, 7) + d(10…15):
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 00 | 01 | 13 | 12 |
| 01 | 04 | 15 | 17 | 06 |
| 11 | X12 | X13 | X15 | X14 |
| 10 | 08 | 09 | X11 | X10 |
F = B'C + BD
From four 3-literal terms to two 2-literal terms. Check it in the tool.
4. From expression to circuit
A sum of products is implemented in two levels: one AND gate per term and an OR joining them (or, equivalently, two levels of NAND). Counting terms and literals means counting gates and inputs:
| Version | AND gates | OR | Literals |
|---|---|---|---|
| Minterms (0–15) | 6 × 4 inputs | 1 × 6 | 24 |
| Minimized (0–15) | 4 × 3 | 1 × 4 | 12 |
| Minimized (BCD) | 2 × 2 | 1 × 2 | 4 |
The minimizer draws this AND-OR circuit below the result and, if you define several outputs, marks the products they share.
Suggested path
- Guide: how Karnaugh maps work — Gray order, adjacency, prime implicants and cases with several solutions.
- Exercises: placing minterms, adjacency, minimizing with don’t cares and checking a solution.
- Guide: BCD to 7-segment decoder, a complete design with seven outputs.