Propiedad asociativa

Ajustar Compartir Imprimir Citar
Propiedad de una operación matemática

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, 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 en una fila 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:

()2+3)+4=2+()3+4)=92× × ()3× × 4)=()2× × 3)× × 4=24.{displaystyle {begin{aligned}(2+3)+4 limit=2+(3+4)=9,2times (3times 4) limit=(2times 3)times 4=24.end{aligned}}}

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, entonces 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 asociativo cuando este diagrama se comunica. Es decir, cuando los dos caminos de S×S×S a S compose a la misma función desde S×S×S a S.

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

()x Alternativa Sí.) z = x.Sí. Alternativa z) para todos x, Sí., z dentro 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 en la multiplicación.

()xSí.)z = x()Sí.z) xSí.z para todos x, Sí., z dentro 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 resultado en una celosía Tamari del orden cuatro, posiblemente diferentes productos.

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 maneras posibles:

Si la operación producto es asociativa, la ley asociativa generalizada dice que todas estas expresiones dará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 "the" producto se puede escribir sin ambigüedades como

abcd.

A medida que aumenta la cantidad de elementos, la cantidad 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 tanto, A ↔ (B ↔ C) es equivalente a (A ↔ B) ↔ C, pero A ↔ B ↔ C generalmente significa (A ↔ B) y (B ↔ C ), que no es equivalente.

Ejemplos

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

Algunos ejemplos de operaciones asociativas incluyen los siguientes.

  • La concatenación de las tres cuerdas "hello", " ", "world" puede ser computado concatenando las dos primeras cuerdas (dar "hello ") y apegar la tercera cadena ("world"), o al unirse a la segunda y tercera cadena (dar " 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 adición y multiplicación de números reales son asociativos; es decir,

    ()x+Sí.)+z=x+()Sí.+z)=x+Sí.+z()xSí.)z=x()Sí.z)=xSí.z}para todosx,Sí.,z▪ ▪ R.{displaystyle left.{begin{matrix}(x+y)+z=x+(y+z)=x+y+zquad \(x,y)z=x(y,z)=x,y,zqquad qquad quad quad quad ,end{matrix} {m} {R}.}

    Debido a la asociación, las paréntesis de agrupación pueden omitirse sin ambigüedad.
  • La operación trivial x Alternativa Sí. = x (es decir, el resultado es el primer argumento, no importa cuál sea el segundo argumento) es asociativo pero no conmutativo. Asimismo, la operación trivial x ∘ Sí. = Sí. (es decir, el resultado es el segundo argumento, no importa cuál sea el primer argumento) es asociativo pero no conmutativo.
  • La adición y multiplicación de números complejos y las cuaterniones son asociativas. La adición de octoniones también es asociativa, pero la multiplicación de octoniones no es asociativa.
  • El mayor divisor común y las múltiples funciones menos comunes actúan asociativamente.
    gcd⁡ ⁡ ()gcd⁡ ⁡ ()x,Sí.),z)=gcd⁡ ⁡ ()x,gcd⁡ ⁡ ()Sí.,z))=gcd⁡ ⁡ ()x,Sí.,z)lcm⁡ ⁡ ()lcm⁡ ⁡ ()x,Sí.),z)=lcm⁡ ⁡ ()x,lcm⁡ ⁡ ()Sí.,z))=lcm⁡ ⁡ ()x,Sí.,z)}para todosx,Sí.,z▪ ▪ Z.{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}
  • Tomando la intersección o la unión de conjuntos:
    ()A∩ ∩ B)∩ ∩ C=A∩ ∩ ()B∩ ∩ C)=A∩ ∩ B∩ ∩ C()A∪ ∪ B)∪ ∪ C=A∪ ∪ ()B∪ ∪ C)=A∪ ∪ B∪ ∪ C}para todos los juegosA,B,C.{displaystyle left.{begin{matrix}(Acap B)cap C=Acap (Bcap C)=Acap Bcap Cquad(Acup B)cup C=Acup (Bcup C)=Acup Bcup Cquadend{Matrix}} {mbox} {mbox}
  • Si M es un juego S denota el conjunto de todas las funciones de M a M, entonces el funcionamiento de la composición de la función en S es asociativo:
    ()f∘ ∘ g)∘ ∘ h=f∘ ∘ ()g∘ ∘ h)=f∘ ∘ g∘ ∘ hpara todosf,g,h▪ ▪ S.{displaystyle (fcirc g)circ h=fcirco (gcirc h)=fcirc gcirc hqquad {mbox{for all }f,g,hin S.}
  • Ligeramente más generalmente, dados cuatro sets M, N, P y Q, con h: M → N, g: N → P, y f: P → Q, entonces
    ()f∘ ∘ g)∘ ∘ h=f∘ ∘ ()g∘ ∘ h)=f∘ ∘ g∘ ∘ h{displaystyle (fcirc g)circ h=fcirco (gcirc h)=fcirc gcirc h}
    como antes. En resumen, la composición de mapas siempre es asociativa.
  • En la teoría de la categoría, la composición de los morfismos es asociativa por definición. La asociación de functores y transformaciones naturales se deriva de la asociatividad de los morfismos.
  • Considere un conjunto con tres elementos, A, B, y C. La siguiente operación:
    ×ABC
    AAAA
    BABC
    CAAA
    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 matriz representa la composición de la función, se puede concluir inmediatamente que la multiplicación de matriz es asociativa.
  • Para números reales (y para cualquier conjunto totalmente ordenado), la operación mínima y máxima es asociativa:
    max()a,max()b,c))=max()max()a,b),c)ymin()a,min()b,c))=min()min()a,b),c).{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 sustitución

En la lógica proposicional funcional de verdad estándar, asociación o 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:

()PAlternativa Alternativa ()QAlternativa Alternativa R)).. ()()PAlternativa Alternativa Q)Alternativa Alternativa R){displaystyle (Plor (Qlor R))Leftrightarrow ((Plor Q)lor R)}

