Manipulations & Simplifications of Boolean Function and Logic Circuits

We have learned to use the TRUTH TABLE to prove the equality of Boolean Expressions and their Corresponding Digital Logic Gates.

We have seen these in  De Morgan's Theorems  as shown again below:  

         Theorem 1     A.B = A +B                                           Theorem 2    A+B = A. B                                                       

But using the TRUTH TABLE to prove  COMPLEX Boolean expressions may not  be suitable as this will require a lot of tabulations which may bring a lot of room for errors.  For example.

Prove that these  Boolean Expressions or Functions are all equal.  

 a)   A'BC'D' + A'BC'D + A'BCD + A'BCD' + ABC'D' + ABC'D + ABCD + ABCD'  = B

b)    

=  

The Boolean Expression above have 4 Inputs and that means we have to Tabulate all 16 combinations for every term in the expressions.

In a) there are 8 terms needed to be evaluated, each having 16 input compbinations and in b) there are at least 5 terms.

For the above TRUTH TABLE, all in all you need to evaluate 9 X 16 or 144 Boolean computations,  to prove or disprove the equality.

But, with the use of BOOLEAN LAWS, we can easily manipulate COMPLEX Boolean Expressions so that we can get their equivalent or alternate Boolean Expressions.

EXAMPLE, If we have XY + XY'  , we can manipulate this expression using the 2 Boolean Laws Below. 

Distributive Law – This law permits the multiplying or factoring out of an expression.

• (i) A(B + C) = AB + AC      (ii) A + BC = (A + B)(A + C)

  Complement Law – A term AND´ed with its complement equals “0” and a term OR´ed with its complement equals “1”.

• •  A . A = 0,    A variable AND’ed with its complement is always equal to 0.

•  A + A = 1,    A variable OR’ed with its complement is always equal to 1.

