Asociatividad (álgebra)

La asociatividad es una propiedad en el álgebra y la lógica proposicional que se cumple, si dados tres o más elementos cualquiera de un conjunto determinado, se verifica que existe una operación: $\circledcirc$ , que cumpla la igualdad:

a\circledcirc (b\circledcirc c)=(a\circledcirc b)\circledcirc c

Es decir, en una expresión asociativa con dos o más ocurrencias seguidas de un mismo operador asociativo, el orden en que se ejecuten las operaciones no altera el resultado, siempre y cuando se mantenga intacta la secuencia de los operandos. En otras palabras, reorganizar los paréntesis en una expresión asociativa no cambia su valor final.

La suma y el producto de números reales cumplen la propiedad asociativa, siendo válidas las igualdades:

a+(b+c)=(a+b)+c

para la suma y para la multiplicación:

a\cdot (b\cdot c)=(a\cdot b)\cdot c

En ambas, la ubicación de los paréntesis no altera el resultado. Nótese que los operandos se han mantenido en su posición original dentro de la expresión. Muchas operaciones importantes son no asociativas, por ejemplo la resta y la exponenciación. Las expresiones que contienen tanto operaciones asociativas como operaciones no asociativas dan como resultado expresiones no asociativas.

No se debe confundir la asociatividad con la conmutatividad, la cual establece que sí se puede cambiar el orden de los operandos sin afectar el resultado final.

Dentro de una expresión que contenga dos o más apariciones seguidas del mismo operador asociativo, el orden en que se realicen las operaciones no importa siempre que no se cambie la secuencia de los operandos. Es decir (después de reescribir la expresión con paréntesis y en notación infija si es necesario), reordenar los paréntesis en dicha expresión no cambiará su valor. Consideremos las siguientes ecuaciones:

${\begin{aligned}(2+3)+4&=2+(3+4)=9\,\\2\times (3\times 4)&=(2\times 3)\times 4=24.\end{aligned}}$

Aunque los paréntesis se han reordenado en cada línea, los valores de las expresiones no se han alterado. Dado que esto es cierto cuando se realiza la suma y la multiplicación de cualquier número real, se puede decir que "la suma y la multiplicación de números reales son operaciones asociativas".

La asociatividad no es lo mismo que la conmutatividad, que se refiere a si el orden de dos operandos afecta al resultado. Por ejemplo, el orden no importa en la multiplicación de números reales, es decir, $a$ × b = b × a}}, por lo que decimos que la multiplicación de números reales es una operación conmutativa. Sin embargo, operaciones como la composición de funciones y la multiplicación de matrices son asociativas, pero (generalmente) no conmutativas.

Las operaciones asociativas son abundantes en matemáticas; de hecho, muchas estructuras algebraicas (como semigrupos y categorías) requieren explícitamente que sus operaciones binarias sean asociativas.

Sin embargo, muchas operaciones importantes e interesantes no son asociativas; algunos ejemplos son la resta, la exponenciación y el producto vectorial cruzado. En contraste con las propiedades teóricas de los números reales, la suma de números de coma flotante en informática no es asociativa, y la elección de cómo asociar una expresión puede tener un efecto significativo en el error de redondeo.

Definición

Una operación binaria ∗ sobre el conjunto S es asociativa cuando este diagrama conmuta. Es decir, cuando los dos caminos de

S \times S \times S

a

S

componen a la misma función desde

S \times S \times S

a

S

.

Formalmente, una operación binaria $*$ sobre un set $S$ se llama asociativa si satisface la ley asociativa:

$(x * y) * z = x * (y * z)$ para todo $x$ , $y$ , $z$ en $S$ .}}

Aquí, ∗ se utiliza para sustituir el símbolo de la operación, que puede ser cualquier símbolo, e incluso la ausencia de símbolo (yuxtaposición) como para la multiplicación.

$(x y) z = x (y z) = x y z$ para todo $x$ , $y$ , $z$ en $S$ .}}

La ley asociativa también puede expresarse así en notación funcional: $f (f (x, y), z) = f (x, f (y, z))$ .

Ley asociativa generalizada

En ausencia de la propiedad asociativa, cinco factores

a

,

b

,

c

,

d

,

e

resultan en una red Tamari de orden cuatro, posiblemente productos diferentes.

Si una operación binaria es asociativa, la aplicación repetida de la operación produce el mismo resultado independientemente de cómo se inserten los pares de paréntesis válidos en la expresión.^[1] es unívoco; es decir, se obtendrá el mismo elemento independientemente de cómo se inserten los paréntesis en el producto. A esto se le llama ley asociativa generalizada. Por ejemplo, un producto de cuatro elementos puede escribirse, sin cambiar el orden de los factores, de cinco formas posibles:

