
PAGE 1

Ref. Page Chapter 6: Boolean Algebra and Logic Circuits Slide 18
Boo l ea n
A lge bra a n d
'='
Lo gi c circuits
Compu te r Fu n da me n t a ls

PAGE 2

Computer Fundamentals: A. H. M. Saiful Islam
Learning Objectives
In
this chapter you will learn about:
Boolean algebra
Fundamental concepts and basic laws algebra
Boolean function and minimization
Logic gates
•
•
of
Boolean
•
•
•
•
Logic circuits and Boolean expressions
Combinational circuits and design
60
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 2/ 78

PAGE 3

Computer Fundamentals: A. H. M. Saiful Islam
Boolean Algebra
•
•
An algebra that deals with binary number system
George Boole ( 1815 1864), an English mathematician, developed it for:
•
•
Simplifying representation
Manipulation of propositional logic
•
In 1938, Claude E. Shannon proposed using Boolean algebra in
design of relay switching circuits
Provides economical and straightforward approach
•
•
Used extensively in designing electronic circuits used
in computers
60
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 3/ 78

PAGE 4

Computer Fundamentals: A. H. M. Saiful Islam
Fundamental Concepts of Boolean Algebra
• Use of Binary Digit
• Boolean equations can have either of two possible values, 0 and 1
• Logical Addition
• Symbol ‘ ’ , also known as ‘ OR ’ operator, used for logical addition. Follows law of binary addition
• Logical Multiplication
• Symbol ‘ . ’ , also known as ‘ AND ’ operator, used for
logical multiplication.
multiplication
• Complementation
Follows law of binary
• Symbol ‘  ’ , also known as ‘ NOT ’ operator, used for
complementation. Follows law of binary compliment
61
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 4/ 78

PAGE 5

Computer Fundamentals: A. H. M. Saiful Islam
Operator Precedence
Each operator has a precedence level
Higher the operator ’ s precedence level, earlier it is evaluated
Expression is scanned from left to right
First, expressions enclosed within parentheses are evaluated
Then, all complement ( NOT) operations are performed
Then, all ‘ ’ ( AND) operations are performed
•
•
•
•
•
•
•
Finally,
all
‘
’
( OR)
operations
are
performed
( Continued on next slide)
62
Ref.
Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 5/ 78

PAGE 6

Computer Fundamentals: A. H. M. Saiful Islam
Precedence
Operator
( Continued from previous slide..)
1 st
2 nd
3 rd
62
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 6/ 78
X Y Z

PAGE 7

Computer Fundamentals: A. H. M. Saiful Islam
Postulates of Boolean Algebra
Postulate 1:
( a)
( b)
A = 0, if and only if, A is not
A = 1, if and only if, A is not
equal
equal
to
to
1
0
Postulate
2:
0 = x
1 = x
( a)
( b)
x
x
Postulate
3: Commutative
Law
( a)
( b)
x
x
y = y
y = y
x
x
( Continued on next slide)
62
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 7/ 78

PAGE 8

Computer Fundamentals: A. H. M. Saiful Islam
Postulates of Boolean Algebra
( Continued from previous slide..)
Postulate 4:
Associative Law
( a)
( b)
x
x
( y
( y
z) = ( x
z) = ( x
y)
z
z
y)
Postulate 5:
Distributive
Law
( x
( x
( a)
( b)
x
x
( y
( y
z) =
z) =
( x
( x
y)
y)
z)
z)
Postulate 6:
x
( a)
( b)
x
x
= 1
= 0
x
62
Ref. Page
Chapter 6: Boolean Algebra
and Logic Circuits
Slide 8/ 78

PAGE 9

Computer Fundamentals: A. H. M. Saiful Islam
The Principle of Duality
There is a precise duality between the operators
( OR), and the digits 0 and 1.
. ( AND) and
For example, in the table below, the
second row is obtained from
the
and
first row and
‘ 0 ’ wit h ‘ 1’
vice
versa
simply
by
interchanging
‘ ’
with
‘.’
Therefore,
if a
particular
theorem
is
proved,
its dual
theorem
automatically holds and need not be proved separately
63
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 9/ 78
Column 1
Column 2
Column 3
Row 1
1 1 = 1
1 0 = 0 1 = 1
0 0 = 0
Row 2
0 0 = 0
0 1 = 1 0 = 0
1 1 = 1

PAGE 10

