В учебнике изложен материал, соответствующий типовым программам технических специальностей высших учебных заведений Украины, изучающих дискретную математику как фундаментальную основу многих естественных наук. На основании аксиоматики Цермело, проведен водораздел между дискретным и непрерывным в основаниях математики. Используя теоретико-множественный подход, изучаются методы математической логики, основ комбинаторного анализа и теории графов. При этом, где это возможно, значительное внимание уделено алгоритмическим методам при доказательствах теорем и решениях дискретных задач. Разделы теоретического изложения материала подкреплены практическими задачами и упражнениями. Учебник предназначен для студентов, изучающих дискретную математику как самостоятельно, так и в плане тех дисциплин, которые предусмотрены соответствующими учебными программами ВУЗов, а также может быть полезен учащимся выпускных классов лицеев, школ и гимназий, где предусмотрена усиленная подготовка в области математики. СОДЕРЖАНИЕ Предисловие 5 1 ТЕОРЕТИКО-МНОЖЕСТВЕННЫЕ ОСНОВАНИЯ дисциплины 1.1 Понятия и аксиомы теории множеств 6 1.2 Декартовы произведения, отношения и отношение эквивалентности 18 1.3 Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения 27 1.4 Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств 31 1.5 Счетные и континуальные множества 34 1.6 Ординалы и трансфиниты. Аксиома выбора и континуум- гипотеза 40 1.7 Задачи 47 2 ОСНОВЫ МАТЕМАТИЧЕСКОЙ логики 2.1 Высказывания и функции на высказываниях 51 2.2 Операции математической логики 54 2.3 Понятие формулы и свойства операций 56 2.4 Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы 58 2.5 Понятие полноты системы булевых функций 61 2.6 Исчисление предикатов 62 2.7 Введение в методы теории доказательств 64 2.8 Задачи 66 3 КОМБИНАТОРИКА 3.1 Размещения 70 3.2 Размещения без повторений 77 3.3 Перестановки и подстановки 79 3.4 Сочетания, структура соединений 83 3.5 Свойства биномиальных коэффициентов 85 3.6 Понятие производящей функции 88 3.7 Соединения с повторениями 90 3.8 Разбиения множеств 93 4 Г.Г. Асеев, О.М. Абрамов, Д.Э. Ситников. Дискретная математика 3.9 Разбиения чисел 98 3.10 Композиции чисел 101 3.11 Задачи 102 4 основы ТЕОРИИ ГРАФОВ 4.1 Основные понятия и определения 106 4.2 Графы и бинарные отношения 109 4.3 Понятие изоморфизма и изоморфизм плоских графов 112 4.4 Степени вершин графа 114 4.5 Представление графов матрицами 116 4.6 Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов 118 4.7 Маршруты, цепи, циклы и связность 123 4.8 Эйлеровы циклы и цепи 125 4.9 Гамильтоновы циклы. Оценка временной сложности алгоритмов 127 4.10 Деревья 132 4.11 Раскраска вершин и теорема Шеннона об информационной емкости графа 135 4.12 Раскраска ребер графа и теоремы о хроматическом классе 138 4.13 Задачи 140 Ответы и решения 142 Список литературы 161 Список дополнительной литературы 161