Ассоциативная операция

Материал из Циклопедии
Перейти к: навигация, поиск

В математике, ассоциативность бинарной операции — выполнение равенства

(xy)⋆z = x⋆(yz)

для всех x, y и z, где «⋆» обозначает операцию в инфиксной записи.[1] Попросту, для тройки операндов, требующей двух операций «⋆», не имеет значения, с которого конца начинать эту пару операций. Порядок операндов x, y и z, тем не менее, важен.

Важнейшей математической структурой, завязанной на ассоциативные операции, является группа.

Примерами ассоциативных операций являются сложение, умножение (как правило), а также логические связки конъюнкция и дизъюнкция.

Содержание

[править] На множестве

S×S×S  ⋆×id
 
S×S
id×⋆     
S×S
S

Для осмысленности выражений (xy)⋆z и x⋆(yz) необходимо, чтобы результат «⋆» можно было бы подставлять в качестве её же операнда. Обычно такая операция понимается как «внутренняя» (англ. internal binary operation, фр. loi de composition interne), то есть и операнды, и результат лежат в одном и том же множестве S. Тогда ассоциативность операции ⋆: S×S → S выражается как коммутативность изображённой диаграммы.

Множество с заданной на нём внутренней ассоциативной операцией называется полугруппой.

[править] Как средство достижения произвольной арности

Tamari lattice.svg

Ассоциативность операции влечёт равенство результатов различных способов упорядочить n − 1 операций на n операндах для n = 4, 5, …. Итерировать можно любую бинарную операцию, однако именно ассоциативность обеспечивает независимость результата от порядка их применения: с левого конца, с правого, или как-то иначе. Например, для n = 5 таких способов имеется четырнадцать, и число их быстро растёт с ростом n.

Таким образом, из исходной бинарной операции получается операция произвольной натуральной арности n: для n = 1 берётся тождественная операция, для n = 2 — исходная «⋆», для n = 3 и далее — композиции, как показано выше.[2]

[править] Особенности записи

Когда ассоциативность «⋆» предполагается известной, выражения типа xyz, abcd и т. д. пишутся обычно без особых пояснений. Для некоторых операций знак операции может не писаться вовсе: xyz, abcd и т. д.

Одним из немногих исключений является запись для связки эквиваленции (равносильность, ⇔). Эвиваленция ассоциативна (в классической логике как операция на множестве {истина, ложь}), но «PQR» означает «PQ и QR», то есть, равносильность всех трёх суждений P, Q и R.

[править] Ассоциативность умножения

Умножение в большинстве математических структур подразумевается ассоциативным (хотя не обязательно коммутативным). Так, множество с согласованными коммутативным сложением и ассоциативным умножением называется кольцом.

Тем не менее, общее понятие алгебры над кольцом (и, как частный случай, над полем) не требует ассоциативности «умножения».

[править] См. также

[править] Примечания

  1. Вместо «⋆» можно подставить другой символ операции.
  2. При наличии нейтрального элемента (когда полугруппа (S, ⋆) является моноидом), можно добавить и 0-арную операцию, результатом которой является нейтральный элемент.
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты