Definition:Disjunctive Normal Form

From ProofWiki
Jump to navigation Jump to search

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

$\left({\neg p \land q \land r}\right) \lor \left({\neg q \land r}\right) \lor \left({\neg r}\right)$

is in DNF.

$\left({\neg p \land q \land r}\right) \lor \left({\left({p \lor \neg q}\right) \land r}\right) \lor \left({\neg r}\right)$

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

$\left({\neg p \land q \land r}\right) \lor \neg \left({\neg q \land r}\right) \lor \left({\neg r}\right)$

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:

$\left({\left({\left({\neg p \land q}\right) \land r}\right) \lor \left({\neg q \land r}\right)}\right) \lor \left({\neg r}\right)$

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


Sources