Forma normale congiuntiva

Da Wikipedia, l'enciclopedia libera.

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:

\bigwedge_{j=1}^n \left( \bigvee_{k=1+j}^{m(j)} L_{j,k-j} \right)

n : Numero di clausole.

m(i) : Numero di letterali della clausola i-esima.

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[modifica | modifica sorgente]

Le seguenti formule sono in CNF:

(\neg A \vee B) \wedge (B \vee C)
(A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E)
(\neg B \vee C)
(\neg B \vee C) \wedge A
A \wedge B

L'ultima formula ha due clausole, entrambe con un solo letterale.

Da notare che formule come l'ultima, ossia del tipo A_1 \vee A_2 \vee ... \vee A_n (o similmente A_1 \wedge A_2 \wedge ... \wedge A_n) dove A_i sono letterali, sono da considerarsi simultaneamente DNF e CNF.

Voci correlate[modifica | modifica sorgente]

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