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

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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Disjunctive_Normal_Form&oldid=669560"