BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Compiled by
Lochan Khatiwada
1|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Unit 3
Simplification of
Boolean Function
2|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Boolean Functions
Boolean functions deal with the binary variables and the symbols. A Boolean Function
is described by an algebraic expression called Boolean expression which consists of
binary variables, the constants 0 and 1, and the logic operation symbols. Consider the
following example.
F = XY + Z
here, F is a function of x, y, z
x, y, z are binary variables i.e. they can have only value 0 or 1
Representation Types:
3|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
SOP Boolean Function Implementation using Logic Gates
The sum of product or SOP form is represented by using basic logic gates: AND gate
and OR gate. The SOP form implementation will have AND gates at its input side and
as the output of the function is the sum of all product terms, it has an OR gate at its
output side.
An important to remember is that we use NOT gate to represent the inverse or
complement of the variables.
Sum of Products (SOP)
Input AND
Output OR
Implementation for 2 Input Variables
Let us understand how we can implement the following Boolean function using basic
logic gates.
F = A B + A B’
In the given SOP function, we have one compliment term, B. So, to represent the
compliment input, we are using the NOT gates at the input side. And to represent the
product term, we use AND gates.
4|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Implementation for 3 Input Variables
Let us now see how to implement the following Boolean function by using basic logic
gates. It is a 3-input variable function.
F = A B C + A B C’ + A’ B C’
In the given function, we have two compliment terms, A and C. So, to represent the
compliment input, we are using the NOT gates at the input side. And to represent the
product term, we use AND gates. See the below given logic diagram for
representation of the Boolean function.
Another example:
5|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
POS Boolean Function Implementation using Logic Gates
The product of sums or POS form can be represented by using basic logic gates like
AND gate and OR gates. The POS form implementation will have the OR gate at its
input side and as the output of the function is product of all sum terms, it has AND
gate at its output side. In POS form implementation, we use NOT gate to represent the
inverse or complement of the variables.
Sum of Products (SOP)
Input OR
Output AND
Implementation for 2 Input Variables
Let us now see how to implement the following Boolean function by using basic logic
gates.
F = (A + B). (A + B’)
In the given function, we have a complement term, B. So, to represent the compliment
input, we are using the NOT gates at the input side. And to represent the sum term, we
use OR gates. See the below logic diagram for representation of the Boolean function.
Implementation for 3 Input Variables
Implement the Boolean function by using basic logic gates.
F = (A + B + C). (A’ + B’ +C). (A + B’ + C)
In the given Boolean Function, we have two compliment terms, A and B. So, to
represent the compliment input, we are using the NOT gates at the input side. And to
represent the sum term, we use OR gates. See the below given logic diagram for
representation of the Boolean function.
6|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Karnaugh-map or K-map
A Karnaugh Map (K-Map) is a graphical/pictorial representation of Boolean functions
that helps simplify logical expressions and design digital circuits. It is particularly useful
in digital circuit design and optimization. It was developed by Karnaugh in 1953.
Karnaugh map can produce Sumofproduct (SOP) or productofSum (POS) expression
considering which of the two (0,1) outputs are being grouped in it. The grouping of 0’s
result in Product of Sum expression & the grouping of 1’s result in Sum of Product
expression.
For a function with 'n' variables, the K-Map has 2n cells.
i.e.
Two variables
22 = 4 cells
BC
Three variables
23 = 8 cells
Four variables
24 = 16 cells
7|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Examples:
K-map simplification for 2-variables
1. Simplify given function with minterms using k-map: f= Σ (0,2){or f=A'B'+AB'} Ans: B'
2. Simplify given function with minterms using k-map: f(A,B)= Σ (0,1,2) Ans: A'+B'
K-map simplification for 3-variables
1. Simplify given function using k-map: f (A, B, C) = A'B'C'+AB'C' Ans: B'C'
2. Simplify given function using k-map: f (A, B, C) = Σ (0,2,4,5,6) Ans: AB'+C'
K-map simplification for 4-variables
1. Simplify given function using k-map: f = A'BC'D+ABC'D+A'BCD+ABCD+A'B'C'D'
2. Simplify given function using k-map: f (A, B, C, D) = Σ (0,2,4,5,6)
8|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
9|Compiled by: Loch ananan da Khatiwada (MIT)
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
10 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Solved examples for Sum of product (SOP) method:
11 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
12 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Solving using Product of sum (POS) method:
The grouping of 0’s result in Product of Sum expression & the grouping of 1’s
result in Sum of Product expression.
Here, the Σ symbol is given, that means, we insert 1 in given minterms but pairs
0 for POS method.
Here, the Π symbol is given, that means, we insert 0 in given maxterms.
13 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Don’t care condition
In Karnaugh maps (K-maps), "don't care" conditions refer to specific
combinations of input values for which the output of the Boolean function is not
critical. These conditions are marked with a 'd' or 'X' in the K-map, indicating that
the designer can choose either a 0 or a 1 for the corresponding cell without
affecting the overall functionality of the system.
This is helpful if it allows us to form a larger group than would otherwise be
possible without the don’t cares. There is no requirement to group all or any of
the don’t cares.
14 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
(Don’t care in SOP form)
Q. Simplify the Boolean function f(A,B,C,D) = Σ (0,2,3,6,7,12,13,14) + Σ d
(1,4,11,15).
AB CD 00 01 11 10
00
10
11
10
F= A’B’ + A’C + AB
(Don’t care in POS form)
Q. Simplify the Boolean function f(A,B,C,D) = Π (5,8,9,10) + Π d (1,4,11,15).
Here, use zero (0) and pair it in the given functions instead of 1, since it is in
POS form.
CD
AB 00 01 11 10
00 1
01
11
10
F= (A+C+D’) (A’+B)
15 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
16 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Minterms(m) and Maxterms(M)
Note: Each maxterm is the complement of its corresponding minterms and vice
versa.
17 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
18 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
Canonical example:
F (A, B, C) = ABC’ + A’BC + A’B’C (Here all the variables are present)
F (X, Y, Z) = (X+Y+Z’). (X+Y’+Z) (Here all the variables are present)
Here, in each expression, there is not all variables present. That is why, it is called
standard form. But if every variable were present, then it would be called as
canonical form.
=Π (0,2,3,6)
=Π (0,1,2,4)
19 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
BIT 3rd semester Digital Logic Balmiki Lincoln College, Birtamode
20 | C o m p i l e d b y : L o c h a n a n a n d a K h a t i w a d a ( M I T )
