- •Е.Д. Стрельцова, в.С. Стрельцов моделирование дискретных систем Учебно-методическое пособие по дисциплине «Дискретная математика»
- •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.3. Автоморфизмы
Рассмотрим алгебраичскую систему
, , , , .
Зададим отображение , обладающее свойством согласованности с операциями , и отношениями , :
, , ;
, ,
.
Пример 3.1
Рассмотрим алгебраическую систему с одной операцией и одним отношением , , . Пусть и , т.е. рассматривается двуместная операция и бинарное отношение : , . Допустим, что представляет собой операци сложения, а – отношение «быть больше». Тогда можно запмсать:
, , .
Зададим отображение , представляющее собой умножение на число . Тогда , .
Запишем условия согласованности: и для нашего случая.
Имеем ; .
Теорема 3.1. (Теорема об обратном изоморфизме).
Пусть и – однотипные алгебры , , , . Допустим, что – изоморфизм. Тогда также изоморфизм.
Доказательство
Если отображение является изоморфизмом, то имеет место согласованность со всеми парами одноимённых операций , .
Является очевидным, что для любого из множества найдётся и притом только один элемент из , являющийся образом элемента : , . Аналогично будем рассуждать для всех остальных элементов: ,…, . Запишем условие согласованности отображения с одноимёнными операциями:
.
Тогда или
. Последняя запись подтверждает согласованность одноимённых операций с отображением , т.е. отображение является морфизмом. Можно доказать, что биективно. Последнее предлагается студентам доказать самостоятельно.
Теорема 3.2. (Теорема о композиции изоморфизмов).
Пусть даны три универсальных алгебры:
, ,
, ,
, .
Допустим, что и – изоморфизмы. Тогда изоморфизмом является композиция отображений .
Доказательство.
Поскольку отображения и изоморфизмы, то они биективны. Тогда у любого элемента из найдётся образ из и причём только один. Тогда можно записать:
, ;
, :
……………………………………
, .
Аналогично относительно отображения :
, ;
, ;
…………………………………….
, .
Если и изоморфизмы, то можно записать условия согласованности с одноимёнными операциями:
.
Но . Тогда
Последняя запись означает согласованность одноимённых операций и относительно композиции отображений . Свойство биективности отображения предлагается студентам доказать самостоятельно.
3.4. Виды универсальных алгебр
3.4.1. Полугруппы. Моноиды
Пусть дана универсальная алгебра с одной двуместной операцией: , . Эта алгебра называется полугруппой, если её операция ассоциативна, т.е. , , выполняется условие .
В полугруппе могут присутствовать или отсутствовать такие элементы, как левая единица , правая единица и просто единица :
, ;
, ;
.
Теорема 3.3
Если полугруппа одновременно имеет и левую и правую единицу, то эти элементы совпадают и являются единственной единицей группы.
Доказательство.
Пусть полугруппа , содержит одновременно левую и правую единицы. Выполним над ними операцию , имеем: .
Определение 3.6
Полугруппа, содержащая единицу, называется моноидом.
В полугруппе могут присутствовать или отсутствовать такие элементы, как левый ноль , правый ноль и просто ноль :
, ;
, ;
.
Теорема 3.3
Если полугруппа одновременно имеет и левый и правый ноль, то эти элементы совпадают и являются единственным нулём группы.
Доказательство
Пусть полугруппа , содержит одновременно левый и правый нули. Выполним над ними операцию , имеем: .
Определение 3.7
Рассмотрим моноид , . Элемент называется элементом, обратимым слева, если найдётся такой элемент из , что выполняется: . Элемент называется левым элементом, обратным элементу .
Определение 3.8
Рассмотрим моноид , . Элемент называется элементом, обратимым справа, если найдётся такой элемент из , что выполняется: . Элемент называется правым элементом, обратным элементу .
Теорема 3.4
Если элемент моноида , обратим слева и справа, то левый и правый элементы, обратные элементу , совпадают.
Доказательство.
Для доказательства выполним операцию :
,
что и требовалось доказать. Элемент, обратный элементу , будем обозначать .
Определение 3.9
Группой называется моноид, в котором каждый элемент обратим.
Определение 3.10
Группа называется коммутативной или абелевой, если её операция коммутативна: , .