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
Arbitrary Example $1$
- $\paren {\neg p \land q \land r} \lor \paren {\neg q \land r} \lor \paren {\neg r}$
is in disjunctive normal form.
Arbitrary Example $2$
- $\paren {\neg p \land q \land r} \lor \paren {\paren {p \lor \neg q} \land r} \lor \paren {\neg r}$
is not in disjunctive normal form because there is a disjunction buried in the second conjunction.
Arbitrary Example $3$
- $\paren {\neg p \land q \land r} \lor \neg \paren {\neg q \land r} \lor \paren {\neg r}$
is not in disjunctive normal form because the second conjunction is negated.
Arbitrary Example $4$
- $\paren {p \land q \land r \land \neg r} \lor \paren {q \land \neg q} \lor \paren {q \land p \land \neg p}$
is in disjunctive normal form.
It is immediate that the above forms a contradiction.
Disjunction
- $p \lor q$
is in disjunctive normal form, as it is a disjunction of literals.
Conjunction
- $p \land q$
is in disjunctive normal form, as it is a trivial (one-element) disjunction of a conjunction of literals.
Also defined as
When presenting disjunctive normal form, 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
Disjunctive normal form is often found referred to in its abbreviated form DNF or dnf.
Also see
- Results about disjunctive normal form can be found here.
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
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): disjunctive normal form