Forma canonica (algebra di Boole)

Voce principale: Forma canonica.

Questa pagina sull'argomento matematica sembra trattare argomenti unificabili alle pagine Forma normale congiuntiva e Forma normale disgiuntiva.

Commento: che possono confluire qui

Questa voce o sezione sull'argomento matematica è priva o carente di note e riferimenti bibliografici puntuali.

Una forma canonica, detta anche forma normale, di una funzione booleana è una particolare espressione rappresentativa della funzione caratterizzata dall'essere una forma minima, standard e ricavabile sistematicamente utilizzando l'algoritmo di Quine-McCluskey.^[1]

Per ogni funzione booleana di ${\displaystyle n}$ variabili esistono due forme canoniche:

• la prima forma canonica, detta anche forma normale disgiuntiva o somma di prodotti, che si presenta come la sommatoria dei mintermini associati alla funzione. Ovvero la somma di tutti quei prodotti logici che risultano affermati ciascuno per una particolare permutazione degli argomenti della funzione, e solo per quelle permutazioni la cui immagine è l'elemento vero.

• la seconda forma canonica, detta anche forma normale congiuntiva o prodotto di somme, che si presenta come la produttoria dei maxtermini associati alla funzione. Ovvero il prodotto di tutte quelle somme logiche che risultano negate ciascuna per una particolare permutazione degli argomenti della funzione, e solo per quelle permutazioni la cui immagine è l'elemento falso.

Per esempio data la funzione ${\displaystyle y=f(a,b,c)}$ espressa dalla seguente tabella di verità, corredata dai mintermini e maxtermini associati:

A	B	C	Y	mintermine	maxtermine
0	0	0	0	-	${\displaystyle a+b+c}$
0	0	1	0	-	${\displaystyle a+b+{\bar {c}}}$
0	1	0	1	${\displaystyle {\bar {a}}\cdot b\cdot {\bar {c}}}$	-
0	1	1	1	${\displaystyle {\bar {a}}\cdot b\cdot c}$	-
1	0	0	0	-	${\displaystyle {\bar {a}}+b+c}$
1	0	1	0	-	${\displaystyle {\bar {a}}+b+{\bar {c}}}$
1	1	0	1	${\displaystyle a\cdot b\cdot {\bar {c}}}$	-
1	1	1	1	${\displaystyle a\cdot b\cdot c}$	-

è possibile ricavare le espressioni somma di prodotti e prodotto di somme associate alla funzione semplicemente applicando le definizioni:

• ${\displaystyle f(a,b,c)=({\bar {a}}\cdot b\cdot {\bar {c}})+({\bar {a}}\cdot b\cdot c)+(a\cdot b\cdot {\bar {c}})+(a\cdot b\cdot c)}$
• ${\displaystyle f(a,b,c)=(a+b+c)\cdot (a+b+{\bar {c}})\cdot ({\bar {a}}+b+c)\cdot ({\bar {a}}+b+{\bar {c}})}$

Queste due espressioni non sono tuttavia forme canoniche poiché non sono minime. Infatti applicando l'algoritmo di Quine-McCluskey è possibile individuare alcuni termini ridondanti e che quindi possono essere accorpati. Si ricavano quindi le seguenti espressioni minimizzate:

• ${\displaystyle f(a,b,c)=({\bar {a}}\cdot b)+(a\cdot b)}$
• ${\displaystyle f(a,b,c)=(a+b)\cdot ({\bar {a}}+b)}$

che sono le due forme canoniche della funzione ${\displaystyle f}$.

• M. Morris Mano, Charles R. Kime e Tom Martin, Reti logiche, a cura di Antonio Gentile, Filippo Sorbello e Salvatore Vitabile, traduzione di Silvia Franchini, et al., 5ª ed., Milano - Torino, Pearson, 2019, ISBN 978-88-919-0581-9.

• Mintermine
• Maxtermine
• Mappa di Karnaugh
• Metodo di Quine-McCluskey
• Algebra di Boole
• Rete logica

Portale Elettronica

Portale Informatica

Portale Matematica