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

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

${\displaystyle (x\cdot y)\cdot z=x\cdot (y\cdot z)}$ для довільних елементів ${\displaystyle x,y,z\!}$.

Для асоціативної операції результат обчислення ${\displaystyle x_{1}\cdot x_{2}\cdot \dots \cdot x_{n}}$ не залежить від порядку обчислення (розташування дужок), і тому можна опускати дужки у записі виразу. Для неасоціативної операції значення виразу ${\displaystyle x_{1}\cdot x_{2}\cdot \dots \cdot x_{n}}$ при ${\displaystyle n>2\!}$ не визначено.

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

Визначення

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

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

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

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

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

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

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

• (Додавання) і (множення) дійсних чисел, комплексних чисел, (кватерніонів) та матриць є асоціативним.
• (Об'єднання) та (перетин) множин є асоціативним.
• (Композиція відображень) є асоціативним.

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

• (Віднімання) і (ділення) дійсних чисел, комплексних чисел та кватерніонів є неасоціативним.
• Векторний добуток є неасоціативним.
• (Множення) (октоніонів) неасоціативне.

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

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

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

${\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 }$» це (металогічний) (символ), що розуміють як «може бути замінений у (доведенні) на… .»

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

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

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

${\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)}$

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

Див. також

• (Комутативність)
• (Дистрибутивність)
• (Альтернативність)
• (Степенева асоціативність)

Джерела

• (Винберг Э. Б.) Курс алгебри. — 4-е изд. — Москва : МЦНМО, 2011. — 592 с. — .(рос.)

• Українська радянська енциклопедія : у 12 т. / гол. ред. М. П. Бажан ; редкол.: (О. К. Антонов) та ін. — 2-ге вид. — К. : Головна редакція УРЕ, 1974–1985.

Примітки

1. Moore and Parker
2. Copi and Cohen
3. Hurley