Глава 14. Логические схемы 269

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Южный федеральный университет»

ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ
В г. ТАГАНРОГЕ

 

Гладков Л.А, Курейчик В.В., Курейчик В.М.

 

Дискретная математика

УЧЕБНИк

Под ред. КуреЙчика В.М.

Допущено учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям «Информатика и вычислительная техника» и «Информационные системы»

Таганрог

2011

УДК: 621.3 + 681.3

Рецензенты:

Кафедра прикладной математики Московского энергетического института, зав. кафедрой, д.т.н., профессор, лауреат премии президента РФ в области образования А.П. Еремеев (г. Москва).

Ю.О. Чернышев, зав. каф. прикладной математики и вычислительной техники Ростовской государственной академии сельскохозяйственного машиностроения, д.т.н., профессор, заслуженный деятель науки РФ (г. Ростов-на-Дону).

Гладков Л.А, Курейчик В. В., Курейчик В. М. Дискретная математика. Учебник / Под ред. В.М. Курейчика. – Таганрог: Изд-во ТТИ ЮФУ, 2011. – 312 с.

NSB №978-5-8327-0309-1

Рассмотрены такие основные разделы дискретной математики, как теория множеств, алгоритмов, алгебра логики, теория графов. Для лучшего усвоения материала использована современная методика обучения на основе “решебников”. Авторы рассмотрели вопросы: исчисления множеств, задания отношений и соответствий, описания упорядоченных бесконечных множеств, мультимножеств и нечетких множеств, основные алгоритмические модели, основные логические функции и законы алгебры логики, виды и способы задания графов, алгоритмы решения задач на ориентированных и неориентированных графах, а также основные определения из теории гиперграфов и нечетких графов. В начале каждой главы приводится краткое изложение теории, затем подробно рассматриваются примеры и задачи с решениями. Приводятся контрольные задачи, упражнения и глоссарий с пояснением основных терминов. Учебник предназначен для студентов вузов, обучающихся по направлениям «Информатика и вычислительная техника» и «Информационные системы». Учебник может быть полезным для специалистов, занятых разработкой интеллектуальных САПР, поддержки и принятия решений, новых информационных технологий в науке, технике, образовании, бизнесе и экономике.

 

ISBN 978-5-8327-0309-1           © ТТИ ЮФУ, 2011

© Гладков Л.А., Курейчик В. В.,

Курейчик В. М., 2011

Оглавление

Введение                                                                                     9

Цели и задачи преподавания дисциплины
«Дискретная математика»                                                              13

МОДУЛЬ 1. Основы теории множеств                                16

Глава 1. Исчисление множеств                                              18

1.1. Понятие множества                                                         18

1.2. Способы задания множеств                                              21

1.3. Подмножество                                                                    23

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                25

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    27

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 28

Глава 2. Операции над множествами                                  30

2.1. Объединение множеств                                                     30

2.2. Пересечение множеств                                                      30

2.3. Разность множеств                                                           31

2.4. Дополнение множества                                                    34

2.5. Тождества алгебры множеств                                        35

2.6. Доказательства тождеств с множествами                  36

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                38

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    42

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 42

Глава 3. Упорядоченные множества                                    45

3.1. Кортеж (Упорядоченное множество)                             45

3.2. Декартово произведение                                                    47

3.3. Операция проектирования множеств                            49

3.4. График                                                                                52

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                56

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    61

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 62

Глава 4. Отношения                                                                  63

4.1. Основные понятия отношений                                        64

4.2. Основные свойства отношений                                       65

4.3. Операции над отношениями                                            66

4.4. Основные свойства специальных отношений               68

4.5. Разбиение множеств                                                         70

4.6. Отношение порядка                                                           72

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    75

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 76

Глава 5. Соответствия                                                              78

5.1. Определение соответствия                                               78

5.2. Операции над соответствиями                                       81

5.3. Понятие образа и прообраза при соответствии          84

5.4. Доказательства тождеств с соответствиями            87

5.5. Основные свойства соответствий                                 89

5.6. Функция                                                                               97

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    100

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 103

Глава 6. Упорядоченные бесконечные множества          102

6.1. Основные сведения об упорядоченных бесконечных
множествах                                                                                           102

6.2. Проблема континуума                                                       105

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                110

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    111

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 112

Глава 7. Основные понятия теории мультимножеств    114

7.1. Понятие мультимножества                                            114

7.2. Операции над мультимножествами                               117

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                122

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    124

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 124

Глава 8. Нечеткие множества                                                 126

8.1. Нечеткие высказывания                                                     126

8.2. Операции над нечеткими множествами                        129

8.3. Нечеткие отношения и соответствия                           131

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                134

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    140

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 142

ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 1                                     142

ГЛОССАРИЙ К МОДУЛЮ 1                                             152

МОДУЛЬ 2. Основы теории алгоритмов                           163

Глава 9. Введение в теорию алгоритмов                            164

9.1. Понятие алгоритма                                                           164

9.2. Основные свойства алгоритмов                                       167

9.3. Классификация алгоритмов                                             169

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                173

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    176

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 177

Глава 10. Универсальные алгоритмические модели      178

10.1. Преобразование слов в произвольных абстрактных
алфавитах                                                                                             178

10.2. Числовые функции                                                            181

10.3. Построение алгоритмов по принципу «разделяй и
 властвуй»                                                                                              184

10.4. Представление алгоритма в виде детерминированного устройства                                                                                                                 185

10.5. Универсальные схемы алгоритмов                                 188

10.6. «Жадные» алгоритмы                                                      204

10.7. Нечеткие (расплывчатые) алгоритмы                          206

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    209

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 211

Глава 11. Сложность алгоритмов                                         213

11.1. Анализ алгоритмов                                                          213

11.2. Сложность алгоритмов                                                  221

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    225

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 226

ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 2                                     227

ГЛОССАРИЙ К МОДУЛЮ 2                                             230

МОДУЛЬ 3. АЛГЕБРА ЛОГИКИ                                         236

Глава 12. Элементы алгебры логики                                  237

12.1. Логические функции                                                         238

12.2. Основные логические тождества и законы                   245

12.3. Булевы функции одной и двух переменных                    248

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    252

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 253

Глава 13. Нормальные формы булевых функций           255

13.1. Дизъюнктивная и конъюнктивная нормальные формы 255

13.2. Способы перехода от нормальных к совершенным
нормальным формам                                                                            2609

13.3. Алгебра Жегалкина                                                           263

13.4. Функциональная полнота БФ                                        264

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    266

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 267

Глава 14. Логические схемы                                                  269

14.1. Реализация булевых функций                                          269

14.2. Минимизация булевых функций                                     273

14.3. Карты Карно                                                                     277

14.4. Метод Квайна-МакКласски                                             283

14.5. Переход от БФ к простейшим комбинационным схемам 289

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ                                                289

КОНТРОЛЬНЫЕ ВОПРОСЫ                                                    291

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ                 291

ТЕСТОВЫЕ ЗАДАНИЯ К МОДУЛЮ 3                                     292