Соболева Т.С. Дискретная математика: учебник для студ. вузов / Т. С.Соболева, А. В.Чечкин; под ред. А. В.Чечкина. — М., 2006. — 256 с. — (Университетский учебник. Сер. Прикладная математика и информатика).
В учебнике рассмотрены общие (множества и отношения, алгебра и топология) и специальные (математическая логика, математическая кибернетика, математическая информатика) вопросы дискретной математики. Для студентов высших учебных заведений. Может быть полезен аспирантам, научным работникам и специалистам в области прикладной математики и современных наукоемких информационных технологий.
ОГЛАВЛЕНИЕ
Предисловие...................................3
Введение. Новый период развития математики.............5
ЧАСТЬ I. МНОЖЕСТВА И ОТНОШЕНИЯ..................11
Глава 1. Основные понятия теории множеств ................11
1.1. Способы задания множеств............................................11
1.2. Операции над множествами............................................14
1.3. Характеристическая функция множества..........................16
1.4. Декартово произведение множеств .................................17
1.5. Понятие отображения множеств......................................20
Глава 2. Конечные и бесконечные множества ................23
2.1. Конечные множества и комбинаторика..............................23
2.2. Перестановки, размещения и сочетания............................25
2.3. Метод включений и исключений......................................27
2.4. Метод рекуррентных соотношений ..................................29
2.5. Счетные множества и производящие функции....................32
2.6. Несчетные и континуальные множества............................34
Глава 3. Отношения на, множествах ..............................36
3.1. Многоместные отношения..............................................36
3.2. Бинарные отношения на множестве . .............................38
3.3. Отношение эквивалентности (сходства) ............................41
3.4. Отношение порядка (превосходства) ................................44
Глава 4. Элементы теории графов ................................49
4.1. Определение и примеры графов......................................49
4.2. Связность графа..........................................................53
4.3. Обзор основных задач теории графов ..............................56
4.4. Расчет сетевого графика...............................................59
4.5. Плоские графы............................................................62
4.6. Сети Петри................................................................64
ЧАСТЬ II. АЛГЕБРА И ТОПОЛОГИЯ ........................71
Глава 5. Алгебры..........................................................71
5.1. Алгебраические операции..............................................71
5.2. Алгебры с одной алгебраической операцией. Группы............75
5.3. Алгебры с двумя алгебраическими операциями. Кольца
и поля....................................78
5.4. Алгебры с тремя алгебраическими операциями. Булевы алгебры................81
Глава 6. Булевы функции ...................... 84
6.1. Табличное задание булевых функций................................84
6.2. Аналитическое задание булевых функций..........................85
6.3. Полные системы булевых функций..................................87
6.4. Переключательные функции и их минимизация..................89
6.5. Схемы из функциональных элементов..............................93
Глава 7. Элементы общей топологии............... 96
7.1. Топологические пространства, сходимость к точке
и направленности.............................96
7.2. Фильтры и ультрафильтры...................... 99
7.3. Решетки..................................100
7.4. Булевы решетки подмножеств....................103
7.5. Атомы и шкалы решеток подмножеств...............105
7.6. Координатизация множества. Произведение решеток подмножеств...............................108
ЧАСТЬ III. МАТЕМАТИЧЕСКАЯ ЛОГИКА........112
Глава 8. Логика высказываний...................112
8.1. Высказывания..............................112
8.2. Формулы логики высказываний...................115
8.3. Правила преобразования формул..................116
8.4. Нормальные формы формул логики высказываний.......122
8.5. Законы логики высказываний. Тавтологии............123
Глава 9. Логика предикатов.....................125
9.1. Предикаты. Кванторы.........................125
9.2. Формулы логики предикатов.....................127
9.3. Правила преобразования формул логики предикатов......131
9.4. Законы логики предикатов. Общезначимые формулы .....135
Глава 10. Элементы теории доказательств ..........136
10.1. Аксиоматическая (формальная) теория. Исчисление предикатов...............................136
10.2. Метод резолюций ...........................141
10.3. Хорновские дизъюнкты........................144
10.4. Унификация. Метод резолюций в логике предикатов.....147
ЧАСТЬ IV. МАТЕМАТИЧЕСКАЯ КИБЕРНЕТИКА . . 150
Глава 11. Синтаксис языков.....................150
11.1. Языки...................................150
11.2. Грамматики...............................153
11.3. Автоматы ................................156
Глава 12. Теория алгоритмов....................160
12.1. Понятие алгоритма. Перечислимые и разрешимые множества ...............................160
12.2. Вычислимые функции и рекурсивные функции ........163
12.3. Вычислимые функции и машины Тьюринга...........167
12.4. Вычислимые функции и нормальные алгоритмы Маркова . . 172
12.5. Алгоритмически неразрешимые задачи и сложность алгоритмов...............................175
12.6. Задачи ..................................178
Глава 13. Элементы теории кодирования ...........180
13.1. Проблема кодирования сообщений.................180
13.2. Расстояние Хемминга.........................181
13.3. Групповые коды ............................183
13.4. Хемминговы коды...........................185
ЧАСТЬ V. МАТЕМАТИЧЕСКАЯ ИНФОРМАТИКА . . 187
Глава 14. Семантика языков. Информация о точке
и математическое моделирование баз данных . 187
14.1. Четкие сведения о точке.......................187
14.2. Четкая информация о точке.....................193
14.3. Носитель четкой информации о точке...............194
14.4. Нечеткие сведения о точке......................202
14.5. Количество информации.......................207
14.6. Данные о точке.............................210
14.7. Ультрамножество — математическая модель локальной
базы данных..............................213
Глава 15. Принятие решений. Ультраоператоры
и математическое моделирование баз знаний . .215
15.1. Ультраоператор — математическая модель локальной базы знаний..................................215
15.2. Сингулярные ультраоператоры...................217
15.3. Канонические ультраоператоры ..................220
15.4. Математическая модель распределенной базы данных
и знаний.................................223
15.5. Модель лица, принимающего решения ..............225
Глава 16. Дополнения .........................228
16.1. Интеллектуальные системы и две парадигмы математической информатики...................228
16.2. Системный анализ и целеполагание интеллектуальной системы.................................231
16.3. Системный синтез и радикалы (память) интеллектуальной системы.................................238
16.4. Функционирование интеллектуальной системы.........244
16.5. Математическое и компьютерное моделирование........247
Список литературы .............................252
