Ассоциативное свойство - Associative property

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

«Ассоциативные» и «неассоциативные» перенаправления сюда. Для ассоциативного и неассоциативного обучения см. Обучение § Типы.

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

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

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

${displaystyle 2 imes (3 imes 4)=(2 imes 3) imes 4=24.}$

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

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

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

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

Определение

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

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

(Икс ∗ у) ∗ z = Икс ∗ (у ∗ z) для всех Икс, у, z в S.

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

(ху)z = Икс(yz) = xyz для всех Икс, у, z в S.

В функциональных обозначениях ассоциативный закон также может быть выражен так: ж(ж(Икс, у), z) = ж(Икс, ж(у, z)).

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

При отсутствии ассоциативного свойства пять факторов а, б, в, г, д привести к Решетка Тамари порядка четырех, возможно, разные продукты.

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

${displaystyle ((ab)c)d}$

${displaystyle (ab)(cd)}$

${displaystyle (a(bc))d}$

${displaystyle a((bc)d)}$

${displaystyle a(b(cd))}$

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

${displaystyle abcd.}$

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

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

Примеры

В ассоциативных операциях есть ${displaystyle (xcirc y)circ z=xcirc (ycirc z)}$.

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

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

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

${displaystyle left.{egin{matrix}(x+y)+z=x+(y+z)=x+y+zquad (x,y)z=x(y,z)=x,y,zqquad qquad qquad quad ,end{matrix}}ight}{mbox{for all }}x,y,zin mathbb {R} .}$

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

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

${displaystyle left.{egin{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}}ight}{mbox{ for all }}x,y,zin mathbb {Z} .}$

• Принимая пересечение или союз из наборы:

${displaystyle left.{egin{matrix}(Acap B)cap C=Acap (Bcap C)=Acap Bcap Cquad (Acup B)cup C=Acup (Bcup C)=Acup Bcup Cquad end{matrix}}ight}{mbox{for all sets }}A,B,C.}$

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

${displaystyle (fcirc g)circ h=fcirc (gcirc h)=fcirc gcirc hqquad {mbox{for all }}f,g,hin S.}$

• Чуть шире, учитывая четыре набора M, N, п и Q, с час: M к N, грамм: N к п, и ж: п к Q, тогда

${displaystyle (fcirc g)circ h=fcirc (gcirc h)=fcirc gcirc h}$

как прежде. Одним словом, состав карты всегда ассоциативен.

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

×	А	B	C
А	А	А	А
B	А	B	C
C	А	А	А

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

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

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

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

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

${displaystyle (Plor (Qlor R))Leftrightarrow ((Plor Q)lor R)}$

и

${displaystyle (Pland (Qland R))Leftrightarrow ((Pland Q)land R),}$

куда "${displaystyle Leftrightarrow }$" это металогический символ представляющий "можно заменить на доказательство с."

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

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

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

${displaystyle ((Plor Q)lor R)leftrightarrow (Plor (Qlor R))}$

${displaystyle (Plor (Qlor R))leftrightarrow ((Plor Q)lor R)}$

Ассоциативность соединения:

${displaystyle ((Pland Q)land R)leftrightarrow (Pland (Qland R))}$

${displaystyle (Pland (Qland R))leftrightarrow ((Pland Q)land R)}$

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

${displaystyle ((Pleftrightarrow Q)leftrightarrow R)leftrightarrow (Pleftrightarrow (Qleftrightarrow R))}$

${displaystyle (Pleftrightarrow (Qleftrightarrow R))leftrightarrow ((Pleftrightarrow Q)leftrightarrow R)}$

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

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

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

${displaystyle (x*y)*zeq x*(y*z)qquad {mbox{for some }}x,y,zin S.}$

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

• Вычитание

${displaystyle (5-3)-2,eq ,5-(3-2)}$

• Разделение

${displaystyle (4/2)/2,eq ,4/(2/2)}$

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

${displaystyle 2^{(1^{2})},eq ,(2^{1})^{2}}$

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

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

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

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

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

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

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

Несмотря на то, что большинство компьютеров выполняют вычисления с 24 или 53 битами мантиссы,^[9] это важный источник ошибок округления, и такие подходы, как Алгоритм суммирования Кахана способы минимизировать ошибки. Это может быть особенно проблематично при параллельных вычислениях.^[10][11]

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

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

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

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

${displaystyle left.{egin{matrix}x*y*z=(x*y)*zqquad qquad quad ,w*x*y*z=((w*x)*y)*zquad {mbox{etc.}}qquad qquad qquad qquad qquad qquad ,end{matrix}}ight}{mbox{for all }}w,x,y,zin S}$

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

