**Boolean Algebra and Logic Simplification Worked E****xercises:**

**LOGIC SIMPLIFICATION USING ALGEBRAIC METHODS**

**Example 1:**

**Prove that**

*AB*+

*AB′*=

*A*.

**Proof:**LHS = A(B +

*B*′)

*=*

*A*= RHS

**Example 2:**Prove that

**(**

*A*+

*B*′)

*B*=

*AB*.

**Proof:**LHS = (

*A*+

*B′*)

*B*=

*AB*+

*BB*′

*=*

*AB*= RHS

**Example**

**3:**

**Prove that (**

*A*+

*B*′)

*A*=

*A*,

**Proof:**LHS = (

*AA*+

*AB′*) =

*A*(1+

*B′*) =

*A*= RHS

**Example**

**4:**

**Prove that**

*A*+

*A′B*=

*A*+

*B*

**Proof:**LHS =

*A*(1+

*B*)

*+*

*A′B*=

*A*+

*AB*+

*A′B*=

*A*+

*B*(1+

*A*′) =

*A*+

*B*

In the above proof, we have used the relation=

*A*(1+*B*) =*A*.**Example**

**5:**

**Prove that**

*A*⊕

*B*⊕

*AB*=

*A*+

*B*.

**Proof:**

**We**

**first**

**expand**

**the term**

*B*⊕

*AB = B′AB + B(AB)′= B(AB)′*

where we have used

*B′B*= 0. Now we expand using De Morgan the relation

*B*(

*AB*)

*′ = B*(

*A′+B′*)

*=*

*BA*

*′*

Then we find that

*A*⊕*BA′ = A′BA′+ A(BA′)= A′B + A(B′ + A)*

Further reducing, we find that

*A′B + A + AB′ = A′B + A(1+ B′)*

which reduces to

*A**′**B + A(1+ B′) = A**′**B + A = A + B = RHS*

**Example 6:**

**Prove that**

*B + A*

*′*

*B′C = B + A*

*′*

*C*

**Proof:**

**We have**

**LHS =**

**B +**

*A*

*′ B′C = B + B′ (A′C) = B + A′C = RHS*

where we have used a relation similar to

*B + B′C = B + C*.**Example**

**7:**

**Prove that**

*A + A′ B + A′ B′C + A′ B′ C′D + … = A + B + C +…*

**Proof:**

**We know that**

*A + A′ B = A + B*

Extending the above relation, we find

*A + B + A′ B′C = A + (B + A′ B′C) = A + B + A′ C*

where we have used the relation

*(B + A′ B′C) = B + A′ C*But, we know that

*A + A′ C = A + C*. Thus we obtain the relation*A + B + A*

*′*

*B′C = A + (B + A*

*′*

*B′C) = A + B + C*

Carrying out this operation and mathematical induction, we obtain the final relation:

*A + A**′**B + A**′**B′C + A**′**B′C′D + … = A + B + C + D +…*

**Hint:**As stated earlier, logic

**simplification through algebraic methods is very tedious and requires the knowledge of many fundamental theorems and laws, especially when the RHS part is not given. To keep these theorems in memory is not that easy since there exist several of them.**

To simplify the procedure, we suggest that the student (especially one who is writing an examination) first find the correct solution using an appropriate K-map. Once we have the answer with us, we can proceed to solve the problem algebraically. As an example, we solve Example 6 (assuming the RHS part is not given) using this method. For this, let us assume that the given problem is stated as

*A + A*

*′*

*B + A*

*′*

*B′C + A*

*′*

*B′C′D + … = ?*

In the above problem, since the RHS is not given, we are not sure what the answer (RHS) would be. To find the answer (i.e., RHS), we first draw the three-variable map

*M*_{1}as shown in Fig. E6a and enter the implicants*A, A’B,*and*A’B′C**in it as shown.*Next we draw K-map

*M*_{2}as shown in Fig. E5b and remove the first encirclements. Then we regroup them as shown in*M*_{2}to find what*A + A′ B + A′ B′C*would be.From map

