Propiedad asociativa

Propiedad de una operación matemática

En matemáticas , la propiedad asociativa ^[1] es una propiedad de algunas operaciones binarias que significa que reorganizar los paréntesis en una expresión no cambiará el resultado. En lógica proposicional , la asociatividad es una regla válida de reemplazo para expresiones en demostraciones lógicas .

En una expresión que contiene dos o más ocurrencias seguidas del mismo operador asociativo, el orden en el que se realizan las operaciones no importa siempre que no se modifique 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), reorganizar los paréntesis en dicha expresión no cambiará su valor. Considere las siguientes ecuaciones:

$${\displaystyle {\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 reordenaron en cada línea, los valores de las expresiones no se modificaron. Como esto es cierto cuando se realizan sumas y multiplicaciones de números reales , 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 ocupa de 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 no (generalmente) conmutativas.

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

Sin embargo, muchas operaciones importantes e interesantes no son asociativas; algunos ejemplos incluyen la resta , la exponenciación y el producto vectorial . A diferencia de las propiedades teóricas de los números reales, la suma de números de punto 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 × S × S a S forman la misma función de S × S × S a S .

Formalmente, una operación binaria sobre un conjunto S se denomina asociativa si satisface la ley asociativa : ${\displaystyle \ast }$

${\displaystyle (x\ast y)\ast z=x\ast (y\ast z)}$, para todos en S .}} ${\displaystyle x,y,z}$

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

${\displaystyle (xy)z=x(yz)}$, para todos en S. ${\displaystyle x,y,z}$

La ley asociativa también se puede expresar en notación funcional de la siguiente manera: ${\displaystyle (f\circ (g\circ h))(x)=((f\circ g)\circ h)(x)}$

Derecho asociativo generalizado

En ausencia de la propiedad asociativa, cinco factores a , b , c , d , e dan como resultado 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 cuántos pares de paréntesis válidos se inserten en la expresión. ^[2] Esto se denomina ley asociativa generalizada .

El número de corchetes posibles es simplemente el número catalán , , para n operaciones sobre n+1 valores. Por ejemplo, un producto de 3 operaciones sobre 4 elementos se puede escribir (ignorando las permutaciones de los argumentos), de las siguientes maneras: ${\displaystyle C_{n}}$ ${\displaystyle C_{3}=5}$

• ${\displaystyle ((ab)c)d}$
• ${\displaystyle (a(bc))d}$
• ${\displaystyle a((bc)d)}$
• ${\displaystyle (a(b(cd))}$
• ${\displaystyle (ab)(cd)}$

Si la operación del producto es asociativa, la ley asociativa generalizada dice que todas estas expresiones darán el mismo resultado. Por lo tanto, a menos que la expresión con los paréntesis omitidos ya tenga un significado diferente (ver más abajo), los paréntesis pueden considerarse innecesarios y "el" producto puede escribirse sin ambigüedades como

${\displaystyle abcd}$

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 innecesarias para la desambiguación.

Un ejemplo en el que esto no funciona es el bicondicional lógico ↔ . Es asociativo; por lo tanto, A ↔ ( B ↔ C ) es equivalente a ( A ↔ B ) ↔ C , pero A ↔ B ↔ C significa más comúnmente ( A ↔ B ) y ( B ↔ C ) , que no son equivalentes.

Ejemplos

La suma de números reales es asociativa.

Algunos ejemplos de operaciones asociativas incluyen los siguientes.

• La concatenación de las tres cadenas "hello", " ", "world"se puede calcular concatenando las dos primeras cadenas (dando "hello ") y añadiendo la tercera cadena ( "world"), o uniendo la segunda y la tercera cadena (dando " world") y concatenando la primera cadena ( "hello") con el resultado. Los dos métodos producen el mismo resultado; la concatenación de cadenas es asociativa (pero no conmutativa).
• En aritmética , la suma y la multiplicación de números reales son asociativas, es decir,

  $${\displaystyle \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{for all }}x,y,z\in \mathbb {R} .}$$

  Debido a la asociatividad, los paréntesis de agrupación se pueden omitir sin ambigüedad.
