### Document

```2.7 NAND and NOR logic networks
• Introduce the use of NAND and NOR gates in
the synthesis of logic circuits
– Attractive due to their simpler electronic circuits
implementation than AND and OR functions
– Q: Can be used directly in the synthesis of logic
circuits? And how?
1
Graphical symbols for NAND and
NOR gates (Figure 2.20)
x1
x2
x1
x2
x 1  x 2    x n
x 1  x 2
xn
(a) NAND gates
x1
x1
x2
x2
A bubble at the output
side of the gate
symbols
represents the
complemented output
signal.
x 1 + x 2 +  + x n
x1 + x2
xn
(b) NOR gates
2
DeMorgan’s theorem in terms of
logic gates
x1
x2
x1
x2
x1
x2
(a) 1 2 = 1 + 2
A NAND gate is equivalent to the OR gate with inversions at its inputs.
x1
x2
x1
x2
x1
x2
(b) 1 + 2 = 1 2
A NOR gate is equivalent to the AND gate with inversions at its inputs
3
x1
x2
x3
x4
x5
Transform a AND-OR networks
into a network of NAND gates
1. Replace each connection
between AND and OR gate
by inversions of signals.
2. Replace OR gate with
inverted inputs by a NAND
gate.
1
x1
x2
x3
x4
x5
2
Double inversion has
no effect on the
network behavior.
x1
x2
x3
x4
x5
Same topology!
Figure 2.22. Using NAND gates to implement a sum-of-products.
4
•
x1
x1
x2
x2
x3
x3
x4
x4
x5
x5
Can implement any OR-AND
network as a NOR-NOR
network having the same
topology with the similar
transformation procedure.
x1
x2
x3
x4
x5
Figure 2.23. Using NOR gates to implement a product-of sums.
5
Example 2.6
Combining property
14b. (x + y) (x + ) = x
• Let us implement the function using NOR
gates only
1 , 2 , 3 =
(2, 3, 4 , 6, 7) =
(0,1,5)
• The POS expression
=(x1 + x2 + x3) (x1+x2+3 )(1 +x2+3 )
// apply combining property 14b to
// M0 and M1; M1 and M5
= 1 + 2 ( +  )
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
F
0
0
1
1
1
0
1
1
6
x1
x2
f
x3
(a) POS implementation in Example 2.4
x3 is inverted by a NOR
gate that has its inputs x
1
tired together.
=  +
x2
f
x3
(b) NOR implementation
Figure 2.24
NOR-gate realization of the function in Example 2.4.
7
Example 2.7
Distributive property
12a. x (y + z) = xy + xz
• Let us implement the function using NAND
x
x
gates only
0
0
1
1 , 2 , 3 =
(2, 3, 4 , 6, 7)
• The SOP expression
= 1 23 + 1 23 + 12 3 + 12 3 + 1 23
// merge m2, m3, m6, and m7 using P12a;
// merge m4 and m6
= 2(1 3 + 1 3 + 13 + 13) + ( +  )
0
0
0
1
1
1
1
2
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
F
0
0
1
1
1
0
1
1
All 4 combinations = 1
= x2 +
8
x2= x2+x2
x2
x2
f
x3
f
x1
x1
x3
(a) SOP implementation
=  ∙
x2
f
x1
x3
(b) NAND implementation
Figure 2.25. NAND-gate realization of the function in Example 2.3.
9
2.8 Design Examples
• Basic issues that a designer is always
confronted with
– Necessary to specify the desired behavior of the
circuit.
– The circuit has to be synthesized and
implemented.
10
Three-way light control
Let x1, x2, and x3 be the input variables
that denote the state of each switch.
Assume that
• the light is off if all switches are
open
• Closing any one of the switches will
turn the light on.
• Closing a second switch will have
to turn off the light, that is to say,
light will be off if two (or no)
switches are closed.
• Turn the light on by closing the third
switch if two switches are closed.
Figure 2.26. Truth table for a three-way light control.
11
Canonical SOP and POS
• SOP expression for the specified function
= 1 + 2 + 4 + 7
= 1 2 3 + 1 2 3 + 1 2 3 + 1 2 3
• POS expression for the specified function
= 0356
= (1 + 2 + 3) (1 + 2 + 3 )
(1 + 2 + 3 ) (1 + 2 + 3)
12
f
x1
x2
x3
(a) Sum-of-products realization
x1 x2
x3 f1
f2 f3
f4
f
0
0
0
0
1
1
1
0
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
x3
x2
x1
f1
f2
f
f3
f4
(a) Product-of-sums realization
13
Multiplexer
Distributive property
12a. x (y + z) = xy + xz
• A circuit that generates an output that exactly
reflects the state of one of a number of data
inputs, based on the value of one or more
selection control inputs.
s x1 x2
f (s, x1, x2)
000
0
001
0
010
1
011
1
100
0
101
1
110
0
111
1
f(s, x1, x2)
=  +  +  +  //12a
=   +  +   +
=  ∙  +  ∙  ∙
=  +
14
Implementation of a 2-to-1
multiplexer
=  +
x1
s x1 x2
f (s, x1, x2)
000
0
001
0
010
1
011
1
100
0
101
1
110
0
111
1
(a)Truth table
f
s
x2
s
(b) Circuit
f (s, x1, x2)
0
x1
1
x2
s
x1
0
x2
1
(d) More compact truth-table
representation
f
(c) Graphical symbol
15
• A 4-to-1 multiplexer has four data inputs and
one output
– Two selection control inputs are needed
• A 8-to-1 multiplexer needs eight data inputs
and three selection control inputs
• Same circuit structure can be used to
implement multiplexer using NAND gates.
• More discussions on multiplexer are in
Chapter 3 and 6.
16
2.12 EXAMPLES OF SOLVED
PROBLEMS
17
Example 2.8
Determine if the following equation is valid
1 3 + 23 + 12 = 1 2 + 13 + 2 3
Solution: Derive a canonical SOP form for each expression
(an algebraic approach)
LHS = 1 (2 + 2 )3 + (1 + 1 )23 + 12 (3 + 3 )
= 1 23 + 1 2 3 + 123 + 1 23 + 12 3 + 12 3
(
2
0
7
3
5
4 )
= (2,0,7,3,5,4) = (0,2,3,4,5,7)
RHS = 1 2(3 + 3 ) + 1(2 + 2 )3 + (1 + 1 ) 2 3
= 1 23 + 1 23 + 123 + 12 3 + 12 3 + 1 2 3
= (3,2,7,5,4,0) = (0,2,3,4,5,7)
18
Example 2.9
Combining property
14b. (x + y) (x + ) = x
Determine the minimum-cost POS expression for the function
f(x1,x2,x3,x4) = (0,2,4,5,6,7,8,10,12,14,15)
definition in terms of maxiterms, which is f = (1,3,9,11,13)
f = M1 ∙ 3 ∙ 9 ∙ 11 ∙ 13
= (x1+x2+x3+ ) (x1+x2+ + ) ( +x2+x3+ )
( +x2+ + ) ( + +x3+ )
M1 ∙ 3 = x1 + x2 +  // combining property 14b
M9 ∙ 11=  + x2 +
M9 ∙ 13=  + x3 +
f = (x1+x2+ ) ( +x2+ ) (1 +x3+4 ) = (x2+ ) (1 +x3+4 )
19
Example 2.12
Absorption
13a. x+xy = x
Combining
14a. xy+x = x
Derive the simplest SOP expression for the
function
= 234 + 134 + 124
Solution:
f = 234 + 134 +  + 124 //consensus
= 234 + 134 +  + // combining
= 234 + 134 +
= 234 +  +
// absorption
= 234 +
Consensus
17a. xy + +  = xy+
20
Problem 2.31
1
0
0
0
0
0
1
1
1
1
x2 1
0
0
0
1
1
0
0
1
1
x3 1
0
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
x1
f
Time
Figure P2.3. A timing diagram representing a logic function.
Synthesize the function in the simplest SOP form
21
Problem 2.31
1
0
0
0
0
0
1
1
1
1
x2 1
0
0
0
1
1
0
0
1
1
x3 1
0
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
x1
f
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f
1
0
0
1
0
1
1
0
Time
The simplest SOP expression is
= 1 2 3 + 1 x2x3 + x12 x3+x1x23
22
```