Computer Fundamentals: A. H. M. Saiful Islam
Some
Important
Theorems
of
Boolean
Algebra
63
Ref. Page
Chapter 6:
Boolean Algebra and Logic Circuits
Slide 10/ 78
Sr. No.
Theorems/ Identities
Dual Theorems/ Identities
Name
( if any)
1
x x = x
x x = x
Idempotent Law
2
x 1 = 1
x 0 = 0
3
x x y = x
x x y = x
Absorption Law
4
x = x
Involution Law
5
x x y = x y
x x y = x y
6
x y = x y
x y = x y
De Morgan ’s
Law

PAGE 11

Computer Fundamentals: A. H. M. Saiful Islam
Methods of Proving Theorems
The
theorems of Boolean algebra may be proved by
using
one
of
the following methods:
1.
By using postulates to show that L. H. S. = R. H. S
2.
By Perfect Induction or Exhaustive Enumeration
method
where all possible combinations of variables involved in
L. H. S. and R. H. S. are checked to yield identical results
3.
By the Principle of Duality where the dual
of an
proof
already
proved
theorem
is
derived
from
the
of
its
corresponding pair
63
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 11/ 78

PAGE 12

Computer Fundamentals: A. H. M. Saiful Islam
Proving a Theorem
( Example)
by
Using
Postulates
Theorem:
x x
·
y =
x
Proof:
L. H. S.
=
=
=
=
=
=
=
x
x x x x x
x
1 ( 1 ( y
1
y
x
y)
1)
y
by
by by by by
postulate
postulate postulate
2( b)
5( a)
3( a)
theorem 2( a)
postulate 2( b)
R. H. S.
64
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 12/ 78

PAGE 13

Computer Fundamentals: A. H. M. Saiful Islam
Proving a Theorem
( Example)
Theorem:
by
Perfect
Induction
x
x
·
y
=
x
=
64
Ref. Page
Chapter
6: Boolean Algebra and Logic Circuits
Slide 13/ 78
x
y
x · y
x x · y
0
0
0
0
0
1
0
0
1
0
0
1
1
1
1
1

PAGE 14

Computer Fundamentals: A. H. M. Saiful Islam
by the
( Example)
Proving a Theorem
Principle of Duality
Theorem:
x x = x
Proof:
L. H. S.
=
=
=
=
=
=
=
x
( x ( x x
x
x
x
x)
x)
1
( x
by
by by by
by
postulate
postulate postulate postulate
postulate
2( b)
6( a)
5( b)
6( b)
2( a)
X )
x
0
X
R. H. S.
( Continued on next slide)
63
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 14/ 78

PAGE 15

Computer Fundamentals: A. H. M. Saiful Islam
by the
( Example)
Proving a Theorem
Principle of Duality
( Continued from previous slide..)
Dual Theorem:
x x =
x
Proof:
L. H. S.
=
=
=
=
=
=
=
x
x x x x
x
x
x x ( x
1
Notice that each step of
the proof of the dual theorem is derived from the proof of its corresponding pair in
the original theorem
0
x
by
by by by
by
postulate
postulate postulate postulate
postulate
2( a)
6( b)
5( a)
6( a)
2( b)
X
X )
R. H. S.
63
Ref. Page
Chapter
6: Boolean Algebra and Logic
Circuits
Slide 15/ 78

PAGE 16

Computer Fundamentals: A. H. M. Saiful Islam
Boolean Functions
• A Boolean function is an expression formed with:
• Binary variables
• Operators ( OR, AND, and NOT)
• Parentheses, and equal sign
• The value of a Boolean function can be either
0
or
1
• A
Boolean function may be represented
as:
An algebraic expression, or
•
A truth table
•
67
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 16/ 78

PAGE 17

Computer
Representation as an
Algebraic Expression
Fundamentals: A. H. M. Saiful Islam
W = X
Y
· Z
• Variable
W
is
a
function
of
X,
Y,
and
Z,
can also
be
written as W = f ( X, Y, Z)
• The
RHS of the equation is called an
expression
• The
symbols X, Y, Z are the literals
of the function
• For
one
a given Boolean function,
algebraic expressions
there
may
be
more
than
67
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 17/ 78

PAGE 18

Computer Fundamentals: A. H. M. Saiful Islam
Representation
as
a
Truth
Table
( Continued on next slide)
67
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 18/ 78
X
Y
Z
W
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1

PAGE 19

Computer Fundamentals: A. H. M. Saiful Islam
Representation as a Truth Table
( Continued from previous slide..)
• The
n is
number of rows in the table is equal to 2 n , where
the number of literals in the function
• The
are
combinations of 0s
and 1s for rows
of this table
obtained
from
1
the
binary
numbers
by
counting
from
0
to
2 n

67
Ref. Page
Chapter 6: Boolean Algebra and
Logic Circuits
Slide 19/ 78

PAGE 20

Computer Fundamentals: A. H. M. Saiful Islam
Minimization of Boolean Functions
• Minimization of Boolean functions deals with
• Reduction in number of literals
• Reduction in number of terms
• Minimization is achieved through manipulating
expression to obtain equal and simpler
expression( s)
( having
fewer
literals
and/ or
terms)
( Continued on next slide)
68
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 20/ 78

PAGE 21

Computer Fundamentals: A. H. M. Saiful Islam
Minimization of Boolean
( Continued from previous slide..)
Functions
F 1
= x
y
z
x
y
z
x
y
F 1 has 3 literals ( x, y, z) and
3 terms
F
= x
y
x
z
2
F 2 has 3 literals ( x, y, z) and 2 terms
F 2 can be realized with fewer electronic components,
resulting in a cheaper circuit
( Continued on next slide)
68
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 21/ 78

PAGE 22

Computer Fundamentals: A. H. M. Saiful Islam
Minimization
( Continued from previous slide..)
of
Boolean
Functions
Both F 1 and
F 2 produce the same result
68
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 22/ 78
x
y
z
F 1
F 2
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
0
0

PAGE 23

Computer Fundamentals: A. H. M. Saiful Islam
Try out some
Minimization
Boolean
Function
( a )
( b )
( c )
( d )
( e )
x
x
x
y
y
x
x
x
x
y
y
z
x
z
y
z
x
y
x
y
z
z
y
x
y
z
69
Ref. Page
Chapter 6:
Boolean Algebra and Logic Circuits
Slide 23/ 78

PAGE 24

Computer Fundamentals: A. H. M. Saiful Islam
Complement of a Boolean Function
• The complement of a Boolean function is obtained by
interchanging:
Operators OR and AND
•
Complementing each literal
•
• This is based
on
De
Morgan ’ s theorems ,
whose
general form is:
A 1 A 2 A 3 ... A n = A 1 A 2 A 3 ... A n
A 1 A 2 A 3 ... A n = A 1 A 2 A 3 ... A n
70
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 24/ 78

PAGE 25

Computer Fundamentals: A. H. M. Saiful Islam
Complementing a Boolean Function ( Example)
F 1 = x
y
z x y
z
To obtain
F 1 ,
we first interchange the OR and
the
AND
operators giving
x y z
x y z
Now
we complement each
literal
giving
F 1 =
x y z
x y z
71
Ref. Page
Chapter 6: Boolean Algebra
and Logic Circuits
Slide 25/ 78

PAGE 26

Computer Fundamentals: A. H. M. Saiful Islam
Canonical Forms of Boolean Functions
Minterms
:
n variables forming an AND term, with
each variable being primed or unprimed,
provide
2 n
possible combinations called
minterms or standard products
Maxterms
:
n variables forming an OR term, with
each variable being primed or unprimed,
provide
2 n
possible combinations
called
maxterms
or
standard
sums
71
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 26/ 78

PAGE 27

Computer Fundamentals: A. H. M. Saiful Islam
Minterms
and
Maxterms
for
three
Variables
7
7
Note that each minterm is the complement of
its corresponding
maxterm and vice versa
71
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 27/ 78
Variables
Minterms
Maxterms
x
y
z
Term
Designation
Term
Designation
0
0
0
x y z
m 0
x y z
M 0
0
0
1
x y z
m 1
x y z
M 1
0
1
0
x y z
m 2
x y z
M 2
0
1
1
x y z
m 3
x y z
M 3
1
0
0
x y z
m 4
x y z
M 4
1
0
1
x y z
m 5
x y z
M 5
1
1
0
x y z
m 6
x y z
M 6
1
1
1
x y z
m
x y z
M

PAGE 28

Computer Fundamentals: A. H. M. Saiful Islam
Sum of Products ( SOP) Expression
A sum of products ( SOP) expression is a product term
( minterm)
or
several
product
terms
( minterms)
are:
logically
added
( ORed)
together.
Examples
x
x y
x y
z
x
x
y z
x
y x
y
y
x
y
z
72
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 28/ 78

