Associatività

Questo articolo è relativo all'associatività in matematica, per l''associatività nell'architettura a memoria cache per le CPU, vedi cache CPU.

In matematica, l'associatività (o proprietà associativa) e una proprietà che può avere una operazione binaria. Significa che l'ordine di valutazione è irrilevante se l'operazione appare più di una volta in una espressione. Detta in altro modo, non sono richieste parentesi per un'operazione associativa. Si consideri ad esempio l'uguaglianza

(5+2)+1 = 5+(2+1)

Sommando 5 e 2 si ottiene 7, e sommando 1 si ottiene il risultato 8 per il membro a sinistra. Per valutare il membro a destra, si inizia a sommare 2 e 1 ottenendo 3, e quindi si somma 3 e 5 per ottenere 8 ancora. Quindi l'uguaglianza è verificata. Di fatto è verificata per tutti i numeri reali, non solo per 5, 2, e 1. Diciamo che "l'addizione nell'insieme dei numeri reali è un'operazione associativa".

Le operazioni associative sono frequenti in matematica, e infatti molte strutture algebriche richiedono esplicitamente che le loro operazioni binarie siano associative. Tuttavia, molte operazioni importanti non sono associative; un esempio comune è il prodotto vettoriale.

Definizione

Formalmente, un'operazione binaria $*$ su un insieme S è detta associativa se soddisfa la legge associativa:

(x*y)*z=x*(y*z)\qquad\mbox{per ogni }x,y,z\in S.

L'ordine di valutazione non influisce sul valore di tale espressione, e si dimostra che lo stesso vale per le espressioni che contengono un numero arbitrario di operazioni

*

. Quindi, quando

*

è associativa, l'ordine di valutazione può essere lasciato non specificato senza causare ambiguità, omettendo le parentesi e scrivendo semplicemente:

x*y*z.

Esempi

Seguono alcuni esempi di operazioni associative.

In aritmetica, l'addizione e la moltiplicazione di numeri reali sono associative, cioè,

\left. \begin{matrix} (x+y)+z=x+(y+z)=x+y+z\quad \\ (x\,y)z=x(y\,z)=x\,y\,z\qquad\qquad\qquad\quad\ \ \, \end{matrix} \right\} \mbox{per ogni }x,y,z\in\mathbb{R}.

L'addizione e la moltiplicazione dei numeri complessi e dei quaternioni è associativa. La somma degli ottonioni è ancora associativa, ma la moltiplicazione degli ottonioni non è associativa.

Le funzioni massimo comun divisore e minimo comune multiplo agiscono associativamente:

\left.
    \begin{matrix}
     \operatorname{M.C.D.}(\operatorname{M.C.D.}(x,y),z)=
     \operatorname{M.C.D.}(x,\operatorname{M.C.D.}(y,z))=
     \operatorname{M.C.D.}(x,y,z)\ \quad
    \\
     \operatorname{m.c.m.}(\operatorname{m.c.m.}(x,y),z)=
     \operatorname{m.c.m.}(x,\operatorname{m.c.m.}(y,z))=
     \operatorname{m.c.m.}(x,y,z)\quad
    \end{matrix}
   \right\}\mbox{ per ogni }x,y,z\in\mathbb{Z}.

La moltiplicazione di matrici è associativa. Poichè le trasformazioni lieari possono essere rappresentate da matrici, si può immediatamente concludere che le trasformazioni lineari si compongono associativamente.

L'intersezione e l'unione di insiemi:

\left. \begin{matrix} (A\cap B)\cap C=A\cap(B\cap C)=A\cap B\cap C\quad \\ (A\cup B)\cup C=A\cup(B\cup C)=A\cup B\cup C\quad \end{matrix} \right\}\mbox{per tutti gli insiemi }A,B,C.

Se M è un dato insieme e S indica l'insieme di tutte le funzioni da M a M, allora l'operazione di composizione di funzioni su S è associativa:

(f\circ g)\circ h=f\circ(g\circ h)=f\circ g\circ h\qquad\mbox{per ogni }f,g,h\in S.

Leggermente più in generale, dati quattro insiemi M, N, P e Q, con h: M a N, g: N a P, e h: P a Q, allora

