- •Буковинський університет
- •Дискретна математика
- •Навчально-методичний посібник
- •Чернівці
- •Задачі та вправи 12
- •Задачі та вправи 28
- •Операції над множинами
- •Тема „Алгебра лінійних множин”
- •Способи задання множин
- •Порожня множина ()
- •Універсум (u)
- •Множина підмножин
- •Алгебра множин
- •Узагальнення операцій над множинами
- •Задачі до теми „Алгебра лінійних множин”
- •Тема „Відношення і функції”
- •Окремі випадки відношень
- •Властивості композицій:
- •Властивості відношень
- •Основні властивості відображень
- •Відношення еквівалентності
- •Відношення порядку
- •Відношення рівнопотужності
- •Властивості скінченних множин
- •Властивості зчисленних множин
- •Задачі до теми „Відношення і функції”
- •Тема „Булеві функції”
- •Способи задання булевих функцій
- •Булеві функції однієї змінної
- •Область визначення булевих функцій
- •Елементарні функції алгебри логіки
- •Булевий простір
- •Властивості функцій
- •Деякі операції над висловленнями
- •Формули в алгебрі логіки
- •Основні тотожності
- •Правила
- •Принцип двоїстості
- •Типи булевих функцій
- •Канонічні форми перемикальних функцій
- •Досконалі диз’юнктивні нормальні форми перемикальних функцій
- •Досконалі кон’юнктивні нормальні форми перемикальних функцій
- •Властивості досконалих форм
- •Скорочена диз’юнктивна нормальна форма перемикальних функцій
- •Утворення скороченої диз’юнктивної нормальної форми методом Квайна
- •Метод Квайна-Маккласкі
- •Утворення мінімальних кон’юктивних нормальних форм
- •Алгоритм утворення мінімальної кнф
- •Геометричне подання функцій алгебри логіки
- •Спрощення булевих функцій
- •Задачі до теми „Способи задання булевих функцій. Операція суперпозиції”
- •Задачі до теми „Істотні та фіктивні змінні”
- •Задачі до теми „Спеціальні види формул. Диз’юнктивні і кон’юнктивні нормальні форми. Поліном Жегалкіна”
- •Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій
- •Задачі до теми „Класи функцій, що зберігають константи”
- •Задачі до теми „Двоїстість і клас самодвоїстих функцій”
- •Задачі до теми „Монотонність і клас монотонних функцій”
- •Повнота систем булевих функцій
- •Тема „Рекурсивні функції”
- •Частково-рекурсивні функції
- •Тема „Скінченні автомати. Машина Тьюринга”
- •Машина Тьюринга
- •Тема „Основні поняття і властивості алгоритмів”
- •Основні вимоги до алгоритмів
- •Основні властивості алгоритму
- •Тема „Формальні системи. Алгебра висловлювань”
- •Аксіоматичний спосіб опису висловлювань
- •Властивості числення висловлювань
- •Задачі до теми „Алгебра висловлювань”
- •Тема „Логіка і числення предикатів”
- •Рівносильність формул
- •Задачі до теми „Логіка і числення предикатів”
- •Тема „Алгебри. Типи алгебр. Алгебраїчні системи”
- •Гомоморфізм та ізоморфізм алгебри
- •Типи алгебр
- •Алгебраїчні системи
- •Тема „Елементи комбінаторики”
- •Формула включень і виключень
- •Рекурентні співвідношення
- •Основні властивості кількості сполук
- •Біном Ньютона
- •Властивості розкладу бінома Ньютона і біномних коефіцієнтів
- •Поліномні твірні функції
- •Розміщення і функціональні відображення
- •Розбиття
- •Поліномна формула
- •Задачі до теми „Комбінаторика”
- •Тема „Графи”
- •Задання графа за допомогою матриці інцидентності та списку ребер
- •Задання графа за допомогою матриці суміжності
- •Локальні степені вершин графа
- •Частини графа, суграфи та підграфи
- •Операції з частинами графа
- •Маршрути, ланцюги та цикли
- •Цикломатичне число графа
- •Задачі до теми „Графи”
- •Дискретна математика
- •Література
- •Навчальне видання Пукальський Іван Дмитрович,
- •Лусте Ірина Петрівна,
Гомоморфізм та ізоморфізм алгебри
Алгебри з різними типами мають істотно різну будову. Якщо алгебри мають однаковий тип, то наявність у них подібності характеризується за допомогою понять гомоморфізму й ізоморфізму.
Нехай є дві алгебри A = (K; 1, …, p) та M (M; 1, …, p) однакового типу.
Гомоморфізмом алгебри А в алгебру В називається відображення : K M, що задовольняє умову
( i(kj1, …, kj1(i))) = i((kj1), …, (kj1(i))) (1)
для всіх i = 1, …, p (1(i)-арність операцій i і i, яка у них за умовою однакова) та всіх kjr K. Зміст умови (1) в тому, що незалежно від того, чи здійснено спочатку операцію i в A, а потім виконано відображення Г, або спочатку зроблено відображення Г, а потім здійснено відповідну операцію i, результат буде однаковим.
Ізоморфізмом алгебри А на алгебру В називається взаємно однозначний гомоморфізм. У цьому випадку існує обернене відображення –1: M K, також взаємно однозначне.
Якщо існує ізоморфізм A на B, то є ізоморфізм B на A, при цьому алгебри A і B називаються ізоморфними. Потужності основних множин ізоморфних алгебр є рівними (при гомоморфізмі ця рівність може не виконуватися). Якщо A = B, то ізоморфізм називається ізоморфізмом на себе, або автоморфізмом; якщо B A, то ізоморфізм є ізоморфізмом у себе.
Приклад 7. Нехай ZN – множина всіх цілих чисел, Z2N – множина всіх парних чисел. Алгебри (ZN; +) і (Z2N; +) – ізоморфні; ізоморфізмом є відображення Г2n: n 2n, причому умова (1) тут має вигляд 2(a + b) = 2a + 2b. Оскільки Z2N ZN, Г2n – ізоморфізм (ZN; +) у себе. Відображення Г–n: n (–n) є для алгебри (ZN; +) автоморфізмом; умова (1) має вигляд (–a) + (–b) = –(a + b). Для алгебри (ZN; ) Г–n не є автоморфізмом, оскільки (–a)(–b) –(ab).
Сутність ізоморфізму можна виразити таким чином: якщо алгебри А та В – ізоморфні, то елементи й операції В можна перейменувати так, що В збігатиметься з А. З умови (1) ізоморфізму випливає, що будь-яке еквівалентне співвідношення в алгебрі A збігається в будь-якій ізоморфній їй алгебрі A. Це дає змогу, одержавши такі співвідношення в алгебрі A, автоматично поширити їх на всю алгебри, ізоморфну A.
Типи алгебр
Означення. Якщо в множині F S композиція будь-яких двох елементів з F також належить F, то F називається замкненою множиною відносно заданого закону композиції (або відносно заданої операції). Елемент а називається регулярним, якщо з того, що aTx = aTy й xTa = yTa випливає x = y. Таким чином, будь-яке число – регулярно відносно „+”, а для множення регулярним є будь-яке число, крім нуля.
Означення. Нейтральним елементом e S називається такий елемент, що для всіх елементів x S справджується рівність eTx = xTe = x. Нейтральний елемент називають ще одиницею.
Твердження. Якщо нейтральний елемент існує, то він – єдиний і регулярний.
Доведення. Припустимо, що нейтральній елемент не єдиний. Нехай існують два нейтральні елементи e1 S та e2 S, e1 e2. Оскільки e1 – нейтральний елемент, то e1Te2 = e2Te1 = e2, а оскільки e2 – нейтральний елемент, то e2Te1 = e1Te2 = e1. Одержана суперечність доводить твердження.
Доведемо регулярність від супротивного: припустимо, що нейтральний елемент – не регулярний, тобто нехай eTx = eTy й xTe = yTe, але x y. Оскільки у – нейтральний елемент, eTx = xTe = x, але eTx =
eTy – за умовою, а eTy = yTe = y. Одержана суперечність доводить твердження.
Приклад. Розглянемо множину всіх квадратних матриць n-го порядку з числовими елементами. Очевидно, нульова матриця є нейтральним елементом відносно додавання, а одинична матриця – нейтральним елементом відносно множення.
Якщо множина містить нейтральний елемент е відносно операції T, то елемент b називається симетричним елементу a, якщо aTb = bTa = e. При цьому a називається симетричним елементом і b позначається через , тобто b = .
Якщо існує елемент – симетричний елементу a, то він єдиний і регулярний.
Симетричними елементами на множині квадратних матриць n-го порядку відносно операції множення матриць є взаємно обернені матриці.
Означення. Півгрупою називається алгебра з однією асоціативною бінарною операцією. Ця операція є додаванням. Якщо ж додавання комутативне, то півгрупа називається комутативною, або абелевою. Півгрупа з одиницею є моноїдом. Одиниця в півгрупі – завжди єдина.