Chapter 3

Boolean Algebra and Digital Logic

(PART-1)

[Link]
 Chapter 3 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.

[Link]
3.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
3.1 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
3.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
3.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
3.2 Boolean Algebra

7
3.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
3.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
3.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
3.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
3.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
3.2 Boolean Algebra
• Our second group of Boolean identities should be familiar to you
from your study of algebra:

13
3.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
3.2 Boolean Algebra
• We can use Boolean identities to simplify:
F(x,y,z) = xy + x′z + yz

15
Example 1:

Simplify: F(X,Y,Z) = x(yz + y'z) + xy + x'y + xz

16
Example 2:
Simplify: F(X,Y,Z) = xy'z + x(y + z')' + xy'z'

OR

17
3.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:

(xy)’ = x’+ y’ and (x + y)’= x’y’

18
3.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 complement of:

is:

19
3.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.

20
3.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:

21
3.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.

22
3.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.

23
Homework
• Determine by means of truth table the validity of DeMorgan’s
theorem for three variables:
• (ABC)’ = A’ + B’ + C’
• Using DeMorgan’s theorem, show that:
• (A + B)’(A’ + B’)’ = 0
• A + A’B + A’B’ = 1

24
3.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 consider
them as a single unit.
• Integrated circuits contain collections of gates suited to a particular purpose.

25
3.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.
26
3.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.

27
3.3 Logic Gates
• NAND and NOR are two very important gates. Their symbols and
truth tables are shown at the right.

28
3.3 Logic Gates
• The main thing to remember is that combinations
of gates implement Boolean functions.
• The circuit below implements the Boolean
function:
F(x,y,z) = x + y’z:

We simplify our Boolean expressions so

that we can create simpler circuits. 29
Exercises
• Simplify the following using Boolean algebra.
• A + AB
• AB + AB’
• A’BC + AC
• A’B + ABC’ + ABC
• Given the boolean expression F = x’y + xyz’
• Derive an algebraic expression for F’
• Show that F ∙ F’ = 0
• Show that F +F’ = 1

30
Exercises
• Simplify the following using Boolean algebra
• AB + A(CD + CD’)
• (BC’ + A’D)(AB’ + CD’)
• Given the Boolean function F = xy’z + x’y’z + xyz
• List the truth table of the function
• Draw the logic diagram using the original Boolean expression.
• Simplify the expression using Boolean algebra.
• List the truth table of the function from the simplified expression and show
that it is the same as the truth table above.
• Draw the logic diagram from the simplified expression and compare the total
number of gates with the diagram above.

31
Exercises
• Solve the following from the book:
P.189-191, ex: 1,3,5,15,17,22,26,28

32
3.4 Karnaugh Maps (K-maps)
• A Boolean expression could be simplified using the basic relations of
Boolean algebra.
• Difficult, it lacks specific rules for predicting each succeeding step in the
manipulative process.
• The map method (a.k.a. Karnaugh map, or K-map) provides a
graphical and straightforward procedure for simplifying Boolean
expressions

33
Karnaugh Map
• A function of n variables will have 2n minterms.
• A Boolean function is equal to 1 for some minterms, and 0 for others.
• The information contained in a truth table may be represented as a
diagram made up of squares, where each minterm is represented as
a square. For a function of n variables , we will have 2n squares.

34
 Example
• We give the truth table and KMap
for the function, F(x,y) = x + y at
the right.
• This function is equivalent to the
OR of all of the minterms that
have a value of 1. Thus:

F(x,y)= x+y = x’y+ xy’+ xy

35
Karnaugh Map: Example
• Of course, the minterm function that we derived from our Kmap was
not in simplest terms.
• That’s what we started with in this example.
• We can, however, reduce our complicated expression to its simplest
terms by finding adjacent 1s in the Kmap that can be collected into
groups that are powers of two.

• In our example, we have two

such groups.
– Can you find them?
36
Karnaugh Map: Example
• The best way of selecting two groups of 1s form our simple Kmap is
shown below.
• We see that both groups are powers of two and that the groups
overlap.
• The next slide gives guidance for selecting Kmap groups.

After simplification, the function

F reduces to F = X + Y
37
Kmap Simplification for Two Variables
• The rules of Kmap simplification are:
• Groupings can contain only 1s; no 0s.
• Groups can be formed only at right angles; diagonal groups are not allowed.
• The number of 1s in a group must be a power of 2 even if it contains a single
1.
• The groups must be made as large as possible.
• Groups can overlap and wrap around the sides of the Kmap.

38
Karnaugh Map: Example
• F (A,B,C) = ∑ (3,4,6,7) A B C F
• The information contained in a truth 0 0 0 0
table may be expressed in a compact
form by listing the decimal equivalent 0 0 1 0
of minterms equal to 1. 0 1 0 0
0 1 1 1
F = BC + AC’ 1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
39
 Kmap Simplification for Three Variables
• Consider the function:
F(X,Y,Z)= X’Y’Z + X’YZ + XY’Z + XYZ
• Its Kmap is given below.
• What is the largest group of 1s that is a power of 2?

40
 Kmap Simplification for Three Variables
• This grouping tells us that changes in the variables x and y have no
influence upon the value of the function: They are irrelevant.
• This means that the function,
F(X,Y,Z)= X’Y’Z + X’YZ + XY’Z + XYZ
reduces to F(x) = z.

You could verify

this reduction
with identities
or a truth table. 41
Layout of Karnaugh map

42
 2 variable Karnaugh Map
x + x´ = 1

F=AB’+AB F=A’B’+A’B

A A
B
B

F=A F = A’

43
2 variable Karnaugh Map
F =X’Y+XY+XY’

F=X+Y

44
 3 Variable Karnaugh Map
AB A

C
A’B’C’ A’BC’ ABC’ AB’C’
A’B’C A’BC ABC AB’C
C

F = X’YZ’+XYZ+X’YZ F = XY’Z’+XYZ’

YZ
YZ X 00 01 11 10
X 00 01 11 10
0
0

1
1

Wrapping around
edges
F = X’Y+YZ F = XZ’

45
3 variable Karnaugh Map

F(A,B,C) A’BC’+A’B’C’+A’BC+A’B’C
=
BC
A 00 01 11 10

0 F = A’

F(A,B,C) = A’BC+A’B’C+AB’C+ABC+ABC’
BC
A 00 01 11 10
C
AB
0

1 F = AB+C

46
 4 variables K-MAP
Are these ADJACENT SQUARES ?

A’B’C’D’ AB’C’D’

AB’CD’
A’B’CD’ Variables A,B,C,D

47
Exercises
• Simplify the following Boolean functions using three-variable maps.
• F(x,y,z) = ∑ (0, 1, 5, 7)
• F(x,y,z) = ∑ (1, 2, 3, 6, 7)
• F(x,y,z) = ∑ (3, 5, 6, 7)
• F(x,y,z) = ∑ (0, 2, 3, 4, 6)
• Simplify the following Boolean functions using four-variable maps.
• F(A, B, C, D) = ∑ (4, 6, 7, 15)
• F(A, B, C, D) = ∑ (0, 1, 2, 4, 5, 7, 11, 15)

49
Exercises
• Simplify F(w,x,y,z) = w’xy+w’x’yz+w’x’yz’ using kmaps.

50
Chapter 3 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.

51
 Chapter 3
Boolean Algebra and Digital Logic
(PART-2)
 3.3 Logic Gates – Reminder

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

53
 3.3 Logic Gates – Reminder

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

54
 3.3 Logic Gates – Reminder

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

55
 3.3 Logic Gates – Reminder

• NAND and NOR

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

56
 3.3 Logic Gates – Reminder

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

57
 3.3 Logic Gates – Reminder
• 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.

58
 3.3 Logic Gates – Reminder

• The main thing to remember is that combinations

of gates implement Boolean functions.
• The circuit below implements the Boolean
function F(x,y,z) = x + y’z:

We simplify our Boolean expressions so

that we can create simpler circuits.
59
 3.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.

60
 3.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.

61
 3.5 Combinational Circuits

• As we see, the sum can be

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

62
 3.5 Combinational Circuits

• We can change our half

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

63
 3.5 Combinational Circuits

• How can we change the

half adder shown below to
make it a full adder?

64
 3.5 Combinational Circuits

• Here’s our completed full adder.

65
 3.5 Combinational Circuits

• Just as we combined half adders to make a full

adder, full adders can be 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.

66
 3.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.

67
 3.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?

68
 3.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.
This is a
• To be able to select among n block
inputs, log2n control lines are diagram for a
needed. multiplexer.

69
 3.5 Combinational Circuits
• This is what a 4-to-1 multiplexer looks like on the
inside.

If S0 = 1 and S1 =
0, which input is
transferred to the
output?

70
 3.5 Combinational Circuits

• This shifter
moves the bits
of a nibble one
position to the
left or right.
If S = 0, in which
direction do the
input bits shift?

Try:
The Nibble: 1101
*Consider shifting left or right,
we will loose the bit
*Left: 1010
*Right: 0110 71
 Chapter 3 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.

72
 Chapter 3 Conclusion

• Computer circuits consist of combinational logic

circuits and sequential logic circuits.
• Combinational circuits produce outputs (almost)
immediately when their inputs change.
• Sequential circuits are not part of interest for this
lecture.

73