Лекции по дискретной математике и математической логике (190,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

Стр.7

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» А.М. Шмырин, И.А. Седых ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Учебное пособие Липецк Липецкий государственный технический университет 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