~~~~~~~~~~~~~~~~~~~~ Arc.Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~ 
Номер скриншота №:
✰ 07BB8B7CB84F6510BD783371A3C3E083__1716300720 ✰
Заголовок документа оригинал.:
✰ Associative property - Wikipedia ✰
Заголовок документа перевод.:
✰ Ассоциативное свойство — Википедия ✰
Снимок документа находящегося по адресу (URL):
✰ https://en.wikipedia.org/wiki/Associative_law ✰
Адрес хранения снимка оригинал (URL):
✰ https://arc.ask3.ru/arc/aa/07/83/07bb8b7cb84f6510bd783371a3c3e083.html ✰
Адрес хранения снимка перевод (URL):
✰ https://arc.ask3.ru/arc/aa/07/83/07bb8b7cb84f6510bd783371a3c3e083__translat.html ✰
Дата и время сохранения документа:
✰ 11.06.2024 11:02:18 (GMT+3, MSK) ✰
Дата и время изменения документа (по данным источника):
✰ 21 May 2024, at 17:12 (UTC). ✰ 

~~~~~~~~~~~~~~~~~~~~~~ Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~~ 
Сервисы Ask3.ru: 
 Архив документов (Снимки документов, в формате HTML, PDF, PNG - подписанные ЭЦП, доказывающие существование документа в момент подписи. Перевод сохраненных документов на русский язык.)https://arc.ask3.ruОтветы на вопросы (Сервис ответов на вопросы, в основном, научной направленности)https://ask3.ru/answer2questionТоварный сопоставитель (Сервис сравнения и выбора товаров) ✰✰
✰ https://ask3.ru/product2collationПартнерыhttps://comrades.ask3.ru


Совет. Чтобы искать на странице, нажмите Ctrl+F или ⌘-F (для MacOS) и введите запрос в поле поиска.
Arc.Ask3.ru: далее начало оригинального документа

Ассоциативное свойство — Википедия Jump to content

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

Из Википедии, бесплатной энциклопедии
(Перенаправлено из Ассоциативного закона )
Ассоциативное свойство
Визуальный граф, представляющий ассоциативные операции;
Тип Закон , правило замены
Поле
Символическое заявление
  1. Элементарная алгебра
  2. Пропозициональное исчисление

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

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

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

Ассоциативность — это не то же самое, что коммутативность , которая определяет, влияет ли порядок двух операндов на результат. Например, порядок не имеет значения при умножении действительных чисел, то есть 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] Это называется обобщенным ассоциативным законом .

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

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

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

а б в г .

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

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

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

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

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

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

    Из-за ассоциативности группирующие круглые скобки можно без двусмысленности опустить.
  • Тривиальная операция x y = x (т. е. результатом является первый аргумент, независимо от того, каким является второй аргумент) ассоциативна, но не коммутативна. Аналогично, тривиальная операция x y = y (то есть результатом является второй аргумент, независимо от того, каким является первый аргумент) является ассоциативной, но не коммутативной.
  • Сложение и умножение комплексных чисел и кватернионов ассоциативны. Сложение октонионов также ассоциативно, но умножение октонионов неассоциативно.
  • Наибольший общий делитель и наименее общие кратные функции действуют ассоциативно.
  • Взяв пересечение или объединение множеств :
  • Если M — некоторое множество, а S обозначает множество всех функций от M до M , то операция композиции функций на S ассоциативна:
  • В более общем смысле, учитывая четыре набора M , N , P и Q , с h : M N , g : N P и f : P Q , тогда
    как прежде. Короче говоря, композиция карт всегда ассоциативна.
  • В теории категорий композиция морфизмов ассоциативна по определению. Ассоциативность функторов и естественных преобразований следует из ассоциативности морфизмов.
  • Рассмотрим набор из трех элементов A , B и C. : Следующая операция:
    × А Б С
    А А А А
    Б А Б С
    С А А А
    является ассоциативным. Так, например, A ( B C ) = ( A B ) C = A . Эта операция не является коммутативной.
  • Поскольку матрицы представляют собой линейные функции , а умножение матриц представляет композицию функций, можно сразу заключить, что умножение матриц ассоциативно. [3]
  • Для действительных чисел (и для любого полностью упорядоченного набора ) операция минимума и максимума ассоциативна:

Пропозициональная логика [ править ]

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

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

и

где " «является металогическим символом , обозначающим «можно заменить в доказательстве на».

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

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

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

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

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

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

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

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

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

тогда как

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

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

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

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

Чтобы проиллюстрировать это, рассмотрим представление с плавающей запятой с 4-битным мантиссом :

(1.000 2 ×2 0 + 1.000 2 ×2 0 ) + 1.000 2 ×2 4 = 1.000 2 ×2 1 + 1.000 2 ×2 4 = 1.00 1 2 ×2 4
1.000 2 ×2 0 + (1.000 2 ×2 0 + 1.000 2 ×2 4 ) = 1.000 2 ×2 0 + 1.000 2 ×2 4 = 1.00 0 2 ×2 4

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

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

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

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

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

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

Вычитание и деление действительных чисел [11] [12] [13] [14] [15]
Применение функции

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

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

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

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

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

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

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

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

Возведение в степень действительных чисел в инфиксной записи [16]
Операторы со стрелкой вверх Кнута
Взяв векторное произведение трех векторов
Взяв попарное среднее действительных чисел
Взяв относительное дополнение множеств
.

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

История [ править ]

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

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

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

  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 . Если являются элементами множества с ассоциативной операцией, то произведение является однозначным; то есть один и тот же элемент будет получен независимо от того, как в произведении вставлены скобки.
  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 для арифметики с плавающей запятой . дои : 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. ^ Бронштейн, де: Справочник по математике , страницы 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 . дои : 10.1090/S0273-0979-01-00934-X . ISSN   0273-0979 . МР   1886087 . S2CID   586512 .
Arc.Ask3.Ru: конец оригинального документа.
Arc.Ask3.Ru
Номер скриншота №: 07BB8B7CB84F6510BD783371A3C3E083__1716300720
URL1:https://en.wikipedia.org/wiki/Associative_law
Заголовок, (Title) документа по адресу, URL1:
Associative property - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть, любые претензии не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, денежную единицу можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)