Unit - 2

Boolean function minimization Techniques

Q1) What are the 3 basic boolean laws?

A1)

The three basic laws of Boolean Algebra are:

• Commutative law
• Associative law
• Distributive law

Commutative Law

• The logical operation carried between two Boolean variables when gives the same result irrespective of the order the two variables, then that operation is said to be Commutative. The logical OR & logical AND operations between x & y are shown below

x + y = y + x

x.y = y.x

• The symbol ‘+’ and ‘.’ indicates logical OR operation and logical AND operation.
• Commutative law holds good for logical OR & logical AND operations.

Associative Law

• If a logical OR operation of any two Boolean variables is performed first and then the same operation is performed with the remaining variable providing the same result, then that operation is said to be Associative. The logical OR & logical AND operations of x, y & z are:

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

x.(y.z) = (x.y).z

• Associative law holds good for logical OR & logical AND operations.

Distributive Law

• If a logical OR operation of any two Boolean variables is performed first and then AND operation is performed with the remaining variable, then that logical operation is said to be Distributive. The distribution of logical OR & logical AND operations between variables x, y & z are :

x.(y + z) = x.y + x.z

x + (y.z) = (x + y).(x + z)

• Distributive law holds good for logical OR and logical AND operations.

These are the Basic laws of Boolean algebra and we can verify them by substituting the Boolean variables with ‘0’ or ‘1’.

Q2) Consider  the following truth table.

A2)

• Here, the output (f) is ‘1’ for only four combinations of inputs.
• The corresponding min terms are given as p’qr, pq’r, pqr’, pqr.
• By doing logical OR, we get the Boolean function of output (f).
• Hence, the Boolean function of output is,

f = p’qr + pq’r + pqr’ + pqr.

• This is the desired canonical SoP form of output, f.
• It can also be represented as:

f=m3+m5+m6+m7f=m3+m5+m6+m7

f=∑m(3,5,6,7)f=∑m(3,5,6,7)

• First, we represented the function as sum of respective min terms and then, the symbol for summation of those min terms is used.

Q3) Convert the Boolean function into Standard SoP form.

f = p’qr + pq’r + pqr’ + pqr

A3)

Step 1 – By using the Boolean postulate, x + x = x and also writing the last term pqr two more times we get

⇒ f = p’qr + pq’r + pqr’ + pqr + pqr + pqr

Step 2 – By Using Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms.

⇒ f = qr(p’ + p) + pr(q’ + q) + pq(r’ + r)

Step 3 – Then Using Boolean postulate, x + x’ = 1 we get

⇒ f = qr(1) + pr(1) + pq(1)

Step 4 – hence using Boolean postulate, x.1 = x we get

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

This is the required Boolean function.

Q4) Convert the Boolean function into Standard PoS form.

f = (p + q + r).(p + q + r’).(p + q’ + r).(p’ + q + r)

A4)

Step 1 – By using the Boolean postulate, x.x = x and  writing the first term p+q+r two more times we get

⇒ f = (p + q + r).(p + q + r).(p + q + r).(p + q + r’).(p +q’ + r).(p’ + q + r)

Step 2 – Now by using Distributive law, x + (y.z) = (x + y).(x + z) for 1st and 4thparenthesis, 2nd and 5th parenthesis, 3rd and 6th parenthesis.

⇒ f = (p + q + rr’).(p + r + qq’).(q + r + pp’)

Step 3 − Applying Boolean postulate, x.x’=0 for simplifying of the terms present in each parenthesis.

⇒ f = (p + q + 0).(p + r + 0).(q + r + 0)

Step 4 − Using Boolean postulate, x + 0 = x we get

⇒ f = (p + q).(p + r).(q + r)

⇒ f = (p + q).(q + r).(p + r)

This is the simplified Boolean function.

Hence, both Standard SoP and Standard PoS forms are Dual to one another.

Q5) Simplify the Boolean function,

f = p’qr + pq’r + pqr’ + pqr

A5)

Method 1

Given

f = p’qr + pq’r + pqr’ +pqr.

In first and second term r is common and in third and fourth terms pq is common.

So, taking out the common terms by using Distributive law we get,

