Definition:Disjunctive Normal Form

Definition

A propositional formula $P$ is in disjunctive normal form if and only if it consists of a disjunction of:

$(1):\quad$ conjunctions of literals

and/or:

$(2):\quad$ literals.

Examples

$\paren {\neg p \land q \land r} \lor \paren {\neg q \land r} \lor \paren {\neg r}$

is in DNF.

$\paren {\neg p \land q \land r} \lor \paren {\paren {p \lor \neg q} \land r} \lor \paren {\neg r}$

is not in DNF because there is a disjunction buried in the second conjunction.

$\paren {\neg p \land q \land r} \lor \neg \paren {\neg q \land r} \lor \paren {\neg r}$

is not in DNF because the second conjunction is negated.

$p \lor q$

is in DNF, as it is a disjunction of literals.

$p \land q$

is in DNF, as it is a trivial (one-element) disjunction of a conjunction of literals.

Also defined as

Some sources include parentheses as appropriate within both the conjunctions and disjunctions in a standard format, for example:

$\paren {\paren {\paren {\neg p \land q} \land r} \lor \paren {\neg q \land r} } \lor \paren {\neg r}$

but this is usually considered unnecessary in light of the Rule of Distribution.

Also known as

This is often found referred to in its abbreviated form DNF.

Also see

• Definition:Conjunctive Normal Form
• Definition:Negation Normal Form

• Existence of Disjunctive Normal Form of Statement

Sources

• 1964: Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning ... (previous) ... (next): $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 5$: Exercises, Group $\text{III}$
• 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): disjunctive normal form