# Definition:Conjunctive Normal Form

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

- 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}$