Definition:Conjunctive Normal Form

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

• Definition:Disjunctive Normal Form
• Definition:Negation Normal Form

• Existence of Conjunctive Normal Form of Statement

Sources

• 1959: A.H. Basson and D.J. O'Connor: Introduction to Symbolic Logic (3rd ed.) ... (previous) ... (next): $\S 3.7$: Decision Procedures and Normal Forms
• 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}$