Boolean Algebra

Boolean algebra, a logic algebra, allows the rules used in the algebra of numbers to be applied to logic. It formalizes the rules of logic. Boolean algebra is used to simplify Boolean expressions which represent combinational logic circuits. It reduces the original expression to an equivalent expression that has fewer terms which means that less logic gates are needed to implement the combinational logic circuit.

Boolean Expression Simplification

The following example shows how to use algebraic techniques to simplify a boolean expression

~(A * B) * (~A + B) * (~B + B)
~(A * B) * (~A + B) * 16 - Complement law
~(A * B) * (~A + B)5 - Identity law
(~A + ~B) * (~A + B)8 - DeMorgan's law
~A + ~B * B4 - Distributive law
~A + 06 - Complement law
~A5 - Identity law

Each line (or step) gives a new expression and the rule or rules used to derive it from the previous one. There can be several ways to arrive at the final result.

Laws of Boolean Algebra

Boolean Algebra Laws are used to simplify boolean expressions.

    Basic Boolean Laws

  1. Idempotent Law
    • A * A = A
    • A + A = A
  2. Associative Law
    • (A * B) * C = A * (B * C)
    • (A + B) + C = A + (B + C)
  3. Commutative Law
    • A * B = B * A
    • A + B = B + A
  4. Distributive Law
    • A * (B + C) = A * B + A * C
    • A + (B * C) = (A + B) * (A + C)
  5. Identity Law
    • A * 0 = 0     A * 1 = A
    • A + 1 = 1     A + 0 = A
  6. Complement Law
    • A * ~A = 0
    • A + ~A = 1
  7. Involution Law
    • ~(~A) = A
  8. DeMorgan's Law
    • ~(A * B) = ~A + ~B
    • ~(A + B) = ~A * ~B

    Redundancy Laws

  9. Absorption
    • A + (A * B) = A
    • A * (A + B) = A
  10.  
    • (A * B) + (A * ~B) = A
    • (A + B) * (A + ~B) = A
  11.  
    • A + (~A * B) = A + B
    • A * (~A + B) = A * B

Each law is described by two parts that are duals of each other. The Principle of duality is

  • Interchanging the + (OR) and * (AND) operations of the expression.
  • Interchanging the 0 and 1 elements of the expression.
  • Not changing the form of the variables.

Application of Boolean Algebra

Combinational Logic Circuit Design comprises the following steps

  1. From the design specification, obtain the truth table
  2. From the truth table, derive the Sum of Products Boolean Expression.
  3. Use Boolean Algebra to simplify the boolean expression. The simpler the boolean expression, the less logic gates will be used.
  4. Use logic gates to implement the simplified Boolean Expression.