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

У математици, асоцијативно својство[1] је својство неких бинарних операција, што значи да преуређивање заграда у изразу неће променити резултат. У пропозиционој логици, асоцијативност је важеће правило замене израза у логичким доказима. За бинарни оператор се каже да је асоцијативан над скупом K ако за свако важи: . Из асоцијативности оператора следи да у горенаведеним изразима редослед операција не игра улогу, те и запис у коме приоритет није назначен једнозначно одређен:

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

ДефиницијаУреди

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

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

(xy) ∗ z = x ∗ (yz) 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, b,c, d, e резултирају Тамаријевом решетком четвртог реда, могуће различитих производа.

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

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

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

abcd.

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

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

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

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

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

 

и

 

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

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

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

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

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

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

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

 

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

Одузимање
 
Дељење
 
Експоненцијација
 
Векторски производ
 

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

 
док
 

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

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

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

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

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

(1.0002×20 + 1.0002×20) + 1.0002×24 = 1.0002×21 + 1.0002×24 = 1.0012×24
1.0002×20 + (1.0002×20 + 1.0002×24) = 1.0002×20 + 1.0002×24 = 1.0002×24

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

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

Генерално, заграде се морају користити за означавање редоследа евалуације ако се неасоцијативна операција појављује више пута у изразу (осим ако нотација не наводи редослед на други начин, на пример  ). Међутим, математичари се слажу око одређеног редоследа евалуације за неколико уобичајених неасоцијативних операција. Ово је једноставно нотациона конвенција да се избегну заграде.

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

 

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

 

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

Одузимање и дељење реалних бројева[10][11][12][13][14]
 
 
Функциона примена
 

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

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

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

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

 

Правилно форматиран, суперскрипт се понаша као скуп заграда; на пример. у изразу   сабирање се врши пре експоненцијације упркос томе што не постоје експлицитне заграде   обавијене око њега. Тако дат израз као што је  , пуни експонент   основе   се прво процењује. Међутим, у неким контекстима, посебно у рукопису, разлика између  ,   и   може бити тешко уочљива. У таквом случају се обично подразумева десна асоцијативност.

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

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

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

Експоненцијација реалних бројева у инфиксној нотацији[15]
 
Кнутови оператори стрелице нагоре
 
 
Вршење векторског производа три вектора
 
Рачунање просека реалних бројева у паровима
 
Рачунање релативног комплемента скупова
 .

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

ИсторијаУреди

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

Види јошУреди

РеференцеУреди

  1. ^ Hungerford, Thomas W. (1974). Algebra (1st изд.). Springer. стр. 24. ISBN 978-0387905181. »Definition 1.1 (i) a(bc) = (ab)c for all a, b, c in G.« 
  2. ^ Durbin, John R. (1992). Modern Algebra: an Introduction (3rd изд.). New York: Wiley. стр. 78. ISBN 978-0-471-51001-7. »If   are elements of a set with an associative operation, then the product   is unambiguous; this is, the same element will be obtained regardless of how parentheses are inserted in the product.« 
  3. ^ Moore, Brooke Noel; Parker, Richard (2017). Critical Thinking (12th изд.). New York: McGraw-Hill Education. стр. 321. ISBN 9781259690877. 
  4. ^ Copi, Irving M.; Cohen, Carl; McMahon, Kenneth (2014). Introduction to Logic (14th изд.). Essex: Pearson Education. стр. 387. ISBN 9781292024820. 
  5. ^ Hurley, Patrick J.; Watson, Lori (2016). A Concise Introduction to Logic (13th изд.). Boston: Cengage Learning. стр. 427. ISBN 9781305958098. 
  6. ^ Knuth, Donald, The Art of Computer Programming, Volume 3, section 4.2.2
  7. ^ IEEE Computer Society (29. 8. 2008). IEEE Standard for Floating-Point Arithmetic. ISBN 978-0-7381-5753-5. doi:10.1109/IEEESTD.2008.4610935. IEEE Std 754-2008. 
  8. ^ Villa, Oreste; Chavarría-mir, Daniel; Gurumoorthi, Vidhya; Márquez, Andrés; Krishnamoorthy, Sriram, Effects of Floating-Point non-Associativity on Numerical Computations on Massively Multithreaded Systems (PDF), Архивирано из оригинала (PDF) на датум 15. 2. 2013, Приступљено 8. 4. 2014 
  9. ^ Goldberg, David (март 1991). „What Every Computer Scientist Should Know About Floating-Point Arithmetic” (PDF). ACM Computing Surveys. 23 (1): 5—48. S2CID 222008826. doi:10.1145/103162.103163. Архивирано (PDF) из оригинала на датум 2022-05-19. Приступљено 20. 1. 2016. 
  10. ^ George Mark Bergman "Order of arithmetic operations"
  11. ^ "The Order of Operations". Education Place.
  12. ^ "The Order of Operations", timestamp 5m40s. Khan Academy.
  13. ^ "Using Order of Operations and Exploring Properties", section 9. Virginia Department of Education.
  14. ^ Bronstein, de:Taschenbuch der Mathematik, pages 115-120, chapter: 2.4.1.1, ISBN 978-3-8085-5673-3
  15. ^ Exponentiation Associativity and Standard Math Notation Codeplea. 23 August 2016. Retrieved 20 September 2016.
  16. ^ Hamilton, W.R. (1844—1850). „On quaternions or a new system of imaginaries in algebra”. David R. Wilkins collection. Philosophical Magazine. Trinity College Dublin. 
  17. ^ Baez, John C. (2002). „The Octonions”. Bulletin of the American Mathematical Society. 39 (2): 145—205. ISSN 0273-0979. MR 1886087. S2CID 586512. arXiv:math/0105155 . doi:10.1090/S0273-0979-01-00934-X. 

ЛитератураУреди

Спољашње везеУреди