Propiedad asociativa

Este artículo trata sobre la propiedad asociativa en matemáticas. Para la asociatividad en la memoria caché de la unidad de procesamiento central, consulte la memoria caché de la CPU § Asociatividad . Para asociatividad en lenguajes de programación, consulte asociatividad de operadores . Para conocer el significado de un grupo asociado de personas en lingüística, consulte Asociatividad (lingüística) .

Redireccionamiento "asociativo" y "no asociativo" aquí. Para el aprendizaje asociativo y no asociativo, consulte Aprendizaje § Tipos .

Property allowing removing parentheses in a sequence of operations

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Buscar fuentes:  "Propiedad asociativa"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( junio de 2009 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

Reglas de transformación
Cálculo proposicional
Reglas de inferencia
Introducción  / eliminación de implicaciones ( modus ponens ) Introducción  / eliminación bicondicional Introducción  / eliminación de conjunción Introducción  / eliminación de disyunción Silogismo disyuntivo  / hipotético Dilema constructivo  / destructivo Absorción  / modus tollens  / modus ponendo tollens
Reglas de reemplazo
Asociatividad Conmutatividad Distributividad Doble negación Leyes de de Morgan Transposición Implicación material Exportación Tautología Introducción a la negación
Lógica de predicados
Generalización  / instanciación universal Generalización existencial  / instanciación
v t mi

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 reemplazo de expresiones en demostraciones lógicas .

Dentro de una expresión que contiene dos o más ocurrencias en una fila del mismo operador asociativo, el orden en el 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 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 (2+3)+4=2+(3+4)=9\,}$

${\displaystyle 2\times (3\times 4)=(2\times 3)\times 4=24.}$

Aunque los paréntesis se reorganizaron 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 trata 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 , entonces decimos que la multiplicación de números reales es una operación conmutativa.

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 cruzado vectorial . A diferencia de las propiedades teóricas de los números reales, la adición 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 componer a la misma función de S × S × S a S .

Formalmente, una operación binaria ∗ en 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 usa 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 .

( Xy ) z = x ( yz ) = xyz para todos 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 los pares válidos de paréntesis en la expresión. ^[2] Esto se llama ley asociativa generalizada . Por ejemplo, un producto de cuatro elementos puede escribirse, sin cambiar el orden de los factores, de cinco formas posibles:

${\displaystyle ((ab)c)d}$

${\displaystyle (ab)(cd)}$

${\displaystyle (a(bc))d}$

${\displaystyle a((bc)d)}$

${\displaystyle a(b(cd))}$

Si la operación del producto es asociativa, la ley asociativa generalizada dice que todas estas fórmulas darán el mismo resultado. Entonces, a menos que la fórmula 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

${\displaystyle abcd.}$

A medida que aumenta el número de elementos, el número de posibles formas 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 que A (B C) es equivalente a (A B) C, pero A B C más comúnmente significa (A B y B C), que no es equivalente.${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$

Ejemplos

En operaciones asociativas es .${\displaystyle (x\circ y)\circ z=x\circ (y\circ z)}$

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 mediante la concatenación de las dos primeras cuerdas (dar "hello ") y añadiendo la tercera cuerda ( "world"), o uniéndose a la segunda y tercera cuerda (dar " world") y la concatenación de 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 la 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 no es asociativa.
• El máximo común divisor y las funciones mínimas comunes múltiples 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 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.}$

• Un poco más generalmente, dados cuatro conjuntos M , N , P y Q , con h : M a N , g : N a P , yf : P a Q , entonces

${\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h}$

como antes. En resumen, la composición de los mapas es siempre asociativa.

• Considere un conjunto con tres elementos, A, B y C. La siguiente operación:

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

es asociativo. Así, por ejemplo, A (BC) = (AB) 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]

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 reemplazo . Las reglas permiten mover paréntesis en expresiones lógicas en pruebas lógicas . Las reglas (usando la notación de conectivas lógicas ) 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 metaloló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 son tautologías de función de la verdad . ^[7]

Asociatividad de disyunción :

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

${\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))}$

${\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))}$

${\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 en 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 es importante. 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}}$

También tenga en cuenta que las sumas infinitas no son generalmente asociativas, por ejemplo:

${\displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots \,=\,0}$

mientras que

${\displaystyle 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots \,=\,1}$

