Boolean Algebra and K-Maps
Open in the Padhaiko app3.1 Boolean algebra and its laws
Boolean algebra is the algebra of variables that take only the values 0 and 1, with the operations AND (product), OR (sum) and NOT (complement). Every identity has a dual, obtained by swapping AND with OR and 0 with 1.
| Law | AND form | OR form |
|---|---|---|
| Identity | ||
| Null (dominance) | ||
| Idempotent | ||
| Complement | ||
| Involution | ||
| Commutative | ||
| Associative | ||
| Distributive | ||
| Absorption | ||
| Redundancy | ||
| De Morgan | ||
| Consensus |
3.2 Simplifications of Boolean expressions
To simplify, apply the laws to remove terms and literals. Useful moves:
- Factor common literals: .
- Use to remove a complemented literal.
- Use (adjacent terms combine).
- Add a redundant term (consensus) only if it lets two other terms disappear.
- Apply De Morgan to remove long bars.
Algebraic simplification has no fixed method and cannot tell you when you are done, which is why the K-map (section 3.5) is preferred for up to four variables.
3.3 Minterms and maxterms
For variables, a minterm is a product (AND) term that contains every variable once, in true or complemented form, and equals 1 for exactly one input combination. A maxterm is a sum (OR) term that contains every variable once and equals 0 for exactly one combination.
| Row | A | B | C | Minterm | Notation | Maxterm | Notation |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | ||||
| 1 | 0 | 0 | 1 | ||||
| 2 | 0 | 1 | 0 | ||||
| 3 | 0 | 1 | 1 | ||||
| 4 | 1 | 0 | 0 | ||||
| 5 | 1 | 0 | 1 | ||||
| 6 | 1 | 1 | 0 | ||||
| 7 | 1 | 1 | 1 |
A minterm uses the variable true when the input bit is 1; a maxterm uses it true when the input bit is 0. They are complements: .
3.4 Sum-of-product and product-of-sum methods
- Sum of products (SOP): OR of AND terms. The canonical SOP is the sum of the minterms where the function is 1: .
- Product of sums (POS): AND of OR terms. The canonical POS is the product of the maxterms where the function is 0: .
If , then . SOP maps naturally to AND-OR (or NAND-NAND) circuits, and POS to OR-AND (or NOR-NOR) circuits.
3.5 Truth tables and Karnaugh map
A truth table lists the output for all input combinations. From it the canonical SOP or POS can be read directly.
A Karnaugh map (K-map) is the truth table rearranged in a grid so that adjacent cells differ in exactly one variable. This is done by labelling rows and columns in Gray code order (00, 01, 11, 10), not in binary order. Because the map wraps around, the first and last row (and column) are also adjacent.
Procedure for the 3-variable map
- Draw a 2 x 4 grid with on the rows and on the columns in the order 00, 01, 11, 10.
- Put 1 in each cell whose minterm is in the function, 0 elsewhere.
- Group adjacent 1s in blocks of 2, 4 or 8 (powers of two) as large as possible.
- Each group gives one product term from the variables that do not change inside it.
- OR the terms.
| A / BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
The cells 1, 3, 5, 7 form a quad in which stays fixed, and cells 6, 7 form a pair in which stays fixed. So .
3.6 Four variables K-maps.
A 4-variable map has 16 cells arranged 4 x 4 with on the rows and on the columns, both in Gray order 00, 01, 11, 10. Cell numbers are . The map is a torus: the top and bottom rows are neighbours, and so are the left and right columns, and the four corners are mutually adjacent.
| AB / CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 1 | 3 | 2 |
| 01 | 4 | 5 | 7 | 6 |
| 11 | 12 | 13 | 15 | 14 |
| 10 | 8 | 9 | 11 | 10 |
3.7 Cell, pairs, quads and octets
- Cell: one square of the map, one minterm; it needs all 4 literals (n literals).
- Pair (2 cells): removes 1 variable, leaving 3 literals.
- Quad (4 cells): removes 2 variables, leaving 2 literals.
- Octet (8 cells): removes 3 variables, leaving 1 literal.
- 16 cells: the function is the constant 1.
| Group | Cells | Variables eliminated | Literals left |
|---|---|---|---|
| Single cell | 1 | 0 | 4 |
| Pair | 2 | 1 | 3 |
| Quad | 4 | 2 | 2 |
| Octet | 8 | 3 | 1 |
Rules for grouping: use only 1s (for SOP); the group size must be a power of two; make groups as large as possible; every 1 must be covered at least once; use the fewest groups; overlapping is allowed.
3.8 Rolling, envelop effects and redundant groups
- Rolling: a group may roll over the edge of the map: the left column joins the right column and the top row joins the bottom row. The four corners together form a quad.
- Envelop effect: a group may surround or "envelop" 0 cells, for example the four corners (or the four middle cells) of the map. It is the same wrap-around adjacency seen from a different group.
- Redundant group: a group whose 1s are all already covered by other groups adds a term but no new coverage, so it must be dropped. Always check each group has at least one 1 that no other chosen group covers (an essential prime implicant).
3.9 Don't care conditions
Some input combinations never occur or their output does not matter. They are marked X (or d) in the map. An X may be treated as 1 if it makes a group larger, and as 0 otherwise. Never form a group of X cells alone.
Worked Examples
1
Simplify (a) algebraically and (b) by a K-map, and express it in minterm form.
Minterm form. The terms are , , , and . So .
Algebraic method. Group the four terms that contain : . Then .
So .
K-map method. Place the minterms on the map.
| A / BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
Quad of cells 1, 3, 5, 7 gives ; pair of cells 6, 7 gives . Therefore , the same result.
2
Minimise using a K-map and give the minimal SOP expression.
Fill the map.
| AB / CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 0 | 1 |
| 01 | 0 | 1 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 |
| 10 | 1 | 1 | 0 | 1 |
Form the groups. The four corners 0, 2, 8, 10 roll round to make a quad with and fixed, giving . The cells 0, 1, 8, 9 (columns 00 and 01 in rows 00 and 10) form a quad with and fixed, giving . The cell 5 is not yet covered; it pairs with cell 1, and in that pair , , stay fixed, giving .
Combine. . Each group has a 1 that no other group covers (2 and 10 only in the first, 9 only in the second, 5 only in the third), so none is redundant.
3
Minimise in SOP form, and give the canonical POS form of .
Map with don't cares.
| AB / CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | X | 1 | 1 | X |
| 01 | 0 | X | 1 | 0 |
| 11 | 0 | 0 | 1 | 0 |
| 10 | 0 | 0 | 1 | 0 |
Groups. The quad of cells 3, 7, 11, 15 has and fixed: . The quad 1, 3, 5, 7 uses the don't care at 5 and has , fixed: . The don't cares 0 and 2 are not needed, so they are left as 0. Hence .
Canonical POS of . is 0 for the rows 1, 4, 5, 6, so .
(with don't cares 5 used);
Exercises
Exercises: Boolean Algebra and K-Maps
Simplify using Boolean laws: (a) and (b) .
(a) Use : . Then since , and again gives .
(b) By the consensus theorem the term is redundant, because and appear in the other two terms: . Check: , and both pieces are absorbed by and .
(a) ; (b)
Write the canonical SOP and canonical POS for .
Expand each term to include the missing variable. . .
SOP: . The remaining rows 0, 2, 4, 5 give the POS: .
Use a 3-variable K-map to minimise .
Fill the map:
| A / BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
The quad 2, 3, 6, 7 has fixed, giving . The pair 1, 3 has , fixed, giving . Together they cover all five 1s.
Minimise and explain which grouping rule is used.
| AB / CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |
The four corners 0, 2, 8, 10 roll round into a quad with and : . The middle four cells 5, 7, 13, 15 form a quad with and : . The first uses the corner rule and the second is the envelop rule (the group surrounds the centre).
(the XNOR of and )
Minimise .
| AB / CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 1 | 0 | X |
| 01 | X | 1 | 0 | 1 |
| 11 | 1 | 1 | 0 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Cells 4, 5, 12, 13 form a quad with , : . Cells 4, 6, 12, 14 form a quad with , : (using the don't care 4). Cell 1 pairs with cell 5, with , , : .