Дискретная
математика. Кулабухов С.Ю. 151 с.
Учебник
состоит из одного файла формата
PDF, запакованного WinZip. Скачать.
Главы
конспекта разбиты на параграфы, соответствующие, как правило, одной лекции.
Структура каждого параграфа такова: ключевые моменты параграфа, краткая
теория, новые термины, контрольные вопросы, упражнения. Контрольные вопросы
содержат задания, рассчитанные, как правило, на устное их решение в случае
усвоения основ краткой теории. Упражнения носят более глубокий характер и
рассчитаны как на закрепление прочитанного материала, так и на приобретение
определенных вычислительных навыков.
Содержание
Глава
I Введение в теорию
множеств..................8
§
1. Основные понятия теории
множеств..................8
1.1. Первичные понятия теории
множеств...................8
1.2. Равенство множеств. Пустое
множество..............8
1.3. Способы задания
множеств...................................8
1.4. Отношение включения
множеств.........................9
1.5. Свойства отношения
включения..........................9
1.6. Операции над
множествами.................................10
1.7. Свойства операций над
множествами................10
1.8. Количество элементов объединения
множеств..11
1.9. Алгебры
множеств...............................12
1.10. Новые
термины....................................13
1.11. Контрольные
вопросы........................13
1.12.
Упражнения....................................13
§
2. Соответствия, функции,
отображения..............16
2.1. Декартовы
произведения............................16
2.2.
Соответствия....................................16
2.3. Обратное
соответствие...................17
2.4. Частичные
функции........................18
2.5. Обратная частичная
функция........19
2.6. Функции (отображения)................19
2.7. Обратимые
отображения..............20
2.8. Новые
термины.............................20
2.9. Контрольные
вопросы.................20
2.10. Упражнения..................................21
§
3. Суперпозиция соответствий.
Преобразования...22
3.1. Полные образы и прообразы
множеств..................22
3.2. Суперпозиция
соответствий...........................22
3.3. Ассоциативность суперпозиции
соответствий.....23
3.4. Суперпозиция
функций..............................23
3.5. Свойства тождественной и обратной
функции......23
3.6. Преобразования...................................24
3.7. Преобразования конечных
множеств......................25
3.8.
Подстановки.....................................25
3.9. Новые
термины...............................26
3.10. Контрольные
вопросы...................26
3.11.
Упражнения....................................26
§
4. Отношения эквивалентности и
разбиения на классы.......28
4.1. Бинарные
отношения.....................28
4.2. Разбиения на
классы......................28
4.3. Классы
эквивалентности..............29
4.4.
Фактормножество.........................29
4.5. Разбиения и фактормножества....30
4.6. Новые
термины............................30
4.7. Контрольные
вопросы................30
4.8.
Упражнения.................................31
§
5. Отношение порядка...................32
5.1. Основное
определение..............32
5.2. Упорядоченные
множества.......32
5.3. Линейные и вполне упорядоченные
множества...33
5.4.
Решетки.....................................35
5.5. Новые
термины.......................35
5.6. Контрольные
вопросы...........36
5.7.
Упражнения............................36
§
6. Кардинальные
числа............37
6.1. Учение о
мощности...............37
6.2. Сравнение кардинальных
чисел.................37
6.3. Теорема Кантора-Бернштейна....................38
6.4. Операции над кардинальными
числами...39
6.5. Свойства операций над кардинальными
числами....39
6.6. Новые
термины...............................40
6.7. Контрольные
вопросы...................41
6.8.
Упражнения....................................41
Глава
II Основы
комбинаторики.......................42
§
1. Основной принцип комбинаторики. Перестановки,
размещения и сочетания
1.1. Основной принцип
комбинаторики.........42
1.2. Количество подмножеств данного
множества.......44
1.3.
Размещения.....................................44
1.4.
Перестановки.................................45
1.5.
Сочетания......................................46
1.6. Некоторые свойства
сочетаний..47
1.7. Новые термины............................47
1.8.
Упражнения.................................48
§
2. Размещения, перестановки и сочетания
с повторениями. Бином Ньютона и полиномиальная
формула.................50
2.1. Размещения с повторениями.....50
2.2. Перестановки с
повторениями.50
2.3. Сочетания с
повторениями......51
2.4. Бином
Ньютона.........................52
2.5. Полиномиальная
теорема........53
2.6. Биномиальные
тождества.......54
2.7. Новые
термины.......................54
2.8.
Упражнения............................54
Глава
III Алгебра
высказываний...................56
§
1. Построение алгебры
высказываний........56
1.1. Простые и составные высказывания.
Высказывательные переменные..... 56
1.2. Основные логические
связки.......................56
1.3. Логические операции над
высказываниями...56
1.4. Формулы и их логические
возможности.........56
1.5. Равносильные формулы................................58
1.6. Тавтологии и противоречия. Таблицы
истинности.....59
1.7. Свойства логических операций (законы
логики).........59
1.8. Алгебра
высказываний................60
1.9. Новые
термины............................60
1.10. Контрольные
вопросы................60
1.11.
Упражнения.................................61
§
2. Совершенные нормальные формы.
Применение алгебры высказываний к переключательным
схемам............63
2.1. Построение формул по заданным таблицам
истинности............. 63
2.2. Нормальные
формы....................64
2.3. Совершенные нормальные формы......64
2.4. Представление формул алгебры высказываний
совершенными нормальными формами
2.5. Логические операции над двухполюсными
переключателями.......... 65
2.6. Задачи синтеза и анализа переключательных
схем................ 66
2.7. Новые
термины...........................67
2.8. Контрольные
вопросы...............67
2.9.
Упражнения................................68
§
3. Полные системы
связок..........69
3.1. Определение полной системы
связок.....69
3.2. Свойства полных систем
связок..............69
3.3. Описание полных систем связок из
0.....70
3.4. Одноэлементные полные системы
связок.....70
3.5. Исключительность связок & и V.....................71
3.6. Новые
термины....................................72
3.7. Контрольные
вопросы........................73
3.8.
Упражнения.......................................73
Глава
IV Булевы
функции.....................74
§
1. Булевы функции. Реализация булевых
функций формулами .... 74
1.1. Определение и примеры булевых
функций...........74
1.2. Существенные и несущественные
переменные....75
1.3. Реализация булевых функций формулами..............75
1.4. Равносильные
формулы..........................76
1.5. Подстановка и
замена.............................77
1.6. Принцип
двойственности.....................78
1.7. Новые термины...................................78
1.8. Контрольные
вопросы.......................78
1.9.
Упражнения.....................................79
§
2. Полные классы булевых
функций.............80
2.1. Выражение булевых функций через отрицание,
конъюнкцию и дизъюнкцию
2.2. Нормальные формы булевых
функций..........81
2.3. Замкнутые и собственные классы булевых
функций.....81
2.4. Полные классы булевых функций.......83
2.5. Новые
термины....................................85
2.6. Контрольные
вопросы.......................85
2.7.
Упражнения...................................85
Глава
V Исчисление
высказываний..........86
§
1. Язык и аксиомы исчисления
высказываний. Теорема дедукции.
86
1.1. Формальные и содержательные аксиоматические
теории.........86
1.2. Принцип построения формальных
аксиоматических теорий....86
1.3. Выводимость из множества
формул.....................87
1.4. Язык
ИВ......................................87
1.5. Аксиомы и правила вывода
ИВ.......88
1.6. Пример выводимости в
ИВ..............88
1.7. Теорема
дедукции.............................88
1.8. Следствия из теоремы
дедукции....89
1.9. Новые термины...............................90
1.10. Контрольные
вопросы...................90
1.11.
Упражнения.....................................90
§
2. Теорема о
выводимости...............91
2.1. Закон двойного отрицания............91
2.2. Закон противоречивой
посылки...91
2.3. Закон
контрапозиции.....................91
2.4. Первое правило отрицания
импликации.....92
2.5. Обобщенное правило противоречивой
посылки.....92
2.6. Теорема о
выводимости....................93
2.7. Новые
термины.................................94
2.8. Контрольные вопросы.....................95
2.9.
Упражнения......................................95
§
3. Полнота, непротиворечивость и
разрешимость ИВ Независимость аксиом ИВ
3.1. Полнота ИВ относительно
АВ........96
3.2. Непротиворечивость
ИВ.................97
3.3. Разрешимость
ИВ.............................97
3.4. Независимость системы аксиом
ИВ.....97
3.5. Многозначные
логики...........................98
3.6. й-значные
логики..................................99
3.7. Новые
термины....................................99
3.8. Контрольные
вопросы........................99
3.9. Упражнения......................................100
Глава
VI Алгебра
предикатов.........................................................101
§
1. Понятие предиката. Операции над
предикатами............... 101
1.1. Высказывательные
формы................101
1.2. Определение
предиката....................101
1.3. Логические возможности и таблица истинности
предиката..... 102
1.4. Способы задания
предикатов..........103
1.5. Предикатные переменные...............103
1.6. Общие логические возможности двух
предикатов................. 103
1.7. Операции -., &, V, ->•, ~.................103
1.8. Кванторные операции над
предикатами...................... 104
1.9. Новые
термины..............................104
1.10. Контрольные
вопросы..................105
1.11.
Упражнения...................................106
§
2. Язык алгебры предикатов.
Классификация формул ....... 107
2.1. Определение
формулы.................107
2.2. Интерпретации языка алгебры
предикатов..................... 107
2.3. Классификация формул.
Модели........................... 108
2.4. Новые термины............................109
2.5. Контрольные
вопросы................109
2.6.
Упражнения.................................110
§
3. Равносильные формулы алгебры
предикатов...................... 111
3.1. Равносильные формулы алгебры
предикатов.................... 111
3.2. Теорема о подстановках в равносильные
формулы алгебры высказываний. .
3.3. Независимость формул от связанных
переменных................. 112
3.4. Вынесение отрицания за
кванторы......................... 112
3.5. Вынесение кванторов за операции конъюнкции
и дизъюнкции.......... 112
3.6. Перестановка
кванторов.............113
3.7. Новые термины...........................113
3.8. Контрольные
вопросы...............113
3.9.
Упражнения................................113
§
4. Предваренная нормальная
форма............................. 115
4.1. Приведенная форма для формул алгебры
предикатов............... 115
4.2. Предваренная нормальная
форма.......................... 115
4.3. Новые
термины..........................117
4.4. Контрольные
вопросы..............117
4.5. Упражнения...............................117
§
5. Теории первого
порядка..........118
5.1. Термы и формулы теорий первого
порядка..................... 118
5.2. Терм, свободный для переменной в формуле.................... 119
5.3. Аксиомы и правила вывода теорий первого
порядка............... 119
5.4. Области интерпретации и
модели.......................... 120
5.5. Непротиворечивость, полнота и
неразрешимость исчислений предикатов первого
порядка
5.6. Формальная
арифметика..........121
5.7. Примеры выводов в формальной арифметике
5.................. 123
5.8. Теорема Гёделя о неполноте формальной
арифметики 5............. 123
5.9. Новые
термины........................124
Глава
VII
Основы теории
алгоритмов.................................................125
§
1. Рекурсивные функции .......125
1.1. Интуитивное понятие
алгоритма..........................
125
1.2. Необходимость уточнения понятия
алгоритма................... 126
1.3. Простейшие
функции.............126
1.4. Оператор суперпозиции....................126
1.5. Оператор примитивной рекурсии 127
1.6. Оператор
минимизации....................128
1.7. Частично рекурсивные функции. Тезис
Чёрча.................. 129
1.8. Новые
термины..................................129
1.9. Контрольные
вопросы......................129
1.10.
Упражнения....................................130
§
2. Машины
Тьюринга........................131
2.1. Определение машины
Тьюринга..131
2.2. Машинные слова
(конфигурации).............131
2.3. Модель машины
Тьюринга........................132
2.4. Работа модели машины Тьюринга............132
2.5. Вычислимые по Тьюрингу
функции........134
2.6. Новые
термины.....................................
135
2.7. Контрольные
вопросы..............................135
2.8. Упражнения....................................... 136
§
3. Нормальные алгоритмы
Маркова.............................
137
3.1. Марковские
подстановки...............................
137
3.2. Определение нормального алгоритма
Маркова................... 138
3.3. Примеры нормальных алгоритмов
Маркова.................... 138
3.4. Нормально вычислимые
функции...........139
3.5. Принцип нормализации
Маркова...........140
3.6. Новые термины..................................140
3.7. Контрольные
вопросы......................140
3.8.
Упражнения......................................141
§
4. Алгоритмически неразрешимые
проблемы........................ 142
4.1. Невычислимые функции...............................142
4.2. Пример невычислимой
функции.................143
4.3. Рекурсивные
множества...............................143
4.4. Общезначимые формулы алгебры
предикатов................... 144
4.5. Диофантовы
уравнения................................145
4.6. Новые
термины....................................145
4.7. Контрольные
вопросы........................145
4.8.
Упражнения......................................146
Глава
А Алфавиты.....................................................................147
Глава
В Предметный
указатель..................................................... 148
|
