Forma normale congiuntiva

Nella logica booleana, una formula è in forma normale congiuntiva o congiunta (FNC), indicata anche come CNF (acronimo di Conjunctive Normal Form) se è una congiunzione di clausole, dove le clausole sono una disgiunzione di letterali. Una formula in FNC ha quindi la seguente struttura:

${\displaystyle \bigwedge _{i=1}^{n}\left(\bigvee _{k=1}^{m(i)}L_{i,k}\right),}$

dove ${\displaystyle n}$ è il numero di clausole, ${\displaystyle m(i)}$ è il numero di letterali della clausola ${\displaystyle i}$-esima e ${\displaystyle L_{i,k}}$ è il ${\displaystyle k}$-esimo letterale della ${\displaystyle i}$-esima clausola. Un letterale può essere una variabile booleana (cioè che può valere solo 0 o 1, vero o falso) o la negazione di una variabile.

Una funzione booleana è una funzione che ha in ingresso diversi valori booleani (cioè vero/falso oppure 1/0) e come risultato ha un valore booleano. Per ogni funzione booleana, esiste una formula in forma normale congiuntiva che produce come risultato gli stessi valori.

Esempi

Le seguenti formule sono in FNC:

${\displaystyle (\neg A\vee B)\wedge (B\vee C);}$

${\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E);}$

${\displaystyle (\neg B\vee C);}$

${\displaystyle (\neg B\vee C)\wedge A;}$

${\displaystyle A\wedge B.}$

L'ultima formula ha due clausole, entrambe con un solo letterale.

Da notare che formule come l'ultima, ossia del tipo ${\displaystyle A_{1}\vee A_{2}\vee \ldots \vee A_{n}}$ (o similmente ${\displaystyle A_{1}\wedge A_{2}\wedge \ldots \wedge A_{n}}$) dove ${\displaystyle A_{i}}$ sono letterali, sono da considerarsi simultaneamente FND e FNC.

Voci correlate

• Forma normale disgiuntiva
• Forma canonica (algebra di Boole)
• Forma normale negativa
• Clausola di Horn

Collegamenti esterni

• forma normale congiuntiva, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) conjunctive normal form, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.