Forma normale congiuntiva

Questa pagina sull'argomento matematica sembra trattare argomenti unificabili alla pagina Forma canonica (algebra di Boole).

---

Puoi contribuire unendo i contenuti in una pagina unica. Commenta la procedura di unione usando questa pagina di discussione. Segui i suggerimenti del progetto di riferimento.

Questa voce o sezione sull'argomento logica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Questa voce sull'argomento logica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

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.