PAGE 29

Computer Fundamentals: A. H. M. Saiful Islam
Steps to Express a Boolean Function
in
its Sum of Products Form
1.
Construct a
function
truth table
for the
given
Boolean
2.
Form
a
minterm
for
each combination
of
the
variables, which produces a 1 in the
function
3.
The desired expression is
the
2
sum
( OR)
of
all
the
minterms
obtained
in
Step
72
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 29/ 78

PAGE 30

Computer Fundamentals: A. H. M. Saiful Islam
Expressing a Function in its
Sum of Products
Form
( Example)
The following
001,
3 combinations of the variables
produce a 1:
100,
and
111
( Continued on next slide)
73
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 30/ 78
x
y
z
F 1
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1

PAGE 31

Computer Fundamentals: A. H. M. Saiful Islam
Expressing a Function in its
Sum of Products Form ( Example)
( Continued from previous slide..)
• Their corresponding minterms are:
x
y
z,
x y z,
and
x y z
• Taking the
OR of these minterms, we get
F 1 = x
y
z x
y
z x
y
z = m 1 m 4
m 7
F 1
x
y
z
=
1, 4,7
72
Ref. Page
Chapter 6:
Boolean Algebra and Logic Circuits
Slide 31/ 78

PAGE 32

Computer Fundamentals: A. H. M. Saiful Islam
Product of Sums
( POS) Expression
A
product of sums
( POS)
expression
is
a
sum
term
( maxterm) or several sum
terms ( maxterms) logically
multiplied ( ANDed)
together. Examples are:
x y
x y
x y
x
x y
x y
x y z
x y
z
x y
x y
74
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 32/ 78

PAGE 33

Computer Fundamentals: A. H. M. Saiful Islam
Steps to Express a Boolean Function
in
its
Product of Sums Form
1.
Construct a truth table for the given Boolean function
2.
Form a maxterm for each combination
which produces a 0 in the function
of the variables,
3.
The desired expression is the
product
( AND)
of
all
the
maxterms
obtained
in
Step
2
74
Ref. Page
Chapter 6: Boolean Algebra
and
Logic Circuits
Slide 33/ 78

PAGE 34

Computer Fundamentals: A. H. M. Saiful Islam
Expressing a Function in
its
Product of Sums
Form
The following 5 combinations
of variables
produce a 0:
•
000,
010,
011,
101,
and
110
( Continued on next slide)
73
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 34/ 78
x
y
z
F 1
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1

PAGE 35

Computer Fundamentals: A. H. M. Saiful Islam
Expressing a Function in its
Product of Sums Form
( Continued from previous slide..)
Their corresponding maxterms are:
•
x y
z
,
x y z
, x y z
,
x y
z
and
x y z
Taking the
AND of these maxterms, we get:
•
F 1
=
x y z
x y z
x y z
x y z
x y z = M 0 M 2 M 3
M 5 M 6
F 1
x, y, z
= Ð
0,2,3,5,6
74
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 35/ 78

PAGE 36

= Ó
Computer Fundamentals: A. H. M. Saiful Islam
Conversion Between Canonical Forms ( Sum of Products and Product of Sums)
To
convert from
one
canonical
form
to
another,
missing
interchange the symbol and
from the original form.
list
those numbers
Example:
F
x, y, z
= Ð
0,2,4,5
= Ó
1,3,6,7
F
x, y, z
1,4,7 = Ó
0,2,3,5,6
76
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 36/ 78

PAGE 37

Computer Fundamentals: A. H. M. Saiful Islam
Logic Gates
• Logic
gates are
electronic
circuits
that
operate
on
one or more input signals to produce standard output
signal
• Are
the building blocks of all
the
circuits
in
a
computer
• Some of the most basic and useful
logic
gates
are
AND,
OR,
NOT,
NAND
and
NOR
gates
77
Ref. Page
Chapter 6: Boolean Algebra and
Logic Circuits
Slide 37/ 78

PAGE 38

Computer Fundamentals: A. H. M. Saiful Islam
AND Gate
• Physical
operation
realization
of
logical
multiplication
( AND)
• Generates
an
also
output
1
signal
of
1
only
if
all
input
signals
are
77
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 38/ 78

PAGE 39

Computer Fundamentals: A. H. M. Saiful Islam
AND Gate
( Block
Table)
Diagram
Symbol
and
Truth
A
B
C
=
A
B
77
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 39/ 78
Inputs
Output
A
B
C = A B
0
0
0
0
1
0
1
0
0
1
1
1

