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

  1. Construct a K-map.
  1. Find all groups of horizontal or vertical adjacent squares that contain 1.
  2. Each group must be either rectangular or square with 2n squares.
  3. Each group should be as large as possible.
  4. Each 1 on the K-map must be covered at least once. The same 1 can be included in several groups if necessary.
  5. Nonessential groups are omitted. (A nonessential group does not contain a 1 that is not covered by any other group)
  6. Adjacency applies to both vertical and horizontal borders.
  1. Translate each group into a product term by eliminating any variable whose value changes from cell to cell.
  1. 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’y
xy’ / 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 / m2
m4 / m5 / m7 / m6

00 01 11 10

y
0 / 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 / 10
1 / 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 / 10
1
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.

  1. One square represents one minterm, giving a term of three literals.
  2. Two adjacent squares represent a term of two literals.
  3. Four adjacent squares represent a term of one literal.
  4. 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 / 10
1 / 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 / 10
1 / 1 / 1
x 1 / 1 / 1

F = C + A’B

F (A, B, C) =  (1, 2, 3, 5, 7)