МИНИCTEPCTBO ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «СЕВЕРО-КАВКАЗСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» В. В. Бережной, А. В. Шапошников ДИСКРЕТНАЯ МАТЕМАТИКА УЧЕБНОЕ ПОСОБИЕ Направление подготовки 01.03.02 «Прикладная математика и информатика» Бакалавриат Ставрополь 2016 УДК 519.6 (075.8) ББК 22.176 я73 Б 48 Печатается по решению редакционно-издательского совета Северо-Кавказского федерального университета Бережной В. В., Шапошников А. В. <...> Пособие подготовлено в соответствии с Федеральным государственным образовательным стандартом высшего образования, раскрывает основные принципы и особенности изучения современной информатики и состоит из разделов «Множества и отношения», «Теория графов», «Комбинаторика», «Математическая логика» и «Конечные автоматы». <...> Достаточно интересно изложен раздел, посвященный теории графов, в котором большое внимание отведено прикладным задачам теории графов: определению связности вершин графа, поиску кратчайших путей, раскраске графа, потокам в сетях. <...> В разделе «Математическая логика» и «Конечные автоматы» рассмотрены аспекты использования логических функций для синтеза различных цифровых устройств. <...> - 7 - ДИСКРЕТНАЯ МАТЕМАТИКА Объекты, составляющие множество, называются его элементами или членами. <...> Множества и отношения А\В = А ∩B Дизъюнктивная сумма (симметрическая разность) А + В (или А ⊕ В) есть множество всех элементов, принадлежащих или А, или В (но не обоим вместе). <...> Дизъюнктивная сумма получается объединением элементов множеств за исключением тех, которые встречаются дважды. <...> Основные законы и аксиомы алгебры множеств Операции над множествами обладают некоторыми свойствами, которые выражаются совокупностью тождеств, представляющих основные законы и аксиомы алгебры множеств. <...> Дизъюнктивная сумма множеств А⊕В - 13 - ДИСКРЕТНАЯ МАТЕМАТИКА Рис. <...> Основными операциями над множествами являются <...>
Дискретная_математика.pdf
УДК 519.6 (075.8)
ББК 22.176 я73
Б 48
Печатается по решению
редакционно-издательского совета
Северо-Кавказского
федерального университета
Бережной В. В., Шапошников А. В.
Б 48 Дискретная математика: учебное пособие (курс лекций). – Ставрополь:
Изд-во СКФУ, – 2016. – 199 с.
Пособие подготовлено в соответствии с Федеральным государственным
образовательным стандартом высшего образования, раскрывает основные
принципы и особенности изучения современной информатики и состоит из
разделов «Множества и отношения», «Теория графов», «Комбинаторика»,
«Математическая логика» и «Конечные автоматы».
Предназначено для организации и проведения лекционных занятий по
дисциплине «Дискретная математика» для направления подготовки 01.03.02
Прикладная математика и информатика (Бакалавр). Также может быть использовано
студентами направлений 11.03.02 Инфокоммуникационные
технологии и системы связи (Бакалавр), 10.05.03 Информационная безопасность
автоматизированных систем (Специалист), 09.03.02 Информационные
системы и технологии.
УДК 519.6 (075.8)
ББК 22.176 я73
Авторы:
канд. техн. наук, доцент В. В. Бережной,
канд. техн. наук, доцент А. В. Шапошников
Рецензенты:
д-р техн. наук, проф. И. А. Калмыков,
канд. техн. наук С. В. Аникуев
(филиал МИРЭА в г. Ставрополе)
© ФГАОУ ВО «Северо-Кавказский
федеральный университет», 2016
Стр.2
СОДЕРЖАНИЕ
Предисловие ................................................................................................................. 4
ГЛАВА 1. МНОЖЕСТВА И ОТНОШЕНИЯ .................................................... 7
Множества и их спецификации ............................................................... 7
Отношения ..................................................................................................20
Виды отношений .......................................................................................28
Отображения и функции ........................................................................38
ГЛАВА 2. ТЕОРИЯ ГРАФОВ ...............................................................................47
Введение в теорию графов ......................................................................47
Связность графов ......................................................................................63
Маршруты и пути в графе .....................................................................76
Раскраска графов .......................................................................................91
Потоки в графах ........................................................................................98
ГЛАВА 3. КОМБИНАТОРИКА ........................................................................106
Основы комбинаторики ........................................................................106
Методы решения комбинаторных задач ............................................118
Комбинаторные алгоритмы ...................................................................127
ГЛАВА 4. МАТЕМАТИЧЕСКАЯ ЛОГИКА ....................................................135
Основы математической логики ..........................................................135
Преобразование логических функций ..............................................147
Минимизация логических функций аналитическим методом ...156
Минимизация ЛФ методом карт Карно ............................................164
ГЛАВА 5. КОНЕЧНЫЕ АВТОМАТЫ .............................................................174
Конечные автоматы без памяти ..........................................................174
Конечные автоматы с памятью ............................................................183
ЗАКЛЮЧЕНИЕ .......................................................................................................198
Стр.3
ДИСКРЕТНАЯ МАТЕМАТИКА
ПРЕДИСЛОВИЕ
Учебное пособие по дисциплине «Дискретная математика. Курс
лекций» подготовлено в соответствии с Федеральным государственным
образовательным стандартом высшего профессионального образования.
Дисциплина
«Дискретная математика» имеет целью сформировать
у студентов в систематизированной форме понятия об основных
дискретных математических структурах: множествах, комбинаторных
объектах, графах, логических функциях, дискретных автоматах,
изучить методы решения тождеств с множествами, комбинаторных
задач, экстремальных задач теории графов, синтеза логических функций
и дискретных автоматов.
Изучение дисциплины способствует выработке умений применять
методы дискретной математики для решения задач возникающих в
процессе математического моделирования явлений конкретной предметной
области, использованию алгоритмов дискретной математики
для разработки вычислительных программ в различных сферах деятельности
человека.
Дисциплина «Дискретная математика» относится к базовой части
Б.1 Блока дисциплин (модулей) ОП подготовки студентов по направлению
01.03.02 «Прикладная математика и информатика».
В ходе изучения дисциплины «Дискретная математика» необходимо
использовать ранее полученные знания по дисциплинам: «Математический
анализ», «Высшая алгебра и аналитическая геометрия»,
«Основы информатики», «Алгоритмизация и программирование».
В свою очередь, знания и практические навыки, полученные в
ходе изучения дисциплины, используются студентами при освоении
дисциплин «Информационно-логические и алгоритмические основы
вычислительной техники», «Базы данных и экспертные системы»,
«Основы математического и информационного моделирования»,
«Математическое и программное обеспечение компьютерных сетей»,
«Вычислительные системы, сети и телекоммуникации».
- 4 -
Стр.4
Предисловие
Освоение дисциплины «Дискретная математика» позволит будущему
бакалавру по направлению подготовки 01.03.02 – «Прикладная
математика и информатика» полноценно осуществлять свою профессиональную
деятельность, в частности, обладать следующими общепрофессиональными
и профессиональными компетенциями:
Общепрофессиональные компетенции (ОПК)
1. Способностью приобретать новые научные и профессиональные
знания, используя современные образовательные и информационные
технологии (ОПК-2).
2. Способностью к разработке алгоритмических и программных
решений в области системного и прикладного программирования,
математических, информационных и имитационных
моделей, созданию информационных ресурсов глобальных
сетей, образовательного контента, прикладных баз данных,
тестов и средств тестирования систем и средств на соответствие
стандартам и исходным требованиям (ОПК-3).
Профессиональные компетенции (ПК)
1. Способностью понимать, совершенствовать и применять современный
математический аппарат (ПК-2).
2. Способностью к разработке и применению алгоритмических
и программных решений в области системного и прикладного
программного обеспечения (ПК-7).
Учебное пособие представляет курс лекций по одноименной дисциплине
и включает все темы и разделы дисциплине согласно рабочей
программы.
В учебном пособии изложены основы теории множеств и отношений
между элементами этих множеств, приведены свойства и виды
отношений. Достаточно интересно изложен раздел, посвященный теории
графов, в котором большое внимание отведено прикладным задачам
теории графов: определению связности вершин графа, поиску
кратчайших путей, раскраске графа, потокам в сетях. В комбинаторике
рассмотрены не только математические подходы решению комбинаторных
алгоритмов, но и приведены алгоритмы генерации выборок
элементов. В разделе «Математическая логика» и «Конечные
автоматы» рассмотрены аспекты использования логических функций
для синтеза различных цифровых устройств.
- 5 -
Стр.5
ДИСКРЕТНАЯ МАТЕМАТИКА
Данное учебное пособие будет полезным не только для студентов
бакалавриата направления 01.03.02 «Прикладная математика и информатика»,
но и для студентов практически всех направлений Института
информационных технологий и телекоммуникаций, также
изучающих дисциплину «Дискретная математика».
- 6 -
Стр.6