Home
4Universal Gates & Karnaugh Maps
4

Topic 4 of 13

Universal Gates & Karnaugh Maps

Build anything from NAND or NOR, then simplify functions visually with Karnaugh maps.

StartAll topics

← → move between slides · F full screen · M slide list

Before we start

Why this matters

What if your phone, a calculator, and a Mars rover could all be built from just ONE type of Lego brick, repeated a trillion times?

That brick is called a universal gate, and engineers really do build entire computers from it — partly out of elegance, mostly out of stubbornness and cost-cutting. The catch: building everything from one brick makes a glorious mess, which is exactly what a Karnaugh map is for, tidying that mess into the smallest circuit that still works.

Outline

Topics in this chapter

Select a topic to jump to the slide that explains it.

  1. NAND/NOR as universal gates
  2. NAND/NOR implementation
  3. AOI vs. NAND/NOR implementation
  4. AOI-to-NAND worked conversion
  5. 2-, 3-, and 4-variable K-maps
  6. Gray-code ordering
  7. K-map grouping
  8. Wrap-around adjacency
  9. SOP/POS simplification
  10. Prime and essential prime implicants
  11. Don't-care conditions
  12. K-map → Boolean expression → circuit

Concept 1 of 4

Universal gates

A universal gate can build any Boolean function alone. NAND and NOR are universal, and they are cheap and easy to fabricate, so real chips use them heavily.

  • NAND: NOT = tie the inputs together. AND = NAND followed by that NOT. OR = A+B = (A′B′)′, a NAND of inverted inputs.
  • NOR: NOT = tie the inputs together. OR = NOR followed by NOT. AND = AB = (A′+B′)′, a NOR of inverted inputs.

An AND-OR-INVERT (AOI) circuit for a sum of products becomes NAND-NAND: F = AB + CD = ((AB)′(CD)′)′. Using one gate type reduces the number of different ICs you need.

Explore furtherInside the ComputerNAND gateInside the ComputerNOR gateInside the Computer74LS00 chip (NAND)Gate ForgeY = AB + AC from NANDProblems › Universal Gates

Interactive circuit

NOT from one NAND gate

Tie both inputs of a NAND gate to the same signal: (AA)′ = A′. Click the switch to change the input and watch the LED. Use “Show truth table” when it appears.

Explore furtherGate ForgeNOT from NANDProblems › Universal Gates

Interactive circuit

AND from two NAND gates

Click the switches to change the inputs and watch the LEDs. Use “Show truth table” when it appears.

Explore furtherGate ForgeAND from NANDProblems › Universal Gates

Interactive circuit

OR from three NAND gates

Click the switches to change the inputs and watch the LEDs. Use “Show truth table” when it appears.

Explore furtherGate ForgeOR from NANDProblems › Universal Gates

Interactive circuit

NOT from one NOR gate

Tie both inputs of a NOR gate to the same signal: (A+A)′ = A′. Click the switch to change the input and watch the LED. Use “Show truth table” when it appears.

Explore furtherGate ForgeNOT from NORProblems › Universal Gates

Interactive circuit

OR from two NOR gates

Click the switches to change the inputs and watch the LEDs. Use “Show truth table” when it appears.

Explore furtherGate ForgeOR from NORProblems › Universal Gates

Interactive circuit

AND from three NOR gates

Click the switches to change the inputs and watch the LEDs. Use “Show truth table” when it appears.

Explore furtherGate ForgeAND from NORProblems › Universal Gates

Concept 2 of 4

Karnaugh maps

A K-map is a truth table rearranged so that neighbouring cells differ in exactly one variable. Rows and columns are labelled in Gray-code order (00, 01, 11, 10), not binary order. A 2-variable map has 4 cells, 3 variables 8, and 4 variables 16. Each cell is one minterm.

Explore furtherGate ForgeKarnaugh Map Practice (3 Variables, with a Don’t-Care)Problems › Boolean Expressions

Concept 3 of 4

Grouping rules

  • Groups contain 1, 2, 4, 8 or 16 cells (a power of 2) and are rectangular.
  • No diagonals, and never include a cell of the wrong value.
  • Make each group as large as possible and use as few groups as possible.
  • Groups may overlap.
  • Groups may wrap around: left and right edges are neighbours, top and bottom too, so the four corners form a valid group.

In each group, variables that change value are eliminated. To get SOP, group the 1s and write a product term per group. To get POS, group the 0s and write a sum term per group using the complemented literals.

Concept 4 of 4

Prime implicants and don’t-cares

A prime implicant is a group that cannot grow any larger. An essential prime implicant covers at least one 1 that no other prime implicant covers, so it must appear in the answer. Pick all essential groups first, then cover any remaining 1s with as few extra groups as possible.

