Disjunctive Normal Form

Introduction to DNF

Disjunctive Normal Form (DNF) is a standard way to write Boolean expressions:

DNF = OR of ANDs (sum of products)

Structure: (ter$m_1$) $\lor$ (ter$m_2$) $\lor$ ... $\lor$ (termₙ)

Where each term is an AND of literals (variables or their complements).

Examples:

• (A $\land$ B) $\lor$ ($\neg$A $\land$ C) - DNF with 2 terms
• A $\land$ B $\land$ C - DNF with 1 term
• (P $\land$ $\neg$Q) $\lor$ ($\neg$P $\land$ Q) $\lor$ (P $\land$ Q) - DNF with 3 terms

Recognizing DNF

To check if an expression is in DNF:

1. Top level must be OR (or a single term)
2. Each term must be AND of literals only
3. No nested operations - no OR inside AND, no AND inside OR

Valid DNF:

• (A $\land$ B) $\lor$ (C $\land$ D) ✓
• A $\land$ B ✓ (single term)
• A $\lor$ B $\lor$ C ✓ (each term is one literal)

Not DNF:

• A $\land$ (B $\lor$ C) ✗ (OR nested inside AND)
• (A $\lor$ B) $\land$ (C $\lor$ D) ✗ (AND at top level with OR terms)

DNF from Truth Table

To write a function in DNF from its truth table:

1. Find all rows where output is TRUE (1)
2. Write the minterm for each TRUE row
3. OR all minterms together

Example for f(A,B) = 1 when A=0,B=1 or A=1,B=1:

• Row A=0,B=1 $\to$ minterm: $\neg$A $\land$ B
• Row A=1,B=1 $\to$ minterm: A $\land$ B
• DNF: ($\neg$A $\land$ B) $\lor$ (A $\land$ B)

This is called the canonical DNF or sum of minterms.

Sum of Minterms Notation

The sum of minterms notation uses $\Sigma$ (sigma) to list which minterms are ORed:

f(A,B) = $\Sigma$m(1, 3) means: f = $m_1$ $\lor$ $m_3$

Where $m_1$ = $\neg$A $\land$ B and $m_3$ = A $\land$ B.

This is shorthand for listing all the truth table rows where f is TRUE.

Examples (for variables A, B):

• $\Sigma$m(0) = $\neg$A $\land$ $\neg$B (true only at row 0)
• $\Sigma$m(0, 3) = ($\neg$A $\land$ $\neg$B) $\lor$ (A $\land$ B)
• $\Sigma$m(0, 1, 2, 3) = 1 (always true)

Canonical DNF

Canonical DNF (also called "full DNF" or "complete sum of minterms"):

• Every term is a full minterm (includes ALL variables)
• Each minterm appears exactly once
• Unique representation for each function

Non-canonical DNF:

• Terms may not include all variables
• May be simplified but still valid DNF

Example for f(A,B) = A:

• Canonical: (A $\land$ $\neg$B) $\lor$ (A $\land$ B)
• Simplified: A (still DNF, but not canonical)

Evaluating DNF Expressions

To evaluate a DNF expression:

1. Evaluate each AND term separately
2. OR the results together

Since DNF is OR of ANDs:

• The expression is TRUE if any one term is TRUE
• Each term is TRUE only if all its literals are TRUE

Example: (A $\land$ $\neg$B) $\lor$ ($\neg$A $\land$ B) with A=1, B=0:

• First term: 1 $\land$ $\neg$0 = 1 $\land$ 1 = 1 ✓
• Since one term is TRUE, result is TRUE

Converting Expressions to DNF

To convert an expression to DNF:

Method 1: Truth Table

1. Build the truth table
2. Write minterm for each TRUE row
3. OR all minterms

Method 2: Algebraic

1. Eliminate implications/equivalences
2. Move NOTs inward (De Morgan's)
3. Distribute AND over OR

Example: A $\land$ (B $\lor$ C)

• Distribute: (A $\land$ B) $\lor$ (A $\land$ C) $\leftarrow$ DNF!

Properties of DNF

Key DNF Properties:

1. Universality: Any Boolean function can be written in DNF
2. Canonical uniqueness: The canonical DNF (sum of minterms) is unique
3. Easy TRUE detection: Expression is TRUE if ANY term is TRUE
4. Satisfiability: A DNF is satisfiable iff at least one term is satisfiable

Applications:

• Circuit design (two-level AND-OR circuits)
• SAT solving
• Database query optimization

DNF Simplification Preview

Canonical DNF can often be simplified using Boolean algebra:

Common simplifications:

1. Adjacency: (A $\land$ B) $\lor$ (A $\land$ $\neg$B) = A (Terms differing in one variable combine)

2. Absorption: A $\lor$ (A $\land$ B) = A (Larger term absorbed by smaller)

3. Consensus: (A$\land$B) $\lor$ ($\neg$A$\land$C) $\lor$ (B$\land$C) - the (B$\land$C) term is redundant

Simplification reduces circuit complexity without changing function behavior.

DNF from Natural Language

Natural language to DNF:

"The suspect is guilty IF (had motive AND had opportunity) OR (was caught on camera)"

This naturally maps to DNF:

• Each "case" or scenario becomes a term (conjunction)
• Cases are combined with OR
• Result: (Motive $\land$ Opportunity) $\lor$ Camera

DNF matches how we often describe conditions: "They did it if THIS happened, or THAT happened."

Non-Canonical DNF

Canonical DNF: Every term contains ALL variables (minterms).

Non-canonical DNF: Terms may omit variables.

Example (3 variables A, B, C):

• Canonical: (A $\land$ B $\land$ C) $\lor$ (A $\land$ B $\land$ $\neg$C)
• Non-canonical: A $\land$ B (omits C - works for both C values!)

Non-canonical is often simpler but equivalent!

DNF Minimization Preview

Minimizing DNF means finding the simplest equivalent expression.

Key techniques:

• Adjacency: Terms differing in one variable can combine (A$\land$B$\land$C) $\lor$ (A$\land$B$\land$$\neg$C) = A$\land$B
• Absorption: P $\lor$ (P$\land$Q) = P
• Karnaugh maps: Visual method for finding minimal forms

Minimization reduces gates in circuits!

Complex Expression to DNF

Converting to DNF:

1. Eliminate implications: P $\to$ Q becomes $\neg$P $\lor$ Q
2. Push negations inward (De Morgan)
3. Distribute OR over AND: Use P $\lor$ (Q $\land$ R) = (P $\lor$ Q) $\land$ (P $\lor$ R), then expand
4. Distribute AND over OR to get final DNF

Or: Build truth table, then write sum of minterms.

DNF as Sufficient Conditions

Reading DNF semantically:

• Each product term = one sufficient condition for the function to be true
• The OR connecting them = "any of these will do"
• Example: (A $\land$ B) $\lor$ ($\neg$A $\land$ C) means "true when A and B are both true, OR when A is false and C is true"

Why this matters:

• DNF directly answers "when does this function output true?"
• Each term is independent—satisfying any single term is enough
• Short-circuit evaluation: if any term is true, stop checking