Propiedad asociativa

Propiedad de una operación matemática

En matemáticas , la propiedad asociativa ^[1] es una propiedad de algunas operaciones binarias , lo 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 sustitución de expresiones en pruebas lógicas .

Dentro de una expresión que contiene dos o más apariciones seguidas del mismo operador asociativo, el orden en que se realizan las operaciones no importa siempre que no se cambie la secuencia de los operandos . Es decir (después de reescribir la expresión entre 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 se reorganizaron los paréntesis en cada línea, los valores de las expresiones no se modificaron. Dado que esto es cierto al realizar 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 aborda si el orden de dos operandos afecta el 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 abundan 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 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 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 ∗ en el conjunto S es asociativa cuando este diagrama conmuta . Es decir, cuando los dos caminos de S × S × S a S se componen de la misma función de S × S × S a S.

Formalmente, una operación binaria ∗ sobre un conjunto 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 reemplazar 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 se puede expresar en notación funcional así: f ( f ( x , y ), z ) = f ( x , f ( y , z )) .

Derecho asociativo generalizado

En ausencia de la propiedad asociativa, cinco factores a , b , c , d , e dan como resultado una red de 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 pares válidos de paréntesis en la expresión. ^[2] Esto se llama ley asociativa generalizada . Por ejemplo, un producto de cuatro elementos se puede escribir, sin cambiar el orden de los factores, de cinco maneras 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 del producto es asociativa, la ley asociativa generalizada dice que todas estas expresiones producirán el mismo resultado. Entonces, a menos que la expresión con 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

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 ↔ . 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 es equivalente.

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 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 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 primero) 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.
• El máximo común divisor y el 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 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 algún conjunto y S denota el conjunto de todas las funciones de M a M , entonces la operación de composición de funciones en 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
  $${\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h}$$
  como antes. En definitiva, la composición de mapas es siempre asociativa.
• En la teoría de categorías , la composición de morfismos es asociativa por definición. La asociatividad de functores y transformaciones naturales se deriva de la asociatividad de morfismos.
• Considere un conjunto con tres elementos , A , B y C. La siguiente operación: es asociativo. Así, por ejemplo, A ( B C ) = ( A B ) C = A . Esta operación no es conmutativa.
• Debido a 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 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 funcional de verdad estándar, la asociación , ^{[4] [5]} o la asociatividad ^[6] son ​​dos reglas válidas de sustitución . Las reglas permiten mover paréntesis en expresiones lógicas en pruebas lógicas . Las reglas (usando 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 "se puede reemplazar en una prueba con". ${\displaystyle \Leftrightarrow }$

Conectivos funcionales de verdad

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

Asociatividad de disyunción

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

Asociatividad de 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 una verdad conectiva funcional que no es asociativa.

Operación no asociativa

Una operación binaria sobre un conjunto S que no satisface la ley asociativa se llama no asociativa . Simbólicamente, ${\displaystyle *}$

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

Para tal operación 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 cruzado 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 suma es asociativa para sumas finitas, no lo es dentro de sumas infinitas ( series ). Por ejemplo,

$${\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 multiplicación en estructuras llamadas álgebras no asociativas , que tienen también una suma y una multiplicación escalar . Algunos ejemplos son los octoniones y las álgebras de Lie . En á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 coma flotante.

En matemáticas, la suma y multiplicación de números reales es asociativa. Por el contrario, 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 diferentes. ^[7]

Para ilustrar esto, considere una representación de punto flotante con una mantisa 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] 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 resultar especialmente problemático en la 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 acuerdan un orden particular de evaluación para varias operaciones no asociativas comunes. Esto es simplemente una convención de notación para evitar paréntesis. ${\displaystyle {\dfrac {2}{3/4}}}$

Una operación asociativa por la izquierda es una operación no asociativa que convencionalmente se evalúa 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 por la 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 operaciones asociativas por izquierda y por derecha. Las operaciones asociativas por 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 curry , que permite una aplicación parcial.

Las operaciones asociativas por derecha incluyen las siguientes:

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

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

La exponenciación se usa comúnmente entre paréntesis o de forma asociativa por la derecha porque una operación de exponenciación asociativa por la izquierda repetida es de poca utilidad. Las potencias repetidas se reescribirían en su mayoría con multiplicación:

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

Con el formato correcto, 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. Así, dada una expresión como , primero se evalúa el exponente completo de la base . Sin embargo, en algunos contextos, especialmente al escribir a mano, la diferencia entre y puede ser difícil de ver. En tal caso, suele estar implícita la asociatividad por la derecha. ${\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 notación asociativa derecha para estas operaciones puede estar motivado por la correspondencia Curry-Howard y por el isomorfismo curry .

Las operaciones no asociativas para las que no se define ningún 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 cruzado 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, época en la que contemplaba el álgebra no asociativa de los octoniones que había aprendido de John T. Graves . ^[18]

Ver también

• Prueba de asociatividad de Light
• Serie telescópica , el uso de la asociatividad de la suma 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 poder , 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.). Saltador . pag. 24.ISBN​ 978-0387905181. Definición 1.1 (i) a(bc) = (ab)c para todo a, b, c en G.
2. Durbin, John R. (1992). Álgebra moderna: una introducción (3ª ed.). Nueva York: Wiley. pag. 78.ISBN​ 978-0-471-51001-7. Si son elementos de un conjunto con 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. "Asociatividad de productos de matriz". Academia Khan . Consultado el 5 de junio de 2016 .
4. Moore, Brooke Noël; Parker, Richard (2017). Pensamiento crítico (12ª ed.). Nueva York: McGraw-Hill Education. pag. 321.ISBN​ 9781259690877.
5. Copi, Irving M.; Cohen, Carl; McMahon, Kenneth (2014). Introducción a la lógica (14ª ed.). Essex: Educación Pearson. pag. 387.ISBN​ 9781292024820.
6. Hurley, Patrick J.; Watson, Lori (2016). Una introducción concisa a la lógica (13ª ed.). Boston: Aprendizaje Cengage. pag. 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 coma 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 coma flotante en cálculos numéricos en sistemas masivamente multiproceso (PDF) , archivado desde el original (PDF) el 15 de febrero de 2013 , recuperado 8 de abril 2014
10. Goldberg, David (marzo de 1991). "Lo que todo informático debería saber sobre la aritmética de punto flotante" (PDF) . Encuestas de Computación 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 las operaciones aritméticas"
12. "El orden de las operaciones". Lugar de Educación.
13. "El orden de las operaciones", marca de tiempo 5m40s. Academia Khan .
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. Codeplea de asociatividad de exponenciación y notación matemática estándar. 23 de agosto de 2016. Consultado el 20 de septiembre de 2016.
17. Hamilton, WR (1844-1850). "Sobre cuaterniones o un nuevo sistema de imaginarios en álgebra". Colección David R. Wilkins. Revista Filosófica . Trinity College de Dublín .
18. Báez, John C. (2002). «Los Octonions» (PDF) . Boletín de la Sociedad Matemática Estadounidense . 39 (2): 145-205. arXiv : matemáticas/0105155 . doi :10.1090/S0273-0979-01-00934-X. ISSN  0273-0979. SEÑOR  1886087. S2CID  586512.