Forma canonica: differenze tra le versioni

Versione delle 18:33, 9 dic 2008

Versione attuale delle 19:43, 19 set 2023

(31 versioni intermedie di 22 utenti non mostrate)

Riga 1:

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

{{C|spiegare meglio, poco chiaro|matematica|dicembre 2007}}

{{F|matematica|luglio 2017}}

La '''forma canonica''' o '''funzione canonica''' deriva dalla necessità di ricavare una funzione dalla [[tabella della verità]].

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

Esistono due tipi di funzioni canoniche: (il simbolo ' dopo la variabile indica la negazione della stessa, es. A' = A negato)

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.

* Dati i [[mintermine|mintermini]]: sono termini che comprendono tutte le variabili di una funzione, in forma negata o diretta, e le mettono in relazione [[Algebra di Boole#AND|AND]] fra loro. Per esempio a tre variabili (A,B,C):

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

::(A.B.C) (A.B.C') (A.B'.C) (A.B'.C') (A'.B.C) (A'.B.C') (A'.B'.C) (A'.B'.C')

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

:Sono '''funzioni canoniche disgiuntive''' le funzioni ottenute usando esclusivamente mintermini in relazione [[Algebra di Boole#OR|OR]] fra loro. Per esempio:

::Q=(A'.B.C)+(A.B.C')+(A'B'C')+(A.B.C)

== Alcune forme canoniche ==

* Dati i [[maxtermine|maxtermini]]: sono termini che comprendono tutte le variabili di una funzione, in forma negato o diretta, e le mettono in relazione [[Algebra di Boole#OR|OR]] fra loro. Per esempio a tre variabili (A,B,C):

::(A+B+C) (A+B+C') (A+B'+C) (A+B'+C') (A'+B+C) (A'+B+C') (A'+B'+C) (A'+B'+C')

:Sono '''funzioni canoniche congiuntive''' le funzioni ottenute usando esclusivamente maxtermini in relazione [[Algebra di Boole#AND|AND]] fra loro. Per esempio:

::Q= (A+B+C).(A+B+C').(A'+B'+C).(A+B'+C)

=== Algebra booleana ===

Usando la tabella della verità:

{{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.

Valore decimale: A B C: Mintermini: Maxtermini:

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

0 000 A'.B'.C' A+B+C

1 001 A'.B'.C A+B+C'

2 010 A'.B.C' A+B'+C

3 011 A'.B.C A+B'+C'

4 100 A.B'C' A'+B+C

5 101 A.B'.C A'+B+C'

6 110 A.B.C' A'+B'+C

7 111 A.B.C A'+B'+C'

=== Algebra lineare ===

Le funzioni canoniche si dividono in due forme: Prima e Seconda Forma Canonica.

* [[Matrice diagonale]]

* [[Forma canonica di Jordan]]

==1°= formaPolinomi canonica===

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

== Note ==

La Prima forma canonica può essere ricavata utilizzando due diversi procedimenti, il primo che riguarda l'uso del [[teorema di Shannon]] e il secondo attraverso l'analisi di una qualsiasi tabella della verità.

<references/>

== Collegamenti esterni ==

Dallo svolgimento del Teorema di Shannon per una funzione a 2 variabili (in questo caso A,B) si ricava la seguente scrittura:

* {{Collegamenti esterni}}

{{Portale|matematica}}

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

[[Categoria:Algebra]]

a cui poi sostituendo i valori di <math>f</math> che troviamo nella tabella di verità otteniamo la cosiddetta forma ''SOP'' o ''Sum of Product'' o ''Prima forma canonica''.

Es.

Se avessimo una tabella della verità simile a questa:

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

|}

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.

==2° 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:规范形式 (布尔代数)]]