⇒ f = (p’q + pq’)r + pq(r’ + r)

The terms present in first parenthesis can be simplified by using Ex-OR operation.

The terms present in second parenthesis is equal to ‘1’ using Boolean postulate we get

⇒ f = (p ⊕q)r + pq(1)

The first term can’t be simplified further.

But, the second term is equal to pq using Boolean postulate.

⇒ f = (p ⊕q)r + pq

Therefore, the simplified Boolean function is f = (p⊕q)r + pq

Method 2

Given f = p’qr + pq’r + pqr’ + pqr.

Using the Boolean postulate, x + x = x.

Hence we can write the last term pqr two more times.

⇒ f = p’qr + pq’r + pqr’ + pqr + pqr + pqr

Now using the Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms we get.

⇒ f = qr(p’ + p) + pr(q’ + q) + pq(r’ + r)

Using Boolean postulate, x + x’ = 1 and x.1 = x for further simplification .

⇒ f = qr(1) + pr(1) + pq(1)

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Therefore, the simplified Boolean function is f = pq + qr + pr.

Hence we got two different Boolean functions after simplification of the given Boolean function. Functionally, these two functions are same. As per requirement, we can choose one of them.

Q6) Find the complement of the Boolean function,

f = p’q + pq’.

A6)

Using DeMorgan’s theorem, (x + y)’ = x’.y’ we get

⇒ f’ = (p’q)’.(pq’)’

Then by second law, (x.y)’ = x’ + y’ we get

⇒ f’ = {(p’)’ + q’}.{p’ + (q’)’}

Then by using, (x’)’=x  we get

⇒ f’ = {p + q’}.{p’ + q}

⇒ f’ = pp’ + pq + p’q’ + qq’

Using x.x’=0 we get

⇒ f = 0 + pq + p’q’ + 0

⇒ f = pq + p’q’

Therefore, the complement of Boolean function, p’q + pq’ is pq + p’q’.

Q7) Simplify f(X,Y,Z)=∏M(0,1,2,4)f(X,Y,Z)=∏M(0,1,2,4)using K-map.

A7)

Therefore, the simplified Boolean function is

f = (X + Y).(Y + Z).(Z + X)

Q8) Simplify:

F(P,Q,R,S)=∑(0,2,5,7,8,10,13,15)

A8)

F = P’Q’R’S’ + PQ’R’S’ + P’Q’RS’ +PQ’RS’ + QS

F = P’Q’S’ + PQ’S’ + QS

F = Q’S’ +QS

Q9) Simplify:

F(A,B,C)=π(0,3,6,7)

A9)

F = A’BC +ABC +A’B’C’ +ABC’

F = BC + C’ ( A’B’ + AB )

Unit - 2

Boolean function minimization Techniques

Q1) What are the 3 basic boolean laws?

A1)

The three basic laws of Boolean Algebra are:

• Commutative law
• Associative law
• Distributive law

Commutative Law

• The logical operation carried between two Boolean variables when gives the same result irrespective of the order the two variables, then that operation is said to be Commutative. The logical OR & logical AND operations between x & y are shown below

x + y = y + x

x.y = y.x

• The symbol ‘+’ and ‘.’ indicates logical OR operation and logical AND operation.
• Commutative law holds good for logical OR & logical AND operations.

Associative Law

• If a logical OR operation of any two Boolean variables is performed first and then the same operation is performed with the remaining variable providing the same result, then that operation is said to be Associative. The logical OR & logical AND operations of x, y & z are:

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

x.(y.z) = (x.y).z

• Associative law holds good for logical OR & logical AND operations.

Distributive Law

• If a logical OR operation of any two Boolean variables is performed first and then AND operation is performed with the remaining variable, then that logical operation is said to be Distributive. The distribution of logical OR & logical AND operations between variables x, y & z are :

x.(y + z) = x.y + x.z

x + (y.z) = (x + y).(x + z)

• Distributive law holds good for logical OR and logical AND operations.

These are the Basic laws of Boolean algebra and we can verify them by substituting the Boolean variables with ‘0’ or ‘1’.

Q2) Consider  the following truth table.

