Introduction to DLD

Laws of Boolean Algebra in DLD

Laws of Boolean Algebra in DLD are mainly used to minimize Boolean Expressions in Digital Logic Design (DLD). These Boolean Laws are very helpful in reducing the number of logic gates, the number of gate inputs, the number of logic operations, Circuit complexity, Circuit area, Propagation delay, Power consumption, and cost depends on the implementation technology.

Simplification of Boolean Expressions Using Laws of Boolean Algebra

In this section, we will see various examples that help us to understand how the Boolean expressions are simplified using laws of Boolean algebra,

Example: 01

Consider the Boolean expression: Y = AB + AC. This original implementation requires 2 AND gates and 1 OR gate, with a total of 6 gate inputs.

  • Using the Distributive Law: Y = A(B + C)

Now the circuit requires only 1 OR gate and 1 AND gate, with a total of 5 gate inputs. Therefore, Boolean Algebra can reduce the number of gates, gate inputs, operations, circuit complexity, area, delay, and power requirements, depending on the circuit and technology used.

Example: 02

Consider the Boolean expression: Y = AB + AB’. This original circuit requires 2 AND gates, 1 NOT gate, and 1 OR gate.

  • Using the Distributive Law: Y = A(B + B’)
  • Using the Complement Law: Y = A(1)
  • Using the Identity Law: Y = A

However, this example eliminates all gates; you just need a buffer that stores the input, and our input is the output. 

Minimization Techniques in DLD

Minimization techniques simplify Boolean functions to reduce logic gates, gate inputs, circuit complexity, delay, power consumption, and hardware cost. Here is the list of minimization techniques used in DLD

  • Boolean Algebra: Simplifies Boolean expressions using algebraic laws and theorems.
  • Karnaugh Map (K-Map): Minimizes Boolean functions by grouping adjacent 1s, 0s, or don’t-care cells.
  • Quine-McCluskey Method: Uses a systematic tabular procedure to minimize Boolean functions.
  • Don’t-Care Conditions: Uses unused or irrelevant input combinations to obtain further simplification.
  • Computer-Aided Minimization: Uses software tools to simplify complex Boolean functions automatically.

Types of Laws of Boolean Algebra

Here is a comprehensive list of the commonly used Laws, Rules, and Theorems of Boolean Algebra.

1. Identity Laws

The Identity Laws state that combining a Boolean variable with its identity value does not change the variable. For AND operation, the identity value is 1, while for OR operation, it is 0.

  • AND: A · 1 = A
  • OR: A + 0 = A

2. Null / Domination Laws

The Null or Domination Laws state that certain Boolean values completely determine the output. For AND, 0 always produces 0, while for OR, 1 always produces 1.

  • AND: A · 0 = 0
  • OR: A + 1 = 1

3. Idempotent Laws

The Idempotent Laws state that repeating the same Boolean variable in an AND or OR operation does not change its value. Therefore, duplicate variables can be removed during Boolean expression simplification.

  • AND: A · A = A
  • OR: A + A = A

4. Complement Laws

The Complement Laws describe the relationship between a Boolean variable and its complement. A variable ANDed with its complement gives 0, while ORing them gives 1. The complement of 0 is 1, and the complement of 1 is 0.

  • AND: A · A’ = 0
  • OR: A + A’ = 1
  • 0′ = 1
  • 1′ = 0

5. Involution Law

The Involution Law, also called the Double Complement Law, states that taking the complement of a Boolean variable twice returns the original variable. It is useful when simplifying expressions containing multiple complements.

  • (A’)’ = A

6. Commutative Laws

The Commutative Laws state that changing the order of Boolean variables does not change the result. This rule applies to both AND and OR operations.

  • AND: A · B = B · A
  • OR: A + B = B + A

7. Associative Laws

The Associative Laws state that the grouping of Boolean variables can be changed without affecting the result. These laws apply to both AND and OR operations.

  • AND: (A · B) · C = A · (B · C)
  • OR: (A + B) + C = A + (B + C)

8. Distributive Laws

The Distributive Laws allow Boolean terms to be expanded or factored. They are useful for converting and simplifying Boolean expressions.

  • AND over OR: A · (B + C) = AB + AC
  • OR over AND: A + BC = (A + B)(A + C)

9. Absorption Laws

The Absorption Laws eliminate redundant terms from a Boolean expression. They are particularly useful for reducing the number of operations and logic gates.

  • AND: A(A + B) = A
  • OR: A + AB = A

10. De Morgan’s Laws

De Morgan’s Laws provide rules for finding the complement of AND and OR expressions. They change AND to OR, or OR to AND, while complementing each variable.

  • First Law: (AB)’ = A’ + B’
  • Second Law: (A + B)’ = A’B’

For three variables:

  • (ABC)’ = A’ + B’ + C’
  • (A + B + C)’ = A’B’C’

11. Redundancy / Reduction Laws

The Redundancy or Reduction Laws simplify expressions by removing or reducing terms that are not essential to the final result. They are useful for obtaining simpler Boolean expressions and more efficient circuits.

  • A + A’B = A + B
  • A(A’ + B) = AB

12. Consensus Theorem

The Consensus Theorem states that certain terms in a Boolean expression can be removed without changing the output. It helps eliminate unnecessary terms and reduce circuit complexity.

  • AB + A’C + BC = AB + A’C

Here, BC is the consensus term and can be removed.

13. Consensus Theorem — Dual Form

The Dual Consensus Theorem is obtained by applying the Principle of Duality to the Consensus Theorem. It allows a redundant product term to be removed from a Boolean expression.

  • (A + B)(A’ + C)(B + C) = (A + B)(A’ + C)

Here, (B + C) is the redundant term.

14. Principle of Duality

The Principle of Duality states that a valid Boolean expression has a corresponding dual expression. To obtain the dual, interchange AND and OR operations and interchange 0 and 1. The variables and their complements remain unchanged.

  • + ↔ ·
  • 0 ↔ 1

Example:

Original:

A + 0 = A

Dual:

A · 1 = A

Useful Boolean Simplification Rules

These are frequently used when simplifying Boolean expressions:

  • A + AB = A
  • A(A + B) = A
  • A + A’B = A + B
  • A(A’ + B) = AB
  • AB + AB’ = A
  • (A + B)(A + B’) = A
  • A + A’ = 1
  • AA’ = 0
  • A + 1 = 1
  • A · 0 = 0
  • A + 0 = A
  • A · 1 = A