Sop and pos

sum of product and product of sum

1. Digital Logic and
•Introduction
•Sum of Products (SOP)
•Product of Sums (POS)
CONTENT
Circuit Design
SOP and POS
Representations
•Mintermsand Maxterms
•Canonical Representation
AKASH KANUGO,SVVV

2. Boolean Function
•A Boolean function can be described :
―By an algebraic expression.
―Using a Truth Table.•A Boolean function described by an algebraic expression consists of binary
variables, the constants 0 and 1, and the logic operation symbols. variables, the constants 0 and 1, and the logic operation symbols.
•Example : F = A + B’C
•For a given value of the binary variables, the function can be equal to
either 1 or 0.
•In algebraic form, Boolean function can be expressed in a variety of ways,
all of which have equivalent logic.
AKASH KANUGO,SVVV

3. Standard Forms
•All Boolean functions, regardless of their form, can be converted into either
of two standard forms:
―The Sum-of-Product (SOP) form.
―The Product -of-Sum (POS) form
.
•Standardization makes the evaluation, simplification, and implementation
of Boolean expressions much more systematic and easier.
AKASH KANUGO,SVVV

4. Sum of Product (SOP) Form
•The sum of products is a Boolean expression containing AND terms, called
product terms, with one or more literals each. The sum denotes the ORing
of these terms.
•Example:
F = AB + CD + CE
F = A + B’C
F = AB’C’ + A’B’C + A’BC
The logic diagram of a sum-of-products
expression consists of a group of AND gates
followed by a single OR gate.
F
AKASH KANUGO,SVVV

5. Product of Sums (POS) Form
•A product of sums is a Boolean expression containing OR terms, called sum
terms. Each term may have any number of literals. The product denotes
the ANDingof these terms.
•Example:
F = (A’ + B’) (C’ + D’) (B’ + D)
F = A (B’ + C ) (A’ + B + C)
F = (A + B’ + C’) (A’ + B’ + C) (A’ +B + C)
The logic diagram of a product-of-sums
expression consists of a group of OR gates
followed by a single AND gate.
AKASH KANUGO,SVVV

6. Mintermsand Maxterms
•For a Boolean function, a literalis defined as a variable in uncomplementedor
complemented form.
–Example: A, A’, B, B’, etc.•Consider an n-variable Boolean function f (x
1
, x
2
, …, x
n
).
12 n
–A product term (that is, an AND operation) of all the nliterals is called a minterm.
–A sum term (that is, an OR operation) of all the nliterals is called a maxterm.
•Consider a 3-variable function f (A, B, C).
–Examples of minterm: A’.B’.C’, A.B’.C, A.B.C, etc.
–Examples of maxterm: (A + B’ + C’), (A’ + B’ + C’), (A + B + C), etc.
AKASH KANUGO,SVVV

7. Mintermsand Maxterms
•Boolean function of n variables will have 2
n
minterms, corresponding to each
combination of variables.
•Boolean function of n variables will have 2
n
maxterms, corresponding to each
combination of variables.
•For a given row of the truth table, the mintermis formed by including variable •For a given row of the truth table, the mintermis formed by including variable
xif x = 1 and by including x’ if x = 0.
•For a given row of the truth table, the maxtermis formed by including variable
xif x = 0 and by including x’ if x = 1.
AKASH KANUGO,SVVV

8. Minterms Maxterms
ABCTermDesignationTermDesignation
000A’.B’.C’ m
0
A+ B + CM
0
001A’.B’.C m
1
A + B + C’M
1
0 1 0 A’.B.C’ m
2
A + B’ + C M
2
Mintermsand Maxtermsfor Three Binary Variables
0 1 0 A’.B.C’ m
2
A + B’ + C M
2
011A’.B.C m
3
A + B’ + C’M
3
100A.B’.C’ m
4
A’ + B + CM
4
101A.B’.C m
5
A’ + B + C’M
5
110A.B.C’ m
6
A’ + B’ + CM
6
111A.B.C m
7
A’+ B’ + C’M
7
AKASH KANUGO,SVVV

