Simplification of Boolean Functions

Simplification of Boolean Functions Reduces Circuit Gates

Boolean algebra consists of the rules and mathematical operations for binary systems such as computers and other electrical circuits where both inputs and outputs consist of the set {0,1}. Boolean functions are built from Boolean expression tables by minterm expansion (where a minterm has a value of 1 only when the values of all variables equals 1) using AND, OR and NOT operators. These expanded forms often do not represent the simplest form of the Boolean expression and require more gates than practical from an engineering perspective. Use Boolean identity properties when simplifying Boolean functions.

Things You'll Need

• Knowledge of basic Boolean algebra operators

Instructions

Simplification of Boolean Functions Using Boolean Identities

1. Use Identity Laws when simplifying Boolean functions.

   x + 0 = x
   x * 1 = x

2. Employ Complementarity Laws to simplify Boolean functions.

   x + x' = 1
   x * x' = 0

3. Consider Dominance Laws when simplifying Boolean functions.

   x + 1 = 1
   x * 0 = 0

4. 

   Make use of the Involution Law to simplify Boolean functions.

   (x')' = x

5. Exercise Idempotent Laws to aid simplification of Boolean functions.

   x + x = x
   x * x = x

6. Apply Commutative Laws in Boolean function simplification.

   x + y = y + x
   xy = yx

7. Draw on Associative Laws to further simplify Boolean functions.

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

8. Exploit DeMorgans Laws in Boolean function simplification.

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

9. Utilize Redundancy Laws for simplifying Boolean functions.

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

10. Remember Consensus Laws while simplifying Boolean functions.

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

Examples of Using Identities for Simplification of Boolean Functions

1. Using Distributive, Complementarity and Identity Laws, the Boolean function:

   f (x,y)= xy + xy'

   simplifies to f (x,y)= x. [ f (x,y)= xy + xy'= x * (y + y') = x * 1 = x ] The original function contains two AND operators, one OR operator and one NOT. The simplified Boolean function requires no circuit gates.

2. The more complex Boolean function:
   f (x,y,z) = x'y'z' + x'y'z + x'yz' + x'yz + xyz' + xyz

   is simplified to f (x,y,z) = x' + y using Distributive, Complementarity, Identity, Distributive and Redundancy Laws. This reduces the number of gates required for the circuit from 26 to only 2 (one OR and one NOT).

3. 

   Consider elimination of either the AND or OR operator by applying Boolean Identities as a final step for simplification of Boolean functions. Achieve further symbolic simplification using NAND "|", a combination of NOT and AND operators {' *}, and NOR "?", the expression simultaneously defining NOT and OR operators {' +}. Simplification of Boolean functions by elimination of the NOT operator is impossible; the operator set {*+} is not functionally complete as f (x) = x' cannot be expressed in terms of the product and sum operators.

Tips & Warnings

• Remember to follow rules of precedent for Boolean operators when simplifying and solving Boolean functions. Complete complements (NOT), products (AND) and then sums (OR).

• Simplifying Boolean functions using Boolean Identities does not guarantee optimal solutions of the simplest form. The order of law application may lead to suboptimal solutions; there are no firm rules to guide simplification using Boolean Identities that ensure simplest function form. The method does achieve significant reduction of complexity, but use of Karnaugh Maps and logic systems may achieve superior results when simplifying Boolean functions.

Resources

• Read this Article in Spanish
• Simplification of Boolean Functions Using Mapping