Conjunctive Normal Form

logic

Definition

Conjunctive Normal Form

A formula is in conjunctive normal form (CNF) if it is a conjunction of disjunctions of literals. The precise reading depends on the order of the underlying logic: propositional CNF and first-order CNF.

Propositional logic

Definition

Conjunctive Normal Form (Propositional Logic)

A propositional formula is in conjunctive normal form (CNF) if it is a conjunction of disjunctions of literals — a conjunction of clauses:

$$\underset{i=1}{\overset{n}{\bigwedge }}\underset{j=1}{\overset{m_i}{\bigvee }}{L}_{ij},$$

where each $L_{ij}$ is a literal, i.e. an atom or a negated atom. The degenerate cases count as well: a single clause ($p\vee q$), a single literal ($\neg p$), and a single atom ($p$) are all in CNF. Examples:

$$(\neg a\vee b)\wedge (a\vee \neg c\vee d)\wedge \neg b$$

Link to original

First-order logic

Definition

Conjunctive Normal Form (First-Order Logic)

A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where each clause is a disjunction of literals:

$$\underset{i=1}{\overset{n}{\bigwedge }}\underset{j=1}{\overset{m_i}{\bigvee }}{L}_{ij}$$

Each literal $L_{ij}$ is either an atom or a negated atom.

Link to original