MATEMÁTICAS ELEMENTALES

ÁLGEBRA ELEMENTAL

propiedad asociativa ^[1] es una propiedad de algunas operaciones binarias . En lógica proposicional , la asociatividad es una regla válida de reemplazo para expresionesen pruebas lógicas .

Dentro de una expresión que contiene dos o más apariciones 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 de infijo si es necesario) reorganizar los paréntesis en dicha expresión no cambiará su valor. Considera 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 cuando se realizan sumas y multiplicaciones en cualquier número real , se puede decir que "la suma y 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 cambia o no 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.

Las operaciones asociativas son abundantes 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 son no asociativas; algunos ejemplos incluyen la resta , la exponenciación y el producto cruzado vectorial . En contraste con las propiedades teóricas de los números reales, la adición de números de punto flotante en ciencias de la computación 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 [ editar ]

Una operación binaria ∗ en el conjunto S es asociativa cuando se conmuta este diagrama . Es decir, cuando los dos caminos de S × S × Sa S componen 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 puede expresarse en notación funcional por lo tanto: f ( f ( x , y ), z ) = f ( x , f ( y , z )) .

Ley asociativa generalizada [ editar ]

En ausencia de la propiedad asociativa, cinco factores a, b, c, d, e resultan en 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 cómo se inserten pares de paréntesis válidos en la expresión. ^[2]Esto se llama la ley asociativa generalizada . Por ejemplo, se puede escribir un producto de cuatro elementos. Sin cambiar el orden de los factores, de cinco maneras 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 a continuación), los paréntesis pueden considerarse innecesarios y "el" producto puede escribirse de forma inequívoca 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 innecesarios para la desambiguación.

Un ejemplo donde esto no funciona es la lógica bicondicional. $${\ displaystyle \ leftrightarrow}. Es asociativa, por lo tanto A$${\ displaystyle \ leftrightarrow}(SEGUNDO$${\ displaystyle \ leftrightarrow}C) es equivalente a (A$${\ displaystyle \ leftrightarrow}SEGUNDO)$${\ displaystyle \ leftrightarrow}C, pero A$${\ displaystyle \ leftrightarrow}segundo$${\ displaystyle \ leftrightarrow}C más comúnmente significa (A$${\ displaystyle \ leftrightarrow}B y B$${\ displaystyle \ leftrightarrow}C), que no es equivalente.

Ejemplos [ editar ]

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 {para todos}} x, y, z \ in \ mathbb {R }.}

Debido a la asociatividad, los paréntesis de agrupación pueden omitirse 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 multiplicación de números complejos y cuaterniones son asociativos. La adición de octonionestambién es asociativa, pero la multiplicación de octoniones no es asociativa.
• El mayor divisor común y las funciones múltiples menos comunes actúan de manera asociativa.

$${\ 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 {para todos}} 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 {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 la composición de la función 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 \ en 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:

×	UNA	segundo	do
UNA	UNA	UNA	UNA
segundo	UNA	segundo	do
do	UNA	UNA	UNA

es asociativa 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. ^[3]

La lógica proposicional [ editar ]

Regla de reemplazo [ editar ]

En la lógica proposicional funcional de verdad estándar, asociación , ^[4] [5] o 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 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),}

dónde "$${\ displaystyle \ Leftrightarrow}"es un símbolo metalógico que representa" se puede reemplazar en una prueba con ".

Conectivos funcionales de la verdad [ editar ]

La asociatividad es una propiedad de algunos conectivos lógicos de la lógica proposicional funcional a la verdad . Las siguientes equivalencias lógicas demuestran que la asociatividad es una propiedad de conectivos particulares. Las siguientes son tautologías de verdad funcional . ^[7]

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 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 [ editar ]

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

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

• Exposiciónció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

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

El estudio de las estructuras no asociativas surge por 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 álgebras de Lie . Allí la ley asociativa es reemplazada por la identidad jacobi . Las álgebras de la mentira resumen 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 específicas o áreas como las matemáticas combinatorias . Otros ejemplos son cuasigrupo , Quasifield , anillo no asociativo , álgebra no asociativo y magmas no asociativos conmutativos .

Nonassociativity de cálculo de punto flotante [ editar ]

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 punto flotante no es asociativa, ya que los errores de redondeo se introducen cuando se unen valores de tamaño diferente. ^[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.00 0 ₂ × 2 ⁴ = 1.00 0₂ × 2 ⁴

Aunque la mayoría de las computadoras computan con 24 o 53 bits de mantisa, ^[9] esta es una fuente importante de error de redondeo, y los enfoques como el algoritmo de suma de Kahan son formas de minimizar los errores. Puede ser especialmente problemático en computación paralela. ^[10] [11]

Notación para operaciones no asociativas [ editar ]

Artículo principal: asociatividad de operadores

En general, los paréntesis deben usarse 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$${\ displaystyle {\ dfrac {2} {3/4}}}). 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.

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 {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 {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 {para todos}} w, x, y, z \ en S}

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

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

$${\ displaystyle xyz = (xy) -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 ser motivada por el isomorfismo del curry .

Las operaciones asociativas por derecho incluyen lo siguiente:

• Exposición de números reales en notación superíndice:

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

Una razón por la que la exponenciación en general se usa a menudo de forma asociativa por la derecha es que una operación de exponenciación asociativa por la izquierda repetida sería menos útil. Las apariencias múltiples podrían (y serían) reescritas con la multiplicación:

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

Un argumento específico para la notación de superíndice de exponenciación asociativa a la derecha es que el superíndice se comporta inherentemente como un conjunto de paréntesis si se formatea correctamente; por ejemplo, en la expresión$${\ displaystyle 2 ^ {x + 3}}la adición se realiza antes de la exponencia, a pesar de que no hay paréntesis explícitos$${\ displaystyle 2 ^ {(x + 3)}}Envuelto alrededor de él. Así dada una expresión tal como$${\ displaystyle x ^ {y ^ {z}}}, tiene sentido requerir evaluar el exponente completo $${\ displaystyle y ^ {z}} de la base $${\ displaystyle x}primero. Sin embargo, la diferencia entre$${\ displaystyle x ^ {y ^ {z}} = x ^ {(yz)}} y $${\ displaystyle {x ^ {y}} ^ {z} = {(x ^ {y})} ^ {z}}Es difícil de ver, especialmente en la escritura a mano.

• Definición de la 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 correcta para estas operaciones puede estar motivado por la correspondencia de Curry-Howard y por el isomorfismo de curry .

Las operaciones no asociativas para las cuales no se define un orden de evaluación convencional incluyen lo siguiente.

• Exposició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 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}

usw.

• 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 {para algunos}} {\ vec {a}}, {\ vec {b}}, {\ vec {c}} \ in \ mathbb {R} ^ {3}}

• Tomando el promedio por pares de los números reales:

$${\ displaystyle {(x + y) / 2 + z \ sobre 2} \ neq {x + (y + z) / 2 \ sobre 2} \ qquad {\ mbox {para todos}} x, y, z \ in \ mathbb {R} {\ mbox {con}} x \ neq z.}

• Tomando el complemento relativo de conjuntos.$${\ displaystyle (A \ backslash B) \ backslash C} no es lo mismo que $${\ displaystyle A \ backslash (B \ backslash C)}. (Comparar material no implícito en lógica.)