Forma canonica: differenze tra le versioni

Versione delle 17:53, 14 dic 2008

Versione attuale delle 19:43, 19 set 2023

(25 versioni intermedie di 20 utenti non mostrate)

Riga 1:

{{nota disambigua|il concetto dell'algebra di Boole|Forma canonica (algebra di Boole)}}

{{WIP|Tridim}}

{{C|spiegare meglio, poco chiaroF|matematica|dicembreluglio 20072017}}

In [[matematica]] la '''forma canonica''' di un oggetto è una maniera uniforme utilizzata per descriverlo in modo unico<ref name="definizione">{{Treccani|forma-canonica}}</ref>, {{chiarire|salvo una [[relazione di equivalenza]].}}

== Definizione ==

La '''forma canonica''' o '''funzione canonica''' di una espressione booleana è un'espressione logica contenente tutte le variabili booleane in forma vera o negata, in forma di prodotti fondamentali o somme fondamentali di essi. Essa si ricava dalla [[tabella della verità]].

Una forma canonica per un insieme di oggetti dotato di una relazione di equivalenza è la scelta di un unico elemento (detto "in forma canonica") per ogni [[classe di equivalenza]]; ogni oggetto appartiene ad una classe e la sua forma canonica è il rappresentante scelto per quella classe.

Una forma canonica può essere una semplice convenzione (come la [[Rappresentazione matriciale delle coniche#Riduzione di una conica a forma canonica|forma canonica di una conica]]), oppure può essere il risultato di un teorema più profondo (come la [[forma canonica di Jordan]] per le [[matrici]]): essa classifica infatti tutte le classi di equivalenza di un insieme, fornendo un rappresentante per ciascuna.

Tramite la forma canonica per verificare l'equivalenza tra due oggetti basta confrontare le loro forme canoniche: essi sono equivalenti se e solo se hanno la stessa forma canonica.

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

In termini pratici può tuttavia essere un problema trovare la forma canonica di un oggetto fissato.

Ciononostante, l'impiego della forma canonica può rendere più semplice trattare con la relazione di equivalenza.

== Alcune forme canoniche ==

* '''forma disgiuntiva''', detta anche S.O.P. (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 [[Mintermine|mintermini]], in corrispondenza ai valori della funzione che sono 1. Essa si può scrivere in generale per n variabili:

=== Algebra booleana ===

:<math>f(x_0, \dots, x_{n-1}) = \sum_{i = 0}^{2^n - 1} f(i) \cdot P_i</math>

{{vedi anche|Forma canonica (algebra di Boole)}}

In [[algebra booleana]] la forma canonica di una funzione è un [[polinomio]] espresso come somma di termini-prodotto oppure prodotto di termini-somma.

dove <math>P_i</math> sono i mintermini (indicati anche con <math>m_i</math>), cioè i prodotti fondamentali e <math>f(i)</math> sono i valori della funzione della i-esima riga che assume il valore 1. Per esempio a tre variabili A,B,C:

Per ogni [[funzione booleana]] è possibile calcolare una forma normale associata utilizzando l'[[algoritmo di Quine-McCluskey]].

=== Algebra lineare ===

:<math>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)</math>

* [[Matrice diagonale]]

* [[Forma canonica di Jordan]]

=== Polinomi ===

* '''forma congiuntiva''', detta anche P.O.S. (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 [[Maxtermine|maxtermini]], in corrispondenza ai valori della funzione che sono 0. Per n variabili si può scrivere:

Una forma canonica per i [[polinomio|polinomi]] in una variabile è con le potenze in ordine decrescente.

== Note ==

:<math>f(x_0, \dots, x_{n-1}) = \prod_{i=0}^{2^n - 1} \left (f(i) \cdot S_i \right)</math>

<references/>

== Collegamenti esterni ==

dove <math>S_i</math> sono i maxtermini (indicati anche con <math>M_i</math>), cioè le somme fondamentali ed <math>f(i)</math> sono i valori della funzione della i-esima riga che assume il valore 0. Per esempio a tre variabili A,B,C:

* {{Collegamenti esterni}}

{{Portale|matematica}}

:<math>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)</math>

[[Categoria:Algebra]]

Usando la tabella della verità:

{| border=1 cellspacing=0

! numero !! ABC !! Mintermini !! Maxtermini

|-

! 0 || 000 || <math>\overline A \cdot \overline B \cdot \overline C</math> || <math>A + B + C</math>

|-

! 1 || 001 || <math>\overline A \cdot \overline B \cdot C</math> || <math>A + B + \overline C</math>

|-

! 2 || 010 || <math>\overline A \cdot B \cdot \overline C</math> || <math>A + \overline B + C</math>

|-

! 3 || 011 || <math>\overline A \cdot B \cdot C</math> || <math>A + \overline B + \overline C</math>

|-

! 4 || 100 || <math>A \cdot \overline B \cdot \overline C</math> || <math>\overline A + B + C</math>

|-

! 5 || 101 || <math>A \cdot \overline B \cdot C</math> || <math>\overline A + B + \overline C</math>

|-

! 6 || 110 || <math>A \cdot B \cdot \overline C</math> || <math>\overline A + \overline B + C</math>

|-

! 7 || 111 || <math>A \cdot B \cdot C</math> || <math>\overline A + \overline B + \overline C</math>

|}

== Prima forma canonica ==

La Prima forma canonica, S.O.P., si può ricavare direttamene dalla tabella della verità di una funzione. Consideriamo una funzione di tre variabili <math>f(A, B, C)</math> la cui tabella della verità sia ad esempio:

{| class=wikitable style="font-size:95%"

!A !B !C !<math>f(A, B, C)</math>

|-

|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:

:<math>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</math>

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 <math>f(0,0)</math> con il reale valore che la funzione assume nella tabella di verità.

In questa caso avremmo:

<math>f(A,B)=A'B'*0+A'B*0+AB'*0+AB*1</math>

<math>f(A,B)=AB</math>

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 <math>f</math> utilizzando la dicitura A se naturale o A' se complementata.

Es.

{| class=wikitable style="font-size:95%"

!A

!B

!<math>f(A,B)</math>

|-

|0

|1

|1

|}

A=0, B=1

<math>f(A,B)=A'B</math>

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 ==

La Seconda forma canonica viene ricava attraverso l'analisi della tabella della verità ma in modo duale rispetto al metodo adottato nella prima forma canonica.

Questo significa quindi che dalla tabella della verità noi prendiamo le righe in cui la funzione assume valore 0, vediamo se le variabili sono ''naturali'' o ''complementate'', dopodiché scriviamo la funzione <math>f</math> sommando tra di loro le variabili utilizzando la dicitura A' se naturale e A se complementata (N.B.: questa scrittura è ben diversa da quella utilizzata nella prima forma canonica); se la funzione assume più volte il valore 0 i mintermini devono essere divisi da una moltiplicazione, da questo deriva il termine ''POS'' o ''Product of Sum'' o ''Seconda Forma Canonica''.

Es

{| class=wikitable style="font-size:95%"

!A

!B

!<math>f(A,B)</math>

|-

|0

|0

|0

|-

|0

|1

|1

|-

|1

|0

|0

|-

|1

|1

|0

|}

<math>f(A,B)=(A+B)(A'+B)(A'+B')</math>

dove ''A+B'' è della 1° riga, ''A'+B'' è della 3° riga, ''A'+B''' è della 4° riga.

[[Categoria:Algebra di Boole]]

[[Categoria:Elettronica digitale]]

[[ar:الأشكال العادية للجبر المنطقي]]

[[en:Canonical form (Boolean algebra)]]

[[th:รูปแบบบัญญัติ (พีชคณิตแบบบูล)]]

[[zh:规范形式 (布尔代数)]]