*M*, we get the answer as:*A + A*

*′*

*B + A*

*′*

*B′C = A + B + C*

Now we are sure what the RHS would be in this case. Knowing the answer in advance, we can prepare our strategy accordingly to solve the problem.

**Example**

**8:**

**Prove that**

**(i)**

*A*⊕

*A*⊕

*A*⊕

*… = 0*, if the number of

*A*’s is even

**(ii)**

*A*⊕

*A*⊕

*A*⊕

*… = A,*if the number of

*A*’s is odd

**Proof:**

**We know that**

**(i)**

*A*⊕

*A = A*

*′*

*A + A A*

*′*

*= 0*

This means that if the number of

*A’*s is even, then the sum will be 0. Now, if the number is odd (say, three), we get**(ii)**

*A*⊕

*A*⊕

*A*

*= 0 + A = 0. A*

*′*

*+ 1. A = A*

Extending the above two results, using mathematical induction, we get the desired results.

**Example**

**9:**

**Prove that**

*AB*⊕

*AB′ = A*

**Proof:**

**LHS**

*=*

*AB*⊕

*AB′ = AB(AB′)′ + (AB)′ AB′*

*= AB(A′+B) + (A′+B′) AB′*

*= AB + AB′ = A*=RHS

**Example 10:**

**Prove that**

*A′ + B′ + ABC′ = A′ + B′ + C′*

**Proof:**We know that

*A′ + ABC′ = A′ + BC′*

Using the above relation we find LHS =

*A′ + B′ + BC′ = A′ + B′ + C′ = RHS***Example**

**11:**

**Prove that**

*x′y′z +yz + xz = ?*

**Proof:**

**LHS =**

*z(y + y′x′) + xz = z(y + x′) + xz*

**=**

*zy + zx′ + xz = zy + z = z =*RHS

**Example**

**12:**

**Reduce the expression**

**Proof:**

**Applying De Morgan on the barred term in square brackets yields**

**Example**

**13:**

**Prove that**

**:**

*xy + x′y′ + yz = xy + x′y′ + x′z*

**Proof:**

**LHS =**

*xy + x′y′ + yz (1 + x′) = xy + x′y′ + yz +yzx′*

**=**

*xy + x′(y′ + yz) + yz = xy + x′y′ + x′z + yz*

**= (**

*xy + yz + x′z*) + x

*′y′ = xy + x′z +x′y′ =*RHS

where we have applied the consensus theorem on the bracketed terms.

**Example**

**14:**

**Prove that**

**:**

*A′C′ + ABD + AB′D′ + ABCD′ = ?*

**Proof:**

**Since the RHS is not given, we use a K-map and find the RHS**

**Example**

**15**

**:**Prove the De Morgan’s laws, viz.,

*(A + B)′ = A′B′*and

*(AB)′ = A′ + B′*.

**Proof:**These laws were enunciated by Augustus De Morgan (to be pronounced as

*da morgan*), a nineteenth century British mathematician. To prove these laws, we make use of truth tables: Table E14a is used to prove the first law. It can be observed that the entries in the rightmost two columns are the same; this proves the first law.

**Truth**

**Table E14a**Proof of

*(A + B)′ = A′B′*

A | A′ | B | B′ | A+B | ( A+B)′ | A′ B′ |

0 1 | 1 0 | 0 1 | 1 0 | 0 1 | 10 | 10 |

Table E14b proves the second law. The entries related to the second law are as shown in the table. As in the first case, in this case also the entries in the rightmost two columns are the same, which proves the second law.

**Example 16:**Prove the

**transposition theorem**, which states that

*AB + A′C = (A′ + B)(A + C)*

**Solution:**

**Consider the RHS. We find**

RHS =

*(A′ + B)(A + C) = A′A + A′C + BA + BC = A′C + BA + BC*where we have used the basic law

