Спирина М. С. Дискретная математика: Учебник для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. — М., 2004. — 368 с.
Представляет собой углубленный междисциплинарный курс и содержит теоретический материал по традиционным темам дискретной математики и некоторые вопросы классической логики. В каждой главе есть исторический материал, разобранные задачи с указанием методов их решений, система упражнений для самостоятельной работы.
Для студентов и преподавателей учреждений среднего профессионального образования, связанных с информационными системами, компьютерным моделированием, разработкой программных продуктов и автоматизированных систем.
ОГЛАВЛЕНИЕ
Предисловие.................................................................3
Перечень математических символов и сокращений................................6
Введение....................................................................8
Глава 1. Множества.........................................................14
1.1. Общие понятия теории множеств......................................14
1.2. Основные операции над множествами.........................................17
1.3. Соответствия между множествами. Отображения........................20
1.4. Классификация множеств. Мощность множества........................28
1.5. Кортежи. Декартовы произведения.....................................34
1.6 Отношения. Бинарные отношения и их свойства........................38
1.7. Элементы комбинаторики...............................................45
1.8. Подстановки...........................................................55
Упражнения.....................................................................61
Глава 2. Графы...................................................................69
2.1. Основные понятия и определения графа и его элементов.........69
2.2. Операции над графами....................................................79
2.3. Деревья. Лес. Бинарные деревья..........................................80
2.4. Способы задания графа. Изоморфные фафы...............................84
2.5. Сети. Сетевые модели представления информации.....................89
2.6. Применение графов и сетей............................................91
Упражнения.........................................................................96
Глава 3. Понятия...................................................................104
3.1. Понятие как форма мышления...................................................104
3.2. Логические операции над понятиями: обобщение
и ограничение понятий...............................................................109
3.3. Отношения между понятиями.....................................................111
3.4. Операции над понятиями. Определение понятий.....................114
3.5. Деление понятий. Классификация...............................................120
Упражнения..............................................................................127
Глава 4. Математическая логика..........................................................131
4.1. Суждения как форма мышления. Простые высказывания........131
4.2. Булевы функции............................................................................133
4.3. Сложные высказывания...............................................................140
4.3.1. Операции над сложными высказываниями.......................141
4.3.2. Необходимое и достаточное условия импликации...........145
4.3.3. Формулы алгебры логики....................................................152
4.4. Законы правильного мышления..................................................156
4.5. Логика вопросов и ответов...........................................................166
4.6. Минимизация булевых функций.................................................170
4.6.1. Разложение функций по переменным. Нормальные формы..............................170
4.6.2. Логические схемы................................................................175
4.6.3. Карты Карно.........................................................................180
4.7. Сумма по модулю два...................................................................187
4.8. Полином Жегалкина. Функционально замкнутые классы........192
4.8.1. Канонический полином Жегалкина...................................192
4.8.2. Функциональная замкнутость.............................................193
4.8.3. Функционально полные системы функций.......................196
Упражнения.........................................................................................199
Глава 5. Формальные системы и умозаключения.
Логика предикатов..................................................................208
5.1. Формальные системы...................................................................208
5.2. Исчисление высказываний..........................................................219
5.3. Логика предикатов........................................................................224
5.4. Умозаключения как форма мышления. Дедуктивные умозаключения и их виды...............................243
5.4.1. Непосредственные умозаключения по логическому квадрату.............................................245
5.4.2. Простые категорические силлогизмы..................................249
5.4.3. Энтимемы..............................................................................250
5.4.4. Умозаключения из сложных суждений................................251
5.4.5. Применение аппарата алгебры высказываний для
работы с умозаключениями.................................................254
5.5. Методы научного познания.........................................................258
5.6. Индуктивные умозаключения и их виды....................................262
5.6.1. Виды индукции......................................................................263
5.6.2. Методы установления причинных связей...........................265
5.6.3. Формальная аксиоматическая теория для арифметики натуральных чисел................................................................267
5.6.4. Метод математической индукции........................................270
5.6.5. Статистические обобщения..................................................276
5.7. Виды аналогии. Моделирование как метод................................278
5.8. Гипотезы......................................................................281
Упражнения.........................................................................284
Глава 6. Элементы теории и практики кодирования............................289
6.1. История кодирования от древности до наших дней. Защита информации............................289
6.2. Системы счисления для представления информации в ЭВМ ... 295
6.3. Основные понятия вероятностной теории информации..........300
6.4. Обработка сообщений как кодирование.....................................309
6.5. Кодирование информации как средство обеспечения контроля работы автомата.......................312
6.6. Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам.....................327
Упражнения..............................................................336
Глава 7. Конечные автоматы..................................................341
7.1. Определение конечных автоматов...............................................341
7.2. Способы задания конечных автоматов.......................................347
7.3. Общие задачи теории автоматов.................................................351
Упражнения........................................................................357
Заключение......................................................................358
Предметный указатель...............................................................361
Список литературы...................................................................366
