Digital Logic Design

Chapter IV
Boolean Algebra and Logic Simplification
Addis Ababa Science and Technology University

College of Electrical and Mechanical Engineering

Department of Software Engineering

Lecturer: Biruk T.

Digital Logic Design 1

 Introduction
• Boolean algebra is a convenient and systematic way of expressing and analyzing the
operation of logic circuits.

• Boolean algebra is the mathematics of digital systems

• Is used to describe the relationship between inputs and outputs

• A basic knowledge of Boolean algebra is indispensable to the study and

analysis of logic circuits.

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

• Variable: is a symbol to represent a logical quantity.
• Complement: is the inverse of a variable and is indicated by an overbar.
• Literal: is a variable or the complement of a variable.
Digital Logic Design 2
 Boolean Addition
• Boolean addition is equivalent to the OR operation.
• The basic rules are illustrated with their relation to the OR gate as follow.

• In Boolean algebra, a sum term is a sum of literals.

• In logic circuits, a sum term is produced by an OR operation.

Digital Logic Design 3

 Boolean Multiplication
• Boolean multiplication is equivalent to the AND operation.
• The basic rules are illustrated with their relation to the AND gate as
follows.

• In Boolean algebra, a product term is the product of literals.

• In logic circuits, product term is produced by an AND operations.
Digital Logic Design 4
Laws and Rules of Boolean Algebra

Digital Logic Design 5

Laws and Rules of Boolean Algebra

Digital Logic Design 6

 Fig:- Associative law of addition
A + (B + C) = (A + B) + C

Fig:- Associative law of multiplication

A(BC) = (AB)C
Digital Logic Design 7
Laws and Rules of Boolean Algebra

Digital Logic Design 8

Digital Logic Design 9
 Proof 11.
R.H.S. = A+B
= A(B+B’)+B(A+A’)
= AB+AB’+AB+A’B
= AB+AB’+A’B
= (A+A’)B+AB’
= B+AB’
= L.H.S.
B+AB’=A+B

Proof 12. (Assignment)

Digital Logic Design 10

Digital Logic Design 11
Digital Logic Design 12
Exercise – Apply the DeMorgan’s theorems to each
of the following expressions

1. ((A+B+C)D)’ Ans: A’B’C’ + D’

2. (ABC + DEF)’ Ans: (A’ + B’ + C’)(D’ + E’ + F’)

3. (AB’ + C’D + EF)’ Ans: (A’ + B)(C + D’)(E’ + F’)

Digital Logic Design 13

 Boolean Analysis of Logic Circuits
• To derive the Boolean expression for a given logic circuits;
• Begin at the left-most inputs and work toward the final output, writing the
expression for each gate.

• In the example circuit in the following figure, the Boolean expression

is determined as follows;

Digital Logic Design 14

 Constructing a Truth Table for a logic Circuit
• Once the Boolean expression for a given logic
circuit has been determined; a truth table that
shows the output for all possible values of the
input variables can be developed.
• The truth table for the pervious page logic
circuit, with Boolean expression A(B +CD), is
found in the left side.
• Prove it! Operator Precedence

Digital Logic Design 15

 Standard form of Boolean Expressions
• All Boolean expressions can be converted into either of two standard
forms;
• The sum-of-products – SOP form
• The product-of-sums – POS form

• Standardization makes t he evaluation, simplifi c a t i on a n d

implementation of Boolean expressions much more systematic and
easier.

Digital Logic Design 16

Standard Forms of Boolean Expressions
Sum of Products (SOP) Products of Sum (POS)

Notes:
§ SOP and POS expression cannot have more than
one variable combined in a term with an inversion
bar
§ There’s no parentheses in the expression
Digital Logic Design 17
 The Sum-of-Products (SOP) Form
• A product term was defined as a term consisting of the product of
literals.
• When two or more product terms are summed by Boolean addition;
• The resulting expression is a sum-of-products (SOP).
• Some examples are;

Digital Logic Design 18

 The Standard SOP Form
• A SOP expressions in which some of the product terms do not contain
all of the variables in the domain of the expression are not standard.
• Example
• The above expression have a domain made up of the variables A, B, C and D.
• From first term D or and from second term C or are missing.
• A standard SOP expression is one in which all the variables in
the domain appear in each product term in the expression.
• Example :
• Is a standard SOP expression.

Digital Logic Design 19

Example

Digital Logic Design 20

Example

