Boolean Algebra & Combinational Logic

Boolean algebra theorems, expression simplification, Karnaugh maps.

Boolean Algebra

Boolean algebra is the mathematical system underlying all digital logic. Defined by George Boole in 1854, formalized by Claude Shannon for circuits in 1937.

Three fundamental operations:

• AND (·): logical product
• OR (+): logical sum
• NOT (¬): complement

Fundamental Theorems

Basic Identities

Commutativity and Associativity

A · B = B · A          A + B = B + A
(A · B) · C = A · (B · C)    (A + B) + C = A + (B + C)

Distributivity

A · (B + C) = (A · B) + (A · C)
A + (B · C) = (A + B) · (A + C)

De Morgan's Laws

Fundamental for simplification and NAND/NOR implementation:

¬(A · B) = ¬A + ¬B     (NOT AND = OR of complements)
¬(A + B) = ¬A · ¬B     (NOT OR = AND of complements)

In VHDL:

-- De Morgan 1: NOT (A AND B) = (NOT A) OR (NOT B)
o_y <= NOT (i_a AND i_b);  -- equivalent to:
o_y <= (NOT i_a) OR (NOT i_b);
 
-- De Morgan 2: NOT (A OR B) = (NOT A) AND (NOT B)
o_y <= NOT (i_a OR i_b);   -- equivalent to:
o_y <= (NOT i_a) AND (NOT i_b);

Expression Simplification

Algebraic Method

F = A·B + A·B̄
  = A·(B + B̄)    (distributivity)
  = A·1           (complement)
  = A             (identity)

Karnaugh Maps (K-map)

For functions with 2-4 variables, Karnaugh maps allow visual simplification.

2-variable K-map:

Example — 3-variable K-map:

Function: F(A,B,C) = Σ(1,3,5,7) → F = C

The group of 8 → F = C

K-map rules:

• Group '1's in groups of 2ⁿ (1, 2, 4, 8...)
• Groups may overlap
• Edges wrap around (toroidal)
• Larger groups = stronger simplification

Canonical Forms

Sum of Products (SOP)

F = A·B·C̄ + A·B̄·C + Ā·B·C

Each term (minterm) corresponds to a '1' row in the truth table.

Product of Sums (POS)

F = (A+B+C̄) · (A+B̄+C) · (Ā+B+C)

Each term (maxterm) corresponds to a '0' row in the truth table.

Application in VHDL

-- Unsimplified expression
o_f <= (i_a AND i_b AND NOT i_c) OR
       (i_a AND NOT i_b AND i_c) OR
       (NOT i_a AND i_b AND i_c);
 
-- The synthesizer automatically simplifies!
-- You do NOT need to simplify manually for synthesis.
-- The synthesizer uses its own algorithms (ESPRESSO, etc.)

The VHDL synthesizer performs logic simplification automatically — manual simplification is not required for synthesis. However, understanding simplification helps you understand the hardware produced.