Karnaugh Maps

• Applications of Boolean logic to circuit design

– The basic Boolean operations are AND, OR and NOT
– These operations can be combined to form complex expressions, which
can also be directly translated into a hardware circuit
– Boolean algebra helps us simplify expressions and circuits
• Karnaugh Map: A graphical technique for simplifying an expression into a
minimal sum of products (MSP) form:
– There are a minimal number of product terms in the expression
– Each term has a minimal number of literals
• Circuit-wise, this leads to a minimal two-level implementation

1
Review: Minterm

• A product term in which all the variables appear exactly once, either
complemented or uncomplemented, is called a minterm

• A minterm represents exacly one combination of the binary variables in

a truth table. It has the value of 1 for that combination and 0 for the
others

2
Review: Maxterm
• A sum term in which all the variables appear exactly once, either
complemented or uncomplemented, is called a maxterm

• A maxterm represents exacly one combination of the binary variables in

a truth table. It has the value of 0 for that combination and 1 for the
others

• A minterm and maxterm with the same subscript are the complements of
each other, i.e., Mj = m’j
3
Review: Sum of Minterms

• A Boolean function can be represented algebraically from a given truth

table by forming the logical sum of all the minterms that produce a 1
in the function. This expression is called a sum of minterms

F= X’Y’Z’ + X’YZ’ + XY’Z + XYZ

= m0 + m2 + m5 + m7

F(X,Y,Z)= Σm(0,2,5,7)

4
Review: Product of Maxterms

• A Boolean function can be represented algebraically from a given truth

table by forming the logical product of all the maxterms that produce
a 0 in the function. This expression is called a product of maxterms

F= (X+Y+Z’)(X+Y’+Z’)(X’+Y+Z)(X’+Y’+Z)
= M1 . M3 . M4 . M6

F(X,Y,Z)= ∏ M(1,3,4,6)

• To convert a Boolean function F from SoM to PoM:

– Find F’ in SoM form
– Find F= (F’)’ in PoM form
5
Review: Important Properties of Minterms

• There are 2^n minterms for n Boolean variables. These minterms can
be evaluated from the binary numbers from 0 to 2^n-1

• Any Boolean function can be expressed as a logical sum of minterms

• The complement of a function contains those minterms not included in the

original function

F(X,Y,Z)= Σm(0,2,5,7) => F’(X,Y,Z)= Σm(1,3,4,6)

• A function that includes all the 2^n minterms is equal to logic 1

G(X,Y)= Σm(0,1,2,3)= 1

6
Review: Sum-of-Products

• The sum-of-minterms form is a standard algebraic expression that is

obtained from a truth table

• When we simplify a function in SoM form by reducing the number of

product terms or by reducing the number of literals in the terms,
the simplified expression is said to be in Sum-of-Products form

• Sum-of-Products expression can be implemented using a two-level circuit

F= Σm(0,1,2,3,4,5,7) (SoM)
= Y’ + X’YZ’ + XY (SoP)

7
Review: Product-of-Sums

• The product-of-maxterms form is a standard algebraic expression that is

obtained from a truth table

• When we simplify a function in PoM form by reducing the number of

sum terms or by reducing the number of literals in the terms,
the simplified expression is said to be in Product-of-Sums form

• Product-of-Sums expression can be implemented using a two-level circuit

F= ∏ M(0,2,3,4,5,6) (PoM)
= X(Y’ + Z)(X + Y +Z’) (PoS)

8
Re-arranging the Truth Table
• A two-variable function has four possible minterms. We can re-arrange
these minterms into a Karnaugh map

x y minterm Y
0 0 x’y’ 0 1
0 1 x’y 0 x’y’ x’y
1 0 xy’ X
1 xy’ xy
1 1 xy

• Now we can easily see which minterms contain common literals

– Minterms on the left and right sides contain y’ and y respectively
– Minterms in the top and bottom rows contain x’ and x respectively
Y

0 1 Y’ Y
0 x’y’ x’y X’ x’y’ x’y
X
1 xy’ xy X xy’ xy

9
Karnaugh Map Simplifications

• Imagine a two-variable sum of minterms:

x’y’ + x’y

• Both of these minterms appear in the top row of a Karnaugh map, which
means that they both contain the literal x’
Y
x’y’ x’y
X xy’ xy

• What happens if you simplify this expression using Boolean algebra?

x’y’ + x’y = x’(y’ + y) [ Distributive ]

= x’ • 1 [ y + y’ = 1 ]
= x’ [x•1=x]

10
More Two-Variable Examples

• Another example expression is x’y + xy

– Both minterms appear in the right side, where y is uncomplemented
– Thus, we can reduce x’y + xy to just y
Y
x’y’ x’y
X xy’ xy

