Алгебрична операція

Шаблон:Otheruses Шаблон:UniboxАлгебричною операцією на множині $S$ називається функція $f,$ яка є відображенням виду $f:S^n\to S,n\in \mathbb{N},$ де $S^n$ — декартів добуток $\text{S×S×…×S,}$ в який $S$ входить $n$ разів.

У цьому визначенні є два важливих моменти. По-перше, оскільки операція є функцією, то результат застосування операції визначено однозначно. Тому даний упорядкований набір з $n$ елементів множини $S$ функція $f$ переводить тільки в один елемент із $S$. По-друге, операція замкнена на $S$ у тому розумінні, що область визначення та область значень операції лежать у $S^n$ і $S$ відповідно.

Кажуть, що операція $S^n\to S$ має порядок $n$ або є $n$-арна операція. Частіше зустрічається ситуація, коли порядок дорівнює $1$ або $2$. Операції виду $S\to S$ називають унарними, а операції $S^2\to S$ називають бінарними. Елементи упорядкованого набору з $n$ елементів в області визначення $S^n$ називають операндами. Операції звичайно позначають символами, що називають операторами. У випадку унарних операції звичайно символ оператора ставлять перед або над операндом.

Види запису операцій

Розглянемо три варіанти запису бінарної операції складання $a$ і $b.$

• $\text{infix}$ — оператор ставиться між операндами: $a+b;$
• $\text{prefix}$ — оператор ставиться перед операндами: $+ab;$
• $\text{postfix}$ — оператор ставиться після операндів: $ab+.$

Префіксний та постфіксний способи запису не потребують дужок при визначенні порядку обчислювання складних виразів, і це робить їх особливо зручними для автоматичної обробки. Вони часто використовуються для представлення виразів у пам'яті комп'ютера.

Алгоритм обчислення значень виразу, що записаний у постфіксній формі

1. При перегляді запису зліва направо виконується перша знайдена операція, якій безпосередньо передує достатня для неї кількість операндів.
2. На місці виконаної операції і використаних для цього операндів у рядок записується результат виконання операції.
3. Повертаємося до кроку $1.$

Приклад

Маємо вираз: (5 * 6) / ((8 — 3) * (7 + 1) * 4) .
Запишемо його у постфіксній формі: 5 6 * 8 3 — 7 1 + 4 * / .
Тепер ми можемо його розв'язати: 5 6 * 8 3 — 7 1 + 4 * / = 30 8 3 — 7 1 + 4 * / = 30 5 7 1 + 4 * / = 30 5 8 4 * / = 30 160 / = 0.1875 .

Властивості операцій

Нехай дано множину $A,$ на якій визначено дві бінарні операції $\otimes$ та $\oplus$ $.$

Комутативність

Якщо $a\otimes b=b\otimes a$ для всіх $a,b\in A,$ то стверджують, що бінарна операція $\otimes$ на множині $A$ має властивість — комутативність.

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

Якщо $(a\otimes b)\otimes c=a\otimes (b\otimes c)$ для всіх $a,b,c\in A,$ то стверджують, що бінарна операція $\otimes$ на множині $A$ має властивість — асоціативність.

Дистрибутивність

Якщо $a\otimes (b\oplus c)=(a\otimes b)\oplus (a\otimes c)$ для всіх $a,b,c\in A,$ то стверджують, що бінарна операція $\otimes$ на множині $A$ має властивість — дистрибутивність відносно операції $\oplus .$

Приклад

Маємо дві бінарні операції: додавання $(+)$ та віднімання $(-).$ Перевіримо їх комутативність, асоціативність та дистрибутивність на множині дійсних чисел $ℝ.$

Комутативність

$a+b=b+a$ — операція додавання є комутативною.
$a-b\ne b-a$ — операція віднімання не є комутативною.

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

$(a+b)+c=a+(b+c)$ — операція додавання є асоціативною.
$(a-b)-c\ne a-(b-c)$ — операція віднімання не є асоціативною.

Дистрибутивність

$a-(b+c)\ne (a-b)+(a-c)$ — операція додавання не є дистрибутивною відносно операції віднімання.
$a+(b-c)\ne (a+b)-(b+c)$ — операція віднімання не є дистрибутивною відносно операції додавання.

Джерела

Бондаренко М. Ф., Білоус Н. В., Руткас А. Г. Комп'ютерна дискретна математика: Підручник. — Харків: «Компанія СМІТ», 2004. С. 73-76. Шаблон:Ref-uk