y

()P∧ ∧ ()Q∧ ∧ R)).. ()()P∧ ∧ Q)∧ ∧ R),{displaystyle (Pland (Qland R))Leftrightarrow (Pland Q)land R),}

Donde.. {displaystyle Leftrightarrow"es un símbolo metalógico que representa "puede ser reemplazado en una prueba con".

Conectores funcionales de verdad

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 (y sus inversas, ya que ↔ es conmutativo) son tautologías veritativas funcionales.

Associative of disjunction
()()PAlternativa Alternativa Q)Alternativa Alternativa R)Administración Administración ()PAlternativa Alternativa ()QAlternativa Alternativa R)){displaystyle (Plor Q)lor R)leftrightarrow (Plor (Qlor R)}
Associatividad de la conjunción
()()P∧ ∧ Q)∧ ∧ R)Administración Administración ()P∧ ∧ ()Q∧ ∧ R)){displaystyle (Pland Q)land R)leftrightarrow (Pland (Qland R)}
Asociación de equivalencia
()()PAdministración Administración Q)Administración Administración R)Administración Administración ()PAdministración Administración ()QAdministración Administración R)){displaystyle (Pleftrightarrow Q)leftrightarrow R)leftrightarrow (Pleftrightarrow (Qleftrightarrow 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 Alternativa Alternativa {displaystyle *} en un set S que no satisface la ley asociativa se llama no asociativo. Simbólicamente,

()xAlternativa Alternativa Sí.)Alternativa Alternativa zل ل xAlternativa Alternativa ()Sí.Alternativa Alternativa z)para algunosx,Sí.,z▪ ▪ S.{displaystyle (x*y)*zneq x*(y*z)qquad {mbox{for some }}x,y,zin S.}

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