9. •Properties of mintermsand maxterms:
–A mintermassumes value 1 for exactly one combination of variables.
–A maxtermassumes the value 0 for exactly one combination of variables.
•Example: Minterm: A’B’C’ assumes value 1 only for A=0, B= 0 and C=0.
Maxterm: A’ + B + C’ assumes value 0 only for A= 1, B=0 and C= 1.
Mintermsand Maxterms
Maxterm: A’ + B + C’ assumes value 0 only for A= 1, B=0 and C= 1.
•Each mintermis the complement of corresponding maxtermand vice -versa .
•Example : Consider maxterm, M
0
= A + B + C
M
0
’ = (A + B + C )’
M
0
’ = A’B’C’
M
0
'= m
0
AKASH KANUGO,SVVV

10. Canonical Form of Representing Functions
•A canonical form is a unique representation of a function.
•We can derive two canonical representations directly from the truth table:
a)Canonical sum-of-products form
b)Canonical product-of-sums formb)Canonical product-of-sums form
AKASH KANUGO,SVVV

11. Canonical Sum -of –Products form
•It is defined as the logical sum of all the mintermsderived from the rows of
a truth table for which the value of the function is 1.
•Example for the full adder:
S = A’.B’.C + A’.B.C’ + A.B’.C’ + A.B.C
Co = A’.B.C + A.B’.C + A.B.C’ + A.B.C
•We can write down the canonical s-o-p expressions in a compact way by
noting down the decimal equivalents of the input combinations:
S = Σ (1, 2, 4, 7)
Co = Σ (3, 5, 6, 7)
AKASH KANUGO,SVVV

12. Example : Full Adder
ABCSCo
00000
00110
01010
S = A’.B’.C + A’.B.C’ + A.B’.C’ + A.B.C
S = ∑ ( 1,2,4,7)
•A full adder adds three bits A, B, C, and
generates a sum Sand a carry Co.
01101
10010
10101
11001
11111
S = ∑ ( 1,2,4,7)
Co = A’.B.C + A.B’.C + A.B.C’ + A.B.C
Co = ∑ ( 3,5,6,7)
AKASH KANUGO,SVVV

13. •The principle of duality suggests that :
–If it is possible to represent a function F by considering the rows in the truth
table for which F = 1, then it should also be possible to represent Fby
considering the rows for which F = 0.
•This alternative approach uses the complements of minterms, which are called
Canonical Product-of-Sums Form
•This alternative approach uses the complements of minterms, which are called
maxterms.
•This representation is known as Canonical Product-of –Sums form.
AKASH KANUGO,SVVV

14. Canonical Product-of-Sums Form
•It is defined as the logical product of all the maxtermsderived from the
rows of truth table for which the value of function is 0.
•Example for the full adder:
S = (A + B + C) . (A + B’ + C’) . (A’ + B + C’) . (A’ + B’ + C)
Co = (A + B + C) . (A + B + C’) . (A + B’ + C) . (A’ + B + C)
•We can write down the canonical p-o-s expressions in a compact way by
noting down the decimal equivalents of the input combinations:
S = Π (0, 3, 5, 6)
Co = Π (0, 1, 2, 4)
AKASH KANUGO,SVVV

15. Example : Full Adder
ABCSCo
00000
00110
S = (A + B + C) . (A + B’ + C’) . (A’ + B + C’) . (A’ + B’ + C)
S = Π (0, 3, 5, 6) 01010
01101
10010
10101
11001
11111
S = Π (0, 3, 5, 6)
Co = (A + B + C) . (A + B + C’) . (A + B’ + C) . (A’ + B + C)
Co = Π (0, 1, 2, 4)
AKASH KANUGO,SVVV

16. Algebraic Procedure to Obtain Canonical S-O-P
a)Examine each term of a given sum-of-products expression; if it is not a minterm, go to
the next step.
b)For all missing variable x
i
, multiply the term by (x
i
+x
i
’) .
c)Multiply out all products and eliminate redundant product terms.
Example: F (A, B, C) = A + B’.C + A.B.C
= A (B + B’) (C + C’) + B’.C (A + 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 + A.B’.C’ + A’.B’.C
F ( A, B, C) = ∑ ( 1, 4, 5, 6, 7)
AKASH KANUGO,SVVV

17. Algebraic Procedure to Obtain Canonical P-O-S
a)Examine each term of a given product-of-sums expression; if it is not a maxterm, go to
the next step.
b)For all missing variable x
i
, add the term x
i
.x
i
’
c)Obtain the sum terms using distributive law, and eliminate redundant terms.
Example: F (A, B, C) = A’ (B’ + C)Example: F (A, B, C) = A’ (B’ + C)
= (A’ + B.B’ + C.C’) (B’ + C + A.A’)
= [(A’ + B ) (A’ + B’) + C.C’] [ B’ + C + A] [ B’ + C + A’]
= ( A’ + B + C.C’) (A’ + B’ + C.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’)(A’ + B’ + C)(A’ + B’ + C’)(A+ B’ + C)
F ( A, B, C ) = ∏ ( 2, 4, 5, 6, 7)
AKASH KANUGO,SVVV

