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
- $\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
- 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}$
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): conjunctive normal form