Boolean algebra and Karnaugh maps
Boolean algebra
- Boolean algebra simplifies logic expressions — fewer terms means fewer gates in the circuit.
- It uses
+for OR,·for AND, and an overbar for NOT. - A Karnaugh map does the same job visually.
The laws
- Identity: $A + 0 = A$, $A \cdot 1 = A$. Null: $A + 1 = 1$, $A \cdot 0 = 0$.
- Idempotent: $A + A = A$. Inverse: $A + \overline{A} = 1$, $A \cdot \overline{A} = 0$.
- De Morgan's laws: $\overline{A + B} = \overline{A} \cdot \overline{B}$ and $\overline{A \cdot B} = \overline{A} + \overline{B}$ (negate the whole, swap AND/OR, negate each).
- Absorption: $A + A\cdot B = A$.
Practice
By De Morgan's law, $\overline{A \cdot B}$ equals:
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Practice
The absorption law states that $A + A\cdot B$ simplifies to:
If A is 1 the whole is 1; if A is 0 the whole is 0 — so it depends only on A: $A + AB = A$.
Simplifying
- Apply the laws to cut the number of terms. Example:
$$Z = A\cdot B + A\cdot\overline{B} = A\cdot(B + \overline{B}) = A\cdot 1 = A$$
- The simpler expression needs fewer gates, so the circuit is cheaper and faster.
Practice
Simplify $A\cdot B + A\cdot\overline{B}$.
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$.
Karnaugh maps
- A Karnaugh map simplifies an expression by grouping adjacent 1s from a truth table.
- Rows/columns use Gray code order (
00, 01, 11, 10) so adjacent cells differ in one variable. - Make rectangular groups of 1s of size 1, 2, 4, 8 (wrapping at edges). The larger the group, the simpler the term — a group of 2 drops one variable, a group of 4 drops two.
- Cover every 1 with as few, as large, groups as possible.
Practice
A Karnaugh map simplifies a Boolean expression by:
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term.
Practice
In a Karnaugh map, a larger group of 1s gives:
A group of 2 drops one variable, a group of 4 drops two — so bigger groups mean simpler terms.
You've got it
Key idea
- Boolean algebra cuts terms → fewer gates
- De Morgan: $\overline{A \cdot B} = \overline{A} + \overline{B}$; absorption: $A + AB = A$
- $A\cdot B + A\cdot\overline{B} = A$
- a Karnaugh map groups adjacent 1s (Gray-code order); bigger groups = simpler terms