- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3.Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Комбинаторика
- •5.1. Перестановки
- •5.2. Перестановки с неограниченными повторениями
- •5.3. Размещения
- •5.4. Сочетания
- •5.5. Сочетания с повторениями
- •5.6. Производящие функции для сочетаний
- •5.7. Производящие функции для перестановок
- •5.8. Циклы перестановок
- •Общее число дубликатов
- •5.9. Принцип включений и исключений
- •Почему появился ?
- •Задачи и упражнения
- •6. Алгебра высказываний
- •6.1. Операции над высказываниями
- •6.2. Правила записи сложных формул
- •6.3. Таблицы истинности
- •6.4. Равносильность формул
- •6.5. Дизъюнктивные и конъюнктивные нормальные формы
- •6.5.1. Алгоритм приведения пф к нормальным формам
- •6.5.2. Аналитический способ приведения к сднф
- •6.5.3. Табличный способ приведения к сднф
- •6.5.4. Табличный способ приведения к скнф
- •6.6. Логическое следствие
- •Задачи и упражнения
- •7. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •394026 Воронеж, Московский просп., 14
Е.Д. Федорков О.В. Собенина Н.Н. Свиридова
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Воронеж 2005
Воронежский государственный технический
университет
Е.Д. Федорков О.В. Собенина Н.Н. Свиридова
ДИСКРЕТНАЯ МАТЕМАТИКА
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
Воронеж 2005
УДК 519.1
Федорков Е.Д., Собенина О.В., Свиридова Н.Н. Дискретная математика: Учеб. пособие. Воронеж: Воронеж. гос. техн. ун-т, 2005. 215 с.
В учебном пособии излагаются основы современной дискретной математики: теория множеств, теория отношений, теория графов, комбинаторика, алгебра логики. Каждый раздел иллюстрирован примерами, содержит задачи и упражнения для развития навыков решения основных типов задач. Издание соответствует требованиям Государственного образовательного стандарта высшего профессионального образования по направлению 654600 «Информационные системы», специальности 230202 «Информационные технологии в образовании», дисциплине «Дискретная математика».
Издание может быть полезно студентам других технических специальностей, изучающих курс «Дискретная математика».
Учебное пособие подготовлено на магнитном носителе в текстовом редакторе MS WORD 2000 и содержится в файле «Дискретная математика.doc».
Ил. 85. Библиогр.: 8 назв.
-
Рецензенты:
зам. директора ВНИИС по науке д-р техн. наук И.И. Малышев;
канд. физ.-мат. наук, доц. В.Н. Дурова
Федорков Е.Д., Собенина О.В.,
Свиридова Н.Н., 2005
Оформление. ГОУВПО
«Воронежский государственный
технический университет», 2005
Введение
Дискретная математика – область математики, занимающаяся изучением свойств дискретных структур, которые возникают как внутри математики, так и в ее приложениях. Дискретность (от лат discretus – разделенный, прерывистый) – прерывность; противопоставляется непрерывности. Например, система целых чисел (в противоположность системе действительных чисел) является дискретной; дискретное изучение какой-либо величины во времени – это изменение, происходящее через определенные промежутки времени (скачками).
В отличие от дискретной математики классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической математики или дискретной математики как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь, и в связи с этим, какую модель изучаемого явления он рассматривает: дискретную или непрерывную.
Дискретная математика представляет собой важное направление в математике, в котором можно выделить характерные для дискретной математики предметы исследования, методы и задачи, специфика которых обусловлена в первую очередь необходимостью отказа в дискретной математике от основополагающих понятий классической математики – предела и непрерывности. В связи с этим для многих задач дискретной математики сильные средства классической математики оказываются, как правило, малоприемлемыми.
Элементы дискретной математики возникли в глубокой древности. Развиваясь с другими разделами математики, они явились их составной частью. Типичными для того времени были задачи, связанные со свойствами целых чисел и приведшие затем к созданию теории чисел. К их числу могут быть отнесены отыскания алгоритмов сложения и умножения натуральных чисел (2-е тыс. до н. э.), задачи о суммировании и вопросы делимости натуральных чисел в пифагорейской школе (6 в. до н. э.) и т.д.
Стремление к строгости математических рассуждений и анализ рабочего инструмента математики – логики – привели к выделению еще одного важного раздела математики – математической логики (19-20 вв.).
Однако наибольшего развития дискретная математика достигла в связи с запросами практики, приведшими к появлению новой науки – кибернетики и ее теоретической части – математической кибернетики (20 в.)
Дискретная математика включает в себя такие математические разделы, как теория множеств и отношений, теория графов, теория алгоритмов, комбинаторный анализ, математическую логику и другие, которые наиболее интенсивно стали развиваться в связи с внедрением вычислительной техники. Теория графов является эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством и дискретной оптимизации. Широкое применение дискретная математика нашла в современной вычислительной технике: в теоретическом программировании, при проектировании ЭВМ и сетей ЭВМ, баз данных, систем логического управления. Элементы математической логики применяются при решении проблем функционально-логического проектирования.