2.
2 Logic Gates 17
Graphie Algebraic Tiuth
Name symbol table
function
A B
X=A B
0 0
AND or
0 1
X=AB
1 0
1 1
A B x
A 0 0
OR I =A + B
0 1 1
1 0 1
1
Inverter
Buffer
A B
0
NAND -. =(AB)'
0
1 0
1
A B
0 0
NOR . = ( A + BY'
0 1
1 0 0
1 0
A B
Exclusive-OR 0 0
(XOR) =1B + AB'
A B
N(A B)'
Exclusive-NOR 0 0
(Or
or equivalence
r=A'B' +AB
FIGURE 2.2
Digital logic gates.
2.3 Boolean Algebra
Boolean functior
Boolean algebra is an algebra that deals with binary variables and logic oper
three
ations. The variables are designated by letters such as A, B, x, and y. The
Boolean function
basic logic operations are AND, OR, and complement. A
sym
can be expressed algebraically with binary variables, the logicoperation
variables, the Bool
bols, parentheses, and equal sign. For a given value of the Boolean function
the
ean function can be either 1l or 0. Consider, for example,
F=x+y'z
are equal to l; F is
The function F is equal to l ifx is 1or if both y' and z
equal to 0 otherwise. But saying that y'= 1is equivalent
to saying that y = 0
20 DigitalLogic Circuits
since y'is the complement of y. Therefore, we may say that Fis equal to 1if
x=l or if yz = 01. The relationship between a function and its binary varj-
truth table ables can be represented in a truth table. To represent a function in a truth
table we need alist of the 2" combinations of theen binary variables. As shown
in Fig. 2.4(a), there are eight possible distinct combinations for assigning bits
to the three variables x, y, and z. The functionF is equal to 1 for those Com-
binations where x=l or yz=01; it is equal to 0 for all other combinatio.
ABoolean function can be transformed from an algebraic expression
logic diagam into a logic diagram composed of AND, OR, and inverter gates. The l
diagram for F is shown in Fig. 2.4(b). There is an inverter for input yto oen
erate its complement y. There is an AND gate for the term y'z, and an 0
gate is used to combine the two terms. In alogic diagram, the variables of the
function are taken to be the inputs of the circuit, and the variable symbol ot
the function is taken as the output of the circuit.
The purpose of Boolean algebra is to facilitate the analysis and desion
of digital circuits. It provides a convenient tool to:
1 Express in algebraic form a truth table relationship between binary
variables.
2 Express in algebraic form the input-output relationship of logic diagrams.
3. Find simpler circuits for the same function.
Boolean expression ABoolean function specified by a truth table can be expressed algebraically
in many diferent ways. By manipulating a Boolean expression according to
Boolean algebra rules,one may obtain a simpler expression that will require
fewer gates. To see how this is done, we must first study the manipulative
capabilities of Boolean algebra.
Table 2.1 lists the most basic identities of Boolean algebra. All the identi
ties in the table can be proven by means of truth tables. The first eight identities
show the basic relationship between a single variable and itself, or in conjunction
with the binary constants 1 and 0. The next five identities (9 through 13) ar
similar to ordinary algebra. Identity 14 does not apply in ordinary algebra but s
very useful in manipulating Boolean expressions. ldentities 15 and 16 are caleu
DeMorgan's theorems and are discussed below. The last identity states that i a
variable is complemented twice, one obtains the original value of the varnable.
0
0
0 0
1
(a) Truth table (b) Logic diagram
FIGURE 2.4 Iruth table and logic diagram for F =X+yz.
2.3 Boolean Algebra 21
Basic ldentities of Boolean Algebra
TABLE 2.1
(2) xØ =0
( ) x+0=x
(3) x+l =| (4) x 1=x
(6) xx=X
(5) x+x=x
(8) xx'=0
(7) r+r'= 1
(9) x + = t x (10) xy =yx
(12) x(yz) = (xy)z
(11) x+y+:) = (r+)+z
(13) x ( + ) = " + x z
(14) x + yx= (x +y)(x + z)
(15) (r +1)'=x (16) (xy)'=x'+y'
(17) (r)'=x
The identities listed in the table apply to single variables or to Boolean
consider the
functions expressed in terms of binary variables. For example,
following Boolean algebra expression:
AB'+ C'D + AB'+ C'D
From identity
By letting x=AB+CDthe expression can be written as x+x.
reduced to
5in Table 2.1 we find that x +x =x. Thus the expression can be
only two terms:
AB'+ CD+A'B+ C'D=AB'+ C'D
and DeMorgan's theorem
DeMorgan's theorem is very important in dealing with NOR
function is
NAND gates. It states that a NOR gate that performs the (x+y)'
equivalent to the function xy. Similarly, a NAND function can be expressed
NAND gates have
by either (xy)' or (x+ ). For this reason the NOR and
Instead of repre
two distinct graphic symbols, as shown in Figs. 2.5 and 2.6.
Senting a NOR gate with an OR graphic symbol followed by a circle, we can
represent it by an AND graphic symbol preceded bycircles in all inputs. The
invert-AND symbol for the NOR gate follows from DeMorgan's theorem and
Irom the convention that small circles denote complementation. Similarly,
the NAND gate has two distinct symbols, as shown in Fig. 2.5.
To see how Boolean algebra manipulation is used to simplify digital
Circuits, consider the logic diagram of Fig. 2.7(a). The output of the circuit
can be expressed algebraically as follows:
F=ABC+ABC'+A'C
OR gate forms the logical
Dach term corresponds to one AND gate, and the complement 4'and C.
needed to
Sum of the three terms. Two inverters are
Ihe expression can be simplified using Boolean algebra.
F=ABC+ABC'+A'C= AB(C +C') +4'C
=AB +A'C
22 Digital Logic Circuits
y
- (xty+z)' Xy=(« tytzy
(a) OR-Invert (b)Invert-AND
FIGURE 2.5 Two graphic symbols for NORgate.
(ryz)' +y td=(ry2)
(a) AND-Invert (b) Invert-OR
FIGURE 2.6 Two graphic symbols for NAND gate.
A
B
(a) F=ABC + ABC'+ A'C
(b) F =AB + A'C
FIGURE 2.7 Two logic diagrams for the same Boolean function.
Note that (C+ C)'=l by identity 7 and AB· l=AB by identity 4in Table 2.1.
The logic diagram of the simplified expression is drawn in Fig.. 2.7(b).
It requires only four gates rather than the six gates used in the circuit o
2.7(a). The two circuits are equivalent and produce the same truth table rela-
tionship between inputs 4, B, Cand output F.
Complement of a Function
The complement of a function F when expressed in a truth table is obtained
by interchanging l's and 0's in the values of F in the truth table. When the
function 1s expressed in algebraic form, the complement of the function
2.4 Map Simplificatio
OR AND
NOT
(b) (c)
(a)
EIGURE 2.8 Realization of NOT, OR, and AND gates using NAND
gates.
general form of
can be derived by means of DeMorgan's theorem. The
DeMorgan's theorem can be expressed as
follows:
(& +x, t xt...*'= xx.
(ay...xy= ttxt...t*,
From the general DeMorgan's theorem we can derive a simple procedure
for obtaining the complement of an algebraic expression. This is done by
changing all OR operations to AND operations and all AND operations
an
OR operations and then complementing each individual letter variable. As
example, consider the followingexpression and its complement:
F=AB+ C'D'+ BD
F=(4'+ B)(C+ D\(B + D')
AND and OR
The complement expression is obtained by interchanging
operations and complementing each individualvariable. Note
that the com
plement of C'is C.
Universal Logic Gates
NAND and NOR
Of allthe logic gates that we discussed in Sec. 2.2, only the
realized using these
gates are called universal gates because any gate can be
realized by using
gates. We show how NOT, OR, and AND gates can be
respectively. We leave it
NAND gates is shown in Fig. 2.8a, 2.8b, and 2.8c, using NOR
andAND gates
as an exercise for the reader to realize NOT, OR,
other gate, it is possitble
gates. As a universal gate can be used to realize any gates. It
or only NOR
to realize any logic function using only NAND gates
not universal logic gates,
gates are
1S easy to see that AND, OR, and NOT
NOT operation cannot be realized using these gates. However, the set of
aS
NOT} and OR, NOT }are called universal set of logic gates as
gates {AND,
using these universal set of gates.
any logic function can be realized