18. Example : Canonical P-O-S
•Express the Boolean function F (A, B, C) = A.B + A’.C as Canonical POS form.
•First, convert the function into OR terms by using the distributive law,
F ( A, B , C) = ( A.B + A’) (A.B + C ) F ( A, B , C) = ( A.B + A’) (A.B + C )
= ( A + A’) ( B + A’) ( A + C ) (B + C)
= ( A’ + B ) ( A + C ) ( B + C )
AKASH KANUGO,SVVV

19. •F ( A, B, C) = ( A’ + B ) ( A + C ) ( B + C )
= ( A’ + B + C.C’) ( A + C + B.B’) ( B + C + A.A’)
= (A’ + B + C) (A’ + B + C’) (A + C + B) (A + C + B’) (B + C + A) (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) (A + B’ + C) (A’ + B + C) (A’ + B + C’)
= M
0
.M
2
.M
4
.M
5
•F ( A, B, C) = ∏ ( 0, 2, 4, 5 )
AKASH KANUGO,SVVV

20. Conversion between Canonical Forms
•Express the following Boolean function as Canonical POS form.
F ( A , B , C ) = A’.B’.C’ + A’.B’.C + A’.B.C’ + A.B.C’ + A.B.C
AKASH KANUGO,SVVV

21. Conversion between Canonical Forms
•F ( A , B , C ) = A’.B’.C’ + A’.B’.C + A’.B.C’ + A.B.C’ + A.B.C
•The complement of a function can be expressed as sum of those minterms
which are missing from the original function.
•F’ = A’.B.C + A.B.C’ + A.B’.C•F’ = A’.B.C + A.B.C’ + A.B’.C
Now taking complement of both sides results,
(F’)’ = (A’.B.C + A.B.C’ + A.B’.C)’
F = (A’.B.C)’.(A.B.C’)’. (A.B’.C)’
F = [ (A’)’ + B’ + C’ ] [ A’ + B’ + (C’)’] [ A’ + (B’)’ + C’]
F = ( A + B’ + C’) ( A’ + B’ + C ) ( A’ + B + C’)
Demorgan’sTheorem
AKASH KANUGO,SVVV

22. Alternative Procedure
F = A’.B’.C’ + A’.B’.C + A’.B.C’ + A.B.C’ + A.B.C
ABCF
0001
0011
0 1 0 1
Truth Table
0 1 0 1
0110
1000
1010
1101
1111
F = ( A + B’ + C’) ( A’ + B’ + C) ( A’ + B + C’)
AKASH KANUGO,SVVV

23. Advantage of Canonical Form
•A canonical form is a unique representation of a function.
•It can be used to find the equivalency between Boolean functions.
•Example : Consider two Boolean functions:
•F
1
= A’C’ + BC + AB’ F
2
= AC + A’B + B’C’
•Converting both of them into Canonical SOP form results
•F
1
= ∑ (0, 2, 3, 4, 5, 6, 7) F
2
= ∑ (0, 2, 3, 4, 5, 6, 7)
•Thus these two functions are equivalent.
AKASH KANUGO,SVVV

24. Advantage of Canonical Form
•F
1
= A’C’ + BC + AB’
= A’C’ (B + B’) + BC (A + A’) + AB’(C + C’)
= A’BC’ + A’B’C’ + ABC + A’BC + AB’C + AB’C’
F
1
= ∑ (0, 2, 3, 4, 5, 6, 7)
F
2
= AC+ A’B + B’C’
= AC ( B + B’) + A’B( C + C’) + B’C’ ( A + A’)
= ABC + AB’C + A’BC + A’BC’ + AB’C’ + A’B’C’
= A’BC’ + A’B’C’ + ABC + A’BC + AB’C + AB’C’
F
2
= ∑ (0, 2, 3, 4, 5, 6, 7)
AKASH KANUGO,SVVV