PAGE 40

Computer Fundamentals: A. H. M. Saiful Islam
OR Gate
• Physical realization of logical addition ( OR)
operation
• Generates an output signal
of
1
if
at
least
one
of
the
input
signals
is
also
1
77
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 40/ 78

PAGE 41

Computer Fundamentals: A. H. M. Saiful Islam
OR Gate ( Block Diagram
Symbol
and
Truth
Table)
A
B
C
=
A
B
78
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 41/ 78
Inputs
Output
A
B
C = A B
0
0
0
0
1
1
1
0
1
1
1
1

PAGE 42

Computer Fundamentals: A. H. M. Saiful Islam
NOT Gate
• Physical realization of
complementation operation
• Generates an output
signal,
which
is
the
reverse
of
the
input
signal
78
Ref. Page
Chapter 6: Boolean Algebra and Logic
Circuits
Slide 42/ 78

PAGE 43

Computer Fundamentals: A. H. M. Saiful Islam
NOT Gate ( Block Diagram
Symbol
and
Truth
Table)
A
A
79
Ref. Page
Chapter 6: Boolean Algebra
and Logic Circuits
Slide 43/ 78
Input
Output
A
A
0
1
1
0

PAGE 44

Computer
Fundamentals: A. H. M. Saiful Islam
NAND Gate
• Complemented AND gate
• Generates an output signal
of:
1
if any one of the inputs is
a
0
•
0
when
all
the
inputs
are
1
•
79
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 44/ 78

PAGE 45

Computer Fundamentals: A. H. M. Saiful Islam
NAND Gate ( Block
Diagram
Symbol
and
Truth
Table)
A
B
C= A
B = A
B = A B
79
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 45/ 78
Inputs
Output
A
B
C = A B
0
0
1
0
1
1
1
0
1
1
1
0

PAGE 46

Computer Fundamentals: A. H. M. Saiful Islam
NOR Gate
• Complemented OR gate
• Generates an output signal of:
1
only when all inputs are 0
•
0
if
any
one
of
inputs
is
a
1
•
79
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 46/ 78

PAGE 47

Computer Fundamentals: A. H. M. Saiful Islam
NOR Gate
( Block
Table)
Diagram
Symbol
and
Truth
A
B
C= A
B = A
B = A
B
80
Ref. Page
Chapter 6:
Boolean Algebra and Logic Circuits
Slide 47/ 78
Inputs
Output
A
B
C = A B
0
0
1
0
1
0
1
0
0
1
1
0

PAGE 48

Computer Fundamentals: A. H. M. Saiful Islam
Logic Circuits
• When
logic gates are interconnected to form a gating /
logic network, it is known as a combinational logic circuit
• The Boolean algebra expression for a given logic circuit
can be derived by systematically progressing from input to output on the gates
• The three logic gates ( AND, OR, and NOT) are logically
complete
because
any
Boolean
expression
can
gates
be
realized
as
a
logic
circuit
using
only
these
three
80
Ref. Page
Chapter 6: Boolean Algebra and Logic Circuits
Slide 48/ 78

PAGE 49

Computer Fundamentals: A. H. M. Saiful Islam
Finding Boolean Expression
of
a
Logic
Circuit
( Example
1)
A
A
NOT
D= A.
B
C
AND
B
C
OR
Ref. Page
80
Chapter 6: Boolean Algebra and Logic Circuits
Slide 49/ 78
B C

PAGE 50

Computer Fundamentals: A. H. M. Saiful Islam
Finding Boolean Expression
of
a
Logic Circuit
( Example
2)
OR
A
B
A
B
C=
A B
A
B
AND
A
B
NOT
AND
Ref.
Page
81
Chapter 6: Boolean Algebra and Logic Circuits
Slide
50/ 78
A B

PAGE 51

Computer Fundamentals: A. H. M. Saiful Islam
Constructing a Logic Circuit from
Expression ( Example 1)
a
Boolean
A
B C
Boolean
Expression =
AND
A
B
A
B
A
B C
C
OR
Ref. Page
83
Chapter 6: Boolean Algebra and Logic Circuits
Slide 51/ 78

PAGE 52