A2)

• Here, the output (f) is ‘1’ for only four combinations of inputs.
• The corresponding min terms are given as p’qr, pq’r, pqr’, pqr.
• By doing logical OR, we get the Boolean function of output (f).
• Hence, the Boolean function of output is,

f = p’qr + pq’r + pqr’ + pqr.

• This is the desired canonical SoP form of output, f.
• It can also be represented as:

f=m3+m5+m6+m7f=m3+m5+m6+m7

f=∑m(3,5,6,7)f=∑m(3,5,6,7)

• First, we represented the function as sum of respective min terms and then, the symbol for summation of those min terms is used.

Q3) Convert the Boolean function into Standard SoP form.

f = p’qr + pq’r + pqr’ + pqr

A3)

Step 1 – By using the Boolean postulate, x + x = x and also writing the last term pqr two more times we get

⇒ f = p’qr + pq’r + pqr’ + pqr + pqr + pqr

Step 2 – By Using Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms.

⇒ f = qr(p’ + p) + pr(q’ + q) + pq(r’ + r)

Step 3 – Then Using Boolean postulate, x + x’ = 1 we get

⇒ f = qr(1) + pr(1) + pq(1)

Step 4 – hence using Boolean postulate, x.1 = x we get

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

This is the required Boolean function.

Q4) Convert the Boolean function into Standard PoS form.

f = (p + q + r).(p + q + r’).(p + q’ + r).(p’ + q + r)

A4)

Step 1 – By using the Boolean postulate, x.x = x and  writing the first term p+q+r two more times we get

⇒ f = (p + q + r).(p + q + r).(p + q + r).(p + q + r’).(p +q’ + r).(p’ + q + r)

Step 2 – Now by using Distributive law, x + (y.z) = (x + y).(x + z) for 1st and 4thparenthesis, 2nd and 5th parenthesis, 3rd and 6th parenthesis.

⇒ f = (p + q + rr’).(p + r + qq’).(q + r + pp’)

Step 3 − Applying Boolean postulate, x.x’=0 for simplifying of the terms present in each parenthesis.

⇒ f = (p + q + 0).(p + r + 0).(q + r + 0)

Step 4 − Using Boolean postulate, x + 0 = x we get

⇒ f = (p + q).(p + r).(q + r)

⇒ f = (p + q).(q + r).(p + r)

This is the simplified Boolean function.

Hence, both Standard SoP and Standard PoS forms are Dual to one another.

Q5) Simplify the Boolean function,

f = p’qr + pq’r + pqr’ + pqr

A5)

Method 1

Given

f = p’qr + pq’r + pqr’ +pqr.

In first and second term r is common and in third and fourth terms pq is common.

So, taking out the common terms by using Distributive law we get,

⇒ f = (p’q + pq’)r + pq(r’ + r)

The terms present in first parenthesis can be simplified by using Ex-OR operation.

The terms present in second parenthesis is equal to ‘1’ using Boolean postulate we get

⇒ f = (p ⊕q)r + pq(1)

The first term can’t be simplified further.

But, the second term is equal to pq using Boolean postulate.

⇒ f = (p ⊕q)r + pq

Therefore, the simplified Boolean function is f = (p⊕q)r + pq

Method 2

Given f = p’qr + pq’r + pqr’ + pqr.

Using the Boolean postulate, x + x = x.

Hence we can write the last term pqr two more times.

⇒ f = p’qr + pq’r + pqr’ + pqr + pqr + pqr

Now using the Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms we get.

⇒ f = qr(p’ + p) + pr(q’ + q) + pq(r’ + r)

Using Boolean postulate, x + x’ = 1 and x.1 = x for further simplification .

⇒ f = qr(1) + pr(1) + pq(1)

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Therefore, the simplified Boolean function is f = pq + qr + pr.

Hence we got two different Boolean functions after simplification of the given Boolean function. Functionally, these two functions are same. As per requirement, we can choose one of them.

Q6) Find the complement of the Boolean function,

f = p’q + pq’.

A6)

Using DeMorgan’s theorem, (x + y)’ = x’.y’ we get

