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

Свойство, позволяющее удалять круглые скобки в последовательности операций

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

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

$(2\; +\; 3)\; +\; 4\; =\; 2\; +\; (3\; +\; 4)\; =\; 9\; \{\backslash \; displaystyle\; (2\; +\; 3)\; +\; 4\; =\; 2\; +\; (3\; +\; 4)\; =\; 9\; \backslash ,\}$

$2\; \times \; (3\; \times \; 4)\; =\; (2\; \times \; 3)\; \times \; 4\; =\; 24.\; \{\backslash \; displaystyle\; 2\; \backslash \; times\; (3\; \backslash \; times\; 4)\; =\; (2\; \backslash \; times\; 3)\; \backslash \; times\; 4\; =\; 24.\}$

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

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

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

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

Содержание

• 1 Определение
• 2 Обобщенный ассоциативный закон
• 3 Примеры
• 4 Логика высказываний
  • 4.1 Правило замены
  • 4.2 Истинные функциональные связки
• 5 Неассоциативная операция
  • 5.1 Неассоциативность вычисления с плавающей запятой
  • 5.2 Обозначение для неассоциативных операций
• 6 См. Также
• 7 Ссылки

Определение

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

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

(x ∗ y) ∗ z = x ∗ (y ∗ z) для всех x, y, z в S.

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

(xy) z = x (yz) = xyz для всех x, y, z в S.

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

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

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

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

$((ab)\; c)\; d\; \{\backslash \; displaystyle\; ((ab)\; c)\; d\}$

$(\; ab)\; (cd)\; \{\backslash \; displaystyle\; (ab)\; (cd)\}$

$(a\; (bc))\; d\; \{\backslash \; displaystyle\; (a\; (bc))\; d\}$

$a\; ((bc)\; d)\; \{\backslash \; displaystyle\; a\; ((bc)\; d)\}$

$a\; (b\; (cd))\; \{\backslash \; displaystyle\; a\; (b\; (cd))\}$

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

$a\; b\; c\; d.\; \{\backslash \; displaystyle\; abcd.\}$

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

Примером, где это не работает, является логическая двусмысленность $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$. Он ассоциативен, поэтому A $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$(B$\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$C) эквивалентно (A $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$B)$\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$C, но A $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$B$\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$C чаще всего означает ( A $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$B и B $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$C), что не эквивалентно.

Примеры

В ассоциативных операциях это $(x\; \circ \; y)\; \circ \; z\; =\; x\; \circ \; (y\; \circ \; z)\; \{\backslash \; displaystyle\; (x\; \backslash \; circ\; y)\; \backslash \; circ\; z\; =\; x\; \backslash \; circ\; (y\; \backslash \; circ\; z)\}$. Добавление действительных чисел является ассоциативным.

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

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

$(x\; +\; y)\; +\; z\; =\; x\; +\; (y\; +\; z)\; =\; x\; +\; y\; +\; z\; (x\; y)\; z\; =\; x\; (y\; z)\; =\; x\; y\; z\}\; для\; всех\; x,\; y,\; z\; \in \; R.\; \{\backslash \; displaystyle\; \backslash \; left.\; \{\backslash \; begin\; \{matrix\}\; (x\; +\; y)\; +\; z\; =\; x\; +\; (y\; +\; z)\; =\; x\; +\; y\; +\; z\; \backslash \; quad\; \backslash \backslash \; (x\; \backslash ,\; y)\; z\; =\; x\; (y\; \backslash ,\; z))\; =\; x\; \backslash ,\; y\; \backslash ,\; z\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; quad\; \backslash \; \backslash \; \backslash ,\; \backslash \; end\; \{matrix\}\}\; \backslash \; right\; \backslash \}\; \{\backslash \; t\_dv\; \{для\; всех\}\}\; x,\; y,\; z\; \backslash \; in\; \backslash \; mathbb\; \{R\; \}.\}$

Из-за ассоциативности группирующие скобки можно опустить без двусмысленности.

