- •Виберіть два варіанти виконання операції проекції до відношення Фірма-продукція-телефон. За якими атрибутами ви робили проекції?
- •Виконайте обмеження відношення Фірма-продукція-телефон за умови:
- •Алгебраїчні операції та їх властивості
- •Опишіть алгоритм, який визначає, асоціативна бінарна операція або ні. Вхідними даними є таблиця операції (операція задана на скінченній множині).
- •Поняття алгебраїчної структури
- •Визначте алгебраїчну структуру (й, ®), таку, що для будь-якої ггідмножини ГсЙ правильно, що (т, ®) — підструктура структури (5, ф).
- •Доведіть, що:
- •Найпростіші алгебраїчні структури
Визначте алгебраїчну структуру (й, ®), таку, що для будь-якої ггідмножини ГсЙ правильно, що (т, ®) — підструктура структури (5, ф).
Визначте, чи коректно задана алгебраїчна структура. Якщо так, визначте, чи комутативна операція і, якщо можливо, знайдіть одиницю і обернені елементи. Тут N — множина натуральних чисел, 2— множина цілих чисел, Я,—додатна підмножина множини дійсних чисел:
а) (Л^, ®); х 0 у = х - у;
б) (£, ®); х®у*=х*у - 1;
в) (ІУ, ®); х ® у = тах(х, у)\
г) (#+, ®); х ® у = х/у.
Доведіть, що:
а) дві алгебраїчні структури не можуть бути ізоморфними, якщо множини-носії цих структур мають різні потужності;
б) дві алгебраїчні структури можуть не бути ізоморфними, якщо множини-носії цих алгебр мають однакові потужності.
Нехай С — множина структур з однією бінарною операцією, С = {5і, вг, —}• Визначимо відношення ~ на множині С, таке, ЩО 5; ~ виконується, ЯКЩО 5/ І ізоморфні. Доведіть, що ~ є відношенням еквівалентності на множині С.
Найпростіші алгебраїчні структури
Півгрупа, моноїд, група, абелева. група
Розглянемо основні типи алгебраїчних структур, які мають тільки одну бінарну операцію.
Визначення
Півгрупою називається алгебраїчна структура з множи- ною-носієм А і бінарною операцією ®: А2—>А, яка задовольняє властивості асоціативності:
х <8> (у ® г) = (х ® у) ® г; х, у, г є А.
Визначення
Моноїдом називають алгебраїчну структуру з множиною-
носієм М і бінарною операцією ®: М2 -» М такою, що
® асоціативна:
х ® (у ® г) = (х ® у) ® 2, для всіх х, у, г є М.
Існує е є М— одиниця відносно ®:
Є®Х=‘Х = Х®Є для всіх х є М.
Таким чином, моноїд — це півгрупа з одиницею.
Півгрупи і моноїди використовуються при обробці рядків символів. Розглянемо приклад.
Приклад. При обробці рядків символів вводиться операція конкатенації — злиття рядків. Позначимо її *. Конкатенація визначається як а • Р = оф, де а і Р — рядки символів. Візьмемо рядки: «пар», «сам», «о», «воз», «ход», «вар». Застосувавши операції конкатенації, одержуємо такі рядки:
«пар» • «о» = «паро»
«сам» • «о» = «само»
«паро» • «воз» = «паровоз»
«паро» • «ход» = «пароход»
«само» • «вар» = «самовар».
Очевидно, що ця операція асоціативна, оскільки («пар» • «о») • «воз» = «пар» • («о» • «воз») ==
= «паровоз» і т. д.
Отже (А*, •) є півгрупою, де А* — множина різних рядків, що складаються з букв українського алфавіту. Якщо тепер ми позначимо через А* множину всіляких рядків, що складаються
з букв українського алфавіту і порожнього рядку є, то одержимо структуру (А\ •), яка є моноїдом з одиничним елементом є. Оскільки є позначає порожній рядок, то можемо записати є = « ».
«самовар» • «» = «» • «самовар» = «самовар» і т. д.
Визначення
Групою називають множину О з бінарною операцією ®,
що замкнена в С, такою, що
® асоціативна:
х ® (у ® г) = (х ® у) ® 2 для всіх х> у, г є <3.
Існує елемент е є Є — одиниця відносно ®: е®х = х®е = х ДЛЯ ВСІХ X є С.
Кожному елементу х є Є відповідає обернений елемент х' є (З відносно ®:
х'®х — х®х'~е для ВСІХ X є Є.
Із визначення маємо, що група — це моноїд, в якому всі елементи оборотні.
Часто до слів «група» і «моноїд» приписують термін «комутативний». Це означає, що операція у розглянутій структурі задовольняє властивість комутативності, тобто
у ® х — х ® у для всіх х, у є М або О.
Комутативна група називається абелевою групою (на честь норвезького математика Абеля).
Приклади. 1. Групою є множина дійсних чисел разом з операцією додавання: (і?, +), підгрупою цієї групи є , +), де Z — множина цілих чисел. Структура (К, +), де К — множина цілих чисел, що кратні к, /г є ІУ, є підгрупою групи (7,, +). Для цих груп одиницею є 0, обернений елемент утворюється за допомогою застосування унарної операції зміни знака «-». Наведені групи є абелевими групами, оскільки додавання комутативне.
Структура (7і/, +), де N — множина натуральних чисел, не є групою, оскільки не існує обернених елементів і одиниці. Насправді, (ТУ, +) — півгрупа.
Структури (Я, *) і (./V, *) не є групами, а є моноїдами. Одиничним елементом для операції множення є 1. Обернені елементи існують на множині дійсних чисел Я для всіх елементів, крім 0: не існує О'1, такого, що 0 * О'1 — 1. Таким чином, операція множення задає групу на множині дійсних чисел, крім нуля (#\{0}, *). Додатна підмножина множини дійсних чисел з операцією множення (#+, *) теж є групою— підгрупою групи (Д\{0}, *). Множення комутативне, отже, ці групи є абе- лепими.
Позначимо М„ (і?) множину всіх квадратних матриць порядку п з елементами з множини дійсних чисел. Структура (М „(II), +) — комутативний моноїд з одиницею — нульовою матрицею. Структура (М„(і?), *) — некомутативиий моноїд з одиницею одиничною матрицею.
Структура (Z„, ©п)— група з одиницею 0 і оберненим елементом х' = п - х; (Zn, ®„) —■ моноїд з одиницею 1.
Для розв’язку рівнянь необхідно існування та єдиність одиниць і обернених елементів. Доведемо ці твердження.
Твердження 1. Нехай ® — операція на множині А й існує одиниця е відносно ®, тоді одиничний елемент єдиний.
Доведення. Нехай е і е' — дві одиниці відносно ®. Тоді для будь-яких а, b є А правильне а = е' ® a, b = b ® е. Підставляючи а — е, b - <?', одержуємо е = е' ® е - е'.
Твердження 2. Нехай ® — асоціативна операція на множині Aie — одиниця відносно ®. Тоді, якщо х є А і х має обернений елемент, то обернений елемент єдиний відносно ®.
Доведення. Припустимо, що х' і х" — обернені елементи до х, так що
X ® Xі — х' ® X — Є, X ® х" = X" ® X = Є,
тоді
х' — х' ® е — х' ® (л: ® х") = (х' ® х) ® х" = е ® х" = х".
Всередині групи (G, ®) можна розв’язати рівняння а ® ® х = Ь.
До рівності а ® х — b застосуємо зліва а' — обернений до а елемент і послідовно одержуємо:
а' ® (а ® х) = а' ® Ьу
(а' ® а) ® х = а' ® b (® асоціативна),
е ® х = а' ® b (властивість обернених елементів),
х = а' ® b (властивість одиниці); х — розв’язок.
Існування одиниці та обернених елементів відносно деякої операції накладає значне обмеження на вид таблиці Келі для цієї операції. Розглянемо групу (Z7, @7)- Таблиця Келі (див. р. 3.1) для операції ©7 виглядає таким чином:
©, |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
0 |
ж |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
і |
X |
3 |
4 |
5 |
6 |
0 |
2 |
2 |
3 |
Ч |
5 |
6 |
0 |
1 |
3 |
3 |
4 |
5 |
X |
0 |
1 |
2 |
4 |
Л |
5 |
6 |
0 |
X |
2 |
3 |
5 |
5 |
6 |
0 |
1 |
2 |
X |
4 |
6 |
6 |
0 |
1 |
2 |
3 |
4 |
X |
Одиницею відносно операції ®7 є 0. Таблиця симетрична відносно діагоналі — ця умова визначає комутативність операції. Заувалсимо, що кожний стовпчик таблиці містить всі елементи групи.
Твердження 3. Будь-який стовпчик таблиці Келі для операції скінченної групи містить всі елементи групи.
Доведення. Розглянемо деяку групу (О, ®), й — скінченна множина. Припустимо, що деякий стовпчик а, таблиці Келі для операції ® не містить якого-небудь елемента множини Є. Тоді якийсь інший елемент а, в цьому стовпчику повинен зустрітися двічі, скажімо, у йому та /-ому рядках. Але тоді аи ® а, — = ау, а, ® а, = а; і отже,
а,. ® а, = а,® а„
ак ® а, ® а/ = а, ® а, ® а/
(помножуємо обидві частини рівності на а/), аи ® е — а,® е,
(а,® а/ = е за визначенням оберненого елемента),
а,, = аі (а, ® е = ак за визначенням одиниці).
Одержуємо а*= а,у що неможливе, оскільки тут ак, а, — елементи групи, що задають різні рядки таблиці. Таким чином, ї-й стовпчик таблиці Келі є перестановкою на множині елементів групи.
Запитання
Дайте визначення півгрупи, моноїду і групи.
Наведіть приклади півгрупи, що не є моноїдом, і моноїду, що не є групою.
Наведіть приклади групи.
Яка група називається абелевою? Наведіть приклади.
Які властивості елементів групи роблять можливим розв’язок рівнянь усередині групи?
Які властивості має таблиця Келі для скінченної групи?
Які властивості має операція абелевої групи?
Завдання
1. Доведіть, що в групі (Є, ®) для всіх а, Ь, с є б виконується:
а) якщо а ® Ь = а ® с, то Ь = с, і, якщо Ь ® а = с ® а, то Ь = с;
б) (а')' = а — обернений елемент до оберненого елемента до а дорівнює а.