• La operación trivial x ∗ y = x (es decir, el resultado es el primer argumento, sin importar cuál sea el segundo argumento) es asociativa pero no conmutativa. Asimismo, la operación trivial x ∘ y = y (es decir, el resultado es el segundo argumento, sin importar cuál sea el primer argumento) es asociativa pero no conmutativa.
• La suma y multiplicación de números complejos y cuaterniones son asociativas. La suma de octoniones también es asociativa, pero la multiplicación de octoniones no es asociativa.
• Las funciones máximo común divisor y mínimo común múltiplo actúan asociativamente. $${\displaystyle \left.{\begin{matrix}\operatorname {gcd} (\operatorname {gcd} (x,y),z)=\operatorname {gcd} (x,\operatorname {gcd} (y,z))=\operatorname {gcd} (x,y,z)\ \quad \\\operatorname {lcm} (\operatorname {lcm} (x,y),z)=\operatorname {lcm} (x,\operatorname {lcm} (y,z))=\operatorname {lcm} (x,y,z)\quad \end{matrix}}\right\}{\mbox{ for all }}x,y,z\in \mathbb {Z} .}$$
• Tomando la intersección o la unión de conjuntos : $${\displaystyle \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{for all sets }}A,B,C.}$$
• Si M es un conjunto y S denota el conjunto de todas las funciones desde M hasta M , entonces la operación de composición de funciones sobre S es asociativa: $${\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h\qquad {\mbox{for all }}f,g,h\in S.}$$
• De manera un poco más general, dados cuatro conjuntos M , N , P y Q , con h  : M → N , g  : N → P y f  : P → Q , entonces como antes. En resumen, la composición de mapas es siempre asociativa. $${\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h}$$
• En la teoría de categorías , la composición de morfismos es asociativa por definición. La asociatividad de los funtores y las transformaciones naturales se desprende de la asociatividad de los morfismos.
• Consideremos un conjunto con tres elementos, A , B y C. La operación es la siguiente: es asociativa. Así, por ejemplo, A ( B C ) = ( A B ) C = A . Esta operación no es conmutativa.
• Dado que las matrices representan funciones lineales y la multiplicación de matrices representa la composición de funciones, se puede concluir inmediatamente que la multiplicación de matrices es asociativa. ^[3]
• Para los números reales (y para cualquier conjunto totalmente ordenado ), la operación de mínimo y máximo es asociativa: $${\displaystyle \max(a,\max(b,c))=\max(\max(a,b),c)\quad {\text{ and }}\quad \min(a,\min(b,c))=\min(\min(a,b),c).}$$

Lógica proposicional

Regla de reemplazo

En la lógica proposicional veritativo-funcional estándar, la asociación ^{[4] [5]} o la asociatividad ^[6] son ​​dos reglas válidas de reemplazo . Las reglas permiten mover paréntesis en expresiones lógicas en demostraciones lógicas . Las reglas (usando la notación de conectivos lógicos ) son:

$${\displaystyle (P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)}$$

y

$${\displaystyle (P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R),}$$

donde " " es un símbolo metalógico que representa "puede reemplazarse en una prueba con". ${\displaystyle \Leftrightarrow }$

Conectivas funcionales de la verdad

La asociatividad es una propiedad de algunos conectivos lógicos de la lógica proposicional veritativo-funcional . Las siguientes equivalencias lógicas demuestran que la asociatividad es una propiedad de conectivos particulares. Las siguientes (y sus recíprocas, ya que ↔ es conmutativa) son tautologías veritativo-funcionales . ^{[ cita requerida ]}

Asociatividad de la disyunción

${\displaystyle ((P\lor Q)\lor R)\leftrightarrow (P\lor (Q\lor R))}$

Asociatividad de la conjunción

${\displaystyle ((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))}$

Asociatividad de equivalencia

${\displaystyle ((P\leftrightarrow Q)\leftrightarrow R)\leftrightarrow (P\leftrightarrow (Q\leftrightarrow R))}$

