Асоцијативност

У математици, асоцијативно својство је својство неких бинарних операција, што значи да преуређивање заграда у изразу неће променити резултат. У пропозиционој логици, асоцијативност је важеће правило замене израза у логичким доказима. За бинарни оператор $\circ :K\times K\to K$ се каже да је асоцијативан над скупом K ако за свако $a,b,c\in K$ важи: $a\circ \left(b\circ c\right)=\left(a\circ b\right)\circ c$. Из асоцијативности оператора $\circ$ следи да у горенаведеним изразима редослед операција не игра улогу, те и запис у коме приоритет није назначен једнозначно одређен: $a\circ b\circ c$

У оквиру израза који садржи два или више појављивања у низу истог асоцијативног оператора, редослед којим се операције изводе није битан све док се редослед операнада не мења. То јест (након поновног писања израза са заградама и у инфиксном запису ако је потребно), преуређивање заграда у таквом изразу неће променити његову вредност. Размотрите следеће једначине:

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

Дефиниција

Бинарна операција ∗ на скупу S је асоцијативна када овај дијаграм комутује. То јест, када се два пута од S×S×S до S компонују на исту функцију од S×S×S до S.

Формално, бинарна операција ∗ на скупу S назива се асоцијативна ако задовољава асоцијативни закон:

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

Овде се ∗ користи за замену симбола операције, који може бити било који симбол, па чак и одсуство симбола (јукстапозиција) као за множење.

(xy)z = x(yz) = xyz за свако x, y, z in S.

Асоцијативни закон се такође може изразити функционалном нотацијом на следећи начин: f(f(x, y), z) = f(x, f(y, z)).

Записивање неасоцијативних операција

Уколико се неасоцијативна операција појављује више од једном у изразу, за одређивање редоследа операција користе се заграде. Ипак, за неке честе неасоцијативне операције постоје правила њиховог коришћења без заграда.

Операција је лево асоцијативна ако је правило да се користи слева надесно, т.ј.

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

а десно асоцијативна ако је правило да се користи здесна налево, т.ј.

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

На пример, одузимање је лево асоцијативно, степеновање десно асоцијативно док за векторски производ нема правила.

Генерализовани асоцијативни закон

У одсуству асоцијативног својства, пет фактора a, b,c, d, e резултирају Тамаријевом решетком четвртог реда, могуће различитих производа.

Ако је бинарна операција асоцијативна, поновљена примена операције даје исти резултат без обзира на то колико су валидни парови заграда уметнути у израз. Ово се зове генерализовани асоцијативни закон. На пример, производ од четири елемента може се написати, без промене редоследа фактора, на пет могућих начина:

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

Ако је операција производа асоцијативна, генерализовани закон асоцијативности налаже да ће сви ови изрази дати исти резултат. Дакле, осим ако израз са изостављеним заградама већ има другачије значење (види доле), заграде се могу сматрати непотребним и „производ“ се може недвосмислено написати као

abcd.

Како се број елемената повећава, број могућих начина за уметање заграда брзо расте, али они остају непотребни за вишезначност.

Пример где ово не функционише је логички двоуслован ↔. То је асоцијативно је; дакле, A ↔ (B ↔ C) је еквивалентно са (A ↔ B) ↔ C, али A ↔ B ↔ C најчешће значи (A ↔ B) and (B ↔ C), што није еквивалентно.

Пропозициона логика

Правило замене

У стандардној истинито-функционалној пропозиционој логици, асоцијација, или асоцијативност су два валидна правила замене. Правила дозвољавају померање заграда у логичким изразима у логичким доказима. Правила (користећи нотацију логичких конекција) су:

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

и

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

где је „$\Leftrightarrow$” металолошки симбол који представља „може се заменити у доказу са”.

Истинисно функционални спојеви

Асоцијативност је својство неких логичких спојева истинито-функционалне пропозиционалне логике. Следеће логичке еквиваленције показују да је асоцијативност својство одређених веза. Следеће (и њихове конверзе, пошто је ↔ комутативно) су истиносно-функционалне таутологије.

Асоцијативност дисјункције

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

Асоцијативност везника

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

Асоцијативност еквиваленције

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

Заједничко порицање је пример истинито функционалне повезаности која није асоцијативна.

Неасоцијативна операција

Бинарна операција $*$ на скупу S који не задовољава асоцијативни закон назива се неасоцијативна. симболично,

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

За такву операцију редослед евалуације је важан. На пример:

Одузимање

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

Дељење

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

Експоненцијација

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

Векторски производ

${\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}}$

