25th May, 2020 JESUS AND MARY SCHOOL & COLLEGE MODULE 2

CLASS 12

COMPUTER SCIENCE

BOOLEAN ALGEBRA AND LOGIC SIMPLIFICATION

Sum Of Product (SOP)

Sum of Product is the abbreviated form of SOP. Sum of product form is a form of expression in
Boolean algebra in which different product terms of inputs are being summed together. This product is
not arithmetical multiply but it is Boolean logical AND and the Sum is Boolean logical OR.
To understand better about SOP, we need to know about min term.
Min Term
Minterm means the term that is true for a minimum number of combinations of inputs. That is true for
only one combination of inputs.
Since AND gate also gives True only when all of its inputs are true so we can say min terms are AND of
input combinations like in the table given below

.
3 inputs have 8 different combinations. Each combination has a min terms denoted by small m and its
decimal combination number written in subscript. Each of these minterms will be only true for the
specific input combination.

Types of Sum Of Product (SOP) Forms

There are few different forms of Sum of Product.

 Canonical SOP Form
 Non-Canonical SOP Form
 Minimal SOP Form
Canonical SOP Form
“Canonical” means “standardized” and “disjunctive” means “Logical OR union”. Canonical SOP
expression is represented by summation sign ∑ and minterms in the braces for which the output is true.

For this function the canonical SOP expression is

F = ∑( m1, m2, m3, m5 )
Which means that the function is true for the min terms {1, 2, 3, 5}.
By expanding the summation we get.
F = m 1 + m2 + m3 + m5
Now putting min terms in the expression
F = A̅ B̅ C + A̅ BC̅ + A̅ BC + AB̅ C
Canonical form contains all inputs either complemented or non-complemented in its product terms.
Non-Canonical SOP Form
As the name suggests, this form is the non-standardized form of SOP expressions. The product terms are
not the min terms but they are simplified. Let’s take the above function in canonical form as an example.
F = A̅ B̅ C + A̅ BC̅ + A̅ BC + AB̅ C
F = A̅ B̅ C + A̅ B(C̅ + C) + AB̅ C
F = A̅ B̅ C + A̅ B(1) + AB̅ C
F = A̅ B̅ C + A̅ B + AB̅ C
This expression is still in Sum of Product form but it is non-canonical or non-standardized form.
Minimal SOP Form
This form is the most simplified SOP expression of a function. It is also a form of non-canonical form.
Product of Sum
Product of Sum abbreviated for POS.
The product of Sum form is a form in which products of different sum terms of inputs are taken. These
are not arithmetic product and sum but they are logical Boolean AND and OR respectively.
Max Term
Maxterm means the term or expression that is true for a maximum number of input combinations or that
is false for only one combination of inputs.
Since OR gate also gives false for only one input combination. So Maxterm is OR of either
complemented or non-complemented inputs.
Max terms for 3 input variables are given below

.
3 inputs have 8 different combinations so it will have 8 maxterms. Maxterms are denoted by capital M
and decimal combination number In the subscript as shown in the table given above.
In maxterm, each input is complemented because Maxterm gives ‘0’ only when the mentioned
combination is applied and Maxterm is complement of minterm.
M3 = m̅ 3

M3 = (A̅ BC)’
M3 = A + B̅ +C̅ DE Morgan’s law
Which is why for A=0 Max term consist A & for A=1 Max term consist A̅ .

Types of Product Of Sum Forms

There are different types of Product of Sum forms.
 Canonical POS Form
 Non – Canonical Form
 Minimal POS Form
Canonical POS Form
It is also known as Product of Max term or Canonical Conjunctive Normal Form (CCNF). Canonical
means standard and conjunctive means intersection.
In this form, Maxterms are AND together for which output is false.
Canonical POS expression is represented by ∏ and Maxterms for which output is false in brackets as
shown in the example given below.

F = ∏ (M0, M4, M6, M7)

