Definition:Conjunctive Normal Form

Definition

A logical formula $P$ is in conjunctive normal form (abbreviated CNF) if it consists of a conjunction of:

• disjunctions of literals, and/or
• 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.

See also

• Disjunctive Normal Form (DNF)
• Negation Normal Form (NNF)

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Exercises: Group $\text{III}$