Disjunctive Normal Form

logic

Definition

Disjunctive Normal Form

A formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals. The precise reading depends on the order of the underlying logic: propositional DNF and first-order DNF.

Propositional logic

Definition

Disjunctive Normal Form (Propositional Logic)

A propositional formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals — a disjunction of terms:

$$\underset{i=1}{\overset{n}{\bigvee }}\underset{j=1}{\overset{m_i}{\bigwedge }}{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 conjunction ($p\wedge q$), a single literal ($\neg p$), and a single atom ($p$) are all in DNF. Example:

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

Link to original

First-order logic

Definition

Disjunctive Normal Form (First-Order Logic)

A formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals:

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

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

Link to original