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. |
| 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. |
| De Morgan's theorem/də ˈmɔːɡənz ˈθɪərəm/ | Rules for inverting logic: NOT (A AND B) = (NOT A) OR (NOT B), and the same with AND and OR swapped. |
| Karnaugh map/ˈkɑːnɔː mæp/ | A grid of a truth table's outputs, arranged so that neighbouring 1s can be grouped to simplify logic. |
| don't-cares | don't-cares |
One bulb, two switches
- A hallway light can be switched from either end of the hall. Flip either switch and the light changes state.
- That wiring is a logic function of two inputs, and the electrician built it without writing any algebra. This lesson gives the algebra and a map that simplifies it.
Boolean algebra
- Boolean algebra 布尔代数 works on 0 and 1 with AND ($A \cdot B$), OR ($A + B$) and NOT ($A'$). Most laws match ordinary algebra: $A \cdot (B + C) = A \cdot B + A \cdot C$.
- New ones shorten expressions. $A + A = A$, $A + A' = 1$, and absorption 吸收律: $A + A \cdot B = A$, because whenever $A \cdot B$ is 1, $A$ already is.
Simplify A + A·B.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Absorption: whenever $A \cdot B$ is 1, $A$ is already 1, so the term adds nothing. Check the four rows of $A, B$ to confirm.
De Morgan: break the bar, change the sign
- De Morgan's theorem 德摩根定律 moves a NOT through a bracket: $(A \cdot B)' = A' + B'$ and $(A + B)' = A' \cdot B'$.
- It is how a NAND or NOR circuit is read. "Not both" is the same as "at least one is off".
The hallway light is the XOR: $F = A' \cdot B + A \cdot B'$. It is 1 exactly when the two switches differ, so flipping either one changes $F$.
Match each expression to its equal.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
De Morgan: break the bar and change the sign. A variable ORed with its complement is always 1; ANDed with it, always 0.
The Karnaugh map
- A Karnaugh map 卡诺图 lays out the truth table so that neighbouring cells differ in exactly one variable. The columns run 00, 01, 11, 10 (Gray-code order), and the edges wrap round.
- Circle 1s in rectangles of 1, 2, 4 or 8 cells. A group of $2^{k}$ cells removes $k$ variables: only the variables that stay constant across the group survive.
A K-map group of four cells keeps which variables?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
A variable that takes both values inside the group cannot tell the cells apart, so it drops out. The odd-row group keeps only C because A and B both change inside it.
In a four-variable K-map, a group of 8 cells leaves how many variables in its product term?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$8 = 2^{3}$ cells remove 3 of the 4 variables, leaving a single literal, for example $D$ alone.
Worked example: the odd rows
- $F = \sum m(1, 3, 5, 7)$ is 1 on the odd rows of a three-variable table: exactly the rows where $C = 1$.
- On the map the four cells form one group. $A$ and $B$ both change inside it, so they drop out and $F = C$. Check all 8 rows: it matches.
The Karnaugh group for Σm(1, 3, 5, 7) of A, B, C reads as —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The odd rows are exactly the C = 1 rows: one group of four that removes A and B. The 8-row check confirms F = C.
Don't-cares
- Some input combinations never happen, such as codes 10 to 15 on a decimal digit. Mark them as don't-cares 无关项 (X) on the map.
- An X may join a group to make it bigger, which removes more variables. Never circle Xs on their own: they need no output.
A group made only of don't-care cells should be added to the simplified expression.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Don't-cares need no output. They may join a group of 1s to enlarge it, but a group of Xs alone only adds gates.
Worked example: four-input majority
- $M$ is 1 when at least three of $A, B, C, D$ are 1: minterms 7, 11, 13, 14 and 15, the codes with three or four 1s.
- Overlapping groups of four give $M = A \cdot B \cdot (C + D) + C \cdot D \cdot (A + B)$. Checking all 16 rows against "count ≥ 3" agrees everywhere, and the factored form needs fewer gates than five separate minterms.
The 4-variable majority function (1 when at least 3 inputs are 1) has minterms —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Count the 1s in each 4-bit code: 0111 (7), 1011 (11), 1101 (13), 1110 (14), 1111 (15) are exactly the codes with three or four 1s. Simplified: $AB(C+D) + CD(A+B)$, checked on all 16 rows.
Three common slips
- Grouping diagonally. Groups must be rectangles of $2^{k}$ cells; diagonal neighbours differ in two variables.
- Keeping a changing variable. If a variable is 0 in some cells of the group and 1 in others, it drops out.
- Not checking. With 8 or 16 rows, an exhaustive check takes a minute and catches every grouping error.
The K-map of the XOR A'·B + A·B' has no two adjacent 1s, so it cannot be simplified into fewer product terms.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Its 1s sit at 01 and 10, which differ in both variables: diagonal, not adjacent. XOR stays as two terms, which is why it gets its own gate.
Recap
- Absorption and De Morgan shorten expressions: break the bar, change the sign.
- K-map groups are rectangles of $2^{k}$ cells in Gray order; a group keeps only its constant variables.
- Don't-cares enlarge groups but never form one; verify every result on the full table.