$((a b) c) d$
$(a b)(c d)$
$(a (b c)) d$
$a ((b c) d)$
$a (b (c d))$

Si la operación producto es asociativa, la ley asociativa generalizada dice que todas estas expresiones darán el mismo resultado. Así que, a menos que la expresión con paréntesis omitido ya tenga un significado diferente (véase más adelante), los paréntesis pueden considerarse innecesarios y "el" producto puede escribirse sin ambigüedad como

$a b c d$ .

A medida que aumenta el número de elementos, el número de formas posibles de insertar paréntesis crece rápidamente, pero siguen siendo innecesarios para la desambiguación.

Un ejemplo en el que esto no funciona es el bicondicional lógico $\leftrightarrow$ Es asociativo; por tanto,

$A \leftrightarrow (B \leftrightarrow C)$ es equivalente a $(A \leftrightarrow B) \leftrightarrow C$ , pero $A \leftrightarrow B \leftrightarrow C$ más comúnmente significa {{math|(A ↔ B) y (B ↔ C), que no es equivalente.

Notación formal

Sea A un conjunto en el cual se ha definido una operación binaria interna $\circledcirc$ tal que

{\begin{array}{rccl}\circledcirc :&A\times A&\longrightarrow &A\\&(a,b)&\longmapsto &c=a\circledcirc b\end{array}}

Se dice que la operación $\circledcirc$ es asociativa si:

\forall a,b,c\in A\;:\quad a\circledcirc (b\circledcirc c)=(a\circledcirc b)\circledcirc c

La ley asociativa también puede ser expresada en notación funcional así:

f(f(x,y),z)=f(x,f(y,z))\,

Suma y resta

Partiendo del conjunto de los números naturales

\mathbb {N} =\{1,2,3,4,\dots \}

para la operación suma, definida como:

{\begin{array}{rccl}+:&\mathbb {N} \times \mathbb {N} &\longrightarrow &\mathbb {N} \\&(a,b)&\longmapsto &c=a+b\end{array}}

$(\mathbb {N} ,+)\,$ tiene la propiedad asociativa, dado que:

\forall a,b,c\in \mathbb {N} \;:\quad a+(b+c)=(a+b)+c

Por ejemplo:

5+(3+2)=(5+3)+2

Sin embargo, para la operación resta, definida como:

{\begin{array}{rccl}-:&\mathbb {N} \times \mathbb {N} &\longrightarrow &\mathbb {N} \\&(a,b)&\longmapsto &c=a-b\end{array}}

$(\mathbb {N} ,-)\,$ no tiene la propiedad asociativa, dado que:

\forall a,b,c\in \mathbb {N} \;:\quad a-(b-c)\neq (a-b)-c

Por ejemplo:

5-(3-2)\neq (5-3)-2

Ejemplos

La adición de números reales es asociativa.

La concatenación de las cadenas de caracteres "hola", " ", "mundo" se puede computar concatenando las primeras dos cadenas de caracteres (resultando en "hola ") y luego la tercera cadena de caracteres ("mundo"), o alternativamente, uniendo la segunda y tercera cadena de caracteres (resultando en " mundo") y concatenando la primera cadena de caracteres ("hola") con ese resultado. Los dos métodos producen el mismo resultado final. La concatenación de cadenas de caracteres es asociativa (pero no es conmutativa).
En aritmética, la adición y la multiplicación de números reales son asociativas. Debido a su asociatividad, la agrupación por paréntesis puede ser omitida sin ambigüedad. Esto es,

\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{para todo }}x,y,z\in \mathbb {R} .

Un ejemplo de la asociatividad de la suma es:

(2+3)+7=5+7=12\quad =\quad 2+(3+7)=2+10=12

y de la asociatividad de la multiplicación

(2\cdot 3)\cdot 7=6\cdot 7=42\quad =\quad 2\cdot (3\cdot 7)=2\cdot 21=42

Sin embargo, la resta no es asociativa,

2-(3-1)=0\quad \neq \quad (2-3)-1=-2

y tampoco lo es la división,

(4:2):2=1\quad \neq \quad 4:(2:2)=4

.

ni la exponenciación, que es igualmente no asociativa

2^{(2^{3})}=2^{8}=256\quad \neq \quad (2^{2})^{3}=4^{3}=64

La adición y multiplicación de números complejos y cuaterniones son asociativas. La adición de octoniones también es asociativa, pero la multiplicación de octoniones es no asociativa.
Las funciones máximo común divisor y mínimo común múltiplo actúan de forma asociativa.

\left.{\begin{matrix}\operatorname {mcd} (\operatorname {mcd} (x,y),z)=\operatorname {mcd} (x,\operatorname {mcd} (y,z))=\operatorname {mcd} (x,y,z)\ \quad \\\operatorname {mcm} (\operatorname {mcm} (x,y),z)=\operatorname {mcm} (x,\operatorname {mcm} (y,z))=\operatorname {mcm} (x,y,z)\quad \end{matrix}}\right\}{\mbox{ para todo }}x,y,z\in \mathbb {Z} .

