Question

Minimize the sums of products as well as the product of sums using k-maps, and using Boolean algebra show which pairs are equivalent.

Answer 1

SOP

f= (xyz +x`yz+ xy`z+ .....) Is called sum of products.

The + is sum operator which is an OR gate.The product such as xy is an AND gate for the two inputs x and y

Eg:     

Q. Minimize the following Boolean function using sum of products (SOP)

• f(a,b,c,d) = m(3,7,11,12,13,14,15)

(a,b,c,d) = m(3,7,11,12,13,14,15)

=a`b`cd + a`bcd + ab`cd + abc`d`+ abc`d + abcd` + abcd

=cd(a`b` + a`b + ab`) + ab(c`d` + c`d + cd` + cd )

=cd(a`[b` + b] + ab`) + ab(c`[d` + d] + c[d` + d])

=cd(a`[1] + ab`) + ab(c`[1] + c[1])

=ab+ab`cd + a`cd =ab+cd(ab` + a`)

=ab+ cd(a + a`)(a`+b`)

= ab + a`cd + b`cd

= ab +cd(a` + b`)

POS

Minimum product of sums (MPOS).The minimum product of sums (MPOS) of a function, f, is a POS representation of fthat contains the fewest number of sum terms and the fewest number of literals of any POS representation of f..The zeros are considered exactly the same as ones in the case of sum of product (SOP)

example

f(a,b,c,d) = M(0,1,2,4,5,6,8,9,10)

=m(3,7,11,12,13,14,15)

=[(a+b+c+d)(a+b+c+d`)(a+b`+c`+d`)(a`+b+c`+d`)(a`+b`+c+ d)(a`+b`+c+ d`) (a`+b`+c`+d)(a`+b`+c`+d`)]

Karnaugh Maps (K-maps)

Karnaugh maps --A tool for representing Boolean functions of up to six variables.•K-maps are tables of rows and columns with entries represent 1`s or 0`s of SOP and POS representations.

Simplification of Boolean FunctionsUsing K-maps•K-map cells that are physically adjacent are also logically adjacent. Also, cells on an edge of a K-map are logically adjacent to cells on the opposite edge of the map.•If two logically adjacent cells both contain logical 1s, the two cells can be combined to eliminate the variable that has value 1 in one cell’s label and value 0 in the other.

Simplification of Boolean Functions Using K-maps

•This is equivalent to the algebraic operation, aP + a'P =P where P is a product term not containing aor a'.•A group of cells can be combined only if all cells in the group have the same value for some set of variables.

Prove the distributive law :A+(BC)=(A+B)(A+C)

LHS = A + BC = A.1 + BC ,using A.1 = A
= A(1 + B) + BC ,using 1+B = 1
=A + AB +BC
=A(1 + C) +AB +BC , using 1+C = 1
=A + AC +AB +BC
=A*A + AC + AB + BC ,using A*A=A
=(A+B) (A+C) =RHS