⇒ f’ = (p’q)’.(pq’)’

Then by second law, (x.y)’ = x’ + y’ we get

⇒ f’ = {(p’)’ + q’}.{p’ + (q’)’}

Then by using, (x’)’=x  we get

⇒ f’ = {p + q’}.{p’ + q}

⇒ f’ = pp’ + pq + p’q’ + qq’

Using x.x’=0 we get

⇒ f = 0 + pq + p’q’ + 0

⇒ f = pq + p’q’

Therefore, the complement of Boolean function, p’q + pq’ is pq + p’q’.

Q7) Simplify f(X,Y,Z)=∏M(0,1,2,4)f(X,Y,Z)=∏M(0,1,2,4)using K-map.

A7)

Therefore, the simplified Boolean function is

f = (X + Y).(Y + Z).(Z + X)

Q8) Simplify:

F(P,Q,R,S)=∑(0,2,5,7,8,10,13,15)

A8)

F = P’Q’R’S’ + PQ’R’S’ + P’Q’RS’ +PQ’RS’ + QS

F = P’Q’S’ + PQ’S’ + QS

F = Q’S’ +QS

Q9) Simplify:

F(A,B,C)=π(0,3,6,7)

A9)

F = A’BC +ABC +A’B’C’ +ABC’

F = BC + C’ ( A’B’ + AB )

Unit - 2

Boolean function minimization Techniques

Q1) What are the 3 basic boolean laws?

A1)

The three basic laws of Boolean Algebra are:

• Commutative law
• Associative law
• Distributive law

Commutative Law

• The logical operation carried between two Boolean variables when gives the same result irrespective of the order the two variables, then that operation is said to be Commutative. The logical OR & logical AND operations between x & y are shown below

x + y = y + x

x.y = y.x

• The symbol ‘+’ and ‘.’ indicates logical OR operation and logical AND operation.
• Commutative law holds good for logical OR & logical AND operations.

Associative Law

• If a logical OR operation of any two Boolean variables is performed first and then the same operation is performed with the remaining variable providing the same result, then that operation is said to be Associative. The logical OR & logical AND operations of x, y & z are:

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

x.(y.z) = (x.y).z

• Associative law holds good for logical OR & logical AND operations.

Distributive Law

• If a logical OR operation of any two Boolean variables is performed first and then AND operation is performed with the remaining variable, then that logical operation is said to be Distributive. The distribution of logical OR & logical AND operations between variables x, y & z are :

x.(y + z) = x.y + x.z

x + (y.z) = (x + y).(x + z)

• Distributive law holds good for logical OR and logical AND operations.

These are the Basic laws of Boolean algebra and we can verify them by substituting the Boolean variables with ‘0’ or ‘1’.

Q2) Consider  the following truth table.

A2)

• Here, the output (f) is ‘1’ for only four combinations of inputs.
• The corresponding min terms are given as p’qr, pq’r, pqr’, pqr.
• By doing logical OR, we get the Boolean function of output (f).
• Hence, the Boolean function of output is,

f = p’qr + pq’r + pqr’ + pqr.

• This is the desired canonical SoP form of output, f.
• It can also be represented as:

f=m3+m5+m6+m7f=m3+m5+m6+m7

f=∑m(3,5,6,7)f=∑m(3,5,6,7)

• First, we represented the function as sum of respective min terms and then, the symbol for summation of those min terms is used.

Q3) Convert the Boolean function into Standard SoP form.

f = p’qr + pq’r + pqr’ + pqr

A3)

Step 1 – By using the Boolean postulate, x + x = x and also writing the last term pqr two more times we get

⇒ f = p’qr + pq’r + pqr’ + pqr + pqr + pqr

Step 2 – By Using Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms.

⇒ f = qr(p’ + p) + pr(q’ + q) + pq(r’ + r)

Step 3 – Then Using Boolean postulate, x + x’ = 1 we get

⇒ f = qr(1) + pr(1) + pq(1)

Step 4 – hence using Boolean postulate, x.1 = x we get

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

This is the required Boolean function.

Q4) Convert the Boolean function into Standard PoS form.

