Lecture 4 Nand, Nor Gates,

Circuit Minimization
and
Karnaugh Maps
Prof. Sin-Min Lee
Department of Computer Science
Boolean Algebra to Logic Gates

• Logic circuits are built from components called logic

gates.
• The logic gates correspond to Boolean operations +, *, ’.

OR AND NOT
+ * ’
• Binary operations have two inputs, unary has one
 Logic Circuits ≡ Boolean Expressions
• All logic circuits are equivalent to Boolean expressions and any boolean expression can be rendered
as a logic circuit.
• AND-OR logic circuits are equivalent to sum-of-products form.
• Consider the following circuits:

A
A B Y=AB*+B*C
B C ABC
C A
AB*C B Y
Y C

A*B
y=ABC+AB*C+A*B
 NAND and NOR Gates
• NAND and NOR gates can greatly simplify circuit
diagrams. As we will see, can you use these gates
wherever you could use AND, OR, and NOT.

A B AB
NAND 0 0 1
0 1 1 A B AB
1 0 1 0 0 1
1 1 0 0 1 0
1 0 0
NOR
1 1 0
 XOR and XNOR Gates
• XOR is used to choose between two mutually exclusive
inputs. Unlike OR, XOR is true only when one input or the
other is true, not both.

A B AB
0 0 0 A B A B
XOR 0 1 1
1 0 1 0 0 1
1 1 0 0 1 0
XNOR 1 0 0
1 1 1
NAND and NOR as Universal Logic
Gates
• Any logic circuit
can be built using
only NAND gates,
or only NOR gates.
They are the only
logic gate needed.
• Here are the
NAND
equivalents:
 NAND and NOR as Universal Logic
Gates (cont)
• Here are the
NOR equivalents:
• NAND and NOR
can be used to
reduce the
number of
required gates in
a circuit.
 Example Problem
• A hall light is controlled by two light switches, one
at each end. Find (a) a truth function, (b) a Boolean
expression, and (c) a logic network that allows the
light to be switched on or off by either switch.

Let x and y be the switches:

x y f(x,y)
0 0 0 (What kind of
0 1 1 gate has this
1 0 1 truth table?
1 1 0
 x y f(x,y)
0 0 0
Example (cont) 0 1 1
1 0 1
1 1 0
• One possible equation is the complete sum-of-
products form:
f(X,Y) = XY* + X*Y
• Use The Most Complex Machine xLogicCircuit
Module to implement the
equation.
How to use NAND gates to build an OR gate?

A C Truth Table
Q A B C D Q
B D 0 0 1 1 0
0 1 1 0 1
1 0 0 1 1
Hint 1 : Use 3 NAND gates 1 1 0 0 1

Hint 2 : Use 2 NAND gates to build 2 NOT gates

Hint 3 : Put the 3rd NAND gate
after the 2 “NOT” gates
How to use NAND gates to build a NOR gate?
Truth Table
A C E A B C D E Q
Q 0 0 1 1 0 1
B D 0 1 1 0 1 0
1 0 0 1 1 0
1 1 0 0 1 0

Hint 1 : Use 4 NAND gates

Hint 2 : Use 3 NAND gates to build an OR gate
Hint 3 : Use a NOR gate to build a NOT gate

Hint 4 : Put the “NOT” gate after “OR” gate

 How to use NOR gate to build a NOT gate?
Truth Table

B A B C Q
A Q 0 0 0 1
C 1 1 1 0
Hint!
Link inputs B & C together (to a same source).
When A = 0, B = C = A = 0
When A = 1, B = C = A = 1
 How to use NOR gates to build an OR gate?
Truth Table
A B C D E Q
NOR NOT 0 0 1 1 1 0
A D 0 1 0 0 0 1
C
Q 1 0 0 0 0 1
B E
1 1 0 0 0 1
Hint 1 : Use 2 NOR gates
Hint 2 : From a NOR gate, build a NOT gate
Hint 3 : Put this “NOT” gate after a NOR gate
 How to use NOR gates to build an AND gate?
Truth Table
A B C D Q
A
C 0 0 1 1 0
Q
0 1 1 0 0
D
B 1 0 0 1 0
1 1 0 0 1
Hint 1 : Use 3 NOR gates
Hint 2 : From 2 NOR gates, build 2 NOT gates
Hint 3 : Each “NOT” gate
is an input to the 3rd NOR gate
 How to use NOR gates to build a NAND gate?
A Truth Table
C E
Q A B C D E Q
D 0 0 1 1 0 1
B
Hint 1 : Use 4 NOR gates 0 1 1 0 0 1
Hint 2 : Use 3 NOR gates 1 0 0 1 0 1
to build a NAND gate
(previous lesson)
1 1 0 0 1 0
Hint 3 : Use the 4th NOR gate to build a NOT gate
Hint 4 : Insert “NOT” gate after “NAND” gate
Hint 5 : NOT-NAND = AND
 How to use NAND gates to build a NOT gate?
Truth Table
B A B C Q
A Q
0 0 0 1
C
1 1 1 0
Hint!
Link inputs B & C together (to a same source).
When A = 0, B = C = A = 0
When A = 1, B = C = A = 1
 How to use NAND gates to build an AND gate?
Truth Table
NOT A B C Q
NAND
0 0 1 0
0 1 1 0
A C
Q 1 0 1 0
B
1 1 0 1
Hint 1 : Use 2 NAND gates
Hint 2 : From a NAND gate, build a NOT gate
Hint 3 : Put this “NOT” gate after a NAND gate
Hint 4 : NOT-NAND = AND
 How to use NAND gates to build an OR gate?
Truth Table
A C A B C D Q
Q 0 0 1 1 0
B D 0 1 1 0 1
1 0 0 1 1
1 1 0 0 1
Hint 1 : Use 3 NAND gates
Hint 2 : Use 2 NAND gates to build 2 NOT gates
Hint 3 : Put the 3rd NAND gate
after the 2 “NOT” gates
 How to use NAND gates to build a NOR gate?
Truth Table
A C E A B C D E Q
Q 0 0 1 1 0 1
B D 0 1 1 0 1 0
1 0 0 1 1 0
1 1 0 0 1 0
Hint 1 : Use 4 NAND gates
Hint 2 : Use 3 NAND gates to build an OR gate
Hint 3 : Use a NOR gate to build a NOT gate
Hint 4 : Put the “NOT” gate after “OR” gate
Since functions can be represented by a sum of product form
of minterms, any function can be shown in the map by
placing each a 1 in each square which represents a minterm
in the function.

EXAMPLE: Draw the map for f = X + Y

1. Determine which minterms are needed by using truth table.

X Y f = X + Y minterm
0 0 0 m0
0 1 1 m1
1 0 1 m2
1 1 1 m3
2. Draw the map and place a 1 in each square for required
minterms. Y
Y
X 1
1
0

X 1 1 1

f = X + Y = m1 + m2 + m3 = X´ Y + X Y´ + X Y
 Use the 2-Variable Karnaugh Map
for Minimization

Example: Given f (X,Y) =  (0, 2)

Find: Simplified sum of products

Y Y
X

m0 m1

X m2 m3
 2-Variable Karnaugh Map

1. Place the 1’s corresponding to the minterms on

the map.
f (X,Y) =  (0, 2)

Y Y
X

1 0

X 1 0
 2-Variable Karnaugh Map

2. Now group the 1’s into columns or rows; in this case

we can group them in the first column.

f (X,Y) =  (0, 2)
Y Y
X

1 0

X 1 0

3. This column is Y´ so the simplified function f (X,Y) = Y´

 2-Variable Karnaugh Map

Example 2: Given f (X,Y) =  (0, 2, 3)

Find: Simplified sum of products

Y Y
X

m0 m1

X m2 m3
 2-Variable Karnaugh Map

Example 3: Given f (X,Y) =  (0, 1)

Find: Simplified sum of products

Y Y
X

m0 m1

X m2 m3
 Three Variable Map
m0 m1 m3 m2
m4 m5 m7 m6
Y
YZ
X 00 01 11 10
0 X´ Y´ Z´ X´ Y´ Z X´ Y Z X´ YZ´

X 1 X Y´ Z´ XY´Z XYZ X Y Z´

Z
 Three Variable Map
There are 2N = 23 = 8 squares.

The minterms are arranged so that only one variable

changes from 0 to 1 or from 1 to 0 as you move from
square to square in the vertical or horizontal direction.

For any two adjacent squares, only one literal changes

from complemented to non-complemented (normal).
From this property the left and right ends of the map
are “adjacent.”
 Y
YZ
X 00 01 11 10
0 X´Y´Z´ X´ Y´ Z X´ Y Z X´ Y Z´

X 1 X Y´Z´ X Y´ Z XYZ X YZ´

Using the distributive and complement properties, any two

adjacent minterms can be combined and simplified to a single
term with one less literal.
 Combining terms on the Karnaugh Map simplifies Boolean
functions.
Example: combine adjacent squares for X´ Y´ Z and XY´Z

X´Y´ Z + XY´Z = Y´ Z ( X´ + X) = Y´ Z · 1 = Y´ Z

Example: Combine adjacent squares for X Y´Z´ and X YZ´

XY´Z´ + X YZ´ = X Z´ ( Y´ + Y) = X Z´ · 1 = X Z´
Y
YZ
X 00 01 11 10
0 X´Y´Z´ X´ Y´ Z X´ Y Z X´ Y Z´

X 1 X Y´Z´ X Y´ Z XYZ X YZ´

Z
Example: Simplify
f = X´Y´ Z´ + X Y Z + X´Y´ Z + X´ Y Z

Y
YZ
X 00 01 11 10

0 1 1 1

X 1 1

Z
f = X´Y´ + Y Z
 Even if the function is not in its simplest form, we can still
use the map to simplify it further.

Example: Simplify f = X´ Y´ + Y´ Z + X´ Z + X Y Z
Y
YZ
X 00 01 11 10

0 1 1 1

X 1 1 1

Z
f = Z + X´ Y´ (by further grouping of minterms)
 3-Variable Karnaugh Map

Example: Given f (X,Y,Z) =  (0, 2, 3, 4, 7)

Find: Simplified sum of products

YZ Y
X

m0 m1 m3 m2

m4 m5 m7 m6
X

Z
 3-Variable Karnaugh Map

Example: Given f (X,Y,Z) =  (0, 2, 3, 4, 7)

Simplified sum of products: f = YZ + YZ + XY

YZ Y
X

1 0 1 1

1 0 1 0
X

Z
 Truth Table

f (X,Y,Z) =  (0, 2, 3, 4, 7)

Simplified sum of products: f = Y´Z´ + YZ + X´Y

The truth table for f:

X Y Z f
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
 f (X,Y,Z) =  (0, 2, 3, 4, 7)
= Y´Z´ + YZ + X´Y

Y
Z

Y f
Z

X
Y
 3-Variable Karnaugh Map

Example 2: Given f (X,Y,Z) =  (2, 3, 4, 5)

Find: Simplified sum of products

YZ Y
X

m0 m1 m3 m2

m4 m5 m7 m6
X

Z
 3-Variable Karnaugh Map

Example 2: Given f (X,Y,Z) =  (1, 2, 5, 6, 7)

Find: Simplified sum of products

YZ Y
X

m0 m1 m3 m2

m4 m5 m7 m6
X

Z
 3-Variable Karnaugh Map

Example 3: Given f (X,Y,Z) = X´Z + X´Y + XY´Z + YZ

Find: “Sum of minterms” expression

YZ Y
X

m0 m1 m3 m2

m4 m5 m7 m6
X

Z
 Exclusive OR
XOR

f = X´Y + XY´ = X  Y
X Y f
0 0 0
0 1 1
1 0 1
1 1 0
 Exclusive OR

f (X,Y) =  (1, 2) = X  Y

Y Y
X

0 1

1 0
X
 XOR Truth Table

f (X,Y,Z) = X  Y  Z =  (1, 2, 4, 7)

The truth table for f:

X Y Z f
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
 Exclusive OR

X
Y

f (X,Y,Z) = X  Y  Z
Z
 Four Variable Map Y
YZ
WX 00 01 11 10
m0 m1 m3 m2 00
m4 m5 m7 m6
01
m12 m13 m15 m14 X
m8 m9 m11 m10 11 w x y´z
W
W x´y´z
10

Z
 Four Variable Map
N = 4 variables
2N = 24 = 16 square (minterms)

Row and column are numbered using a reflected-code

sequence. The minterm number can be obtained by
concatenation of the row and column number .

Example: Row 4 = 10, Column 2 = 01 giving

1001 = 9 decimal for W X´ Y´ Z.
 Y
YZ
00 01 11 10

00 wx´y´z´ 1 1 w´x´y z´

01
X
11
W wx´y´z
10 ´
1 1 wx´y´z

Notice that top and bottom edges and right and left edges are
“adjacent.”
1 square = a term with 4 literals
2 square = a term with 3 literal
4 square = a term with 2 literals
8 square = a term with 1 literal
16 square = a function equal to 1 Y
YZ
WX 00 01 11 10
00
01
X
11
W
10

Z
Simplify: f (W, X, Y, Z) = W X´ Z + W X Z + W´ Y Z
Y
YZ
WX 00 01 11 10
00
01
X
11
W
10

f=WZ+YZ
Z
f = Z ( W + Y)
 Simplify: f (W, X, Y, Z) =  ( 0, 1, 4, 5, 6, 8, 9, 12, 13, 14)
Y
YZ
WX 00 01 11 10

00
01
X
11
W
10

f = Y´ + WZ´ + XZ´ Z

8 square 4 square 4 square

Simplify: f = W´ X´ Y´ + X´Y Z´ + W´ X Y Z´ + W X´ Y´

Y
YZ
WX 00 01 11 10

00
01
X
11
10

f = X´ Z´ + X´ Y´ + W´ Y Z´
 Simplification of kmap

• Generate all PIs

• Find EPIs
• If EPIs can cover all minterms, then it is
answer. Otherwise choose some non-
essential PIs (which has less cost) such that
all minterms are cover.
 Step 1
x1x2

• Generate PIs 00 01 11 10

x3x4
– Blue circle are PIs
00
– They are the largest 0 4 12 8

circle you can drawn 01 1 1

on kmap 1 5 13 9

11 1 1 1
3 7 15 11

10 1 1 1 1
2 6 14 10
 Step 2
• Find EPIs x1x2

00 01 11 10
– Red circle are EPIs x3x4

• Minterm 5, 14, 11 can 00

0 4 12 8
only be cover by these 3
red circle 01 1 1
1 5 13 9

11 1 1 1
3 7 15 11

10 1 1 1 1
2 6 14 10
 Step 3
x1x2

• EPIs cannot cover 00 01 11 10

minterm 7 x3x4

00
– Choose between 0 4 12 8

green/blue circle to 01 1 1
cover minterm 7 1 5 13 9

– Green is chosen as it is 11 1 1 1
3 7 15 11
larger
• Less cost 10 1 1 1 1
2 6 14 10
 Final
• Final result is obtained
– x3x4’ + x2’x3x1x2+ x1’x3 + x2x3’x4
00 01 11 10

x3x4

00
0 4 12 8

01 1 1
1 5 13 9

11 1 1 1
3 7 15 11

10 1 1 1 1
2 6 14 10
 Complement and Product of Sums

On the K Map a 1 was placed in the squares which represented

minterms for a function. The squares not used represent the
complement of the function. Mark these squares with 0,
combine them and read the complement as a sum of products
function, f´. Using De Morgan’s Law on f´ will give f, the original
Function. It will be in a product of sums form.

Example: Determine the Product of sums form

for f ( W, X, Y, Z) =  (0, 1, 2, 5, 8, 9, 10)
f´ = W X + YZ + X Z´ from the map
f = (W´ + X´) ( Y´ + Z´) ( X´ + Z) by De Morgan’s
 Complement and Product of Sums

Also, can determine the product of sums form directly from

The map by recognizing that the 0’s on the map represent
maxterms. Remember that a 1 on the edge of the map
Represents a complemented literal for maxterms.

Thus, for f ( W, X, Y, Z) =  (0, 1, 2, 5, 8, 9, 10)…….

(combine 0’s on k-map)…

f = ( Y´ + Z´) (W´ + X´) ( X´ + Z)

 Y
YZ
WX 00 01 11 10
00 1 1 0 1

01 0 1 0 0

11 0 0 0 0
W
10 1 1 0 1

Z
f = ( Y´ + Z´ ) ( W´ + X´ ) ( X´ + Z)