Сборник задач по дискретной математике (200,00 руб.)

Стр.2

Стр.130

Стр.131

УДК 519.1(076.1) П598 д-р физ.-мат. наук, профессор C. В. Судоплатов, канд. физ.-мат. наук, доцент Е. В. Грачёв Рецензенты: П598 Сборник задач по дискретной математике: учеб. пособие/ Е. Н.Порошенко. — 2-е изд., испр. и доп. — Новосибирск: Изд-во НГТУ, Порошенко Е. Н. 2018. — 132 c. ISBN 978-5-7782-3562-5 В пособии подобраны задачи по курсу дискретной математики, читаемому на I–II курсах НГТУ. Кроме того, в нем содержится большое количество примеров, способствующих самостоятельной работе и приобретению навыков решения задач. Работа подготовлена на кафедре алгебры и математической логики В авторской редакции УДК 519.1(076.1) ISBN 978-5-7782-3562-5 -c Порошенко Е. Н., 2013, 2018 технический-c Новосибирский государственный университет, 2013, 2018

Стр.2

Оглавление Предисловие ко второму изданию Предисловие к первому изданию Список обозначений 1 Элементы теории множеств 3 3 5 8 1.1 Множества и операции над ними . . . . . . . . . . . . . . 8 1.2 Отношения и функции . . . . . . . . . . . . . . . . . . . . 12 1.3 Матрицы бинарных отношений. Специальные бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4 Эквивалентности и порядки . . . . . . . . . . . . . . . . . 23 1.5 Изоморфизмы частично упорядоченных множеств . . . . 30 1.6 Метод математической индукции . . . . . . . . . . . . . . 32 1.7 Мощность множеств . . . . . . . . . . . . . . . . . . . . . 35 2 Алгебраические системы 40 2.1 Определение алгебраических систем. Алгебры. Группы . 40 2.2 Таблицы Кэли . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3 Гомоморфизмы и изоморфизмы алгебраических систем . 47 2.4 Подсистемы . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3 Дистрибутивные решетки и булевы алгебры 4 Числовые системы 54 59 4.1 Системы счисления . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Делимость. Алгоритм Евклида . . . . . . . . . . . . . . . 60 4.3 Линейные диофантовы уравнения. Сравнения . . . . . . 62 4.4 Многомодульная арифметика . . . . . . . . . . . . . . . . 67

Стр.130

Оглавление 5 Теория графов 131 75 5.1 Способы задания графов. Изоморфизмы графов . . . . . 75 5.2 Операции над графами . . . . . . . . . . . . . . . . . . . 83 5.3 Маршруты. Достижимость. Связность . . . . . . . . . . . 86 5.4 Остовы. Фундаментальные циклы. Фундаментальные разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.5 Расстояния в графах. Эйлеровы графы. Планарные графы 91 6 Алгебра логики 96 6.1 Формулы алгебры логики. Таблицы истинности. Эквивалентность . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.2 ДНФ и КНФ. СДНФ и СКНФ . . . . . . . . . . . . . . . 99 6.3 Тупиковые и минимальные ДНФ и КНФ . . . . . . . . . 103 6.4 Полином Жегалкина. Полные системы функций . . . . . 106 Ответы Библиографический список 109 129

Стр.131