Disjunctive Normal Form

logic

Definition

Disjunctive Normal Form

A formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals. Thus, a formula of the form

$$(L_{1,1}\wedge \cdots \wedge L_{1,m})\vee \cdots \vee (L_{n,1}\wedge \cdots \wedge L_{n,m})$$

where each $L_{i,j}$ is a literal, is in disjunctive normal form.

Examples:

• $(a\wedge b)\vee (a\wedge \neg c\wedge d)\vee \neg b$
• $(\neg a\wedge x\wedge \neg c\vee d)\vee (\neg b\wedge \neg y)$