12. Визначте, чи мають зазначені операції наведені властивості. Заповніть таблицю позначеннями «Так» — має і «Ні» — не має. Операції розглядаються на множині дійсних чисел.

    	х -і- у	х + у	х- у	\х - у\	шах(*, у)	min(.r, у)
    Асоціативна
    Комутативна
    Має одиницю

13. Опишіть алгоритм, який визначає, асоціативна бінарна опе­рація або ні. Вхідними даними є таблиця операції (операція задана на скінченній множині).

Опишіть алгоритм, який визначає, комутативна бінарна опера­ція ® відносно Ф чи ні. Вхідними даними є таблиці операцій ® і ® (операції задані на скінченній множині).

3. Поняття алгебраїчної структури

Алгебраїчна структура, підструктура, гомоморфізм, ізоморфізм

Визначення

Алгебраїчною структурою (коротко — структурою)

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

Приклад. Алгебраїчна структура з операцією додавання на множині N натуральних чисел позначається (ІУ, +).

Приклад. Множина £₇ = {0, 1, 2, 3, 4, 5, 6} разом із зви­чайною операцією додавання (+) не буде алгебраїчною струк­турою, оскільки результат виконання операції може не нале­жати множині 7,і, наприклад, б + 3 = 9, 9 £ 7,-,. Але (£₇, ©7) є алгебраїчною структурою, оскільки область значень опера­ції ®₇ лежить у 2₇.

Визначення

Структура 8' -(А', ©') є підструктурою алгебраїчної структури 8 - (А, ©), якщо:

12. А' с А.

13. ©' і Ф операції одного порядку і звуження операції Ф на підмножині А співпадає з операцією ©' (наприклад, для бінарних операцій а © Ь = а ©' Ь для всіх а, Ь є А').

Очевидно, що найбільшою підструктурою структури 8 є сама структура 8. У деяких випадках інших підструктур може не бути.

Приклади. Нехай Е — множина парних натуральних чисел, тоді (Е, +) буде підструктурою структури (Л^г, +), де N— мно­жина натуральних чисел.

Структура ({0, 1}, *) є підструктурою структури (^, *), де

• — множина цілих чисел.

Відношення між алгебраїчними структурами можуть бути не тільки такі, що включають (структура — підструктура). Мож­ливі й інші відношення, що дозволяють здійснювати перехід від структури до структури, з втратою деякої інформації або без втрати інформації.

Визначення

Нехай задано дві структури (А, ®)_г (С, ®) з операціями <3>, ® одного порядку п. Відображення <р: А —> С назива­ється гомоморфізмом із структури (А, ®) у структуру (С, ®), якщо воно переставлене з операціями у такому розумінні:

Ф • ® = ® • ф,

де відображення ф: А" —> С^п діє за правилом <р(а_ь а₂, а„) = (ф(а₁), ф(а₂), ф(а„)), Vа_i є А.

Для бінарних операцій (п = 2), зокрема, ф(л: ® у) — ф(лг) ® ф(г/) для будь-яких х, у є А.

Графічне визначення гомоморфізму для випадку бінарних операцій пояснює рис. 3.1.

Рис. 3.1. Гомоморфізм <р: ф (х ® у) ** ер (де) ® ф(у)

Якщо спростити наведену ілюстрацію, то одержимо кому­тативну діаграму, яка пов’язує окремі елементи множин та зображена на рис. 3.2.

(х, у) х®у

ф ф 7 Т

(ф(х), ф(у)) —ф(дг) © ф(г/) « ф(х ® у)

Рис. 3.2. Зв’язок між окремими елементами множин при гомоморфізмі ф

Часто такі діаграми зображують у більш спрощеному вигляді, вказуючи тільки необхідні множини, як показано на рис. 3.3.

Подібні діаграми часто використо­вуються для зображення зв’язків між структурами, вони називаються кому­тативними, оскільки показують мож­ливість переходу до результату різними способами (за напрямком стрілок).

Приклад. Нехай задано відображення 0: 2+ —> £₁₀, що пе­реводить будь-яке ціле невід’ємне число у решту від ділення цього числа на 10. Тоді

0(20) = 0, 0(17) = 7,...

Якщо (£+, +) і (£₁₀, Єю) структури з операцією звичайно­го додавання +., що визначена на 7+ і додаванням за модулем 10 на £ю, то 0 є гомоморфізмом з першої структури у другу. Наприклад,

0(24 + 38) - 0(62) - 2,

0(24) 0_1О 0(38) - 4 0,о 8 - 2.

Одержання даного результату двома різними способами можна проілюструвати комутативною діаграмою (рис. 3.4):

+

(24, 38)

(4,8)-

Рис. 3.4. Комутативна діаграма. Дія гомоморфізму 0

з (^і, +) в (£ю, ®ю) для елементів 24 і 38 множини 2

