Министерство образования и науки Российской Федерации

Южно-Российский государственный технический университет

(Новочеркасский политехнический институт)

Е.Д. Стрельцова, в.С. Стрельцов моделирование дискретных систем Учебно-методическое пособие по дисциплине «Дискретная математика»

Новочеркасск

ЮРГТУ (НПИ)

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

10. . Композиция соответствий………………………………………………...43

2.11. Отображения……………………………………………………………….45

12. Виды отображений. Функциональное отображение (функция)……….45

13. Функционалы……………………………………………………………..47

14. Операторы…………………………………………………………………50

15. Линейные операторы……………………………………………………..53

16. Сюрьективное отображение (сюръекция)………………………………54

17. Инъективное отображение (инъекция)………………………………….54

18. Отношения………………………………………………………………...55

19. Бинарные отношения…………………………………………………….60

    1. Матричный способ задания отношений……………………….....60

    2. Задание отношений в виде графа…………………………………62

    3. Задание отношений с помощью фактор множества……………..63

20. Свойства бинарных отношений……………………..………………….64

21. Отношение толерантности……………………………………………….66

22. Отношение эквивалентности…………………………………………….67

23. Отношение порядка………………………………………………………70

24. Изоморфизм отношений………………………………………………….72

25. Решётки……………………………………………………………………73

26. Операции над бинарными отношениями……………………………….75

    1. Объединение отношений………………………………………….76

    2. Пересечение отношений…………………………………………..76

    3. Разность отношений……………………………………………….77

    4. Включение отношений…………………………………………….78

    5. Переход к обратному отношению………………………………...78

    6. Произведение отношений…………………………………………79

    7. Транзитивное замыкание………………………………………….80

Вопросы к разделу № 2………………………………………………………….81

2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ……………………………………..….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

2. ПРАКТИКУМ К РЕШЕНИЮ ЗАДАЧ……………………………..……..95

1. Операции над множествами……………………………………………96

4.2. Векторное произведение………………………………………………..101

4.3. Соответствие……………………………………………………………105

Список литературы…………………………………………………………….111