Forma normale congiuntiva

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

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

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 CNF ha quindi la seguente struttura:

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

${\displaystyle n}$ : Numero di clausole.

${\displaystyle m(i)}$ : Numero di letterali della clausola i-esima.

${\displaystyle 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:

${\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 ...\vee A_{n}}$ (o similmente ${\displaystyle A_{1}\wedge A_{2}\wedge ...\wedge A_{n}}$) dove ${\displaystyle A_{i}}$ sono letterali, sono da considerarsi simultaneamente DNF e CNF.

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.

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