HENCE

                    X(Y+Y')     Distributive Law 

                    X(1)            Complement Law

Therefore 

                   X(Y+Y') = X

Let us consider now the equation above.

A'BC'D' + A'BC'D + A'BCD + A'BCD' + ABC'D' + ABC'D + ABCD + ABCD'  = B

A'BC'D' + A'BC'D + A'BCD + A'BCD' + ABC'D' + ABC'D + ABCD + ABCD' 

    A'BC'(D' + D)    +   A'BC(D + D')      +   ABC'(D' + D)     +  ABC(D + D')       Distributive Law 

             A'BC'         +       A'BC                    +       ABC'              +         ABC                   Complement Law

                             A'B(C' + C)                 +                   AB(C' + C)                                      Distributive Law 

                                                          A'B + AB                                                                        Complement Law

                                                          (A' + A)B                                                                        Distributive Law 

                                                              B                                                                                 Complement Law

So the ABove Boolean Expressions (Functions) are the same, and that we can MANIPULATE any BOOLEAN FUNCTIONS or EXPRESSIONS in order to simplify or get its other equivalent Boolean Expressions. 

We can also say that we can simplify a Boolean Expression using Boolean Laws which is equivalent to simplifying its equivalent Logic Gates Network or Logic Circuit.

Let us consider now the following Boolean Function. F(x,y,z) = x'y'z + x'yz + xy'

And let also consider its equivalent Logic Circuit as shown below.

We can now ask ourselves, if this Logic circuit can be simplified ?  The answer can be given by Manipulation its equivalent Boolean Function and see if we can simplify it.   From the new 

 F(x,y,z) = x'y'z + x'yz + xy'

                     x'z(y' + y)  + xy'     Distributive Law 

                              x'z + xy'                    Complement Law

From the simplified and equivalent Boolean Expression, we get the also the new and simplified equivalent corresponding Logic Circuit.

Let us consider another example.  f = ABCD + A'BCD + (BC)'

f = ABCD + A'BCD + (BC)'

     BCD(A+A') + (BC)'             Distributive

     BCD +  (BC)'                  Complement

     ( BC + (BC)' ) ( D + (BC)' )  Distributive

     ( BC + B' + C') ( D + (BC)' ) De Morgans

     ( ( B + B' ) ( C + B') + C' ) ( D + (BC)' )  Distributive

     ( C +B' + C') ( D + (BC)' )   Complement & Associative

     ( B + 1 ) ( D + (BC)' )       Complement

     ( D + (BC)' )                 Identity

      D + (BC)'  =  D + B' + C'    De Morgans

From the Above Boolean Manipulations we can simplify the Function f = ABCD + A'BCD + (BC)' to   D + (BC)'

And this is done using the BOOLEAN LAWS available at hand.

We can also verify and get the same results using the TRUTH TABLE to prove the equivalence of the Boolean expressions above.

Likewise, we can say that the equivalent Logic Circuit corresponding to f = ABCD + A'BCD + (BC)'

can be simplified to an equivalent Logic Circuit corresponding to f = D + (BC)' since the later will require lesser components than the former one.

Let us implement the Logic Circuits for both Boolean Functions and verify by comparison.  

Comparing we can see that the function    f = D + (BC)'    has only 2 Loguc Gates while the other has 4 Logic Gates.  In Digital switching, lesser components mean more reliable because they are more stable, and more efficient because they are faster. And this is the goal of simplifying Logic CIrcuits, to achieve a more reliable, efficient and economical computing system.

•  Gate requirements can be estimated directly from expression for Boolean function.

EXAMPLES:

1) Simplify the logic circuit shown below, using Boolean simplification.

The first step is to determine the expression for the output z = ABC + AB'(A'C')' .  Once the expression is determined, it is usually a good idea to break down all large inverter signs using DeMorgan’s theorems and then multiply out all terms.

z =  ABC + AB'(A'C')' 

   =  ABC + AB'(A+C)          De Morgans

   =  ABC + AB'A+AB'C)    Distributive

   =  ABC + AB'+AB'C        Indempotent Law

   =  AC(B+B')+ AB'           Distributive

   =  A(B'+C)                         Distributive

Shown below is the simplified Logic Circuit

2) Prove  that the Logic circuits a and b are equal.

3) Simplify the expression z = AB'C' + AB'C + ABC

Method-1

 z = AB'C' + AB'C + ABC

    = AB'(C'+C )+ ABC

    = AB'+ ABC

    = A(B'+BC)   = A( (B'+B)(B'+C) )

    = A(B'+C)

Method-2

 z = AB'C' + AB'C + ABC

    = AB'C' + AB'C + ABC

    = AB'C' + AB'C + AB'C  + ABC

    = AB'(C'+C )+ AC(B'+B)

    = AB'+ AC

    = A(B'+C)

4) Let us prove the validity of the 2nd Distributive Law X+YZ  = (X+Y)(X+Z)

     X+YZ  = (X+Y)(X+Z)

                    X(X+Z) + Y(X+Z)

                    XX + XZ + XY + YZ

                     X + XZ + XY + YZ

                     X(1 + Z + Y) + YZ

                      X(1) + YZ

                          X + YZ

The ordinary distributive law states that the AND operation distributes over OR,  A(B + C) = AB + AC, 

while the second distributive law states that OR distributes over AND, A + BC = (A + B)(A + C). 

This second law is very useful in manipulating Boolean expressions.   In particular, an expression like  A+BC, 

which cannot be factored in ordinary algebra, is easily factored using the second distributive law:  A+BC = (A + B)(A + C). 

Any expressions can be substituted for X and Y in Boolean theorems.

There is a Boolean Law UNITING which we can apply.

• • Uniting

  • (i) XY + XY’ = X                (ii)  (X + Y)(X + Y’) = X     

Therefore Z = X where X = A+B'C.    

Using theBoolean Law of  Adsorption

• • (i) (X + Y’)Y = XY               (ii)  XY’ + Y = X + Y

Therefore Z =  XY’ + Y =  X + Y  = ( B′D + C′E′ ) + (AB + C)′

Note that in this example we let Y=(AB+C)′ rather than (AB+C) in order to match the form.

Adding redundant terms. Redundant terms can be introduced in several ways such as adding xx , multiplying by (x . x), adding yz to xy . xz, or adding xy to x.When possible, the added terms should be chosen so that they will combine with or eliminate other terms.  

Simplify  WX + XY + X'Z' + WY'Z'

WX + XY + X'Z' + WY'Z'  + WZ'  ; consensus theorem   WX+X'Z' +WZ' = WX+X'Z' 

WX + XY + X'Z' + WZ' (Y' +1)      ; distributive                                                                      

WX + XY + X'Z' + WZ'                    ; Annulment Law  A + 1 = 1                                                      

WX + XY + X'Z'                                  ; consensus theorem  WX+X'Z' +WZ' = WX+X'Z'  

Simplify     X.Y + X'Z + Y.Z     (Note: this is the Consensus Equation)

X.Y + X'Z + Y.Z (X+X')       ;Shannon Expansion

X.Y + X'Z + XYZ +X'YZ     ; Distributive

X.Y(1+Z) + X'Z (1+Y)         ; Commutative, Distributive

X.Y + X'Z                            ; Identity

Simplify  ABC + A'BC + AB'C + ABC'

                      BC(A+A') + AB'C + ABC'    distributive

                         BC + AB'C + ABC'                  complement  

                      C(B+AB') + ABC'                    distributive

                      C ((B+A)(B+B')) + ABC'      distributive

                      C (B+A) +ABC'                        complement

                      AC + BC + ABC'                       distributive

                      AC + B (C + AC')                     distributive

                      AC + B ((C+A)(C+C'))           distributive

                      AC + B (C+A)                           complement

                      AC + B (A+C)                           commutative

                      AC + AB + BC                           distributive

REMEMBER THE NOTES ON DUALITY - We can apply the DUALITY to simplify Boolean Expression.

Given any logic expression, its dual is formed  by replacing all + with ·, and vice versa and  replacing all 0s with 1s and vice versa

f(a,b) = a+b  dual of  f(a,b) = a·b

f(x) = x+0    dual of  f(x) = x·1

Let us consider again this example.  XY + X'Z + YZ  

WE had simplified this using the concensus, and we get  XY + X'Z + YZ  = XY + X'Z

Let us apply the duality in the following example. (X+Y) (X'+Z) (Y+Z)  =  (X+Y)(X'+Z)

MORE EXAMPLES:

(a) xy + xy' = x(y + y') = x

(b) x'yz + xz = (x'y + x)z = z(x + x')(x + y) = z(x + y)

(c) A'B(D' + C'D) + B(A + A'CD) = B(A'D' + A'C'D + A + A'CD)

        = B(A'D' + A + A'D(C + C') = B(A + A'(D' + D)) = B(A + A') = B

Complement of a Boolean Function

The complement of a function f can be obtained (1)algebraically by applying De Morgan’s Theorem. It follows from this theorem that the complement of a function can also be derived (2)by taking the dual of the function and complementing each literal.

Find the complement of the function f= C'(AB + A'B'D + A'BD')

Rewrite the Boolean expression using the OVER BAR  

Using DeMorgan’s Theorem as many times as required, the complement of the function can be obtained.

By taking the dual and complementing each literal, we obtained the following:

Find the complement of the F = ( A' + B ) ( A + B' ) using De Morgans and Dual/Complement Theorem.

De Morgans 

F' = ( (A' + B) (A + B') )'

        ( A' + B )' + ( A + B' )'

        ( AB' ) + ( A'B)

Dual/Complement

Fd = ( A'B) + ( AB')        F' = ( AB') + ( A'B)

Let us find the complement of an XOR Gate using DEMorgans and DUALITY and COMPLEMENTING, which should yield to XNOR.

XOR Gate                                                       XNOR Gate   

The Logic Function of an XOR Gate is F = A'B + AB'

Using DeMorgans

 F = A'B + AB'

F' = ( A'B + AB' )'

       ( A'B)' (AB')'

       ( A+B')(A'+B)

       AA' + AB + A'B' + BB'

       AB + A'B'

Using DUAL/Complement

 F = A'B + AB'

Fd =  (A'+B)(A+B')

F' =  (A+B')(A'+B)

       AA' + AB + A'B' + BB'

       AB + A'B'

Hence the Function of  XNOR Gate is F = AB + A'B' , which is the complement of  XOR Gate that is F = AB' + A'B. 

Get the Complement of the Functions then verify using Duality/Complement procedure.

(a) F = (xy' + x'y)

(b) F = [(x' + y + z')(x + y')(x + z)] 

(c) F = y'z' + wx' + w'z'

(d) F =  wx + yz

(a) F' = (xy' + x'y)' = (xy')'(x'y)' = (x' + y)(x + y') = xy + x'y'

      Fd = (x+y').(x'+y)  ,           F' =  (x' + y)(x + y') = xy + x'y'

(b) F' = [(x' + y + z')(x + y')(x + z)]' = (x' + y + z')' + (x + y')' + (x + z)' =

       F' = xy'z + x'y + x'z'

       Fd =  [(x' .y .z')+(x .y')+(x.z)]    F'= [(x .y' .z)+(x' .y)+(x'.z')]  = xy'z + x'y + x'z'

(c) F = y'z' + wx' + w'z'

    F =[(y + z)' + (w' + x)' + (w + z)']     (De Morgans)

    F' =[(y + z)' + (w' + x)' + (w + z)']'   (Complement )

    F' =(y + z) (w' + x) (w + z)                 (Dual/Complement) of Original Function F = y'z' + wx' + w'z'

(d) F =  wx + yz       

    F' = (w'+x').(y'+z')    Getting F' by Duality/Complement

    F' = (wx + yz)'            Complement the whole Original F

        = (wx)'.(yz)'            De Morgans

         = (w'+x').(y'+z')    De Morgans

Homework-09: (1 week)

Simplify the following Boolean Functions.

I

(a) xy + xy' = 

(b) (x + y)(x + y') = 

(c) xyz + x'y + xyz' = 

(d) (A + B)'(A' + B') = 

(e) xyz' + x'yz + xyz + x'yz' = 

(f) (x + y + z')(x' + y' + z) = 

II

(a) ABC + A'B + ABC' = 

(b) x'yz + xz = (x'y + x)z = 

(c) (x + y)'(x' + y') = 

(d) xy + x(wz + wz') = 

(e) (BC' + A'D)(AB' + CD') = 

(f) (x + y' + z')(x' + z') = 

III

(a) A'C' + ABC + AC' = 

(b) (x'y' + z)' + z + xy + wz = 

 (c) A'B(D' + C'D) + B(A + A'CD) = 

(d) (A' + C)(A' + C')(A + B + C'D) = 

 (e) ABCD + A'BD + ABC'D = 

IV -Using the Specified GATES Draw the Equivalent Logic Circuits for the following Boolean Expressions

A) F = AB + CD USING  AND – OR gates

                     SOLUTION for A) 

B) F = (A + B)(C + D)  USING OR – AND

C)  F = AB + CD   USING  NAND – NAND

D)  F = (A+B)(C+D)   USING NOR – NOR

E)  F = (A+B)(C+D)   USING AND – NOR

F)  F = (A+B) (C+D)  USING   NAND – AND

G)  F = AB + CD  USING  OR – NAND

H)  F = AB + CD  USING  NOR – OR