Chapter 3
Simplification of Boolean Functions
The Map Method
- The Karnaugh map method provides a simple, straightforward procedure for minimizing Boolean expressions.
- The K-map minimization procedure obtains a minimal expression directly from a truth table. The map is a diagram made up of squares containing 1s and/or 0s.
- The map presents a visual diagram of all possible ways a function may be expressed in a standard form.
- By recognizing various patterns, the user can derive alternative algebraic expression for the same function.
Two- And Three- Variable Maps
Minimization Procedure
- Construct a K-map.
- Find all groups of horizontal or vertical adjacent squares that contain 1.
- Each group must be either rectangular or square with 2n squares.
- Each group should be as large as possible.
- Each 1 on the K-map must be covered at least once. The same 1 can be included in several groups if necessary.
- Nonessential groups are omitted. (A nonessential group does not contain a 1 that is not covered by any other group)
- Adjacency applies to both vertical and horizontal borders.
- Translate each group into a product term by eliminating any variable whose value changes from cell to cell.
- Sum all the product terms.
Note: Don't care conditions can be used to provide further simplification of the representation of a function.
0
x’y’ / x’yxy’ / Xy
m0 / m1
m2 / m3
Two-variable map 0
- In the previous example there are four minterms for two variables. The 0’s and 1’s designate the values of variable x and y, respectively.
- Variable x appears primed in row 0 and unprimed in row 1. Similarly, y appears primed in column 0 and unprimed in column 1.
- Ex: let’s represent the function xy and the function x + y.
A three-variable map
m0 / m1 / m3 / m2m4 / m5 / m7 / m6
00 01 11 10
y0 / x’y’z’ / x’y’z / x’yz / x’yz’
x 1 / xy’z’ / xy’z / xyz / xyz’
z
- There are 8 minterms for three binary variables (8 squares). The minterms are not arranged in a binary sequence; however, it is listed similar to Gray code.
- Variables appear unprimed in the squares where it is = 1 and primed where it is equal to 0.
- Any 2 adjacent squares in the map differ by only one variable, which is primed in one square and unprimed in the other.
- Ex: m5 and m7 lie in two adjacent squares where y is primed m5 in and unprimed in m7.
- Ex: simplify the Boolean function F (x, y, z) = (2, 3, 4, 5)
00 / 01 / 11 / 101 / 1
x 1 / 1 / 1
F = x’y + xy’
- There are cases where two cases are considered to be adjacent even though they don’t touch each other.
- Ex: simplify the Boolean function F (x, y, z) = (3, 4, 6,7)
00 / 01 / 11 / 101
x 1 / 1 / 1 / 1
= x’yz + xy’z’ + xyz + xyz’
= yz + xz’
- The number of adjacent squares that may be combined must always represent a number that is a power of two such as 1, 2, 4, and 8.
- As a larger number of adjacent squares are combined, we obtain a product term with fewer literals.
- One square represents one minterm, giving a term of three literals.
- Two adjacent squares represent a term of two literals.
- Four adjacent squares represent a term of one literal.
- Eight adjacent squares encompass the entire map and produce a function that is equal to 1.
- Ex: Simplify the Boolean function F (x, y, z) = (0, 2, 4, 5,6)
00 / 01 / 11 / 101 / 1
x 1 / 1 / 1 / 1
F = z’ + xy’
- Ex: Simplify the Boolean function F = A’C + A’B + AB’C + BC
00 / 01 / 11 / 101 / 1 / 1
x 1 / 1 / 1
F = C + A’B
F (A, B, C) = (1, 2, 3, 5, 7)