Min terms

A minterm is defined as the product term of n variables, in which each of the n

variables will appear once either in its complemented or un-complemented form.
The min term is denoted as mi where i is in the range of 0 ≤ i < 2ⁿ.

A variable is in complemented form, if its value is assigned to 0, and the variable is

un-complimented form, if its value is assigned to 1.
For a 2-variable (x and y) Boolean function, the possible minterms are:

x’y’, x’y, xy’ and xy.

For a 3-variable (x, y and z) Boolean function, the possible minterms are:

x’y’z’, x’y’z, x’yz’, x’yz, xy’z’, xy’z, xyz’ and xyz.

 Outpu
Inputs Minterm
t

X Y F M

0 0 0 X'Y'

0 1 1 X'Y

1 0 1 XY'

1 1 1 XY
 Max terms
A max term is defined as the product of n variables, within the range of 0 ≤ i < 2ⁿ. The
max term is denoted as Mi. In max term, each variable is complimented, if its value is
assigned to 1, and each variable is un-complimented if its value is assigned to 0.

For a 2-variable (x and y) Boolean function, the possible max terms are:

x + y, x + y’, x’ + y and x’ + y’.

For a 3-variable (x, y and z) Boolean function, the possible maxterms are:

x + y + z, x + y + z’, x + y’ + z, x + y’ + z’, x’ + y + z, x’ + y + z’, x’ + y’ + z and x’ + y’ + z’.

 MAX TERMS
A B Y

0 0 0 A+B

0 1 1 A+B’

1 0 1 A’+B

1 1 0 A’+B’
 SOP AND POS FORM

Representation of Boolean expression can be primarily done in two ways. They are
as follows:

Sum of Products (SOP) form

Product of Sums (POS) form
If the input variable (let A) value is :
Zero (0) – a is LOW -It should be represented as A’ (Complement of A)
One (1) – a is HIGH -It should be represented as A
 Considering number of input variables =3, Say A, B and C.
Total number of combinations are: 2^3=8.

ABC
000
001
010
011
100
101
110
111
 Sum of Products (SOP): SUM OF MIN-TERMS
It is one of the ways of writing a boolean expression.
As the name suggests, it is formed by adding (OR operation) the product terms.
These product terms are also called as ‘min-terms’.
Min-terms are represented with ‘m’, they are the product(AND operation) of
boolean variables either in normal form or complemented form.

Therefore, SOP is sum of minterms and is represented as:

F in SOP = \Sigma m(0, 3)
Here, F is sum of minterm0 and minterm3.

For Example:
A=0, B=0, C=0 Minterm is A'.B'.C'
A=1, B=0, C=1 Minterm is A.B'.C
SOP form can be obtained by

Writing an AND term for each input combination, which produces HIGH output.
Writing the input variables if the value is 1, and write the complement of the variable
if its value is 0.
OR the AND terms to obtain the output function.
Ex: Boolean expression for majority function F = A’BC + AB’C + ABC ‘ + ABC

A’BC

AB’C
ABC’
ABC
 Consider a function X, whose
truth table is as follows
(INPUTS) (OUTPUT)
ABC X DECIMAL
000 0 0
001 1 1
The function X can be written in SOP form by adding all the min-terms when X
010 0 2 is HIGH(1).
011 1 3 While writing SOP, the following convention is to be followed:

100 0 4
101 0 5
If variable A is Low(0) - A'
110 1 6
A is High(1) - A
111 0 7
X (SOP) = \Sigma m(1, 3, 6)
= A’.B’.C + A’.B.C + A.B.C’
 Product of Sums (POS) Form/ PRODUCT OF MAX TERMS

POS form can be obtained by

Writing an OR term for each input combination, which produces LOW output.
Writing the input variables if the value is 0, and write the complement of the
variable if its value is 1.
AND the OR terms to obtain the output function.
Ex: Boolean expression for majority function F = (A + B + C) (A + B + C ‘) (A + B’ + C)
(A’ + B + C)
Boolean expression for majority function F = (A + B + C) (A + B + C ‘) (A + B’ + C) (A’ +
B + C)
 SOP POS

A way of representing boolean

A way of representing boolean expressions as product of sum
1. expressions as sum of product
terms.
terms.

SOP uses minterms. Minterm is

product of boolean variables either POS uses maxterms. Maxterm is sum of boolean variables either
2.
in normal form or complemented in normal form or complemented form.
form.

It is sum of minterms. Minterms are

3. It is product of maxterms. Maxterms are represented as ‘M’
represented as ‘m’

SOP is formed by considering all the POS is formed by considering all the maxterms, whose output is
4.
minterms, whose output is HIGH(1) LOW(0)

While writing minterms for SOP,

