Propietat associativa

En matemàtiques, l'associativitat o propietat associativa^[1] és una propietat que pot tenir una operació binària. Significa que quan una expressió conté dos o més elements seguits dels mateixos operadors associatius, l'ordre de les operacions no altera el resultat, sempre que no es modifiqui la seqüència dels operands. És a dir, canviar els parèntesis en una expressió no modifica el resultat. Per exemple

(5+2)+1=5+(2+1)=8

Tot i que els parèntesis han estat canviats, el resultat de l'expressió no ha estat alterat. Com que la suma de nombres reals satisfà aquesta propietat, diem que "la suma de nombres reals és una operació associativa".

L'associativitat no ha de ser confosa amb la commutativitat. La commutativitat permet canviar l'ordre o la seqüència dels operands de l'expressió, metre que l'associativitat no ho permet. Per exemple,

(5+2)+1=5+(2+1)

és un exemple d'associativitat perquè els parèntesis han estat canviats (i per tant l'ordre en què s'efectuen les operacions), mentre que els operands 5, 2 i 1 apareixen en el mateix ordre d'esquerra a dreta a l'expressió. En canvi

(5+2)+1=(2+5)+1

no és un exemple d'associativitat, sinó que de commutativitat, perquè la seqüència de l'operand canvia quan el 2 i el 5 intercanvien les posicions.

Les operacions associatives són abundants en matemàtiques, i de fet la majoria de les estructures algebraiques requereixen explícitament que les seves operacions binàries siguin associatives. Tanmateix, moltes operacions destacades són no-associatives; un exemple estàndard és el del producte vectorial.

Definició

Formalment, una operació binària $*\!\!\!$ en un conjunt S s'anomena associativa si satisfà la propietat associativa:

(x*y)*z=x*(y*z)\qquad {\mbox{per a tots }}x,y,z\in S.

L'ordre en què s'efectuen les operacions no afecta el valor de les expressions, i es pot veure que succeeix el mateix per a expressions que contenen qualsevol nombre d'operacions $*\!\!\!$ . Així, quan $*\!\!\!$ és associativa, no cal especificar l'ordre en què s'efectuen les operacions i es poden ometre els parèntesis sense caure en una ambigüitat. Així, es pot escriure simplement

x*y*z.\,

Tanmateix, és important destacar que canviar l'ordre en què s'efectuen les operacions no implica que es pugui canviar les operacions pròpiament tot movent els operands en l'expressió.

Notació formal

Sigui A un conjunt en el qual s'ha definit una operació binària interna $\circledcirc$ tal que

{\begin{array}{rccl}\circledcirc :&A\times A&\longrightarrow &A\\&(a,b)&\longmapsto &c=a\circledcirc b\end{array}}

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

\forall a,b,c\in A\;:\quad a\circledcirc (b\circledcirc c)=(a\circledcirc b)\circledcirc c

També es pot expressar la llei associativa en notació funcional de la següent manera:

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

Suma i resta

Partint del conjunt dels nombres naturals

\mathbb {N} =\{1,2,3,4,\dots \}

per a l'operació suma, definida com:

{\begin{array}{rccl}+:&\mathbb {N} \times \mathbb {N} &\longrightarrow &\mathbb {N} \\&(a,b)&\longmapsto &c=a+b\end{array}}

$(\mathbb {N} ,+)\,$ té la propietat associativa, atès que:

\forall a,b,c\in \mathbb {N} \;:\quad a+(b+c)=(a+b)+c

Per exemple:

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

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

{\begin{array}{rccl}-:&\mathbb {N} \times \mathbb {N} &\longrightarrow &\mathbb {N} \\&(a,b)&\longmapsto &c=a-b\end{array}}

$(\mathbb {N} ,-)\,$ no té la propietat associativa, atès que:

\forall a,b,c\in \mathbb {N} \;:\quad a-(b-c)\neq (a-b)-c

Per exemple:

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

En lògica proposicional

Regla de reemplaçament

En la lògica proposicional estàndard, l'associació,^[2]^[3] o associativitat^[4] són dues regles de reemplaçament vàlides. Aquestes regles permeten moure els parèntesis en expressions lògiques utilitzades en demostracions lò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)

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

Connectives funcionals de veritat

L'associativitat és una propietat d'algunes connectives lògiques en les funcions de veritat de la lògica proposicional. Les següents equivalències lògiques demostren que l'associativitat és una propietat de connectives lògiques particulars. Són, així mateix, tautologies de funcions de veritat.

Associativitat 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)

Associativitat 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)

Associativitat 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 exemple de connectiva funcional de veritat que no és associativa.

Exemples

Els següents són alguns exemples d'operacions associatives.

En aritmètica, la suma i la multiplicació de nombres reals és associativa. És a dir :

\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{per a tots }}x,y,z\in \mathbb {R} .