La negación conjunta es un ejemplo de un 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, ${\displaystyle *}$

$${\displaystyle (x*y)*z\neq x*(y*z)\qquad {\mbox{for some }}x,y,z\in S.}$$

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

Sustracción

${\displaystyle (5-3)-2\,\neq \,5-(3-2)}$

División

${\displaystyle (4/2)/2\,\neq \,4/(2/2)}$

Exponenciación

${\displaystyle 2^{(1^{2})}\,\neq \,(2^{1})^{2}}$

Producto vectorial

${\displaystyle {\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 adición es asociativa para sumas finitas, no es asociativa dentro de sumas infinitas ( series ). Por ejemplo, mientras que $${\displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots =0}$$ $${\displaystyle 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 asociativas , que también tienen una adición y una multiplicación escalar . Algunos ejemplos son los octoniones y las álgebras de Lie . 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 conmutativos no asociativos .

No asociatividad del cálculo de punto flotante

En matemáticas, la suma y multiplicación de números reales son asociativas. En cambio, en informática, la suma y multiplicación de números de punto flotante no son asociativas, ya que pueden introducirse distintos errores de redondeo cuando se unen valores de distinto tamaño en un orden diferente. ^[7]

Para ilustrar esto, considere una representación de punto flotante con un significado de 4 bits :

(1.000 ₂ ×2 ⁰ + 1.000 ₂ ×2 ⁰ ) + 1.000 ₂ ×2 ⁴ = 1.000 ₂ ×2 ¹ + 1.000 ₂ ×2 ⁴ = 1.00 1 ₂ ×2 ⁴

1,000 ₂ ×2 ⁰ + (1,000 ₂ ×2 ⁰ + 1,000 ₂ ×2 ⁴ ) = 1,000 ₂ ×2 ⁰ + 1,000 ₂ ×2 ⁴ = 1,00 0 ₂ ×2 ⁴

Aunque la mayoría de las computadoras calculan con 24 o 53 bits de mantisa, ^[8] esto sigue siendo 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. ^{[9] [10]}

Notación para operaciones no asociativas

En general, se deben utilizar paréntesis para indicar el orden de evaluación si una operación no asociativa aparece más de una vez en una expresión (a menos que la notación especifique el orden de otra manera, como ). Sin embargo, los matemáticos están de acuerdo en un orden particular de evaluación para varias operaciones no asociativas comunes. Esto es simplemente una convención de notación para evitar los paréntesis. ${\displaystyle {\dfrac {2}{3/4}}}$

Una operación asociativa por la izquierda es una operación no asociativa que se evalúa convencionalmente de izquierda a derecha, es decir,

$${\displaystyle \left.{\begin{array}{l}a*b*c=(a*b)*c\\a*b*c*d=((a*b)*c)*d\\a*b*c*d*e=(((a*b)*c)*d)*e\quad \\{\mbox{etc.}}\end{array}}\right\}{\mbox{for all }}a,b,c,d,e\in S}$$

Mientras que una operación asociativa derecha se evalúa convencionalmente de derecha a izquierda:

$${\displaystyle \left.{\begin{array}{l}x*y*z=x*(y*z)\\w*x*y*z=w*(x*(y*z))\quad \\v*w*x*y*z=v*(w*(x*(y*z)))\quad \\{\mbox{etc.}}\end{array}}\right\}{\mbox{for all }}z,y,x,w,v\in S}$$

Se producen tanto operaciones asociativas por la izquierda como por la derecha. Las operaciones asociativas por la izquierda incluyen las siguientes:

Resta y división de números reales ^{[11] [12] [13] [14] [15]}

${\displaystyle x-y-z=(x-y)-z}$

${\displaystyle x/y/z=(x/y)/z}$

Aplicación de funciones

${\displaystyle (f\,x\,y)=((f\,x)\,y)}$

Esta notación puede estar motivada por el isomorfismo de curry , que permite una aplicación parcial.

Las operaciones asociativas por la derecha incluyen las siguientes:

Exponenciación de números reales en notación superíndice

${\displaystyle x^{y^{z}}=x^{(y^{z})}}$

La exponenciación se utiliza habitualmente con corchetes o asociativamente por la derecha porque una operación de exponenciación repetida por la izquierda es de poca utilidad. Las potencias repetidas se reescribirían en su mayoría con multiplicación:

${\displaystyle (x^{y})^{z}=x^{(yz)}}$

Si se formatea correctamente, el superíndice se comporta inherentemente como un conjunto de paréntesis; por ejemplo, en la expresión, la suma se realiza antes de la exponenciación a pesar de que no hay paréntesis explícitos alrededor de ella. Por lo tanto, dada una expresión como , el exponente completo de la base se evalúa primero. Sin embargo, en algunos contextos, especialmente en escritura a mano, la diferencia entre , y puede ser difícil de ver. En tal caso, la asociatividad por la derecha suele estar implícita. ${\displaystyle 2^{x+3}}$ ${\displaystyle 2^{(x+3)}}$ ${\displaystyle x^{y^{z}}}$ ${\displaystyle y^{z}}$ ${\displaystyle x}$ ${\displaystyle {x^{y}}^{z}=(x^{y})^{z}}$ ${\displaystyle x^{yz}=x^{(yz)}}$ ${\displaystyle x^{y^{z}}=x^{(y^{z})}}$

Definición de función

${\displaystyle \mathbb {Z} \rightarrow \mathbb {Z} \rightarrow \mathbb {Z} =\mathbb {Z} \rightarrow (\mathbb {Z} \rightarrow \mathbb {Z} )}$

${\displaystyle x\mapsto y\mapsto x-y=x\mapsto (y\mapsto x-y)}$

El uso de la notación asociativa derecha para estas operaciones puede estar motivado por la correspondencia Curry-Howard y por el isomorfismo de curry .

Las operaciones no asociativas para las que no se define un orden de evaluación convencional incluyen las siguientes.

Exponenciación de números reales en notación infija ^[16]

${\displaystyle (x^{\wedge }y)^{\wedge }z\neq x^{\wedge }(y^{\wedge }z)}$

Operadores de flecha hacia arriba de Knuth

${\displaystyle a\uparrow \uparrow (b\uparrow \uparrow c)\neq (a\uparrow \uparrow b)\uparrow \uparrow c}$

${\displaystyle a\uparrow \uparrow \uparrow (b\uparrow \uparrow \uparrow c)\neq (a\uparrow \uparrow \uparrow b)\uparrow \uparrow \uparrow c}$

Tomando el producto vectorial de tres vectores

${\displaystyle {\vec {a}}\times ({\vec {b}}\times {\vec {c}})\neq ({\vec {a}}\times {\vec {b}})\times {\vec {c}}\qquad {\mbox{ for some }}{\vec {a}},{\vec {b}},{\vec {c}}\in \mathbb {R} ^{3}}$

Tomando el promedio por pares de números reales

${\displaystyle {(x+y)/2+z \over 2}\neq {x+(y+z)/2 \over 2}\qquad {\mbox{for all }}x,y,z\in \mathbb {R} {\mbox{ with }}x\neq z.}$

Tomando el complemento relativo de conjuntos

${\displaystyle (A\backslash B)\backslash C\neq A\backslash (B\backslash C)}$.

(Compárese la no implicación material en lógica.)

Historia

William Rowan Hamilton parece haber acuñado el término "propiedad asociativa" ^[17] alrededor de 1844, una época en la que estaba contemplando el álgebra no asociativa de los octoniones que había aprendido de John T. Graves . ^[18]

Véase también

• Prueba de asociatividad de Light
• Serie telescópica , el uso de la asociatividad de la adición para cancelar términos en una serie infinita
• Un semigrupo es un conjunto con una operación binaria asociativa.
• La conmutatividad y la distributividad son otras dos propiedades de las operaciones binarias que se discuten con frecuencia.
• La asociatividad de potencia , la alternatividad , la flexibilidad y la asociatividad N-aria son formas débiles de asociatividad.
• Las identidades Moufang también proporcionan una forma débil de asociatividad.

Referencias

1. Hungerford, Thomas W. (1974). Álgebra (1.ª ed.). Springer . pág. 24. ISBN 978-0387905181. Definición 1.1 (i) a(bc) = (ab)c para todos a, b, c en G.
2. Durbin, John R. (1992). Álgebra moderna: una introducción (3.ª ed.). Nueva York: Wiley. pág. 78. ISBN 978-0-471-51001-7. Si son elementos de un conjunto con una operación asociativa, entonces el producto es inequívoco; es decir, se obtendrá el mismo elemento independientemente de cómo se inserten los paréntesis en el producto. ${\displaystyle a_{1},a_{2},\dots ,a_{n}\,\,(n\geq 2)}$ ${\displaystyle a_{1}a_{2}\cdots a_{n}}$
3. "Matrix product associativity" (Asociatividad de productos matriciales). Khan Academy . Consultado el 5 de junio de 2016 .
4. Moore, Brooke Noel; Parker, Richard (2017). Pensamiento crítico (12.ª ed.). Nueva York: McGraw-Hill Education. pág. 321. ISBN 9781259690877.
5. Copi, Irving M.; Cohen, Carl; McMahon, Kenneth (2014). Introducción a la lógica (14.ª ed.). Essex: Pearson Education. pág. 387. ISBN 9781292024820.
6. Hurley, Patrick J.; Watson, Lori (2016). Una introducción concisa a la lógica (13.ª ed.). Boston: Cengage Learning. pág. 427. ISBN 9781305958098.
7. Knuth, Donald, El arte de la programación informática , Volumen 3, sección 4.2.2
8. IEEE Computer Society (29 de agosto de 2008). Estándar IEEE para aritmética de punto flotante . doi :10.1109/IEEESTD.2008.4610935. ISBN 978-0-7381-5753-5. Norma IEEE 754-2008.
9. Villa, Oreste; Chavarría-mir, Daniel; Gurumoorthi, Vidhya; Márquez, Andrés; Krishnamoorthy, Sriram, Efectos de la no asociatividad de punto flotante en los cálculos numéricos en sistemas multiproceso masivos (PDF) , archivado desde el original (PDF) el 15 de febrero de 2013 , consultado el 8 de abril de 2014
10. Goldberg, David (marzo de 1991). "What Every Computer Scientist Should Know About Floating-Point Arithmetic" (PDF) . Encuestas de computación de la ACM . 23 (1): 5–48. doi :10.1145/103162.103163. S2CID  222008826. Archivado (PDF) desde el original el 19 de mayo de 2022 . Consultado el 20 de enero de 2016 .
11. George Mark Bergman "Orden de operaciones aritméticas"
12. "El orden de las operaciones". Lugar de Educación.
13. "El orden de las operaciones", marca de tiempo 5m40s. Khan Academy .
14. "Uso del orden de operaciones y exploración de propiedades" Archivado el 16 de julio de 2022 en Wayback Machine , sección 9. Departamento de Educación de Virginia.
15. Bronstein, de:Taschenbuch der Mathematik , páginas 115-120, capítulo: 2.4.1.1, ISBN 978-3-8085-5673-3 
16. Exponenciación Asociatividad y Notación Matemática Estándar Codeplea. 23 de agosto de 2016. Consultado el 20 de septiembre de 2016.
17. Hamilton, WR (1844–1850). "Sobre los cuaterniones o un nuevo sistema de imaginarios en álgebra". Colección de David R. Wilkins. Philosophical Magazine . Trinity College Dublin .
18. Baez, John C. (2002). "Los octoniones" (PDF) . Boletín de la American Mathematical Society . 39 (2): 145–205. arXiv : math/0105155 . doi :10.1090/S0273-0979-01-00934-X. ISSN  0273-0979. MR  1886087. S2CID  586512.