Asociatividad (àlgebra)

Archiu:Associativity of binary operations (without question marks).svg

La asociatividad és una propietat en el àlgebra i la llògica proposicional que es complix, si donats tres o més elements qualsevol d'un conjunt determinat, es verifica que existix una operació: $⊚$ , que complixca l'igualtat:

a ⊚ (b ⊚ c) = (a ⊚ b) ⊚ c

És dir, en una expressió associativa en dos o més ocurrències seguides d'un mateix operador associatiu, l'orde en que s'eixecuten les operacions no altera el resultat, sempre i quan es mantinga intacta la seqüència dels operants. En atres paraules, reorganisar els paréntesis en una expressió associativa no canvia el seu valor final.

La suma i el producte d'número real complixen la propietat associativa, sent vàlides les igualtats:

a + (b + c) = (a + b) + c

per a la suma i per a la multiplicació:

a \cdot (b \cdot c) = (a \cdot b) \cdot c

En abdós, l'ubicació dels paréntesis no altera el resultat. Note's que els operants s'han mantingut en la seua posició original dins de l'expressió. Moltes operacions importants són no associatives, per eixemple la resta i la exponenciación. Les expressions que contenen tant operacions associatives com a operacions no associatives donen com resultat expressions no associatives.

No es deu confondre la asociatividad en la conmutatividad, la qual establix que sí es pot canviar l'orde dels operants sense afectar el resultat final.

Dins d'una expressió que continga dos o més aparicions seguides del mateix operador associatiu, l'orde en que es realisen les operacions no importa sempre que no es canvie la seqüència dels operants. És dir (despuix de reescriure l'expressió en paréntesis i en notació infija si és necessari), reordenar els paréntesis en dita expressió no canviarà el seu valor. Considerem les següents equacions:

$\begin{matrix} (2 + 3) + 4 & = 2 + (3 + 4) = 9 \\ 2 \times (3 \times 4) & = (2 \times 3) \times 4 = 24. \end{matrix}$

Encara que els paréntesis s'han reordenado en cada llínea, els valors de les expressions no s'han alterat. Ya que açò és cert quan es realisa la suma i la multiplicació de qualsevol número real, es pot dir que «la suma i la multiplicació d'número real són operacions associatives».

La asociatividad no és lo mateix que la conmutatividad, que es referix a si l'orde de dos operants afecta al resultat. Per eixemple, l'orde no importa en la multiplicació d'número real, és dir, $a \times b = b \times a$ , per lo que diem que la multiplicació d'número real és una operació conmutativa. No obstant, operacions com la composició de funcions i la multiplicació de matrius són associatives, pero (generalment) no conmutativas.

Les operacions associatives són abundants en matemàtiques; de fet, moltes estructures algebraiques (com semigrupos i categories) requerixen explícitament que les seues operacions binarias siguen associatives.

No obstant, moltes operacions importants i interessants no són associatives; alguns eixemples són la resta, la exponenciación i el producte vectorial creuat. En contrast en les propietats teòriques dels número real, la suma de números de menge flotant en informàtica no és associativa, i l'elecció de cóm associar una expressió pot tindre un efecte significatiu en el error de grosseig.

Definició

Formalment, una operació binaria Plantilla:Math sobre un conjunt Plantilla:Mvar es diu associativa si satisfà la llei associativa:

Plantilla:Math para tot Plantilla:Mvar, Plantilla:Mvar, Plantilla:Mvar en Plantilla:Mvar.}}

Ací, ∗ s'utilisa per a substituir el símbol de l'operació, que pot ser qualsevol símbol, i inclús l'absència de símbol (yuxtaposició) com per a la multiplicació.

Plantilla:Math para tot Plantilla:Mvar, Plantilla:Mvar, Plantilla:Mvar en Plantilla:Mvar.}}

La llei associativa també pot expressar-se aixina en notació funcional: Plantilla:Math.

Llei associativa generalisada

Si una operació binaria és associativa, l'aplicació repetida de l'operació produïx el mateix resultat independentment de cóm s'inserten els parells de paréntesis vàlits en l'expressió.^[1] és unívoc; és dir, s'obtindrà el mateix element independentment de cóm s'inserten els paréntesis en el producte. A açò se li crida llei associativa generalisada. Per eixemple, un producte de quatre elements pot escriure's, sense canviar l'orde dels factors, de cinc formes possibles:

Si l'operació producte és associativa, la llei associativa generalisada diu que totes estes expressions donaran el mateix resultat. Aixina que, a menos que l'expressió en paréntesis omés ya tinga un significat diferent (vejau més alvance), els paréntesis poden considerar-se innecessaris i «el» producte pot escriure's sense ambigüitat com

Plantilla:Math.

A mida que aumenta el número d'elements, el número de formes possibles d'insertar paréntesis creix ràpidament, pero seguixen sent innecessaris per a la desambiguación.

Un eixemple en el que açò no funciona és el bicondicional llògic Plantilla:Math És associatiu; per tant,

Plantilla:Math és equivalent a Plantilla:Math, pero Plantilla:Math més comunament significa {{math|(Plantilla:Var ↔ Plantilla:Var) i (Plantilla:Var ↔ Plantilla:Var), que no és equivalent.

Notació formal

Siga A un conjunt en el qual s'ha definit una operació binaria interna $⊚$ tal que

\begin{matrix} ⊚ : & A \times A & ⟶ & A \\ (a, b) & ⟼ & c = a ⊚ b \end{matrix}

Es diu que l'operació $⊚$ és associativa si:

\forall a, b, c \in A : a ⊚ (b ⊚ c) = (a ⊚ b) ⊚ c

La llei associativa també pot ser expressada en notació funcional aixina:

f (f (x, y), z) = f (x, f (y, z))

Suma i resta

Partint del conjunt dels número natural

ℕ = {1, 2, 3, 4, \dots}

per a l'operació suma, definida com:

\begin{matrix} + : & ℕ \times ℕ & ⟶ & ℕ \\ (a, b) & ⟼ & c = a + b \end{matrix}

$(ℕ, +)$ té la propietat associativa, ya que:

\forall a, b, c \in ℕ : a + (b + c) = (a + b) + c

Per eixemple:

5 + (3 + 2) = (5 + 3) + 2

No obstant, per a l'operació resta, definida com:

\begin{matrix} - : & ℕ \times ℕ & ⟶ & ℕ \\ (a, b) & ⟼ & c = a - b \end{matrix}

$(ℕ, -)$ no té la propietat associativa, ya que:

\forall a, b, c \in ℕ : a - (b - c) \neq (a - b) - c

Per eixemple:

5 - (3 - 2) \neq (5 - 3) - 2

Eixemples

La concatenació de les cadenes de caràcters «hola», « », «món» es pot computar concatenant les primeres dos cadenes de caràcters (resultant en «hola ») i després la tercera cadena de caràcters («món»), o alternativament, unint la segona i tercera cadena de caràcters (resultant en « món») i concatenant la primera cadena de caràcters («hola») en eixe resultat. Els dos métodos produïxen el mateix resultat final. La concatenació de cadenes de caràcters és associativa (pero no és conmutativa). En aritmètica, la adició i la multiplicació d'número real són associatives. Pel seu asociatividad, l'agrupació per paréntesis pot ser omesa sense ambigüitat. Açò és,

\begin{matrix} (x + y) + z = x + (y + z) = x + y + z \\ (x y) z = x (y z) = x y z \end{matrix}} para todo x, y, z \in ℝ .

Un eixemple de la asociatividad de la suma és:

(2 + 3) + 7 = 5 + 7 = 12 = 2 + (3 + 7) = 2 + 10 = 12

i de la asociatividad de la multiplicació

(2 \cdot 3) \cdot 7 = 6 \cdot 7 = 42 = 2 \cdot (3 \cdot 7) = 2 \cdot 21 = 42

No obstant, la resta no és associativa,

2 - (3 - 1) = 0 \neq (2 - 3) - 1 = - 2

i tampoc ho és la divisió,

(4 : 2) : 2 = 1 \neq 4 : (2 : 2) = 4

.

ni la exponenciación, que és igualment no associativa

2^{(2^{3})} = 2^{8} = 256 \neq (2^{2})^{3} = 4^{3} = 64

L'adició i multiplicació de número complejo i cuaterniones són associatives. L'adició d'octoniones també és associativa, pero la multiplicació de octoniones és no associativa. Les funcions màxim comú divisor i mínim comú múltiple actuen de forma associativa.

\begin{matrix} mcd (mcd (x, y), z) = mcd (x, mcd (y, z)) = mcd (x, y, z) \\ mcm (mcm (x, y), z) = mcm (x, mcm (y, z)) = mcm (x, y, z) \end{matrix}} para todo x, y, z \in ℤ .