La suma i multiplicació de nombres complexos i quaternions és associativa. La suma d'octonions també és associativa, però el producte d'octonions és no-associativa.

El màxim comú divisor i el mínim comú múltiple són funcions associatives.

\left.{\begin{matrix}\operatorname {MCD} (\operatorname {MCD} (x,y),z)=\operatorname {MCD} (x,\operatorname {MCD} (y,z))=\operatorname {MCD} (x,y,z)\ \quad \\\operatorname {mcm} (\operatorname {mcm} (x,y),z)=\operatorname {mcm} (x,\operatorname {mcm} (y,z))=\operatorname {mcm} (x,y,z)\quad \end{matrix}}\right\}{\mbox{ per a tots }}x,y,z\in \mathbb {Z} .

Com que les transformacions lineals són funcions que poden ésser representades per multiplicacions de matriu, les quals representen la composició funcional, es pot deduir directament que la multiplicació de matrius és associativa.

La intersecció de la unió de conjunts és associativa:

\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{per a tots els conjunts }}A,B,C.

Si M és un conjunt i S denota el conjunt de totes les funcions d'M a M, aleshores la composició funcional en S és associativa:

(f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h\qquad {\mbox{per a tots }}f,g,h\in S.

Una mica més generalment, donats quatre conjunts M, N, P i Q, tals que h: M a N, g: N a P, i f: P a Q, aleshores

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

com abans. En resum, la composició d'aplicacions sempre és associativa.

Si es considera un conjunt amb tres elements A, B, i C. La següent operació és associativa:

×	A	B	C
+
A	A	A	A
B	A	B	C
C	A	A	A

Així, per exemple, A(BC)=(AB)C. Aquesta aplicació no és commutativa.

Com que les matrius representen funcions de transformació lineal, amb la multiplicació matricial representant composició funcional, es pot concloure immediatament que la multiplicació de matrius és associativa.^[5]

No-associativitat

Una operació binària $*$ en un conjunt S que no satisfà la propietat associativa se l'anomena no-associativa.^[6] Simbòlicament,

(x*y)*z\neq x*(y*z)\qquad {\mbox{per alguns }}x,y,z\in S.

Per una operació com aquesta, l'ordre en què s'efectuen les operacions sí que influeix en el resultat. La resta, la divisió i l'exponenciació són exemples destacats d'operacions no associatives:

{\begin{matrix}(5-3)-2\neq 5-(3-2)\quad \\(4/2)/2\neq 4/(2/2)\qquad \qquad \\2^{(1^{2})}\neq (2^{1})^{2}.\quad \qquad \qquad \end{matrix}}

En general, els parèntesis s'usen per indicar l'ordre en què s'efectuen les operacions si una operació no-associativa apareix més d'una vegada en una expressió. Tanmateix, els matemàtics en general es posen d'acord en un ordre preestablert en diverses operacions no-associatives. Això no és més que una convenció sintàctica per tal d'evitar haver d'escriure parèntesis.

Una operació associativa per l'esquerra és una operació no-associativa que per convenció s'avalua d'esquerra a dreta. Per exemple:

\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{per a tots }}w,x,y,z\in S

mentre que una operació associativa per la dreta és una operació que s'avalua de dreta a esquerra per convenció:

\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{per a tots }}w,x,y,z\in S

Existeixen casos d'operacions associatives tant per l'esquerra com per la dreta. Més endavant se'n mostren alguns exemples.

Més exemples

Algunes operacions associatives per l'esquerra:

Resta i divisió de nombres naturals:

x-y-z=(x-y)-z\qquad {\mbox{per a tots }}x,y,z\in \mathbb {R} ;

x/y/z=(x/y)/z\qquad \qquad \quad {\mbox{per a tots }}x,y,z\in \mathbb {R} {\mbox{ on }}y\neq 0,z\neq 0.

Algunes operacions associatives per la dreta:

Exponenciació de nombres reals:

x^{y^{z}}=x^{(y^{z})}.\,

La raó per la qual l'exponenciació és associativa per la dreta és perquè una operació d'exponenciació per l'esquerra repetida seria menys útil. Múltiples aparicions es podrien reescriure amb multiplicacions:

(x^{y})^{z}=x^{(yz)}.\,

Operacions no-associatives per les que no existeixen convencions per l'ordre d'efectuar les operacions inclouen les següents.

Prendre la mitjana aritmètica de nombres reals:

{(x+y)/2+z \over 2}\neq {x+(y+z)/2 \over 2}\neq {x+y+z \over 3}\qquad {\mbox{per algunes variables }}x,y,z\in \mathbb {R} .

Prendre el complementari de conjunts:

(A\backslash B)\backslash C\neq A\backslash (B\backslash C)\qquad {\mbox{per alguns conjunts }}A,B,C.

