Digital Logic Design

Chapter IV
Boolean algebra and logic simplification
Addis Ababa Science and Technology
College of Electrical and Mechanical Engineering
Lecturer: Ambasa Aklilu (MSc)
 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.
• 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.
 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.
 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.
Laws and Rules of Boolean Algebra
Laws and Rules of Boolean Algebra
Laws and Rules of Boolean Algebra
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’)

 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;
 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!
 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 the evaluation, simplification and

implementation of Boolean expressions much more systematic and
easier.
 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;
 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.
Example
Example
 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;
 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.
 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.
Example
 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.
Converting Standard SOP to Standard POS
 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.
 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.
Example
 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.
Example
 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:
 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:
Example
• From the truth table given below determine the standard SOP
expression and the equivalent standard POS expression.
Example
• From the truth table given below determine the standard SOP
expression and the equivalent standard POS expression.
 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.
• 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.
 The 3-variable K-Map
• The 3-variable K-map is an array of 8 cells.

ABC ABC

ABC ABC

ABC ABC

ABC ABC
 The 4-variable K-Map
• The 4 variable K-map is an array of 16 cells.
 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
 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.
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’
K-map Simplification of SOP
• After an SOP expression has been mapped, a minimum SOP
expression is obtained by grouping the 1’s and determining the
minimum SOP expression from the map.
• Grouping the 1’s:
• You can group 1’s on the K-map according to the following rules by enclosing
those adjacent cell containing 1’s.
1. The goal is to maximize the size of the groups and to minimize the number
of groups. group must contain either 1,2,4,8 …. All are the power of 2
2. Each cell in the group must be adjacent to one or more cells in the same
group;
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.
 Determining the minimum SOP Expression
From the Map
1. Each group of cells containing 1’s creates one product term
1. Variables that occur both in complemented and un-complemented form
within the group are eliminated.

2. Determine the minimum product term for each group.

3. When all the minimum product terms are derived from K-map, they
are summed to form the minimum SOP expression.
Example-1
Simplify A’B’C’ + A’BC’ + A’BC using K-map
Example-2
• Determine the product terms for each of the K-map in figure below
and write the resulting minimum SOP expression.