Question

[8] Using properties of Boolean algebra, simplify the following Boolean expressions so they could be built with the minimum number of gates. a. X= A + BC + AB + ABC + B b. Y = AB + B(AC + BC + ABC' + A) C. W = ABC' + AB'C' + B'CD + A'C + BC d. Z = (A + B')' + (ABC')' +A(B + A'C)'

Answer 1

We have to simplify the given Boolean expressions using Boolean algebra properties such that they can be built using minimum number of gates. We can simplify a Boolean expression either using Boolean algebra property or using K-map. We have to use Boolean algebra property in this question. For all the gates, we will consider them as 2 input 1 output gate, except NOT gate which is 1 input 1 output gate. So, lets simplify the expressions now.

a) : X = A + BC + AB + ABC + B :- Lets simplify this step by step.

X = A + BC + AB + B(AC + 1)    ( Taking B common from ABC and B)

X = A + BC + AB + B.1               ( By Annulment law, for any variable X + 1 = 1 so AC + 1 = 1)

X = A + BC + B(A + 1)                ( Taking B common from AB and B)

X = A + BC + B.1                        ( By Annulment law, for any variable X + 1 = 1 so A + 1 = 1)

X = A + B(C + 1)                         ( Taking B common from BC and B)

X = A + B                                    ( By Annulment law, for any variable X + 1 = 1 so C+ 1 = 1)

X = A + B is the simplified Boolean form of the given expression. As we can see that it is a simple OR operation between A and B, so this expression can be built using only one OR gate. So, the simplified expression needs only one OR gate to build a circuit for the expression. The circuit diagram is shown in the image below. Only 1 gate required.

A Х OR B x=A+B

b) : Y = AB + B(AC + BC + ABC' + A) :- Simplification of this expression is shown below.

Y = AB + B(AC + BC + A(BC' + 1)) ( Taking A common from ABC' and A)

Y = AB + B(AC + BC + A.1)                  ( By Annulment law, for any variable X + 1 = 1 so BC' + 1 = 1)

Y = AB + B(A(C + 1) + BC)                   ( Taking A common from AC and A)

Y = AB + B(A.1 + BC)                           ( By Annulment law, for any variable X + 1 = 1 so C+ 1 = 1)

Expanding the bracket :

Y = AB + BA + BBC                               

Y = AB + AB + BC                                ( By Commutative law, AB = BA. By idempotent law, A.A = A, so in BBC

                                                               we can replace BB with B as B.B = B)

Y = AB + BC                                         ( By Idempotent law, A+A = A, so AB + AB = AB)

Y = B(A + C)                                         ( Taking B common from AB and BC)

The simplified form of the given Boolean expression is Y = B(A + C) which will take minimum number of gates to build a circuit equivalent to the expression. Y = AB + BC will take 3 gates: 2 AND gates(for AB and BC) and 1 OR gate (for AB + BC). But Y = B(A + C) will take only 2 gates: 1 OR gate(for A+C) and 1 AND gate(for B(A+C)).

So, the simplifies Boolean expression which can be built using minimum number of gates is 2. The circuit diagram for the simplifies expression is shown in the image below. 2 gates will be required.

수 AtC OR y = e (A+c)

c) : W = ABC' + AB'C' + B'CD + A'C + BC :- Step by step simplification is shown in the image below.

W = AC'(B + B') + B'CD + A'C + BC        ( Taking AC' common from ABC' and AB'C')

W = AC'.1 + B'CD + A'C + BC                  ( By complement law, A + A' = 1, so B + B' = 1)

W = AC' + A'C + B'CD + BC                     ( Rearranging the terms)

W = AC' + A'C + C(B'D + B)                     ( Taking C common from B'CD and BC)

W = AC' + A'C + C((B'+B)(B+D))              ( By Distributive law, X + YZ = (X+Y)(X+Z))

W = AC' + A'C + C(1.(B+D))                     ( By Complementt law, A + A' =1, so B + B' = 1)

W = AC' + A'C + C(B+D)                           ( By Identity law, A.1 = A, so (B+D).1 = (B+D))

W = AC' + A'C + C(B+D) is the simplified Boolean expression of the given expression which will require minimum number of gates to build an equivalent circuit. On furthe expansion of C(B+D) using Distributive law, number of gates required will increase. So, this is the required simplified Boolean expression. It requires 1 XOR gate as AC' + A'C represents the output of XOR gate for inputs A and B, 1 OR gate for B+D, 1 AND gate for C(B+D) and 1 OR gate for (A'C + AC') + (C(B+D)). The circuit diagram for the expression is shown in the image below. 4 gates are required.

ÁC +AC IXOR OR C(BID) LOR BID W=Ad'+A'c + c(@+D)

d) : Z = (A+B')' + (ABC')' + A(B + A'C)' :- Simplification of this expression is shown in the following steps.

Z = ( A'.(B')') + (ABC')' + A(B+A'C)'    ( Applying De Morgans law, (X+Y)' = X'.Y', so (A+B')' = (A'.(B')') )

Z = A'.B + (ABC')' + A(B+A'C)'               ( By Double Negation law, (X')' = X, so (B')' = B)

Z = A'B + (A' + B' + (C')') + A(B+A'C)'   (Applying De Morgans law, (XYZ)' = X' + Y' + Z')

Z = A'B + (A'+B'+C) + A(B+A'C)'            ( By Double Negation law, (X')' = X, so (C')' = C)

Z = A'B + A' + B' + C + A(B'.(A'C)')         ( Applying De Morgans law, (X+Y)' = X'+Y')

Z = A'B + A' + B' + C + A(B'((A')' + C'))   ( Applying De Morgans law on (A'C)')

Z = A'B + A' + B' + C + A(B'(A + C'))    ( By Double Negation law, (X')' = X, so (A')' = A)

Z = A'B + A' + B' + C + A(B'A + B'C'))    ( By Distributive law, X(Y+Z) = XY + XZ)

Z = A'B + A' + B' + C + AB'A + AB'C'     ( By Distributive law, X(Y+Z) = XY + XZ)

Z = A'B + A' + B' + C + AAB' + AB'C'     ( By Commutative law, B'A = AB')

Z = A'B + A' + B' + C + AB' + AB'C'       ( By idempotent law, A.A = A, so we can replace AAB' with AB')

Z = A'(B + 1) + B' + C + AB' + AB'C'      ( Taking A' common from A'B and A')

Z = A' + B' + C + AB' + AB'C'                 ( By Annulment law, A + 1 = 1, so B+1 = 1)

Z = A' + C + B'(1 + A) + AB'C'               ( Taking B' common from B' and AB')

Z = A' + C + B' + AB'C'                          ( By Annulment law, A + 1 = 1, so A+1 = 1)

Z = A' + C + B'(1 + AC')                         ( Taking B' common from B' and AB'C')

Z = A' + C + B'                                       ( By Annulment law, A + 1 = 1, so AC'+1 = 1)

The expression Z = A' + B' + C is the simplified minimal expression which takes minimum number of gates to build an equivalent circuit. A' + B' is the output of a NAND gate for inputs A and B, so we need 1 NAND gate and 1 OR gate for (A'+B')+C. The circuit for the minimal expression is shown in the image below. 2 gates required for the circuit.

Á+ B' N OR z=A+Btc