(f\circ g)\circ h=f\circ(g\circ h)=f\circ g\circ h

come prima. In breve, la composizione di mappe è sempre associativa.

Non associatività

Un'operazione binaria $*$ su un insieme S che non soddisfa la legge associativa è detta non associativa. In simboli,

(x*y)*z\ne x*(y*z)\qquad\mbox{per qualche }x,y,z\in S.

Per tale operazione l'ordine di valutazione è importante. La sottrazione, la divisione e l'esponenziazione sono esempi ben noti di operazioni non associative:

\begin{matrix} (5-3)-2\ne 5-(3-2)\quad \\ (4/2)/2\ne 4/(2/2)\qquad\qquad \\ 2^{(1^2)}\ne (2^1)^2.\quad\qquad\qquad \end{matrix} In generale, le parentesi devono essere usate per indicare l'ordine di valutazione, se un'operazione non associativa appare più di una volta in un'espressione. Tuttavia i matematici si accordano su un particolare ordine di valutazione per molte operazioni non associative comuni. Questa è una convenzione, e non una verità matematica.

Una operazione associativa a sinistra è un'operazione non associativa che viene valutata convenzionalmente da sinistra a destra, cioè,

\left. \begin{matrix} x*y*z=(x*y)*z\qquad\qquad\quad\, \\ w*x*y*z=((w*x)*y)*z\quad \\ \mbox{etc.}\qquad\qquad\qquad\qquad\qquad\qquad\ \ \, \end{matrix} \right\} \mbox{per ogni }w,x,y,z\in S mentre un'operazione associativa a destra è valutata convenzionalmente da destra a sinistra:

\left. \begin{matrix} x*y*z=x*(y*z)\qquad\qquad\quad\, \\ w*x*y*z=w*(x*(y*z))\quad \\ \mbox{etc.}\qquad\qquad\qquad\qquad\qquad\qquad\ \ \, \end{matrix} \right\} \mbox{per ogni }w,x,y,z\in S Esistono sia operazioni associative a sinistra che operazioni associative a destra; sotto sono dati alcuni esempi.

Altri esempi

Le operazioni associative a sinistra includono:

Sottrazione e divisione di numeri reali:

x-y-z=(x-y)-z\qquad\mbox{per ogni }x,y,z\in\mathbb{R};

x/y/z=(x/y)/z\qquad\qquad\quad\mbox{per ogni }x,y,z\in\mathbb{R}\mbox{ con }y\ne0,z\ne0.

Le operazioni associative a destra includono le seguenti:

Esponenziazione di numeri reali:

x^{y^z}=x^{(y^z)}.

La ragione per cui l'esponenziazione è associativa a destra è che un'esponenziazione associativa a sinistra ripetuta sarebbe meno pratica. Le ripetizioni multiple possono (e vengono) riscritte con il simbolo di moltiplicazione:

(x^y)^z=x^{(yz)}.

l'operatore di assegnazione in molti linguaggi di programmazione è associativo a destra, ad esempio nel caso del linguaggio C.

x = y = z; significa x = (y = z); a non (x = y) = z;

In altre parole, l'istruzione assegna il valore di z sia a x che a y.

Operazioni non associative per cui non è stato definito nessun ordine convenzionale di valutazione includono le seguenti:

Prendere la media di numeri reali:

{(x+y)/2+z\over2}\ne{x+(y+z)/2\over2}\ne{x+y+z\over3}\qquad\mbox{per qualche }x,y,z\in\mathbb{R}.

Prendere il complemento relativo di insiemi:

(A\backslash B)\backslash C\ne A\backslash (B\backslash C)\qquad\mbox{per qualche insieme }A,B,C.

Voci correlate

Un semigruppo è un insieme dotato di un'operazione binaria associativa.
Commutatività e distributività sono altre due proprietà delle operazioni binarie frequentemente discusse.
Associatività della potenza e alternatività sono forme deboli di associatività.

Algebra elementare | Nozioni algebriche generali

Gourt Home::Gourt :: Associatività

Definizione

Esempi

Non associatività

Altri esempi

Voci correlate