• Тривиальная операция x ∗ y = x (то есть результат - первый аргумент, независимо от того, какой второй аргумент) ассоциативный, но не коммутативный. Точно так же тривиальная операция x ∘ y = y (то есть результат - второй аргумент, независимо от того, какой является первый аргумент) ассоциативна, но не коммутативна.
• Сложение и умножение комплексных чисел и кватернионы ассоциативны. Сложение октонионов также ассоциативно, но умножение октонионов неассоциативно.
• Действуют функции наибольший общий делитель и наименьшее общее кратное ассоциативно.

$gcd\; \; (gcd\; \; (x,\; y),\; z)\; =\; gcd\; \; (x,\; gcd\; \; (y,\; z))\; =\; gcd\; \; (x,\; y,\; z)\; lcm\; \; (lcm\; \; (x,\; y),\; z)\; =\; lcm\; \; (x,\; lcm\; \; (y,\; z))\; =\; lcm\; \; (x,\; y,\; z)\}\; для\; всех\; x,\; y,\; z\; \in \; Z.\; \{\backslash \; displaystyle\; \backslash \; left.\; \{\backslash \; begin\; \{matrix\}\; \backslash \; operatorname\; \{gcd\}\; (\backslash \; operatorname\; \{gcd\}\; (x,\; y),\; z)\; =\; \backslash \; operatorname\; \{gcd\}\; (x,\; \backslash \; operatorname\; \{gcd\}\; (y,\; z))\; =\; \backslash \; operatorname\; \{gcd\}\; (x,\; y,\; z)\; \backslash \; \backslash \; quad\; \backslash \backslash \backslash \; operatorname\; \{lcm\}\; (\backslash \; operatorname\; \{lcm\}\; (x,\; y),\; z)\; =\; \backslash \; operatorname\; \{lcm\}\; (x,\; \backslash \; operatorname\; \{\; lcm\}\; (y,\; z))\; =\; \backslash \; operatorname\; \{lcm\}\; (x,\; y,\; z)\; \backslash \; quad\; \backslash \; end\; \{matrix\}\}\; \backslash \; right\; \backslash \}\; \{\backslash \; t\_dv\; \{для\; всех\}\}\; x,\; y,\; z\; \backslash \; in\; \backslash \; mathbb\; \{Z\}.\}$

• Взяв пересечение или объединение из , получаем :

$(A\; \cap \; B)\; \cap \; C\; =\; A\; \cap \; (B\; \cap \; C)\; =\; A\; \cap \; B\; \cap \; C\; (A\; \cup \; B)\; \cup \; C\; =\; A\; \cup \; (B\; \cup \; C)\; =\; A\; \cup \; B\; \cup \; C\}\; для\; всех\; множеств\; A,\; B,\; C.\; \{\backslash \; displaystyle\; \backslash \; left.\; \{\backslash \; begin\; \{matrix\}\; (A\; \backslash \; cap\; B)\; \backslash \; cap\; C\; =\; A\; \backslash \; cap\; (B\; \backslash \; cap\; C)\; =\; A\; \backslash \; cap\; B\; \backslash \; cap\; C\; \backslash \; quad\; \backslash \backslash \; (A\; \backslash \; cup\; B)\; \backslash \; чашка\; C\; =\; A\; \backslash \; cup\; (B\; \backslash \; cup\; C)\; =\; A\; \backslash \; cup\; B\; \backslash \; cup\; C\; \backslash \; quad\; \backslash \; end\; \{matrix\}\}\; \backslash \; right\; \backslash \}\; \{\backslash \; t\_dv\; \{для\; всех\; наборов\}\}\; A,\; B,\; C.\}$

• Если M - некоторое множество и S обозначает множество всех функций от M до M, то операция композиции функций на S ассоциативна:

$(f\; \circ \; g)\; \circ \; h\; =\; f\; \circ \; (\; g\; \circ \; h)\; =\; f\; \circ \; g\; \circ \; h\; для\; всех\; f,\; g,\; h\; \in \; S.\; \{\backslash \; Displaystyle\; (е\; \backslash \; circ\; g)\; \backslash \; circ\; h\; =\; f\; \backslash \; circ\; (g\; \backslash \; circ\; h)\; =\; f\; \backslash \; circ\; g\; \backslash \; circ\; h\; \backslash \; qquad\; \{\backslash \; t\_dv\; \{для\; всех\}\}\; f,\; g,\; h\; \backslash \; in\; S.\}$

• В более общем плане, учитывая четыре набора M, N, P и Q, где h: M до N, g: N до P и f: P до Q, тогда

$(f\; \circ \; g)\; \circ \; h\; =\; е\; \circ \; (г\; \circ \; час)\; знак\; равно\; е\; \circ \; г\; \circ \; час\; \{\backslash \; displaystyle\; (f\; \backslash \; circ\; g)\; \backslash \; circ\; h\; =\; f\; \backslash \; circ\; (g\; \backslash \; circ\; h)\; =\; f\; \backslash \; circ\; g\; \backslash \; circ\; h\}$

, как и раньше. Короче говоря, композиция карт всегда ассоциативна.

• Рассмотрим набор из трех элементов: A, B и C. Следующая операция:

×	A	B	C
A	A	A	A
B	A	B	C
C	A	A	A

ассоциативна. Таким образом, например, A (BC) = (AB) C = A. Эта операция не является коммутативной.

• Поскольку матрицы представляют линейные функции, а матричное умножение представляет композицию функций, можно сразу сделать вывод, что матричное умножение ассоциативно.

Логика высказываний

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

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

$(P\; \vee \; (Q\; \vee \; R))\; \iff \; ((P\; \vee \; Q)\; \vee \; R)\; \{\backslash \; displaystyle\; (P\; \backslash \; lor\; (Q\; \backslash \; lor\; R)))\; \backslash \; Leftrightarrow\; ((P\; \backslash \; lor\; Q)\; \backslash \; lor\; R)\}$

и

$(P\; \wedge \; (Q\; \wedge \; R))\; \iff \; ((P\; \wedge \; Q)\; \wedge \; R),\; \{\backslash \; displaystyle\; (P\; \backslash \; land\; (Q\; \backslash \; land\; R))\; \backslash \; Leftrightarrow\; ((P\; \backslash \; land\; Q)\; \backslash \; land\; R),\}$

где "$\iff \; \{\backslash \; displaystyle\; \backslash \; Leftrightarrow\}$" - это металогическое символ, представляющий «может быть заменен в пробе на.»

Функциональные связки истинности

Ассоциативность - это свойство некоторых логических связок функциональных связок истинности логики высказываний. Следующие логические эквиваленты демонстрируют, что ассоциативность является свойством определенных связок. Ниже приведены функциональные истинности тавтологии.

Ассоциативность дизъюнкции :

$((P\; \vee \; Q)\; \vee \; R)\; \leftrightarrow \; (P\; \vee \; (Q\; \vee \; R))\; \{\backslash \; displaystyle\; ((P\; \backslash \; lor\; Q)\; \backslash \; lor\; R)\; \backslash \; leftrightarrow\; (P\; \backslash \; lor\; (Q\; \backslash \; lor\; R))\}$

$(P\; \vee \; (Q\; \vee \; R))\; \leftrightarrow \; ((P\; \vee \; Q)\; \vee \; R)\; \{\backslash \; displaystyle\; (P\; \backslash \; lor\; (Q\; \backslash \; lor\; R)))\; \backslash \; leftrightarrow\; ((P\; \backslash \; lor\; Q)\; \backslash \; lor\; R)\}$

Ассоциативность конъюнкции :

$((P\; \wedge \; Q)\; \wedge \; R)\; \leftrightarrow \; (P\; \wedge \; (Q\; \wedge \; R))\; \{\backslash \; displaystyle\; ((P\; \backslash \; земля\; Q)\; \backslash \; земля\; R)\; \backslash \; leftrightarrow\; (P\; \backslash \; земля\; (Q\; \backslash \; земля\; R))\}$

$(P\; \wedge \; (Q\; \wedge \; R))\; \leftrightarrow \; ((P\; \wedge \; Q)\; \wedge \; R)\; \{\backslash \; displaystyle\; (P\; \backslash \; земля\; (Q\; \backslash \; земля\; R))\; \backslash \; leftrightarrow\; ((P\; \backslash \; земля\; Q)\; \backslash \; земля\; R)\}$

Ассоциативность эквивалентности :

$((P\; \leftrightarrow \; Q)\; \leftrightarrow \; R)\; \leftrightarrow \; (P\; \leftrightarrow \; (Q\; \leftrightarrow \; R))\; \{\backslash \; Displaystyle\; ((P\; \backslash \; leftrightarrow\; Q)\; \backslash \; leftrightarrow\; R)\; \backslash \; leftrightarrow\; (P\; \backslash \; leftrightarrow\; (Q\; \backslash \; leftrightarrow\; R))\}$

$(P\; \leftrightarrow \; (Q\; \leftrightarrow \; R))\; \leftrightarrow \; ((P\; \leftrightarrow \; Q)\; \leftrightarrow \; R)\; \{\backslash \; displaystyle\; (P\; \backslash \; leftrightarrow\; (Q\; \backslash \; leftrightarrow\; R))\; \backslash \; leftrightarrow\; ((P\; \backslash \; leftrightarrow\; Q)\; \backslash \; leftrightarrow\; R)\}$

Совместное отрицание - пример функциональной связки истинности, которая не является ассоциативной.

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

Бинарная операция $\ast \; \{\backslash \; displaystyle\; *\}$на множестве S, которая не удовлетворяет ассоциативному закону, называется неассоциативный . Символически

$(x\; \ast \; y)\; \ast \; z\; \ne \; x\; \ast \; (y\; \ast \; z)\; для\; некоторых\; x,\; y,\; z\; \in \; S.\; \{\backslash \; displaystyle\; (x\; *\; y)\; *\; z\; \backslash \; neq\; x\; *\; (y\; *\; z)\; \backslash \; qquad\; \{\backslash \; t\_dv\; \{for\; some\}\}\; x,\; y,\; z\; \backslash \; in\; S.\}$

Для такой операции порядок оценки имеет значение. Например:

• Вычитание

$(5–3)\; -\; 2\; \ne \; 5\; -\; (3–2)\; \{\backslash \; displaystyle\; (5-3)\; -2\; \backslash ,\; \backslash \; neq\; \backslash ,\; 5-\; (3-2)\}$

• Деление

$(4/2)\; /\; 2\; \ne \; 4\; /\; (2/2)\; \{\backslash \; displaystyle\; (4/2)\; /\; 2\; \backslash ,\; \backslash \; neq\; \backslash ,\; 4\; /\; (2/2)\}$

• Возведение в степень

$2\; (1\; 2)\; \ne \; (2\; 1)\; 2\; \{\backslash \; displaystyle\; 2\; ^\; \{(1\; ^\; \{2\})\}\; \backslash ,\; \backslash \; neq\; \backslash ,\; (2\; ^\; \{1\})\; ^\; \{2\}\}$

Также обратите внимание что бесконечные суммы обычно не ассоциативны, например:

$(1\; +\; -\; 1)\; +\; (1\; +\; -\; 1)\; +\; (1\; +\; -\; 1)\; +\; (1\; +\; -\; 1)\; +\; (1\; +\; -\; 1)\; +\; (\; 1\; +\; -\; 1)\; +\dots \; знак\; равно\; 0\; \{\backslash \; displaystyle\; (1\; +\; -1)\; +\; (1\; +\; -1)\; +\; (1\; +\; -1)\; +\; (1\; +\; -1)\; +\; (1\; +\; -1)\; +\; (1+\; -1)\; +\; \backslash \; dots\; \backslash ,\; =\; \backslash ,\; 0\}$

, тогда как

$1\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\dots \; =\; 1\; \{\backslash \; displaystyle\; 1\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; (-1\; +\; 1)\; +\; (-\; 1\; +\; 1)\; +\; \backslash \; dots\; \backslash ,\; =\; \backslash ,\; 1\}$

Изучение неассоциативных структур возникает по причинам, несколько отличным от основного направления классической алгебры. Одна область в неассоциативной алгебре, которая стала очень большой, - это область алгебр Ли. Там ассоциативный закон заменяется тождеством Якоби . Алгебры Ли абстрагируют сущность бесконечно малых преобразований и стали повсеместными в математике.

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

Неассоциативность вычисления с плавающей запятой

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

Чтобы проиллюстрировать это, рассмотрим представление с плавающей запятой с 4-битной мантиссой :. (1.000 2 × 2 + 1.000 2 × 2) + 1.000 2 × 2 = 1.000 2 × 2 + 1.000 2 × 2 = 1.001 2×2. 1.000 2 × 2 + (1.000 2 × 2 + 1.000 2 × 2) = 1.000 2 × 2 + 1.000 2 × 2 = 1.000 2×2

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

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

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

A левоассоциативная операция - это неассоциативная операция, которая обычно вычисляется слева направо, т. Е.

$x\; \ast \; y\; \ast \; z\; =\; (x\; \ast \; y)\; \ast \; zw\; \ast \; x\; \ast \; y\; \ast \; z\; =\; ((w\; \ast \; x)\; \ast \; y)\; \ast \; z\; и\; т.\; д.\}\; для\; всех\; w,\; x,\; y,\; z\; \in \; S\; \{\backslash \; displaystyle\; \backslash \; left.\; \{\backslash \; begin\; \{matrix\}\; x\; *\; y\; *\; z\; =\; (x\; *\; y)\; *\; z\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; quad\; \backslash ,\; \backslash \backslash \; w\; *\; x\; *\; y\; *\; z\; =\; ((w\; *\; x)\; *\; y)\; *\; z\; \backslash \; quad\; \backslash \backslash \; \{\backslash \; t\_dv\; \{и\; т.\; д.\}\}\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; \backslash \; \backslash ,\; \backslash \; end\; \{matrix\}\}\; \backslash \; right\; \backslash \}\; \{\backslash \; t\_dv\; \{для\; всех\}\}\; w,\; x,\; y,\; z\; \backslash \; in\; S\}$

в то время как правоассоциативный операция условно вычисляется справа налево:

$x\; \ast \; y\; \ast \; z\; =\; x\; \ast \; (y\; \ast \; z)\; w\; \ast \; x\; \ast \; y\; \ast \; z\; =\; w\; \ast \; (x\; \ast \; (y\; \ast \; z))\; и\; т.\; д.\}\; для\; всех\; w\; Икс,\; Y,\; Z\; \in \; S\; \{\backslash \; Displaystyle\; \backslash \; влево.\; \{\backslash \; begin\; \{matrix\}\; х\; *\; у\; *\; Z\; =\; х\; *\; (у\; *\; г)\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; quad\; \backslash ,\; \backslash \backslash \; ш\; *\; х\; *\; у\; *\; г\; =\; w\; *\; (x\; *\; (y\; *\; z))\; \backslash \; quad\; \backslash \backslash \; \{\backslash \; t\_dv\; \{и\; т.\; д.\}\}\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; \backslash \; \backslash ,\; \backslash \; end\; \{matrix\}\}\; \backslash \; right\; \backslash \}\; \{\backslash \; t\_dv\; \{для\; всех\}\}\; w,\; x,\; y,\; z\; \backslash \; in\; S\}$

Имеются как левоассоциативные, так и правоассоциативные операции. К левоассоциативным операциям относятся следующие:

• Вычитание и деление действительных чисел:

$x\; -\; y\; -\; z\; =\; (x\; -\; y)\; -\; z\; \{\backslash \; displaystyle\; xyz\; =\; (xy)\; -z\}$

$x\; /\; y\; /\; z\; =\; (x\; /\; y)\; /\; z\; \{\backslash \; displaystyle\; x\; /\; y\; /\; z\; =\; (x\; /\; y)\; /\; z\}$

• Функция приложения:

$(fxy)\; =\; ((fx)\; y)\; \{\backslash \; displaystyle\; (f\; \backslash ,\; x\; \backslash ,\; y)\; =\; ((f\; \backslash ,\; x)\; \backslash ,\; y)\}$

Это обозначение может быть мотивировано изоморфизмом каррирования.

Правоассоциативные операции включают следующее:

• Возведение в степень действительных чисел в надстрочной записи:

$xyz\; =\; x\; (yz)\; \{\backslash \; displaystyle\; x\; ^\; \{y\; ^\; \{z\}\}\; =\; x\; ^\; \{(y\; ^\; \{z\})\}\}$

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

$(xy)\; z\; =\; x\; (yz)\; \{\backslash \; displaystyle\; (x\; ^\; \{y\})\; ^\; \{z\}\; =\; x\; ^\; \{(yz)\}\}$

Отформатировано правильно, надстрочный индекс по своей природе представляет собой набор круглых скобок; например в выражении $2\; x\; +\; 3\; \{\backslash \; displaystyle\; 2\; ^\; \{x\; +\; 3\}\}$сложение выполняется перед возведением в степень, несмотря на отсутствие явных скобок $2\; (x\; +\; 3)\; \{\backslash \; displaystyle\; 2\; ^\; \{(x\; +\; 3)\}\}$обернут вокруг него. Таким образом, с учетом такого выражения, как $xyz\; \{\backslash \; displaystyle\; x\; ^\; \{y\; ^\; \{z\}\}\}$, полный показатель $yz\; \{\backslash \; displaystyle\; y\; ^\; \{z\}\}$базы $x\; \{\backslash \; displaystyle\; x\}$оценивается первым. Однако в некоторых контекстах, особенно в почерке, разница между $xyz\; =\; (xy)\; z\; \{\backslash \; displaystyle\; \{x\; ^\; \{y\}\}\; ^\; \{z\}\; =\; (x\; ^\; \{y\})\; ^\; \{z\}\}$, $xyz\; =\; x\; (yz)\; \{\backslash \; displaystyle\; x\; ^\; \{yz\}\; =\; x\; ^\; \{(yz)\}\}$и $xyz\; =\; x\; (yz)\; \{\backslash \; displaystyle\; x\; ^\; \{y\; ^\; \{\; z\}\}\; =\; x\; ^\; \{(y\; ^\; \{z\})\}\}$может быть трудно увидеть. В таком случае обычно подразумевается право-ассоциативность.

• Определение функции

$Z\; \to \; Z\; \to \; Z\; =\; Z\; \to \; (Z\; \to \; Z)\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; \backslash \; rightarrow\; \backslash \; mathbb\; \{Z\}\; \backslash \; rightarrow\; \backslash \; mathbb\; \{Z\}\; =\; \backslash \; mathbb\; \{Z\}\; \backslash \; rightarrow\; (\backslash \; mathbb\; \{Z\}\; \backslash \; rightarrow\; \backslash \; mathbb\; \{Z\})\}$

$x\; \mapsto \; y\; \mapsto \; x\; -\; y\; =\; x\; \mapsto \; (y\; \mapsto \; x\; -\; y)\; \{\backslash \; displaystyle\; x\; \backslash \; mapsto\; y\; \backslash \; mapsto\; xy\; =\; x\; \backslash \; mapsto\; (y\; \backslash \; mapsto\; xy)\}$

Использование правоассоциативных обозначений для этих операций может быть мотивировано соответствием Карри – Ховарда и каррирование изоморфизм.

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

• Возведение в степень действительных чисел в инфиксной записи:

$(x\; \wedge \; y)\; \wedge \; z\; \ne \; x\; \wedge \; (y\; \wedge \; z)\; \{\backslash \; displaystyle\; (x\; ^\; \{\backslash \; wedge\}\; y)\; ^\; \{\backslash \; wedge\}\; z\; \backslash \; neq\; x\; ^\; \{\backslash \; wedge\}\; (y\; ^\; \{\backslash \; wedge\}\; z)\}$

• Операторы Кнута со стрелкой вверх :

$a\; \uparrow \uparrow \; (b\; \uparrow \uparrow \; c)\; \ne \; (a\; \uparrow \uparrow \; b)\; \uparrow \uparrow \; c\; \{\backslash \; displaystyle\; a\; \backslash \; uparrow\; \backslash \; uparrow\; (b\; \backslash \; uparrow\; \backslash \; uparrow\; c)\; \backslash \; neq\; (a\; \backslash \; uparrow\; \backslash \; uparrow\; b)\; \backslash \; uparrow\; \backslash \; uparrow\; c\}$

$a\; \uparrow \uparrow \uparrow \; (b\; \uparrow \uparrow \uparrow \; c)\; \ne \; (a\; \uparrow \uparrow \uparrow \; b)\; \uparrow \; \uparrow \uparrow \; c\; \{\backslash \; displaystyle\; a\; \backslash \; uparrow\; \backslash \; uparrow\; \backslash \; uparrow\; (b\; \backslash \; uparrow\; \backslash \; uparrow\; \backslash \; uparrow\; c)\; \backslash \; neq\; (a\; \backslash \; uparrow\; \backslash \; uparrow\; \backslash \; uparrow\; b)\; \backslash \; uparrow\; \backslash \; uparrow\; \backslash \; uparrow\; c\}$

• Принимая перекрестное произведение трех векторов:

$a\; \to \; \times \; (b\; \to \; \times \; c\; \to )\; \ne \; (a\; \to \; \times \; b\; \to )\; \times \; c\; \to \; для\; некоторых\; a\; \to ,\; b\; \to ,\; c\; \to \; \in \; R\; 3\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{a\}\}\; \backslash \; times\; (\{\backslash \; vec\; \{b\}\}\; \backslash \; times\; \{\backslash \; vec\; \{c\}\})\; \backslash \; neq\; (\{\backslash \; vec\; \{a\}\}\; \backslash \; times\; \{\backslash \; vec\; \{b\}\})\; \backslash \; times\; \{\; \backslash \; vec\; \{c\}\}\; \backslash \; qquad\; \{\backslash \; t\_dv\; \{для\; некоторых\}\}\; \{\backslash \; vec\; \{a\}\},\; \{\backslash \; vec\; \{b\}\},\; \{\backslash \; vec\; \{c\}\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{3\}\; \}$

• Взяв попарное среднее действительных чисел:

$(x\; +\; y)\; /\; 2\; +\; z\; 2\; \ne \; x\; +\; (y\; +\; z)\; /\; 2\; 2\; для\; всех\; x,\; y,\; z\; \in \; R\; с\; x\; \ne \; z.\; \{\backslash \; displaystyle\; \{(x\; +\; y)\; /\; 2\; +\; z\; \backslash \; over\; 2\}\; \backslash \; neq\; \{x\; +\; (y\; +\; z)\; /\; 2\; \backslash \; over\; 2\}\; \backslash \; qquad\; \{\backslash \; t\_dv\; \{для\; всех\}\}\; x,\; y,\; z\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; \{\backslash \; t\_dv\; \{with\}\}\; x\; \backslash \; neq\; z.\}$

• Взяв относительное дополнение наборов $(A\; \setminus \; B)\; \setminus \; C\; \{\backslash \; displaystyle\; (A\; \backslash \; backslash\; B)\; \backslash \; обратная\; косая\; черта\; C\}$отличается от $A\; \setminus \; (B\; \setminus \; C)\; \{\backslash \; displaystyle\; A\; \backslash \; backslash\; (B\; \backslash \; backslash\; C)\}$. (Сравните материальное непроявление в логике.)

См. Также

Найдите ассоциативное свойство в Викисловаре, бесплатном словаре.

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

Ссылки