Asocijativnost

U matematici, asocijativno svojstvo je svojstvo nekih binarnih operacija, što znači da preuređivanje zagrada u izrazu neće promeniti rezultat. U propozicionoj logici, asocijativnost je važeće pravilo zamene izraza u logičkim dokazima. Za binarni operator $\circ :K\times K\to K$ se kaže da je asocijativan nad skupom K ako za svako $a,b,c\in K$ važi: $a\circ \left(b\circ c\right)=\left(a\circ b\right)\circ c$. Iz asocijativnosti operatora $\circ$ sledi da u gorenavedenim izrazima redosled operacija ne igra ulogu, te i zapis u kome prioritet nije naznačen jednoznačno određen: $a\circ b\circ c$

U okviru izraza koji sadrži dva ili više pojavljivanja u nizu istog asocijativnog operatora, redosled kojim se operacije izvode nije bitan sve dok se redosled operanada ne menja. To jest (nakon ponovnog pisanja izraza sa zagradama i u infiksnom zapisu ako je potrebno), preuređivanje zagrada u takvom izrazu neće promeniti njegovu vrednost. Razmotrite sledeće jednačine:

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

Definicija

Binarna operacija ∗ na skupu S je asocijativna kada ovaj dijagram komutuje. To jest, kada se dva puta od S×S×S do S komponuju na istu funkciju od S×S×S do S.

Formalno, binarna operacija ∗ na skupu S naziva se asocijativna ako zadovoljava asocijativni zakon:

(x ∗ y) ∗ z = x ∗ (y ∗ z) for all x, y, z in S.

Ovde se ∗ koristi za zamenu simbola operacije, koji može biti bilo koji simbol, pa čak i odsustvo simbola (jukstapozicija) kao za množenje.

(xy)z = x(yz) = xyz za svako x, y, z in S.

Asocijativni zakon se takođe može izraziti funkcionalnom notacijom na sledeći način: f(f(x, y), z) = f(x, f(y, z)).

Zapisivanje neasocijativnih operacija

Ukoliko se neasocijativna operacija pojavljuje više od jednom u izrazu, za određivanje redosleda operacija koriste se zagrade. Ipak, za neke česte neasocijativne operacije postoje pravila njihovog korišćenja bez zagrada.

Operacija je levo asocijativna ako je pravilo da se koristi sleva nadesno, t.j.

$a\circ b\circ c=(a\circ b)\circ c$

a desno asocijativna ako je pravilo da se koristi zdesna nalevo, t.j.

$a\circ b\circ c=a\circ (b\circ c)$

Na primer, oduzimanje je levo asocijativno, stepenovanje desno asocijativno dok za vektorski proizvod nema pravila.

Generalizovani asocijativni zakon

U odsustvu asocijativnog svojstva, pet faktora a, b,c, d, e rezultiraju Tamarijevom rešetkom četvrtog reda, moguće različitih proizvoda.

Ako je binarna operacija asocijativna, ponovljena primena operacije daje isti rezultat bez obzira na to koliko su validni parovi zagrada umetnuti u izraz. Ovo se zove generalizovani asocijativni zakon. Na primer, proizvod od četiri elementa može se napisati, bez promene redosleda faktora, na pet mogućih načina:

• ((ab)c)d
• (ab)(cd)
• (a(bc))d
• a((bc)d)
• a(b(cd))

Ako je operacija proizvoda asocijativna, generalizovani zakon asocijativnosti nalaže da će svi ovi izrazi dati isti rezultat. Dakle, osim ako izraz sa izostavljenim zagradama već ima drugačije značenje (vidi dole), zagrade se mogu smatrati nepotrebnim i „proizvod“ se može nedvosmisleno napisati kao

abcd.

Kako se broj elemenata povećava, broj mogućih načina za umetanje zagrada brzo raste, ali oni ostaju nepotrebni za višeznačnost.

Primer gde ovo ne funkcioniše je logički dvouslovan ↔. To je asocijativno je; dakle, A ↔ (B ↔ C) je ekvivalentno sa (A ↔ B) ↔ C, ali A ↔ B ↔ C najčešće znači (A ↔ B) and (B ↔ C), što nije ekvivalentno.

