- •Е.Д. Стрельцова, в.С. Стрельцов моделирование дискретных систем Учебно-методическое пособие по дисциплине «Дискретная математика»
- •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
Министерство образования и науки Российской Федерации
Южно-Российский государственный технический университет
(Новочеркасский политехнический институт)
Е.Д. Стрельцова, в.С. Стрельцов моделирование дискретных систем Учебно-методическое пособие по дисциплине «Дискретная математика»
Новочеркасск
ЮРГТУ (НПИ)
2011
УДК 62-50(076.5)
Рецензент – канд. техн. наук, доцент И.И. Гурчин
Стрельцова Е.Д., Стрельцов В.С.
Моделирование дискретных систем: методическое пособие по дисциплине «Дискретная математика» / Юж.-Рос. гос. техн. ун-т. (НПИ) Новочеркасск: >HUNE (YGB), 2011.- 111 с.
В пособии излагаются основные разделы курса «Дискретная математика», к которым относятся основные понятия алгебры логики, теории множеств и отношений, теории алгебраических структур. При подготовке пособия использован конструктивный подход. Для освоения методов дискретного анализа и углублённого изучения дисциплины составлены задачи.
Предназначено для студентов, обучающихся по специальностям «Вычислительные машины, комплексы, системы и сети» и «Информатика и вычислительная техника».
УДК 62-50(076.5)
© Южно-Российский государственный
Технический университет (НПИ), 2011.
© Стрельцова Е.Д., Стрельцов В.С.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ……………………………………………………………………….6
1. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ……………………………………………..7
1.1. Основные понятия……………………………………………………………9
1.2. Алгоритм нахождения фиктивных аргументов…………………………...12
1.3. Элементарные функции алгебры логики……………………….…………14
Вопросы к разделу № 1..………………………………………………………..19
2. Теория множеств и отношений………………………………….20
2.1. Множества. Способы задания множеств……………………………...…..20
2.2. Основные операции над множествами…………………………………….23
2.2.1. Объединение множеств…………………………………………………...24
2 .2.2. Пересечение множеств……………………………………………………26
2.2.3. Разность множеств……………………………………………………….27
2.2.4. Дополнение множеств…………………………………………………….28
2.2.6. Разбиения и покрытия множеств………………………………………..30
2.3. Соотношения между множествами………………………………………..30
2.4. Свойство операций над множествами……………………………………33
2.5. Упорядоченные множества………………………………………………..34
2.6. Прямое (декартово) произведение множеств……………………………..35
2.7. Степень множеств………………………………………………………….36
2.8. Сечение и проекция…………………………………………………………37
2.9. Соответствия……………………………………………………………….40
. Композиция соответствий………………………………………………...43
2.11. Отображения……………………………………………………………….45
Виды отображений. Функциональное отображение (функция)……….45
Функционалы……………………………………………………………..47
Операторы…………………………………………………………………50
Линейные операторы……………………………………………………..53
Сюрьективное отображение (сюръекция)………………………………54
Инъективное отображение (инъекция)………………………………….54
Отношения………………………………………………………………...55
Бинарные отношения…………………………………………………….60
Матричный способ задания отношений……………………….....60
Задание отношений в виде графа…………………………………62
Задание отношений с помощью фактор множества……………..63
Свойства бинарных отношений……………………..………………….64
Отношение толерантности……………………………………………….66
Отношение эквивалентности…………………………………………….67
Отношение порядка………………………………………………………70
Изоморфизм отношений………………………………………………….72
Решётки……………………………………………………………………73
Операции над бинарными отношениями……………………………….75
Объединение отношений………………………………………….76
Пересечение отношений…………………………………………..76
Разность отношений……………………………………………….77
Включение отношений…………………………………………….78
Переход к обратному отношению………………………………...78
Произведение отношений…………………………………………79
Транзитивное замыкание………………………………………….80
Вопросы к разделу № 2………………………………………………………….81
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ……………………………………..….82
3.1. Понятие алгебраической системы………………………………………....82
3.2. Морфизм алгебраических систем…………………………………………85
3.3. Автоморфизмы……………………………………………………………...85
3.4. Виды универсальных алгебр…………………………………………….…89
3.4.1. Полугруппы. Моноиды…………………………………………………...89
3.4.2. Морфизм групп……………………………………………………………91
3.4.3. Свойства морфизма групп………………………………………………..92
3.4.4. Кольцо……………………………………………………………………..93
Вопросы к разделу №3…………………………………………………………..94
ПРАКТИКУМ К РЕШЕНИЮ ЗАДАЧ……………………………..……..95
Операции над множествами……………………………………………96
4.2. Векторное произведение………………………………………………..101
4.3. Соответствие……………………………………………………………105
Список литературы…………………………………………………………….111