Boolean Algebra Basics

Foundations of Boolean Algebra

• Logical States: Binary variables are limited to two distinct states: $1$ (logic high / true) and $0$ (logic low / false).

• Primary Purpose: Forms the mathematical framework for analyzing, designing, and optimizing digital binary circuits.

Fundamental Operations

• Boolean Addition ($\text{OR}$ Operation):

  • Denoted by the plus symbol ($+$); forms a sum term (e.g., $A + B$).

  • Condition: Evaluates to $1$ if one or more literals equal $1$; evaluates to $0$ only when all literals are simultaneously $0$.

• Boolean Multiplication ($\text{AND}$ Operation):

  • Denoted by a dot ($\cdot$) or adjacent literals (e.g., $AB$); forms a product term.

  • Condition: Evaluates to $1$ if and only if all literals equal $1$; evaluates to $0$ if any single literal is $0$.

Universal Laws of Boolean Algebra

• Commutative Laws: Operand order does not alter output.

  • Addition: $A + B = B + A$

  • Multiplication: $A \cdot B = B \cdot A$

• Associative Laws: Grouping order across identical operations does not alter output.

  • Addition: $(A + B) + C = A + (B + C)$

  • Multiplication: $(A \cdot B) \cdot C = A \cdot (B \cdot C)$

• Distributive Laws:

  • Multiplication over Addition: $A \cdot (B + C) = AB + AC$

  • Addition over Multiplication: $A + (B \cdot C) = (A + B)(A + C)$

Essential Rules and Identities

• Identity Rules: $A + 0 = A$ and $A \cdot 1 = A$

• Null (Annulment) Rules: $A + 1 = 1$ and $A \cdot 0 = 0$

• Idempotent Rules: $A + A = A$ and $A \cdot A = A$

• Involution (Double Negation): $({A}')' = A$

• Complement Rules: $A + {A}' = 1$ and $A \cdot {A}' = 0$

• Absorption Rules: $A + AB = A$ and $A(A + B) = A$

• Elimination Rule: $A + {A}'B = A + B$

• Second Distributive Dual: $(A + B)(A + C) = A + BC$

• XOR and XNOR:

  • $X \oplus Y = {X}'Y + X{Y}' = (X + Y)({X}' + {Y}')$

  • $X \odot Y = {X}'{Y}' + XY = (X \oplus Y)'$

DeMorgan's Theorems and Dualities

• First Theorem (Law of Intersection): The complement of a product equals the sum of the complements.

  • Mathematical Identity: $({A \cdot B})' = {A}' + {B}'$

  • Gate Equivalence: A $\text{NAND}$ gate functions identically to an inverted-input $\text{OR}$ (Negative-OR) gate.

• Second Theorem (Law of Union): The complement of a sum equals the product of the complements.

  • Mathematical Identity: $({A + B})' = {A}' \cdot {B}'$

  • Gate Equivalence: A $\text{NOR}$ gate functions identically to an inverted-input $\text{AND}$ (Negative-AND) gate.

• Duality Principle: An expression's dual is obtained by interchanging $0 \leftrightarrow 1$ and $\text{AND} (\cdot) \leftrightarrow \text{OR} (+)$.

Circuit Simplification Workflow

1. Write Boolean logic expressions at each successive gate output node.

2. Apply DeMorgan's theorems to break overbars covering multiple terms.

3. Cancel paired double-negations via involution ($({A}')' = A$).

4. Expand and factor terms using associative and distributive laws.

5. Eliminate redundant variables and terms using identity, complement, idempotent, and absorption rules to minimize hardware gate count.