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

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

(x\cdot y)\cdot z=x\cdot (y\cdot z)

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

x,y,z\!

.

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

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

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

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

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

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

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

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

(P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)

та

(P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R),

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

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

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

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

((P\lor Q)\lor R)\leftrightarrow (P\lor (Q\lor R))

(P\lor (Q\lor R))\leftrightarrow ((P\lor Q)\lor R)

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

((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))

(P\land (Q\land R))\leftrightarrow ((P\land Q)\land R)

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

((P\leftrightarrow Q)\leftrightarrow R)\leftrightarrow (P\leftrightarrow (Q\leftrightarrow R))

(P\leftrightarrow (Q\leftrightarrow R))\leftrightarrow ((P\leftrightarrow Q)\leftrightarrow R)

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

Див. також

Джерела

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

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

Примітки

Moore and Parker
Copi and Cohen
Hurley

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Moore and Parker

[2] Copi and Cohen

[3] Hurley

Правила перетворення
Числення висловлень
Правила висновування
Введення / усунення імплікації (modus ponens) Введення / усунення еквівалентності Введення / усунення кон'юнкції Введення / усунення диз'юнкції Диз'юнктивний / гіпотетичний силогізм Конструктивна / деструктивна дилема Абсорбція / modus tollens / modus ponendo tollens
Правила підстановки
Асоціативність Комутативність Дистрибутивність Подвійне заперечення Правила де Моргана Транспозиція Матеріальна імплікація Експортація Тавтологія Введення заперечення
Предикатна логіка
Універсальне узагальнення / конкретизація Екзистенційне узагальнення / конкретизація