Sustracción
()5− − 3)− − 2ل ل 5− − ()3− − 2){displaystyle (5-3)-2,neq ,5-(3-2)}
División
()4/2)/2ل ل 4/()2/2){displaystyle (4/2)/2,neq ,4/(2/2)}
Exponentiation
2()12)ل ل ()21)2{displaystyle 2^{(1^{2}},neq ,(2^{1})^{2}
Vector cross product
i× × ()i× × j)=i× × k=− − j()i× × i)× × j=0× × j=0{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicrosoft} {fnMicrosoft Sans Serif} {fnMicrosoft} {f} {f} {f}cH00}cH00cH00}f} = '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)+⋯ ⋯ =0{displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+dots =0}
1+()− − 1+1)+()− − 1+1)+()− − 1+1)+()− − 1+1)+()− − 1+1)+()− − 1+1)+⋯ ⋯ =1.{displaystyle 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+ = 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 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 magmas de cuasigrupos, cuasicampos, anillos no asociativos y conmutativos no asociativos.

No asociatividad del cálculo de coma 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.0002× 20 + 1.0002× 20) + 1.0002× 24 = 1.0002× 21 + 1.0002× 24 = 1.0012× 24
1.0002× 20 + (1.0002× 20 + 1.0002× 24) = 1.0002× 20 + 1.0002× 24 = 1.0002× 24

Aunque la mayoría de las computadoras calculan con 24 o 53 bits de mantisa, 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, los paréntesis deben ser utilizados 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 23/4{displaystyle {dfrac {2}{3/4}}). Sin embargo, los matemáticos están de acuerdo en un orden particular de evaluación para varias operaciones comunes no asociativas. Esto es simplemente una convención notacional para evitar paréntesis.

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

xAlternativa Alternativa Sí.Alternativa Alternativa z=()xAlternativa Alternativa Sí.)Alternativa Alternativa zwAlternativa Alternativa xAlternativa Alternativa Sí.Alternativa Alternativa z=()()wAlternativa Alternativa x)Alternativa Alternativa Sí.)Alternativa Alternativa zetc.}para todosw,x,Sí.,z▪ ▪ S{displaystyle left.{begin{matrix}x*y*z=(x*y)*zqquad qquad quadquad ,w*x*y*z=(w*x)*y)*zquad \mbox{etc}}qquad qenddqqqqqqdqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqquad

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

