Boolean Algebra, De Morgan's Laws and Karnaugh Maps
1. Why Simplify a Boolean Expression?
Every logic expression corresponds to a circuit of gates. A simpler expression means fewer gates, which means lower cost, less power, less heat and a faster circuit. Simplification is therefore an engineering task, not just an algebraic exercise.
2. The Laws of Boolean Algebra
| Law | AND form | OR form |
|---|---|---|
| Identity | A.1 = A | A+0 = A |
| Null / Annulment | A.0 = 0 | A+1 = 1 |
| Idempotent | A.A = A | A+A = A |
| Inverse / Complement | A.A' = 0 | A+A' = 1 |
| Commutative | A.B = B.A | A+B = B+A |
| Associative | (A.B).C = A.(B.C) | (A+B)+C = A+(B+C) |
| Distributive | A.(B+C) = A.B + A.C | A+(B.C) = (A+B).(A+C) |
| Absorption | A.(A+B) = A | A+(A.B) = A |
| Double negation | (A')' = A | |
3. De Morgan's Laws
(A.B)' = A' + B'
(A+B)' = A' . B'
How to apply them, in three steps:
- Change the operator — AND becomes OR, OR becomes AND.
- Invert each individual term.
- Remove the bar that spanned the whole expression.
Proving De Morgan with a truth table
| A | B | A.B | (A.B)' | A' | B' | A'+B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
The two bold columns are identical, which proves the law. Producing a truth table like this is a valid and often-requested way to demonstrate equivalence.
4. Worked Simplifications
Example 1
Simplify A.B + A.B'
| A.B + A.B' | Start |
| A.(B + B') | Distributive law — factor out A |
| A.1 | Inverse law: B + B' = 1 |
| A | Identity law |
Four gates reduce to a plain wire.
Example 2
Simplify (A + B).(A + B')
| A + (B.B') | Distributive law (OR form) |
| A + 0 | Inverse law |
| A | Identity law |
Example 3 — using De Morgan
Simplify (A' + B)'
| (A')' . B' | De Morgan: OR becomes AND, invert each term |
| A.B' | Double negation |
5. Karnaugh Maps
A Karnaugh map (K-map) simplifies an expression visually, avoiding long algebraic manipulation. It is a truth table redrawn so that adjacent cells differ by only one variable.
Worked example
Simplify A'.B + A.B using a two-variable K-map. Write a 1 in each cell where the expression is true:
| B = 0 | B = 1 | |
|---|---|---|
| A = 0 | 0 | 1 |
| A = 1 | 0 | 1 |
The two 1s form a group of 2. Within that group B is always 1, while A changes from 0 to 1. The variable that changes is eliminated, so the simplified expression is simply B.
Rules for grouping
- Group only 1s, never 0s
- Groups must contain 1, 2, 4, 8… cells — always a power of 2
- Groups must be rectangular: horizontal or vertical, never diagonal
- Make each group as large as possible — larger groups remove more variables
- Groups may overlap
- Groups may wrap around the edges of the map
- Every 1 must be in at least one group
- In each group, eliminate the variables that change and keep those that stay constant
A three-variable map
For three variables the map is 2 × 4, with the pair BC across the top in Gray code order:
| BC = 00 | BC = 01 | BC = 11 | BC = 10 | |
|---|---|---|---|---|
| A = 0 | 0 | 1 | 1 | 0 |
| A = 1 | 0 | 1 | 1 | 0 |
The group of four spans both values of A and both values of B, so both are eliminated. C is 1 throughout, giving C.
6. Exam Focus
Quick self-check
- State both of De Morgan's laws.
- Simplify A.B + A.B' + A'.B.
- Apply De Morgan to (A.B' + C)'.
- Why must K-map labels use Gray code?
- What size must a K-map group be, and why can a group of three never be valid?
- State two practical benefits of simplifying a logic circuit.