A circuit built straight from a truth table is often bigger than it needs to be. Simplifying the Boolean expression gives a circuit with fewer gates, which is cheaper, faster and uses less power. This lesson introduces the laws and a visual method, the Karnaugh map.

Boolean laws

Using . for AND, + for OR, and a ‘ to show NOT:

  • Identity: A + 0 = A, A . 1 = A
  • Null: A + 1 = 1, A . 0 = 0
  • Idempotent: A + A = A, A . A = A
  • Complement: A + A’ = 1, A . A’ = 0
  • Double negation: (A’)’ = A
  • Commutative: A + B = B + A, A . B = B . A
  • Associative: (A + B) + C = A + (B + C)
  • Distributive: A . (B + C) = A.B + A.C, and A + (B . C) = (A + B) . (A + C)
  • Absorption: A + A.B = A, A . (A + B) = A
  • De Morgan’s laws: (A . B)’ = A’ + B’, and (A + B)’ = A’ . B’

De Morgan’s laws are very useful: they swap AND and OR while inverting the inputs and output, which explains how NAND and NOR relate to the other gates.

Algebraic simplification example

Simplify Q = A.B + A.B'.

Q = A.B + A.B'
  = A.(B + B')     distributive
  = A.1            complement
  = A              identity

A circuit with a single wire replaces two AND gates, a NOT gate and an OR gate.

Another: Q = A + A'.B.

Q = (A + A').(A + B)   distributive
  = 1.(A + B)          complement
  = A + B              identity

Karnaugh maps

A Karnaugh map (K-map) is a grid showing the truth table so that neighbouring cells differ in only one input. Simplification becomes a matter of grouping 1s.

For two variables A and B:

        B=0  B=1
A=0      m0   m1
A=1      m2   m3

Rules for grouping:

  • Groups must be rectangles of 1s with sizes that are powers of two (1, 2, 4, 8).
  • Make groups as large as possible.
  • Groups may wrap around the edges (in 3 and 4 variable maps).
  • Every 1 must be in at least one group; groups may overlap.
  • For each group, keep only the variables that do not change across it.

Example: if the cells where A=1 (both B values) are 1, one group of two cells covers them and the variable B changes, so the result is just Q = A.

Why simplify?

Fewer gates mean lower cost, less heat, higher speed (fewer gate delays) and fewer places for faults.

Check your understanding

What does A + A’ equal?

  • 0
  • 1
  • A
  • A’

Answer: 1. A variable ORed with its complement is always true.

According to De Morgan’s law, (A . B)’ equals what?

  • A’ . B’
  • A’ + B’
  • A + B
  • A . B

Answer: A’ + B’. Invert each input and swap AND for OR.

Simplify A + A.B.

  • A
  • B
  • A.B
  • 1

Answer: A. This is the absorption law.

In a Karnaugh map, group sizes must be…

  • any whole number
  • powers of two
  • always 3
  • prime numbers

Answer: powers of two. Groups of 1, 2, 4 or 8 cells are valid.