La intersección o la unión de conjuntos son asociativas.

\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{para todos los conjuntos }}A,B,C.

SI M es algún conjunto y S denota el conjunto de todas las cunciones de M a M, entonces la operación de composición funcional sobre S es asociativa.

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

Más generalmente, dados cuatro conjuntos M, N, P y Q, con h: M a N, g: N a P, y f: P a Q, entonces

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

tal como en el ejemplo anterior. En resumen, la composición de aplicaciones siempre es asociativa.

Para un conjunto con tres elementos A, B, y C, la siguiente operación es asociativa.

×	A	B	C
A	A	A	A
B	A	B	C
C	A	A	A

De esta manera, por ejemplo, A(BC)=(AB)C = A. Esta operación no es conmutativa.

Ya que las matrices representan funciones de transformación lineal, con la multiplicación matricial representando composición funcional, se puede concluir inmediatamente que la multiplicación matricial es asociativa.^[2]

En lógica proposicional

Regla de Reemplazo

En la lógica proposicional estándar, la asociación,^[3]^[4] o asociatividad^[5] son dos reglas de reemplazo válidas. Estas reglas permiten mover los paréntesis en expresiones lógicas usadas en pruebas lógicas. Las reglas son:

(P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)

(P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R)

donde " $\Leftrightarrow$ " es un símbolo metalógico que representa "puede ser reemplazado en una prueba por".

Conectivas de funciones de verdad

Asociatividad es una propiedad de algunas conectivas lógicas en las funciones de verdad de la lógica proposicional. Las siguientes equivalencias lógicas demuestran que la asociatividad es una propiedad de conectivas lógicas particulares. Son asimismo tautologías de funciones de verdad.

Asociatividad de la disyunción:

((P\lor Q)\lor R)\leftrightarrow (P\lor (Q\lor R))

(P\lor (Q\lor R))\leftrightarrow ((P\lor Q)\lor R)

Asociatividad de la conjunción:

((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))

(P\land (Q\land R))\leftrightarrow ((P\land Q)\land R)

Asociatividad de la equivalencia:

((P\leftrightarrow Q)\leftrightarrow R)\leftrightarrow (P\leftrightarrow (Q\leftrightarrow R))

(P\leftrightarrow (Q\leftrightarrow R))\leftrightarrow ((P\leftrightarrow Q)\leftrightarrow R)

La negación conjunta es un ejemplo de conectivo funcional de verdad que no es asociativo.

Operación no asociativa

Una operación binaria $*$ sobre un conjunto S que no satisface la ley asociativa se denomina no asociativa'. Simbólicamente,

$(x*y)*z\neq x*(y*z)\qquad {\mbox{para algunos }}x,y,z\in S.$

Para una operación de este tipo, el orden de evaluación sí importa. Por ejemplo:

Sustracción: $(5-3)-2\,\neq \,5-(3-2)$
División: $(4/2)/2\,\neq \,4/(2/2)$
Exponenciación: $2^{(1^{2})}\,\neq \,(2^{1})^{2}$
Producto vectorial: ${\begin{aligned}\mathbf {i} \times (\mathbf {i} \times \mathbf {j} )&=\mathbf {i} \times \mathbf {k} =-\mathbf {j} \\(\mathbf {i} \times \mathbf {i} )\times \mathbf {j} &=\mathbf {0} \times \mathbf {j} =\mathbf {0} \end{aligned}}$

Además, aunque la suma es asociativa para sumas finitas, no lo es dentro de sumas infinitas (series). Por ejemplo,