*A′A*= 0. Now, the remaining expression*A′C+BA+BC*can be seento be a statement of the consensus theorem, which reduces to

*A′C+BA.*That is,*AB + BC + A′C = AB +A′C*= LHS

**Example 17: Involution law:**This law states that

*A′*)

*′ = A*

**Proof:**Involution law becomes highly useful in solving problems applying De Morgan’s laws. The law can be proved using the truth table E16. We find that the first and last columns agree with each other, which proves the law.

**Truth Table E16**Involution Law

A | A’ | (A′)′= A |

0 1 | 1 0 | 01 |

**Example 18:**Define the EXOR

**function.**

**Solution:**

**The logic function**

*Z = AB′ + A′B*

**is called the**

**EXCLUSIVE-OR (EXOR**or

**XOR)**function. This relation can be derived from Table E17a, the truth table for the OR function.

**Truth Table E17a**The

**OR function**

A | B | Z = A+B |

0 0 1 1 | 0 1 0 1 | 0111 |

In Table E17a, if we change the last row as shown in Table E17b, we get the XOR function.

**Truth Table E17b**The XOR functionA | B | Z = A ⊕ B |

0 0 1 1 | 0 1 0 1 | 0110 |

From Table E17b, we get the XOR relation

**,***A*⊕*B = AB′ + A′B*where the symbol ‘⊕’ represents the XOR operation. It is to be noted that it is the XOR operation (and not the OR operation) that really represents the algebraic addition of two bits.

**Example 19:**Define the

**EXNOR**

**function.**

**Solution:**The logic statement (

*A*′

*B+AB*′)′

*is called the*

**EXCLUSIVE**-

**NOR**(

**EXNOR**or

**XNOR**) function. This relation is derived from the truth table for the OR function as shown below. EXNOR represents the complementary operation of the algebraic addition of two bits. The EXNOR operation in the last column may be read as “NOT of either

*A*OR

*B*”.

**Truth Table E18**The XNOR function

A | B | A ⊕ B | (AB′ + A′B)′ |

0 0 1 1 | 0 1 0 1 | 0 1 1 0 | 1001 |

From Table E18, we get the EXNOR relation as

*(A*⊕*B)′ = A′B′ + AB*

**Example**

**20**

**:**

**Use De Morgan’s laws to expand the XNOR relation.**

**Solution:**

**The**

**XOR operation given by**

*Z = (AB′ + A′B)′*

Since XNOR operation is the complement of , by applying De Morgan on the RHS, we get

*Z = (AB′)′.(A′B)′*

Applying De Morgan on the two RHS terms individually yields

*Z = [A′ + (B′)′][(A′)′+ B′]*

*= (A′ + B)(A + B′) = AA′ + BB′ + AB + A′B′*

**=**

*AB + A′B′*

Thus we get

*(AB′ + A′B)′ = AB + A′B′*

**Example**

**21:**Explain the principle of

*duality*.

**Solution:**Consider the function

*f*(

*x*) =

*x*

_{1 }+

*x*

_{2}∙

*x*

_{3}

*+*

*x*

_{4}∙

*x*

_{5}∙

*x*

_{6}(1)

Replacing the pluses with dots and dots with pluses in the RHS of Eq. (1), we get a new function

_{ }

*F*(

*x*) =

*x*

_{1 }∙

*(*

*x*

_{2}+

*x*

_{3})

*∙ (*

*x*

_{4 }+

*x*

_{5}+

*x*

_{6}) (2)

The function

*F*(*x*) defined in Eq. (2) is called the*dual*of the function*f*(*x*). We find that*f*(*x*) and*F*(*x*) are equally valid functions and duality is a special property of Boolean (binary) algebra. The property of duality exists in every stage of Boolean algebra. For example, positive and negative logic schemes are dual schemes. Similarly, AND is the dual of OR, NAND is the dual of NOR, and so on. To illustrate further, consider the De Morgan’s law (A + B)

*′ = A′.B′*(1)Now, in Eq. (1), replace the plus with a dot and the dot with a plus; this action yields the expression

