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

Свойство математической операции

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

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

$${\displaystyle {\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 приводят к решетке Тамари четвертого порядка, возможно, к различным продуктам.

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

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

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

а б в г .

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

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

Примеры

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

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

• Объединение трех строк , , можно вычислить путем объединения первых двух строк (выдача ) и добавления третьей строки ( ) или путем соединения второй и третьей строк (выдача ) и объединения первой строки ( ) с результатом. Оба метода дают один и тот же результат; конкатенация строк ассоциативна (но не коммутативна)."hello"" ""world""hello ""world"" world""hello"
• В арифметике сложение и умножение действительных чисел ассоциативны ; то есть,
  $${\displaystyle \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 (то есть результатом является второй аргумент, независимо от того, каким является первый аргумент) является ассоциативной, но не коммутативной.
• Сложение и умножение комплексных чисел и кватернионов ассоциативны. Сложение октонионов также ассоциативно, но умножение октонионов неассоциативно.
• Наибольший общий делитель и наименее общие кратные функции действуют ассоциативно.
  $${\displaystyle \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} .}$$
• Взяв пересечение или объединение множеств : _
  $${\displaystyle \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 ассоциативна:
  $${\displaystyle (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 , тогда
  $${\displaystyle (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 . Эта операция не является коммутативной.
• Поскольку матрицы представляют собой линейные функции , а умножение матриц представляет композицию функций, можно сразу заключить, что умножение матриц ассоциативно. ^[3]
• Для действительных чисел (и для любого полностью упорядоченного набора ) операция минимума и максимума ассоциативна:
  $${\displaystyle \max(a,\max(b,c))=\max(\max(a,b),c)\quad {\text{ and }}\quad \min(a,\min(b,c))=\min(\min(a,b),c).}$$

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

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

В стандартной логике высказываний с функциональной истинностью ассоциация , ^{[4] [5]} или ассоциативность ^[6] являются двумя действительными правилами замены . Правила позволяют передвигать скобки в логических выражениях в логических доказательствах . Правила (с использованием обозначения логических связок ):

$${\displaystyle (P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)}$$

и

$${\displaystyle (P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R),}$$

где « » — металогический символ , обозначающий «может быть заменен в доказательстве на». ${\displaystyle \Leftrightarrow }$

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

Ассоциативность — это свойство некоторых логических связок истинностно-функциональной логики высказываний . Следующие логические эквивалентности демонстрируют, что ассоциативность является свойством определенных связок. Следующие ниже (и их обратные, поскольку ↔ коммутативен) являются истинностно-функциональными тавтологиями . ^{[ нужна цитата ]}

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

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

Ассоциативность союза

${\displaystyle ((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))}$

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

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

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

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

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

$${\displaystyle (x*y)*z\neq x*(y*z)\qquad {\mbox{for some }}x,y,z\in S.}$$

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

Вычитание

${\displaystyle (5-3)-2\,\neq \,5-(3-2)}$

Разделение

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

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

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

Векторное векторное произведение

${\displaystyle {\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}}}$

Кроме того, хотя сложение ассоциативно для конечных сумм, оно не ассоциативно внутри бесконечных сумм ( рядов ). Например,

$${\displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots =0}$$

$${\displaystyle 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots =1.}$$

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

Другими примерами являются квазигруппа , квазиполе , неассоциативное кольцо и коммутативная неассоциативная магма .

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

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

Чтобы проиллюстрировать это, рассмотрим представление с плавающей запятой с 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 битами мантиссы, ^[8] это является важным источником ошибок округления, и такие подходы, как алгоритм суммирования Кахана , являются способами минимизировать ошибки. Это может быть особенно проблематично при параллельных вычислениях. ^{[9] [10]}

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

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

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

$${\displaystyle \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}$$

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

$${\displaystyle \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}$$

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

Вычитание и деление действительных чисел ^{[11] [12] [13] [14] [15]}

${\displaystyle x-y-z=(x-y)-z}$

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

Применение функции

${\displaystyle (f\,x\,y)=((f\,x)\,y)}$

Это обозначение может быть мотивировано изоморфизмом каррирования , который допускает частичное применение.

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

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

${\displaystyle x^{y^{z}}=x^{(y^{z})}}$

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

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

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

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

${\displaystyle \mathbb {Z} \rightarrow \mathbb {Z} \rightarrow \mathbb {Z} =\mathbb {Z} \rightarrow (\mathbb {Z} \rightarrow \mathbb {Z} )}$

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

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

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

Возведение в степень действительных чисел в инфиксной записи ^[16]

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

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

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

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

Взяв векторное произведение трех векторов

${\displaystyle {\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}}$

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

${\displaystyle {(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.}$

Взяв относительное дополнение множеств

${\displaystyle (A\backslash B)\backslash C\neq A\backslash (B\backslash C)}$.

(Сравните материальную неимпликацию в логике.)

История

Уильям Роуэн Гамильтон, по-видимому, ввёл термин «ассоциативное свойство» ^[17] примерно в 1844 году, когда он размышлял о неассоциативной алгебре октонионов, о которой он узнал от Джона Т. Грейвса . ^[18]

Смотрите также

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

Рекомендации

1. Хангерфорд, Томас В. (1974). Алгебра (1-е изд.). Спрингер . п. 24. ISBN 978-0387905181. Определение 1.1 (i) a(bc) = (ab)c для всех a, b, c в G.
2. Дурбин, Джон Р. (1992). Современная алгебра: введение (3-е изд.). Нью-Йорк: Уайли. п. 78. ИСБН 978-0-471-51001-7. Если являются элементами множества с ассоциативной операцией, то произведение однозначно; то есть один и тот же элемент будет получен независимо от того, как в произведении вставлены скобки. ${\displaystyle a_{1},a_{2},\dots ,a_{n}\,\,(n\geq 2)}$ ${\displaystyle a_{1}a_{2}\cdots a_{n}}$
3. «Ассоциативность матричного продукта» . Ханская академия . Проверено 5 июня 2016 г.
4. Мур, Брук Ноэль; Паркер, Ричард (2017). Критическое мышление (12-е изд.). Нью-Йорк: Образование Макгроу-Хилл. п. 321. ИСБН 9781259690877.
5. Копи, Ирвинг М.; Коэн, Карл; МакМахон, Кеннет (2014). Введение в логику (14-е изд.). Эссекс: Pearson Education. п. 387. ИСБН 9781292024820.
6. Херли, Патрик Дж.; Уотсон, Лори (2016). Краткое введение в логику (13-е изд.). Бостон: Cengage Learning. п. 427. ИСБН 9781305958098.
7. Кнут, Дональд, Искусство компьютерного программирования , Том 3, раздел 4.2.2
8. Компьютерное общество IEEE (29 августа 2008 г.). Стандарт IEEE для арифметики с плавающей запятой . doi :10.1109/IEESTD.2008.4610935. ISBN 978-0-7381-5753-5. Стандарт IEEE 754-2008.
9. Вилла, Оресте; Чаваррия-мир, Даниэль; Гурумурти, Видья; Маркес, Андрес; Кришнамурти, Шрирам, Эффекты неассоциативности с плавающей запятой на числовые вычисления в многопоточных системах (PDF) , заархивировано из оригинала (PDF) 15 февраля 2013 г. , получено 8 апреля 2014 г.
10. Голдберг, Дэвид (март 1991 г.). «Что должен знать каждый ученый-компьютерщик об арифметике с плавающей запятой» (PDF) . Обзоры вычислительной техники ACM . 23 (1): 5–48. дои : 10.1145/103162.103163. S2CID  222008826. Архивировано (PDF) из оригинала 19 мая 2022 г. Проверено 20 января 2016 г.
11. Джордж Марк Бергман «Порядок арифметических операций»
12. «Порядок действий». Место образования.
13. «Порядок действий», временная метка 5:40 с. Ханская академия .
14. «Использование порядка операций и исследование свойств». Архивировано 16 июля 2022 г. в Wayback Machine , раздел 9. Департамент образования Вирджинии.
15. Бронштейн, de:Taschenbuch der Mathematik , страницы 115-120, глава: 2.4.1.1, ISBN 978-3-8085-5673-3 
16. Ассоциативность возведения в степень и стандартная математическая запись Codeplea. 23 августа 2016 г. Проверено 20 сентября 2016 г.
17. Гамильтон, WR (1844–1850). «О кватернионах или новой системе воображаемых в алгебре». Коллекция Дэвида Р. Уилкинса. Философский журнал . Тринити-колледж Дублина .
18. Баэз, Джон К. (2002). «Октонионы» (PDF) . Бюллетень Американского математического общества . 39 (2): 145–205. arXiv : math/0105155 . doi : 10.1090/S0273-0979-01-00934-X. ISSN  0273-0979. MR  1886087. S2CID  586512.