$Diagrama de Venn de complementaris relatius (A\B)\C i A\(B\C)$

La part verda del diagrama de Venn de l'esquerra representa (A\B)\C. La part verda del diagrama de Venn de la dreta representa A\(B\C).

Història

Sembla que va ser William Rowan Hamilton qui va acunyar el terme "propietat associativa"^[7] al voltant de l'any 1844, quan estava estudiant la l'àlgebra no associativa dels octonions, que havia après del matemàtic irlandès John T. Graves.^[8]

Relació amb la commutativitat en alguns casos particulars

En general, les operacions associatives no tenen perquè ser commutatives. No obstant això, donades certes condicions particulars, pot ser que l'associativitat impliqui commutativitat. Els operadors associatius definits en un interval de la recta dels reals són commutatius si són continus i injectius en tots els arguments.^[9] Una conseqüència d'això és que tot operador continu i associatiu amb dues entrades reals que és estrictament creixent en cadascuna d'elles és també commutatiu.^[10]

Vegeu també

Un semigrup és un conjunt amb una operació binària associativa i tancada.
La commutativitat i distributivitat són les altres dues propietats de les operacions binàries freqüentment usades.
L'associativitat de les potències i l'alternativitat són formes febles d'associativitat.

Referències

↑ Hungerford, Thomas W. Algebra. 1st. Springer, 1974, p. 24. ISBN 978-0387905181. «Definition 1.1 (i) a(bc) = (ab)c for all a, b, c in G.»
↑ Moore, Brooke Noel; Parker, Richard. Critical Thinking. 12th. New York: McGraw-Hill Education, 2017, p. 321. ISBN 9781259690877.
↑ Copi, Irving M.; Cohen, Carl; McMahon, Kenneth. Introduction to Logic. 14th. Essex: Pearson Education, 2014, p. 387. ISBN 9781292024820.
↑ Hurley, Patrick J.; Watson, Lori. A Concise Introduction to Logic. 13th. Boston: Cengage Learning, 2016, p. 427. ISBN 9781305958098.
↑ «Matrix product associativity». Khan Academy. [Consulta: 5 juny 2016].
↑ Schafer, Richard D. Dover Publications. An introduction to Non-associative algebras, 1995, p. 1-8. ISBN 0-486-68813-5.
↑ Hamilton, W.R. «On quaternions or a new system of imaginaries in algebra». Philosophical Magazine. Trinity College Dublin, 1844–1850.
↑ Baez, John C. «The Octonions». Bulletin of the American Mathematical Society, vol. 39, 2, 2002, pàg. 145–205. arXiv: math/0105155. DOI: 10.1090/S0273-0979-01-00934-X. ISSN: 0273-0979.
↑ Aczél, J. Lectures on Functional Equations and Their Applications (en anglès). Academic Press, 1966, p. 267. ISBN 978-0-08-095525-4.
↑ Ling, Cho-Hsin «Representation of associative functions». Publicationes Mathematicae, vol. 12, 01-09-1964, pàg. 189–212.

[1] Hungerford, Thomas W. Algebra. 1st. Springer, 1974, p. 24. ISBN 978-0387905181. «Definition 1.1 (i) a(bc) = (ab)c for all a, b, c in G.»

[2] Moore, Brooke Noel; Parker, Richard. Critical Thinking. 12th. New York: McGraw-Hill Education, 2017, p. 321. ISBN 9781259690877.

[3] Copi, Irving M.; Cohen, Carl; McMahon, Kenneth. Introduction to Logic. 14th. Essex: Pearson Education, 2014, p. 387. ISBN 9781292024820.

[4] Hurley, Patrick J.; Watson, Lori. A Concise Introduction to Logic. 13th. Boston: Cengage Learning, 2016, p. 427. ISBN 9781305958098.

[5] «Matrix product associativity». Khan Academy. [Consulta: 5 juny 2016].

[6] Schafer, Richard D. Dover Publications. An introduction to Non-associative algebras, 1995, p. 1-8. ISBN 0-486-68813-5.

[Hamilton-7] Hamilton, W.R. «On quaternions or a new system of imaginaries in algebra». Philosophical Magazine. Trinity College Dublin, 1844–1850.

[Baez-8] Baez, John C. «The Octonions». Bulletin of the American Mathematical Society, vol. 39, 2, 2002, pàg. 145–205. arXiv: math/0105155. DOI: 10.1090/S0273-0979-01-00934-X. ISSN: 0273-0979.

[9] Aczél, J. Lectures on Functional Equations and Their Applications (en anglès). Academic Press, 1966, p. 267. ISBN 978-0-08-095525-4.

[10] Ling, Cho-Hsin «Representation of associative functions». Publicationes Mathematicae, vol. 12, 01-09-1964, pàg. 189–212.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]