f = (p + q + r).(p + q + r’).(p + q’ + r).(p’ + q + r)

A4)

Step 1 – By using the Boolean postulate, x.x = x and  writing the first term p+q+r two more times we get

⇒ f = (p + q + r).(p + q + r).(p + q + r).(p + q + r’).(p +q’ + r).(p’ + q + r)

Step 2 – Now by using Distributive law, x + (y.z) = (x + y).(x + z) for 1st and 4thparenthesis, 2nd and 5th parenthesis, 3rd and 6th parenthesis.

⇒ f = (p + q + rr’).(p + r + qq’).(q + r + pp’)

Step 3 − Applying Boolean postulate, x.x’=0 for simplifying of the terms present in each parenthesis.

⇒ f = (p + q + 0).(p + r + 0).(q + r + 0)

Step 4 − Using Boolean postulate, x + 0 = x we get

⇒ f = (p + q).(p + r).(q + r)

⇒ f = (p + q).(q + r).(p + r)

This is the simplified Boolean function.

Hence, both Standard SoP and Standard PoS forms are Dual to one another.

Q5) Simplify the Boolean function,

f = p’qr + pq’r + pqr’ + pqr

A5)

Method 1

Given

f = p’qr + pq’r + pqr’ +pqr.

In first and second term r is common and in third and fourth terms pq is common.

So, taking out the common terms by using Distributive law we get,

⇒ f = (p’q + pq’)r + pq(r’ + r)

The terms present in first parenthesis can be simplified by using Ex-OR operation.

The terms present in second parenthesis is equal to ‘1’ using Boolean postulate we get

⇒ f = (p ⊕q)r + pq(1)

The first term can’t be simplified further.

But, the second term is equal to pq using Boolean postulate.

⇒ f = (p ⊕q)r + pq

Therefore, the simplified Boolean function is f = (p⊕q)r + pq

Method 2

Given f = p’qr + pq’r + pqr’ + pqr.

Using the Boolean postulate, x + x = x.

Hence we can write the last term pqr two more times.

⇒ f = p’qr + pq’r + pqr’ + pqr + pqr + pqr

Now using the Distributive law for 1st and 4th terms, 2nd and 5th terms, 3rdand 6th terms we get.

⇒ f = qr(p’ + p) + pr(q’ + q) + pq(r’ + r)

Using Boolean postulate, x + x’ = 1 and x.1 = x for further simplification .

⇒ f = qr(1) + pr(1) + pq(1)

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Therefore, the simplified Boolean function is f = pq + qr + pr.

Hence we got two different Boolean functions after simplification of the given Boolean function. Functionally, these two functions are same. As per requirement, we can choose one of them.

Q6) Find the complement of the Boolean function,

f = p’q + pq’.

A6)

Using DeMorgan’s theorem, (x + y)’ = x’.y’ we get

⇒ f’ = (p’q)’.(pq’)’

Then by second law, (x.y)’ = x’ + y’ we get

⇒ f’ = {(p’)’ + q’}.{p’ + (q’)’}

Then by using, (x’)’=x  we get

⇒ f’ = {p + q’}.{p’ + q}

⇒ f’ = pp’ + pq + p’q’ + qq’

Using x.x’=0 we get

⇒ f = 0 + pq + p’q’ + 0

⇒ f = pq + p’q’

Therefore, the complement of Boolean function, p’q + pq’ is pq + p’q’.

Q7) Simplify f(X,Y,Z)=∏M(0,1,2,4)f(X,Y,Z)=∏M(0,1,2,4)using K-map.

A7)

Therefore, the simplified Boolean function is

f = (X + Y).(Y + Z).(Z + X)

Q8) Simplify:

F(P,Q,R,S)=∑(0,2,5,7,8,10,13,15)

A8)

F = P’Q’R’S’ + PQ’R’S’ + P’Q’RS’ +PQ’RS’ + QS

F = P’Q’S’ + PQ’S’ + QS

F = Q’S’ +QS

Q9) Simplify:

F(A,B,C)=π(0,3,6,7)

A9)

F = A’BC +ABC +A’B’C’ +ABC’

F = BC + C’ ( A’B’ + AB )