Ассоциативная операция
В математике, ассоциативность бинарной операции — выполнение равенства
- (x⋆y)⋆z = x⋆(y⋆z)
для всех x, y и z, где «⋆» обозначает операцию в инфиксной записи.[1] Попросту, для тройки операндов, требующей двух операций «⋆», не имеет значения, с которого конца начинать эту пару операций. Порядок операндов x, y и z, тем не менее, важен.
Важнейшей математической структурой, завязанной на ассоциативные операции, является группа.
Примерами ассоциативных операций являются сложение, умножение (как правило), а также логические связки конъюнкция и дизъюнкция.
На множестве[править]
| S×S×S | ⋆×id →
|
S×S |
| id×⋆↓ | ↓⋆ | |
| S×S | ⋆ →
|
S |
Для осмысленности выражений (x⋆y)⋆z и x⋆(y⋆z) необходимо, чтобы результат «⋆» можно было бы подставлять в качестве её же операнда. Обычно такая операция понимается как «внутренняя» (англ. internal binary operation, фр. loi de composition interne), то есть и операнды, и результат лежат в одном и том же множестве S. Тогда ассоциативность операции ⋆: S×S → S выражается как коммутативность изображённой диаграммы.
Множество с заданной на нём внутренней ассоциативной операцией называется полугруппой.
Как средство достижения произвольной арности[править]
Ассоциативность операции влечёт равенство результатов различных способов упорядочить n − 1 операций на n операндах для n = 4, 5, …. Итерировать можно любую бинарную операцию, однако именно ассоциативность обеспечивает независимость результата от порядка их применения: с левого конца, с правого, или как-то иначе. Например, для n = 5 таких способов имеется четырнадцать, и число их быстро растёт с ростом n.
Таким образом, из исходной бинарной операции получается операция произвольной натуральной арности n: для n = 1 берётся тождественная операция, для n = 2 — исходная «⋆», для n = 3 и далее — композиции, как показано выше.[2]
Особенности записи[править]
Когда ассоциативность «⋆» предполагается известной, выражения типа x⋆y⋆z, a⋆b⋆c⋆d и т. д. пишутся обычно без особых пояснений. Для некоторых операций знак операции может не писаться вовсе: xyz, abcd и т. д.
Одним из немногих исключений является запись для связки эквиваленции (равносильность, ⇔). Эвиваленция ассоциативна (в классической логике как операция на множестве {истина, ложь}), но «P⇔Q⇔R» означает «P⇔Q и Q⇔R», то есть, равносильность всех трёх суждений P, Q и R.
Ассоциативность умножения[править]
Умножение в большинстве математических структур подразумевается ассоциативным (хотя не обязательно коммутативным). Так, множество с согласованными коммутативным сложением и ассоциативным умножением называется кольцом.
Тем не менее, общее понятие алгебры над кольцом (и, как частный случай, над полем) не требует ассоциативности «умножения».