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 )