stringtranslate.com

Propiedad asociativa

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

En una expresión que contiene dos o más ocurrencias seguidas del mismo operador asociativo, el orden en el que se realizan las operaciones no importa siempre que no se modifique 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:

Aunque los paréntesis se reordenaron en cada línea, los valores de las expresiones no se modificaron. Como esto es cierto cuando se realizan sumas y multiplicaciones de números reales , 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 se ocupa de si el orden de dos operandos afecta al 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 son abundantes en matemáticas; de hecho, muchas estructuras algebraicas (como los semigrupos y las 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 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 ∗ sobre el conjunto S es asociativa cuando este diagrama conmuta . Es decir, cuando los dos caminos de S × S × S a S forman la misma función de S × S × S a S .

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

, para todos 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 en la multiplicación .

, para todos en S.

La ley asociativa también se puede expresar en notación funcional de la siguiente manera:

Derecho asociativo generalizado

En ausencia de la propiedad asociativa, cinco factores a , b , c , d , e dan como resultado 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 cuántos pares de paréntesis válidos se inserten en la expresión. [2] Esto se denomina ley asociativa generalizada .

El número de corchetes posibles es simplemente el número catalán , , para n operaciones sobre n+1 valores. Por ejemplo, un producto de 3 operaciones sobre 4 elementos se puede escribir (ignorando las permutaciones de los argumentos), de las siguientes maneras:

Si la operación del producto es asociativa, la ley asociativa generalizada dice que todas estas expresiones darán el mismo resultado. Por lo tanto, a menos que la expresión con los 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 medida que aumenta el número de elementos, el número de formas posibles de insertar paréntesis crece rápidamente, pero siguen siendo innecesarias para la desambiguación.

Un ejemplo en el que esto no funciona es el bicondicional lógico . Es asociativo; por lo tanto, A ↔ ( BC ) es equivalente a ( AB ) ↔ C , pero ABC significa más comúnmente ( AB ) y ( BC ) , que no son equivalentes.

Ejemplos

La suma de números reales es asociativa.

Algunos ejemplos de operaciones asociativas incluyen los siguientes.

Lógica proposicional

Regla de reemplazo

En la lógica proposicional veritativo-funcional 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 demostraciones lógicas . Las reglas (usando la notación de conectivos lógicos ) son:

y

donde " " es un símbolo metalógico que representa "puede reemplazarse en una prueba con".

Conectivas funcionales de la verdad

La asociatividad es una propiedad de algunos conectivos lógicos de la lógica proposicional veritativo-funcional . Las siguientes equivalencias lógicas demuestran que la asociatividad es una propiedad de conectivos particulares. Las siguientes (y sus recíprocas, ya que es conmutativa) son tautologías veritativo-funcionales . [ cita requerida ]

Asociatividad de la disyunción
Asociatividad de la conjunción
Asociatividad de equivalencia

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 satisface la ley asociativa se denomina no asociativa . Simbólicamente,

Para una operación de este tipo, el orden de evaluación importa. Por ejemplo:

Sustracción
División
Exponenciación
Producto vectorial

Además, aunque la adición es asociativa para sumas finitas, no es asociativa dentro de sumas infinitas ( series ). Por ejemplo, mientras que

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 adición y una multiplicación escalar . Algunos ejemplos son los octoniones y las álgebras de Lie . En las á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 punto flotante

En matemáticas, la suma y multiplicación de números reales son asociativas. En cambio, en informática, la suma y multiplicación de números de punto flotante no son asociativas, ya que pueden introducirse distintos errores de redondeo cuando se unen valores de distinto tamaño en un orden diferente. [7]

Para ilustrar esto, considere una representación de punto flotante con un significado de 4 bits :

(1.000 2 ×2 0 + 1.000 2 ×2 0 ) + 1.000 2 ×2 4 = 1.000 2 ×2 1 + 1.000 2 ×2 4 = 1.00 1 2 ×2 4
1,000 2 ×2 0 + (1,000 2 ×2 0 + 1,000 2 ×2 4 ) = 1,000 2 ×2 0 + 1,000 2 ×2 4 = 1,00 0 2 ×2 4

Aunque la mayoría de las computadoras calculan con 24 o 53 bits de mantisa, [8] esto sigue siendo 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. [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 están de acuerdo en un orden particular de evaluación para varias operaciones no asociativas comunes. Esto es simplemente una convención de notación para evitar los 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,

Mientras que una operación asociativa derecha se evalúa convencionalmente de derecha a izquierda:

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

Resta y división de números reales [11] [12] [13] [14] [15]
Aplicación de funciones

Esta notación puede estar motivada por el isomorfismo de curry , que permite una aplicación parcial.

Las operaciones asociativas por la derecha incluyen las siguientes:

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

La exponenciación se utiliza habitualmente con corchetes o asociativamente por la derecha porque una operación de exponenciación repetida por la izquierda es de poca utilidad. Las potencias repetidas se reescribirían en su mayoría con multiplicación:

Si se formatea correctamente, 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. Por lo tanto, dada una expresión como , el exponente completo de la base se evalúa primero. Sin embargo, en algunos contextos, especialmente en escritura a mano, la diferencia entre , y puede ser difícil de ver. En tal caso, la asociatividad por la derecha suele estar implícita.

Definición de función

El uso de la notación asociativa derecha para estas operaciones puede estar motivado por la correspondencia 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 [16]
Operadores de flecha hacia arriba de Knuth
Tomando el producto vectorial de tres vectores
Tomando el promedio por pares de números reales
Tomando el complemento relativo de conjuntos
.

(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, una época en la que estaba contemplando el álgebra no asociativa de los octoniones que había aprendido de John T. Graves . [18]

Véase también

Referencias

  1. ^ Hungerford, Thomas W. (1974). Álgebra (1.ª ed.). Springer . pág. 24. ISBN 978-0387905181. Definición 1.1 (i) a(bc) = (ab)c para todos a, b, c en G.
  2. ^ Durbin, John R. (1992). Álgebra moderna: una introducción (3.ª ed.). Nueva York: Wiley. pág. 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.
  3. ^ "Asociatividad de productos matriciales". 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. pág. 321. ISBN 9781259690877.
  5. ^ Copi, Irving M.; Cohen, Carl; McMahon, Kenneth (2014). Introducción a la lógica (14.ª ed.). Essex: Pearson Education. pág. 387. ISBN 9781292024820.
  6. ^ Hurley, Patrick J.; Watson, Lori (2016). Una introducción concisa a la lógica (13.ª ed.). Boston: Cengage Learning. pág. 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 punto 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 punto flotante en los cálculos numéricos en sistemas multiproceso masivos (PDF) , archivado desde el original (PDF) el 15 de febrero de 2013 , consultado el 8 de abril de 2014
  10. ^ Goldberg, David (marzo de 1991). "What Every Computer Scientist Should Know About Floating-Point Arithmetic" (PDF) . Encuestas de computación de la 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 operaciones aritméticas"
  12. ^ "El orden de las operaciones". Lugar de Educación.
  13. ^ "El orden de las operaciones", marca de tiempo 5m40s. Khan Academy .
  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. ^ Exponenciación Asociatividad y Notación Matemática Estándar Codeplea. 23 de agosto de 2016. Consultado el 20 de septiembre de 2016.
  17. ^ Hamilton, WR (1844–1850). "Sobre los cuaterniones o un nuevo sistema de imaginarios en álgebra". Colección de David R. Wilkins. Philosophical Magazine . Trinity College Dublin .
  18. ^ Baez, John C. (2002). "Los octoniones" (PDF) . Boletín de la American Mathematical Society . 39 (2): 145–205. arXiv : math/0105155 . doi :10.1090/S0273-0979-01-00934-X. ISSN  0273-0979. MR  1886087. S2CID  586512.