Asocijativnost

Šablon:Nedostaju izvori U matematici, asocijativnost je osobina koju mogu posjedovati binarne operacije. Ona predstavlja, unutar izraza koji sadrži dva ili više istih asocijativnih operatora u nizu, da red kojim se operacije izvode nije bitan sve dok je niz operanda nepromijenjen. To jest, premještanje zagrada u takvom izrazu neće utjecati na njegovu vrijednost. Razmotrimo slijedeći primjer

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

Iako su zagrade premještene, vrijednost izraza se nije promienila. Pošto ovo važi kada vršimo sabiranje bilo kojih realnih brojeva, kažemo da je "sabiranje realnih brojeva asocijativna operacija."

Asocijativnost ne treba miještati sa komutativnosti. Komutativnost dozvoljava mijenjanje redoslijeda ili niza operanada unutar izraza, dok asocijativnost to ne dopušta. Naprimjer,

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

je primjer asocijativnosti, pošto su zagrade premještene (i, zbog toga, red operacija takom izračunavanja), dok su se operandi 5, 2 i 1 pojavili u istom redoslijedu od lijeva na desno u izrazu.

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

nije primjer asocijativnosti pošto je niz operanda promijenjen kada su 2 i 5 zamijenili mjesto.

Asocijativne operacije su mnogobrojne u matematici, te, u stvari, većina algebarskih struktura eksplicitno traži da njihove binarne operacije budu asocijativne. Međutim, mnoge važne i interesantne operacije nisu asocijativne; jedan od takvih primjera bi bio vektorski proizvod.

Definicija

Formalno, binarna operacija $*$ na skupu S naziva se asocijativnom ako zadovoljava zakon asocijacije:

$(x*y)*z=x*(y*z)\text{za sve }x,y,z\in S.$

Redoslijed izračunavanja ne utiče na vrijednost takvih izraza, te se može pokazati da to isto važi i za izraze koji sadrže bilo koji broj $*$ operacija. Zbog toga, kada je $*$ asocijativno, redoslijed izračunavanja ne mora se specifikovati stavljanjem zagrada, te se jednostavno piše:

$x*y*z.$

Međutim, važno je zapamtiti da ,ijenjanje redoslijeda operacija ne uključuje niti dozvoljava mijenjanje samih operacija, tako što bi operande razmiještali unutar izraza.

Ako je binarna operacija asocijativna, ponavljana primjena operacije daje isti rezultat bez obzira na to koliko je važećih parova i zagrada u izrazu.

Za četiri elementa rezultat binarne operacije može se odrediti na 5 načina

1. $(ab)c)d$
2. $(ab)(cd)$
3. $(a(bc))d$
4. $a((bc)d)$
5. $a(b(cd))$

Ako važi zakon asocijacije navedeni slučaj može se pisati $abcd$

Primjeri

Neki primjeri asocijativnih operacija su slijedeći.

• U aritmetici, sabiranje i množenje realnih brojeva su asocijativne operacije; npr.,

$\begin{array}{c}(x+y)+z=x+(y+z)=x+y+z\\ (xy)z=x(yz)=xyz\end{array}\}\text{za sve }x,y,z\in ℝ.$

• Sabiranje i množenje kompleksnih brojeva i kvaterniona je asocijativno. Sabiranje oktoniona je, također, asocijativno, ali množenje istih nije.

• Funkcije najvećeg zajedničkoh dijelioca i najmanjeg zajedničkog sadržaoca ponašaju se asocijativno.

$\begin{array}{c}\gcd (\gcd (x,y),z)=\gcd (x,\gcd (y,z))=\gcd (x,y,z)\\ \mathrm{lcm}(\mathrm{lcm}(x,y),z)=\mathrm{lcm}(x,\mathrm{lcm}(y,z))=\mathrm{lcm}(x,y,z)\end{array}\}\text{ za sve }x,y,z\in \mathbb{Z}.$

• Pošto su linearne transformacije funkcije moje mogu biti prikazane preko matrica, gdje množenje matrica predstavlja kompoziciju funkcija, zaključujemo da je množenje matrica asocijativno.

• Uzimajući presjek unije skupova:

$\begin{array}{c}(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{array}\}\text{za sve skupove }A,B,C.$

• Ako je M neki skup, a S označava skup svih funkcija iz M u M, tada je operacija kompozicije funkcije na S asocijativna:

$(f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h\text{za sve }f,g,h\in S.$

• Nešto općenitije, za data četiri skupa M, N, P i Q, gdje vrijedi h: M u N, g: N u P i f: P u Q, tada je

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

Ukratko, kompozicija preslikavanja je uvijek asocijativna.

• Razmotrimo skup sa tri elementa, A, B i C. Slijedeća operacija:

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

je asocijativna. Zbog toga, naprimjer, vrijedi A(BC)=(AB)C. Ovo preslikavanje nije komutativno.

Pravilo zamjene

Za dokazivanje logičkih operacija vrijede dva pravila zamjene

$(P\vee (Q\vee R))\iff ((P\vee Q)\vee R)$ i

$(P\wedge (Q\wedge R))\iff ((P\wedge Q)\wedge R),$

Vrjijedi asocijativnost za disjunkciju

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

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

konjukciju

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

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

ekvivalenciju

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

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

Ne asocjativnost

Za binarnu operaciju $*$ za koju ne važi asocijativnost kažemo da je ne asocijativna.

$(x*y)*z\ne x*(y*z)\text{za }x,y,z\in S.$

• Oduzimanje

$(5-3)-2\ne 5-(3-2)$

• Dijeljenje

$(4/2)/2\ne 4/(2/2)$

• Stepenovanje

$2^{(1^2)}\ne (2^1{)}^2$

• I beskonaćne sume nisu asocjativne

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

dok je

$1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+\dots =1$

Također pogledajte

• Polugrupa je skup sa zatvorenim binarnim operacijama.
• Komutativnost i distributivnost su ostale dvije često korištene osobine binarnih operacija.
• Asocijativnost stepena i alternativnost su slabi oblici asocijativnosti.