Propoziciona logika

Pravilo zamene

U standardnoj istinito-funkcionalnoj propozicionoj logici, asocijacija, ili asocijativnost su dva validna pravila zamene. Pravila dozvoljavaju pomeranje zagrada u logičkim izrazima u logičkim dokazima. Pravila (koristeći notaciju logičkih konekcija) su:

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

i

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

gde je „$\Leftrightarrow$” metalološki simbol koji predstavlja „može se zameniti u dokazu sa”.

Istinisno funkcionalni spojevi

Asocijativnost je svojstvo nekih logičkih spojeva istinito-funkcionalne propozicionalne logike. Sledeće logičke ekvivalencije pokazuju da je asocijativnost svojstvo određenih veza. Sledeće (i njihove konverze, pošto je ↔ komutativno) su istinosno-funkcionalne tautologije.

Asocijativnost disjunkcije

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

Asocijativnost veznika

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

Asocijativnost ekvivalencije

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

Zajedničko poricanje je primer istinito funkcionalne povezanosti koja nije asocijativna.

Neasocijativna operacija

Binarna operacija $*$ na skupu S koji ne zadovoljava asocijativni zakon naziva se neasocijativna. simbolično,

$$(x*y)*z\neq x*(y*z)\qquad {\mbox{for some }}x,y,z\in S.$$

Za takvu operaciju redosled evaluacije je važan. Na primer:

Oduzimanje

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

Deljenje

$(4/2)/2\,\neq \,4/(2/2)$

Eksponencijacija

$2^{(1^{2})}\,\neq \,(2^{1})^{2}$

Vektorski proizvod

${\begin{aligned}\mathbf {i} \times (\mathbf {i} \times \mathbf {j} )&=\mathbf {i} \times \mathbf {k} =-\mathbf {j} \\(\mathbf {i} \times \mathbf {i} )\times \mathbf {j} &=\mathbf {0} \times \mathbf {j} =\mathbf {0} \end{aligned}}$

Takođe, iako je sabiranje asocijativno za konačne sume, ono nije asocijativno unutar beskonačnih zbirova (serija). Na primer,

$$(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots =0$$ dok $$1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots =1.$$

Neke neasocijativne operacije su fundamentalne u matematici. Često se pojavljuju kao množenje u strukturama koje se nazivaju neasocijativne algebre, koje takođe imaju sabiranje i skalarno množenje. Primeri su oktonioni i Lijeve algebre. U Lijevim algebrama, množenje zadovoljava Jakobijev identitet umesto asocijativnog zakona; ovo omogućava apstrahovanje algebarske prirode infinitezimalnih transformacija.

Drugi primeri su kvazigrupe, kvazipolje, neasocijativni prsten i komutativne neasocijativne magme.

Neasocijativnost izračunavanja sa pomičnim zarezom

U matematici je sabiranje i množenje realnih brojeva asocijativno. Nasuprot tome, u računarskoj nauci, sabiranje i množenje brojeva sa pokretnim zarezom nije asocijativno, jer se greške zaokruživanja uvode kada se vrednosti različite veličine spoje.

Da bi se ovo ilustrovalo, razmotrite prikaz sa pomičnim zarezom sa 4-bitnom mantisom:

(1.000₂×2⁰ + 1.000₂×2⁰) + 1.000₂×2⁴ = 1.000₂×2¹ + 1.000₂×2⁴ = 1.001₂×2⁴

1.000₂×2⁰ + (1.000₂×2⁰ + 1.000₂×2⁴) = 1.000₂×2⁰ + 1.000₂×2⁴ = 1.000₂×2⁴

Iako većina računara računa sa 24 ili 53 bitnom mantisom, ovo je važan izvor greške zaokruživanja, a pristupi kao što je Kahanov algoritam sumiranja su načini da se greške minimiziraju. To može biti posebno problematično u paralelnom računarstvu.

Notacija za neasocijativne operacije

Glavni članak: Asocijativnost operatora

Generalno, zagrade se moraju koristiti za označavanje redosleda evaluacije ako se neasocijativna operacija pojavljuje više puta u izrazu (osim ako notacija ne navodi redosled na drugi način, na primer ${\dfrac {2}{3/4}}$). Međutim, matematičari se slažu oko određenog redosleda evaluacije za nekoliko uobičajenih neasocijativnih operacija. Ovo je jednostavno notaciona konvencija da se izbegnu zagrade.

Levo-asocijativna operacija je neasocijativna operacija koja se konvencionalno vrednuje s leva na desno, tj.

$$\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{за свако }}w,x,y,z\in S$$