input with value 1 is considered as While writing maxterms for POS, input with value 1 is considered
5. the variable itself and input with as the complement and input with value 0 is considered as the
value 0 is considered as variable itself.
complement of the input.
 Write a Boolean SOP
expression for this truth
table, then simplify that
expression as much as
possible
A B C Output
0000
0010
0101 A’BC’
0110
1000
1010
1101 ABC’ Original SOP expression:
1110
A’BC’+ABC’ = BC’(A’+A)= BC’
( SINCE A+A’=1)
 Conversion of SOP form to standard SOP form or Canonical SOP form
For getting the standard SOP form of the given non-standard SOP form, we will add all
the variables in each product term which do not have all the variables. By using the
Boolean algebraic law, (x + x' = 0) and by following the below steps we can easily
convert the normal SOP function into standard SOP form.

Multiply each non-standard product term by the sum of its missing variable and its
complement.
Repeat step 1, until all resulting product terms contain all variables
For each missing variable in the function, the number of product terms doubles.
Convert the non standard SOP function F = AB + A C + B C INTO
CANONICAL

Sol:

F=AB+AC+BC
= A B (C + C') + A (B + B') C + (A + A') B C
= A B C + A B C' + A B C + A B' C + A B C + A' B C
= A B C + A B C' + A B' C + A' B C
 Conversion of POS form to standard POS form or Canonical POS form

For getting the standard POS form of the given non-standard POS form, we will
add all the variables in each product term that do not have all the variables.
By using the Boolean algebraic law (x * x' = 0) and by following the below steps,
we can easily convert the normal POS function into a standard POS form.

By adding each non-standard sum term to the product of its missing

variable and its complement, which results in 2 sum terms
Applying Boolean algebraic law, x + y z = (x + y) * (x + z)
By repeating step 1, until all resulting sum terms contain all variables

By these three steps, we can convert the POS function into a standard POS
function.
F = (p' + q + r) * (q' + r + s') * (p + q' + r' + s)

1. Term (p' + q + r)

As we can see that the variable s or s' is missing in this term. So we add s*s' = 1 in this
term.

(p' + q + r + s*s') = (p' + q + r + s) * (p' + q + r + s')

2. Term (q' + r + s')

Similarly, we add p*p' = 1 in this term for getting the term containing all the
variables.

(q' + r + s' + p*p') = (p + q' + r + s') * (p' + q' + r + s')

 3. Term (q' + r + s')

Now, there is no need to add anything because all the variables are contained in this
term.

So, the standard POS form equation of the function is

F = (p' + q + r + s)* (p' + q + r + s')* (p + q' + r + s')* (p' + q' + r + s') * (p + q' + r' + s)
 CONVERT THE EXP INTO CANONICAL FORM
F(P,Q,R)= PQ+PR’+QR’
F(..) = PQ(R+R’) + PR’(Q+Q’) + QR’(P+P’)
= PQR+PQR’+PQR’+PQ’R’+PQR’+P’QR’
= 111 , 110 , 100, 110,010

= M7, M6, M4, M2

 SIMPLIFICATION OF BOOLEAN TERM _(A+B’+C) (A+B+C)(A+B’+C’)

= (A+B’+C) (A+B+C)(A+B’+C’)
= LETS SUPPOSE A+C = X
= X+B’) (X+B)(A+B’+C’)
= DISTRIBUTIVE LAW : X+BB’ = (X+B )(X+B’)
= X+BB’ (A+B’+C’)
= X (A+B’+C’)
= (A+C)(A+B’+C’)
= AGAIN DISTRIBUTIVE LAW A+BC= (A+B) (A+C)
= A+ C.(B’+C’)
= A+B’C+CC’
= A+B’C
 Karnaugh Map-

The Karnaugh Map also called as K Map is a graphical representation

that provides a systematic method for simplifying the boolean expressions.

For a boolean expression consisting of n-variables, number of cells required

in K Map = 2n cells.
 Two Variable K Map-

Two variable K Map is drawn for a boolean expression consisting of two

variables.
The number of cells present in two variable K Map = 22 = 4 cells.
So, for a boolean function consisting of two variables, we draw a 2 x 2 K Map.
 Three Variable K Map-

Three variable K Map is drawn for a boolean expression consisting of three

variables.
The number of cells present in three variable K Map = 23 = 8 cells.
So, for a boolean function consisting of three variables, we draw a 2 x 4 K
Map.

Three variable K Map may be represented as-

 Four Variable K Map-

Four variable K Map is drawn for a boolean expression consisting of four

variables.
The number of cells present in four variable K Map = 24 = 16 cells.
So, for a boolean function consisting of four variables, we draw a 4 x 4 K Map.

Four variable K Map may be represented as-

 Karnaugh Map Simplification Rules-

To minimize the given boolean function,

We draw a K Map according to the number of variables it contains.

We fill the K Map with 0’s and 1’s according to its function.
Then, we minimize the function in accordance with the following rules.
Rule-01: We can either group 0’s with 0’s or 1’s with 1’s but we can not group 0’s and
1’s together.
X representing don’t care can be grouped with 0’s as well as 1’s.
Rule-02: Groups may overlap each other.

Rule-03: We can only create a group whose number of cells can be represented in
the power of 2.In other words, a group can only contain 2n i.e. 1, 2, 4, 8, 16 and so on
number of cells.
Rule-04 :
Groups can be only either horizontal or vertical.
We can not create groups of diagonal or any other shape.
Rule-05: Each group should be as large as possible.
Rule-06: Opposite grouping and corner grouping are allowed.
The example of opposite grouping is shown illustrated in Rule-05.
The example of corner grouping is shown below.
Rule-07: There should be as few groups as possible.
Simplify the given 2-variable Boolean equation by using K-map.

F = X Y’ + X’ Y + X’Y’

First, let’s construct the truth table for the given equation,

By reducing each group, we obtain a conjunction of the minimized expression such

as by taking out the common terms from two groups, i.e. X’ and Y’. So the reduced
equation will be X’ +Y
 3 variable K-maps
For a 3-variable Boolean function, there is a possibility of 8 output min
terms. The general representation of all the min terms using 3-variables is
shown below.
Simplify the given 3-variable Boolean equation by using k-map.

F = X’ Y Z + X’ Y’ Z + X Y Z’ + X’ Y’ Z’ + X Y Z + X Y’ Z’

First, let’s construct the truth table for the given equation,
Simplify the given 4-variable Boolean equation by using k-map. F (W, X, Y, Z) = (1, 5, 12,
13)

Sol: F (W, X, Y, Z) = (1, 5, 12, 13)

By preparing k-map, we can minimize the given

Boolean equation as

F = W Y’ Z + W ‘Y’ Z
 Problem-01:
Minimize the following boolean function-

F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15)

Solution-
Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.
We fill the cells of K Map in accordance with the given boolean function.
Then, we form the groups in accordance with the above rules.
 Now,
F(A, B, C, D) = (A’B + AB)(C’D + CD) + (A’B’ + A’B + AB + AB’)C’D + (A’B’ + AB’)(C’D’ + CD’) =
BD + C’D + B’D’
F(A, B, C, D) = BD + C’D + B’D’
 Minimize the following boolean function-

F(A, B, C, D) = Σm(0, 1, 3, 5, 7, 8, 9, 11, 13, 15)

Solution-

Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.

We fill the cells of K Map in accordance with the given boolean function.
Then, we form the groups in accordance with the above rules.
F(A, B, C, D) = (A’B’ + A’B + AB + AB’)(C’D + CD) + (A’B’ + AB’)(C’D’ + C’D)

= D + B’C’
Thus, minimized boolean expression is-

F(A, B, C, D) = B’C’ + D
 Various Implicants in K-Map

An implicant refers to the product/minterm term in the SOP (Sum of Products) or

the sum/maxterm term in the POS (Product of Sums) of a Boolean function. For
example, let us consider any boolean function, F = MN + MNO + NO, then implicants
are MN, MNO and NO.

Prime Implicants
A group of squares or rectangles made up of a bunch of adjacent minterms that is
allowed by definition of a Karnaugh Map are known as prime implicants or PI, i.e. all
the possible groups that are formed in K-Map.

Example
 Redundant Prime Implicants
The redundant prime implicants or RPI refer to the prime implicants for
which every one of its minterms gets covered by some important prime
implicants. This type of prime implicant never happens to appear in the final
solution.

Example
 Essential Prime Implicants
These refer to those subcubes or groups that cover at least one of the
minterms that can’t get covered by another prime implicant. The EPI or
essential prime implicants refer to the prime implicants that always appear
in the final solution.
 Selective Prime Implicants
The SPI or selective prime implicants refer to those prime implicants for
which neither the redundant nor essential prime implicants are there. They
are also called non-essential prime implicants. These may appear in certain
types of solutions or may not even appear in some solutions at all.

Example
 Example-1
Find the number of implicants, EPI, PI, RPI and SPI if F = ∑(1, 5, 6, 7, 11, 12, 13,
15)
Find the number of implicants, EPI, PI, RPI and SPI if F = ∑(0, 1, 5, 8, 12, 13)
 Example-3
Find the number of implicants, EPI, PI, RPI and SPI if F = ∑(0, 1, 5, 7, 15, 14, 10)