${displaystyle left.{egin{matrix}x*y*z=x*(y*z)qquad qquad quad ,w*x*y*z=w*(x*(y*z))quad {mbox{etc.}}qquad qquad qquad qquad qquad qquad ,end{matrix}}ight}{mbox{for all }}w,x,y,zin S}$

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

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

${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} ightarrow mathbb {Z} ightarrow mathbb {Z} =mathbb {Z} ightarrow (mathbb {Z} ightarrow mathbb {Z} )}$

${displaystyle xmapsto ymapsto x-y=xmapsto (ymapsto x-y)}$

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

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

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

${displaystyle (x^{wedge }y)^{wedge }zeq x^{wedge }(y^{wedge }z)}$

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

${displaystyle auparrow uparrow (buparrow uparrow c)eq (auparrow uparrow b)uparrow uparrow c}$

${displaystyle auparrow uparrow uparrow (buparrow uparrow uparrow c)eq (auparrow uparrow uparrow b)uparrow uparrow uparrow c}$

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

${displaystyle {vec {a}} imes ({vec {b}} imes {vec {c}})eq ({vec {a}} imes {vec {b}}) imes {vec {c}}qquad {mbox{ for some }}{vec {a}},{vec {b}},{vec {c}}in mathbb {R} ^{3}}$

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

${displaystyle {(x+y)/2+z over 2}eq {x+(y+z)/2 over 2}qquad {mbox{for all }}x,y,zin mathbb {R} {mbox{ with }}xeq z.}$

• Принимая относительное дополнение наборов ${displaystyle (Aackslash B)ackslash C}$ не то же самое, что ${displaystyle Aackslash (Backslash C)}$. (Сравнивать материальное непонимание в логике.)

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

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

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

1. Хангерфорд, Томас В. (1974). Алгебра (1-е изд.). Springer. п. 24. ISBN  978-0387905181. Определение 1.1 (i) a (bc) = (ab) c для всех a, b, c в G.
2. Дурбин, Джон Р. (1992). Современная алгебра: введение (3-е изд.). Нью-Йорк: Вили. п. 78. ISBN  978-0-471-51001-7. Если ${displaystyle a_{1},a_{2},dots ,a_{n},,(ngeq 2)}$ элементы множества с ассоциативной операцией, то произведение ${displaystyle a_{1}a_{2}dots a_{n}}$ однозначно; то есть один и тот же элемент будет получен независимо от того, как скобки вставлены в продукт
3. «Матричная ассоциативность продуктов». Ханская академия. Получено 5 июн 2016.
4. Мур, Брук Ноэль; Паркер, Ричард (2017). Критическое мышление (12-е издание). Нью-Йорк: Образование Макгроу-Хилла. п. 321. ISBN  9781259690877.
5. Copi, Irving M .; Коэн, Карл; МакМахон, Кеннет (2014). Введение в логику (14-е издание). Эссекс: образование Пирсона. п. 387. ISBN  9781292024820.
6. Херли, Патрик Дж .; Уотсон, Лори (2016). Краткое введение в логику (13-е издание). Бостон: Cengage Learning. п. 427. ISBN  9781305958098.
7. «Символьное логическое доказательство ассоциативности». Math.stackexchange.com. 22 марта 2017.
8. Кнут, Дональд, Искусство программирования, Том 3, раздел 4.2.2
9. IEEE Computer Society (29 августа 2008 г.). Стандарт IEEE для арифметики с плавающей запятой. Дои:10.1109 / IEEESTD.2008.4610935. ISBN  978-0-7381-5753-5. IEEE Std 754-2008.
10. Вилла, Орест; Чаваррия-мир, Даниэль; Гурумурти, Видхья; Маркес, Андрес; Кришнамурти, Шрирам, Влияние неассоциативности с плавающей запятой на численные вычисления в многопоточных системах (PDF), заархивировано из оригинал (PDF) 15 февраля 2013 г., получено 8 апреля 2014
11. Гольдберг, Дэвид (Март 1991 г.). «Что должен знать каждый компьютерный ученый об арифметике с плавающей точкой» (PDF). Опросы ACM Computing. 23 (1): 5–48. Дои:10.1145/103162.103163. Получено 20 января 2016. ([1], [2] В архиве 2016-04-06 в Wayback Machine )
12. Джордж Марк Бергман: Порядок арифметических операций
13. Место обучения: Порядок действий
14. Ханская академия: Порядок действий, отметка времени 5 мин. 40 сек.
15. Департамент образования Вирджинии: Использование порядка операций и изучение свойств, раздел 9
16. Бронштейн: de: Taschenbuch der Mathematik, страницы 115-120, глава: 2.4.1.1, ISBN  978-3-8085-5673-3
17. Ассоциативность возведения в степень и стандартная математическая запись Codeplea. 23 августа 2016 г. Проверено 20 сентября 2016 г.