dok se desna asocijativna operacija konvencionalno procenjuje s desna na levo:

$$\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{за свако }}w,x,y,z\in S$$

Javljaju se levo-asocijativne i desno-asocijativne operacije. Levo-asocijativne operacije uključuju sledeće:

Oduzimanje i deljenje realnih brojeva

$x-y-z=(x-y)-z$

$x/y/z=(x/y)/z$

Funkciona primena

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

Ova notacija može biti motivisana prenosnim izomorfizmom, koji omogućava delimičnu primenu.

Desno asocijativne operacije uključuju sledeće:

Eksponencijalizacija realnih brojeva u zapisu u superskriptu

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

Eksponencijalnost se obično koristi sa zagradama ili desno asocijativno jer je ponovljena levo-asocijativna operacija stepenovanja od male koristi. Ponovljena stepenovanja bi uglavnom bila prepisana množenjem:

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

Pravilno formatiran, superskript se ponaša kao skup zagrada; na primer. u izrazu $2^{x+3}$ sabiranje se vrši pre eksponencijacije uprkos tome što ne postoje eksplicitne zagrade $2^{(x+3)}$ obavijene oko njega. Tako dat izraz kao što je $x^{y^{z}}$, puni eksponent $y^{z}$ osnove $x$ se prvo procenjuje. Međutim, u nekim kontekstima, posebno u rukopisu, razlika između ${x^{y}}^{z}=(x^{y})^{z}$, $x^{yz}=x^{(yz)}$ i $x^{y^{z}}=x^{(y^{z})}$ može biti teško uočljiva. U takvom slučaju se obično podrazumeva desna asocijativnost.

Definicija funkcije

$\mathbb {Z} \rightarrow \mathbb {Z} \rightarrow \mathbb {Z} =\mathbb {Z} \rightarrow (\mathbb {Z} \rightarrow \mathbb {Z} )$

$x\mapsto y\mapsto x-y=x\mapsto (y\mapsto x-y)$

Korišćenje desno-asocijativnih notacija za ove operacije može biti motivisano Kari–Hauardovom korespondencijom i presnosnim izomorfizmom.

Neasocijativne operacije za koje nije definisan konvencionalni redosled evaluacije uključuju sledeće.

Eksponencijacija realnih brojeva u infiksnoj notaciji

$(x^{\wedge }y)^{\wedge }z\neq x^{\wedge }(y^{\wedge }z)$

Knutovi operatori strelice nagore

$a\uparrow \uparrow (b\uparrow \uparrow c)\neq (a\uparrow \uparrow b)\uparrow \uparrow c$

$a\uparrow \uparrow \uparrow (b\uparrow \uparrow \uparrow c)\neq (a\uparrow \uparrow \uparrow b)\uparrow \uparrow \uparrow c$

Vršenje vektorskog proizvoda tri vektora

${\vec {a}}\times ({\vec {b}}\times {\vec {c}})\neq ({\vec {a}}\times {\vec {b}})\times {\vec {c}}\qquad {\mbox{ for some }}{\vec {a}},{\vec {b}},{\vec {c}}\in \mathbb {R} ^{3}$

Računanje proseka realnih brojeva u parovima

${(x+y)/2+z \over 2}\neq {x+(y+z)/2 \over 2}\qquad {\mbox{for all }}x,y,z\in \mathbb {R} {\mbox{ with }}x\neq z.$

