Transcript Chapter 3.5
Chapter 3.5
Logic Circuits
How does Boolean algebra relate
to computer circuits?
Data is stored and manipulated in a computer as
a binary number.
Individual bits of the number are represented
with two different voltage levels, 0 and 1.
Bits are combined using complicated circuits to
do operations such as integer arithmetic.
Example: Add 75 and 3
Given a string, 0000000001001011 and a string
0000000000000011 it creates the string
0000000001001110.
This is accomplished using simple circuits called “gates”.
“And” Gate
Wires labeled a and b contain an “input”
voltage that either represents “1” or “0”. The
“output” voltage, labeled a b is given by this
“truth table”:
a
0
0
1
1
b
0
1
0
1
a b
0
0
0
1
“Or” Gate
Wires labeled a and b contain an “input”
voltage that either represents “1” or “0”. The
“output” voltage, labeled a b is given by this
“truth table”:
a
b
a+b
0
0
0
0
1
1
1
0
1
1
1
1
“Inverter” Gate
A wire labeled a
contains an “input”
voltage that either
represents “1” or “0”.
The “output” voltage,
labeled a’ is given by
this “truth table”:
a
1
a’
0
0
1
Building a logic circuit
Using the “and”, “or”, and “inverter” gates,
we can design more complicated circuits.
Consider the following circuit. What outputs will be
obtained for different combinations of input?
a
b
1
1
1
0
0
1
0
0
How many gates are there?
In the previous example there was a twoinput or gate, a two-input and gate, and a
not gate.
Is there an equivalent circuit which uses
less gates?
Write the Boolean algebra expression which
corresponds to the following circuit:
Use the laws of Boolean algebra to
simplify the last expression.
How many gates can be saved?
Write the Boolean algebra expression which
corresponds to the following circuit:
Use the laws of Boolean algebra to
simplify the last expression.
How many gates can be saved?
Sums of Products
Two examples of sums of products are
xy’+yx’ and xy’z + x’y’z + x’y’z’
Karnaugh maps is a useful graphical
technique for simplifying Boolean algebra
expressions such as these and they give
the simplest possible sums-of-products
expression.
Simplify xy’ + x’y’ using a Karnaugh map
Check the boxes that
correspond to xy’ and x’y’.
Circle any rectangle shapes
formed by the checks.
Determine the variable that will
not appear in the simplified
answer.
Simplify x’y + x’y’ + xy using a Karnaugh map
Karnaugh maps for 3 variables
Use the map shown.
Along the top, labels that are
side by side differ in exactly
one of the two variables.
Check the appropriate boxes.
Note: 1x1 squares do not
remove any variables; a
vertical or horizontal circle of
“area 2” removes one variable.
Simplify x’yz + x’yz’ + xyz’+ x’y’z using a
Karnaugh map
Simplify x’y’z + x’yz’ + x’yz + xy’z + xyz using a
Karnaugh map
What is the simplified
expression?
Is yz+y’z+x’y the
simplest expression?
Simplify x’y’z + x’yz’ + x’yz + xy’z + xyz using a
Karnaugh map
Note: yz+y’z+x’y is
NOT the simplest
expression.
What is the simplified
expression?
Guidelines for choosing rectangles:
Choose rectangles so that the number of
rectangles is as small as possible and
each individual rectangle is as large as
possible (but sides of length 3 are not
allowed.)
Simplify xy’z’ + x’z + xy using a Karnaugh
map