Computer Fundamentals: A. H. M. Saiful Islam
Constructing a Logic Circuit from a Boolean
Expression ( Example 2)
Boolean Expression =
A B C
D E
F
AND
NOT
A
B
A
B
A B
AND
AND
C
D
C
D
A
B C
D E
F
AND
E
F
E
F
E F
NOT
Ref. Page
83
Chapter 6: Boolean Algebra and Logic Circuits
Slide 52/ 78

PAGE 53

Computer Fundamentals: A. H. M. Saiful Islam
Universal NAND Gate
NAND
gate
is
to
an
universal
gate, it
any
is
alone
•
sufficient
expression
implement
Boolean
To
understand this, consider:
•
Basic logic gates ( AND, OR, and
logically complete
NOT) are
•
Sufficient to show that AND, OR, and NOT
•
gates
gates
can
be
implemented
with
NAND
Ref. Page
84
Chapter 6: Boolean Algebra and Logic Circuits
Slide 53/ 78

PAGE 54

Computer Fundamentals: A. H. M. Saiful Islam
Implementation of NOT, AND and OR
Gates
by
NAND
Gates
A
A = A A = A
A
( a) NOT gate
implementation.
A
B
A
B
A
B
A
B
( b) AND
gate
implementation.
( Continued on next slide)
Ref. Page
85
Chapter 6: Boolean Algebra and Logic Circuits
Slide 54/ 78

PAGE 55

Computer Fundamentals: A. H. M. Saiful Islam
Implementation of NOT,
NAND Gates
( Continued from previous slide..)
AND
and
OR
Gates by
A
A = A
A
A
B
A
B
A
B
B
( c)
OR
gate
implementation.
Ref. Page
85
Chapter
6: Boolean Algebra and Logic Circuits
Slide 55/ 78
B B = B

PAGE 56

Computer Fundamentals: A. H. M. Saiful Islam
Method of Implementing a Boolean Expression with Only NAND Gates
Step
1:
From
the
given
algebraic
expression,
draw
the logic
diagram with AND, OR, and NOT gates. Assume that
both the normal
available
( A) and complement ( A )
inputs are
Step
2:
Draw a second logic diagram with the equivalent NAND
logic substituted for
each AND, OR, and NOT gate
Step
3:
Remove
diagram
all
as
pairs
double
of
cascaded
inverters
from
the
any
inversion does
not perform
logical
single
function. Also
remove
inverters
connected
to
the
external
inputs
and
complement
corresponding input variable
Ref. Page
85
Chapter 6: Boolean Algebra and Logic Circuits
Slide 56/ 78

PAGE 57

Computer Fundamentals: A. H. M. Saiful Islam
Implementing a Boolean
NAND Gates ( Example)
Expression with
Only
A
B
C
A B D
Boolean
Expression
=
A
A B
A
B
C
A
B
D
B
B
D A
C
B
D
A B
D
C A B D
( a)
Step 1:
AND/ OR implementation
( Continued on next slide)
Ref. Page
87
Chapter 6: Boolean Algebra and Logic Circuits
Slide 57/ 78

PAGE 58

Computer Fundamentals: A. H. M. Saiful Islam
Implementing a Boolean
NAND Gates ( Example)
( Continued from previous slide..)
Expression
with
Only
AND
OR
A
B
B
D
A B C
A B
D
A
4
C
C A B D
( b) Step 2: Substituting
equivalent NAND functions
( Continued on next slide)
Ref. Page
87
Chapter 6: Boolean Algebra and Logic Circuits
Slide 58/ 78
2
A
1
A B
5
AND OR
BD
3
AND
A BD

PAGE 59

Computer Fundamentals: A. H. M. Saiful Islam
Implementing a Boolean
Expression with
Only
NAND Gates
( Continued from previous slide..)
( Example)
A
1
B
A
B C
A B
D
5
B
D
2
3
A
C
4
( c)
Step 3: NAND
implementation.
Ref. Page
87
Chapter 6: Boolean Algebra and Logic Circuits
Slide 59/ 78

PAGE 60

Computer Fundamentals: A. H. M. Saiful Islam
Universal NOR Gate
NOR gate is an universal gate, it is alone sufficient to
implement any Boolean expression
•
To understand this, consider:
•
Basic logic gates ( AND, OR, and NOT) are logically
complete
•
Sufficient to show that AND, OR,
and
NOT
gates
can
•
be
implemented
with
NOR
gates
Ref. Page
89
Chapter 6: Boolean Algebra and Logic Circuits
Slide
60/ 78

PAGE 61

Computer Fundamentals: A. H. M. Saiful Islam
Implementation of NOT, OR and AND
Gates
by
NOR
Gates
A
A = A
A = A
A
( a) NOT gate
implementation.
A
B
A
B
A
B
A
B
( b) OR gate
implementation.
( Continued on next slide)
Ref. Page
89
Chapter 6: Boolean Algebra and Logic Circuits
Slide 61/ 78

PAGE 62

Computer Fundamentals: A. H. M. Saiful Islam
Implementation of NOT,
NOR Gates
( Continued from previous slide..)
OR
and AND
Gates by
A
A = A
A
A B
A
B
A
B
B
( c)
AND
gate
implementation.
Ref. Page
89
Chapter 6: Boolean Algebra and Logic Circuits
Slide 62/ 78
B B = B

PAGE 63

Computer Fundamentals: A. H. M. Saiful Islam
Method of Implementing a Boolean Expression with Only NOR Gates
Step
1:
For
the
given
algebraic
expression,
draw
the logic
diagram
both the available
with AND,
OR, and NOT gates. Assume that
normal
and complement
A
inputs are
A
Step
2:
Draw a second logic
substituted for each
diagram with equivalent NOR logic
AND, OR, and NOT gate
Step
3:
Remove
diagram
all parts of
cascaded
inverters
from
the
any
as
double
inversion does
not perform
logical
single
function. Also
remove
inverters
connected
to
the
external
inputs
and
complement
corresponding input variable
Ref. Page
89
Chapter 6: Boolean Algebra and Logic Circuits
Slide 63/ 78

PAGE 64

Computer Fundamentals: A. H. M. Saiful Islam
Implementing a Boolean Expression
NOR Gates ( Examples)
( Continued from previous slide..)
with
Only
A
B C
A B
D
Boolean
Expression
=
A
A B
B
A B C
A B
D
B
D A
C
B
D
A B D
C
A B
D
( a)
Step 1: AND/ OR implementation.
( Continued on next slide)
Ref. Page
90
Chapter 6: Boolean Algebra and Logic Circuits
Slide 64/ 78

PAGE 65

Computer Fundamentals: A. H. M. Saiful Islam
Implementing a Boolean Expression
with
Only
NOR Gates
( Continued from previous slide..)
( Examples)
AN
D
A
A
B
1
OR
B
A
B C
A B
D
5
6
AN
D
B
B
D
2
D
OR
AN
D
A
4
C
A B D
C
A B D
Substituting equivalent
( b)
Step 2:
NOR
functions.
( Continued on next slide)
Ref. Page
90
Chapter 6: Boolean Algebra and Logic Circuits
Slide 65/ 78
3

PAGE 66

Computer Fundamentals: A. H. M. Saiful Islam
Implementing a Boolean
Expression with
Only
NOR Gates
( Continued from previous slide..)
( Examples)
A
B
1
A B C
A B
D
6
5
B
D
A
2
3
4
C
( c)
Step
3:
NOR
implementation.
Ref. Page
91
Chapter 6: Boolean Algebra and Logic Circuits
Slide 66/ 78

PAGE 67

Computer Fundamentals: A. H. M. Saiful Islam
Exclusive OR Function
A
B
= A
B
A
B
A B
C = A
B = A
B A B
A
B
C =
A
B = A
B A B
Also,
A
B
C =
A
B
C = A
B
C
( Continued on next slide)
Ref. Page
91
Chapter
6: Boolean Algebra and Logic Circuits
Slide 67/ 78

PAGE 68

Computer Fundamentals: A. H. M. Saiful Islam
Exclusive OR
( Continued from previous slide..)
Function
( Truth
Table)
Ref. Page
92
Chapter 6: Boolean Algebra and Logic Circuits
Slide 68/ 78
Inputs
Output
A
B
C = A B
0
0
0
0
1
1
1
0
1
1
1
0

PAGE 69

ƒn ƒn
Computer Fundamentals: A. H. M. Saiful Islam
Equivalence Function
Symbol
with
Block
Diagram
0
A
B
=
A
B
A
B
A B
A
B A B
C =
A 0 B =
Also,
( A 0 B)
0 = A 0
( B
0 C) =
A
0 B 0
C
( Continued on next slide)
Ref. Page
91
Chapter 6: Boolean Algebra and
Logic Circuits
Slide 69/ 78

PAGE 70