La intersecció o la unió de conjunts són associatives.

\begin{matrix} (A \cap B) \cap C = A \cap (B \cap C) = A \cap B \cap C \\ (A \cup B) \cup C = A \cup (B \cup C) = A \cup B \cup C \end{matrix}} para todos los conjuntos A, B, C .

SI M és algun conjunt i S denota el conjunt de totes les cunciones de M a M, llavors l'operació de composició funcional sobre S és associativa.

(f \circ g) \circ h = f \circ (g \circ h) = f \circ g \circ h para todo f, g, h \in S .

Més generalment, daus quatre conjunts M, N, P i Q, en h: M a N, g: N a P, i f: P a Q, llavors

(f \circ g) \circ h = f \circ (g \circ h) = f \circ g \circ h

tal com en l'eixemple anterior. En resum, la composició d'aplicacions sempre és associativa.

Per a un conjunt en tres elements A, B, i C, la següent operació és associativa.

×	A ! href="regles de tongada" \|B	C
A \|A \|A \|-	B	B	C
C	A \| href="Conectiva_llògica" \|A \|- href="Funció_de_veritat"

D'esta manera, per eixemple, A(BC)=(AB)C = A. Esta operació no és conmutativa.

Ya que les matrius representen funcions de transformació llineal, en la multiplicació matricial representant composició funcional, es pot concloure immediatament que la multiplicació matricial és associativa.^[2]

En llògica proposicional

Regla de Tongada

En la llògica proposicional estàndart, la associació,^[3]^[4] o asociatividad^[5] són dos regles de tongada vàlides. Estes regles permeten moure els paréntesis en expressions llògiques usades en proves llògiques. Les regles són:

(P \lor (Q \lor R)) \Leftrightarrow ((P \lor Q) \lor R)

(P \land (Q \land R)) \Leftrightarrow ((P \land Q) \land R)

a on « $\Leftrightarrow$ » és un símbol metalógico que representa «pot ser reemplaçat en una prova per».

Conectivas de funcions de veres

Asociatividad és una propietat d'algunes conectivas llògiques en les funciones de veres de la llògica proposicional. Les següents #equivalència llògiques demostren que la asociatividad és una propietat de conectivas llògiques particulars. Són aixina mateix tautologias de funcions de veres.

Asociatividad de la disjunció:

((P \lor Q) \lor R) \leftrightarrow (P \lor (Q \lor R))

(P \lor (Q \lor R)) \leftrightarrow ((P \lor Q) \lor R)

Asociatividad de la conjunció:

((P \land Q) \land R) \leftrightarrow (P \land (Q \land R))

(P \land (Q \land R)) \leftrightarrow ((P \land Q) \land R)

Asociatividad de l'equivalència:

((P \leftrightarrow Q) \leftrightarrow R) \leftrightarrow (P \leftrightarrow (Q \leftrightarrow R))

(P \leftrightarrow (Q \leftrightarrow R)) \leftrightarrow ((P \leftrightarrow Q) \leftrightarrow R)

La negació conjunta és un eixemple de conectivo funcional de veres que no és associatiu.

Operació no associativa

Una operació binaria $*$ sobre un conjunt S que no satisfà la llei associativa es denomina no associativa'. Simbòlicament,

$(x * y) * z \neq x * (y * z) para algunos x, y, z \in S .$

Per a una operació d'este tipo, l'orde d'evaluació sí importa. Per eixemple:

Substracció: $(5 - 3) - 2 \neq 5 - (3 - 2)$
Divisió: $(4 / 2) / 2 \neq 4 / (2 / 2)$
Exponenciación: $2^{(1^{2})} \neq (2^{1})^{2}$
Producte vectorial: $\begin{matrix} 𝐢 \times (𝐢 \times 𝐣) & = 𝐢 \times 𝐤 = - 𝐣 \\ (𝐢 \times 𝐢) \times 𝐣 & = 𝟎 \times 𝐣 = 𝟎 \end{matrix}$

