EEE 3101: Digital Logic and Circuits

Boolean Algebra

Course Teacher: Nafiz Ahmed Chisty

Associate Professor and Head (UG)

Department of EEE
Faculty of Engineering, AIUB
Room# DNG03, Ground Floor, D Building
Email: chisty@[Link]
Website: [Link]
Website: [Link]
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

BOOLEAN OPERATIONS AND EXPRESSIONS

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

❑ Boolean algebra is the mathematics of digital systems. A basic knowledge of

Boolean algebra is indispensable to the study and analysis of logic circuits. In
the last chapter, Boolean operations and expressions in terms of their
relationship to NOT, AND, OR, NAND, and NOR gates were introduced.

❑ Variable, complement, and literal are terms used in Boolean algebra.

❑ A variable is a symbol (usually an italic uppercase letter) used to represent a

logical quantity. Any single variable can have a 1 or a 0 value.

❑ The complement is the inverse of a variable and is indicated by a bar over the
variable (overbar). The complement of the variable A is read as "not A" or "A
bar."

❑ A literal is a variable or the complement of a variable.

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Boolean Algebra Operator Precedence

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Precedence Operator
level
1 brackets ( )
2 Boolean complement NOT
3 Boolean product AND
4 Boolean sum OR

Note:
Brackets have the highest precedence, i.e.,
everything inside brackets is evaluated first.

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Boolean Addition
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Boolean addition is equivalent to the OR operation

0+0=0
0+1=1
1+0=1
1+1=1

Boolean Multiplication
Boolean multiplication is equivalent to the AND operation
0*0=0
0*1=0
1*0=0
1*1 =1
Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Laws and Rules of Boolean Algebra

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Laws of Boolean Algebra

• Commutative Laws
• Associative Laws
• Distributive Law
❑Commutative Law of Addition:
A+B=B+A

❑Commutative Law of Multiplication:

A*B=B*A

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

❑ Associative Law of Addition:

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

A + (B + C) = (A + B) + C

❑ Associative Law of Multiplication:

A * (B * C) = (A * B) * C

❑ Distributive Law:
A(B + C) = AB + AC

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Rules of Boolean Algebra

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Nafiz A. Chisty
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

OR Truth Table AND Truth Table

Nafiz A. Chisty
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Nafiz A. Chisty
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

11
Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

:
DeMorgan’s Theorem
DeMorgan's first theorem is stated as follows:
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

The complement of a product of variables is equal to the sum of the complements

of the variables,

DeMorgan's second theorem is stated as follows:

The complement of a sum of variables is equal to the product of the complements
of the variables.

Remember:
“Break the bar,
change the sign”

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

SIMPLIFICATION USING BOOLEAN ALGEBRA

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Simplification means fewer gates

for the same function

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

SIMPLIFICATION USING BOOLEAN ALGEBRA

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Domain of a Boolean Expression: The domain of a general Boolean expression

is the set of variables contained in the expression in either complemented or
complemented form.
For example, the domain of the expressing A’B+ AB’C is the set of variables A, B,
C and the domain of the expression ABC’ + CD’E + B’CD’ is the set of variables A,
B, C, D, E.

Standard Forms of Boolean Expressions

All Boolean expressions, regardless of their form, can be converted into either of two
standard forms: the sum-of-products form or the product-of-sums form. Standardization
makes the evaluation, simplification, and implementation of Boolean expressions much
more systematic and easier.

Sum of Products (SOP)= minterm

Product of Sums (POS)=maxterm

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

The sum-of-product (SOP) form

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

• Sum of Products: A Product is defined as a term consisting of products of the

literals. When two or more products are summed in a Boolean expression, it is
called the Sum-of Products (SOP).

• Standard SOP: It is an expression where all the variables are present in each
product terms. The products in a SSOP are called min terms (𝐦𝐢) .

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

The product of sum (POS) form

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

• Product of Sum: A Sum is defined as a term consisting of sum of the literals. When
two or more sum terms are multiplied in a Boolean Expression, it is called the Product-
of Sum (POS).

• Standard POS: It is an expression where all the variables are present in each sum
terms. Each sum terms are called max terms (𝐌𝐢) .

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Minterms and Maxterms

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

• Each variable in a Boolean expression is a literal.

• Boolean variable can appear in normal (A) or complemented (A’) form.
• Each product of all variables in the domain is called Min-Term.
• Each sum of all variables in the domain is called Max-Term.
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

BOOLEAN EXPRESSIONS AND TRUTH TABLES

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Converting SOP Expressions to Truth Table Format

• Truth-table can be formed for any Boolean expression.
• Converting a Boolean Expression to SSOP can make this task a lot easier.

Find the truth-table for the following Boolean expression:

= 111 + 110 + 100 + 000

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Converting POS Expressions to Truth Table Format

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Connecting the Dots between SOP and POS

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

From the truth table determine the standard SOP expression and the equivalent POS
expression.
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

The Karnaugh Map

A Karnaugh map is similar to a truth table. The main purpose of K-Map is to simplify a
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Boolean expression.
A Karnaugh map provides a systematic method for simplifying Boolean expressions and,
if properly used, will produce the simplest SOP or POS expression possible, known as the
minimum expression.
The effectiveness of algebraic simplification depends on your familiarity with all the laws,
rules, and theorems of Boolean algebra and on your ability to apply them. The Karnaugh
map, on the other hand, provides a "cookbook" method for simplification.

000 001 0000 0001 0011 0010

010 011 0100 0101 0111 0110

110 111 1100 1101 1111 1110

100 101 1000 1001 1011 1010

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Cell Adjacency
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Cells that differ by only one

variable are adjacent.

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

KARNAUGH MAP SOP MINIMIZATION

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Mapping a Standard SOP Expression

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Mapping a Nonstandard SOP Expression

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

A Boolean expression must first be in standard form before you use a Karnaugh map.

Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Karnaugh Map Simplification of SOP Expressions

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

a minimum SOP expression is obtained by grouping the 1s

Grouping the 1s: You can group 1s on the Karnaugh map according to the following
rules by enclosing those adjacent cells containing Is.
The goal is to maximize the size of the groups and to minimize the number of
groups.
1. A group must contain either 1, 2, 4, 8, or 16 cells, which are all powers of two. In the
case of a 3-variable map, 23 = 8 cells is the maximum group.
2. Each cell in a group must be adjacent to one or more cells in that same group, but all
cells in the group do not have to be adjacent to each other.
3. Always include the largest possible number of 1s in a group in accordance with rule 1.
4. Each 1 on the map must be included in at least one group. The 1s already in a group
can be included in another group as long as the overlapping groups include ungrouped
1s keeping accordance to rules above.

1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1
1 1 1 1 1 1

1 1 1 1 1 1 1
Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Determining the Minimum SOP Expression from the Map: When all the 1s representing the
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

standard product terms in an expression are properly mapped and grouped, the process of
determining the resulting minimum SOP expression begins. The following rules are applied
to find the minimum product terms and the minimum SOP expression:
1. Group the cells that have 1s. Each group of cells containing 1s creates one product term
composed of all variables that occur in only one form (either un-complemented or
complemented) within the group. Variables that occur both un-complemented and
complemented within the group are eliminated. These are called contradictory variables.
2. Determine the minimum product term for each group.
a. For a 3-variable map:
(1) A 1-ceIl group yields a 3-variable product term
(2) A 2-cell group yields a 2-variable product term
(3) A 4-cell group yields a 1-variable term
(4) An 8-cell group yields a value of 1 for the expression
b. For a 4-variable map:
(1) A 1-cell group yields a 4-variable product term
(2) A 2-cell group yields a 3-variable product term
(3) A 4-cell group yields a 2-variable product term
(4) An 8-cell group yields a 1-variable term
(5) A 16-cell group yields a value of 1 for the expression
3. When all the minimum product terms are derived from the Karnaugh map, they are
summed to form the minimum SOP expression.
Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

ABCD ABCD
0011 0100
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

0010 0101
0111 0111
0110 0110
------- 1100
A’ C 1101
1111
ABCD 1110
1101 -------
1001 B
-------
A C’D

Nafiz A. Chisty
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

101 + 001 + 001 + 000 + 100

34
Nafiz A. Chisty
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Mapping Directly from a Truth Table

Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

Nafiz A. Chisty
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

36
Nafiz A. Chisty
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Nafiz A. Chisty
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Determine the simplifies POS for the

following expression
F(A,B,C,D)= (0,1,3,5)
ᵋ
 Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

"Don't Care" Conditions

Sometimes a situation arises in which some input variable combinations are not allowed.
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB

For example, in BCD code there are six invalid combinations: 1010, 1011, 1100, 1101,
1110, and 1111. Since these un-allowed states will never occur in an application involving
the BCD code, they can be treated as "don't care" terms with respect to their effect on the
output. That is, for these "don't care" terms either a 1 or a 0 may be assigned to the
output: it really does not matter since they will never occur.
The "don't care" terms can be used to advantage on the Karnaugh map. Figure below
shows that for each "don't care" term, an X is placed in the cell. When grouping the 1s, the
Xs can be treated as 1s to make a larger grouping or as 0s if they cannot be used to
advantage. The larger a group, the simpler the resulting term will be.

40
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

Reference:
[1] Thomas L. Floyd, “Digital Fundamentals” 11th edition, Prentice Hall.
[2] M. Morris Mano, “Digital Logic & Computer Design” Prentice Hall.
Thanks
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

000 001
0
0 1
1
2 010 011
2 3
3
4 110 111

5 6 7

6 100 101

7 4 5
Nafiz Ahmed Chisty| Head (UG) and Associate Professor, Dept. of EEE, FE, AIUB Nafiz Ahmed Chisty| Associate Professor and Head (UG), Dept. of EEE, FE, AIUB| chisty@[Link]

0
1
2 0000 0001 0011 0010
3 0 1 3 2
4
5
0100 0101 0111 0110
6
7 4 5 7 6
8
9 1100 1101 1111 1110
10 13 15 14
12
11
12
13 1000 1001 1011 1010
14 8 9 11 10
15