Disjunctive Normal Form (Propositional Logic)

Definition

Disjunctive Normal Form (Propositional Logic)

A propositional formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals — a disjunction of terms:

$$\underset{i=1}{\overset{n}{\bigvee }}\underset{j=1}{\overset{m_i}{\bigwedge }}{L}_{ij},$$

where each $L_{ij}$ is a literal, i.e. an atom or a negated atom. The degenerate cases count as well: a single conjunction ($p\wedge q$), a single literal ($\neg p$), and a single atom ($p$) are all in DNF. Example:

$$(a\wedge b)\vee (a\wedge \neg c\wedge d)\vee \neg b$$

Transformation

Every formula has an equivalent DNF (normal form existence). Rewriting applies the De Morgan’s rules, double negation elimination, and distributivity — for DNF one distributes $\wedge$ over $\vee$, the dual of the CNF distribution:

$$(A_1\vee \cdots \vee A_m)\wedge B\equiv (A_1\wedge B)\vee \cdots \vee (A_m\wedge B)$$

Worked transformation

$$\begin{array}{rl}(p\to q)\wedge (r\vee s)& \equiv (\neg p\vee q)\wedge (r\vee s)\\ & \equiv (\neg p\wedge r)\vee (\neg p\wedge s)\vee (q\wedge r)\vee (q\wedge s)\end{array}$$

Exponential Blow-up

Warning

As with CNF, some formulas have only exponentially large equivalent DNFs, e.g. nested equivalences such as $p_1\leftrightarrow (p_2\leftrightarrow (p_3\leftrightarrow p_4))$. Naming (the definitional transformation) avoids the blow-up by preserving satisfiability rather than equivalence.