📜 Lecture 5: Boolean Algebra & Simplification

This lecture introduces the algebraic rules used to simplify Boolean expressions, which leads to smaller, cheaper, and faster circuits.

Key Concepts

• DeMorgan's Laws:

  • (X + Y)' = X' · Y' (Break the bar, change the OR to AND)
  • (X · Y)' = X' + Y' (Break the bar, change the AND to OR)
  • Extended Example: (X·Y' + Z)' = (X·Y')' · Z' = (X' + Y) · Z'

• Basic Boolean Laws (Summary):

  • Operations with 0/1:
    • X + 0 = X
    • X · 1 = X (Identity)
    • X + 1 = 1 (Annihilator)
    • X · 0 = 0 (Annihilator)
  • Idempotent Law:
    • X + X = X
    • X · X = X
  • Complementarity Law:
    • X + X' = 1
    • X · X' = 0
  • Distributive Laws:
    • X(Y + Z) = XY + XZ
    • X + YZ = (X + Y) · (X + Z) (This is a key rule)
  • Commutative/Associative Laws: Order doesn't matter.
    • X + Y = Y + X
    • X(YZ) = (XY)Z = XYZ

• Duality:

  • To find the Dual (F^D) of an expression: Swap all + and ·, and swap all 0 and 1.
  • Crucially: Variables and complements are not changed.
  • Example: F = A·B' + C
  • Dual: F^D = (A + B') · C

• Relationship between Dual and Complement:

  • The Complement (F') and the Dual (F^D) are related.
  • F'(A,B,C) = F^D(A', B', C')
  • (The complement of a function is the dual of that function with all inputs complemented).

• Graphical DeMorgan's Law:

  • A method for transforming gates visually.
  • Example: A NOR-NOR circuit ( (A+B)' + (C+D)' )' can be transformed. Applying DeMorgan's to the final NOR gives (A+B)'' · (C+D)'' = (A+B)·(C+D). This is an OR-AND circuit.
  • The lecture shows a NAND-NOR circuit ( (AB)' + (CD)' )' simplifying to (AB)'' · (CD)'' = AB · CD, which is a single 4-input AND gate.

• Simplification Theorems:

  1. Absorption Law:
     • X + XY = X
     • X(X + Y) = X (Dual)
  2. Adjacency Law:
     • XY + XY' = X
     • (X + Y)(X + Y') = X (Dual)
  3. Redundancy Theorem:
     • XY + X'Z + YZ = XY + X'Z
     • The YZ term is redundant and can be removed.

• Circuit Minimization Example (from Lecture 4):

  • Function: f = A'BC' + A'BC + AB'C + ABC
  • Step 1: Group adjacent terms using X+X=X (Idempotent Law) to duplicate a term: f = (A'BC' + A'BC) + (A'BC + ABC) + (AB'C + ABC)
  • Step 2: Apply Adjacency Law (XY + XY' = X) to each group:
    • (A'B)(C' + C) = A'B
    • (BC)(A' + A) = BC
    • (AC)(B' + B) = AC
  • Step 3: Resulting expression: f = A'B + BC + AC
  • Step 4: Apply Redundancy Theorem (XY + X'Z + YZ = XY + X'Z):
    • Here X=A, Y=C, Z=B. The term BC (or YZ) is redundant.
  • Final Simplified Function: f = A'B + AC