Boolean algebra and Karnaugh maps
| English | Chinese | Pinyin |
|---|---|---|
| Boolean algebra | 布尔代数 | bù ěr dài shù |
| Karnaugh map | 卡诺图 | kǎ nuò tú |
| De Morgan's laws | 德摩根定律 | dé mó gēn dìng lǜ |
| absorption | 吸收律 | xī shōu lǜ |
| Gray code | 格雷码 | gé léi mǎ |
The maths of true and false
- 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$.
De Morgan's law in a truth table: NOT (A AND B) equals (NOT A) OR (NOT B)
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:
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Match each Boolean law to what it says.
These laws let you simplify Boolean expressions algebraically before building the circuit.
Simplifying
- Apply the laws to cut the number of terms. Example:
- The simpler expression needs fewer gates, so the circuit is cheaper and faster.
A Karnaugh map: grouping the four 1s simplifies the expression to Z = A
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.
- A Boolean expression can be described by truth tables and simplified with a K-map (Karnaugh map).
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.
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).
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes.
You've got it
- 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