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.
