PadhaikoAll subjects

Boolean Algebra and K-Maps

Digital Logic (ENEX 152)

Open in the Padhaiko app

3.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.

Laws of Boolean Algebra
LawAND formOR 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:

  1. Factor common literals: .
  2. Use to remove a complemented literal.
  3. Use (adjacent terms combine).
  4. Add a redundant term (consensus) only if it lets two other terms disappear.
  5. 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.

Minterms and Maxterms for Three Variables
RowABCMintermNotationMaxtermNotation
0000
1001
2010
3011
4100
5101
6110
7111

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

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

  1. Draw a 2 x 4 grid with on the rows and on the columns in the order 00, 01, 11, 10.
  2. Put 1 in each cell whose minterm is in the function, 0 elsewhere.
  3. Group adjacent 1s in blocks of 2, 4 or 8 (powers of two) as large as possible.
  4. Each group gives one product term from the variables that do not change inside it.
  5. OR the terms.
3-variable K-map of F = sum m(1,3,5,6,7)
A / BC00011110
00110
10111

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.

Minterm Numbers on a 4-variable K-map
AB / CD00011110
000132
014576
1112131514
10891110

3.7 Cell, pairs, quads and octets

Group Size and Literals in a 4-variable Map
GroupCellsVariables eliminatedLiterals left
Single cell104
Pair213
Quad422
Octet831

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

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

Example 1

1 (8 marks)

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.

K-map for Example 1
A / BC00011110
00110
10111

Quad of cells 1, 3, 5, 7 gives ; pair of cells 6, 7 gives . Therefore , the same result.

Answer:

Example 2

2 (10 marks)

Minimise using a K-map and give the minimal SOP expression.

Fill the map.

K-map for Example 2
AB / CD00011110
001101
010100
110000
101101

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.

Answer:

Example 3

3 (10 marks)

Minimise in SOP form, and give the canonical POS form of .

Map with don't cares.

K-map for Example 3 (X = don't care)
AB / CD00011110
00X11X
010X10
110010
100010

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 .

Answer:

(with don't cares 5 used);


Exercises

Exercises: Boolean Algebra and K-Maps

Question 1

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 .

Answer:

(a) ; (b)

Question 2

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: .

Answer:

Question 3

Use a 3-variable K-map to minimise .

Fill the map:

K-map for Question 3
A / BC00011110
00111
10011

The quad 2, 3, 6, 7 has fixed, giving . The pair 1, 3 has , fixed, giving . Together they cover all five 1s.

Answer:

Question 4

Minimise and explain which grouping rule is used.

K-map for Question 4
AB / CD00011110
001001
010110
110110
101001

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).

Answer:

(the XNOR of and )

Question 5

Minimise .

K-map for Question 5 (X = don't care)
AB / CD00011110
00010X
01X101
111101
100000

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 , , : .

Answer:

← Logic GatesCombinational Logic Circuits →