(A.B)

*′ = A′ + B′*(2)We find that Eq. (2) is the complementary De Morgan’s law. This suggests that the De Morgan’s laws form a

*dual**pair*. We now state that every rule and law applicable to a positive-logic scheme is applicable to its corresponding

_{ }negative- (or, complementary-) logic scheme also. We now formally define the dual of a given function as follows:_{ }

*A function F(x) is said to be the dual of another function f(x), provided that F(x) is obtained from f(x) by replacing the multiplication signs (∙) and summation signs (+) in f*(

*x*)

*with summation signs and multiplication signs, respectively, and with no change in the variables of f(x).*

The definition given above may also be considered as the

*duality**theorem*. In this context, we may define*duality as the state of being dual*.**Example**

**22:**

**Find**

**(**

*ABC*′)+(

*ABC*′)′

**Solution:**Let us assume that

*ABC*′ =

*P*. Then we find that (

*ABC*′)′ =

*P*′. Now the given function can be written as:

(

*ABC*′) + (*ABC*′)′ =*P*+*P*′ =**1****Example**

**23:**

**Find**

**(**

*ABC*′)+(

*ABC*′)′ using a different method.

**Solution:**Applying De Morgan on the bracketed term yields

(

*ABC*′) + (*ABC*′)′ =*ABC*′+*A*′+*B*′+*C*But we know that

*ABC*′+*A*′ =*BC*′+*A*′and

*A*′+*BC*′+*B*′ =*C*′+*B*′+*A*′Finally,

*C*′+*B*′+*C*+*A*′= (*C*′+*C*)*+**B*′ +*A*′ =**1****Example**

**24:**

**Find**

*w*(

*x*+

*y*′z) +

*x*+

*y′z*.

**Solution:**

**Expanding the given expression yields**

*wx*+

*wy*′z +

*x*+

*y′z*=

*wx*+

*x*+

*wy*′z +

*y′z*

=

*x*+*y′z***Example**

**25:**

**Find**

**(**

*w*+

*x′*+

*y*z)(

*w′*+

*x′*+

*yz*).

**Solution:**

**Expanding the given expression yields**

**(**

*w*+

*x′*+

*y*z)(

*w′*+

*x′*+

*yz*) =

*wx′*+

*wyz*+

*x′ w′*+

*x′*+

*x′yz*+

*yzw′*+

*yzx′*+

*yz*

=

*wx′*+*wyz*+*x′ w′*+*x′*+*x′yz*+*yzw′*+*yzx′*+*yz**= x′*(

*w*+

*w′*)+

*yz*(

*w*+

*w′*)+

*x′*(1 +

*yz*)

*+*

*yz*(

*x′*+ 1)

*= x′*+

*yz*+

*x′*+

*yz*=

**x′****+**

*yz***Example**

**26:**

**Find**

**(**

*a*+

*b′*)(

*a*+

*c*+

*d*)(

*a*+

*c*+

*d′*).

**Solution:**

**Performing the first multiplication in the given expression yields**

**(**

*a*+

*b′*) (

*a*+

*c*+

*d*) = (

*a*+

*ac*+

*ad*) +

*b′c*+

*b′d*

=

*a*+*b′c*+*b′d*Now, we perform the second multiplication, which gives

*(*

*a*+

*b′c*+

*b′d*) (

*a*+

*c*+

*d′*) = (

*aa*+

*ac*+

*ad′*+

*ab′c*+

*ab′d*)

*+*

*(*

*b′c*+

*b′cd′*+

*b′cd*)

*=*

**a****+**

*b′c*

**Example**

**27:**

**Find**

*ab′*(

*c*+

*d*) + (

*c*+

*d*)

*′*.

**Solution:**

**Performing the first multiplication and applying De Morgan to the complemented (third) term in the given expression yields**

**(**

*ab′*)(

*c*+

*d*) + (

*c*+

*d*)

*′*=

