Boolean Expression Simplification

Every extra gate in a combinational circuit costs silicon area, power, and propagation delay. Boolean expression simplification is the systematic process that chip designers use to strip a logic function down to its minimum gate count before layout.

Core Concept

Algebraic simplification applies axioms and theorems in sequence to reduce the literal count of a Boolean expression. A literal is any variable in complemented or uncomplemented form. Fewer literals means fewer gate inputs and shorter critical paths.

The two main methods are algebraic manipulation and Karnaugh map grouping. Algebraic manipulation is flexible but requires spotting patterns. K-maps are mechanical and less error-prone for up to six variables. Both methods must give the same minimal result — if they differ, a mistake was made.

A 74HC08 quad-AND gate has t_pd ≈ 6 ns at 5 V and fan-out of 10. Combining it with a 74HC32 OR gate and a 74HC86 XOR gate lets a designer implement F=BC+A(B⊕C) in three standard ICs instead of five separate gates for the unsimplified form.

Boolean Expression

The unsimplified sum of products (SOP) form is F = A'BC + ABC + AB'C + ABC'. After applying the complement axiom (A'+A=1) and factoring, F = BC + A(B⊕C). The number of literals falls from 12 to 5.

Given:
  F = A'B'C' + A'BC' + AB'C' + ABC'

Formula / Rule:
  Factor out common terms, apply complement axiom, then absorption if possible

Step by step:
  Step 1: Factor C': F = C'·(A'B' + A'B + AB' + AB)
  Step 2: Group inside bracket:
          A'B' + A'B = A'(B'+B) = A'·1 = A'
          AB' + AB     = A(B'+B)  = A·1  = A
  Step 3: F = C'·(A' + A)
  Step 4: A' + A = 1
  Step 5: F = C'·1 = C'

Final Answer:
  F = C' (the function depends only on C)

Exam Tip: Always look for a common factor across ALL minterms first — if found, the expression may collapse to a single literal as shown above. A common mistake is grouping only pairs and missing a larger factorisation. Also, the SOP and POS minimal forms may have the same number of gates but different structures; GATE sometimes asks for the form with fewer literals specifically.

Key Properties

• Goal: minimise literal count, then gate count, then levels of logic (depth)
• Complement axiom A+A'=1 is the most used single step in algebraic simplification
• Absorption A+AB=A removes entire product terms without changing the function
• Redundancy theorem A+A'B=A+B expands coverage without adding minterms
• 74HC86 XOR gate: Vcc 2–6 V, t_pd ≈ 7 ns, replaces two AND gates and one OR gate in many expressions
• Two-level SOP/POS is standard for PLDs and early synthesis; XOR-based forms suit LUT-based FPGAs
• Minimal SOP may not be unique — multiple expressions with equal literal count can all be correct

Quick Revision

• Literal = one variable (complemented or not); minimising literals reduces gate inputs
• Step order: factor → complement axiom → absorption → redundancy → repeat
• If a variable appears in every minterm, factor it out first
• SOP minimal and POS minimal are duals — one may have fewer literals than the other
• K-map gives the same result as algebra but is faster for 3–4 variables
• XOR structure appears when adjacent minterms differ in exactly two variables
• Exam trap: stopping after one factoring step and missing a further complement-axiom collapse