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

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

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

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

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

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

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

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

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

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

Определение [ править ]

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

( Х * у ) * г = х * ( у * г ) для всех х , у , г в S .

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

( Х ) г = х ( уг ) = хуг для всех х , у , г в S .

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

Обобщенный ассоциативный закон [ править ]

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

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

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

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

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

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

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

${\displaystyle abcd.}$

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

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

Примеры [ править ]

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

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

• Конкатенации из трех строк "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. Следующая операция:

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

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

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

Логика высказываний [ править ]

Правило замены [ править ]

В стандартной истине функциональной логики, ассоциации , ^{[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 }$

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

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

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

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

${\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\land (Q\land R))\leftrightarrow ((P\land Q)\land R)}$

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

${\displaystyle ((P\leftrightarrow Q)\leftrightarrow R)\leftrightarrow (P\leftrightarrow (Q\leftrightarrow 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 (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.00 1 ₂ × 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.{\begin{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}}\right\}{\mbox{for all }}w,x,y,z\in S}$

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

${\displaystyle \left.{\begin{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}}\right\}{\mbox{for all }}w,x,y,z\in 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} \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)}$

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

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

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

${\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}$${\displaystyle A\backslash (B\backslash C)}$

См. Также [ править ]

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

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

Ссылки [ править ]