МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» А.М. Шмырин, И.А. Седых ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Учебное пособие Липецк Липецкий государственный технический университет 2014 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» А.М. Шмырин, И.А. Седых ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Учебное пособие Липецк Липецкий государственный технический университет 2014 3 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Учебное пособие Составители: _____________ А.М. Шмырин, ________________ И.А. Седых Зав. кафедрой высшей математики ______________А.М. Шмырин Липецк Липецкий государственный технический университет 4 2014 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» А.М. Шмырин, И.А. Седых ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Учебное пособие Утверждаю к печати Объем 10,0 п.л. <...> Ш 758 Лекции по дискретной математике и математической логике [Текст]: учеб. пособие / А.М. Шмырин, И.А. Седых. <...> ISBN 978-5-88247-714-0 Учебное пособие соответствует государственному образовательному стандарту дисциплин «Дискретная математика», «Математическая логика и теория алгоритмов». <...> Расширение функций переходов и выходов на множество входных слов . <...> Эквивалентность конечных <...>
Лекции_по_дискретной_математике_и_математической_логике_.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
А.М. Шмырин, И.А. Седых
ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
Учебное пособие
Липецк
Липецкий государственный технический университет
2014
3
Стр.2
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
Учебное пособие
Составители:
_____________ А.М. Шмырин,
________________ И.А. Седых
Зав. кафедрой высшей математики
______________А.М. Шмырин
Липецк
Липецкий государственный технический университет
4
Стр.3
2014
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
А.М. Шмырин, И.А. Седых
ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
Учебное пособие
Утверждаю к печати
Объем 10,0 п.л.
Тираж 100 экз.
Проректор по учебной работе
Ю.П. Качановский
« »_________________2014 г
Липецк
Липецкий государственный технический университет
2014
5
Стр.4
УДК 519(07)
Ш 758
Рецензенты:
В.Н. Малыш, д-р техн. наук, проф. Липецкого государственного
педагогического университета;
кафедра математических, естественнонаучных и экономических
дисциплин МОУ ВПО «Институт права и экономики».
Шмырин А.М.
Ш 758 Лекции по дискретной математике и математической логике [Текст]:
учеб. пособие / А.М. Шмырин, И.А. Седых. – Липецк: Изд-во Липецкого
государственного технического университета, 2014. – 159 с.
ISBN 978-5-88247-714-0
Учебное пособие соответствует государственному образовательному
стандарту дисциплин «Дискретная математика», «Математическая логика и
теория алгоритмов». Пособие содержит краткий курс дискретной математики и
математической логики. В каждом разделе приведены подробно разобранные
примеры.
Данное пособие предназначено для студентов направлений подготовки
010800.62 – «Механика и математическое моделирование», 220100.62 –
«Системный анализ и управление», а также студентов других технических
специальностей, изучающих дискретную математику.
Табл. 44. Ил. 89. Библиогр.: 17 назв.
ISBN 978-5-88247-714-0
© ФГБОУ ВПО «Липецкий
государственный
6
технический
университет», 2014
© Шмырин А.М., Седых И.А., 2014
Стр.5
Содержание
Введение ................................................................................................... 9
1. Множества ...........................................................................................11
1.1. Множества и операции над ними. Аксиомы алгебры
множеств...................................................................................11
1.2. Комплекты ................................................................................16
1.3. Нечёткие множества .................................................................17
2. Отношения и соответствия ..................................................................18
2.1. Прямое произведение ...............................................................18
2.2. Соответствия.............................................................................19
2.3. Отношения ................................................................................21
3. Графы ...................................................................................................26
3.1. Определения графов .................................................................27
3.2. Элементы графов ......................................................................31
3.3. Связность ..................................................................................33
3.4. Метрические характеристики графа .........................................39
3.5. Виды графов и операции над графами .....................................40
3.6. Деревья .....................................................................................45
3.7. Раскраска графов ......................................................................49
3.8. Планарность..............................................................................50
4. Алгоритмы на графах...........................................................................59
4.1. Обходы графов .........................................................................59
4.2. Остов минимального веса (кратчайший остов) ........................63
4.3. Кратчайшие пути ......................................................................65
5. Транспортные сети...............................................................................71
5.1. Поток в транспортной сети .......................................................72
5.2. Нахождение полного потока.....................................................74
5.3. Нахождение максимального потока .........................................75
6. Математическая логика .......................................................................77
6.1. Алгебра высказываний .............................................................77
7
Стр.6
6.2. Булевы функции .......................................................................91
6.3. Минимизация булевых функций ............................................ 122
7. Конечные автоматы ........................................................................... 128
7.1. Пример конечного автомата ................................................... 128
7.2. Понятие конечного автомата .................................................. 132
7.3. Способы задания конечного автомата .................................... 134
7.4. Расширение функций переходов и выходов на множество
входных слов .......................................................................... 139
7.5. Автоматное отображение ....................................................... 140
7.6. Изоморфизм и эквивалентность конечных автоматов............ 141
7.7. Алгоритм Мили нахождения минимального
конечного автомата................................................................ 144
7.8. Частичные автоматы и их минимизация................................. 147
7.9. Эквивалентность конечных автоматов Мили и Мура ............ 154
7.10. Представление конечных автоматов матрицами
соединений............................................................................. 156
7.11. Дерево конечного автомата.................................................... 158
7.12. Построение схем из функциональных элементов
для булевых конечных автоматов .......................................... 159
Заключение ............................................................................................ 161
Библиографический список ................................................................... 162
8
Стр.7