El estudio de las estructuras no asociativas surge de razones algo diferentes de la corriente principal del álgebra clásica. Un área dentro del álgebra no asociativa que ha crecido mucho es la de las álgebras de Lie . Allí, la ley asociativa es reemplazada por la identidad de Jacobi . Las álgebras de mentira abstraen la naturaleza esencial de las transformaciones infinitesimales y se han vuelto omnipresentes en las matemáticas.

Existen otros tipos específicos de estructuras no asociativas que se han estudiado en profundidad; estos tienden a provenir de algunas aplicaciones o áreas específicas, como las matemáticas combinatorias . Otros ejemplos son cuasigrupo , quasifield , anillo no asociativo , álgebra no asociativo y magmas no asociativos conmutativos .

No asociatividad del cálculo de punto 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. ^[8]

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,000 ₂ × 2 ⁴

Aunque la mayoría de las computadoras calculan con 24 o 53 bits de mantisa, ^[9] 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 la computación paralela. ^{[10] [11]}

Notación para operaciones no asociativas

Artículo principal: Asociatividad del operador

En general, se deben usar 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. Esta es simplemente una convención de notación para evitar los paréntesis.${\displaystyle {\dfrac {2}{3/4}}}$

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

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

mientras que una operación asociativa por la derecha se evalúa convencionalmente de derecha a izquierda:

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

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

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

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

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

• Aplicación de la función:

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

Esta notación puede estar motivada por el isomorfismo de curry .

Las operaciones de asociación 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 con paréntesis o asociativamente a la derecha porque una operación repetida de exponenciación asociativa a la izquierda es de poca utilidad. Los poderes repetidos se reescriben principalmente con la multiplicación:

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

Formateado correctamente, el superíndice se comporta de forma inherente como un conjunto de paréntesis; por ejemplo, en la expresión, la suma se realiza antes de la potenciació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 en la escritura, la diferencia entre , y puede ser difícil de ver. En tal caso, generalmente está 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 la notación asociativa a la derecha para estas operaciones puede estar motivado por la correspondencia de 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: ^[17]

${\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.}$

• No es lo mismo tomar el complemento relativo de conjuntos que . (Compare la no implicación material en lógica).${\displaystyle (A\backslash B)\backslash C}$${\displaystyle A\backslash (B\backslash C)}$

Ver también

Busque propiedad asociativa en Wikcionario, el diccionario gratuito.

• Prueba de asociatividad de la luz
• Serie telescópica , el uso de asociatividad de 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 poder , la alternatividad , la flexibilidad y la asociatividad N-aria son formas débiles de asociatividad.
• Las identidades mufang también proporcionan una forma débil de asociatividad.

Referencias

1. Hungerford, Thomas W. (1974). Álgebra (1ª ed.). Springer . 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 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}\dots a_{n}}$
3. "Asociatividad de producto de matriz" . 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. pag. 321. ISBN 9781259690877.
5. Copi, Irving M .; Cohen, Carl; McMahon, Kenneth (2014). Introducción a la lógica (14ª ed.). Essex: Pearson Education. 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. "Prueba de asociatividad lógica simbólica" . Math.stackexchange.com . 22 de marzo de 2017.
8. Knuth, Donald, El arte de la programación informática , Volumen 3, sección 4.2.2
9. 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. IEEE Std 754-2008.
10. Villa, Oreste; Chavarría-mir, Daniel; Gurumoorthi, Vidhya; Márquez, Andrés; Krishnamoorthy, Sriram, Efectos de la no asociatividad de punto flotante en cálculos numéricos en sistemas de múltiples subprocesos masivos (PDF) , archivado del original (PDF) el 15 de febrero de 2013 , consultado el 8 de abril de 2014
11. Goldberg, David (marzo de 1991). "Lo que todo informático debe 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 . Consultado el 20 de enero de 2016 .  ( [1] , [2] Archivado el 6 de abril de 2016 en la Wayback Machine )
12. George Mark Bergman: orden de operaciones aritméticas
13. Lugar de educación: el orden de las operaciones
14. Khan Academy : The Order of Operations , marca de tiempo 5m40s
15. Departamento de Educación de Virginia: Uso del orden de operaciones y exploración de propiedades , sección 9
16. Bronstein: de: Taschenbuch der Mathematik , páginas 115-120, capítulo: 2.4.1.1, ISBN 978-3-8085-5673-3 
17. Asociatividad de exponenciación y código de notación matemática estándar . 23 de agosto de 2016. Consultado el 20 de septiembre de 2016.