Simplification of Combinational Logic Circuits Using Boolean Algebra ||
Digital Circuit Simplification
There are several Boolean expressions, functions that produce the same results for all possible values in the truth table. In this article, we consider the equipment minimisation criteria. Consider the two functions given below.Example 1: A(A + B)
= A.A + A.B Distributive Law
= A + A.B Rule 7
= A (1 + B) Distributive Law
= A (1) Rule 2
= A Rule 4
Example 2: A(A'+AB)
= AA' + AAB Distributive Law
= 0 + A.B Rule 8, Rule 7
= A.B
Example 3: BC + B'C
= C.(B+B') Distributive Law
= C.(1) Rule 7
= C Rule 4
Example 4: A(A+A'B)
= A.A + A.A'B Distributive Law
= A + 0.B Rule 7 , Rule 8
= A
Example 5: AB'C + A'BC + A'B'C
= AB'C + A'C(B+B') Distributive Law
= AB'C + A'C(1). Rule 6
= C (AB' + A')
= C (A' + B'). Rule 11
= A'C + B'C
Example 6: BD + B(D+E) + D'(D+F)
= B (D+D+E) + DD' + D'F Distributive Law
= B (D + E) + 0 + D'F Rule 5 Rule 8
= BD + BE + D'F
Example 7: A'B'C + (A+B+C')' + A'B'C'D
= A'B'C + A'B'C'' + A'B'C'D
De Morgan's Theorem
= A'B'C + A'B'C + A'B'C'D Rule 9
= A'B'C + A'B'C'D Rule 5
=A'B' (C + C'D)
= A'B' (C + D) Rule 11
Example 8: (B + BC)(B + B'C)(B + D)
= (B)(B + C)(B + D) Rule 10 Rule 11
= (B.B + B.C)(B + D)
= (B + B.C)(B + D) Rule 7
= B (B + D) Rule 10
= B.B + B.D
= B + B.D Rule 7
= B Rule 10
Example 9: A'B'C'D + AB(CD)' + (AB)'CD
= A'B'C'D + AB(C' + D') + (A' + B')CD De Morgan's Theorem
= A'B'C'D + ABC' + ABD' + A'CD + B'CD
= A'D(B'C' + C) + ABC' + ABD' + B'CD
= A'D(B' + C) + ABC' + ABD' + B'CD
Rule 11
= A'B'D + A'DC + ABC' + ABD' + B'CD
Example 10: ABC[AB + C'(BC + AC)]
= ABC [AB + BCC' + ACC']
= ABC [AB + 0 + 0 ] Rule 8
= ABC [AB]
= ABC Rule 7
Example 11: (A + B')(A + C)
= A.A + A.C + A.B' + B'C
= A + A.C + A.B' +B'C Rule 7
= A (1 + C) + A.B' +B'C
= A.1 + A.B' +B'C Rule 2
= A ( 1 + B') + B'C
= A.1 + B'C Rule 2
= A + B'C
Example 12: A'B + A'BC' + A'BCD + A'BC'D'E
= A' (B + BC') + A'BCD + A'BC'D'E
= A'.B + A'BCD + A'BC'D'E Rule 10
=>> Let, A'B = X, CD = Y
= X + XY + XY'E
= X + X(Y+ Y'E)
= X + X(Y+ E) Rule 11
= X + XY + XE
= X (1+Y) + XE
= X (1) + XE Rule 2
= X + XE
= X (1 + E)
= X (1) Rule 2
= X
= A'B X = A'B
If you look at the example, this problem can be solved in two steps with the help of Rule 10.
Let's solve it in another way.
= A'B + A'BCD + A'BC'D'E Rule 10 on first two terms
= A'B + A'BC'D'E Again Rule 10 on first two terms
= A'B Again Rule 10 on the remaining two terms.
Example 13: AB + A'B'C + A
= AB + A + A'B'C
= A + A'B'C Rule 10
= A + B'C Rule 11
Example 14: (A + A')(AB + ABC')
= (1) . A(B + BC') Rule 6
= A . (B) Rule 10
= A.B
Example 15: AB + (A' + B')C + AB
= AB + AB + A'C + B'C
= AB + A'C + B'C. Rule 5
Example 16: (A.B + C.D) [(A' + B')(C' + D')]
Observing both terms, we find out that both expressions complement each other. Here is an article on how to find the complement of a Boolean expression.
= [(A + B) (C + D)] [(A' + B') (C' + D')]
=> Let X = (A + B) (C + D)
= X . X'
= 0 Rule 8
Example 17: A.B.C.D + A.B.C'.D' + A.B.C'.D + A.B.C.D.E + A.B.C'.D'.E' + A.B.C'.D.E
= A.B ( C.D + C'.D') + A.B.C'.D + A.B.C.D.E + A.B.C'.D'.E' + A.B.C'.D.E
= A.B (1) + A.B.C'.D + A.B.C.D.E + A.B.C'.D'.E' + A.B.C'.D.E Rule 6
= A.B + A.B.C.D.E + A.B.C'.D'.E' + A.B.C'.D + A.B.C'.D.E
= A.B + A.B (C.D.E + C'.D'.E') + A.B.C'.D (E + 1). Distributive Law
= A.B + A.B (1) + A.B.C'.D (1) Rule 6 Rule 2
= A.B + A.B + A.B.C'.D
= A.B + A.B.C'.D Rule 5
= A.B Rule 10
Example 18: X'Y' + XY + X'Y
= X' (Y' + Y) + XY
= X' (1) + XY Rule 6
= X' + Y Rule 11
Example 19: (X + Y)(X + Y')
= X.X + X.Y' + X.Y + Y.Y' Distributive Law
= X + X(Y' + Y) + 0 Rule 7 Rule 8
= X + X (1) Rule 6
= X Rule 5
Example 20: X'Y +XY' + XY + X'Y'
= X' (Y + Y') + X (Y + Y')
= X' (1) + X (1) Rule 6
= X' + X
= 1 Rule 6
Example 21: X' + XY + XZ' + XY'Z'
= X' + XY + XZ' (1 + Y')
= X' + Y + XZ' (1) Rule 11 Rule 2
= X' + XZ' + Y
= X' + Z' + Y Rule 11
Example 22: XY' + Y'Z' + X'Z'
This is the consensus theorem. The answer is XY' + X'Z'
= XY' + Y'Z' (1) + X'Z' Rule 4
= XY' + Y'Z' (X + X') + X'Z' Rule 6
= XY' + Y'ZX + Y'Z'X' + X'Z'
= XY'(1 + Z) + X'Z' (1 + Y'). Rule 2
= XY' + X'Z'
Example 23: ABC + A'B + ABC'
= AB ( C + C') + A'B
= AB (1) + A'B Rule 6
= AB + A'B
= B (A + A')
= B (1) Rule 6
= B
Example 24: X'YZ + XZ
= Z (X'Y + X)
= Z (X + Y) Rule 11
= X'Z' + YZ
Example 25: (X + Y)' (X' + Y')
= (X + Y)'(X' + Y')
=X' Y' (X' + Y')
De Morgan's Theorem
= X'X'Y' + X'Y'Y'
= X'Y' + X'Y' Rule 7
= X'Y' Rule 5
Example 26: XY + X(WZ + WZ')
= XY + XW(Z + Z')
= XY + XW(1) Rule 6
Example 27: (BC' + A'D)(AB' + CD')
= BC'AB' + BC'CD' + A'DAB' + A'DCD'
= 0 + 0 + 0 + 0 Rule 8
Example 28: A'C' + ABC + AC'
= A'C' + AC' + ABC
= C' (A' + A) + ABC
= C' (1) + ABC. Rule 6
= C' + AB Rule 11
Example 29: (X'Y' + Z)' + Z + XY +WZ
= (X'Y')'.Z' + Z + XY + WZ
De Morgan's Theorem
= (X'' + Y'')Z' + Z + XY + WZ
De Morgan's Theorem
= (X + Y)Z' + Z + XY + WZ
= XZ' + YZ' + Z + XY + WZ
= XZ' + YZ' + XY + Z(W + 1) Rule 2
= XZ' + YZ' + XY + Z(1)
= XZ' + XY + YZ' + Z Rearrange
= XZ' + XY + Z + Y Rule 11
= XZ' + Z + XY + Y Rearrange
= Z + X + Y Rule 11 Rule 10
Example 30: A'B(D' + C'D) + B (A + A'CD)
= A'B (D' + C') + B (A + CD) Rule 11 Rule 11
= A'BD' + A'BC' + AB + BCD
= B(A'D' + A) + A'BC' + BCD
= B(A + D') + A'BC' + BCD Rule 11
= AB + BD' + A'BC' + BCD
= B(A + A'C') + B(D' + DC)
= B(A + C') + B(D' + C) Rule 11 Rule 11
= AB + BC' +BD' + BC
= AB + BD' + B(C' + C)
= AB + BD' + B(1) Rule 6
= AB + B (D' + 1)
= AB + B (1) Rule 2
= B Rule 10
Example 31: (A' + C)(A' + C')(A + B + C'D)
= (A'A' + A'C' + A'C + CC')(A + B + C'D)
= (A' + A'C' + A'C + 0)(A + B + C'D)
Rule 7 Rule 8
=(A' + A'C)(A + B + C'D) Rule 10
= A'(A + B + C'D) Rule 10
= A'A + A'B + A'C'D
= 0 + A'B + A'C'D Rule 8
Example 32: [AB'(C + BD) + A'B']C
=(AB'C + AB'BD + A'B')C
= (AB'C + 0 + A'B')C Rule 8
= AB'CC + A'B'C
= AB'C + A'B'C Rule 7
= B'C (A +A')
= B'C(1) Rule 6
Example 33: [AB (C + (BD)') + (AB)'] CD
= [AB ( C + B' + D') + A' + B'] CD
De Morgan's Theorem De Morgan's Theorem
= [ABC + ABB' + ABD' + A' + B']CD
= [ABC + A' + ABD' + B' + 0] CD
Rule 8
= [A' + BC + B' + AD'] CD Rule 11 Rule 11
= [A' + AD' + B' + BC] CD Rearrange
= [A' + D' + B' + C] CD Rule 11Rule 11
= A'CD + CD'D + B'CD + CCD
= A'CD + 0 + B'CD + CD Rule 8 Rule 7
= A'CD + CD Rule 10
= CD Rule 10
Example 34: A'BC + AB'C' + A'B'C' + AB'C + ABC
= BC(A' + A) + B'C'(A + A') + AB'C
= BC(1) + B'C'(1) + AB'C Rule 6
= BC + B'(C' + AC)
= BC + B'(C' + A) Rule 11
= BC + AB' + B'C'
Example 35: ABC' + A'B'C + A'BC + A'B'C'
= ABC' + A'C(B + B') + A'B'C'
= ABC' + A'C(1) + A'B'C' Rule 6
= ABC' + A'(C + B'C')
= ABC' + A'(C + B') Rule 11
= ABC' + A'B' + A'C
Example 36: (AB + AC)' + A'B'C
= (A (B + C))' + A'B'C
= A' + (B + C)' + A'B'C
De Morgan's Theorem
= A' + B'C' + A'B'C
De Morgan's Theorem
= A' + B'(C' + A'C)
= A' + B' (C' + A') Rule 11
= A' + A' + B'C'
= A' + B'C' Rule 5
Example 37: (AB)' + (AC)' + A' B'C'
= (A' + B') + (A' + C') + A'B'C'
De Morgan's Theorem
= A' + A' + B' + C' + A'B'C'
= A' + B' + C' + A'B'C' Rule 5
= A' + B' + C' +(A'B')C'
= A' + B' + C' Rule 10
Example 38: A + AB + AB'C
= A + A(B + B'C)
= A + A(B + C) Rule 11
= A + AB + AC
= A + AC Rule 10
= A Rule 10
Example 39: (A' + B)C + ABC
= A'C + BC + ABC
= BC + C(A' + AB)
= BC + C(A' + B) Rule 11
= BC + A'C + BC
= BC + A'C Rule 5
Example 40: AB'C(BD + CDE) + AC'
= AB'CBD + AB'CCDE + AC'
= 0 + AB'CDE + AC' Rule 8 Rule 7
= AB'CDE + AC'