Ассоциативное свойство

Эта статья об ассоциативном свойстве в математике. Информацию об ассоциативности в кэше памяти центрального процессора см. в разделе «Ассоциативность кэша ЦП» . Информацию об ассоциативности в языках программирования см. в разделе «Ассоциативность операторов» . Чтобы узнать о значении связанной группы людей в лингвистике, см. Ассоциативность (лингвистика) .

Сюда перенаправляются «Ассоциативные» и «неассоциативные». Информацию об ассоциативном и неассоциативном обучении см. в разделе «Типы обучения» .

Ассоциативное свойство

Визуальный граф, представляющий ассоциативные операции; $(x\circ y)\circ z=x\circ (y\circ z)$
Тип	Закон , правило замены
Поле	Элементарная алгебра Булева алгебра Теория множеств Линейная алгебра Пропозициональное исчисление
Символическое заявление	Элементарная алгебра $(x\,*\,y)\,*\,z=x\,*\,(y\,*\,z)\forall x,y,z\in S$ Пропозициональное исчисление $(P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)$ $(P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R),$

В математике свойство ассоциативное — это свойство некоторых бинарных операций , означающее, что перестановка круглых скобок в выражении не изменит результат. В логике высказываний ассоциативность является действительным правилом замены выражений в логических доказательствах .

В выражении, содержащем два или более вхождений подряд одного и того же ассоциативного оператора, порядок выполнения операций не имеет значения, пока последовательность операндов не изменяется. То есть (после переписывания выражения в скобках и при необходимости в инфиксной записи) перестановка скобок в таком выражении не изменит его значения. Рассмотрим следующие уравнения:

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

Несмотря на то, что круглые скобки в каждой строке были переставлены, значения выражений не изменились. Поскольку это справедливо при выполнении сложения и умножения любых действительных чисел , можно сказать, что «сложение и умножение действительных чисел являются ассоциативными операциями».

Ассоциативность — это не то же самое, что коммутативность , которая определяет, влияет ли порядок двух операндов на результат. Например, порядок не имеет значения при умножении действительных чисел, то есть a × b = b × a , поэтому мы говорим, что умножение действительных чисел является коммутативной операцией. Однако такие операции, как композиция функций и умножение матриц, являются ассоциативными, но не (обычно) коммутативными.

Ассоциативные операции широко распространены в математике; Фактически, многие алгебраические структуры (такие как полугруппы и категории ) явно требуют, чтобы их бинарные операции были ассоциативными.

Однако многие важные и интересные операции неассоциативны; некоторые примеры включают вычитание , возведение в степень и векторное векторное произведение . В отличие от теоретических свойств действительных чисел, добавление чисел с плавающей запятой в информатике не является ассоциативным, и выбор того, как связать выражение, может существенно повлиять на ошибку округления.

Определение

Бинарная операция* на множестве S является ассоциативной, если эта диаграмма коммутирует . То есть, когда два пути от S × S × S до S составляют одну и ту же функцию от S × S × S до S .

Формально бинарная операция ∗ на множестве S называется ассоциативной, если она удовлетворяет ассоциативному закону :

( Икс * y ) * z знак равно Икс * ( y * z ) для всех x , y , z в S .

Здесь * используется для замены символа операции, которым может быть любой символ и даже отсутствие символа ( сопоставление ), как при умножении .

( Икс y ) z знак равно Икс ( y z ) знак равно Икс y z для всех x , y , z в S .

Ассоциативный закон также можно выразить в функциональной записи следующим образом: f ( f ( x , y ), z ) = f ( x , f ( y , z )) .

Обобщенный ассоциативный закон

В отсутствие ассоциативного свойства пять факторов a , b , c , d , e приводят к решетке Тамари четвертого порядка, возможно, к различным продуктам.

Если бинарная операция является ассоциативной, повторное применение операции дает один и тот же результат независимо от того, какие допустимые пары круглых скобок вставлены в выражение. Это называется обобщенным ассоциативным законом .

Количество возможных заключений в скобки — это число каталанское C _n для n операций над n+1 значениями. Например, произведение 3 операций над 4 элементами можно записать (игнорируя перестановки аргументов) в C ₃ = 5 возможных способов:

• (( а б ) в ) d
• ( а б )( в г )
• ( а ( б в )) d
• а (( б в ) d )
• а ( б ( в г ))

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

а б в г .

По мере увеличения количества элементов количество возможных способов вставки скобок быстро растет, но они остаются ненужными для устранения неоднозначности.

Примером, когда это не работает, является логическое бикондиционал ↔ . Это ассоциативно; таким образом, A ↔ ( B ↔ C ) эквивалентно ( A ↔ B ) ↔ C , но A ↔ B ↔ C чаще всего означает ( A ↔ B ) и ( B ↔ C ) , что не эквивалентно.

Примеры

Сложение действительных чисел ассоциативно.

Некоторые примеры ассоциативных операций включают следующее.

• Объединение строк трех "hello", " ", "world" можно вычислить путем объединения первых двух строк (давая "hello ") и добавление третьей строки ( "world"), или соединив вторую и третью строку (давая " world") и объединение первой строки ( "hello") с результатом. Оба метода дают один и тот же результат; конкатенация строк ассоциативна (но не коммутативна).
• В арифметике ; сложение и умножение действительных чисел ассоциативны то есть,

  $$\left.{\begin{matrix}(x+y)+z=x+(y+z)=x+y+z\quad \\(x\,y)z=x(y\,z)=x\,y\,z\qquad \qquad \qquad \quad \ \ \,\end{matrix}}\right\}{\mbox{for all }}x,y,z\in \mathbb {R} .$$

  Из-за ассоциативности группирующие круглые скобки можно опустить без двусмысленности.
• Тривиальная операция x ∗ y = x (т. е. результатом является первый аргумент, независимо от того, каким является второй аргумент) ассоциативна, но не коммутативна. Аналогично, тривиальная операция x ∘ y = y (то есть результатом является второй аргумент, независимо от того, каким является первый аргумент) является ассоциативной, но не коммутативной.
• Сложение и умножение комплексных чисел и кватернионов ассоциативны. Сложение октонионов также ассоциативно, но умножение октонионов неассоциативно.
• Наибольший общий делитель и наименее общие кратные функции действуют ассоциативно. $$\left.{\begin{matrix}\operatorname {gcd} (\operatorname {gcd} (x,y),z)=\operatorname {gcd} (x,\operatorname {gcd} (y,z))=\operatorname {gcd} (x,y,z)\ \quad \\\operatorname {lcm} (\operatorname {lcm} (x,y),z)=\operatorname {lcm} (x,\operatorname {lcm} (y,z))=\operatorname {lcm} (x,y,z)\quad \end{matrix}}\right\}{\mbox{ for all }}x,y,z\in \mathbb {Z} .$$
• Взяв пересечение или объединение множеств ​ : $$\left.{\begin{matrix}(A\cap B)\cap C=A\cap (B\cap C)=A\cap B\cap C\quad \\(A\cup B)\cup C=A\cup (B\cup C)=A\cup B\cup C\quad \end{matrix}}\right\}{\mbox{for all sets }}A,B,C.$$
• Если M — некоторое множество, а S обозначает множество всех функций от M до M , то операция композиции функций на S ассоциативна: $$(f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h\qquad {\mbox{for all }}f,g,h\in S.$$
• В более общем смысле, учитывая четыре набора M , N , P и Q , с h : M → N , g : N → P и f : P → Q , тогда $$(f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h$$как раньше. Короче говоря, композиция карт всегда ассоциативна.
• В теории категорий композиция морфизмов ассоциативна по определению. Ассоциативность функторов и естественных преобразований следует из ассоциативности морфизмов.
• Рассмотрим набор из трех элементов A , B и C. : Следующая операция:

  ×	А	Б	С
  А	А	А	А
  Б	А	Б	С
  С	А	А	А

  является ассоциативным. Так, например, A ( B C ) = ( A B ) C = A . Эта операция не является коммутативной.
• Поскольку матрицы представляют собой линейные функции , а умножение матриц представляет композицию функций, можно сразу заключить, что умножение матриц ассоциативно.
• Для действительных чисел (и для любого полностью упорядоченного набора ) операция минимума и максимума ассоциативна: $$\max(a,\max(b,c))=\max(\max(a,b),c)\quad {\text{ and }}\quad \min(a,\min(b,c))=\min(\min(a,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.00 1 ₂ ×2 ⁴

1.000 ₂ ×2 ⁰ + (1.000 ₂ ×2 ⁰ +1.000 ₂ ×2 ⁴ ) = 1.000 ₂ ×2 ⁰ + 1.000 ₂ ×2 ⁴ = 1.00 0 ₂ ×2 ⁴

Несмотря на то, что большинство компьютеров используют 24 или 53 бита мантиссы, это по-прежнему является важным источником ошибок округления, и такие подходы, как алгоритм суммирования Кахана, являются способами минимизировать ошибки. Это может быть особенно проблематично при параллельных вычислениях.

Обозначение неассоциативных операций

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

В общем, круглые скобки должны использоваться для указания порядка вычисления , если неассоциативная операция встречается в выражении более одного раза (если только запись не определяет порядок другим способом, например ${\dfrac {2}{3/4}}$). Однако математики договорились об определенном порядке вычисления некоторых распространенных неассоциативных операций. Это просто соглашение об обозначениях, позволяющее избежать круглых скобок.

операция Левоассоциативная — это неассоциативная операция, которая традиционно вычисляется слева направо, т. е.

$$\left.{\begin{array}{l}a*b*c=(a*b)*c\\a*b*c*d=((a*b)*c)*d\\a*b*c*d*e=(((a*b)*c)*d)*e\quad \\{\mbox{etc.}}\end{array}}\right\}{\mbox{for all }}a,b,c,d,e\in S$$

тогда как правоассоциативная операция традиционно оценивается справа налево:

$$\left.{\begin{array}{l}x*y*z=x*(y*z)\\w*x*y*z=w*(x*(y*z))\quad \\v*w*x*y*z=v*(w*(x*(y*z)))\quad \\{\mbox{etc.}}\end{array}}\right\}{\mbox{for all }}z,y,x,w,v\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 года, когда он размышлял о неассоциативной алгебре октонионов, о которой он узнал от Джона Т. Грейвса .

См. также

• Тест на ассоциативность Лайта
• Телескопический ряд , использование дополнительной ассоциативности для сокращения членов бесконечного ряда.
• Полугруппа — это множество с ассоциативной бинарной операцией.
• Коммутативность и дистрибутивность — два других часто обсуждаемых свойства бинарных операций.
• Степенная ассоциативность , альтернативность , гибкость и N-арная ассоциативность являются слабыми формами ассоциативности.
• Личности Муфанг также обеспечивают слабую форму ассоциативности.