Digital Logic Design 21

 The Product-of-Sums (POS) Form
• A sum term is defined as a term consisting of the sum (Boolean
addition) of literals (variables or their complements).
• When two or more sum terms are multiplied, the resulting expression
is a product-of-sums (POS).
• Some examples are;

Digital Logic Design 22

 The Product-of-Sums (POS) Form
• POS expression can be implemented by logic; in which the outputs of
a number of OR gates connect to the inputs of an AND gate.

Digital Logic Design 23

 The Standard POS Form
• .
• This is not a standard form POS expressions;
• Notice that the complete set of variables in the domain is not represented in
the first two terms of the expression; that is, D or is missing from the first
term and C or is missing from the second term.
• A standard POS expression is one in which all the variables in the
domain appear in each sum term in the expression. For example;
•
• This is a standard POS expression.
• Any non-standard POS expression can be converted to the standard
form using algebra.

Digital Logic Design 24

Digital Logic Design 25
Example

Digital Logic Design 26

Converting Standard SOP to Standard POS
• The binary values of the product terms in a given standard SOP
expression are not present in the equivalent standard POS expression.
• Also, the binary values that are not represented in the SOP expression are
present in the equivalent POS expression.
• Therefore, to convert from standard SOP to standard POS;
1. Evaluate each product term in the SOP expression.
• That is, determine the binary numbers that represent the product terms.

2. Determine all of the binary numbers not included in the evaluation in step 1.

3. Write the equivalent sum term for each binary number from step 2 and
express in POS form.
• Using a similar procedure, you can go from POS to SOP.
Digital Logic Design 27
Converting Standard SOP to Standard POS

Digital Logic Design 28

 Boolean Expressions and Truth Tables
• All standard Boolean expressions can be easily converted into truth
table format using binary values for each term in the expression.

• The truth table is a common way of presenting, in a concise format,

the logical operation of a circuit.

• Standard SOP or POS expressions can be determined from a truth

table.

Digital Logic Design 29

Converting SOP Expressions to Truth Table
1. List all possible combinations of binary values of the variable in the
expression.

2. Convert the SOP expression to standard form if it is not already.

3. Place a 1 in the output column for each binary value that makes the
standard SOP expression a 1 and place a 0 for all the remaining
binary values.

Digital Logic Design 30

Example

Digital Logic Design 31

Converting POS Expressions to Truth Table
1. List all the possible combinations of binary values of the variables
just as was done for the SOP expression.

2. Convert the POS expression to standard form if it is not already.

3. Finally, place a 0 in the output column for each binary value that
makes the expression a 0 and place a 1 for all the remaining binary
value.

Digital Logic Design 32

Example

Digital Logic Design 33

If given POS or SOP
step 1: find its respective truth table
POS -> zero
SOP->One

Digital Logic Design 34

Determining Standard Expressions from a Truth Table
• To determine the standard SOP expression represented by a truth table;
• List the binary values of the input variables for which the output is 1.

• Convert each binary value to the corresponding product term by replacing each
1 with the corresponding variable and each 0 with the corresponding variable
complement.
• For example:

Digital Logic Design 35

 Determining Standard Expressions from a Truth Table
• To determine the standard POS expression represented by a truth table,
• List the binary values for which the output is 0.

• Convert each binary value to the corresponding sum term by replacing each 1
with the corresponding variable complement and each 0 with the
corresponding variable.
• For example:

Digital Logic Design 36

Example
• From the truth table given below determine the standard SOP
expression and the equivalent standard POS expression.

37
Example
• From the truth table given below determine the standard SOP
expression and the equivalent standard POS expression.

Digital Logic Design 38

 The Karanaugh Map (K-Map)
• A karnaugh map provides a systematic method for simplifying
Boolean expressions,
• If properly used, it produce the simplest SOP or POS expression possible,
known as the minimum expression.
• Karnaugh maps (K-maps) provide an easy and visual method for finding the
minimum-cost SoP (or PoS) for a Boolean expression.
• A K-map is similar to a truth table because it presents all of the possible
values of input variables and the resulting output for each value.
• Instead of being organized into columns and rows like a truth table; the K-
Map is an array of cells in which each cell represents a binary value of the
input variables.

Digital Logic Design 39

 Cont.
Ø A K-map is a pictorial arrangement of the truth table which allows easy
interpretation for choosing the minimum number of terms needed to
algebraically express a function.

Ø The minimization using K-map is simple. It is much faster and more time-
efficient than the minimization techniques with Boolean Algebra.

Ø K-maps works well for Boolean expressions of up to 6 input variables/

literals.

Digital Logic Design 40

 Karnaugh Map (K-Map)
• The map is made up of a table of every possible
SOP using the number of variables that are being
used.
• If 2 variables are used then a 2X2 map is used
• If 3 variables are used then a 4X2 map is used
• If 4 variables are used then a 4X4 map is used
• If 5 Variables are used then a 8X4 map is used
 K-Map SOP Minimization
• K-map is used for simplifying Boolean expressions to their
minimum form.
• Contains the fewest possible terms with the fewest possible variables
per term.
• Generally, a minimum SOP expression can be implemented with
fewer logic gates than a standard expression.
• Mapping a standard SOP expression:
• A 1 is placed on the K-map for each product term in the expression.
• For Example, for the product term a 1 goes in the 101 cell on 3-variable
map.

Digital Logic Design 42

2 Variables Karnaugh Map
B B
A Notice that the map is going
false to true, left to right and
A top to bottom

B B
The upper right hand cell A 1
is A B if X= A B then put
an X in that cell A

This show the expression true when A = 0 and B = 0

 2 Variables Karnaugh Map

B B
If X=AB + AB then A 1
put an X in both of
these cells A 1

From Boolean reduction we know that A B + A B = B

Rule 1
B B
Variables occur both in
From the Karnaugh map we A 1 complemented and un-
can circle adjacent cell and
find that X = B A 1 complemented form within
Rule 2 the group are eliminated.
The rectangles/circle may contain 1, 2, 4, 8, … cells of 1’s
3 Variables Karnaugh Map

Gray Code 0 1
C C

00 AB
01 AB
11 AB
10 AB
3 Variables Karnaugh Map (cont’d)

X=A B C + A B C + A B C + A B C

Gray Code 0 1
One
C C
simplification
00 AB 1 1 could be
01 AB X=AB+AB
11 AB
10 AB 1 1
3 Variables Karnaugh Map (cont’d)

X=A B C + A B C + A B C + A B C

Gray Code 0 1
Another
C C simplification
00 AB 1 1 could be
01 AB X=BC+BC
11 AB A Karnaugh
10 AB Map does wrap
1 1
around
3 Variables Karnaugh Map (cont’d)

X=A B C + A B C + A B C + A B C

Gray Code 0 1
C C
The Best
00 AB 1 1 simplification
01 AB would be
11 AB X =B
10 AB 1 1
4 Variables Karnaugh Map

Gray Code 0 0 01 11 10
CD CD CD CD
00 AB
01 AB
11 AB
10 AB
Simplify :

Gray Code 00 01 11 10
CD CD CD CD
00 AB 1 Now try it
01 AB with Boolean
1 1
reductions
11 AB 1 1
10 AB 1

X = ABD + ABC + CD
 The 3-variable K-Map
• The 3-variable K-map is an array of 8 cells.

m0 m1
ABC ABC

m2 m3
ABC ABC

m6 m7 ABC ABC

ABC ABC
m4 m5

Digital Logic Design 51

 Cell Adjacency
• The cells in a K-map are arranged so that there is only a single-variable
change between adjacent cells.
• In the 3-variable map the 010 cell is adjacent to the 000, 011, 110 cell.
• The 010 cell is not adjacent to the 001, 111, 100 or 101 cell.
• Cells in the top row are adjacent to the corresponding cells in the
bottom row. -> Wrap-around adjacency
• Cells in the outer left column are adjacent to the corresponding cells in
the outer right column. -> Wrap-around adjacency

Digital Logic Design 52

 The 4-variable K-Map
• The 4 variable K-map is an array of 16 cells.
CD
AB 00 01 11 10
00 m0 m1 m3 m2

01 m4 m5 m7 m6

11 m12 m13 m15 m14

10 m8 m9 m11 m10

Digital Logic Design 53

Digital Logic Design 54
Mapping a Standard SOP Expression
• Step 1: Determine the binary value of each product term in the
standard SOP expression.
• Step 2: Place 1 on the K-map in the cell having the same value as the
product term.

•Ex:- A’B’C’ + A’B’C + ABC’ + AB’C’

•: A’B’+AC’
Digital Logic Design 55
Digital Logic Design 56
 Determining the minimum SOP Expression
From the Map
1. Each group of cells containing 1’s, creates one product term.

2. Variables that occur both in complemented and un-complemented

form within the group are eliminated.

3. Determine the minimum product term for each group.

4. When all the minimum product terms are derived from K-map, they
are summed to form the minimum SOP expression.

Digital Logic Design 57

Individual Assignment:
A. Simplify F=A’B’C’ + A’BC’ + A’BC using K-map
B. Implement F using Basic Logic Gates
C. Implement the simplified Boolean expression
D. Discuss the difference

Digital Logic Design 58

Example-1
Simplify A’B’C’ + A’BC’ + A’BC using K-map

Digital Logic Design 59

Example-2
• Determine the product terms for each of the K-map in figure below
and write the resulting minimum SOP expression.

Digital Logic Design 60

K-map: Product-of-Sums (POS) Minimization
n A K-map can also be used for Product-of-Sums minimization (instead of Sum-
of-Products).
n In this case, we group the 0s and get the minimized form of the maxterms, and
then take the multiplication of them. F=(A+B’+C’)(A+B’+C)(A’+B’+C)
BC
A 00 01 11 10
0 1 1 0 0 (A + B’)

1 1 1 1 0 (B’ + C)

B’ AC F = πM(2,3,6)
F = (A + B’)(B’ + C)
F = B’ + AC
3 Variables Karnaugh Map (cont’d)
4 Variables Karnaugh Map

CD
AB 00 01 1 1 10

00
01
11
10
4 Variables Karnaugh Map (cont’d)
4 Variables Karnaugh Map (cont’d)
Karnaugh Map - Assignment
Mapping a Standard SOP expression
§ Example:
Y  A B C D  A B C D  A B CD  A BCD  A B C D  A B C D

Y  B D  ACD
Mapping a Standard POS expression
§ Example:
Using K-Map, convert the following standard POS
expression into a minimum SOP expression
Y  A( B  C )

Y = AB + AC or standard SOP : Y  A B C  A BC  ABC

 K-map simplification
Example: Simplify the Boolean function F(ABCD)=(0,1,2,5,8,9,10) in
(a) S-of-p (b) P-of-s

Using the minterms (1’s) Using the maxterms (0’s) and complimenting F
F(ABCD)= B’D’+B’C’+A’C’D Grouping as if they were minterms, then using
De Morgen’s theorem to get F.
F’(ABCD)= BD’+CD+AB
F(ABCD)= (B’+D)(C’+D’)(A’+B’)
Don’t Care Conditions
n In some situations, we don’t care about the value of a function for
certain combinations of the variables.
n These combinations may be impossible to occur in a certain contexts or
the value of the function may not matter when they occur.

n In such situations mentioned above, we say the function is incompletely

specified.
n There are multiple (completely specified) logic functions that can be used in the
design. So, we can utilize the don’t cares to create the simplest possible circuit.
n When constructing the rectangles in the simplification procedure, we can choose
either to cover or not to cover the don’t cares.

n Don’t cares can be treated as 1’s or 0’s, depending on which is more

advantageous.
n It may be covered or not. It is denoted with X’s.
Don’t Care Conditions
n Here is an example of a Karnaugh map with don’t cares (X).

● Covering 1’s without ● Covering 1’s utilizing X

utilizing X

n Instead of using 2-cell implicants, we can use 4-cell implicants, and the Boolean
function can be better simplified.
n Instead of F = A’BD’ + BC’D
we can use F = BC’ + A’B
Exercise: Don’t Care Conditions

F(A,B,C,D) = πM(0,2,3,9) + d(4,5,7,8,14)

F = B + AC + A’C’D

F(A,B,C,D) = Σm(0,2,4,5,6,12,13,15)
+ d(1,7,8,11,14)
F = B + A’D’
K-Map with “Don’t Care” Conditions (cont’d)

“Don’t Care” Conditions

§ Example:
Determine the minimal SOP using K-Map:

F(A, B, C, D)  M(0,2,6,8, 9,10) D(5,12,13, 14,15)

F ( A, B, C , D)  CD  BC  AD
Solution :

F(A, B, C, D)  M(0,2,6,8,9,10) D(5,12,13,14,15)

CD
AB 00 01 11 10
00 0 1 1 0
0 1 3 2

01 1 X 1 0
4 5 7 6

11 X X X X AD
BC 12 13 15 14

10 0 0 1 0
8 9 11 10
CD
Minimum SOP expression is
F( A, B, C, D)  CD BC  AD
End of Chapter - 4

73