$(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots =0$ whereas $1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots =1.$ Algunas operaciones no asociativas son fundamentales en matemáticas. Aparecen a menudo como la multiplicación en estructuras llamadas álgebras no asociativass, que tienen también una suma y una multiplicación escalar. Algunos ejemplos son los octonioness y las álgebras de Lies. En las álgebras de Lie, la multiplicación satisface la identidad de Jacobi en lugar de la ley asociativa; esto permite abstraer la naturaleza algebraica de las transformaciones infinitesimales.

Otros ejemplos son cuasigrupo, cuasicampo, anillo no asociativo y magmas no asociativos conmutativos.

No-asociatividad del cálculo en coma flotante

En matemáticas, la suma y multiplicación de números reales es asociativa. En cambio, en informática, la suma y multiplicación de números de coma flotante no es asociativa, ya que se introducen errores de redondeo cuando se unen valores de tamaños distintos.^[6].

Para ilustrar esto, considere una representación en coma flotante con un mantisa de 4 bits:

(1.000₂×2⁰ + 1.000₂×2⁰) + 1.000₂×2⁴ = 1.000₂×2¹ + 1.000₂×2⁴ = 1.001₂×2⁴

1.000₂×2⁰ + (1.000₂×2⁰ + 1.000₂×2⁴) = 1.000₂×2⁰ + 1.000₂×2⁴ = 1.000₂×2⁴

Aunque la mayoría de los ordenadores calculan con 24 o 53 bits de mantisa,^[7] esta es una fuente importante de error de redondeo, y enfoques como el algoritmo de suma de Kahan son formas de minimizar los errores. Puede ser especialmente problemático en computación paralela.^[8]^[9]

Véase también

Referencias

↑ Durbin, John R. (1992). Modern Algebra: an Introduction (3rd edición). New York: Wiley. p. 78. ISBN 978-0-471-51001-7. «If $a_{1},a_{2},\dots ,a_{n}\,\,(n\geq 2)$ are elements of a set with an associative operation, then the product $a_{1}a_{2}\cdots a_{n}$ is unambiguous; this is, the same element will be obtained regardless of how parentheses are inserted in the product.»
↑ «Matrix product associativity». Khan Academy. Consultado el 5 de junio de 2016.
↑ Moore and Parker
↑ Copi and Cohen
↑ Hurley
↑ Knuth, Donald, The Art of Computer Programming, Volumen 3, sección 4.2.2
↑ IEEE Computer Society (29 de agosto de 2008). IEEE Standard for Floating-Point Arithmetic. ISBN 978-0-7381-5753-5. IEEE Std 754-2008.
↑ Villa, Oreste; Chavarría-mir, Daniel; Gurumoorthi, Vidhya; Márquez, Andrés; Krishnamoorthy, Sriram, Effects of Floating-Point non-Associativity on Numerical Computations on Massively Multithreaded Systems, archivado desde el original el 15 de febrero de 2013, consultado el 8 de abril de 2014 .
↑ Goldberg, David (March 1991). «What Every Computer Scientist Should Know About Floating-Point Arithmetic». ACM Computing Surveys 23 (1): 5-48. S2CID 222008826. doi:10.1145/103162.103163. Archivado desde el original el 19 de mayo de 2022. Consultado el 20 de enero de 2016.

Datos: Q177251

[1] Durbin, John R. (1992). Modern Algebra: an Introduction (3rd edición). New York: Wiley. p. 78. ISBN 978-0-471-51001-7. «If $a_{1},a_{2},\dots ,a_{n}\,\,(n\geq 2)$ are elements of a set with an associative operation, then the product $a_{1}a_{2}\cdots a_{n}$ is unambiguous; this is, the same element will be obtained regardless of how parentheses are inserted in the product.»

[2] «Matrix product associativity». Khan Academy. Consultado el 5 de junio de 2016.

[3] Moore and Parker

[4] Copi and Cohen

[5] Hurley

[6] Knuth, Donald, The Art of Computer Programming, Volumen 3, sección 4.2.2

[7] IEEE Computer Society (29 de agosto de 2008). IEEE Standard for Floating-Point Arithmetic. ISBN 978-0-7381-5753-5. IEEE Std 754-2008.

[8] Villa, Oreste; Chavarría-mir, Daniel; Gurumoorthi, Vidhya; Márquez, Andrés; Krishnamoorthy, Sriram, Effects of Floating-Point non-Associativity on Numerical Computations on Massively Multithreaded Systems, archivado desde el original el 15 de febrero de 2013, consultado el 8 de abril de 2014 .

[Goldberg_1991-9] Goldberg, David (March 1991). «What Every Computer Scientist Should Know About Floating-Point Arithmetic». ACM Computing Surveys 23 (1): 5-48. S2CID 222008826. doi:10.1145/103162.103163. Archivado desde el original el 19 de mayo de 2022. Consultado el 20 de enero de 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]