Елементи абстрактної алгебри

Приклади розв’язання задач

1. Задано відношення R Í X ´ X, X = N, (x, y) Î R, якщо x ² – y ² ділиться на 2. Дослідити відношення на рефлективність, антирефлективність, симетричність, антисиметричність, транзитивність.

Розв’язування: Очевидно, що відношення є рефлективним, бо для довільних x вираз x ² ‑ x ² завжди рівний нулю, а отже ділиться на 2. Оскільки R є рефлективне, то воно не може бути антирефлективним.

При аналізі на симетричність припустимо, що (x, y) Î R, і нехай (x ² – y ²) / 2 = z. Тоді для (y, x), (y ² – x ²) / 2 = - z, отже і (y, x) Î R. Звідси робимо висновок, що відношення R є симетричним, а отже воно не буде антисиметричним.

З умови належності пари (x, y) відношенню R випливає, що x та y повинні одночасно бути або парними або непарними числами. Для того, щоб (y, z) Î R, необхідно, щоб число z також було або парним або непарним одночасно з числом y, а, отже, і з числом x. Тому умова транзитивності (x R y і y R z ® x R z) виконується.

Так як, досліджене відношення R є рефлективним, симетричним та транзитивним, то це - відношення еквівалентності.

2. Знайти d_R, r_R, R ^-1, R ○ R, R ○ R ^-1, R ^-1○ R, для відношення R = {(x, y)| x, y Î N i x ділить у }.

Розв’язування. Будемо вважати, що нуль ділить нуль. Наступні множини d_R, r_R та N співпадають (d_R = r_R = N), оскільки (х, х) Î R. Множина R ^-1 = {(x, y) | x, y Î N i y ділить x }. Композиція R ○ R = R, а R ○ R ^-1 = N ², тому що (х, у) Î R ○ R ^-1 це твердження, що існує z таке, що x ділить z i у ділить z. Але таке z легко знайти за довільними х та у. Треба взяти, наприклад, z = x×y. Множина R ^-1○ R = N ², тому що (х, у) Î R ^-1○ R це твердження, що існує z таке, що z ділить x і z ділить y. Треба взяти z = 1 для довільних x та y.

3. Довести, що для будь-яких бінарних відношень виконується рівність (R ₁ È R ₂)^‑1 = R ₁^‑1 Ç R ₂^‑1.

Розв’язування: (x, y) Î (R ₁ È R ₂)^‑1 Û (x, y) Ï (R ₁ È R ₂) Û (x, y) Ï R ₁ або (x, y) Ï R ₂ Û (x, y) Î R ₁^‑1 або (x, y) Î R ₂^‑1 Û (x, y) Î R ₁^‑1 Ç R ₂^‑1.

4. Оцінити потужність множини всіх можливих відображень множини натуральних чисел в множину цілих чисел (тобто N ® Z).

Розв’язування: Так як існує бієктивне відображення N ® Z, то задачу можна звести до оцінки всіх можливих відображень N ® N. Потужність множини всіх можливих відображень N ® N рівна ν^ν, де ν –потужність зчисленної множини.

Основу сучасних швидких та якісних технологій обробки інформації становлять комп’ютери – від персональних до суперЕОМ. Подання інформації для для ЕОМ дискретне, і її обробка складається з послідовностей елементарних перетворень тих чи інших інформаційних одиниць (слів, літер, цифр тощо). Тобто, фундаментальною ідеєю щодо відображення реального світу в комп’ютері є ідея дискретизації об’єктів. Для ефективної роботи на комп’ютері необхідно навчитися будувати моделі реальних об’єктів та процесів їх перетворення. Досить часто такими моделями можуть бути конструкції дискретної математики, зокрема, такі, як алгебраїчні структури, що розглядаються в даних методичних вказівках.

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

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

Однією з областей застосування є кодування інформації при передачі через канал зв’язку. При цьому ставиться вимога забезпечити виправлення помилок, які виникають внаслідок фізичних завад у каналах зв’язку або пристроях зберігання інформації. Це досягається шляхом введення при кодуванні надлишковості, яка дозволяє так вибрати послідовності символів для передачі, щоб вони задовольняли додатковим умовам, перевірка яких після прийому дає можливість виявити й виправити помилки. Найкращих результатів досягнуто, коли символи, що передаються, розглядаються як елементи певних алгебраїчних структур, зокрема скінченних полів (полів Галуа). При цьому простими стають процедури кодування й декодування, зменшується ймовірність неправильного декодування даних (циклічні коди, коди Ріда-Соломона тощо).

Іншою областю застосування є криптографія: захист інформації шляхом її перетворення, що виключає прочитання цієї інформації сторонньою особою. Ще кілька десятиліть тому такий підхід стосувався в основному військових операцій або був пов’язаний з шпигунськими історіями, а не був предметом широкого використання. Причиною бурхливого розвитку криптографії є широке використання комп'ютерних мереж, зокрема глобальної мережі Internet, по яких передаються великі обсяги інформації державного, військового, комерційного й приватного характеру, що не допускає можливості доступу до неї сторонніх осіб. При виконанні сучасних алгоритмів шифрування з таємним ключем використовуються алгебраїчні структури скінчених полів (наприклад, стандарт AES симетричного шифрування США). Широко вживаний алгоритм RSA шифрування з відкритим ключем (багато провідних світових ІТ-компаній вклали в його розвиток значні кошти, він стоїть в основі функціонування Internet-платежів eMoney) ґрунтується на алгебраїчному понятті фактор-кільця кільця цілих чисел за модулем великого натурального числа.

Іншими областями, де використовуються алгебраїчні структури, є аналіз та синтез скінченних автоматів; реляційні бази даних.

Дата добавления: 2014-11-29