Асоціативна операція (сполучний закон) — бінарна операція, яка володіє властивістю асоціативності (від латинського слова associatio — «з'єднання»), тобто виконується:
для довільних елементів .
Для асоціативної операції результат обчислення не залежить від порядку обчислення (розташування дужок), і тому можна опускати дужки у записі виразу. Для неасоціативної операції значення виразу при не визначено.
Довільна групова операція — асоціативна.
Визначення
Формально, бінарна операція ∗ над множиною S називається асоціативною якщо вона задовольняє правилу асоціативності:
(x ∗ y) ∗ z = x ∗ (y ∗ z) для всіх x, y, z у S.
Тут символ ∗ використовується для заміни символу операції, яка може зрештою задаватися будь-яким символом, а також символ може бути відсутнім (як часто буває при записуванні множення.
(xy)z = x(yz) = xyz для всіх x, y, z у S.
Асоціативне правило також можна записати у функціональній нотації наступним чином: .
Приклади асоціативних операцій
Додавання і множення дійсних чисел, комплексних чисел, кватерніонів та матриць є асоціативним. Об'єднання та перетин множин є асоціативним. Композиція відображень є асоціативним.
Приклади неасоціативних операцій
Віднімання і ділення дійсних чисел, комплексних чисел та кватерніонів є неасоціативним. Векторний добуток є неасоціативним. Множення октоніонів неасоціативне.
Логіка висловлювань
Правило підстановки В стандартній логіці висловлювань, асоціація,Moore and ParkerCopi and Cohen або асоціативністьHurley є двома істинними правилами підстановки. Правила дозволяють переставити дужки в логічних виразах при логічному виведенні. Це наступні правила (у нотації із логічними сполучниками):
та
де «» це металогічний символ, що розуміють як «може бути замінений у доведенні на… .»
Істині функціональні сполучники Асоціативність є властивістю деяких логічних сполучників істинно-функціональної логіки висловлювань. Наступні логічні еквівалентності демонструють, що асоціативність є властивістю конкретних сполучників. Наступні вирази є істинно-функціональними тавтологіями.
Асоціативність диз'юнкції:
Асоціативність кон'юнкції:
Асоціативність еквівалентності:
Спільне заперечення є прикладом істинно-функціонального сполучника, який не є асоціативним.
Див. також Комутативність Дистрибутивність Альтернативність Степенева асоціативність
Джерела
Примітки