Chapter 3

Boolean Algebra and

Digital Logic
Objectives

 Understand the relationship between Boolean logic

and digital computer circuits.
 Learn how to design simple logic circuits.
 Understand how digital circuits work together to
form complex computer systems.

2
1 Introduction

 In the latter part of the nineteenth century, George

Boole incensed philosophers and mathematicians
alike when he suggested that logical thought could
be represented through mathematical equations .
 How dare anyone suggest that human thought could be
encapsulated and manipulated like an algebraic formula?
 Computers, as we know them today, are
implementations of Boole’s Laws of Thought.
 John Atanasoff and Claude Shannon were among the first
to see this connection.

3
Introduction

 In the middle of the twentieth century, computers

were commonly known as “thinking machines” and
“electronic brains.”
 Many people were fearful of them.
 Nowadays, we rarely ponder the relationship
between electronic digital computers and human
logic. Computers are accepted as part of our lives.
 Many people, however, are still fearful of them.
 In this chapter, you will learn the simplicity that
constitutes the essence of the machine.

4
2 Boolean Algebra

 Boolean algebra is a mathematical system for

the manipulation of variables that can have
one of two values.
 In formal logic, these values are “true” and “false.”
 In digital systems, these values are “on” and “off,”
1 and 0, or “high” and “low.”
 Boolean expressions are created by
performing operations on Boolean variables.
 Common Boolean operators include AND, OR, and
NOT.

5
2 Boolean Algebra

 A Boolean operator can be

completely described using a
truth table.
 The truth table for the Boolean
operators AND and OR are
shown at the right.
 The AND operator is also known
as a Boolean product. The OR
operator is the Boolean sum.

6
2 Boolean Algebra

 The truth table for the

Boolean NOT operator is
shown at the right.
 The NOT operation is most
often designated by an
overbar. It is sometimes
indicated by a prime mark
( ‘ ) or an “elbow” ().

7
2 Boolean Algebra

 A Boolean function has:

 At least one Boolean variable,
 At least one Boolean operator, and
 At least one input from the set {0,1}.
 It produces an output that is also a member of
the set {0,1}.

Now you know why the binary numbering system is so handy in digital

systems.

8
2 Boolean Algebra

 The truth table for the

Boolean function:

is shown at the right.

 To make evaluation of the
Boolean function easier,
the truth table contains
extra (shaded) columns to
hold evaluations of
subparts of the function.
9
2 Boolean Algebra

 As with common
arithmetic, Boolean
operations have rules of
precedence.
 The NOT operator has
highest priority, followed
by AND and then OR.
 This is how we chose the
(shaded) function
subparts in our table.

10
2 Boolean Algebra

 Digital computers contain circuits that implement

Boolean functions.
 The simpler that we can make a Boolean function,
the smaller the circuit that will result.
 Simpler circuits are cheaper to build, consume less
power, and run faster than complex circuits.
 With this in mind, we always want to reduce our
Boolean functions to their simplest form.
 There are a number of Boolean identities that help
us to do this.

11
2 Boolean Algebra

 Most Boolean identities have an AND (product)

form as well as an OR (sum) form. We give our
identities using both forms. Our first group is rather
intuitive:

12
2 Boolean Algebra

 Our second group of Boolean identities should be

familiar to you from your study of algebra:

13
2 Boolean Algebra

 Our last group of Boolean identities are perhaps the

most useful.
 If you have studied set theory or formal logic, these
laws are also familiar to you.

14
2 Boolean Algebra

 We can use Boolean identities to simplify the

function:
as follows:

15
2 Boolean Algebra

 Sometimes it is more economical to build a

circuit using the complement of a function (and
complementing its result) than it is to implement
the function directly.
 DeMorgan’s law provides an easy way of finding
the complement of a Boolean function.
 Recall DeMorgan’s law states:

16
2 Boolean Algebra

 DeMorgan’s law can be extended to any number of

variables.
 Replace each variable by its complement and
change all ANDs to ORs and all ORs to ANDs.
 Thus, we find the the complement of:

is:

17
2 Boolean Algebra

 Through our exercises in simplifying Boolean

expressions, we see that there are numerous
ways of stating the same Boolean expression .
 These “synonymous” forms are logically equivalent.
 Logically equivalent expressions have identical truth
tables.
 In order to eliminate as much confusion as
possible, designers express Boolean functions in
standardized or canonical form.

18
2 Boolean Algebra

 There are two canonical forms for Boolean