Računanje relativnog komplementa skupova

$(A\backslash B)\backslash C\neq A\backslash (B\backslash C)$.

(Uporedi materijalnu neimplikaciju u logici.)

Istorija

Smatra se da je Vilijam Rouan Hamilton skovao termin „asocijativno svojstvo“ oko 1844. godine, u vreme kada je razmišljao o neasocijativnoj algebri oktonona na koje ga je uputio Džon T. Grejvs.

Vidi još

• Antikomutativnost
• Distributivnost
• Komutativnost

Literatura

• Ayres, Frank (1965). Schaum's Outline of Modern Abstract Algebra (1st izd.). McGraw-Hill. ISBN 978-0-07-002655-1. .
• Howie, John M. (1995). Fundamentals of Semigroup Theory. Clarendon Press. ISBN 978-0-19-851194-6. Zbl 0835.20077. 
• Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (1961). The Algebraic Theory of Semigroups. 1. American Mathematical Society. ISBN 978-0-8218-0271-7. Zbl 0111.03403. 
• Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (2010) [1967]. The algebraic theory of semigroups. 2. American Mathematical Society. ISBN 978-0-8218-0272-4. 
• Grillet, Pierre Antoine (1995). Semigroups: An Introduction to the Structure Theory. Marcel Dekker. ISBN 978-0-8247-9662-4. Zbl 0830.20079. 
• Grillet, Pierre Antoine (2001). Commutative Semigroups. Springer Verlag. ISBN 978-0-7923-7067-3. Zbl 1040.20048. 
• Hollings, Christopher (2009). „The Early Development of the Algebraic Theory of Semigroups”. Archive for History of Exact Sciences. 63: 497—536. doi:10.1007/s00407-009-0044-3. 
• Hollings, Christopher (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. ISBN 978-1-4704-1493-1. Zbl 1317.20001. 
• Petrich, Mario (1973). Introduction to Semigroups. Charles E. Merrill. ISBN 978-0-675-09062-9. Zbl 0321.20037. 
• Feller, William (1971). An introduction to probability theory and its applications. II (2nd izd.). Wiley. MR 0270403. 
• Hille, Einar; Phillips, Ralph S. (1974). Functional analysis and semi-groups. American Mathematical Society. ISBN 978-0821874646. MR 0423094. 
• Suschkewitsch, Anton (1928). Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit. Mathematische Annalen. 99. str. 30—50. ISSN 0025-5831. MR 1512437. doi:10.1007/BF01459084. hdl:10338.dmlcz/100078 . 
• Kantorovitz, Shmuel (2009). Topics in Operator Semigroups. Springer. ISBN 978-0-8176-4932-6. Zbl 1187.47003. 
• Jacobson, Nathan (2009). Basic algebra. 1 (2nd izd.). Dover. ISBN 978-0-486-47189-1. 
• Lawson, Mark V. (1998). Inverse semigroups: the theory of partial symmetries. World Scientific. ISBN 978-981-02-3316-7. Zbl 1079.20505. 
• Lothaire, M. (2011) [2002]. Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. 90. Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183. 
• Rajagopalan, Sridhar; Schulman, Leonard J. (2000). „Verification of Identities”. SIAM Journal on Computing. 29 (4): 1155—1163. CiteSeerX 10.1.1.4.6898 . doi:10.1137/S0097539797325387. 
• Kehayopulu, Niovi; Philip Argyris (1993). „An algorithm for Light's associativity test using Mathematica”. J. Comput. Inform. 3 (1): 87–98. ISSN 1180-3886. 
• Bednarek, A R (1968). „An extension of Light's associativity test”. American Mathematical Monthly. 75 (5): 531–532. JSTOR 2314731. doi:10.2307/2314731. 
• Kalman, J A (1971). „Bednarek's extension of Light's associativity test”. Semigroup Forum. 3 (1): 275—276. S2CID 124362744. doi:10.1007/BF02572966. 

Spoljašnje veze

• „Matrix product associativity”. Khan Academy. Pristupljeno 5. 6. 2016. CS1 održavanje: Format datuma (veza)