*ab′c*+

*ab′d*+

*c′d′*

Now, we are in confusion regarding the route through which we have to move to reach the destiny. As the first step, we try expanding the term

*c′d′*. This is because the term*c′d*′ contains four 4-variable terms, given within brackets below, and contains components related to*ab′c*and*ab′d*. Thus we find RHS =

*ab′c*+*ab′d*+ (*a′b′c′d′*+*a′bc′d′*+*abc′d′*+*ab′c′d′*)Now, we find that terms

*ab′d*+

*ab′c′d′ =*

*ab′*(

*d*+

*c′d′*) =

*ab′d*+

*ab′c′*

Using the above two factors, the RHS may be expressed as

RHS =

*ab′c*+*ab′d*+*ab′c′*+*a′b′c′d′*+*a′b c′d′*+*ab c′d′*Combining factors

*ab′c*and*ab′c*yields RHS =

*ab′*+*ab′d*+*a′b′c′d′*+*a′bc′d′*+*abc′d′*Combining factors

*ab′*and*ab′d*, we get RHS =

*ab′*+*a′b′c′d′*+*a′bc′d′*+*abc′d′*Combining factors

*a′b′c′d′*and*a′bc′d′* RHS =

*ab′*+*a′c′d′*+*abc′d′*Finally, combining factors

*a′c′d′*and*a′bc′d′*, we obtain the reduced expression as RHS =

*ab′*+*c′d′* It can be seen that the reduction process is quite laborious and lengthy. Further, the reduction has been performed based on hunches and previous experience. Experiences and difficulties of this kind led to the development of the K-map and QM methods of Boolean reduction.

**Example**

**28:**

**Find**

*a*+

*b*+

*c′d*(

*a*+

*b*)

*′*.

**Solution:**

**Performing the first multiplication and applying De Morgan to the complemented (third) term in the given expression yields**

*a*+

*b*+

*c′d*(

*a*+

*b*)

*′*=

*a*+

*b*+

*c′d*(

*a′b′*) =

*a*+

*b*+

*a′b′c′d*

= (

*a*+*a′b′c′d*) +*b*=*a*+*b′c′d*+*b***Example**

**29:**

**Find**

**[(**

*ab*)′

*+*

*a′*+

*ab*]

*′*.

**Solution:**

**Applying De Morgan to the terms within the square brackets yields**

**[(**

*ab*)′

*+*

*a′*+

*ab*]

*′*=

**[(**

*ab*)′]′ ∙

*a*∙

**(**

*ab*)′

Applying De Morgan to RHS terms, we get

**[(**

*ab*)′]′ ∙

*a*∙

**(**

*ab*)′ =

*ab*∙

*a*∙ (

*a*′ +

*b*′) =

*ab*(

*a*′ +

*b*′) =

**0**

[

**Note****:**This may also be reduced at the second stage itself (without second the demorganization. For this observe that**[(**

*ab*)′]′ ∙

*a*∙

**(**

*ab*)′ = (

*ab*) ∙

**(**

*ab*)′ =

**0**

**Example**

**30:**

**Prove that**

**(**

*a*+

*b*′)

**(**

*b*+

*c*′)

**(**

*c*+

*d*′)

**(**

*d*+

*a*′) =

**(**

*a′*+

*b*)

**(**

*b′*+

*c*)

**(**

*c′*+

*d*)

**(**

*d′*+

*a*)

**Solution:**

**Multiplying the individual terms in LHS yields**

**LHS =**

**(**

*ab*+

*ac′*+

*b′c′*)

**(**

*cd*+

*ca*′ +

*d′a′*) =

*abcd*+

*b′c′d′a′*(1)

Similarly, multiplying the RHS terms yields

RHS =

**(***a′b′*+*a′c*+*bc*)**(***c′d′*+*c′a*+*da*) =*a′b′c′d′*+*bcda*(2)We find that

**Equation (1) = Equation (2)**

which is the desired result.

thanks

ReplyDelete