Asocijativnost

S Wikipedije, slobodne enciklopedije

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

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,

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.

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[uredi | uredi izvor]

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

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:

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

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

Primjeri[uredi | uredi izvor]

Neki primjeri asocijativnih operacija su slijedeći.

  • Ako je M neki skup, a S označava skup svih funkcija iz M u M, tada je operacija kompozicije funkcije na S asocijativna:
  • 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
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[uredi | uredi izvor]

Za dokazivanje logičkih operacija vrijede dva pravila zamjene

i

Vrjijedi asocijativnost za disjunkciju

konjukciju

i

ekvivalenciju

Ne asocjativnost[uredi | uredi izvor]

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

  • I beskonaćne sume nisu asocjativne

dok je

Također pogledajte[uredi | uredi izvor]