Forma canonica (algebra di Boole)

Da Wikipedia, l'enciclopedia libera.

La forma canonica, o forma normale di una funzione booleana è un modello di rappresentazione di un'espressione booleana ricavabile dall'analisi della propria tabella di verità.

Data una funzione booleana, esistono due tipi di forme canoniche:

  • prima forma canonica o forma disgiuntiva, detta anche S.O.P. (sum of products, somma di prodotti), costruita come somme di prodotti fondamentali, cioè da termini che comprendono tutte le variabili della funzione, in forma vera o negata, detti mintermini, in corrispondenza dei valori di uscita della funzione uguali a 1. Essa si può scrivere in generale per n variabili:
f(x_0, \dots, x_{n-1}) = \sum_{i = 0}^{2^n - 1} f(i) \cdot P_i

dove P_i rappresenta i mintermini (indicati anche con m_i), cioè i prodotti fondamentali, e f(i) rappresenta il valore di uscita della funzione in corrispondenza dell'i-esima riga. Per esempio, con tre variabili A,B,C:

f(A,B,C) = (A \cdot B \cdot C) + (A \cdot B \cdot \overline C) + (A \cdot \overline B \cdot C) + (A \cdot \overline B \cdot \overline C) + (\overline A \cdot B \cdot C) + (\overline A \cdot B \cdot \overline C) + (\overline A \cdot \overline B \cdot C) + (\overline A \cdot \overline B \cdot \overline C)
  • seconda forma canonica o forma congiuntiva, detta anche P.O.S. (product of sums, prodotto di somme), costruita da prodotti di somme fondamentali, cioè da termini che comprendono tutte le variabili della funzione, in forma vera o negata, detti maxtermini, in corrispondenza dei valori di uscita della funzione uguali a 0. Anch'essa si può generalizzare ad n variabili:
f(x_0, \dots, x_{n-1}) = \prod_{i=0}^{2^n - 1} \left (f(i) + S_i \right)

dove S_i rappresenta i maxtermini (indicati anche con M_i), cioè le somme fondamentali, ed f(i) rappresenta il valore di uscita della funzione in corrispondenza dell'i-esima riga. Per esempio, con tre variabili A,B,C:

f(A,B,C) = (A + B + C) \cdot (A + B + \overline C) \cdot (A + \overline B + C) \cdot (A + \overline B + \overline C) \cdot (\overline A + B + C) \cdot (\overline A + B + \overline C) \cdot (\overline A + \overline B + C) \cdot (\overline A + \overline B + \overline C)

Usando la tabella della verità:

numero ABC Mintermini Maxtermini
0 000 \overline A \cdot \overline B \cdot \overline C A + B + C
1 001 \overline A \cdot \overline B \cdot C A + B + \overline C
2 010 \overline A \cdot B \cdot \overline C A + \overline B + C
3 011 \overline A \cdot B \cdot C A + \overline B + \overline C
4 100 A \cdot \overline B \cdot \overline C \overline A + B + C
5 101 A \cdot \overline B \cdot C \overline A + B + \overline C
6 110 A \cdot B \cdot \overline C \overline A + \overline B + C
7 111 A \cdot B \cdot C \overline A + \overline B + \overline C

Prima forma canonica[modifica | modifica wikitesto]

La prima forma canonica, S.O.P., si può ricavare direttamente dalla tabella di verità di una funzione. Per esempio, consideriamo una funzione di tre variabili f(A, B, C) la cui tabella di verità sia ad esempio:

A B C f(A, B, C)
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Dobbiamo prendere in considerazione i valori della funzione pari a 1, quindi la prima, quarta, settima e ottava riga, che corrisponde ai valori delle variabili presi in forma vera e negata:

f(A,B,C)= (\overline A \cdot \overline B \cdot \overline C) + (\overline A \cdot B \cdot C) + (A \cdot B \cdot \overline C) + (A \cdot B \cdot C)

Un altro modo è quello di usare il Teorema di Shannon.

Non facciamo altro che prendere la funzione ricavata dallo sviluppo del teorema di Shannon e sostituiamo i valori come f(0,0) con il reale valore che la funzione assume nella tabella di verità. In questa caso avremmo: f(A,B)=A'B'*0+A'B*0+AB*0+AB*1

f(A,B)=AB

Se i casi in cui la funzione assume due volte valore 1 non c'è nessun problema in quanto uno dei tre zeri della funzione trovata diventa uno e quindi rimane il termine per cui la funzione risulta 1.

Nel caso in cui non volessimo usare il Teorema di Shannon basta prendere le righe della tabella in cui la funzione assume 1 come valore e andare a vedere se le variabili sono naturali o complementate (naturali quando e.s. A=1 o B=1 e complementate quando e.s. A=0 o B=0) e quindi scrivere la f utilizzando la dicitura A se naturale o A' se complementata.

Esempio

A B f(A,B)
0 1 1

A=0, B=1

f(A,B)=\overline A \cdot B

In questo caso se la funzione assume più di una volta il valore 1 basterà aggiungere attraverso una somma l'altro mintermine utilizzando sempre il procedimento di prima per ricavarlo.

Seconda forma canonica[modifica | modifica wikitesto]

La seconda forma canonica viene ricavata attraverso l'analisi della tabella di verità, ma in modo duale rispetto al metodo adottato nella prima forma canonica.

Dalla tabella di verità prendiamo quindi le righe in cui la funzione assume valore 0, controlliamo se le variabili sono naturali o complementate, dopodiché scriviamo la funzione f sommando tra di loro le variabili utilizzando la dicitura \overline A se naturale e A se complementata (diversamente da quella utilizzata nella prima forma canonica); se la funzione assume più volte il valore 0 i mintermini devono essere divisi da un prodotto. Ad esempio:

A B f(A,B)
0 0 0
0 1 1
1 0 0
1 1 0

f(A,B)=(A + B)(\overline A + B)(\overline A + \overline B)

ove A + B è determinato dalla 1ª riga, \overline A + B è determinato dalla 3ª riga e \overline A + \overline B è determinato dall'ultima riga.

Altre caratteristiche[modifica | modifica wikitesto]

In tale forma una clausola agisce come un vincolo sui possibili valori che le variabili che la compongono possono avere. Ad esempio la clausola (A OR ~B OR C) è soddisfatta da tutti gli assegnamenti FALSE-TRUE possibili tranne che A = C = FALSE e B = TRUE. Una formula in CNF può, inoltre, essere vista come un sistema di vincoli nello spazio degli assegnamenti binari delle sue variabili. Per estendere questo concetto è utile notare l'esistenza di un altro tipo di "sistema di vincoli", come i sistemi di disequazioni lineari su variabili reali o intere che individuano una regione ammissibile (e quindi degli assegnamenti ammissibili) in programmazione lineare e programmazione lineare intera. La regione ammissibile di una formula CNF contiene precisamente quei valori che rendono la formula valutabile come TRUE.

Voci correlate[modifica | modifica wikitesto]