Computer Fundamentals: A. H. M. Saiful Islam
Equivalence
Function
( Truth
Table)
Ref. Page
92
Chapter 6: Boolean Algebra and Logic Circuits
Slide 70/ 78
Inputs
Output
A
B
C = A 0 B
0
0
1
0
1
0
1
0
0
1
1
1

PAGE 71

Computer Fundamentals: A. H. M. Saiful Islam
Steps in Designing Combinational Circuits
1.
State the given problem completely and exactly
2.
Interpret the problem and determine the available input
variables and required output variables
3.
Assign a letter symbol to each input and output variables
4.
Design the truth table that defines the required relations
between inputs and outputs
5.
Obtain the simplified Boolean function for each output
6.
Draw the logic circuit diagram to implement the Boolean
function
Ref. Page
93
Chapter 6: Boolean Algebra and Logic Circuits
Slide 71/ 78

PAGE 72

Computer Fundamentals: A. H. M. Saiful Islam
Designing a Combinational Circuit
Example
1
–
Half Adder
Design
S = A B A B
C = A B
Boolean
functions
for the two outputs.
Ref. Page
93
Chapter 6: Boolean Algebra and Logic Circuits
Slide 72/ 78
Inputs
Outputs
A
B
C
S
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0

PAGE 73

Computer Fundamentals: A. H. M. Saiful Islam
Designing a Combinational Circuit
Example 1
( Continued from previous slide..)
–
Half Adder
Design
A
A B
A
S
=
A
B A
B
B
B
A B
A
B
C
= A B
Logic circuit
diagram to
implement the Boolean functions
Ref. Page
94
Chapter 6: Boolean Algebra and Logic Circuits
Slide 73/ 78

PAGE 74

Computer Fundamentals: A. H. M. Saiful Islam
Designing a Combinational Circuit
Example
2
–
Full Adder
Design
Truth table for a full adder
( Continued on next slide)
Ref. Page
94
Chapter 6: Boolean Algebra and Logic Circuits
Slide 74/ 78
Inputs
Outputs
A
B
D
C
S
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1

PAGE 75

Computer Fundamentals: A. H. M. Saiful Islam
Designing a Combinational Circuit
Example 2 – Full Adder Design
( Continued from previous slide..)
Boolean functions for the two outputs:
S = A
B D A B D A B D A B D
C = A
= A
B D A B D A B D A B D
B A
D B
D
( when
simplified)
( Continued on next slide)
Ref. Page
95
Chapter 6: Boolean Algebra and Logic Circuits
Slide 75/ 78

PAGE 76

Computer Fundamentals: A. H. M. Saiful Islam
Designing a Combinational Circuit
Example 2
( Continued from previous slide..)
–
Full Adder Design
A
A
B
D
B
D
A B
D
S
A
B D
A B
D
( a)
Logic
circuit diagram
for sums
( Continued on next slide)
Ref. Page
95
Chapter 6: Boolean Algebra and
Logic Circuits
Slide 76/ 78
A B D
A B D
A B D

PAGE 77

Computer Fundamentals: A. H. M. Saiful Islam
Designing a Combinational Circuit
Example 2
( Continued from previous slide..)
–
Full Adder Design
A
B
A
B
A
D
C
A
D
B
D
( b)
Logic circuit diagram
for
carry
Ref. Page
95
Chapter 6: Boolean Algebra and Logic Circuits
Slide 77/ 78
B D

PAGE 78

Computer Fundamentals: A. H. M. Saiful Islam
Key Words/ Phrases
•
•
•
•
•
•
•
•
Absorption law
AND gate
Associative law
Boolean algebra Boolean expression Boolean functions Boolean identities Canonical forms for
Boolean functions
Combination logic circuits
Cumulative law
Complement of a function
Complementation
De Morgan ’s law Distributive law Dual identities
•
•
•
Equivalence function
Exclusive OR function
Exhaustive enumeration method
Half adder Idempotent law Involution law Literal
Logic circuits
Logic gates Logical addition Logical multiplication Maxterms
Minimization of Boolean
functions Minterms NAND gate
•
•
•
•
•
NOT gate
Operator precedence
OR gate
Parallel Binary Adder Perfect induction method
Postulates of Boolean algebra
Principle of duality Product of Sums expression Standard forms Sum of Products
expression
Truth table
Universal NAND gate
Universal NOR gate
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Ref.
Page
97
Chapter 6: Boolean Algebra and Logic Circuits
Slide 78/ 78
Back to top of page