В загальному випадку для гомоморфізму 0: (2₊, +) —► -> (£_]0, 0ю) комутативна діаграма буде виглядати так, як це зображено на рис. 3.5.

Zl

Рис. 3.5. Комутативна діаграма дії гомоморфізму 0 з (/?,, +) в (£ю, ©іо)

Визначення

Гомоморфізм, який є бієкцією, називають ізоморфізмом.

Якщо існує ізоморфізм між двома структурами, то гово­рять, що вони ізоморфій одна одній.

Таким чином, для будь-якого ізоморфізму <р існує оберне­не відображення ф~\ також взаємно однозначне. Якщо існує ізоморфізм структури S у структуру Q, то існує й ізоморфізм Q У S.

Відношення ізоморфізму — це відношення еквівалентності на множині алгебраїчних структур, тому ізоморфізм розбиває множину всіх алгебраїчних структур на класи еквівалентності. Використовуючи ізоморфізм, можна здійснювати еквівалентні перетворення алгебраїчних структур. Якщо алгебраїчні струк­тури S і Q ізоморфні, то елементи і операції Q можна пере­йменувати так, що Q співпадає з S. Будь-яке співвідношення у структурі S зберігається у будь-якій ізоморфній їй структурі Q. Це дозволяє, одержавши певні співвідношення у структурі S, автоматично поширити їх на всі структури, що ізоморфні S. Тому алгебраїчні структури часто розглядаються з точністю до ізоморфізму, тобто розглядаються класи еквівалентності за відношенням ізоморфізму.

Приклад. Розглянемо спосіб вимірювання довжини у дюй­мах та сантиметрах. Якщо додати бінарну операцію додавання, то одержимо дві структури: (inch, +), (см, +). Визначимо ізо­морфізм у: х (см) = 2,54 * х (inch).

Як показано на діаграмі (рис. 3.6), ми можемо провести обчислення (дода- нминя) у дюймах, а потім перевести ре­зультат у сантиметри, і також можливо спочатку зобразити ті ж операнди в сан­тиметрах і потім провести додавання.

И обох випадках буде одержано один І той же результат. Наприклад, нехай необхідно визначити довжину d деяко­го »пробу, що складається з частин а і Ь. Виміривши частини її і Ь у дюймах, одержали, що а = 10", Ь *= 15". Знайдемо d дії'»ми способами:

(І = 10" 4- 15" = 25", 2,54 * 25" = 63,5 см;

(І 10" * 2,54 + 15" * 2,54 = 25,4 см + 38,1 см - 63,5 см.

Для цього прикладу комутативна діаграма виглядає таким чином (рис. 3.7):

+

(10", 15")

(25,4 см, 38,1 см)

Рис. 3.7. Перетворення окремих елементів при ізоморфізмі у з (inch, +) у (см, +)

Відображення є ізоморфізмом, оскільки у — однозначна відповідність та існує обернене відображення у': х (inch) =

3. 0,39 * х (см).

Наведемо ще два приклади ізоморфізмів.

Приклад. Нехай Z — множина всіх цілих чисел, Z₂n — мно­жина всіх парних чисел. Алгебри (Z; +) і (Z₂n', +) ізоморфні. Ізоморфізмом є відображення ср₂л-: п -» 2л для всіх п є Z.

Приклад. Ізоморфізмом між алгебраїчними структурами (Я,, *) і (Я, +), де Я,. — додатна підмножина Я, є відображен­ням а -» loga. Умова гомоморфізму ф (х ® у) = ер (х) Ф ф (у) у цьому випадку має вигляд log(a * b) — loga + log&.

Запитання

12. Дайте визначення алгебраїчної структури.

13. Що називається підструктурою алгебраїчної структури? Яким відношенням пов’язані множини-носії алгебраїчної структури та її підструктури? Наведіть приклади підструктур.

14. Дайте визначення гомоморфізму та ізоморфізму. Чим вони відрізняються ?

15. За допомогою чого здійснюється розбиття алгебраїчних струк­тур на класи еквівалентності?

16. Наведіть приклади ізоморфних алгебраїчних структур.

17. Наведіть приклад гомоморфізму, що не є ізоморфізмом. Пояс­ніть, чому обране вами відношення не ізоморфізм.

Завдання

• Розглянемо алгебраїчні структури ({а, Ь, с, сі}, ®) і ({а, Ь, с}, ®), де операції ® і ® задані таблицами:

©	и	b	с	d
а	а	b	с	d
b	h	с	d	a
с	с	d	a	b
d	d	a	b	с

Для кожної алгебраїчної структури визначте:

а) чи комутативна операція?

б) чи асоціативна операція?

в) чи існує одиниця для коленої операції, якщо існує, то який це елемент?

г) якщо одиниця існує, визначте, які елементи мають обернені?