Такође, иако је сабирање асоцијативно за коначне суме, оно није асоцијативно унутар бесконачних збирова (серија). На пример,

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

док

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

Неке неасоцијативне операције су фундаменталне у математици. Често се појављују као множење у структурама које се називају неасоцијативне алгебре, које такође имају сабирање и скаларно множење. Примери су октониони и Лијеве алгебре. У Лијевим алгебрама, множење задовољава Јакобијев идентитет уместо асоцијативног закона; ово омогућава апстраховање алгебарске природе инфинитезималних трансформација.

Други примери су квазигрупе, квазипоље, неасоцијативни прстен и комутативне неасоцијативне магме.

Неасоцијативност израчунавања са помичним зарезом

У математици је сабирање и множење реалних бројева асоцијативно. Насупрот томе, у рачунарској науци, сабирање и множење бројева са покретним зарезом није асоцијативно, јер се грешке заокруживања уводе када се вредности различите величине споје.

Да би се ово илустровало, размотрите приказ са помичним зарезом са 4-битном мантисом:

(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⁴

Иако већина рачунара рачуна са 24 или 53 битном мантисом, ово је важан извор грешке заокруживања, а приступи као што је Каханов алгоритам сумирања су начини да се грешке минимизирају. То може бити посебно проблематично у паралелном рачунарству.

Нотација за неасоцијативне операције

Главни чланак: Асоцијативност оператора

Генерално, заграде се морају користити за означавање редоследа евалуације ако се неасоцијативна операција појављује више пута у изразу (осим ако нотација не наводи редослед на други начин, на пример ${\dfrac {2}{3/4}}$). Међутим, математичари се слажу око одређеног редоследа евалуације за неколико уобичајених неасоцијативних операција. Ово је једноставно нотациона конвенција да се избегну заграде.

Лево-асоцијативна операција је неасоцијативна операција која се конвенционално вреднује с лева на десно, тј.

$$\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$$

док се десна асоцијативна операција конвенционално процењује с десна на лево:

$$\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$$

Јављају се лево-асоцијативне и десно-асоцијативне операције. Лево-асоцијативне операције укључују следеће:

Одузимање и дељење реалних бројева

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

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

Функциона примена

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

Ова нотација може бити мотивисана преносним изоморфизмом, који омогућава делимичну примену.

Десно асоцијативне операције укључују следеће:

Експоненцијализација реалних бројева у запису у суперскрипту

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

Експоненцијалност се обично користи са заградама или десно асоцијативно јер је поновљена лево-асоцијативна операција степеновања од мале користи. Поновљена степеновања би углавном била преписана множењем:

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

Правилно форматиран, суперскрипт се понаша као скуп заграда; на пример. у изразу $2^{x+3}$ сабирање се врши пре експоненцијације упркос томе што не постоје експлицитне заграде $2^{(x+3)}$ обавијене око њега. Тако дат израз као што је $x^{y^{z}}$, пуни експонент $y^{z}$ основе $x$ се прво процењује. Међутим, у неким контекстима, посебно у рукопису, разлика између ${x^{y}}^{z}=(x^{y})^{z}$, $x^{yz}=x^{(yz)}$ и $x^{y^{z}}=x^{(y^{z})}$ може бити тешко уочљива. У таквом случају се обично подразумева десна асоцијативност.

Дефиниција функције

$\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)$

Коришћење десно-асоцијативних нотација за ове операције може бити мотивисано Кари–Хауардовом кореспонденцијом и пресносним изоморфизмом.

Неасоцијативне операције за које није дефинисан конвенционални редослед евалуације укључују следеће.

Експоненцијација реалних бројева у инфиксној нотацији

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

Кнутови оператори стрелице нагоре

$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$

Вршење векторског производа три вектора

${\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}$

Рачунање просека реалних бројева у паровима

${(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.$

Рачунање релативног комплемента скупова

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

(Упореди материјалну неимпликацију у логици.)

Историја

Сматра се да је Вилијам Роуан Хамилтон сковао термин „асоцијативно својство“ око 1844. године, у време када је размишљао о неасоцијативној алгебри октонона на које га је упутио Џон Т. Грејвс.

Види још

• Антикомутативност
• Дистрибутивност
• Комутативност

Литература

• Ayres, Frank (1965). Schaum's Outline of Modern Abstract Algebra (1st изд.). 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 изд.). 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. стр. 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 изд.). 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. 

Спољашње везе

• „Matrix product associativity”. Khan Academy. Приступљено 5. 6. 2016. CS1 одржавање: Формат датума (веза)