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 Teknopedia.

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.

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.

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

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

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica