Definition:Conjunctive Normal Form

From ProofWiki
Jump to navigation Jump to search

Definition

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

$(1): \quad$ disjunctions of literals

and/or:

$(2): \quad$ literals.


Examples

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

is in CNF.

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

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

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

is not in CNF because the second disjunction is negated.

$p \land q$

is in CNF, as it is a conjunction of literals.

$p \lor q$

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


Also defined as

When presenting conjunctive 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 \lor q} \lor r} \land \paren {\neg q \lor r} } \land \paren {\neg r}$

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


Also known as

Conjunctive normal form is often found referred to in its abbreviated form CNF.


Also see

  • Results about conjunctive normal form can be found here.


Sources