In generale, in matematica, una forma normale di un oggetto matematico è una sua rappresentazione in una forma prestabilita, che preserva l’equivalenza con l’oggetto originario rispetto a una deterinata relazione di equivalenza. In altre parole una forma normale, è un modo “standard” per descrivere una famiglia di oggetti matematici, che evidenzia un certo tipo di struttura di tali oggetti.
Prende il nome di normalizzazione il processo di trasformazione di un oggetto matematico in una forma normale.
Nel contesto della logica proposizionale classica:
Definizione: un letterale è una variabile o la negazione di una variabile:
$$ p, \neg p, q, \neg q, r, \neg r, ... \ \ \ PV=\{p, q, r, ...\} $$
Definizione: una formula è in forma normale disgiuntive (DNF, Disjunctive Normal Form) se è della forma
$$ \bigvee_{i=1}^{n}\Big(\bigwedge_{j=1}^{m_i}l_{i, j}\Big)=(l_{1,1}\land ... \land l_{1, m_1})\lor ...\lor(l_{n,1}\land...\land l_{n, m_n}) $$
dove, per ogni $i=1, ..., n$ e $j=1, ..., m_i$ (con $n\geq 1$ e $m_i\geq1$), $l_{i, j}$ è un letterale.
Definizione: una formula è in forma normale congiuntiva (CNF, Conjunctive Normall Form) se è della forma
$$ \bigwedge_{i=1}^n \Big( \bigvee_{j=1}^{m_i} l_{i, j} \Big)=(l_{1,1}\lor ... \lor l_{1, m_1})\land ...\land (l_{n, 1}\lor ...\lor l_{n, m_n}) $$
dove, per ogni $i=1, ..., n$ e $j=1, ..., m_i$ (con $n\geq 1$ e $m_i \geq 1$), $l_{i, j}$ è un letterale.
Questa formula è la duale della DNF, cioè, rispetto a quest’ultima, vengono scambiati i ruoli della congiunzione e della disgiunzione.