Асоціативність

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Асоціативна операція (сполучний закон) — бінарна операція, яка володіє властивістю асоціативності (від латинського слова associatio — «з'єднання»), тобто виконується:

для довільних елементів .

Для асоціативної операції результат обчислення не залежить від порядку обчислення (розташування дужок), і тому можна опускати дужки у записі виразу. Для неасоціативної операції значення виразу при не визначено.

Довільна групова операція — асоціативна.

Визначення

[ред. | ред. код]
Бінарна операція ∗ над множиною S є асоціативною коли ця діаграма є комутативною. Тобто, коли два шляхи від S×S×S до S є композицією тієї ж функції від S×S×S до S.

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

(xy) ∗ z = x ∗ (yz) для всіх x, y, z у S.

Тут символ ∗ використовується для заміни символу операції, яка може зрештою задаватися будь-яким символом, а також символ може бути відсутнім (як часто буває при записуванні множення.

(xy)z = x(yz) = xyz для всіх x, y, z у S.

Асоціативне правило також можна записати у функціональній нотації наступним чином: f(f(x, y), z) = f(x, f(y, z)).

Приклади асоціативних операцій

[ред. | ред. код]

Приклади неасоціативних операцій

[ред. | ред. код]

Логіка висловлювань

[ред. | ред. код]

Правило підстановки

[ред. | ред. код]

В стандартній логіці висловлювань, асоціація,[1][2] або асоціативність[3] є двома істинними правилами підстановки. Правила дозволяють переставити дужки в логічних виразах при логічному виведенні. Це наступні правила (у нотації із логічними сполучниками):

та

де «» це металогічний символ, що розуміють як «може бути замінений у доведенні на… .»

Істині функціональні сполучники

[ред. | ред. код]

Асоціативність є властивістю деяких логічних сполучників істинно-функціональної логіки висловлювань. Наступні логічні еквівалентності демонструють, що асоціативність є властивістю конкретних сполучників. Наступні вирази є істинно-функціональними тавтологіями.

Асоціативність диз'юнкції:

Асоціативність кон'юнкції:

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

Спільне заперечення є прикладом істинно-функціонального сполучника, який не є асоціативним.

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Moore and Parker
  2. Copi and Cohen
  3. Hurley