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:
: Numero di clausole.
: Numero di letterali della clausola i-esima.
: È 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:
L'ultima formula ha due clausole, entrambe con un solo letterale.
Da notare che formule come l'ultima, ossia del tipo (o similmente ) dove 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.