xAlternativa Alternativa Sí.Alternativa Alternativa z=xAlternativa Alternativa ()Sí.Alternativa Alternativa z)wAlternativa Alternativa xAlternativa Alternativa Sí.Alternativa Alternativa z=wAlternativa Alternativa ()xAlternativa Alternativa ()Sí.Alternativa Alternativa z))etc.}para todosw,x,Sí.,z▪ ▪ S{displaystyle left.{begin{matrix}x*y*z=x*(y*z)qquad qquad quadquad ,w*x*y*z=w*(x*(y*z)quad \mbox{etc}}qquad qquad qquadqqdqqqqqqquadquad

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

Substracción y división de números reales
x− − Sí.− − z=()x− − Sí.)− − z{displaystyle x-y-z=(x-y)-z}
x/Sí./z=()x/Sí.)/z{displaystyle x/y/z=(x/y)/z}
Aplicación de funciones
()fxSí.)=()()fx)Sí.){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 la derecha incluyen lo siguiente:

Exponenciación de números reales en notación de superscript
xSí.z=x()Sí.z){displaystyle x^{y^{z}=x^{(y^{z}}}

La Exponenciación se utiliza comúnmente con corchetes o de derecha asociativamente porque una operación de exponentiación repetida asociativa izquierda es de poco uso. Los poderes repetidos serían reescritos principalmente con la multiplicación:

()xSí.)z=x()Sí.z){displaystyle (x^{y}=x^{(yz)}

Formado correctamente, el superscripto se comporta inherentemente como un conjunto de paréntesis; por ejemplo, en la expresión 2x+3{displaystyle 2^{x+3} la adición se realiza antes de la exponentiación a pesar de que no hay paréntesis explícitas 2()x+3){displaystyle 2^{(x+3)} envuelto alrededor. Así, dada una expresión como xSí.z{displaystyle x^{y^{z}}, el exponente completo Sí.z{displaystyle y^{z} de la base x{displaystyle x} se evalúa primero. Sin embargo, en algunos contextos, especialmente en la escritura, la diferencia entre xSí.z=()xSí.)z{displaystyle {x^{y}{z}=(x^{y}{z}} {f}}}, xSí.z=x()Sí.z){displaystyle x^{yz}=x^{(yz)} y xSí.z=x()Sí.z){displaystyle x^{y^{z}=x^{(y^{z}}} puede ser difícil de ver. En tal caso, la asociación correcta suele ser implícita.

Definición de función
Z→ → Z→ → Z=Z→ → ()Z→ → Z){displaystyle mathbb {Z} rightarrow mathbb {Z} rightarrow mathbb {Z} =mathbb {Z} rightarrow (mathbb {Z} rightarrow mathbb {Z}}}
x↦ ↦ Sí.↦ ↦ x− − Sí.=x↦ ↦ ()Sí.↦ ↦ x− − Sí.){displaystyle xmapsto ymapsto x-y=xmapsto (ymapsto x-y)}

Utilizar notación asociativa adecuada para estas operaciones puede ser motivada por la correspondencia Curry-Howard y por el isomorfismo currying.

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 de infijo
()x∧ ∧ Sí.)∧ ∧ zل ل x∧ ∧ ()Sí.∧ ∧ z){displaystyle (x^{wedge }y)}{wedge }zneq x^{wedge }(y^{wedge }z)}
Los operadores de arriba de Knuth
a↑ ↑ ↑ ↑ ()b↑ ↑ ↑ ↑ c)ل ل ()a↑ ↑ ↑ ↑ b)↑ ↑ ↑ ↑ c{displaystyle auparrow uparrow (buparrow uparrow c)neq (auparrow uparrow b)uparrow uparrow c}
a↑ ↑ ↑ ↑ ↑ ↑ ()b↑ ↑ ↑ ↑ ↑ ↑ c)ل ل ()a↑ ↑ ↑ ↑ ↑ ↑ b)↑ ↑ ↑ ↑ ↑ ↑ c{displaystyle auparrow uparrow uparrow (buparrow uparrow uparrow c)neq (auparrow uparrow b)uparrow uparrow uparrow c}
Tomando el producto de la cruz de tres vectores
a→ → × × ()b→ → × × c→ → )ل ل ()a→ → × × b→ → )× × c→ → para algunosa→ → ,b→ → ,c→ → ▪ ▪ R3{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicrosoft Sans Serif} {fnMicrosoft Sans {fnMicrosoft Sans} {fnMicrosoft Sans Serif} {fnMicrosoft} {fnMicrosoft} {f}f}f} {f}f}f}f}f}f}f}f}f}f}f}f}f}f}fnKf}fnMis}fnMis}f}f}fnMis}fnKf}fnMis}f}fnMisfnMis}fnMis}fnMis}fnMis}}fnMis}fnMisc}fnMiscf}fnMis
Tomando el promedio de pares de números reales
()x+Sí.)/2+z2ل ل x+()Sí.+z)/22para todosx,Sí.,z▪ ▪ Rconxل ل z.{displaystyle {(x+y)/2+z over 2}neq {x+(y+z)/2 over 2}qquad {mbox{for all }}x,y,zin mathbb {R} {mbox{ with }xneq z.}
Tomando el complemento relativo de los conjuntos
()A∖ ∖ B)∖ ∖ Cل ل A∖ ∖ ()B∖ ∖ C){displaystyle (Abackslash B)backslash Cneq Abackslash (Bbackslash C)}.

(Comparar la nonimplicación material en la lógica.)

Historia

William Rowan Hamilton parece haber acuñado el término "propiedad asociativa" 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.