- •Е.Д. Стрельцова, в.С. Стрельцов моделирование дискретных систем Учебно-методическое пособие по дисциплине «Дискретная математика»
- •2. Теория множеств и отношений………………………………….20
- •Введение
- •1. Функции алгебры логики
- •1.1. Основные понятия
- •Пример функции алгебры логики , заданной таблицей
- •1.2. Алгоритм нахождения фиктивных аргументов.
- •1.3. Элементарные функции алгебры логики
- •Функции алгебры логики, зависящие от одного аргумента
- •Вопросы к разделу 1
- •2. Теория множеств и отношений
- •2.1. Множества. Способы задания множеств
- •2.2. Основные операции над множествами
- •2.2.1. Объединение множеств
- •2 .2.2. Пересечение множеств
- •2.2.3. Разность множеств
- •2.2.4. Дополнение множеств
- •2.4. Свойства операций над множествами
- •2.5. Упорядоченные множества
- •2.6. Прямое (декартово) произведение множеств
- •2.7. Степень множеств
- •2.8. Сечение и проекция
- •Декартово произведение
- •2.9. Соответствия
- •2.10. Композиция соответствий.
- •2.11. Отображения
- •2.12. Виды отображений. Функциональное отображение (функция)
- •2.13. Функционалы
- •2.14. Операторы
- •2.15. Линейные операторы
- •Отношение «Читает лекции по…»
- •Отношение «Посещать лекции»
- •2.20. Бинарные отношения
- •2.20.1. Матричный способ задания отношений
- •2.20.2. Задание отношений в виде графа
- •2.20.3. Задание отношений с помощью фактор множества
- •2.21. Свойства бинарных отношений
- •2.22. Отношение эквивалентности
- •2.23. Отношение порядка
- •2.24. Изоморфизм отношений
- •2.26. Операции над бинарными отношениями
- •2.26.1. Объединение отношений
- •2.26.2. Пересечение отношений
- •2.26.3. Разность отношений
- •2.26.4. Включение отношений
- •2.26.5. Переход к обратному отношению
- •2.26.6. Произведение отношений
- •2.26.7. Транзитивное замыкание
- •Вопросы к разделу № 2
- •3. Алгебраические системы
- •3.1. Понятие алгебраической системы
- •3.1. Морфизм алгебраических систем
- •3.3. Автоморфизмы
- •3.4. Виды универсальных алгебр
- •3.4.1. Полугруппы. Моноиды
- •3.4.2. Морфизм групп
- •3.4.3. Свойства морфизма групп
- •3.4.4. Кольцо
- •Вопросы к разделу №3
- •4. Практикум к решению задач Основные обозначения
- •4.1. Операции над множествами
- •Разностью множеств а и в называется множество
- •Симметрической разностью множеств а и в называется множество
- •Пустым множеством называется множество, не имеющее ни одного элемента.
- •Задачи и упражнения
- •На основании (14) можно записать
- •По определению объединения
- •Пусть теперь у (ав) (ас) у (ав) у (ас) (у а у в) (у а у с) у а (у в у с)
- •Задачи для самостоятельного решения
- •4.2. Векторное произведение
- •4.3. Соответствие
- •Свойства отношений
- •Список литературы
- •Моделирование дискретных систем
- •3 46428, Г. Новочеркасск, ул. Просвещения, 132
3.4.2. Морфизм групп
Пусть даны две группы: , , , . Обе группы представляют собой однотипные алгебры. Моморфизмом группы на группу называется отображение , которое является согласованным с заданной операцией:
;
.
Морфизм может быть гомоморфизмом, мономорфизмом или изоморфизмом в зависимости от того, является ли отображение соръекцией, инъекцией или биекцией.
3.4.3. Свойства морфизма групп
Теорема 3.4
Морфизм групп переводит единицу в единицу.
Доказательство
Рассмотрим две группы: , , , . Пусть – единица группы . Возьмём любой произвольный элемент множества и выполним следующую операцию: . Последняя запись означает, что является единицей группы .
Теорема 3.5
Морфизм групп переводит ноль в ноль.
Доказательство
Будем рассматривать две группы: , , , . Пусть – ноль группы . Возьмём любой произвольный элемент множества и выполним следующую операцию: . Последняя запись означает, что является нулёмгруппы .
Теорема 3.6
Морфизм групп переводит обратный элемент в обратный элемент.
Доказательство
Будем рассматривать две группы: , , , . Пусть – элемент, являющийся обратным элементу группы . Над элементами и выполним следующую операцию: . Последняя запись означает, что является нулёмгруппы .
3.4.4. Кольцо
Рассмотрим алгебру с двумя двуместными операциями:
, , .
Пусть – абелева группа, а – полугруппа.
В этом случае алгебра носит название кольца.
Определение 3.11
Кольцо называется кольцом с единицей, если в нём есть единица относительно операции .
Определение 3.12
Кольцо называется коммутативным кольцом с единицей, если операция коммутативна.
Пример 3.1
Рассмотрим алгебру , , , где множество действительных чисел, представляет собой операцию сложения, а операцию умножения. Таким образом, нами рассматривается кольцо . Необходимо проверить, является ли алгебра кольцом?
Решение
1. Проверим алгебру относительно операции сложения.
- , выполняется свойство коммутативности ;
- , , выполняется свойство ассоциативности ;
- в множестве есть число «0» (ноль), для которого справедливо , ; по определению число «0» является единицей кольца относительно операции сложения;
- в множестве для любого числа найдётся обратный ему элемент , .
- операция сложения коммутативна ;
2. Проверим алгебру относительно операции умножения.
- , свойство коммутативности выполняется ;
- , , выполняется свойство ассоциативности ;
- в множестве есть число «1» (единица), для которого справедливо
, ; по определению число «1» является единицей кольца относительно операции умножения.
- операция умножения коммутативна ;
Таким образом, алгебра представляет собой коммутативное кольцо с единицей.
Вопросы к разделу №3
Дайте определение алгебраической системы. Запишите высказывательную форму.
Какие алгебраические системы называются однотипными?
Какие алгебраические системы называются конечными?
Какие алгебраические системы называются конечного типа?
Какое множество называется замкнутым относительно операции?
Какое отображение называется морфизмом алгебраических систем?
Что называется мономорфизмом? Гомоморфизмом? Изоморфизмом?
Дайте определение автоморфизма.
Сформулируйте теорему об обратном изоморфизме. Приведите доказательство теоремы.
Сформулируйте теорему о композиции изоморфизмов. Приведите её доказательство.
Что называется полугруппой?
Дайте определение левой и правой единицы полугруппы, а также просто единицы.
Что называется моноидом?
Дайте определение левого и правого нуля полугруппы, а также просто нуля.
Что называется левым и правым обратимым элементом?
Дайте определение группы.
Какая группа называется абелевой?
Что такое морфизм групп?
Сформулируйте теорему о переводе морфизмом групп единицы в единицу.
Сформулируйте теорему о переводе морфизмом групп нуля в ноль.
Сформулируйте теорему о переводе морфизмом групп обратного элемента в обратный элемент.
Какая универсальная алгебра называется кольцом?
Дайте определение кольца с единицей.
Приведите примеры колец.