Expanding the product
F = M0.M4.M6.M7
F = (A+B+C)(A̅ +B+C)(A̅ +B̅ +C)(A̅ +B̅ +C̅ )
The canonical form contains all inputs either complemented or non-complemented in its each Sum term.
Non – Canonical Form
The product of sum expression that is not in standard form is called non-canonical form.
Let’s take the above-given function as an example.
F = (A+B+C)(A̅ +B+C)(A̅ +B̅ +C)(A̅ +B̅ +C̅ )
F = (B+C) (A̅ +B̅ +C)(A̅ +B̅ +C̅ )
Same but inverted terms eliminates from two Max terms and form a single term to prove it here is an
example.
= (A+B+C) (A̅ +B+C)
= AA̅ +AB+AC+A̅ B+BB+BC+A̅ C+BC+CC
= 0+AB+AC+A̅ B+A̅ C+B+BC+C
= A(B+C)+A̅ (B+C)+B(1+C)+C
= (B+C)(A+A̅ )+B(1)+C
= (B+C)(0)+B+C
= B+C
The expression achieved is still in Product of Sum form but it is non-canonical form.
Minimal POS Form
This is the most simplified and optimized form of a POS expression which is non-canonical.
Conversions of Canonical Forms

We can represent the one canonical formed equation in other canonical form i.e. we can represent the
SOP form of equation in POS form and POS form equation in SOP form. To convert the canonical
equations, we interchange the Σ and Π symbols after listing out the index numbers of the equations,
which are excluded from the original form of equation.

The important thing to remember about Boolean functions is that, the SOP and POS forms are Duals to
each other. There are 2 steps to follow to convert the canonical form of the equations. They are

Step 1: Interchanging the operational symbols, Σ and Π in the equation.

Step 2: Use the De Morgan’s principle of Duality to the index numbers of the Boolean function or
writing the indexes of the terms that are not presented in the given form of equation.

Conversion of SOP form to POS form

To convert the SOP form into POS form, first we should change the Σ to Π and then write the numeric
indexes of missing variables of the given Boolean function.

Example:

The SOP function

F = ∑ A, B, C (0, 2, 3, 5, 7) = A’ B’ C’ + A B’ C’ + A B’ C + ABC’ + ABC is written in POS form by

Step 1: changing the operational sign to Π

Step 2: writing the missing indexes of the terms, 001, 100 and 110. Now write the sum form for these
noted terms.

001 = (A + B + C) ,100 = (A + B’ + C’), 110 = (A + B’ + C’)

Writing down the new equation in the form of POS form,

F = Π A, B, C (1, 4, 6) = (A + B + C) * (A + B’ + C’) * (A + B’ + C’)

Conversion of POS form to SOP form

To convert the POS form into SOP form, first we should change the Π to Σ and then write the numeric
indexes of missing variables of the given Boolean function.

Ex: The POS function F = Π A, B, C (2, 3, 5) = A B’ C’ + A B’ C + ABC’ is written in SOP form by

Step 1: changing the operational sign to Σ

Step 2: writing the missing indexes of the terms, 000, 001, 100, 110, and 111. Now write the product
form for these noted terms.

000 = A’ * B’ * C’ ,001 = A’ * B’ * C, 100 = A * B’ * C’

110 = A * B* C’ 111 = A * B * C

Writing down the new equation in the form of SOP form,

F = Σ A, B, C (0, 1, 4, 6, 7) = (A’ * B’ * C’) + (A’ * B’ * C) + (A * B’ * C’) + (A * B* C’) + (A * B * C)

Conversion of SOP form to standard SOP form or Canonical SOP form

We can include all the variables in each product term of the SOP form equation, which doesn’t have all
the variables by converting into standard SOP form. The normal SOP form function can be converted to
standard SOP form by using the Boolean algebraic law, (A + A’ = 1) and by following the below steps.

Step 1:

By multiplying each non-standard product term with the sum of its missing variable and its complement,
which results in 2 product terms

Step 2:

By repeating the step 1, until all resulting product terms contain all variables

By these two steps we can convert the SOP function into standard SOP function. In this process, for
each missing variable in the function, the number of product terms will double.

Example:

Convert the non standard SOP function F = x y + x z + y z

Sol: F=xy+xz+yz

= x y (z + z’) + x (y + y’) z + (x + x’) y z

= x y z + x y z’ + x y z + x y’ z + x y z + x’ y z

= x y z + x y z’ + x y’ z + x’ y z

The standard SOP form is F = x y z + x y z’ + x y’ z + x’ y z

Conversion of POS form to standard POS form or Canonical POS form

We can include all the variables in each product term of the POS form equation, which doesn’t have all
the variables by converting into standard POS form. The normal POS form function can be converted to
standard POS form by using the Boolean algebraic law, (A * A’ = 0) and by following the below steps.

Step 1:
By adding each non-standard sum term to the product of its missing variable and its complement, which
results in 2 sum terms
Step 2:
Applying Boolean algebraic law, A + BC = (A + B) * (A + C)
Step 3:
By repeating the step 1, until all resulting sum terms contain all variables
By these three steps we can convert the POS function into standard POS function.
Example:
F = (A’ + B + C) * (B’ + C + D’) * (A + B’ + C’ + D)
In the first term, the variable D or D’ is missing, so we add D*D’ = 1 to it. Then
(A’ + B + C + D*D’) = (A’ + B + C + D) * (A’ + B + C + D’)
Similarly, in the second term, the variable A or A’ is missing, so we add A*A’ = 1 to it. Then
(B’ + C + D’ + A*A’) = (A + B’ + C + D’) * (A’ + B’ + C + D’)
The third term is already in the standard form, as it has all the variables. Now the standard POS form
equation of the function is
F = (A’ + B + C + D) * (A’ + B + C + D’) * (A + B’ + C + D’) * (A’ + B’ + C + D’) * (A + B’ + C’ + D)

Cardinal form of min term or max term Expression

A boolean function which is defined by using min term designations is known as cardinal form of min
term expression.
Syntax For min term expression
F(variables) = Σ (min term designations)
Example A’B’C +ABC’+ABC
001 (1 or m1) 110(6 is decimal of 110 or m6) 111 (7 or m7)
F(A,B,C) = Σ (1,6,7) (it is Cardinal form)
OR
For min term expression
F(variables) = Π (max term designations)
Example (A’+B’+C) .(A+B+C’).(A+B+C)
110 (6 or m6) 001(1 is decimal of 001 or m1) 000 (0 or m0)
F(A,B,C) = Π (0,1,6) (it is Cardinal form)
 WORKSHEET 1

Assignment Work

1. Convert the expression A + B into its equivalent canonical SOP form.

2. Convert the expression A + B.C into its equivalent canonical SOP form.
3. Obtain min term expression from the cardinal form of Boolean function as given below
F(A,B,C) = Σ (5,3,1,6)
4. Convert the expression A. B into its equivalent canonical POS form.
5. Convert the expression A. (B + C) into its equivalent canonical POS form.
6. Obtain max term expression for the Boolean function given below-
F(A,B,C) = Π (7, 0, 3, 5)
7. Convert the following Boolean function into Canonical POS forms
(X + Y’).(Y’ + Z)
8. Simplify of the Boolean expression by using Boolean laws:
A.(A’ + B).C.(A + B)
9. Differentiate between canonical and cardinal form of expression.
10. Convert the following SOP expression into its corresponding product of sum form
F(O,V,W) = O’.V’.W’ + O’.V’.W + O’.V.W + O.V.’W
11. Write a Program in Java to fill a 2-D array with the first ‘m*n’ prime numbers, where ‘m’ is the
number of rows and ‘n’ is the number of columns.
For example: If rows(m) = 4 and columns(n) = 5, then the result should be:

Note: - Please do all this work in your copies which will be check when school be re-open.

Please consider this important