Ademés, encara que la suma és associativa per a sumes finitas, no ho és dins de sumes infinites (séries). Per eixemple,

$(1 + - 1) + (1 + - 1) + (1 + - 1) + (1 + - 1) + (1 + - 1) + (1 + - 1) + \dots = 0$ mentres que $1 + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + \dots = 1.$ Algunes operacions no associatives són fonamentals en matemàtiques. Apareixen a sovint com la multiplicació en estructures anomenades #àlgebra no associatives, que tenen també una suma i una multiplicació escalar. Alguns eixemples són els octoniones i les #àlgebra de Lie. En les #àlgebra de Lie, la multiplicació satisfà la identitat de Jacobi en lloc de la llei associativa; açò permet abstraure la naturalea algebraica de les transformacions infinitesimals.

Atres eixemples són els cuasigrupos, cuasicuerpos, anells no associatius i #magma no associatius conmutativos.

No-asociatividad del càlcul en menge flotant

En matemàtiques, la suma i multiplicació d'número real és associativa. En canvi, en informàtica, la suma i multiplicació de números de menge flotant no és associativa, ya que s'introduïxen errors de grosseig quan s'unixen valors de tamanys distints.^[6]

Per a ilustrar açò, considere una representació en menge flotant en un mantissa de 4 bits:

(1.000₂×2⁰ + 1.000₂×2⁰) + 1.000₂×2⁴ = 1.000₂×2^{Plantilla:Fontcolor} + 1.000₂×2⁴ = 1.00Plantilla:Fontcolor₂×2⁴

1.000₂×2⁰ + (1.000₂×2⁰ + 1.000₂×2⁴) = 1.000₂×2^{Plantilla:Fontcolor} + 1.000₂×2⁴ = 1.00Plantilla:Fontcolor₂×2⁴

Encara que la majoria dels ordenadors calculen en 24 o 53 bits de mantissa,^[7] esta és una font important d'error de grosseig, i enfocaments com el algoritme de suma de Kahan són formes de minimisar els errors. Pot ser especialment problemàtic en computació paralela.^[8]

Vore també

Referències

↑ Durbin, John R. (1992). Modern Algebra: an Introduction, 3rd edició, New York: Wiley, p. 78. ISBN 978-0-471-51001-7. «If $a_{1}, a_{2}, \dots, a_{n} (n \geq 2)$ llaure elements of a set with an associative operation, then the product $a_{1} a_{2} \dots a_{n}$ is unambiguous; this is, the same element will be obtained regardless of how parentheses llaure inserted in the product.»
↑ «Matrix product associativity». Khan Academy. Consultat el 5 de juny de 2016.
↑ Moore and Parker
↑ Copi and Cohen
↑ Hurley
↑ Knuth, Donald, The Art of Computer Programming, Volum 3, secció 4.2.2
↑ IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic. ISBN 978-0-7381-5753-5.
↑ Goldberg, David. “What Every Computer Scientist Should Know About Floating-Point Arithmetic”. ACM Computing Surveys 23 (1): 5–48. doi:10.1145/103162.103163.

Referències

Este artícul conté una traducció derivada de «Asociatividad (álgebra)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Durbin, John R. (1992). Modern Algebra: an Introduction, 3rd edició, New York: Wiley, p. 78. ISBN 978-0-471-51001-7. «If $a_{1}, a_{2}, \dots, a_{n} (n \geq 2)$ llaure elements of a set with an associative operation, then the product $a_{1} a_{2} \dots a_{n}$ is unambiguous; this is, the same element will be obtained regardless of how parentheses llaure inserted in the product.»

[2] «Matrix product associativity». Khan Academy. Consultat el 5 de juny de 2016.

[3] Moore and Parker

[4] Copi and Cohen

[5] Hurley

[6] Knuth, Donald, The Art of Computer Programming, Volum 3, secció 4.2.2

[7] IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic. ISBN 978-0-7381-5753-5.

[Goldberg_1991-8] Goldberg, David. “What Every Computer Scientist Should Know About Floating-Point Arithmetic”. ACM Computing Surveys 23 (1): 5–48. doi:10.1145/103162.103163.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

×	A ! href="regles de tongada" \|B	C
A \|A \|A \|-	B	B	C
C	A \| href="Conectiva_llògica" \|A \|- href="Funció_de_veritat"