• How about x’y’ + x’y + xy?

– We have x’y’ + x’y in the top row, corresponding to x’
– There’s also x’y + xy in the right side, corresponding to y
– This whole expression can be reduced to x’ + y
Y
x’y’ x’y
X xy’ xy

11
A Three-Variable Karnaugh Map
• For a three-variable expression with inputs x, y, z, the arrangement of
minterms is more tricky:

YZ YZ
00 01 11 10 00 01 11 10
0 x’y’z’ x’y’z x’yz x’yz’ 0 m0 m1 m3 m2
X X
1 xy’z’ xy’z xyz xyz’ 1 m4 m5 m7 m6

• Another way to label the K-map (use whichever you like):

Y Y
x’y’z’ x’y’z x’yz x’yz’ m0 m1 m3 m2
X xy’z’ xy’z xyz xyz’ X m4 m5 m7 m6
Z Z

12
Why the funny ordering?
• With this ordering, any group of 2, 4 or 8 adjacent squares on the map
contains common literals that can be factored out

Y x’y’z + x’yz
x’y’z’ x’y’z x’yz x’yz’ = x’z(y’ + y)
X xy’z’ xy’z xyz xyz’ = x’z • 1
Z = x’z

• “Adjacency” includes wrapping around the left and right sides:

Y x’y’z’ + xy’z’ + x’yz’ + xyz’

x’y’z’ x’y’z x’yz x’yz’ = z’(x’y’ + xy’ + x’y + xy)
X xy’z’ xy’z xyz xyz’ = z’(y’(x’ + x) + y(x’ + x))
Z
= z’(y’+y)
= z’
• We’ll use this property of adjacent squares to do our simplifications.

13
Example K-map Simplification
• Let’s consider simplifying f(x,y,z) = xy + y’z + xz

• First, you should convert the expression into a sum of minterms form,
if it’s not already
– The easiest way to do this is to make a truth table for the function, and
then read off the minterms
– You can either write out the literals or use the minterm shorthand
• Here is the truth table and sum of minterms for our example:

x y z f(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0 f(x,y,z) = x’y’z + xy’z + xyz’ + xyz
1 0 0 0 = m1 + m5 + m6 + m7
1 0 1 1
1 1 0 1
1 1 1 1
14
Unsimplifying Expressions

• You can also convert the expression to a sum of minterms with Boolean
algebra
– Apply the distributive law in reverse to add in missing variables.
– Very few people actually do this, but it’s occasionally useful.
xy + y’z + xz = (xy • 1) + (y’z • 1) + (xz • 1)
= (xy • (z’ + z)) + (y’z • (x’ + x)) + (xz • (y’ + y))
= (xyz’ + xyz) + (x’y’z + xy’z) + (xy’z + xyz)
= xyz’ + xyz + x’y’z + xy’z

• In both cases, we’re actually “unsimplifying” our example expression

– The resulting expression is larger than the original one!
– But having all the individual minterms makes it easy to combine them
together with the K-map

15
Making the Example K-map
• Next up is drawing and filling in the K-map
– Put 1s in the map for each minterm, and 0s in the other squares
– You can use either the minterm products or the shorthand to show
you where the 1s and 0s belong
• In our example, we can write f(x,y,z) in two equivalent ways

f(x,y,z) = x’y’z + xy’z + xyz’ + xyz f(x,y,z) = m1 + m5 + m6 + m7

Y Y
x’y’z’ x’y’z x’yz x’yz’ m0 m1 m3 m2
X xy’z’ xy’z xyz xyz’ X m4 m5 m7 m6
Z Z

• In either case, the resulting K-map is shown below

Y
0 1 0 0
X 0 1 1 1
Z

16
K-maps From Truth Tables
• You can also fill in the K-map directly from a truth table
– The output in row i of the table goes into square mi of the K-map
– Remember that the rightmost columns of the K-map are “switched”
Y
m0 m1 m3 m2
x y z f(x,y,z)
X m4 m5 m7 m6
0 0 0 0
Z
0 0 1 1
0 1 0 0
0 1 1 0
Y
0 1 0 0
X 0 1 1 1
Z
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

17
Grouping the Minterms Together

• The most difficult step is grouping together all the 1s in the K-map
– Make rectangles around groups of one, two, four or eight 1s
– All of the 1s in the map should be included in at least one rectangle
– Do not include any of the 0s
Y
0 1 0 0
X 0 1 1 1
Z

• Each group corresponds to one product term. For the simplest result:
– Make as few rectangles as possible, to minimize the number of products
in the final expression.
– Make each rectangle as large as possible, to minimize the number of
literals in each term.
– It’s all right for rectangles to overlap, if that makes them larger.

18
Reading the MSP from the K-map
• Finally, you can find the minimal SoP expression
– Each rectangle corresponds to one product term
– The product is determined by finding the common literals in that
rectangle
Y
0 1 0 0
X 0 1 1 1
Z

Y
x’y’z’ x’y’z x’yz x’yz’
X xy’z’ xy’z xyz xyz’
Z

• For our example, we find that xy + y’z + xz = y’z + xy. (This is one of the
additional algebraic laws from last time.)

19
Practice K-map 1

• Simplify the sum of minterms m1 + m3 + m5 + m6

X
Z

Y
m0 m1 m3 m2
X m4 m5 m7 m6
Z

20
Solutions for Practice K-map 1

• Here is the filled in K-map, with all groups shown

– The magenta and green groups overlap, which makes each of them as
large as possible
– Minterm m6 is in a group all by its lonesome
Y
0 1 1 0
X 0 1 0 1
Z

• The final MSP here is x’z + y’z + xyz’

21
K-maps can be tricky!

• There may not necessarily be a unique MSP. The K-map below yields two
valid and equivalent MSPs, because there are two possible ways to
include minterm m7
Y
0 1 0 1
X 0 1 1 1
Z

Y Y
0 1 0 1 0 1 0 1
X 0 1 1 1 X 0 1 1 1
Z Z
y’z + yz’ + xy y’z + yz’ + xz

• Remember that overlapping groups is possible, as shown above

22
Four-variable K-maps
• We can do four-variable expressions too!
– The minterms in the third and fourth columns, and in the third and
fourth rows, are switched around.
– Again, this ensures that adjacent squares have common literals

• Grouping minterms is similar to the three-variable case, but:

– You can have rectangular groups of 1, 2, 4, 8 or 16 minterms
– You can wrap around all four sides
23
Four-variable K-maps

Y Y
w’x’y’z’ w’x’y’z w’x’yz w’x’yz’ m0 m1 m3 m2
w’xy’z’ w’xy’z w’xyz w’xyz’ m4 m5 m7 m6
X X
wxy’z’ wxy’z wxyz wxyz’ m12 m13 m15 m14
W W
wx’y’z’ wx’y’z wx’yz wx’yz’ m8 m9 m11 m10
Z Z

24
Example: Simplify m0+m2+m5+m8+m10+m13
• The expression is already a sum of minterms, so here’s the K-map:

Y Y
1 0 0 1 m0 m1 m3 m2
0 1 0 0 m4 m5 m7 m6
X X
0 1 0 0 m12 m13 m15 m14
W W
1 0 0 1 m8 m9 m11 m10
Z Z

• We can make the following groups, resulting in the MSP x’z’ + xy’z

Y Y
1 0 0 1 w’x’y’z’ w’x’y’z w’x’yz w’x’yz’
0 1 0 0 w’xy’z’ w’xy’z w’xyz w’xyz’
X X
0 1 0 0 wxy’z’ wxy’z wxyz wxyz’
W W
1 0 0 1 wx’y’z’ wx’y’z wx’yz wx’yz’
Z Z

25
Five-variable K-maps

V= 0 V= 1

Y Y
m0 m1 m3 m2 m16 m17 m19 m8
m4 m5 m7 m6 m20 m21 m23 m22
X X
m12 m13 m15 m14 m28 m29 m31 m30
W W
m8 m9 m11 m10 m24 m25 m27 m26
Z Z
26
Simplify f(V,W,X,Y,Z)=Σm(0,1,4,5,6,11,12,14,16,20,22,28,30,31)

1 1 1

1 1 1 1 1

1 1 1 1 1

V= 0 V= 1

f = XZ’ Σm(4,6,12,14,20,22,28,30)
+ V’W’Y’ Σm(0,1,4,5)
+ W’Y’Z’ Σm(0,4,16,20)
+ VWXY Σm(30,31)
+ V’WX’YZ m11
27
PoS Optimization from SoP

F(W,X,Y,Z)= Σm(0,1,2,5,8,9,10)
= ∏ M(3,4,6,7,11,12,13,14,15)

0 0 0 F(W,X,Y,Z)= (W’ + X’)(Y’ + Z’)(X’ + Z)

0 0 0 0

28
SoP Optimization from PoS

F(W,X,Y,Z)= ∏ M(0,2,3,4,5,6)
= Σm(1,7,8,9,10,11,12,13,14,15)

1 F(W,X,Y,Z)= W + XYZ + X’Y’Z

1 1 1 1

1 1 1 1

29
I don’t care!

• You don’t always need all 2n input combinations in an n-variable function

– If you can guarantee that certain input combinations never occur
– If some outputs aren’t used in the rest of the circuit

• We mark don’t-care outputs in truth tables and K-maps with Xs.

x y z f(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 X
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 X
1 1 1 1

• Within a K-map, each X can be considered as either 0 or 1. You should pick

the interpretation that allows for the most simplification.

30
Practice K-map 3

• Find a MSP for

f(w,x,y,z) = Σm(0,2,4,5,8,14,15), d(w,x,y,z) = Σm(7,10,13)

This notation means that input combinations wxyz = 0111, 1010 and 1101
(corresponding to minterms m7, m10 and m13) are unused.

Y
1 0 0 1
1 1 x 0
X
0 x 1 1
W
1 0 0 x
Z

31
Solutions for Practice K-map 3

• Find a MSP for:

f(w,x,y,z) = Σm(0,2,4,5,8,14,15), d(w,x,y,z) = Σm(7,10,13)

Y
1 1
1 1 x
X
x 1 1
W
1 x
Z

f(w,x,y,z)= x’z’ + w’xy’ + wxy

32
AND, OR, and NOT

33
Buffer and 3-State Buffer

• Buffer is used to amplify an electrical signal

- Reconstructing the signal
- More gates to be attached to the output
• Three state buffer
- E (Enable): Controls the output
- Hi-Z: High impedance

34
NAND and NOR

• NAND: Not AND, NOR: Not OR

• Both NAND and NOR are universal gates
• Universal gate: A gate that alone can be used to implement all Boolean
functions
• It is sufficient to show that NAND (NOR) can be used to implement
AND, OR, and NOT operations
35
NANDs are special!
• The NAND gate is universal: it can replace all other gates!

– NOT
(xx)’ = x’ [ because xx = x ]

– AND

((xy)’ (xy)’)’ = xy [ from NOT above ]

– OR

((xx)’ (yy)’)’ = (x’ y’)’ [ xx = x, and yy = y ]

=x+y [ DeMorgan’s law ]

36
XOR and XNOR

• Exclusive-OR (XOR): X ⊕ Y = XY’ + X’Y

• Exclusive-NOR (XNOR): (X ⊕ Y)’ = XY + X’Y’

X⊕0=X X ⊕ 1 = X’
X⊕X=0 X ⊕ X’ = 1
X ⊕ Y’ = (X ⊕ Y)’ X’ ⊕ Y = (X ⊕ Y)’
X⊕Y=Y⊕X
(X ⊕ Y) ⊕ Z = X ⊕ (Y ⊕ Z) = X ⊕ Y ⊕ Z 37
More on XOR

• The general XOR function is true when an odd number of its arguments
are true

• For example, we can use Boolean algebra to simplify a three-input XOR to

the following expression and truth table.
x y z x⊕y⊕z
x ⊕ (y ⊕ z) 0 0 0 0
= x ⊕ (y’z + yz’) [ Definition of XOR ] 0 0 1 1
= x’(y’z + yz’) + x(y’z + yz’)’ [ Definition of XOR ]
0 1 0 1
= x’y’z + x’yz’ + x(y’z + yz’)’ [ Distributive ]
= x’y’z + x’yz’ + x((y’z)’ (yz’)’) [ DeMorgan’s ] 0 1 1 0
= x’y’z + x’yz’ + x((y + z’)(y’ + z)) [ DeMorgan’s ] 1 0 0 1
= x’y’z + x’yz’ + x(yz + y’z’) [ Distributive ] 1 0 1 0
= x’y’z + x’yz’ + xyz + xy’z’ [ Distributive ] 1 1 0 0
1 1 1 1

38
High-Impedance Outputs

• Gates with only output values logic 0 and logic 1

- The output is connected to either Vcc or Gnd
• A third output value: High-Impedance (Hi-Z, Z, or z)
- The output behaves as an open-circuit, i.e., it appears to be
disconnected

• Gates with Hi-Z output values can have their outputs connected together
if no two gates drive the line at the same time to opposite 0 and 1 values

• Gates with only logic 0 and logic 1 outputs cannot have their outputs
connected together

39
Three-State Buffers

40
Three-State Buffers

41
Transmission Gate

If C= 1 (C’= 0) => Y = X

If C= 0 (C’= 1) => Y = Hi-Z

42
Transmission Gate XOR

43
K-map Summary

• K-maps are an alternative to algebra for simplifying expressions

– The result is a minimal sum of products, which leads to a minimal two-
level circuit
– It’s easy to handle don’t-care conditions
– K-maps are really only good for manual simplification of small
expressions...

• Things to keep in mind:

– Remember the correct order of minterms on the K-map
– When grouping, you can wrap around all sides of the K-map, and your
groups can overlap
– Make as few rectangles as possible, but make each of them as large as
possible. This leads to fewer, but simpler, product terms
– There may be more than one valid solution

44