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

Алгебричною операцією на множині $S$ називається функція $f,$ яка є відображенням виду $f\colon S^{n}\to S,\ n\in \mathbb {N} ,\$ де $S^{n}$ — декартів добуток ${\mbox{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.$

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

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

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

При перегляді запису зліва направо виконується перша знайдена операція, якій безпосередньо передує достатня для неї кількість операндів.
На місці виконаної операції і використаних для цього операндів у рядок записується результат виконання операції.
Повертаємося до кроку $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 120 / = 0,25 .

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

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

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

Якщо $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 .$

Приклад

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

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

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

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

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

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

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

Примітки

Позначення абстрактної бінарної операції.

Джерела

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

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

[:0-1] Позначення абстрактної бінарної операції.