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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]Collegamenti esterni
[modifica | modifica wikitesto]- forma normale congiuntiva, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
- (EN) conjunctive normal form, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.