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

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

В математике ассоциативное свойство ^[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 называется ассоциативной, если она удовлетворяет ассоциативному закону : ${\displaystyle \ast }$

${\displaystyle (x\ast y)\ast z=x\ast (y\ast z)}$, для всех в S .}} ${\displaystyle x,y,z}$

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

${\displaystyle (xy)z=x(yz)}$, для всех в S . ${\displaystyle x,y,z}$

Ассоциативный закон можно также выразить в функциональной записи следующим образом: ${\displaystyle (f\circ (g\circ h))(x)=((f\circ g)\circ h)(x)}$

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

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

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

Число возможных скобок — это просто каталонское число , , для n операций над n+1 значениями. Например, произведение 3 операций над 4 элементами может быть записано (игнорируя перестановки аргументов) следующими возможными способами: ${\displaystyle C_{n}}$ ${\displaystyle C_{3}=5}$

• ${\displaystyle ((ab)c)d}$
• ${\displaystyle (a(bc))d}$
• ${\displaystyle a((bc)d)}$
• ${\displaystyle (a(b(cd))}$
• ${\displaystyle (ab)(cd)}$

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

${\displaystyle abcd}$

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

Примером, где это не работает, является логическое двуусловие ↔ . Оно ассоциативно; таким образом, 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-е изд.). Springer . стр. 24. ISBN 978-0387905181Определение 1.1 (i) a(bc) = (ab)c для всех a, b, c из G.
2. Дурбин, Джон Р. (1992). Современная алгебра: введение (3-е изд.). Нью-Йорк: Wiley. стр. 78. ISBN 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. "Ассоциативность матричного продукта". Khan Academy . Получено 5 июня 2016 г.
4. Мур, Брук Ноэль; Паркер, Ричард (2017). Критическое мышление (12-е изд.). Нью-Йорк: McGraw-Hill Education. стр. 321. ISBN 9781259690877.
5. Копи, Ирвинг М.; Коэн, Карл; Макмахон, Кеннет (2014). Введение в логику (14-е изд.). Эссекс: Pearson Education. стр. 387. ISBN 9781292024820.
6. Херли, Патрик Дж.; Уотсон, Лори (2016). Краткое введение в логику (13-е изд.). Бостон: Cengage Learning. стр. 427. ISBN 9781305958098.
7. Кнут, Дональд, Искусство программирования , том 3, раздел 4.2.2
8. IEEE Computer Society (29 августа 2008 г.). Стандарт IEEE для арифметики с плавающей точкой . doi :10.1109/IEEESTD.2008.4610935. ISBN 978-0-7381-5753-5. Стандарт IEEE 754-2008.
9. Вилья, Оресте; Чаваррия-мир, Даниэль; Гурумурти, Видья; Маркес, Андрес; Кришнамурти, Шрирам, Влияние неассоциативности чисел с плавающей точкой на числовые вычисления в системах с массивной многопоточностью (PDF) , заархивировано из оригинала (PDF) 15 февраля 2013 г. , извлечено 8 апреля 2014 г.
10. Голдберг, Дэвид (март 1991 г.). «Что каждый специалист по компьютерам должен знать об арифметике с плавающей точкой» (PDF) . ACM Computing Surveys . 23 (1): 5–48. doi :10.1145/103162.103163. S2CID  222008826. Архивировано (PDF) из оригинала 2022-05-19 . Получено 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. Гамильтон, У. Р. (1844–1850). «О кватернионах или новой системе мнимых в алгебре». Коллекция Дэвида Р. Уилкинса. Философский журнал . Тринити-колледж в Дублине .
18. Baez, John C. (2002). «Октонионы» (PDF) . Бюллетень Американского математического общества . 39 (2): 145–205. arXiv : math/0105155 . doi :10.1090/S0273-0979-01-00934-X. ISSN  0273-0979. MR  1886087. S2CID  586512.