Digital Logic Design

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

College of Engineering

Department of ECE 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. 2
Digital Logic Design
 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

Digital Logic Design 15
 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
 Parenthesis
 NOT
 AND
 OR
Digital Logic Design 16
 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.

Digital Logic Design 17

 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 18
 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 19

 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 20

Example

Digital Logic Design 21

Example

Digital Logic Design 22

 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 23

 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 24

 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 25
Digital Logic Design 26
Example

Digital Logic Design 27

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 28
Converting Standard SOP to Standard POS

Digital Logic Design 29

 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.

30
Digital Logic Design
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 31

Example

Digital Logic Design 32

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 33

Example

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

Digital Logic Design 35

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 36

 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 37

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

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

Digital Logic Design 39

 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 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
0 1
false to true, left to right and
A 2 3
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
 Introduction to Gray Code
• Gray code is a binary numeral system where two 2-bits 4-bits
successive values differ in only one bit (binary digit). 00 0000
01 0001
11 0011
• Today, Gray codes are widely used to facilitate error 10 0010
correction in digital communications such as digital 0110
3-bits 0111
terrestrial television and some cable TV systems. 000 0101
001 0100
1100
• This code was originally designed to prevent 011
010 1101
spurious output from electromechanical switches. 110 1111
111 1110
101 1010
100 1011
1001
1000

45
 Cont.
Gray As
Decimal Binary Decimal Binary Gray
Decimal

0 000 000 0
... ...
1 001 001 1
2 010 011 3
3 011
3 011 010 2
4 100 4 100 110 6
5 101 111 7
... ...
6 110 101 5
7 111 100 4

46
3 Variables Karnaugh Map

Gray Code 0 1
C C

00 AB 0 1

01 AB 2 3

11 AB 6 7

10 AB
4 5
3 Variables Karnaugh Map (cont’d)
ഥB
X=A ഥ Cത + A
ഥB ഥ Cത + A B
ഥC+AB ഥ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)

ഥB
X=A ഥ Cത + A
ഥB ഥ Cത + A B
ഥC+AB ഥ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)

ഥB
X=A ഥ Cത + A
ഥB ഥ Cത + A B
ഥC+AB ഥ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
0 1 3 2
00 AB
4 5 7 6
01 AB
11 AB 12 13 15 14

10 AB 8 9 11 10
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
 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 54

 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 55

Digital Logic Design 56
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 57
Digital Logic Design 58
 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 59
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 60

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

Digital Logic Design 61

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 62

K-map: Product-of-Sums (POS) Minimization
 A K-map can also be used for Product-of-Sums minimization (instead of Sum-
of-Products).
 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 (cont’d)
4 Variables Karnaugh Map (cont’d)
Karnaugh Map - Assignment
Mapping a Standard SOP expression
 Example:
Y  ABC D  ABC D  ABCD  ABCD  ABC D  ABC D

Answer:

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 )
Answer:

Y = AB + AC or standard SOP : Y  ABC  ABC  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
 In some situations, we don’t care about the value of a function for
certain combinations of the variables.
 These combinations may be impossible to occur in a certain contexts or
the value of the function may not matter when they occur.

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

specified.
 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.
 When constructing the rectangles in the simplification procedure, we can choose
either to cover or not to cover the don’t cares.

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

advantageous.
 It may be covered or not. It is denoted with X’s.
Don’t Care Conditions
 Here is an example of a Karnaugh map with don’t cares (X).
CD CD
AB 00 01 11 10 AB 00 01 11 10

00 0 0 X 0 00 0 0 X 0

01 1 1 X 1 01 1 1 X 1

11 X 1 0 0 11 X 1 0 0

10 0 X 0 0 10 0 X 0 0

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

utilizing X X

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

00 0 1 0 0

01 X X X 1
F(A,B,C,D) = πM(0,2,3,9) + d(4,5,7,8,14)
11 1 1 1 X F = B + AC + A’C’D
10 X 0 1 1

CD
AB 00 01 11 10

00 1 X 0 1

01 1 1 X 1
F(A,B,C,D) = Σm(0,2,4,5,6,12,13,15)
11 1 1 1 X + d(1,7,8,11,14)
F = B + A’D’
10 X 0 X 0
 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)
Answer:

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
Questions ?

74