expressions: sum-of-products and product-of-sums.
 Recall the Boolean product is the AND operation and the
Boolean sum is the OR operation.
 In the sum-of-products form, ANDed variables are
ORed together.
 For example:
 In the product-of-sums form, ORed variables are
ANDed together:
 For example:

19
2 Boolean Algebra

 It is easy to convert a function

to sum-of-products form using
its truth table.
 We are interested in the values
of the variables that make the
function true (=1).
 Using the truth table, we list
the values of the variables that
result in a true function value.
 Each group of variables is then
ORed together.
20
2 Boolean Algebra

 The sum-of-products form

for our function is:

We note that this function is not in simplest terms. Our

aim is only to rewrite our function in canonical sum-of-

products form.

21
3 Logic Gates

 We have looked at Boolean functions in abstract

terms.
 In this section, we see that Boolean functions are
implemented in digital computer circuits called gates.
 A gate is an electronic device that produces a result
based on two or more input values.
 In reality, gates consist of one to six transistors, but digital
designers think of them as a single unit.
 Integrated circuits contain collections of gates suited to a
particular purpose.

22
3 Logic Gates

 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.
23
3 Logic Gates

 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.

24
3 Logic Gates

 NAND and NOR

are two very
important gates.
Their symbols and
truth tables are
shown at the right.

25
3 Logic Gates

 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.
26
3 Logic Gates

 Gates can have multiple inputs and more than

one output.
 A second output can be provided for the complement
of the operation.
 We’ll see more of this later.

27
4 Digital Components

 The main thing to remember is that

combinations of gates implement Boolean
functions.
 The circuit below implements the Boolean
function:

We simplify our Boolean expressions so that we can create simpler

circuits.

28
5 Combinational Circuits

 We have designed a circuit that implements the

Boolean function:

 This circuit is an example of a combinational logic

circuit.
 Combinational logic circuits produce a specified
output (almost) at the instant when input values
are applied.
 In a later section, we will explore circuits where this is
not the case.

29
5 Combinational Circuits

 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.

30
5 Combinational Circuits

 As we see, the sum can be

found using the XOR
operation and the carry
using the AND operation.

31
5 Combinational Circuits

 We can change our half

adder into to a full adder
by including gates for
processing the carry bit.
 The truth table for a full
adder is shown at the
right.

32
5 Combinational Circuits

 How can we change the

half adder shown below
to make it a full adder?

33
5 Combinational Circuits

 Here’s our completed full adder.

34
5 Combinational Circuits

 Just as we combined half adders to make a full

adder, full adders can connected in series.
 The carry bit “ripples” from one adder to the next;
hence, this configuration is called a ripple-carry
adder.

Today’s systems employ more efficient adders.

35
5 Combinational Circuits

 Decoders are another important type of

combinational circuit.
 Among other things, they are useful in selecting a
memory location according a binary value placed
on the address lines of a memory bus.
 Address decoders with n inputs can select any of 2n
locations.

This is a block diagram

for a decoder.

36
5 Combinational Circuits

 This is what a 2-to-4 decoder looks like on the

inside.

If x = 0 and y = 1, which

output line is enabled?

37
5 Combinational Circuits

 A multiplexer does just the

opposite of a decoder.
 It selects a single output
from several inputs.
 The particular input chosen
for output is determined by
the value of the multiplexer’s
control lines.
 To be able to select among n This is a block diagram

inputs, log2n control lines are for a multiplexer.

needed.
38
5 Combinational Circuits

 This is what a 4-to-1 multiplexer looks like on the

inside.

If S = 1 and S = 0, which input

0 1
is transferred to the output?

39
6 Sequential Circuits

 Combinational logic circuits are perfect for

situations when we require the immediate
application of a Boolean function to a set of inputs.
 There are other times, however, when we need a
circuit to change its value with consideration to its
current state as well as its inputs.
 These circuits have to “remember” their current state.
 Sequential logic circuits provide this functionality
for us.

40
6 Sequential Circuits

 As the name implies, sequential logic circuits require

a means by which events can be sequenced.
 State changes are controlled by clocks.
 A “clock” is a special circuit that sends electrical pulses
through a circuit.
 Clocks produce electrical waveforms such as the
one shown below.

41
6 Sequential Circuits

 State changes occur in sequential circuits only

when the clock ticks.
 Circuits can change state on the rising edge,
falling edge, or when the clock pulse reaches its
highest voltage.

