Boolean algebra and Karnaugh maps
Introduced| English | Meaning |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | A mathematical system for combining and manipulating true-or-false values using logical operations. |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | Rules stating that negating an AND gives the OR of the negated operands, and negating an OR gives the AND of the negated operands. |
| Karnaugh map/ˈkɑːnɔː mæp/ | Karnaugh map |
| truth table/truːθ ˈteɪbl/ | A table listing the output of a logical expression or circuit for every combination of inputs. |
| absorption/əbˈsɔːpʃn/ | A Boolean simplification law in which combining a value with a term already containing it leaves the value unchanged, such as A OR (A AND B) equalling A. |
| Gray code/ɡreɪ kəʊd/ | A binary coding scheme in which neighbouring values differ in exactly one bit. |
The master's thesis that built the digital age
- In 1937 a 21-year-old student named Claude Shannon noticed that the telephone relays he was studying were doing the same thing as an algebra George Boole had invented eighty years earlier for reasoning about true and false.
- If a switch is a Boolean variable, then a circuit is an expression, and simplifying the expression removes gates from the circuit. Fewer gates is cheaper, faster and less power.
- His thesis has been called the most important of the century. Everything on this page is that one idea used as a tool.
- This lesson is Boolean algebra 布尔代数, De Morgan's laws, and the Karnaugh map 卡诺图 that does the same job by eye.
The notation and the laws
+means OR,·means AND and is often left out, and an overbar means NOT. A truth table 真值表 describes the same thing exhaustively.- Identity: $A + 0 = A$ and $A \cdot 1 = A$. Null: $A + 1 = 1$ and $A \cdot 0 = 0$.
- Idempotent: $A + A = A$. Inverse: $A + \overline{A} = 1$ and $A \cdot \overline{A} = 0$.
- Absorption 吸收律: $A + A\cdot B = A$, because if $A$ is true the whole expression is true regardless of $B$.
Match each Boolean law to what it says.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
These laws let you simplify Boolean expressions algebraically before building the circuit.
By the absorption law, A + A·B simplifies to ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
If A is true the whole expression is true whatever B is, and if A is false both terms are false. B cannot affect the result.
De Morgan's laws
- De Morgan's laws 德摩根定律 are the two the exam asks you to use by name:
- The recipe in words: negate the whole, swap AND and OR, negate each operand.
- They matter practically because they let any expression be rewritten using only NAND gates or only NOR gates, and a chip built from one repeated gate is cheaper to manufacture.
Two expressions, one truth table
Boolean algebra
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables.
By De Morgan's law, $\overline{A \cdot B}$ equals:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Applying De Morgan's law to an expression involves which steps? Select all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative.
Worked example: simplify, and count the gates
- Simplify $Z = A\cdot B + A\cdot\overline{B}$ and say what it saves.
- Factor out $A$: $Z = A\cdot(B + \overline{B})$. By the inverse law $B + \overline{B} = 1$, so $Z = A \cdot 1 = A$.
- The original needs two AND gates, a NOT and an OR: four gates. The simplified expression needs none, just the input $A$.
- Always finish with what the simplification buys: fewer gates, so a cheaper, faster circuit that uses less power.
Simplify $A\cdot B + A\cdot\overline{B}$.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B needs two ANDs, one NOT and one OR. How many gates does its simplified form need?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved.
The Karnaugh map
- A Karnaugh map simplifies an expression by grouping adjacent 1s taken from the truth table.
- Rows and columns are labelled in Gray code 格雷码 order,
00, 01, 11, 10, so that adjacent cells differ in exactly one variable. That is the whole trick: it makes the algebra visible as adjacency. - Place a 1 in each cell where the output is 1, then find rectangular groups of 1s whose sides are powers of two: 1, 2, 4, 8. Groups may wrap around the edges.
The bigger the rectangle, the simpler the term
A Karnaugh map simplifies a Boolean expression by:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work.
Reading a group
- Inside a group, a variable that stays the same survives in the term; a variable that changes disappears.
- So a group of 2 drops one variable, a group of 4 drops two, and a group of 8 drops three. The larger the group, the simpler the term.
- Cover every 1 using as few and as large groups as possible, then OR the group terms together. Groups may overlap, and overlapping is often what allows a larger one.
In a Karnaugh map, a larger group of adjacent 1s eliminates more variables, giving a simpler term (a group of 2 drops one variable, a group of 4 drops two).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes.
Put the steps of simplifying with a Karnaugh map in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 1.
Worked example: read a two-variable map
- A Karnaugh map for $A$ and $B$ has 1s in the cells $\overline{A}B$ and $AB$. Simplify.
- The two 1s are adjacent: they share the $B = 1$ column, so they group as a rectangle of 2.
- Inside that group $B$ stays 1 throughout, while $A$ changes from 0 to 1. The variable that changes disappears.
- So the whole expression is simply $Z = B$. Compare that with the unsimplified sum of products, $\overline{A}B + AB$, which needs a NOT, two ANDs and an OR.
Which method to use
- Boolean algebra is exact and works for any number of variables, but you must spot which law applies.
- A Karnaugh map is mechanical and hard to get wrong for two to four variables, which is what the exam sets, and it shows you the largest grouping directly.
- Both give the same answer. The benefit of the K-map is that simplification becomes looking, not searching for a law.
Marks that slip away
- De Morgan is negate the whole, swap the operator, negate each part. Changing only the operator is the classic half-answer.
- K-map rows must be in Gray code order,
00, 01, 11, 10. In binary counting order the adjacency is wrong and the grouping fails. - Group sizes are powers of two and may wrap the edges. A group of three is not a group.
- Say what simplifying is for: fewer gates, so cheaper, faster, lower power.
You've got it
- Boolean algebra rewrites an expression into fewer terms, so the circuit needs fewer gates
- De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ and $\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 from the truth table, with rows and columns in Gray code order so neighbours differ in one variable
- a variable that changes within a group disappears, so bigger groups give simpler terms: cover every 1 with as few, as large, groups as possible