Disjunctive Normal Form — Definition, Formula & Examples

Disjunctive Normal Form (DNF) is a way of writing a logical formula as a disjunction (OR) of one or more conjunctions (ANDs), where each conjunction contains only variables or their negations.

A propositional formula is in disjunctive normal form if it is expressed as $C_1 \lor C_2 \lor \cdots \lor C_n$ , where each clause $C_i$ is a conjunction of literals, and a literal is either a propositional variable $p$ or its negation $\lnot p$ .

Key Formula

\bigvee_{i=1}^{n}\left(\bigwedge_{j=1}^{m} l_{ij}\right)

Where:

$n$ = Number of disjunctive clauses
$m$ = Number of literals in each clause (may vary by clause)
$l_{ij}$ = A literal — either a variable or its negation

How It Works

To convert any propositional formula into DNF, first build its truth table and identify every row where the formula evaluates to true. For each such row, form a conjunction of all variables: use the variable itself if its value is true in that row, or its negation if false. Finally, take the disjunction (OR) of all these conjunctions. The result is logically equivalent to the original formula and is guaranteed to be in DNF.

Worked Example

Problem: Convert the formula

(p \to q)

into disjunctive normal form.

Step 1: Rewrite the conditional using its logical equivalence.

p \to q \equiv \lnot p \lor q

Step 2: Check whether the result is already in DNF. Each disjunct must be a conjunction of literals. Here

\lnot p

is a single literal (a trivial conjunction), and

q

is also a single literal.

\lnot p \lor q

Step 3: Verify via truth table: the formula is true when

p

is false (regardless of

q

) or when

q

is true. The rows

(F,F)

(F,T)

, and

(T,T)

all give true, matching

\lnot p \lor q

Answer: The DNF of

(p \to q)

\lnot p \lor q

Why It Matters

DNF is a canonical form used in digital circuit design, where each AND clause maps to a logic gate feeding into a single OR gate. It also appears in database query optimization and automated theorem proving, making it a practical tool well beyond the classroom.

Common Mistakes

Mistake: Confusing DNF with CNF (Conjunctive Normal Form). Students sometimes write an AND of ORs and call it DNF.

Correction: DNF is an OR of ANDs. CNF is the dual: an AND of ORs. Remember "Disjunctive" means the top-level connective is disjunction (OR).