Boolean Algebra and Logic Simplification Examples

Boolean Algebra and Logic Simplification Worked Exercises:

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₁ 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₂ as shown in Fig. E5b and remove the first encirclements. Then we regroup them as shown in M₂ 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 

(Bars denote negation).                                     

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	1 0	1 0

      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.

                            Truth Table E14b Proof of (AB)′ = A′ + B′

A	A′	B	B′	AB	(AB)′	A′+ B′
0 1	1 0	0 1	1 0	0 1	1 0	1 0

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 seen

to 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	0 1

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	0 1 1 1

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

Truth Table E17b The XOR function

A	B	Z = A ⊕ B
0 0 1 1	0 1 0 1	0 1 1 0

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	1 0 0 1

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₁ + x₂∙x₃ + x₄∙x₅∙x₆                                            (1)

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

                                                               F(x) = x₁ ∙ (x₂ + x₃) ∙ (x₄ + x₅ + x₆)                                 (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′ + yz)(w′ + x′  + yz).

Solution: Expanding the given expression yields

              (w + x′ + yz)(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

                                                    = a + b + c′d

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.