Введение
Ассоциативное свойство в математике
Свойство математической операции
В математике ассоциативное свойство — это свойство некоторых бинарных операций, которое означает, что перестановка скобок в выражении не изменит результат. В логике высказываний ассоциативность является допустимым правилом подстановки для выражений в логических доказательствах. В выражении, содержащем два или более последовательных применений одного и того же ассоциативного оператора, порядок выполнения операций не имеет значения, если последовательность операндов не меняется. То есть (после переписывания выражения со скобками и в инфиксной нотации, если это необходимо), перестановка скобок в таком выражении не изменит его значение. Рассмотрим следующие уравнения:
Несмотря на то, что скобки были переставлены в каждой строке, значения выражений остались неизменными. Поскольку это справедливо для сложения и умножения любых действительных чисел, можно сказать, что «сложение и умножение действительных чисел являются ассоциативными операциями». Ассоциативность отличается от коммутативности, которая определяет, влияет ли порядок двух операндов на результат. Например, порядок не имеет значения при умножении действительных чисел, то есть , поэтому мы говорим, что умножение действительных чисел является коммутативной операцией. Однако такие операции, как композиция функций и умножение матриц, ассоциативны, но не (обычно) коммутативны. Ассоциативные операции широко распространены в математике; на самом деле, многие алгебраические структуры (такие как полугруппы и категории) явно требуют, чтобы их бинарные операции были ассоциативными. Однако многие важные и интересные операции неассоциативны; к ним относятся вычитание, возведение в степень и векторное произведение. В отличие от теоретических свойств действительных чисел, сложение чисел с плавающей точкой в информатике не является ассоциативным, и выбор способа группировки выражения может существенно повлиять на ошибку округления.
Обобщенное ассоциативное право
Если двоичная операция ассоциативна, повторное применение этой операции даёт один и тот же результат, независимо от того, как расставлены скобки в выражении. Это называется обобщённым законом ассоциативности. Количество возможных способов расстановки скобок равно числу Каталана, 1=Cn, для n операций над n+1 значениями. Например, произведение 3 операций над 4 элементами можно записать (не учитывая перестановки аргументов) 1=C3 = 5 различными способами:
If the product operation is associative, the generalized associative law says that all these expressions will yield the same result. So unless the expression with omitted parentheses already has a different meaning (see below), the parentheses can be considered unnecessary and "the" product can be written unambiguously as
As the number of elements increases, the number of possible ways to insert parentheses grows quickly, but they remain unnecessary for disambiguation. An example where this does not work is the logical biconditional ↔. It is associative; thus, is equivalent to , but most commonly means , which is not equivalent.
Если операция произведения ассоциативна, обобщённый закон ассоциативности утверждает, что все эти выражения дадут один и тот же результат. Следовательно, если выражение без скобок не имеет иного значения (см. ниже), скобки можно считать избыточными, и "произведение" можно записать однозначно. По мере увеличения числа элементов количество возможных способов расстановки скобок быстро растёт, но они остаются ненужными для устранения неоднозначности. Пример, когда это не работает, – логическая эквивалентность ↔. Она ассоциативна, поэтому эквивалентно , но обычно означает , что не эквивалентно.
If the product operation is associative, the generalized associative law says that all these expressions will yield the same result. So unless the expression with omitted parentheses already has a different meaning (see below), the parentheses can be considered unnecessary and "the" product can be written unambiguously as
As the number of elements increases, the number of possible ways to insert parentheses grows quickly, but they remain unnecessary for disambiguation. An example where this does not work is the logical biconditional ↔. It is associative; thus, is equivalent to , but most commonly means , which is not equivalent.
Примеры
Некоторые примеры ассоциативных операций включают следующее.
История
Уильям Роуэн Гамильтон, по-видимому, ввел термин "ассоциативное свойство" примерно в 1844 году, в период, когда он размышлял о неассоциативной алгебре октонионов, о которой он узнал от Джона Т. Грейвза.