42
6 Sequential Circuits

 Circuits that change state on the rising edge, or

falling edge of the clock pulse are called edge-
triggered.
 Level-triggered circuits change state when the
clock voltage reaches its highest or lowest level.

43
6 Sequential Circuits

 To retain their state values, sequential circuits rely

on feedback.
 Feedback in digital circuits occurs when an output
is looped back to the input.
 A simple example of this concept is shown below.
 If Q is 0 it will always be 0, if it is 1, it will always be 1.
Why?

44
6 Sequential Circuits

 You can see how feedback works by examining

the most basic sequential logic components, the
SR flip-flop.
 The “SR” stands for set/reset.
 The internals of an SR flip-flop are shown below,
along with its block diagram.

45
6 Sequential Circuits

 The behavior of an SR flip-flop is described by

a characteristic table.
 Q(t) means the value of the output at time t.
Q(t+1) is the value of Q after the next clock
pulse.

46
6 Sequential Circuits

 The SR flip-flop actually

has three inputs: S, R,
and its current output, Q.
 Thus, we can construct
a truth table for this
circuit, as shown at the
right.
 Notice the two undefined
values. When both S
and R are 1, the SR flip-
flop is unstable.
47
6 Sequential Circuits

 If we can be sure that the inputs to an SR flip-flop

will never both be 1, we will never have an
unstable circuit. This may not always be the case.
 The SR flip-flop can be modified to provide a
stable state when both inputs are 1.
• This modified flip-flop is called a JK flip-flop,

shown at the right.

- The “JK” is in honor of

Jack Kilby.

48
6 Sequential Circuits

 At the right, we see

how an SR flip-flop
can be modified to
create a JK flip-flop.
 The characteristic
table indicates that
the flip-flop is stable
for all inputs.

49
6 Sequential Circuits

 Another modification of the SR flip-flop is the D

flip-flop, shown below with its characteristic table.
 You will notice that the output of the flip-flop
remains the same during subsequent clock
pulses. The output changes only when the value
of D changes.

50
6 Sequential Circuits

 The D flip-flop is the fundamental circuit of

computer memory.
 D flip-flops are usually illustrated using the block
diagram shown below.
 The next slide shows how these circuits are
combined to create a register.

51
6 Sequential Circuits

 This illustration shows a

4-bit register consisting of
D flip-flops. You will
usually see its block
diagram (below) instead.

A larger memory configuration

is in your text.

52
6 Sequential Circuits

 A binary counter is
another example of a
sequential circuit.
 The low-order bit is
complemented at each
clock pulse.
 Whenever it changes
from 0 to 1, the next bit
is complemented, and
so on through the
other flip-flops.

53
7 Designing Circuits

 We have seen digital circuits from two points of

view: digital analysis and digital synthesis.
 Digital analysis explores the relationship between a
circuits inputs and its outputs.
 Digital synthesis creates logic diagrams using the values
specified in a truth table.
 Digital systems designers must also be mindful of
the physical behaviors of circuits to include minute
propagation delays that occur between the time
when a circuit’s inputs are energized and when the
output is accurate and stable.
54
7 Designing Circuits

 Digital designers rely on specialized software to

create efficient circuits.
 Thus, software is an enabler for the construction of
better hardware.
 Of course, software is in reality a collection of
algorithms that could just as well be
implemented in hardware.
 Recall the Principle of Equivalence of Hardware and
Software.

55
7 Designing Circuits

 When we need to implement a simple, specialized

algorithm and its execution speed must be as fast as
possible, a hardware solution is often preferred.
 This is the idea behind embedded systems, which
are small special-purpose computers that we find in
many everyday things.
 Embedded systems require special programming
that demands an understanding of the operation of
digital circuits, the basics of which you have learned
in this chapter.

56
Conclusion

 Computers are implementations of Boolean logic.

 Boolean functions are completely described by
truth tables.
 Logic gates are small circuits that implement
Boolean operators.
 The basic gates are AND, OR, and NOT.
 The XOR gate is very useful in parity checkers
and adders.
 The “universal gates” are NOR, and NAND.

57
Conclusion

 Computer circuits consist of combinational logic

circuits and sequential logic circuits.
 Combinational circuits produce outputs (almost)
immediately when their inputs change.
 Sequential circuits require clocks to control their
changes of state.
 The basic sequential circuit unit is the flip-flop:
The behaviors of the SR, JK, and D flip-flops
are the most important to know.

58
End of Chapter 3

59