Дискретная математика (250,00 руб.)

Стр.2

Стр.3

Стр.127

Стр.128

Министерство образования и науки Российской Федерации Сибирский федеральный университет А. В. Васильева, И. В. Шевелева ДИСКРЕТНАЯ МАТЕМАТИКА Учебное пособие Красноярск СФУ 2016

Стр.2

УДК 519(07) ББК 22.174я73 В191 Рецензенты: В. Р. Майер, доктор педагогических наук, заведующий кафедрой алгебры, геометрии и методики их преподавания КГПУ им. В. П. Астафьева; цент кафедры высшей математики и информатики СибГТУ Васильева, А. В. В191 Ю. В. Казаков, кандидат физико-математических наук, доДискретная математика : учеб. пособие / А. В. Васильева, И. В. Шевелева. – Красноярск : Сиб. федер. ун-т, 2016. – 128 с. ISBN 978-5-7638-3511-3 Изложен теоретический материал по разделам дискретной математики: множества, отношения, математическая логика, графы, который проиллюстрирован большим количеством примеров. Каждый раздел завершается вопросами и заданиями для самоконтроля. Приведены задания для самостоятельной работы. Предназначено для студентов укрупненных групп направлений подготовки 11.00.00 «Электроника, радиотехника и системы связи»(11.03.01 «Радиотехника», 11.03.02 «Инфокоммуникационные технологии и системы связи», 11.03.03 «Конструирование и технология электронных средств», 11.05.11 «Радиоэлектронные системы и комплексы»), 12.00.00 «Фотоника, приборостроение, оптические и биотехнические системы и технологии» (12.03.01 «Приборостроение»), направлений 09.03.03 «Прикладная информатика», 38.03.05 «Бизнес-информатика», 15.03.06 «Мехатроника и робототехника», специальности 25.05.03 «Техническая эксплуатация транспортного радиооборудования». Электронный вариант издания см.: http://catalog.sfu-kras.ru УДК 519(07) ББК 22.174я73 ISBN 978-5-7638-3511-3 уни-c Сибирский федеральный верситет, 2016

Стр.3

ОГЛАВЛЕНИЕ Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Элементы теории множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Понятие множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Отношение включения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Способы задания множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4. Операции над множествами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5. Эквивалентность множеств. Понятие мощности . . . . . . . . . . . 11 Вопросы и задания для самоконтроля . . . . . . . . . . . . . . . . . . . . 16 2. Отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1. Понятие отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2. Бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3. Способы заданий бинарных отношений . . . . . . . . . . . . . . . . . . . . 19 2.4. Свойства бинарных отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5. Отношение эквивалентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.6. Отношение порядка. Упорядоченные множества . . . . . . . . . . 26 2.7. Функции и отображения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.8. Операции. Понятие алгебры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Вопросы и задания для самоконтроля . . . . . . . . . . . . . . . . . . . . 35 3. Элементы математической логики . . . . . . . . . . . . . . . . . . . . . 37 3.1. Моделирование высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2. Таблицы истинности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3. Равносильные формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4. Полные системы связок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5. Равносильные преобразования логических формул . . . . . . . . 45 3.6. Функции алгебры логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.7. Разложение логической функции по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ) . . . . . . . . . . . . . 50 3.8. Двойственность. Принцип двойственности . . . . . . . . . . . . . . . . 52 3.9. Дизъюнктивные и конъюнктивные нормальные формы. Проблема минимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.10. Многочлен Жегалкина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.11. Некоторые приложения алгебры логики . . . . . . . . . . . . . . . . . . 65 3.12. Предикаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Вопросы и задания для самоконтроля . . . . . . . . . . . . . . . . . . . . 76 4. Элементы теории графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.1. Историческая справка и основные понятия . . . . . . . . . . . . . . . 77 4.2. Способы задания графов. Изоморфизм графов . . . . . . . . . . . 80 126

Стр.127

4.3. Маршруты, цепи, циклы в графах . . . . . . . . . . . . . . . . . . . . . . . . 86 4.4. Понятие связности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.5. Взвешенные графы. Нахождение кратчайших маршрутов . 94 4.6. Обходы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.7. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Вопросы и задания для самоконтроля . . . . . . . . . . . . . . . . . . . 104 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . 105 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Библиографический список. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 127

Стр.128