Chapter 3
Boolean Algebra
and Digital Logic
2
Chapter 3 Objectives
• Relationship between Boolean Algebra and Computer
Circuits
• Design Logic Circuits
• Look at some common Logic Circuits
• Combine Logic Circuits together to accomplish larger
goals
3
3.2 Boolean Algebra
• Boolean algebra is a mathematical system for the
manipulation of variables that can have one of two
values.
– Formal logic uses true and false
– Digital systems use on and off, 1 and 0, or presence
or absence of a voltage difference
• Boolean expressions use Boolean operators on
Boolean variables.
• Boolean functions are functions that take one or
more Boolean variable inputs and output one
Boolean value
4
• A Boolean operator can be described
using a truth table.
– A truth table describes the output of an
expression for each input.
• NOT (¬x) is Boolean negation (x′)
• AND (x∧y) is the Boolean product (xy)
• OR (x∨y) is the Boolean sum (x+y)
• Boolean expressions have defined order
of operations.
3.2 Boolean Algebra
5
3.2 Boolean Algebra
6
3.2 Boolean Algebra
AND OR
Identity Law 1x = x 0+x = x
Null Law 0x = 0 1+x = 1
Idempotent Law xx = x x+x = x
Inverse Law xx′ = 0 x+x′ = 1
Commutative Law xy = yx x+y = y+x
Associative Law (xy)z = x(yz) (x+y)+z = x+(y+z)
Distributive Law x+yz = (x+y)(x+z) x(y+z) = xy+xz
Absorbtion Law x(x+y) = x x+xy = x
DeMorgan’s Law (xy)′ = x′+y′ (x+y)′ = x′y′
Double Compliment Law x′′ = x
7
3.2 Boolean Algebra
8
• Boolean Expressions have two
canonical (normalized) forms.
• Sum of Products
– F(x,y,z) = xy + xz + yz
– F(x,y,z) = xy + z
• Product of Sums
– F(x,y,z) = (x+y)(x+z)(y+z)
– F(x,y,z) = (x+z)(x’+y+z)
3.2 Boolean Algebra
x y z F
product
sum
0 0 0 0 x+y+z
0 0 1 1 x′y′z
0 1 0 0 x+y′+z
0 1 1 1 x′yz
1 0 0 0 x′+y+z
1 0 1 0 x′+y+z′
1 1 0 1 xyz′
1 1 1 1 xyz
9
• We have looked at Boolean functions
in abstract terms.
• Boolean functions are implemented in digital
computer circuits called gates.
3.3 Logic Gates
10
• The three simplest gates are the AND, OR, and NOT
gates.
• They correspond directly to their respective Boolean
operations, as you can see by their truth tables.
3.3 Logic Gates
11
• NAND and
NOR are two
very
important
gates. Their
symbols and
truth tables
are shown at
the right.
3.3 Logic Gates
12
• Another very useful gate is the exclusive OR
(XOR) gate.
• The output of the XOR operation is true only when
the values of the inputs differ.
Note the special symbol
for the XOR operation.
3.3 Logic Gates
13
• Gates can have multiple inputs and more than
one output.
– A second output can be provided for the
complement of the operation.
3.3 Logic Gates
14
• NAND and NOR are known as universal gates
because they are inexpensive to manufacture and
any Boolean function can be constructed using only
NAND or only NOR gates.
3.3 Logic Gates
15
• Logic Gates are composed of
transistors or similar electronic
device.
• Transistors use voltage differences
to control the flow of electricity
3.3 Logic Gates
https://commons.wikimedia.org/w/index.php?curid=2593317
A B Out
Vss Vss Vdd
Vss Vdd Vdd
Vdd Vss Vdd
Vdd Vdd Vss
3.4 Digital Components
• Standard digital
components are
combined into single
integrated circuit
packages.
• Boolean logic can be
used to implement the
desired functions.
16
17
• The circuit below implements the Boolean
function F(x,y,z) = x + y’z:
3.4 Digital Components
3.4 Digital Components
18
19
• A Karnaugh map, or Kmap, is a
graphical representation of a truth
table that can be used help simplify
a Boolean expression
• Kmaps use minterms from canonical
expression forms to determine
• Kmaps have a cell for each minterm.
3A Karnaugh Maps
20
• Let’s use a Kmap to
represent and then simplify
F(x,y) = x + y
• We can simplify by grouping
1s together
• There are specific rules for
grouping
3A Karnaugh Maps
F(x,y)= x+y = x’y+xy’+xy
21
• Consider the function:
• Its Kmap is given below.
3A.3 Kmap Simplification
for Three Variables
F(X,Y,Z)= X’Y’Z + X’YZ + XY’Z + XYZ
22
• Now for a more complicated Kmap. Consider the
function:
3A.3 Kmap Simplification
for Three Variables
F(X,Y,Z)=
X’Y’Z’+ X’Y’Z + X’YZ + X’YZ’+
XY’Z’ + XYZ’
23
• We have populated the Kmap shown below with
the nonzero minterms from the function
3A.3 Kmap Simplification for Four
Variables
24
• It is possible to have a choice as to how to pick
groups within a Kmap, while keeping the groups
as large as possible.
• The (different) functions that result from the
groupings below are logically equivalent.
3A.3 Kmap Simplification for Four
Variables
25
• Real circuits don’t always need to have an output
defined for every possible input.
• If a circuit is designed so that a particular set of
inputs can never happen, we call this set of inputs
a don’t care condition.
• In a Kmap, there are maked with an X
3A.6 Don’t Care Conditions
26
• The truth table of:
differs from the truth table of:
• However, the values for which they differ, are the
inputs for which we have don’t care conditions.
3A.6 Don’t Care Conditions
F(W,X,Y,Z)= W’Y’+ YZ
F(W,X,Y,Z)= W’Z + YZ
27
• Combinational logic circuits
give us many useful devices.
• One of the simplest is the
half adder, which finds the
sum of two bits.
• We can gain some insight as
to the construction of a half
adder by looking at its truth
table, shown at the right.
3.5 Combinational Circuits