ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ И НАУКИ
ХАНТЫ-МАНСИЙСКОГО АВТОНОМНОГО ОКРУГА – ЮГРЫ
БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
ХАНТЫ-МАНСИЙСКОГО АВТОНОМНОГО ОКРУГА – ЮГРЫ
«СУРГУТСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»
А.В. Иванова
С.А. Курманова
ДИСКРЕТНАЯ МАТЕМАТИКА
В ПРИМЕРАХ И ЗАДАЧАХ
УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ
Направления подготовки
44.03.05 Педагогическое образование
(с двумя профилями подготовки)
Направленность
«Математика и Информатика»
Сургут, 2023
Стр.1
УДК 519.8:378.147(075.8)
ББК 22.18р30я73-9
И 18
Печатается по решению
Редакционно-издательского совета
БУ «Сургутский государственный
педагогический университет»
Рецензенты:
Мугаллимова Светлана Ринатовна, кандидат педагогических наук, доцент,
заведующий кафедрой высшей математики и информатики
Сургутский государственный педагогический университет
Далингер Виктор Алексеевич, доктор педагогических наук, профессор,
профессор кафедры математики и методики обучения математике
Омский государственный педагогический университет
И 18 Дискретная математика в примерах и задачах : учебно-методическое пособие : направление
подготовки 44.03.05 Педагогическое образование (с двумя профилями подготовки),
направленность «Математика и Информатика» / А. В. Иванова, С. А. Курманова ; Департамент
образования и науки ХМАО – Югры, Бюджетное учреждение высшего образования
ХМАО – Югры «Сургутский государственный педагогический университет». – Сургут :
РИО БУ «Сургутский государственный педагогический университет», 2023. – 95, [1] с. –
Текст : непосредственный.
Иванова, А. В.
Учебно-методическое пособие включает теоретические и практические материалы
для организации лекционных, практических, семинарских и самостоятельных занятий по дисциплине
«Дискретная математика». Пособие состоит из трех разделов, каждый из которых содержит
главы и параграфы с теоретическим материалом, примерами решения типовых задач,
задания для самостоятельного выполнения и вопросы для самопроверки, позволяющие проверить
усвоение изложенного материала.
Пособие предназначено для бакалавров направления подготовки 44.03.05 Педагогическое
образование (с двумя профилями подготовки), направленность «Математика и Информатика».
УДК 519.8:378.147(075.8)
ББК 22.18р30я73-9
© Иванова А.В., Курманова С.А., 2023
© БУ «Сургутский государственный педагогический университет», 2023
2
Стр.2
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ ...................................................................................................................................................... 4
ГЛАВА 1. АЛГЕБРА ЛОГИКИ ............................................................................................................................... 6
1.1 ЛОГИКА ВЫСКАЗЫВАНИЙ ............................................................................................................................ 6
1.1.1 ЛОГИЧЕСКИЕ ОПЕРАЦИИ, ФОРМУЛЫ ЛОГИКИ .................................................................................... 6
1.1.2 НОРМАЛЬНЫЕ ФОРМЫ ............................................................................................................................. 11
1.2 БУЛЕВЫ ФУНКЦИИ ....................................................................................................................................... 19
1.2.1 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ .................................................................................................. 19
1.2.2 ПОЛНОТА МНОЖЕСТВ БУЛЕВЫХ ФУНКЦИЙ ....................................................................................... 23
1.2.3 РЕЛЕЙНО-КОНТАКТНЫЕ СХЕМЫ ........................................................................................................... 27
1.3 ЛОГИКА ПРЕДИКАТОВ ................................................................................................................................. 34
1.3.1 ПРЕДИКАТЫ. ОПЕРАЦИИ НАД ПРЕДИКАТАМИ .................................................................................. 34
1.3.2 ВЫСКАЗЫВАНИЯ С КВАНТОРАМИ ........................................................................................................ 36
ГЛАВА 2. ТЕОРИЯ ОТОБРАЖЕНИЙ И АЛГЕБРА ПОДСТАНОВОК ............................................................... 41
2.1 БИНАРНЫЕ ОТНОШЕНИЯ ............................................................................................................................ 41
2.2 ТЕОРИЯ ОТОБРАЖЕНИЙ И АЛГЕБРА ПОДСТАНОВОК ........................................................................... 46
2.2.1 ОТОБРАЖЕНИЯ И ИХ СВОЙСТВА ........................................................................................................... 46
2.2.2 АЛГЕБРА ПОДСТАНОВОК ......................................................................................................................... 47
ГЛАВА 3. ТЕОРИЯ ГРАФОВ ................................................................................................................................ 51
3.1 ГРАФЫ И ИХ ПРЕДСТАВЛЕНИЕ ................................................................................................................. 51
3.1.1 ВИДЫ ГРАФОВ ............................................................................................................................................ 51
3.1.2 СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ ................................................................................................... 54
3.2 ОПЕРАЦИИ НАД ГРАФАМИ ......................................................................................................................... 59
3.2.1 БИНАРНЫЕ ОПЕРАЦИИ НАД ГРАФАМИ ................................................................................................ 59
3.2.2 УНАРНЫЕ ОПЕРАЦИИ НАД ГРАФАМИ .................................................................................................. 60
3.3 СВЯЗНОСТЬ ГРАФА ....................................................................................................................................... 64
3.4 ДЕРЕВЬЯ. МИНИМАЛЬНЫЙ ОСТОВ ........................................................................................................... 72
3.5 ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ГРАФЫ ОБХОДЫ ГРАФОВ ................................................................. 79
3.5.1 ПОСТРОЕНИЕ ЭЙЛЕРОВА ЦИКЛА ........................................................................................................... 79
3.5.2 ПОИСК ГАМИЛЬТОНОВА ЦИКЛА ........................................................................................................... 80
3.5.3 ОБХОДЫ ГРАФОВ ....................................................................................................................................... 80
3.6 РАСКРАСКА ГРАФА ...................................................................................................................................... 87
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ .................................................................................................... 95
3
Стр.3
Математика учит точности мысли, подчинению логике
доказательства, понятию строго обоснованной истины,
а всё это формирует личность, пожалуй, больше, чем
музыка.
А.Д. Александров
ПРЕДИСЛОВИЕ
Дискретная математика – это раздел математики, изучающий свойства дискретных структур,
которые возникают как в самой математике, так и в её приложениях. Анализ школьных программ
и учебных пособий по информатике и математике показал необходимость серьезной подготовки будущих
учителей математики и информатики в области дискретной математики.
Так, например, в школьных курсах информатики и математики нашли свое отражение вопросы,
связанные с содержанием таких разделов дискретной математики как «Комбинаторный анализ»
(задачи на различные способы предъявления объектов, на подсчет комбинаций, задачи на классификацию,
на разрезание и перекладывание фигур и т.д., бином Ньютона), «Математическая
логика» (формальный язык нулевого порядка, конечные функции, метод математической индукции),
«Алгебраические системы», «Теория графов» (использование графов для описания информационных
процессов, задача о кенигсбергских мостах, задача коммивояжера, задача о раскраске карт),
«Теория кодирования» (алфавитное кодирование, системы счисления, криптография), «Теория алгоритмов»
(элементы дескриптивной теории алгоритмов), «Теория формальных языков» (формальная
система, интерпретация формальной системы).
Дисциплина «Дискретная математика» включена в учебный план по направлению подготовки
44.03.05 Педагогическое образование (с двумя профилями подготовки), направленность Математика
и Информатик» в часть, формируемую участниками образовательных отношений.
Цель изучения данной дисциплины заключается в освоении способов математической деятельности
на основе фундаментальных понятий и положений дискретной математики для решения
задач профессиональной деятельности.
Задачи:
формирование умения применять методы алгебры логики, необходимые для реализации
образовательной программы;
овладение системой основных математических понятий методов теории отображений
и алгебры подстановок, необходимых для реализации образовательной программы;
освоение способов применения алгоритмов теории графов для решения профессиональных
задач.
Процесс освоения дисциплины направлен на формирование следующих компетенций:
ПК-1 - способен осуществлять обучение по образовательной программе на основе использования
современных подходов и образовательных технологий;
ПК-4 - способен развивать культуру мышления в процессе освоения математической деятельности
на основе взаимопереходов знаковых систем.
В результате изучения дисциплины обучающийся овладеет следующими компонентами
компетенций:
знать:
− содержание разделов дискретной математики;
− основную терминологию дискретной математики;
− правила символьной записи математических текстов на языке дискретной математики;
− исторические факты по становлению и развитию разделов дискретной математики;
− способы решения различных задач на изучение дискретных математических объектов
и структур для осуществления внутри модельного решения;
− приложения дискретной математики для интерпретации полученного решения задач;
− фундаментальные основы дискретной математики;
уметь:
− осуществлять и фиксировать взаимопереходы знаковых систем в процессе изучения дискретных
математических объектов и структур;
4
Стр.4
− осуществлять математическое моделирование при изучении дискретных математических
объектов и структур;
− осуществлять математические рассуждения в процессе изучения дискретных математических
объектов и структур;
владеть:
− умением выбирать способ представления математического текста с помощью знаковых
систем в процессе изучения дискретных математических объектов и структур;
− умением определять последовательность шагов для осуществления взаимопереходов знаковых
систем для решения различных задач на изучение дискретных математических объектов и
структур;
− умением осуществлять анализ и синтез математических объектов и процедур в процессе
изучения дискретных математических объектов и структур;
− умением оценивать целесообразность и корректность взаимопереходов знаковых систем
при решении различных задач на изучение дискретных математических объектов и структур;
− умением выбирать модели и методы решения задач дискретной математики;
− умением строить математические модели при решении задач дискретной математики;
− умением осуществлять внутримодельное решение задачи дискретной математики;
− умением оценивать и интерпретировать полученное решение задачи дискретной математики;
−
умением ставить цели учебной математической деятельности по изучению дискретных
математических объектов и структур;
− умением выбирать методы решения задач дискретной математики;
− умением определять последовательность шагов для решения задачи дискретной математике
на основе математических рассуждений;
− умением оценивать корректность математических рассуждений при решении различных
задач на изучение дискретных математических объектов и структур;
иметь опыт:
− осуществления взаимопереходов знаковых систем в процессе изучения дискретных математических
объектов и структур;
− оценки целесообразности и корректности взаимопереходов знаковых систем в процессе
изучения дискретных математических объектов и структур;
− построения математических моделей в процессе изучения дискретных математических
объектов и структур;
− оценки и интерпретации полученного решения задачи дискретной математики;
− логического анализа математических объектов и процедур в процессе изучения дисциплины.
Целью
данного пособия является методическая поддержка проведения лекционных, практических,
семинарских занятий по дисциплине «Дискретная математика». Содержание пособия ориентировано
на комплексное освоение теоретических основ и практических умений по дисциплине.
Пособие состоит из 3 разделов: «Алгебра логики», «Теория отображений и алгебра подстановок»,
«Теория графов». Каждый раздел содержит главы и параграфы с теоретическим материалом,
примерами решения типовых задач, задания для самостоятельного выполнения и вопросы для
самопроверки, позволяющие проверить усвоение изложенного материала.
Иллюстрации и таблицы, представленные в пособии, содержат сквозную нумерацию.
Представленные списки рекомендуемой литературы помогут обучающимся в изучении дисциплины,
при необходимости в углублении и закреплении полученных знаний.
Данное учебно-методическое пособие, в силу его содержательных и структурных особенностей,
может быть полезным учителям, обучающимся высших учебных заведений и колледжей
(в первую очередь – педагогических), обучающимся старших классов и всем, кто интересуется дискретной
математикой.
5
Стр.5