Propiedad asociativa -Associative property

En matemáticas , la propiedad asociativa 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 ocurrencias 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:

${\ estilo de visualización (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 cuando se realizan sumas y multiplicaciones 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, en la multiplicación de números reales no importa el orden, 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 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 vectorial . A diferencia de las propiedades teóricas de los números reales, la adición 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 ∗ en el conjunto S es asociativa cuando este diagrama conmuta . Es decir, cuando los dos caminos de S × S × S a S componen la misma función de S × S × S a S.

Formalmente, una operación binaria ∗ sobre un conjunto S se denomina asociativa si cumple la ley asociativa :

( X ∗ y ) ∗ z = X ∗ ( y ∗ z ) para todos los 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 los 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 )) .

Ley asociativa generalizada

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 de paréntesis válidos en la expresión. Esto se llama la ley asociativa generalizada . Por ejemplo, un producto de cuatro elementos se puede escribir, sin cambiar el orden de los factores, de cinco formas posibles:

${\ estilo de visualización ((ab) c) d}$

${\ estilo de visualización (ab) (cd)}$

${\ estilo de visualización (a (bc)) d}$

${\ estilo de visualización a ((bc) d)}$

${\ estilo de visualización a (b (cd))}$

Si la operación 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

${\ estilo de visualización 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 innecesarios para la desambiguación.

Un ejemplo donde 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 significa más comúnmente (A B y B C), que no es equivalente. ${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$${\ estilo de visualización \ flecha izquierda derecha}$

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 concatenando las dos primeras cadenas (dando "hello ") y agregando 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{matriz}(x+y)+z=x+(y+z)=x+y+z\quad \\(x\,y)z=x(y\,z )=x\,y\,z\qquad \qquad \qquad \quad \ \ \,\end{matriz}}\right\}{\mbox{para todo }}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. Del mismo modo, 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 suma de octoniones también es asociativa, pero la multiplicación de octoniones no es asociativa.
• Las funciones de 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) )=\nombre del operador {gcd} (x,y,z)\ \quad \\\nombre del operador {lcm} (\nombre del operador {lcm} (x,y),z)=\nombre del operador {lcm} (x,\nombre del operador { lcm} (y,z))=\operatorname {lcm} (x,y,z)\quad \end{matriz}}\right\}{\mbox{ para todos }}x,y,z\in \mathbb {Z} .}$

• Tomando la intersección o la unión de conjuntos :

${\displaystyle \left.{\begin{matriz}(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 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{para todos}}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 , y f : 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.

• Debido a que las matrices representan funciones lineales y la multiplicación de matrices representa la composición de funciones, uno puede concluir inmediatamente que la multiplicación de matrices es asociativa.

Lógica proposicional

Regla de reemplazo

En la lógica proposicional funcional de verdad estándar, la asociación o la asociatividad 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 conectores 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 ser reemplazado en una prueba por". ${\ estilo de visualización \ flecha izquierda derecha}$

Conectivos funcionales de verdad

La asociatividad es una propiedad de algunos conectivos lógicos de la lógica proposicional funcional veritativa . Las siguientes equivalencias lógicas demuestran que la asociatividad es una propiedad de los conectivos particulares. Las siguientes son tautologías veritativo-funcionales .

Asociatividad de la 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 la 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 sobre un conjunto S que no cumple la ley asociativa se llama no asociativa . Simbólicamente, ${\ estilo de visualización *}$

${\displaystyle (x*y)*z\neq x*(y*z)\qquad {\mbox{para algunos }}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

${\ estilo de visualización (4/2)/2\,\neq\,4/(2/2)}$

• exponenciación

${\ estilo de visualización 2 ^ {(1 ^ {2})} \, \ neq \, (2 ^ {1}) ^ {2}}$

• Producto cruzado vectorial

${\displaystyle {\begin{alineado}\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{alineado}} }$

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)+\puntos =0}$

mientras que

${\displaystyle 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\puntos = 1.}$

Algunas operaciones no asociativas son fundamentales en matemáticas. Aparecen a menudo como la 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 los magmas de cuasigrupos , cuasicampos , anillos no asociativos y conmutativos no asociativos .

No asociatividad del cálculo de punto flotante

En matemáticas, la suma y la 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.

Para ilustrar esto, considere una representación de coma 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 una mantisa de 24 o 53 bits, 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.

Notación para operaciones no asociativas

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 comunes no asociativas. Esta 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 se evalúa convencionalmente de izquierda a derecha, es decir,

${\displaystyle \left.{\begin{matriz}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{matriz}}\right\}{\mbox{para todos}} w,x,y,z\en S}$

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

${\displaystyle \left.{\begin{matriz}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{matriz}}\right\}{\mbox{para todos}} w,x,y,z\en S}$

Se producen operaciones tanto asociativas por la izquierda como por la derecha. Las operaciones asociativas por la izquierda incluyen lo siguiente:

• Resta y división de números reales:

${\ estilo de visualización xyz = (xy) -z}$

${\ estilo de visualización x/y/z=(x/y)/z}$

• Aplicación de función:

${\ estilo de visualización (f \, x \, y) = ((f \, x) \, y)}$

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

Las operaciones asociativas por la derecha incluyen lo siguiente:

• 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 corchetes o asociativamente a la derecha porque una operación repetida de exponenciación asociativa a la izquierda es de poca utilidad. Las potencias repetidas se reescribirían principalmente con la multiplicación:

${\ estilo de visualización (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. Así, dada una expresión como , se evalúa primero el exponente completo de la base . Sin embargo, en algunos contextos, especialmente en la escritura a mano, la diferencia entre y puede ser difícil de ver. En tal caso, por lo general se implica la asociatividad por la derecha.${\ estilo de visualización 2^{x+3}}$${\ estilo de visualización 2^{(x+3)}}$${\ estilo de visualización x^{y^{z}}}$${\ estilo de visualización y^{z}}$${\ estilo de visualización x}$${\ estilo de visualización {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 xy=x\mapsto (y\mapsto xy)}$

El uso de la notación asociativa por 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:

${\displaystyle (x^{\cuña }y)^{\cuña }z\neq x^{\cuña }(y^{\cuña }z)}$

• Operadores de flecha hacia arriba de Knuth :

${\displaystyle a\flecha arriba \flecha arriba (b\flecha arriba \flecha arriba c)\neq (a\flecha arriba \flecha arriba b)\flecha arriba \flecha arriba c}$

${\ Displaystyle a \ flecha arriba \ flecha arriba \ flecha arriba (b \ flecha arriba \ flecha arriba \ flecha arriba c) \ neq (a \ flecha arriba \ flecha arriba \ flecha arriba b) \ flecha arriba \ flecha arriba \ flecha arriba c}$

• Tomando el producto cruz de tres vectores:

${\displaystyle {\vec {a}}\times ({\vec {b}}\times {\vec {c}})\neq ({\vec {a}}\times {\vec {b}}) \times {\vec {c}}\qquad {\mbox{ para algunos }}{\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{para todos}}x,y,z\in \ mathbb {R} {\mbox{ con }}x\neq z.}$

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

Historia

William Rowan Hamilton parece haber acuñado el término "propiedad asociativa" alrededor de 1844, una época en la que contemplaba el álgebra no asociativa de los Octonions que había aprendido de John T. Graves.

Ver también

• Prueba de asociatividad de Light
• Serie telescópica , el uso de la asociatividad adicional 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