Forma normale congiuntiva
# 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 CNF ha quindi la seguente struttura:

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

$n$ : Numero di clausole.

$m(i)$ : Numero di letterali della clausola i-esima.

$L_{i,k}$ : È il k-esimo letterale della 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 CNF:

    $(\neg A\vee B)\wedge (B\vee C)$
    $(A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E)$
    $(\neg B\vee C)$
    $(\neg B\vee C)\wedge A$
    $A\wedge B$

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

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