A don’t-care (X or d) is an input combination that never occurs or whose output does not matter. Treat it as 1 when that enlarges a group, otherwise ignore it. Never form a group made only of X cells.

K-map ordering of two variables

Row / column labelBinary value
000
011
113
102

Gray order: neighbours differ in exactly one bit.

Explore furtherGate ForgeKarnaugh Map Practice: BCD Odd-Digit DetectorProblems › Boolean Expressions

Interactive

Demo: interactive K-map

Worked example 1 of 3

Worked example 1

An AOI (AND-OR-Invert) circuit implements F = BC′ + AC using one inverter, two AND gates and one OR gate. Redesign it using only NAND gates.
Show the solution
  1. Start from the AOI circuit: C feeds an inverter to get C′; AND gate 1 makes BC′; AND gate 2 makes AC; the OR gate adds them to give F = BC′ + AC.
  2. Replace every AND, OR and inverter with its NAND equivalent: each AND becomes NAND+NAND-as-inverter, the inverter on C becomes a NAND with its inputs tied together, and the OR becomes a NAND fed by two NAND-inverters.
  3. Redraw: this leaves two back-to-back NAND pairs (one per product term) feeding a final NAND.
  4. Eliminate the double inversions — a NAND used only to re-invert the output of the previous NAND cancels out, since (X′)′ = X.
  5. What remains is exactly one NAND gate per product term — NAND(B, C′) and NAND(A, C) — feeding a third NAND gate.
  6. Check algebraically: the final gate outputs ((BC′)′ · (AC)′)′ = BC′ + AC = F by De Morgan’s theorem, so the circuit is equivalent.
Result F = BC′ + AC, built from NAND gates only (one NAND per product term plus a final NAND, all fed by a NAND wired as the C-inverter). The same five-step process works with NOR gates for a product-of-sums expression, replacing the final NAND with a NAND-of-NORs pattern that also collapses to one gate per sum term.
AOI circuit (F = BC′ + AC)All-NAND circuit (same F)CC′BBC′AACFCC′C′B(BC′)′A(AC)′F
Left: the original AOI circuit (one inverter, two AND gates, one OR gate). Right: the same function built entirely from NAND gates, following the five steps above — C′ now comes from a NAND with its own inputs tied together, and each product term collapses to a single NAND gate.

Worked example 2 of 3

Worked example 2

Simplify F(A,B,C,D) = Σm(1,3,7,11,15) + d(0,2,5).
Show the solution
  1. CD covers 3, 7, 11, 15 and is essential (only it covers 11).
  2. Cell 1 is still uncovered. A′B′ (0,1,2,3) or A′D (1,3,5,7) both cover it.
  3. Result F = CD + A′B′ (or CD + A′D). Both are minimal.

Worked example 3 of 3

Worked example 3

Simplify F(x,y,z) = Σm(2,3,4,5).
Show the solution
  1. Cells 2 and 3 (x′y) form a group. Cells 4 and 5 (xy′) form another.
  2. F = x′y + xy′, which is x ⊕ y.

Practice

Practice (1 of 2)

Try each one on paper first, then check your answer.

1. Build NOT, AND and OR using only NAND gates.
Show the answer
NOT: tie both inputs. AND: NAND then NOT. OR: NAND(A′, B′) where each input is first inverted by a NAND.
2. Build NOT, OR and AND using only NOR gates.
Show the answer
NOT: tie both inputs. OR: NOR then NOT. AND: NOR(A′, B′).
3. Simplify F(A,B,C) = Σm(0,1,2,5,6,7).
Show the answer
A′B′ + BC′ + AC (or A′C′ + B′C + AB). Both have three terms.

Practice

Practice (2 of 2)

Try each one on paper first, then check your answer.

4. Simplify F(A,B,C,D) = Σm(1,3,5,7,9) + d(11,13,15).
Show the answer
D. Every odd cell is 1 or X, so one group of eight covers them.
5. Simplify F(A,B,C,D) = Σm(0,1,2,4,5,6,8,9,12,13,14).
Show the answer
C′ + A′D′ + BD′
Practice in Gate Forge

Build NOT, AND and OR using only NAND gates, then again with only NOR gates, and compare with the truth table.

Open Gate ForgeGate ForgeA free circuit simulator — place and wire gates, generate truth tables and timing diagrams, and work through 90+ guided problems.

Check yourself

Quiz

Summary

Summary

  • NAND and NOR are universal. Tie inputs for NOT.
  • K-map order is Gray code: 00, 01, 11, 10.
  • Groups are 1, 2, 4, 8 or 16 cells, may overlap, and may wrap.
  • Take essential prime implicants first, then cover what is left.
  • Use don’t-cares only when they make a group larger.
Next topic: Combinational LogicAll topics