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

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

is in CNF.

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

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

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

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

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

$\left({\left({\left({\neg p \lor q}\right) \lor r}\right) \land \left({\neg q \lor r}\right)}\right) \land \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 CNF.


Also see


Sources