Книга: Триумфгородских М. В. «Дискретная математика и математическая логика для информатиков, экономистов и менеджеров»

В книге изложен ряд разделов и вопросов дискретной математики и математической логики, изучаемых главным образом на младших курсах вузов. В данное издание включены не только основные понятия и теоретические положения дисциплины, но также примеры, методы, приемы и алгоритмы решения прикладных задач.
Книга может представлять интерес для широкого круга будущих специалистов, бакалавров и магистров соответствующих специальностей и направлений подготовки.

Содержание:

Предисловие...... 3 Глава 1. Основы теории множеств...... 6 1. 1. Основные понятия теории множеств...... 6 1. 2. Множества и их спецификации...... 9 1. 3. Операции над множествами...... 14 1. 4. Тождества алгебры множеств...... 19 1. 5. Отношения...... 25 1. 6. Матрица бинарного отношения и ее применение...... 28 1. 7. Соответствия...... 33 1. 8. Отображения...... 35 1. 9. Функции...... 36 Вопросы для самоконтроля...... 39 Библиографический список...... 41 Глава 2. Комбинаторика...... 42 2. 1. Перестановки, размещения и сочетания...... 42 2. 2. Разбиения...... 44 2. 3. Перестановки с повторениями...... 46 2. 4. Размещения с повторениями...... 47 2. 5. Сочетания с повторениями...... 47 2. 6. Комбинаторный принцип включений и исключений...... 48 Вопросы для самоконтроля...... 49 Библиографический список...... 50 Глава 3. Элементы теории нечетких и выпуклых множеств...... 51 3. 1. Нечеткое множество и нечеткое отношение...... 51 3. 2. Операции над нечеткими множествами...... 52 3. 3. Примерный вид функций принадлежности...... 56 3. 4. Выпуклые множества...... 57 3. 5. Средневзвешенное по элементам множества...... 57 Вопросы для самоконтроля...... 58 Библиографический список...... 59 Глава 4. Алгоритмы на базе однонаправленных функций...... 60 4. 1. Понятие о неразрешимых вычислительных проблемах...... 60 4. 2. Однонаправленные функции...... 61 4. 3. Алгоритм RSA в режиме шифрования...... 66 4. 4. Алгоритм RSA в режиме электронной цифровой подписи...... 68 4. 5. Алгоритм Эль-Гамаля в режиме шифрования...... 70 4. 6. Алгоритм Эль-Гамаля в режиме электронной цифровой подписи...... 73 4. 7. Применение теоремы об остатках при разделении секрета...... 74 Вопросы для самоконтроля...... 78 Библиографический список...... 79 Глава 5. Основы теории графов...... 80 5. 1. Диаграммы графов и их элементы...... 80 5. 2. Маршруты и циклы в графах...... 83 5. 3. Матричное представление графов в ЭВМ...... 85 5. 4. Эйлеровы и гамильтоновы циклы...... 90 5. 5. Планарные графы и их применение...... 94 5. 6. Внутренняя и внешняя устойчивость множества вершин графа...... 95 5. 7. Потоки в сетях...... 98 5. 8. Динамическое программирование и кратчайший путь в графе...... 105 5. 9. Динамическое программирование и задача о замене оборудования...... 111 5. 10. Динамическое программирование и распределение инвестиций...... 116 5. 11. Алгоритм Дейкстры поиска кратчайших путей в графах...... 121 5. 12. Задача коммивояжера...... 124 Вопросы для самоконтроля...... 128 Библиографический список...... 130 Глава 6. Исчисление высказываний...... 132 6. 1. Краткий экскурс в историю логики высказываний...... 132 6. 2. Логика и исчисление высказываний...... 134 6. 3. Классическое определение исчисления высказываний...... 137 6. 4. Конструктивное определение исчисления высказываний...... 138 6. 5. О правилах вывода в исчислении высказываний...... 139 6. 6. Известные аксиоматизации исчисления высказываний...... 140 Вопросы для самоконтроля...... 141 Библиографический список...... 143 Глава 7. Исчисление предикатов...... 144 7. 1. Логика и исчисление предикатов...... 144 7. 2. Правила вывода в логике предикатов первого порядка...... 148 7. 3. Метод резолюции для логики предикатов первого порядка...... 149 Вопросы для самоконтроля...... 152 Библиографический список...... 153 Глава 8. Модальная и нечеткая логики...... 154 8. 1. Основные понятия модальной логики...... 154 8. 2. Синтаксис и семантика модальной логики...... 156 8. 3. Схемы модальных формул...... 157 8. 4. Бинарные отношения и семантика возможных миров...... 157 8. 5. Обзор некоторых формально-логических моделей...... 159 8. 6. Нечеткие логические формулы...... 161 Вопросы для самоконтроля...... 164 Библиографический список...... 165 Глава 9. Немонотонные рассуждения и методы поиска...... 166 9. 1. Модифицируемые рассуждения и свойства немонотонных логик...... 166 9. 2. Зацикливание немонотонных рассуждений и его преодоление...... 167 9. 3. Стратегии немонотонного вывода в глубину и ширину...... 169 9. 4. Логические рассуждения и метод математической индукции...... 171 Вопросы для самоконтроля...... 176 Библиографический список...... 177

Издательство: "Диалог-МИФИ" (2011)

ISBN: 9785864042380