- •Виберіть два варіанти виконання операції проекції до відношення Фірма-продукція-телефон. За якими атрибутами ви робили проекції?
- •Виконайте обмеження відношення Фірма-продукція-телефон за умови:
- •Алгебраїчні операції та їх властивості
- •Опишіть алгоритм, який визначає, асоціативна бінарна операція або ні. Вхідними даними є таблиця операції (операція задана на скінченній множині).
- •Поняття алгебраїчної структури
- •Визначте алгебраїчну структуру (й, ®), таку, що для будь-якої ггідмножини ГсЙ правильно, що (т, ®) — підструктура структури (5, ф).
- •Доведіть, що:
- •Найпростіші алгебраїчні структури
Визначте, чи мають зазначені операції наведені властивості. Заповніть таблицю позначеннями «Так» — має і «Ні» — не має. Операції розглядаються на множині дійсних чисел.
х -і- у
х + у
х- у
\х - у\
шах(*, у)
min(.r, у)
Асоціативна
Комутативна
Має одиницю
Опишіть алгоритм, який визначає, асоціативна бінарна операція або ні. Вхідними даними є таблиця операції (операція задана на скінченній множині).
Опишіть алгоритм, який визначає, комутативна бінарна операція ® відносно Ф чи ні. Вхідними даними є таблиці операцій ® і ® (операції задані на скінченній множині).
Поняття алгебраїчної структури
Алгебраїчна структура, підструктура, гомоморфізм, ізоморфізм
Визначення
Алгебраїчною структурою (коротко — структурою)
називається множина разом із заданими операціями, визначеними і замкненими (див. п. 4.8) на цій множині. Ця множина називається носієм алгебраїчної структури.
Приклад. Алгебраїчна структура з операцією додавання на множині N натуральних чисел позначається (ІУ, +).
Приклад. Множина £7 = {0, 1, 2, 3, 4, 5, 6} разом із звичайною операцією додавання (+) не буде алгебраїчною структурою, оскільки результат виконання операції може не належати множині 7,і, наприклад, б + 3 = 9, 9 £ 7,-,. Але (£7, ©7) є алгебраїчною структурою, оскільки область значень операції ®7 лежить у 27.
Визначення
Структура 8' -(А', ©') є підструктурою алгебраїчної структури 8 - (А, ©), якщо:
А' с А.
©' і Ф операції одного порядку і звуження операції Ф на підмножині А співпадає з операцією ©' (наприклад, для бінарних операцій а © Ь = а ©' Ь для всіх а, Ь є А').
Очевидно, що найбільшою підструктурою структури 8 є сама структура 8. У деяких випадках інших підструктур може не бути.
Приклади. Нехай Е — множина парних натуральних чисел, тоді (Е, +) буде підструктурою структури (Лг, +), де N— множина натуральних чисел.
Структура ({0, 1}, *) є підструктурою структури (^, *), де
— множина цілих чисел.
Відношення між алгебраїчними структурами можуть бути не тільки такі, що включають (структура — підструктура). Можливі й інші відношення, що дозволяють здійснювати перехід від структури до структури, з втратою деякої інформації або без втрати інформації.
Визначення
Нехай задано дві структури (А, ®)г (С, ®) з операціями <3>, ® одного порядку п. Відображення <р: А —> С називається гомоморфізмом із структури (А, ®) у структуру (С, ®), якщо воно переставлене з операціями у такому розумінні:
Ф • ® = ® • ф,
де відображення ф: А" —> Сп діє за правилом <р(аь а2, а„) = (ф(а1), ф(а2), ф(а„)), Vаi є А.
Для бінарних операцій (п = 2), зокрема, ф(л: ® у) — ф(лг) ® ф(г/) для будь-яких х, у є А.
Графічне визначення гомоморфізму для випадку бінарних операцій пояснює рис. 3.1.
Рис. 3.1. Гомоморфізм <р: ф (х ® у) ** ер (де) ® ф(у)
Якщо спростити наведену ілюстрацію, то одержимо комутативну діаграму, яка пов’язує окремі елементи множин та зображена на рис. 3.2.
(х, у) х®у
ф ф 7 Т
(ф(х), ф(у)) —ф(дг) © ф(г/) « ф(х ® у)
Рис. 3.2. Зв’язок між окремими елементами множин при гомоморфізмі ф
Часто такі діаграми зображують у більш спрощеному вигляді, вказуючи тільки необхідні множини, як показано на рис. 3.3.
Подібні діаграми часто використовуються для зображення зв’язків між структурами, вони називаються комутативними, оскільки показують можливість переходу до результату різними способами (за напрямком стрілок).
Приклад. Нехай задано відображення 0: 2+ —> £10, що переводить будь-яке ціле невід’ємне число у решту від ділення цього числа на 10. Тоді
0(20) = 0, 0(17) = 7,...
Якщо (£+, +) і (£10, Єю) структури з операцією звичайного додавання +., що визначена на 7+ і додаванням за модулем 10 на £ю, то 0 є гомоморфізмом з першої структури у другу. Наприклад,
0(24 + 38) - 0(62) - 2,
0(24) 01О 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) =
0,39 * х (см).
Наведемо ще два приклади ізоморфізмів.
Приклад. Нехай Z — множина всіх цілих чисел, Z2n — множина всіх парних чисел. Алгебри (Z; +) і (Z2n', +) ізоморфні. Ізоморфізмом є відображення ср2л-: п -» 2л для всіх п є Z.
Приклад. Ізоморфізмом між алгебраїчними структурами (Я,, *) і (Я, +), де Я,. — додатна підмножина Я, є відображенням а -» loga. Умова гомоморфізму ф (х ® у) = ер (х) Ф ф (у) у цьому випадку має вигляд log(a * b) — loga + log&.
Запитання
Дайте визначення алгебраїчної структури.
Що називається підструктурою алгебраїчної структури? Яким відношенням пов’язані множини-носії алгебраїчної структури та її підструктури? Наведіть приклади підструктур.
Дайте визначення гомоморфізму та ізоморфізму. Чим вони відрізняються ?
За допомогою чого здійснюється розбиття алгебраїчних структур на класи еквівалентності?
Наведіть приклади ізоморфних алгебраїчних структур.
Наведіть приклад гомоморфізму, що не є ізоморфізмом. Поясніть, чому обране вами відношення не ізоморфізм.
Завдання
Розглянемо алгебраїчні структури ({а, Ь, с, сі}, ®) і ({а, Ь, с}, ®), де операції ® і ® задані таблицами:
© |
и |
b |
с |
d |
а |
а |
b |
с |
d |
b |
h |
с |
d |
a |
с |
с |
d |
a |
b |
d |
d |
a |
b |
с |
Для кожної алгебраїчної структури визначте:
а) чи комутативна операція?
б) чи асоціативна операція?
в) чи існує одиниця для коленої операції, якщо існує, то який це елемент?
г) якщо одиниця існує, визначте, які елементи мають обернені?