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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Ассоциативная собственность»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июнь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

В математика, то ассоциативное свойство^[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 {для всех}} x, y, zin mathbb {R}.}$

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

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

${displaystyle left. {egin {matrix} имя оператора {gcd} (имя оператора {gcd} (x, y), z) = имя оператора {gcd} (x, имя оператора {gcd} (y, z)) = имя оператора {gcd} ( x, y, z) quad имя оператора {lcm} (имя оператора {lcm} (x, y), z) = имя оператора {lcm} (x, имя оператора {lcm} (y, z)) = имя оператора {lcm} (x , y, z) quad end {matrix}} ight} {mbox {для всех}} 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 {для всех наборов}} A, B, C.}$

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

${displaystyle (fcirc g) circ h = fcirc (gcirc h) = fcirc gcirc hqquad {mbox {для всех}} 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 {для некоторых}} x, y, zin S.}$

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

• Вычитание

${displaystyle (5-3) -2, экв, 5- (3-2)}$

• Разделение

${displaystyle (4/2) / 2, экв., 4 / (2/2)}$

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

${displaystyle 2 ^ {(1 ^ {2})}, уравнение, (2 ^ {1}) ^ {2}}$

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

${displaystyle (1 + -1) + (1 + -1) + (1 + -1) + (1 + -1) + (1 + -1) + (1 + -1) + точки, =, 0}$

в то время как

${displaystyle 1 + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + (- 1 + 1) + точки, =, 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 {и т. д. .}} qquad qquad qquad qquad qquad qquad, end {matrix}} ight} {mbox {для всех}} 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 {и т. д.}} qquad qquad qquad qquad qquad qquad, end {matrix}} ight} {mbox {для всех}} w, x, y, zin S}$

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

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

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

${стиль отображения 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 ^ {клин} y) ^ {клин} zeq x ^ {клин} (y ^ {клин} 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 {для некоторых}} {vec {a}}, {vec {b}}, {vec {c}} в 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 (A ackslash B) ackslash C}$ не то же самое, что ${displaystyle A ackslash (B ackslash C)}$. (Сравнивать материальное непонимание в логике.)

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

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

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